mono/mcs/class/corlib/System.Collections/Stack.cs

// -*- Mode: C; tab-width: 8; c-basic-offset: 8 -*-
//
// System.Collections.Stack
//
// Author:
//    Garrett Rooney ([email protected])
//
// (C) 2001 Garrett Rooney
//

namespace System.Collections {

	public class Stack : ICollection, IEnumerable, ICloneable {

		// properties
		private object[] contents;
		private int current = -1;
		private int count = 0;
		private int capacity = 16;
		private int modCount = 0;

		private void Resize(int ncapacity) {
			object[] ncontents = new object[ncapacity];

			Array.Copy(contents, ncontents, count);

			capacity = ncapacity;
			contents = ncontents;
		}

		public Stack() {
			contents = new object[capacity];
		}

		public Stack(ICollection collection) {
			capacity = collection.Count;
			contents = new object[capacity];
			current = capacity - 1;
			count = capacity;

			collection.CopyTo(contents, 0);
		}

		public Stack(int c) {
			capacity = c;
			contents = new object[capacity];
		}

		private class SyncStack : Stack {

			Stack stack;

			public SyncStack(Stack s) {
				stack = s;
			}
			
			public override int Count {
				get { 
					lock (stack) {
						return stack.Count; 
					}
				}
			}
			
			public override bool IsReadOnly {
				get { return false; }
			}

			public override bool IsSynchronized {
				get { return true; }
			}
			
			public override object SyncRoot {
				get { return stack.SyncRoot; }
			}

			public override void Clear() {
				lock(stack) { stack.Clear(); }
			}

			public override object Clone() {
				lock (stack) { 
					return Stack.Synchronized((Stack)stack.Clone()); 
				}
			}

			public override bool Contains(object obj) {
				lock (stack) { return stack.Contains(obj); }
			}

			public override void CopyTo(Array array, int index) {
				lock (stack) { stack.CopyTo(array, index); }
			}

			public override IEnumerator GetEnumerator() {
				lock (stack) { 
					return new Enumerator(stack); 
				}
			}

			public override object Peek() {
				lock (stack) { return stack.Peek(); }
			}

			public override object Pop() {
				lock (stack) { return stack.Pop(); }
			}

			public override void Push(object obj) {
				lock (stack) { stack.Push(obj); }
			}

			public override object[] ToArray() {
				lock (stack) { return stack.ToArray(); }
			}
		}

		public static Stack Synchronized(Stack s) {
			if (s == null) {
				throw new ArgumentNullException();
			}

			return new SyncStack(s);
		}

		public virtual int Count {
			get { return count; }
		}

		public virtual bool IsReadOnly {
			get { return false; }
		}

		public virtual bool IsSynchronized {
			get { return false; }
		}

		public virtual object SyncRoot {
			get { return this; }
		}

		public virtual void Clear() {
			modCount++;

			for (int i = 0; i < count; i++) {
				contents[i] = null;
			}

			count = 0;
			current = -1;
		}

		public virtual object Clone() {
			Stack stack;

			if (IsSynchronized) {
				stack = new Stack();

				stack.current = current;
				stack.contents = contents;
				stack.count = count;
				stack.capacity = capacity;
			} else {
				stack = new SyncStack(this);
			}

			return stack;
		}

		public virtual bool Contains(object obj) {
			if (count == 0)
				return false;

			for (int i = 0; i < count; i++) {
				if (contents[i].Equals(obj))
					return true; 
			}

			return false;
		}

		public virtual void CopyTo (Array array, int index) {
			if (array == null) {
				throw new ArgumentNullException();
			}

			if (index < 0) {
				throw new ArgumentOutOfRangeException();
			}

			if (array.Rank > 1 || 
			    index >= array.Length || 
			    count > array.Length - index) {
				throw new ArgumentException();
			}

			for (int i = current; i != -1; i--) {
				array.SetValue(contents[i], 
					       count - (i + 1) + index);
			}
		}

		private class Enumerator : IEnumerator {

			Stack stack;
			private int modCount;
			private int current;

			internal Enumerator(Stack s) {
				// this is odd.  it seems that you need to 
				// start one further ahead than current, since 
				// MoveNext() gets called first when using an 
				// Enumeration...
				stack = s;
				modCount = s.modCount;
				current = s.current + 1;
			}

			public virtual object Current {
				get {
					if (modCount != stack.modCount 
					    || current == -1 
					    || current > stack.count)
						throw new InvalidOperationException();
					return stack.contents[current];
				}
			}

			public virtual bool MoveNext() {
				if (modCount != stack.modCount 
				    || current == -1) {
					throw new InvalidOperationException();
				}

				current--;

				if (current == -1) {
					return false;
				} else {
					return true;
				}
			}

			public virtual void Reset() {
				if (modCount != stack.modCount) {
					throw new InvalidOperationException();
				}

				// start one ahead of stack.current, so the 
				// first MoveNext() will put us at the top
				current = stack.current + 1;
			}
		}

		public virtual IEnumerator GetEnumerator() {
			return new Enumerator(this);
		}

		public virtual object Peek() {
			if (current == -1) {
				throw new InvalidOperationException();
			} else {
				return contents[current];
			}
		}

		public virtual object Pop() {
			if (current == -1) {
				throw new InvalidOperationException();
			} else {
				modCount++;

				object ret = contents[current];
		
				count--;
				current--;
		
				return ret;
			}
		}

		// FIXME: We should probably be a bit smarter about our 
		// resizing.  After a certain point, doubling isn't that smart.
		// We just need to find out what that point is...
		public virtual void Push(Object o) {
			modCount++;

			if (capacity == count) {
				Resize(capacity * 2);
			}

			count++;
			current++;

			contents[current] = o;
		}

		public virtual object[] ToArray() {
			object[] ret = new object[count];

			Array.Copy(contents, ret, count);

			// ret needs to be in LIFO order
			Array.Reverse(ret);

			return ret;
		}
	}
}