Queue.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / clr / src / BCL / System / Collections / Queue.cs / 1305376 / Queue.cs

                            // ==++== 
//
//   Copyright (c) Microsoft Corporation.  All rights reserved.
//
// ==--== 
/*==============================================================================
** 
** Class: Queue 
**
** [....] 
**
** Purpose: A circular-array implementation of a queue.
**
** 
=============================================================================*/
namespace System.Collections { 
    using System; 
    using System.Security.Permissions;
    using System.Diagnostics; 
    using System.Diagnostics.Contracts;

    // A simple Queue of objects.  Internally it is implemented as a circular
    // buffer, so Enqueue can be O(n).  Dequeue is O(1). 
    [DebuggerTypeProxy(typeof(System.Collections.Queue.QueueDebugView))]
    [DebuggerDisplay("Count = {Count}")] 
[System.Runtime.InteropServices.ComVisible(true)] 
    [Serializable]
    public class Queue : ICollection, ICloneable { 
        private Object[] _array;
        private int _head;       // First valid element in the queue
        private int _tail;       // Last valid element in the queue
        private int _size;       // Number of elements. 
        private int _growFactor; // 100 == 1.0, 130 == 1.3, 200 == 2.0
        private int _version; 
        [NonSerialized] 
        private Object _syncRoot;
 
        private const int _MinimumGrow = 4;
        private const int _ShrinkThreshold = 32;

        // Creates a queue with room for capacity objects. The default initial 
        // capacity and grow factor are used.
        public Queue() 
            : this(32, (float)2.0) { 
        }
 
        // Creates a queue with room for capacity objects. The default grow factor
        // is used.
        //
        public Queue(int capacity) 
            : this(capacity, (float)2.0) {
        } 
 
        // Creates a queue with room for capacity objects. When full, the new
        // capacity is set to the old capacity * growFactor. 
        //
        public Queue(int capacity, float growFactor) {
            if (capacity < 0)
                throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); 
            if (!(growFactor >= 1.0 && growFactor <= 10.0))
                throw new ArgumentOutOfRangeException("growFactor", Environment.GetResourceString("ArgumentOutOfRange_QueueGrowFactor", 1, 10)); 
            Contract.EndContractBlock(); 

            _array = new Object[capacity]; 
            _head = 0;
            _tail = 0;
            _size = 0;
            _growFactor = (int)(growFactor * 100); 
        }
 
        // Fills a Queue with the elements of an ICollection.  Uses the enumerator 
        // to get each of the elements.
        // 
        public Queue(ICollection col) : this((col==null ? 32 : col.Count))
        {
            if (col==null)
                throw new ArgumentNullException("col"); 
            Contract.EndContractBlock();
            IEnumerator en = col.GetEnumerator(); 
            while(en.MoveNext()) 
                Enqueue(en.Current);
        } 


        public virtual int Count {
            get { return _size; } 
        }
 
        public virtual Object Clone() { 
            Queue q = new Queue(_size);
            q._size = _size; 

            int numToCopy = _size;
            int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy;
            Array.Copy(_array, _head, q._array, 0, firstPart); 
            numToCopy -= firstPart;
            if (numToCopy > 0) 
                Array.Copy(_array, 0, q._array, _array.Length - _head, numToCopy); 

            q._version = _version; 
            return q;
        }

        public virtual bool IsSynchronized { 
            get { return false; }
        } 
 
