2 // System.Collections.Stack
5 // Garrett Rooney (rooneg@electricjellyfish.net)
7 // (C) 2001 Garrett Rooney
11 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
13 // Permission is hereby granted, free of charge, to any person obtaining
14 // a copy of this software and associated documentation files (the
15 // "Software"), to deal in the Software without restriction, including
16 // without limitation the rights to use, copy, modify, merge, publish,
17 // distribute, sublicense, and/or sell copies of the Software, and to
18 // permit persons to whom the Software is furnished to do so, subject to
19 // the following conditions:
21 // The above copyright notice and this permission notice shall be
22 // included in all copies or substantial portions of the Software.
24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 namespace System
.Collections
{
35 [MonoTODO ("Fix serialization compatibility with MS.NET")]
36 public class Stack
: ICollection
, IEnumerable
, ICloneable
{
39 private object[] contents
;
40 private int current
= -1;
41 private int count
= 0;
43 private int modCount
= 0;
45 private void Resize(int ncapacity
) {
47 ncapacity
= Math
.Max (ncapacity
, 16);
48 object[] ncontents
= new object[ncapacity
];
50 Array
.Copy(contents
, ncontents
, count
);
56 public Stack () : this (16) {}
58 public Stack(ICollection col
) : this (col
== null ? 16 : col
.Count
) {
60 throw new ArgumentNullException("col");
62 current
= col
.Count
- 1;
65 col
.CopyTo(contents
, 0);
68 public Stack (int initialCapacity
) {
69 if (initialCapacity
< 0)
70 throw new ArgumentOutOfRangeException ("initialCapacity");
72 capacity
= Math
.Max (initialCapacity
, 16);
73 contents
= new object[capacity
];
77 private class SyncStack
: Stack
{
81 internal SyncStack(Stack s
) {
85 public override int Count
{
94 public override bool IsReadOnly {
97 return stack.IsReadOnly;
103 public override bool IsSynchronized
{
107 public override object SyncRoot
{
108 get { return stack.SyncRoot; }
111 public override void Clear() {
112 lock(stack
) { stack.Clear(); }
115 public override object Clone() {
117 return Stack
.Synchronized((Stack
)stack
.Clone());
121 public override bool Contains(object obj
) {
122 lock (stack
) { return stack.Contains(obj); }
125 public override void CopyTo(Array array
, int index
) {
126 lock (stack
) { stack.CopyTo(array, index); }
129 public override IEnumerator
GetEnumerator() {
131 return new Enumerator(stack
);
135 public override object Peek() {
136 lock (stack
) { return stack.Peek(); }
139 public override object Pop() {
140 lock (stack
) { return stack.Pop(); }
143 public override void Push(object obj
) {
144 lock (stack
) { stack.Push(obj); }
147 public override object[] ToArray() {
148 lock (stack
) { return stack.ToArray(); }
152 public static Stack
Synchronized(Stack s
) {
154 throw new ArgumentNullException();
157 return new SyncStack(s
);
160 public virtual int Count
{
161 get { return count; }
165 public virtual bool IsReadOnly {
166 get { return false; }
170 public virtual bool IsSynchronized
{
171 get { return false; }
174 public virtual object SyncRoot
{
178 public virtual void Clear() {
181 for (int i
= 0; i
< count
; i
++) {
189 public virtual object Clone() {
190 Stack stack
= new Stack (contents
);
191 stack
.current
= current
;
196 public virtual bool Contains(object obj
) {
201 for (int i
= 0; i
< count
; i
++) {
202 if (contents
[i
] == null)
206 for (int i
= 0; i
< count
; i
++) {
207 if (contents
[i
].Equals(obj
))
215 public virtual void CopyTo (Array array
, int index
) {
217 throw new ArgumentNullException("array");
221 throw new ArgumentOutOfRangeException("index");
224 if (array
.Rank
> 1 ||
225 index
>= array
.Length
||
226 count
> array
.Length
- index
) {
227 throw new ArgumentException();
230 for (int i
= current
; i
!= -1; i
--) {
231 array
.SetValue(contents
[i
],
232 count
- (i
+ 1) + index
);
236 private class Enumerator
: IEnumerator
, ICloneable
{
242 private int modCount
;
245 internal Enumerator(Stack s
) {
247 modCount
= s
.modCount
;
251 public object Clone ()
253 return MemberwiseClone ();
256 public virtual object Current
{
258 if (modCount
!= stack
.modCount
261 || current
> stack
.count
)
262 throw new InvalidOperationException();
263 return stack
.contents
[current
];
267 public virtual bool MoveNext() {
268 if (modCount
!= stack
.modCount
)
269 throw new InvalidOperationException();
273 current
= stack
.current
;
274 return current
!= -1;
281 return current
!= -1;
285 public virtual void Reset() {
286 if (modCount
!= stack
.modCount
) {
287 throw new InvalidOperationException();
294 public virtual IEnumerator
GetEnumerator() {
295 return new Enumerator(this);
298 public virtual object Peek() {
300 throw new InvalidOperationException();
302 return contents
[current
];
306 public virtual object Pop() {
308 throw new InvalidOperationException();
312 object ret
= contents
[current
];
313 contents
[current
] = null;
318 // if we're down to capacity/4, go back to a
319 // lower array size. this should keep us from
320 // sucking down huge amounts of memory when
321 // putting large numbers of items in the Stack.
322 // if we're lower than 16, don't bother, since
323 // it will be more trouble than it's worth.
324 if (count
<= (capacity
/4) && count
> 16) {
332 public virtual void Push(Object o
) {
335 if (capacity
== count
) {
336 Resize(capacity
* 2);
342 contents
[current
] = o
;
345 public virtual object[] ToArray() {
346 object[] ret
= new object[count
];
348 Array
.Copy(contents
, ret
, count
);
350 // ret needs to be in LIFO order