mcs/class/referencesource/System/compmod/system/collections/generic/stack.cs

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