        public virtual Object SyncRoot {
            get { 
                if( _syncRoot == null) {
                    System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null);
                }
                return _syncRoot; 
            }
        } 
 
        // Removes all Objects from the queue.
        public virtual void Clear() { 
            if (_head < _tail)
                Array.Clear(_array, _head, _size);
            else {
                Array.Clear(_array, _head, _array.Length - _head); 
                Array.Clear(_array, 0, _tail);
            } 
 
            _head = 0;
            _tail = 0; 
            _size = 0;
            _version++;
        }
 
        // CopyTo copies a collection into an Array, starting at a particular
        // index into the array. 
        // 
        public virtual void CopyTo(Array array, int index)
        { 
            if (array==null)
                throw new ArgumentNullException("array");
            if (array.Rank != 1)
                throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); 
            if (index < 0)
                throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index")); 
            Contract.EndContractBlock(); 
            int arrayLen = array.Length;
            if (arrayLen - index < _size) 
                throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));

            int numToCopy = _size;
            if (numToCopy == 0) 
                return;
            int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy; 
            Array.Copy(_array, _head, array, index, firstPart); 
            numToCopy -= firstPart;
            if (numToCopy > 0) 
                Array.Copy(_array, 0, array, index+_array.Length - _head, numToCopy);
        }

        // Adds obj to the tail of the queue. 
        //
        public virtual void Enqueue(Object obj) { 
            if (_size == _array.Length) { 
                int newcapacity = (int)((long)_array.Length * (long)_growFactor / 100);
                if (newcapacity < _array.Length + _MinimumGrow) { 
                    newcapacity = _array.Length + _MinimumGrow;
                }
                SetCapacity(newcapacity);
            } 

            _array[_tail] = obj; 
            _tail = (_tail + 1) % _array.Length; 
            _size++;
            _version++; 
        }

        // GetEnumerator returns an IEnumerator over this Queue.  This
        // Enumerator will support removing. 
        //
        public virtual IEnumerator GetEnumerator() 
        { 
            return new QueueEnumerator(this);
        } 

        // Removes the object at the head of the queue and returns it. If the queue
        // is empty, this method simply returns null.
        public virtual Object Dequeue() { 
            if (Count == 0)
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue")); 
            Contract.EndContractBlock(); 

            Object removed = _array[_head]; 
            _array[_head] = null;
            _head = (_head + 1) % _array.Length;
            _size--;
            _version++; 
            return removed;
        } 
 
        // Returns the object at the head of the queue. The object remains in the
        // queue. If the queue is empty, this method throws an 
        // InvalidOperationException.
        public virtual Object Peek() {
            if (Count == 0)
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue")); 
            Contract.EndContractBlock();
 
            return _array[_head]; 
        }
 
        // Returns a synchronized Queue.  Returns a synchronized wrapper
        // class around the queue - the caller must not use references to the
        // original queue.
        // 
        [HostProtection(Synchronization=true)]
        public static Queue Synchronized(Queue queue) 
        { 
            if (queue==null)
                throw new ArgumentNullException("queue"); 
            Contract.EndContractBlock();
            return new SynchronizedQueue(queue);
        }
 
        // Returns true if the queue contains at least one object equal to obj.
        // Equality is determined using obj.Equals(). 
        // 
        // Exceptions: ArgumentNullException if obj == null.
       public virtual bool Contains(Object obj) { 
            int index = _head;
            int count = _size;

            while (count-- > 0) { 
                if (obj == null) {
                    if (_array[index] == null) 
                        return true; 
                } else if (_array[index] != null && _array[index].Equals(obj)) {
                    return true; 
                }
                index = (index + 1) % _array.Length;
            }
 
            return false;
        } 
 
        internal Object GetElement(int i)
        { 
            return _array[(_head + i) % _array.Length];
        }

        // Iterates over the objects in the queue, returning an array of the 
        // objects in the Queue, or an empty array if the queue is empty.
        // The order of elements in the array is first in to last in, the same 
        // order produced by successive calls to Dequeue. 
        public virtual Object[] ToArray()
        { 
            Object[] arr = new Object[_size];
            if (_size==0)
                return arr;
 
            if (_head < _tail) {
                Array.Copy(_array, _head, arr, 0, _size); 
            } else { 
                Array.Copy(_array, _head, arr, 0, _array.Length - _head);
                Array.Copy(_array, 0, arr, _array.Length - _head, _tail); 
            }

            return arr;
        } 

 
        // PRIVATE Grows or shrinks the buffer to hold capacity objects. Capacity 
        // must be >= _size.
        private void SetCapacity(int capacity) { 
            Object[] newarray = new Object[capacity];
            if (_size > 0) {
                if (_head < _tail) {
                    Array.Copy(_array, _head, newarray, 0, _size); 
                } else {
                    Array.Copy(_array, _head, newarray, 0, _array.Length - _head); 
                    Array.Copy(_array, 0, newarray, _array.Length - _head, _tail); 
                }
            } 

            _array = newarray;
            _head = 0;
            _tail = (_size == capacity) ? 0 : _size; 
            _version++;
        } 
 
        public virtual void TrimToSize()
        { 
            SetCapacity(_size);
        }

 
        // Implements a synchronization wrapper around a queue.
        [Serializable] 
        private class SynchronizedQueue : Queue 
        {
            private Queue _q; 
            private Object root;

            internal SynchronizedQueue(Queue q) {
                this._q = q; 
                root = _q.SyncRoot;
            } 
 
            public override bool IsSynchronized {
                get { return true; } 
            }

            public override Object SyncRoot {
                get { 
                    return root;
                } 
            } 

            public override int Count { 
                get {
                    lock (root) {
                        return _q.Count;
                    } 
                }
            } 
 
            public override void Clear() {
                lock (root) { 
                    _q.Clear();
                }
            }
 
            public override Object Clone() {
                lock (root) { 
                    return new SynchronizedQueue((Queue)_q.Clone()); 
                }
            } 

            public override bool Contains(Object obj) {
                lock (root) {
                    return _q.Contains(obj); 
                }
            } 
 
            public override void CopyTo(Array array, int arrayIndex) {
                lock (root) { 
                    _q.CopyTo(array, arrayIndex);
                }
            }
 
            public override void Enqueue(Object value) {
                lock (root) { 
                    _q.Enqueue(value); 
                }
            } 

            public override Object Dequeue() {
                lock (root) {
                    return _q.Dequeue(); 
                }
            } 
 
            public override IEnumerator GetEnumerator() {
                lock (root) { 
                    return _q.GetEnumerator();
                }
            }
 
            public override Object Peek() {
                lock (root) { 
                    return _q.Peek(); 
                }
            } 

            public override Object[] ToArray() {
                lock (root) {
                    return _q.ToArray(); 
                }
            } 
 
            public override void TrimToSize() {
               lock (root) { 
                    _q.TrimToSize();
                }
            }
        } 

 
        // Implements an enumerator for a Queue.  The enumerator uses the 
        // internal version number of the list to ensure that no modifications are
        // made to the list while an enumeration is in progress. 
        [Serializable]
        private class QueueEnumerator : IEnumerator, ICloneable
        {
            private Queue _q; 
            private int _index;
            private int _version; 
            private Object currentElement; 

            internal QueueEnumerator(Queue q) { 
                _q = q;
                _version = _q._version;
                _index = 0;
                currentElement = _q._array; 
                if (_q._size == 0)
                    _index = -1; 
            } 

            public Object Clone() 
            {
                return MemberwiseClone();
            }
 
            public virtual bool MoveNext() {
                if (_version != _q._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); 
 
                if (_index < 0) {
                    currentElement = _q._array; 
                    return false;
                }

                currentElement = _q.GetElement(_index); 
                _index++;
 
                if (_index == _q._size) 
                    _index = -1;
                return true; 
            }

            public virtual Object Current {
                get { 
                    if (currentElement == _q._array)
                    { 
                        if (_index == 0) 
                            throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
                        else 
                            throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));
                    }
                    return currentElement;
                } 
            }
 
            public virtual void Reset() { 
                if (_version != _q._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
                if (_q._size == 0) 
                    _index = -1;
                 else
                     _index = 0;
                currentElement = _q._array; 
            }
        } 
 
        internal class QueueDebugView {
            private Queue queue; 

            public QueueDebugView( Queue queue) {
                if( queue == null)
                    throw new ArgumentNullException("queue"); 
                Contract.EndContractBlock();
 
                this.queue = queue; 
            }
 
            [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
            public Object[] Items   {
                get {
                    return queue.ToArray(); 
                }
            } 
        } 
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK