2 // System.Collections.Generic.Stack
5 // Martin Baulig (martin@ximian.com)
6 // Ben Maurer (bmaurer@ximian.com)
8 // (C) 2003, 2004 Novell, Inc.
12 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
14 // Permission is hereby granted, free of charge, to any person obtaining
15 // a copy of this software and associated documentation files (the
16 // "Software"), to deal in the Software without restriction, including
17 // without limitation the rights to use, copy, modify, merge, publish,
18 // distribute, sublicense, and/or sell copies of the Software, and to
19 // permit persons to whom the Software is furnished to do so, subject to
20 // the following conditions:
22 // The above copyright notice and this permission notice shall be
23 // included in all copies or substantial portions of the Software.
25 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
26 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
27 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
28 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
29 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
30 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
31 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 using System.Runtime.InteropServices;
36 using System.Diagnostics;
38 namespace System.Collections.Generic
42 [DebuggerDisplay ("Count={Count}")]
43 [DebuggerTypeProxy (typeof (CollectionDebuggerView))]
44 public class Stack <T> : IEnumerable <T>, ICollection, IEnumerable
50 private const int INITIAL_SIZE = 16;
56 public Stack (int count)
59 throw new ArgumentOutOfRangeException ("count");
61 _array = new T [count];
64 public Stack (IEnumerable <T> collection)
66 if (collection == null)
67 throw new ArgumentNullException ("collection");
69 ICollection <T> col = collection as ICollection <T>;
73 _array = new T [_size];
74 col.CopyTo (_array, 0);
76 foreach (T t in collection)
84 Array.Clear (_array, 0, _array.Length);
90 public bool Contains (T t)
92 return _array != null && Array.IndexOf (_array, t, 0, _size) != -1;
95 public void CopyTo (T [] dest, int idx)
98 throw new ArgumentNullException ("dest");
100 throw new ArgumentOutOfRangeException ("idx");
102 // this gets copied in the order that it is poped
103 if (_array != null) {
104 Array.Copy (_array, 0, dest, idx, _size);
105 Array.Reverse (dest, idx, _size);
112 throw new InvalidOperationException ();
114 return _array [_size - 1];
120 throw new InvalidOperationException ();
123 T popped = _array [--_size];
124 // clear stuff out to make the GC happy
125 _array [_size] = default(T);
129 public void Push (T t)
131 if (_array == null || _size == _array.Length)
132 Array.Resize <T> (ref _array, _size == 0 ? INITIAL_SIZE : 2 * _size);
136 _array [_size++] = t;
139 public T [] ToArray ()
141 T [] copy = new T [_size];
146 public void TrimExcess ()
148 if (_array != null && (_size < _array.Length * 0.9))
149 Array.Resize <T> (ref _array, _size);
154 get { return _size; }
157 bool ICollection.IsSynchronized {
158 get { return false; }
161 object ICollection.SyncRoot {
165 void ICollection.CopyTo (Array dest, int idx)
168 if (_array != null) {
169 _array.CopyTo (dest, idx);
170 Array.Reverse (dest, idx, _size);
172 } catch (ArrayTypeMismatchException) {
173 throw new ArgumentException ();
177 public Enumerator GetEnumerator ()
179 return new Enumerator (this);
182 IEnumerator <T> IEnumerable<T>.GetEnumerator ()
184 return GetEnumerator ();
187 IEnumerator IEnumerable.GetEnumerator ()
189 return GetEnumerator ();
193 public struct Enumerator : IEnumerator <T>, IEnumerator, IDisposable {
194 const int NOT_STARTED = -2;
196 // this MUST be -1, because we depend on it in move next.
197 // we just decr the _size, so, 0 - 1 == FINISHED
198 const int FINISHED = -1;
204 internal Enumerator (Stack <T> t)
208 _version = t._version;
211 // for some fucked up reason, MSFT added a useless dispose to this class
212 // It means that in foreach, we must still do a try/finally. Broken, very
214 public void Dispose ()
219 public bool MoveNext ()
221 if (_version != parent._version)
222 throw new InvalidOperationException ();
227 return idx != FINISHED && -- idx != FINISHED;
233 throw new InvalidOperationException ();
235 return parent._array [idx];
239 void IEnumerator.Reset ()
241 if (_version != parent._version)
242 throw new InvalidOperationException ();
247 object IEnumerator.Current {
248 get { return Current; }