2 // System.Collections.Stack
\r
5 // Garrett Rooney (rooneg@electricjellyfish.net)
\r
7 // (C) 2001 Garrett Rooney
\r
10 namespace System.Collections {
\r
13 public class Stack : ICollection, IEnumerable, ICloneable {
\r
16 private object[] contents;
\r
17 private int current = -1;
\r
18 private int count = 0;
\r
19 private int capacity = 16;
\r
20 private int modCount = 0;
\r
22 private void Resize(int ncapacity) {
\r
23 object[] ncontents = new object[ncapacity];
\r
25 Array.Copy(contents, ncontents, count);
\r
27 capacity = ncapacity;
\r
28 contents = ncontents;
\r
32 contents = new object[capacity];
\r
35 public Stack(ICollection collection) {
\r
36 capacity = collection.Count;
\r
37 contents = new object[capacity];
\r
38 current = capacity - 1;
\r
41 collection.CopyTo(contents, 0);
\r
44 public Stack(int c) {
\r
46 contents = new object[capacity];
\r
50 private class SyncStack : Stack {
\r
54 internal SyncStack(Stack s) {
\r
58 public override int Count {
\r
61 return stack.Count;
\r
66 public override bool IsReadOnly {
\r
69 return stack.IsReadOnly;
\r
74 public override bool IsSynchronized {
\r
75 get { return true; }
\r
78 public override object SyncRoot {
\r
79 get { return stack.SyncRoot; }
\r
82 public override void Clear() {
\r
83 lock(stack) { stack.Clear(); }
\r
86 public override object Clone() {
\r
88 return Stack.Synchronized((Stack)stack.Clone());
\r
92 public override bool Contains(object obj) {
\r
93 lock (stack) { return stack.Contains(obj); }
\r
96 public override void CopyTo(Array array, int index) {
\r
97 lock (stack) { stack.CopyTo(array, index); }
\r
100 public override IEnumerator GetEnumerator() {
\r
102 return new Enumerator(stack);
\r
106 public override object Peek() {
\r
107 lock (stack) { return stack.Peek(); }
\r
110 public override object Pop() {
\r
111 lock (stack) { return stack.Pop(); }
\r
114 public override void Push(object obj) {
\r
115 lock (stack) { stack.Push(obj); }
\r
118 public override object[] ToArray() {
\r
119 lock (stack) { return stack.ToArray(); }
\r
123 public static Stack Synchronized(Stack s) {
\r
125 throw new ArgumentNullException();
\r
128 return new SyncStack(s);
\r
131 public virtual int Count {
\r
132 get { return count; }
\r
135 public virtual bool IsReadOnly {
\r
136 get { return false; }
\r
139 public virtual bool IsSynchronized {
\r
140 get { return false; }
\r
143 public virtual object SyncRoot {
\r
144 get { return this; }
\r
147 public virtual void Clear() {
\r
150 for (int i = 0; i < count; i++) {
\r
151 contents[i] = null;
\r
158 public virtual object Clone() {
\r
161 stack = new Stack();
\r
163 stack.current = current;
\r
164 stack.contents = contents;
\r
165 stack.count = count;
\r
166 stack.capacity = capacity;
\r
171 public virtual bool Contains(object obj) {
\r
175 for (int i = 0; i < count; i++) {
\r
176 if (contents[i].Equals(obj))
\r
183 public virtual void CopyTo (Array array, int index) {
\r
184 if (array == null) {
\r
185 throw new ArgumentNullException();
\r
189 throw new ArgumentOutOfRangeException();
\r
192 if (array.Rank > 1 ||
\r
193 index >= array.Length ||
\r
194 count > array.Length - index) {
\r
195 throw new ArgumentException();
\r
198 for (int i = current; i != -1; i--) {
\r
199 array.SetValue(contents[i],
\r
200 count - (i + 1) + index);
\r
204 private class Enumerator : IEnumerator {
\r
207 private int modCount;
\r
208 private int current;
\r
210 internal Enumerator(Stack s) {
\r
211 // this is odd. it seems that you need to
\r
212 // start one further ahead than current, since
\r
213 // MoveNext() gets called first when using an
\r
216 modCount = s.modCount;
\r
217 current = s.current + 1;
\r
220 public virtual object Current {
\r
222 if (modCount != stack.modCount
\r
224 || current > stack.count)
\r
225 throw new InvalidOperationException();
\r
226 return stack.contents[current];
\r
230 public virtual bool MoveNext() {
\r
231 if (modCount != stack.modCount
\r
232 || current == -1) {
\r
233 throw new InvalidOperationException();
\r
238 if (current == -1) {
\r
245 public virtual void Reset() {
\r
246 if (modCount != stack.modCount) {
\r
247 throw new InvalidOperationException();
\r
250 // start one ahead of stack.current, so the
\r
251 // first MoveNext() will put us at the top
\r
252 current = stack.current + 1;
\r
256 public virtual IEnumerator GetEnumerator() {
\r
257 return new Enumerator(this);
\r
260 public virtual object Peek() {
\r
261 if (current == -1) {
\r
262 throw new InvalidOperationException();
\r
264 return contents[current];
\r
268 public virtual object Pop() {
\r
269 if (current == -1) {
\r
270 throw new InvalidOperationException();
\r
274 object ret = contents[current];
\r
279 // if we're down to capacity/4, go back to a
\r
280 // lower array size. this should keep us from
\r
281 // sucking down huge amounts of memory when
\r
282 // putting large numbers of items in the Stack.
\r
283 // if we're lower than 16, don't bother, since
\r
284 // it will be more trouble than it's worth.
\r
285 if (count <= (capacity/4) && count > 16) {
\r
286 Resize(capacity/2);
\r
293 public virtual void Push(Object o) {
\r
296 if (capacity == count) {
\r
297 Resize(capacity * 2);
\r
303 contents[current] = o;
\r
306 public virtual object[] ToArray() {
\r
307 object[] ret = new object[count];
\r
309 Array.Copy(contents, ret, count);
\r
311 // ret needs to be in LIFO order
\r
312 Array.Reverse(ret);
\r