SHARE
TWEET

.NET 4.0 Stack<T>

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