-//\r
-// System.Collections.Stack\r
-//\r
-// Author:\r
-// Garrett Rooney (rooneg@electricjellyfish.net)\r
-//\r
-// (C) 2001 Garrett Rooney\r
-//\r
-\r
-//\r
-// Copyright (C) 2004 Novell, Inc (http://www.novell.com)\r
-//\r
-// Permission is hereby granted, free of charge, to any person obtaining\r
-// a copy of this software and associated documentation files (the\r
-// "Software"), to deal in the Software without restriction, including\r
-// without limitation the rights to use, copy, modify, merge, publish,\r
-// distribute, sublicense, and/or sell copies of the Software, and to\r
-// permit persons to whom the Software is furnished to do so, subject to\r
-// the following conditions:\r
-// \r
-// The above copyright notice and this permission notice shall be\r
-// included in all copies or substantial portions of the Software.\r
-// \r
-// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
-// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
-// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
-// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE\r
-// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION\r
-// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION\r
-// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\r
-//\r
-\r
-namespace System.Collections {\r
- [Serializable]\r
- [MonoTODO ("Fix serialization compatibility with MS.NET")]\r
- public class Stack : ICollection, IEnumerable, ICloneable {\r
-\r
- // properties\r
- private object[] contents;\r
- private int current = -1;\r
- private int count = 0;\r
- private int capacity;\r
- private int modCount = 0;\r
-\r
- private void Resize(int ncapacity) {\r
- \r
- ncapacity = Math.Max (ncapacity, 16);\r
- object[] ncontents = new object[ncapacity];\r
-\r
- Array.Copy(contents, ncontents, count);\r
-\r
- capacity = ncapacity;\r
- contents = ncontents;\r
- }\r
-\r
- public Stack () : this (16) {}\r
-\r
- public Stack(ICollection col) : this (col == null ? 16 : col.Count) {\r
- if (col == null)\r
- throw new ArgumentNullException("col");\r
- \r
- current = col.Count - 1;\r
- count = col.Count;\r
-\r
- col.CopyTo(contents, 0);\r
- }\r
-\r
- public Stack (int initialCapacity) {\r
- if (initialCapacity < 0)\r
- throw new ArgumentOutOfRangeException ("initialCapacity");\r
- \r
- capacity = Math.Max (initialCapacity, 16);\r
- contents = new object[capacity];\r
- }\r
-\r
- [Serializable]\r
- private class SyncStack : Stack {\r
-\r
- Stack stack;\r
-\r
- internal SyncStack(Stack s) {\r
- stack = s;\r
- }\r
- \r
- public override int Count {\r
- get { \r
- lock (stack) {\r
- return stack.Count; \r
- }\r
- }\r
- }\r
- \r
-/*\r
- public override bool IsReadOnly {\r
- get { \r
- lock (stack) {\r
- return stack.IsReadOnly; \r
- }\r
- }\r
- }\r
-*/\r
- \r
- public override bool IsSynchronized {\r
- get { return true; }\r
- }\r
- \r
- public override object SyncRoot {\r
- get { return stack.SyncRoot; }\r
- }\r
-\r
- public override void Clear() {\r
- lock(stack) { stack.Clear(); }\r
- }\r
-\r
- public override object Clone() {\r
- lock (stack) { \r
- return Stack.Synchronized((Stack)stack.Clone()); \r
- }\r
- }\r
-\r
- public override bool Contains(object obj) {\r
- lock (stack) { return stack.Contains(obj); }\r
- }\r
-\r
- public override void CopyTo(Array array, int index) {\r
- lock (stack) { stack.CopyTo(array, index); }\r
- }\r
-\r
- public override IEnumerator GetEnumerator() {\r
- lock (stack) { \r
- return new Enumerator(stack); \r
- }\r
- }\r
-\r
- public override object Peek() {\r
- lock (stack) { return stack.Peek(); }\r
- }\r
-\r
- public override object Pop() {\r
- lock (stack) { return stack.Pop(); }\r
- }\r
-\r
- public override void Push(object obj) {\r
- lock (stack) { stack.Push(obj); }\r
- }\r
-\r
- public override object[] ToArray() {\r
- lock (stack) { return stack.ToArray(); }\r
- }\r
- }\r
-\r
- public static Stack Synchronized(Stack s) {\r
- if (s == null) {\r
- throw new ArgumentNullException();\r
- }\r
-\r
- return new SyncStack(s);\r
- }\r
-\r
- public virtual int Count {\r
- get { return count; }\r
- }\r
-\r
-/*\r
- public virtual bool IsReadOnly {\r
- get { return false; }\r
- }\r
-*/\r
-\r
- public virtual bool IsSynchronized {\r
- get { return false; }\r
- }\r
-\r
- public virtual object SyncRoot {\r
- get { return this; }\r
- }\r
-\r
- public virtual void Clear() {\r
- modCount++;\r
-\r
- for (int i = 0; i < count; i++) {\r
- contents[i] = null;\r
- }\r
-\r
- count = 0;\r
- current = -1;\r
- }\r
-\r
- public virtual object Clone() {\r
- Stack stack = new Stack (contents);\r
- stack.current = current;\r
- stack.count = count;\r
- return stack;\r
- }\r
-\r
- public virtual bool Contains(object obj) {\r
- if (count == 0)\r
- return false;\r
- \r
- if (obj == null) {\r
- for (int i = 0; i < count; i++) {\r
- if (contents[i] == null)\r
- return true; \r
- }\r
- } else {\r
- for (int i = 0; i < count; i++) {\r
- if (obj.Equals (contents[i]))\r
- return true; \r
- }\r
- }\r
-\r
- return false;\r
- }\r
-\r
- public virtual void CopyTo (Array array, int index) {\r
- if (array == null) {\r
- throw new ArgumentNullException("array");\r
- }\r
-\r
- if (index < 0) {\r
- throw new ArgumentOutOfRangeException("index");\r
- }\r
-\r
- if (array.Rank > 1 || \r
- array.Length > 0 && index >= array.Length || \r
- count > array.Length - index) {\r
- throw new ArgumentException();\r
- }\r
-\r
- for (int i = current; i != -1; i--) {\r
- array.SetValue(contents[i], \r
- count - (i + 1) + index);\r
- }\r
- }\r
-\r
- private class Enumerator : IEnumerator, ICloneable {\r
- \r
- const int EOF = -1;\r
- const int BOF = -2;\r
-\r
- Stack stack;\r
- private int modCount;\r
- private int current;\r
-\r
- internal Enumerator(Stack s) {\r
- stack = s;\r
- modCount = s.modCount;\r
- current = BOF;\r
- }\r
- \r
- public object Clone ()\r
- {\r
- return MemberwiseClone ();\r
- }\r
-\r
- public virtual object Current {\r
- get {\r
- if (modCount != stack.modCount \r
- || current == BOF\r
- || current == EOF\r
- || current > stack.count)\r
- throw new InvalidOperationException();\r
- return stack.contents[current];\r
- }\r
- }\r
-\r
- public virtual bool MoveNext() {\r
- if (modCount != stack.modCount)\r
- throw new InvalidOperationException();\r
- \r
- switch (current) {\r
- case BOF:\r
- current = stack.current;\r
- return current != -1;\r
- \r
- case EOF:\r
- return false;\r
- \r
- default:\r
- current--; \r
- return current != -1;\r
- }\r
- }\r
-\r
- public virtual void Reset() {\r
- if (modCount != stack.modCount) {\r
- throw new InvalidOperationException();\r
- }\r
-\r
- current = BOF;\r
- }\r
- }\r
-\r
- public virtual IEnumerator GetEnumerator() {\r
- return new Enumerator(this);\r
- }\r
-\r
- public virtual object Peek() {\r
- if (current == -1) {\r
- throw new InvalidOperationException();\r
- } else {\r
- return contents[current];\r
- }\r
- }\r
-\r
- public virtual object Pop() {\r
- if (current == -1) {\r
- throw new InvalidOperationException();\r
- } else {\r
- modCount++;\r
-\r
- object ret = contents[current];\r
- contents [current] = null;\r
- \r
- count--;\r
- current--;\r
-\r
- // if we're down to capacity/4, go back to a \r
- // lower array size. this should keep us from \r
- // sucking down huge amounts of memory when \r
- // putting large numbers of items in the Stack.\r
- // if we're lower than 16, don't bother, since \r
- // it will be more trouble than it's worth.\r
- if (count <= (capacity/4) && count > 16) {\r
- Resize(capacity/2);\r
- }\r
-\r
- return ret;\r
- }\r
- }\r
-\r
- public virtual void Push(Object o) {\r
- modCount++;\r
-\r
- if (capacity == count) {\r
- Resize(capacity * 2);\r
- }\r
-\r
- count++;\r
- current++;\r
-\r
- contents[current] = o;\r
- }\r
-\r
- public virtual object[] ToArray() {\r
- object[] ret = new object[count];\r
-\r
- Array.Copy(contents, ret, count);\r
-\r
- // ret needs to be in LIFO order\r
- Array.Reverse(ret);\r
-\r
- return ret;\r
- }\r
- }\r
-}\r
+//
+// System.Collections.Stack
+//
+// Author:
+// Garrett Rooney (rooneg@electricjellyfish.net)
+//
+// (C) 2001 Garrett Rooney
+//
+
+//
+// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
+
+using System.Runtime.InteropServices;
+
+namespace System.Collections {
+
+ [ComVisible(true)]
+ [System.Diagnostics.DebuggerDisplay ("Count={Count}")]
+ [System.Diagnostics.DebuggerTypeProxy (typeof (CollectionDebuggerView))]
+ [Serializable]
+#if INSIDE_CORLIB
+ public
+#else
+ internal
+#endif
+ class Stack : ICollection, IEnumerable, ICloneable {
+
+ // properties
+ private object[] contents;
+ private int current = -1;
+ private int count;
+ private int capacity;
+ private int modCount;
+
+ const int default_capacity = 16;
+
+ private void Resize(int ncapacity)
+ {
+
+ ncapacity = Math.Max (ncapacity, 16);
+ object[] ncontents = new object[ncapacity];
+
+ Array.Copy(contents, ncontents, count);
+
+ capacity = ncapacity;
+ contents = ncontents;
+ }
+
+ public Stack ()
+ {
+ contents = new object[default_capacity];
+ capacity = default_capacity;
+ }
+
+ public Stack(ICollection col) : this (col == null ? 16 : col.Count) {
+ if (col == null)
+ throw new ArgumentNullException("col");
+
+ // We have to do this because msft seems to call the
+ // enumerator rather than CopyTo. This affects classes
+ // like bitarray.
+ foreach (object o in col)
+ Push (o);
+ }
+
+ public Stack (int initialCapacity)
+ {
+ if (initialCapacity < 0)
+ throw new ArgumentOutOfRangeException ("initialCapacity");
+
+ capacity = initialCapacity;
+ contents = new object[capacity];
+ }
+
+ [Serializable]
+ private class SyncStack : Stack {
+
+ Stack stack;
+
+ internal SyncStack(Stack s) {
+ stack = s;
+ }
+
+ public override int Count {
+ get {
+ lock (stack) {
+ return stack.Count;
+ }
+ }
+ }
+
+/*
+ public override bool IsReadOnly {
+ get {
+ lock (stack) {
+ return stack.IsReadOnly;
+ }
+ }
+ }
+*/
+
+ 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 stack)
+ {
+ if (stack == null)
+ throw new ArgumentNullException ("stack");
+
+ return new SyncStack (stack);
+ }
+
+ 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 = new Stack (contents);
+ stack.current = current;
+ stack.count = count;
+ return stack;
+ }
+
+ public virtual bool Contains(object obj) {
+ if (count == 0)
+ return false;
+
+ if (obj == null) {
+ for (int i = 0; i < count; i++) {
+ if (contents[i] == null)
+ return true;
+ }
+ } else {
+ for (int i = 0; i < count; i++) {
+ if (obj.Equals (contents[i]))
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ public virtual void CopyTo (Array array, int index) {
+ if (array == null) {
+ throw new ArgumentNullException("array");
+ }
+
+ if (index < 0) {
+ throw new ArgumentOutOfRangeException("index");
+ }
+
+ if (array.Rank > 1 ||
+ array.Length > 0 && 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, ICloneable {
+
+ const int EOF = -1;
+ const int BOF = -2;
+
+ Stack stack;
+ private int modCount;
+ private int current;
+
+ internal Enumerator(Stack s) {
+ stack = s;
+ modCount = s.modCount;
+ current = BOF;
+ }
+
+ public object Clone ()
+ {
+ return MemberwiseClone ();
+ }
+
+ public virtual object Current {
+ get {
+ if (modCount != stack.modCount
+ || current == BOF
+ || current == EOF
+ || current > stack.count)
+ throw new InvalidOperationException();
+ return stack.contents[current];
+ }
+ }
+
+ public virtual bool MoveNext() {
+ if (modCount != stack.modCount)
+ throw new InvalidOperationException();
+
+ switch (current) {
+ case BOF:
+ current = stack.current;
+ return current != -1;
+
+ case EOF:
+ return false;
+
+ default:
+ current--;
+ return current != -1;
+ }
+ }
+
+ public virtual void Reset() {
+ if (modCount != stack.modCount) {
+ throw new InvalidOperationException();
+ }
+
+ current = BOF;
+ }
+ }
+
+ 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];
+ contents [current] = null;
+
+ count--;
+ current--;
+
+ // if we're down to capacity/4, go back to a
+ // lower array size. this should keep us from
+ // sucking down huge amounts of memory when
+ // putting large numbers of items in the Stack.
+ // if we're lower than 16, don't bother, since
+ // it will be more trouble than it's worth.
+ if (count <= (capacity/4) && count > 16) {
+ Resize(capacity/2);
+ }
+
+ return ret;
+ }
+ }
+
+ public virtual void Push (Object obj)
+ {
+ modCount++;
+
+ if (capacity == count) {
+ Resize(capacity * 2);
+ }
+
+ count++;
+ current++;
+
+ contents[current] = obj;
+ }
+
+ 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;
+ }
+ }
+}
projects / mono.git / blobdiff