3 // Copyright (c) Microsoft Corporation. All rights reserved.
6 /*=============================================================================
10 ** Purpose: An array implementation of a generic stack.
12 ** Date: January 28, 2003
14 =============================================================================*/
15 namespace System.Collections.Generic {
17 using System.Diagnostics;
18 using System.Diagnostics.CodeAnalysis;
19 using System.Security.Permissions;
21 // A simple stack of objects. Internally it is implemented as an array,
22 // so Push can be O(n). Pop is O(1).
24 [DebuggerTypeProxy(typeof(System_StackDebugView<>))]
25 [DebuggerDisplay("Count = {Count}")]
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.
39 private Object _syncRoot;
41 private const int _defaultCapacity = 4;
42 static T[] _emptyArray = new T[0];
44 /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Stack"]/*' />
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) {
56 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired);
57 _array = new T[capacity];
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.
65 /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Stack2"]/*' />
66 public Stack(IEnumerable<T> collection)
69 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
71 ICollection<T> c = collection as ICollection<T>;
74 _array = new T[count];
80 _array = new T[_defaultCapacity];
82 using(IEnumerator<T> en = collection.GetEnumerator()) {
83 while(en.MoveNext()) {
90 /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Count"]/*' />
95 /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.IsSynchronized"]/*' />
96 bool System.Collections.ICollection.IsSynchronized {
100 /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.SyncRoot"]/*' />
101 Object System.Collections.ICollection.SyncRoot {
103 if( _syncRoot == null) {
104 System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
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.
118 /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Contains"]/*' />
119 public bool Contains(T item) {
122 EqualityComparer<T> c = EqualityComparer<T>.Default;
123 while (count-- > 0) {
124 if (((Object) item) == null) {
125 if (((Object) _array[count]) == null)
128 else if (_array[count] != null && c.Equals(_array[count], item) ) {
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) {
139 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
142 if (arrayIndex < 0 || arrayIndex > array.Length) {
143 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
146 if (array.Length - arrayIndex < _size) {
147 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
150 Array.Copy(_array, 0, array, arrayIndex, _size);
151 Array.Reverse(array, arrayIndex, _size);
154 void System.Collections.ICollection.CopyTo(Array array, int arrayIndex) {
156 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
159 if (array.Rank != 1) {
160 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
163 if( array.GetLowerBound(0) != 0 ) {
164 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
167 if (arrayIndex < 0 || arrayIndex > array.Length) {
168 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
171 if (array.Length - arrayIndex < _size) {
172 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
176 Array.Copy(_array, 0, array, arrayIndex, _size);
177 Array.Reverse(array, arrayIndex, _size);
179 catch(ArrayTypeMismatchException){
180 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
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);
190 /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.IEnumerable.GetEnumerator"]/*' />
192 IEnumerator<T> IEnumerable<T>.GetEnumerator() {
193 return new Enumerator(this);
196 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
197 return new Enumerator(this);
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);
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"]/*' />
215 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack);
216 return _array[_size-1];
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"]/*' />
224 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack);
226 T item = _array[--_size];
227 _array[_size] = default(T); // Free memory quicker.
232 public bool TryPop(out T result)
241 result = _array[--_size];
242 _array[_size] = default(T); // Free memory quicker.
247 // Pushes an item to the top of the stack.
249 /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Push"]/*' />
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);
256 _array[_size++] = item;
260 // Copies the Stack to an array, in the same order Pop would return the items.
263 T[] objArray = new T[_size];
266 objArray[i] = _array[_size-i-1];
272 /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator"]/*' />
276 [SuppressMessage("Microsoft.Performance", "CA1815:OverrideEqualsAndOperatorEqualsOnValueTypes", Justification = "not an expected scenario")]
277 public struct Enumerator : IEnumerator<T>,
278 System.Collections.IEnumerator
280 private Stack<T> _stack;
282 private int _version;
283 private T currentElement;
285 internal Enumerator(Stack<T> stack) {
287 _version = _stack._version;
289 currentElement = default(T);
292 /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator.Dispose"]/*' />
293 public void Dispose()
298 /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator.MoveNext"]/*' />
299 public bool MoveNext() {
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);
306 currentElement = _stack._array[_index];
309 if (_index == -1) { // End of enumeration.
313 retval = (--_index >= 0);
315 currentElement = _stack._array[_index];
317 currentElement = default(T);
321 /// <include file='doc\Stack.uex' path='docs/doc[@for="StackEnumerator.Current"]/*' />
324 if (_index == -2) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
325 if (_index == -1) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
326 return currentElement;
330 Object System.Collections.IEnumerator.Current {
332 if (_index == -2) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
333 if (_index == -1) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
334 return currentElement;
338 void System.Collections.IEnumerator.Reset() {
339 if (_version != _stack._version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
341 currentElement = default(T);