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

  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: Stack
  18. **
  19. ** Purpose: An array implementation of a generic stack.
  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 stack of objects. Internally it is implemented as an array,
  31.     // so Push can be O(n). Pop is O(1).
  32.     [DebuggerTypeProxy(typeof(System_StackDebugView<>))]
  33.     [DebuggerDisplay("Count = {Count}")]
  34.     [Serializable()]
  35.     [System.Runtime.InteropServices.ComVisible(false)]
  36.     public class Stack<T> : IEnumerable<T>, System.Collections.ICollection
  37.     {
  38.         private T[] _array;
  39.         // Storage for stack elements
  40.         private int _size;
  41.         // Number of items in the stack.
  42.         private int _version;
  43.         // Used to keep enumerator in sync w/ collection.
  44.         [NonSerialized()]
  45.         private object _syncRoot;
  46.        
  47.         private const int _defaultCapacity = 4;
  48.         static T[] _emptyArray = new T[0];
  49.        
  50.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Stack"]/*' />
  51.         public Stack()
  52.         {
  53.             _array = _emptyArray;
  54.             _size = 0;
  55.             _version = 0;
  56.         }
  57.        
  58.         // Create a stack with a specific initial capacity. The initial capacity
  59.         // must be a non-negative number.
  60.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Stack1"]/*' />
  61.         public Stack(int capacity)
  62.         {
  63.             if (capacity < 0)
  64.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired);
  65.             _array = new T[capacity];
  66.             _size = 0;
  67.             _version = 0;
  68.         }
  69.        
  70.         // Fills a Stack with the contents of a particular collection. The items are
  71.         // pushed onto the stack in the same order they are read by the enumerator.
  72.         //
  73.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Stack2"]/*' />
  74.         public Stack(IEnumerable<T> collection)
  75.         {
  76.             if (collection == null)
  77.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
  78.            
  79.             ICollection<T> c = collection as ICollection<T>;
  80.             if (c != null) {
  81.                 int count = c.Count;
  82.                 _array = new T[count];
  83.                 c.CopyTo(_array, 0);
  84.                 _size = count;
  85.             }
  86.             else {
  87.                 _size = 0;
  88.                 _array = new T[_defaultCapacity];
  89.                
  90.                 using (IEnumerator<T> en = collection.GetEnumerator()) {
  91.                     while (en.MoveNext()) {
  92.                         Push(en.Current);
  93.                     }
  94.                 }
  95.             }
  96.         }
  97.        
  98.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Count"]/*' />
  99.         public int Count {
  100.             get { return _size; }
  101.         }
  102.        
  103.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.IsSynchronized"]/*' />
  104.         bool System.Collections.ICollection.IsSynchronized {
  105.             get { return false; }
  106.         }
  107.        
  108.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.SyncRoot"]/*' />
  109.         object System.Collections.ICollection.SyncRoot {
  110.             get {
  111.                 if (_syncRoot == null) {
  112.                     System.Threading.Interlocked.CompareExchange(ref _syncRoot, new object(), null);
  113.                 }
  114.                 return _syncRoot;
  115.             }
  116.         }
  117.        
  118.         // Removes all Objects from the Stack.
  119.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Clear"]/*' />
  120.         public void Clear()
  121.         {
  122.             Array.Clear(_array, 0, _size);
  123.             // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
  124.             _size = 0;
  125.             _version++;
  126.         }
  127.        
  128.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Contains"]/*' />
  129.         public bool Contains(T item)
  130.         {
  131.             int count = _size;
  132.            
  133.             EqualityComparer<T> c = EqualityComparer<T>.Default;
  134.             while (count-- > 0) {
  135.                 if (((object)item) == null) {
  136.                     if (((object)_array[count]) == null)
  137.                         return true;
  138.                 }
  139.                 else if (_array[count] != null && c.Equals(_array[count], item)) {
  140.                     return true;
  141.                 }
  142.             }
  143.             return false;
  144.         }
  145.        
  146.         // Copies the stack into an array.
  147.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.CopyTo"]/*' />
  148.         public void CopyTo(T[] array, int arrayIndex)
  149.         {
  150.             if (array == null) {
  151.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
  152.             }
  153.            
  154.             if (arrayIndex < 0 || arrayIndex > array.Length) {
  155.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  156.             }
  157.            
  158.             if (array.Length - arrayIndex < _size) {
  159.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  160.             }
  161.            
  162.             Array.Copy(_array, 0, array, arrayIndex, _size);
  163.             Array.Reverse(array, arrayIndex, _size);
  164.         }
  165.        
  166.         void System.Collections.ICollection.CopyTo(Array array, int arrayIndex)
  167.         {
  168.             if (array == null) {
  169.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
  170.             }
  171.            
  172.             if (array.Rank != 1) {
  173.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
  174.             }
  175.            
  176.             if (array.GetLowerBound(0) != 0) {
  177.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
  178.             }
  179.            
  180.             if (arrayIndex < 0 || arrayIndex > array.Length) {
  181.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  182.             }
  183.            
  184.             if (array.Length - arrayIndex < _size) {
  185.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  186.             }
  187.            
  188.             try {
  189.                 Array.Copy(_array, 0, array, arrayIndex, _size);
  190.                 Array.Reverse(array, arrayIndex, _size);
  191.             }
  192.             catch (ArrayTypeMismatchException) {
  193.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
  194.             }
  195.         }
  196.        
  197.         // Returns an IEnumerator for this Stack.
  198.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.GetEnumerator"]/*' />
  199.         public Enumerator GetEnumerator()
  200.         {
  201.             return new Enumerator(this);
  202.         }
  203.        
  204.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.IEnumerable.GetEnumerator"]/*' />
  205.         /// <internalonly/>
  206.         IEnumerator<T> IEnumerable<T>.GetEnumerator()
  207.         {
  208.             return new Enumerator(this);
  209.         }
  210.        
  211.         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  212.         {
  213.             return new Enumerator(this);
  214.         }
  215.        
  216.         public void TrimExcess()
  217.         {
  218.             int threshold = (int)(((double)_array.Length) * 0.9);
  219.             if (_size < threshold) {
  220.                 T[] newarray = new T[_size];
  221.                 Array.Copy(_array, 0, newarray, 0, _size);
  222.                 _array = newarray;
  223.                 _version++;
  224.             }
  225.         }
  226.        
  227.         // Returns the top object on the stack without removing it. If the stack
  228.         // is empty, Peek throws an InvalidOperationException.
  229.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Peek"]/*' />
  230.         public T Peek()
  231.         {
  232.             if (_size == 0)
  233.                 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack);
  234.             return _array[_size - 1];
  235.         }
  236.        
  237.         // Pops an item from the top of the stack. If the stack is empty, Pop
  238.         // throws an InvalidOperationException.
  239.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Pop"]/*' />
  240.         public T Pop()
  241.         {
  242.             if (_size == 0)
  243.                 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack);
  244.             _version++;
  245.             T item = _array[--_size];
  246.             _array[_size] = default(T);
  247.             // Free memory quicker.
  248.             return item;
  249.         }
  250.        
  251.         // Pushes an item to the top of the stack.
  252.         //
  253.         /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Push"]/*' />
  254.         public void Push(T item)
  255.         {
  256.             if (_size == _array.Length) {
  257.                 T[] newArray = new T[(_array.Length == 0) ? _defaultCapacity : 2 * _array.Length];
  258.                 Array.Copy(_array, 0, newArray, 0, _size);
  259.                 _array = newArray;
  260.             }
  261.             _array[_size++] = item;
  262.             _version++;
  263.         }
  264.        
  265.         // Copies the Stack to an array, in the same order Pop would return the items.
  266.         public T[] ToArray()
  267.         {
  268.             T[] objArray = new T[_size];
  269.             int i = 0;
  270.             while (i < _size) {
  271.                 objArray[i] = _array[_size - i - 1];
  272.                 i++;
  273.             }
  274.             return objArray;
  275.         }
  276.        
  277.         /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator"]/*' />
  278.         [Serializable()]
  279.         public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator
  280.         {
  281.             private Stack<T> _stack;
  282.             private int _index;
  283.             private int _version;
  284.             private T currentElement;
  285.            
  286.             internal Enumerator(Stack<T> stack)
  287.             {
  288.                 _stack = stack;
  289.                 _version = _stack._version;
  290.                 _index = -2;
  291.                 currentElement = default(T);
  292.             }
  293.            
  294.             /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator.Dispose"]/*' />
  295.             public void Dispose()
  296.             {
  297.                 _index = -1;
  298.             }
  299.            
  300.             /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator.MoveNext"]/*' />
  301.             public bool MoveNext()
  302.             {
  303.                 bool retval;
  304.                 if (_version != _stack._version)
  305.                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
  306.                 if (_index == -2) {
  307.                     // First call to enumerator.
  308.                     _index = _stack._size - 1;
  309.                     retval = (_index >= 0);
  310.                     if (retval)
  311.                         currentElement = _stack._array[_index];
  312.                     return retval;
  313.                 }
  314.                 if (_index == -1) {
  315.                     // End of enumeration.
  316.                     return false;
  317.                 }
  318.                
  319.                 retval = (--_index >= 0);
  320.                 if (retval)
  321.                     currentElement = _stack._array[_index];
  322.                 else
  323.                     currentElement = default(T);
  324.                 return retval;
  325.             }
  326.            
  327.             /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator.Current"]/*' />
  328.             public T Current {
  329.                 get {
  330.                     if (_index == -2)
  331.                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
  332.                     if (_index == -1)
  333.                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
  334.                     return currentElement;
  335.                 }
  336.             }
  337.            
  338.             object System.Collections.IEnumerator.Current {
  339.                 get {
  340.                     if (_index == -2)
  341.                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
  342.                     if (_index == -1)
  343.                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
  344.                     return currentElement;
  345.                 }
  346.             }
  347.            
  348.             void System.Collections.IEnumerator.Reset()
  349.             {
  350.                 if (_version != _stack._version)
  351.                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
  352.                 _index = -2;
  353.                 currentElement = default(T);
  354.             }
  355.         }
  356.     }
  357. }

Developer Fusion