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 sync 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"]/*' /> 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"]/*' /> Stack(int capacity)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"]/*' /> Stack(IEnumerable<T> collection)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"]/*' /> 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"]/*' /> Contains(T item)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"]/*' /> CopyTo(T[] array, int arrayIndex)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 System.Collections.ICollection.CopyTo(Array array, int arrayIndex)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"]/*' /> 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/> GetEnumerator()192 IEnumerator<T> IEnumerable<T>.GetEnumerator() { 193 return new Enumerator(this); 194 } 195 System.Collections.IEnumerable.GetEnumerator()196 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { 197 return new Enumerator(this); 198 } 199 TrimExcess()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"]/*' /> 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"]/*' /> 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 #if MONO TryPop(out T result)232 public bool TryPop(out T result) 233 { 234 if (_size == 0) 235 { 236 result = default(T); 237 return false; 238 } 239 240 _version++; 241 result = _array[--_size]; 242 _array[_size] = default(T); // Free memory quicker. 243 return true; 244 } 245 #endif 246 247 // Pushes an item to the top of the stack. 248 // 249 /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Push"]/*' /> Push(T item)250 public void Push(T item) { 251 if (_size == _array.Length) { 252 T[] newArray = new T[(_array.Length == 0) ? _defaultCapacity : 2*_array.Length]; 253 Array.Copy(_array, 0, newArray, 0, _size); 254 _array = newArray; 255 } 256 _array[_size++] = item; 257 _version++; 258 } 259 260 // Copies the Stack to an array, in the same order Pop would return the items. ToArray()261 public T[] ToArray() 262 { 263 T[] objArray = new T[_size]; 264 int i = 0; 265 while(i < _size) { 266 objArray[i] = _array[_size-i-1]; 267 i++; 268 } 269 return objArray; 270 } 271 272 /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator"]/*' /> 273 #if !SILVERLIGHT 274 [Serializable()] 275 #endif 276 [SuppressMessage("Microsoft.Performance", "CA1815:OverrideEqualsAndOperatorEqualsOnValueTypes", Justification = "not an expected scenario")] 277 public struct Enumerator : IEnumerator<T>, 278 System.Collections.IEnumerator 279 { 280 private Stack<T> _stack; 281 private int _index; 282 private int _version; 283 private T currentElement; 284 EnumeratorSystem.Collections.Generic.Stack.Enumerator285 internal Enumerator(Stack<T> stack) { 286 _stack = stack; 287 _version = _stack._version; 288 _index = -2; 289 currentElement = default(T); 290 } 291 292 /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator.Dispose"]/*' /> DisposeSystem.Collections.Generic.Stack.Enumerator293 public void Dispose() 294 { 295 _index = -1; 296 } 297 298 /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator.MoveNext"]/*' /> MoveNextSystem.Collections.Generic.Stack.Enumerator299 public bool MoveNext() { 300 bool retval; 301 if (_version != _stack._version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); 302 if (_index == -2) { // First call to enumerator. 303 _index = _stack._size-1; 304 retval = ( _index >= 0); 305 if (retval) 306 currentElement = _stack._array[_index]; 307 return retval; 308 } 309 if (_index == -1) { // End of enumeration. 310 return false; 311 } 312 313 retval = (--_index >= 0); 314 if (retval) 315 currentElement = _stack._array[_index]; 316 else 317 currentElement = default(T); 318 return retval; 319 } 320 321 /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator.Current"]/*' /> 322 public T Current { 323 get { 324 if (_index == -2) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted); 325 if (_index == -1) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded); 326 return currentElement; 327 } 328 } 329 330 Object System.Collections.IEnumerator.Current { 331 get { 332 if (_index == -2) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted); 333 if (_index == -1) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded); 334 return currentElement; 335 } 336 } 337 System.Collections.IEnumerator.ResetSystem.Collections.Generic.Stack.Enumerator338 void System.Collections.IEnumerator.Reset() { 339 if (_version != _stack._version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); 340 _index = -2; 341 currentElement = default(T); 342 } 343 } 344 } 345 } 346