The Labs \ Source Viewer \ SSCLI \ System.Collections.Generic \ Queue

  1. // ==++==
  2. //
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. //
  14. // ==--==
  15. /*=============================================================================
  16. **
  17. ** Class: Queue
  18. **
  19. ** Purpose: A circular-array implementation of a generic queue.
  20. **
  21. ** Date: January 28, 2003
  22. **
  23. =============================================================================*/
  24. namespace System.Collections.Generic
  25. {
  26.     using System;
  27.     using System.Security.Permissions;
  28.     using System.Diagnostics;
  29.    
  30.     // A simple Queue of generic objects. Internally it is implemented as a
  31.     // circular buffer, so Enqueue can be O(n). Dequeue is O(1).
  32.     [DebuggerTypeProxy(typeof(System_QueueDebugView<>))]
  33.     [DebuggerDisplay("Count = {Count}")]
  34.     [Serializable()]
  35.     [System.Runtime.InteropServices.ComVisible(false)]
  36.     public class Queue<T> : IEnumerable<T>, System.Collections.ICollection
  37.     {
  38.         private T[] _array;
  39.         private int _head;
  40.         // First valid element in the queue
  41.         private int _tail;
  42.         // Last valid element in the queue
  43.         private int _size;
  44.         // Number of elements.
  45.         private int _version;
  46.         [NonSerialized()]
  47.         private object _syncRoot;
  48.        
  49.         private const int _MinimumGrow = 4;
  50.         private const int _ShrinkThreshold = 32;
  51.         private const int _GrowFactor = 200;
  52.         // double each time
  53.         private const int _DefaultCapacity = 4;
  54.         static T[] _emptyArray = new T[0];
  55.        
  56.         // Creates a queue with room for capacity objects. The default initial
  57.         // capacity and grow factor are used.
  58.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.Queue"]/*' />
  59.         public Queue()
  60.         {
  61.             _array = _emptyArray;
  62.         }
  63.        
  64.         // Creates a queue with room for capacity objects. The default grow factor
  65.         // is used.
  66.         //
  67.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.Queue1"]/*' />
  68.         public Queue(int capacity)
  69.         {
  70.             if (capacity < 0)
  71.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired);
  72.            
  73.             _array = new T[capacity];
  74.             _head = 0;
  75.             _tail = 0;
  76.             _size = 0;
  77.         }
  78.        
  79.         // Fills a Queue with the elements of an ICollection. Uses the enumerator
  80.         // to get each of the elements.
  81.         //
  82.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.Queue3"]/*' />
  83.         public Queue(IEnumerable<T> collection)
  84.         {
  85.             if (collection == null)
  86.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
  87.            
  88.             _array = new T[_DefaultCapacity];
  89.             _size = 0;
  90.             _version = 0;
  91.            
  92.             using (IEnumerator<T> en = collection.GetEnumerator()) {
  93.                 while (en.MoveNext()) {
  94.                     Enqueue(en.Current);
  95.                 }
  96.             }
  97.         }
  98.        
  99.        
  100.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.Count"]/*' />
  101.         public int Count {
  102.             get { return _size; }
  103.         }
  104.        
  105.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.IsSynchronized"]/*' />
  106.         bool System.Collections.ICollection.IsSynchronized {
  107.             get { return false; }
  108.         }
  109.        
  110.         object System.Collections.ICollection.SyncRoot {
  111.             get {
  112.                 if (_syncRoot == null) {
  113.                     System.Threading.Interlocked.CompareExchange(ref _syncRoot, new object(), null);
  114.                 }
  115.                 return _syncRoot;
  116.             }
  117.         }
  118.        
  119.         // Removes all Objects from the queue.
  120.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.Clear"]/*' />
  121.         public void Clear()
  122.         {
  123.             if (_head < _tail)
  124.                 Array.Clear(_array, _head, _size);
  125.             else {
  126.                 Array.Clear(_array, _head, _array.Length - _head);
  127.                 Array.Clear(_array, 0, _tail);
  128.             }
  129.            
  130.             _head = 0;
  131.             _tail = 0;
  132.             _size = 0;
  133.             _version++;
  134.         }
  135.        
  136.         // CopyTo copies a collection into an Array, starting at a particular
  137.         // index into the array.
  138.         //
  139.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.CopyTo"]/*' />
  140.         public void CopyTo(T[] array, int arrayIndex)
  141.         {
  142.             if (array == null) {
  143.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
  144.             }
  145.            
  146.             if (arrayIndex < 0 || arrayIndex > array.Length) {
  147.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_Index);
  148.             }
  149.            
  150.             int arrayLen = array.Length;
  151.             if (arrayLen - arrayIndex < _size) {
  152.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  153.             }
  154.            
  155.             int numToCopy = (arrayLen - arrayIndex < _size) ? (arrayLen - arrayIndex) : _size;
  156.             if (numToCopy == 0)
  157.                 return;
  158.            
  159.             int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy;
  160.             Array.Copy(_array, _head, array, arrayIndex, firstPart);
  161.             numToCopy -= firstPart;
  162.             if (numToCopy > 0) {
  163.                 Array.Copy(_array, 0, array, arrayIndex + _array.Length - _head, numToCopy);
  164.             }
  165.         }
  166.        
  167.         void System.Collections.ICollection.CopyTo(Array array, int index)
  168.         {
  169.             if (array == null) {
  170.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
  171.             }
  172.            
  173.             if (array.Rank != 1) {
  174.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
  175.             }
  176.            
  177.             if (array.GetLowerBound(0) != 0) {
  178.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
  179.             }
  180.            
  181.             int arrayLen = array.Length;
  182.             if (index < 0 || index > arrayLen) {
  183.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
  184.             }
  185.            
  186.             if (arrayLen - index < _size) {
  187.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  188.             }
  189.            
  190.             int numToCopy = (arrayLen - index < _size) ? arrayLen - index : _size;
  191.             if (numToCopy == 0)
  192.                 return;
  193.            
  194.             try {
  195.                 int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy;
  196.                 Array.Copy(_array, _head, array, index, firstPart);
  197.                 numToCopy -= firstPart;
  198.                
  199.                 if (numToCopy > 0) {
  200.                     Array.Copy(_array, 0, array, index + _array.Length - _head, numToCopy);
  201.                 }
  202.             }
  203.             catch (ArrayTypeMismatchException) {
  204.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
  205.             }
  206.         }
  207.        
  208.         // Adds item to the tail of the queue.
  209.         //
  210.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.Enqueue"]/*' />
  211.         public void Enqueue(T item)
  212.         {
  213.             if (_size == _array.Length) {
  214.                 int newcapacity = (int)((long)_array.Length * (long)_GrowFactor / 100);
  215.                 if (newcapacity < _array.Length + _MinimumGrow) {
  216.                     newcapacity = _array.Length + _MinimumGrow;
  217.                 }
  218.                 SetCapacity(newcapacity);
  219.             }
  220.            
  221.             _array[_tail] = item;
  222.             _tail = (_tail + 1) % _array.Length;
  223.             _size++;
  224.             _version++;
  225.         }
  226.        
  227.         // GetEnumerator returns an IEnumerator over this Queue. This
  228.         // Enumerator will support removing.
  229.         //
  230.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.GetEnumerator"]/*' />
  231.         public Enumerator GetEnumerator()
  232.         {
  233.             return new Enumerator(this);
  234.         }
  235.        
  236.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.IEnumerable.GetEnumerator"]/*' />
  237.         /// <internalonly/>
  238.         IEnumerator<T> IEnumerable<T>.GetEnumerator()
  239.         {
  240.             return new Enumerator(this);
  241.         }
  242.        
  243.         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  244.         {
  245.             return new Enumerator(this);
  246.         }
  247.        
  248.         // Removes the object at the head of the queue and returns it. If the queue
  249.         // is empty, this method simply returns null.
  250.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.Dequeue"]/*' />
  251.         public T Dequeue()
  252.         {
  253.             if (_size == 0)
  254.                 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);
  255.            
  256.             T removed = _array[_head];
  257.             _array[_head] = default(T);
  258.             _head = (_head + 1) % _array.Length;
  259.             _size--;
  260.             _version++;
  261.             return removed;
  262.         }
  263.        
  264.         // Returns the object at the head of the queue. The object remains in the
  265.         // queue. If the queue is empty, this method throws an
  266.         // InvalidOperationException.
  267.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.Peek"]/*' />
  268.         public T Peek()
  269.         {
  270.             if (_size == 0)
  271.                 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);
  272.            
  273.             return _array[_head];
  274.         }
  275.        
  276.         // Returns true if the queue contains at least one object equal to item.
  277.         // Equality is determined using item.Equals().
  278.         //
  279.         // Exceptions: ArgumentNullException if item == null.
  280.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.Contains"]/*' />
  281.         public bool Contains(T item)
  282.         {
  283.             int index = _head;
  284.             int count = _size;
  285.            
  286.             EqualityComparer<T> c = EqualityComparer<T>.Default;
  287.             while (count-- > 0) {
  288.                 if (((object)item) == null) {
  289.                     if (((object)_array[index]) == null)
  290.                         return true;
  291.                 }
  292.                 else if (_array[index] != null && c.Equals(_array[index], item)) {
  293.                     return true;
  294.                 }
  295.                 index = (index + 1) % _array.Length;
  296.             }
  297.            
  298.             return false;
  299.         }
  300.        
  301.         internal T GetElement(int i)
  302.         {
  303.             return _array[(_head + i) % _array.Length];
  304.         }
  305.        
  306.         // Iterates over the objects in the queue, returning an array of the
  307.         // objects in the Queue, or an empty array if the queue is empty.
  308.         // The order of elements in the array is first in to last in, the same
  309.         // order produced by successive calls to Dequeue.
  310.         /// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.ToArray"]/*' />
  311.         public T[] ToArray()
  312.         {
  313.             T[] arr = new T[_size];
  314.             if (_size == 0)
  315.                 return arr;
  316.            
  317.             if (_head < _tail) {
  318.                 Array.Copy(_array, _head, arr, 0, _size);
  319.             }
  320.             else {
  321.                 Array.Copy(_array, _head, arr, 0, _array.Length - _head);
  322.                 Array.Copy(_array, 0, arr, _array.Length - _head, _tail);
  323.             }
  324.            
  325.             return arr;
  326.         }
  327.        
  328.        
  329.         // PRIVATE Grows or shrinks the buffer to hold capacity objects. Capacity
  330.         // must be >= _size.
  331.         private void SetCapacity(int capacity)
  332.         {
  333.             T[] newarray = new T[capacity];
  334.             if (_size > 0) {
  335.                 if (_head < _tail) {
  336.                     Array.Copy(_array, _head, newarray, 0, _size);
  337.                 }
  338.                 else {
  339.                     Array.Copy(_array, _head, newarray, 0, _array.Length - _head);
  340.                     Array.Copy(_array, 0, newarray, _array.Length - _head, _tail);
  341.                 }
  342.             }
  343.            
  344.             _array = newarray;
  345.             _head = 0;
  346.             _tail = _size;
  347.             _version++;
  348.         }
  349.        
  350.         public void TrimExcess()
  351.         {
  352.             int threshold = (int)(((double)_array.Length) * 0.9);
  353.             if (_size < threshold) {
  354.                 SetCapacity(_size);
  355.             }
  356.         }
  357.        
  358.         // Implements an enumerator for a Queue. The enumerator uses the
  359.         // internal version number of the list to ensure that no modifications are
  360.         // made to the list while an enumeration is in progress.
  361.         /// <include file='doc\Queue.uex' path='docs/doc[@for="QueueEnumerator"]/*' />
  362.         [Serializable()]
  363.         public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator
  364.         {
  365.             private Queue<T> _q;
  366.             private int _index;
  367.             // -1 = not started, -2 = ended/disposed
  368.             private int _version;
  369.             private T _currentElement;
  370.            
  371.             internal Enumerator(Queue<T> q)
  372.             {
  373.                 _q = q;
  374.                 _version = _q._version;
  375.                 _index = -1;
  376.                 _currentElement = default(T);
  377.             }
  378.            
  379.             /// <include file='doc\Queue.uex' path='docs/doc[@for="QueueEnumerator.Dispose"]/*' />
  380.             public void Dispose()
  381.             {
  382.                 _index = -2;
  383.                 _currentElement = default(T);
  384.             }
  385.            
  386.             /// <include file='doc\Queue.uex' path='docs/doc[@for="QueueEnumerator.MoveNext"]/*' />
  387.             public bool MoveNext()
  388.             {
  389.                 if (_version != _q._version)
  390.                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
  391.                
  392.                 if (_index == -2)
  393.                     return false;
  394.                
  395.                 _index++;
  396.                
  397.                 if (_index == _q._size) {
  398.                     _index = -2;
  399.                     _currentElement = default(T);
  400.                     return false;
  401.                 }
  402.                
  403.                 _currentElement = _q.GetElement(_index);
  404.                 return true;
  405.             }
  406.            
  407.             /// <include file='doc\Queue.uex' path='docs/doc[@for="QueueEnumerator.Current"]/*' />
  408.             public T Current {
  409.                 get {
  410.                     if (_index < 0) {
  411.                         if (_index == -1)
  412.                             ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
  413.                         else
  414.                             ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
  415.                     }
  416.                     return _currentElement;
  417.                 }
  418.             }
  419.            
  420.             object System.Collections.IEnumerator.Current {
  421.                 get {
  422.                     if (_index < 0) {
  423.                         if (_index == -1)
  424.                             ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
  425.                         else
  426.                             ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
  427.                     }
  428.                     return _currentElement;
  429.                 }
  430.             }
  431.            
  432.             void System.Collections.IEnumerator.Reset()
  433.             {
  434.                 if (_version != _q._version)
  435.                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
  436.                 _index = -1;
  437.                 _currentElement = default(T);
  438.             }
  439.         }
  440.     }
  441. }

Developer Fusion