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 using System
.Runtime
.InteropServices
;
35 namespace System
.Collections
{
38 [System
.Diagnostics
.DebuggerDisplay ("Count={Count}")]
39 [System
.Diagnostics
.DebuggerTypeProxy (typeof (CollectionDebuggerView
))]
46 class Stack
: ICollection
, IEnumerable
, ICloneable
{
49 private object[] contents
;
50 private int current
= -1;
55 const int default_capacity
= 16;
57 private void Resize(int ncapacity
)
60 ncapacity
= Math
.Max (ncapacity
, 16);
61 object[] ncontents
= new object[ncapacity
];
63 Array
.Copy(contents
, ncontents
, count
);
71 contents
= new object[default_capacity
];
72 capacity
= default_capacity
;
75 public Stack(ICollection col
) : this (col
== null ? 16 : col
.Count
) {
77 throw new ArgumentNullException("col");
79 // We have to do this because msft seems to call the
80 // enumerator rather than CopyTo. This affects classes
82 foreach (object o
in col
)
86 public Stack (int initialCapacity
)
88 if (initialCapacity
< 0)
89 throw new ArgumentOutOfRangeException ("initialCapacity");
91 capacity
= initialCapacity
;
92 contents
= new object[capacity
];
96 private class SyncStack
: Stack
{
100 internal SyncStack(Stack s
) {
104 public override int Count
{
113 public override bool IsReadOnly {
116 return stack.IsReadOnly;
122 public override bool IsSynchronized
{
126 public override object SyncRoot
{
127 get { return stack.SyncRoot; }
130 public override void Clear() {
131 lock(stack
) { stack.Clear(); }
134 public override object Clone() {
136 return Stack
.Synchronized((Stack
)stack
.Clone());
140 public override bool Contains(object obj
) {
141 lock (stack
) { return stack.Contains(obj); }
144 public override void CopyTo(Array array
, int index
) {
145 lock (stack
) { stack.CopyTo(array, index); }
148 public override IEnumerator
GetEnumerator() {
150 return new Enumerator(stack
);
154 public override object Peek() {
155 lock (stack
) { return stack.Peek(); }
158 public override object Pop() {
159 lock (stack
) { return stack.Pop(); }
162 public override void Push(object obj
) {
163 lock (stack
) { stack.Push(obj); }
166 public override object[] ToArray() {
167 lock (stack
) { return stack.ToArray(); }
171 public static Stack
Synchronized (Stack stack
)
174 throw new ArgumentNullException ("stack");
176 return new SyncStack (stack
);
179 public virtual int Count
{
180 get { return count; }
184 public virtual bool IsReadOnly {
185 get { return false; }
189 public virtual bool IsSynchronized
{
190 get { return false; }
193 public virtual object SyncRoot
{
197 public virtual void Clear() {
200 for (int i
= 0; i
< count
; i
++) {
208 public virtual object Clone() {
209 Stack stack
= new Stack (contents
);
210 stack
.current
= current
;
215 public virtual bool Contains(object obj
) {
220 for (int i
= 0; i
< count
; i
++) {
221 if (contents
[i
] == null)
225 for (int i
= 0; i
< count
; i
++) {
226 if (obj
.Equals (contents
[i
]))
234 public virtual void CopyTo (Array array
, int index
) {
236 throw new ArgumentNullException("array");
240 throw new ArgumentOutOfRangeException("index");
243 if (array
.Rank
> 1 ||
244 array
.Length
> 0 && index
>= array
.Length
||
245 count
> array
.Length
- index
) {
246 throw new ArgumentException();
249 for (int i
= current
; i
!= -1; i
--) {
250 array
.SetValue(contents
[i
],
251 count
- (i
+ 1) + index
);
255 private class Enumerator
: IEnumerator
, ICloneable
{
261 private int modCount
;
264 internal Enumerator(Stack s
) {
266 modCount
= s
.modCount
;
270 public object Clone ()
272 return MemberwiseClone ();
275 public virtual object Current
{
277 if (modCount
!= stack
.modCount
280 || current
> stack
.count
)
281 throw new InvalidOperationException();
282 return stack
.contents
[current
];
286 public virtual bool MoveNext() {
287 if (modCount
!= stack
.modCount
)
288 throw new InvalidOperationException();
292 current
= stack
.current
;
293 return current
!= -1;
300 return current
!= -1;
304 public virtual void Reset() {
305 if (modCount
!= stack
.modCount
) {
306 throw new InvalidOperationException();
313 public virtual IEnumerator
GetEnumerator() {
314 return new Enumerator(this);
317 public virtual object Peek() {
319 throw new InvalidOperationException();
321 return contents
[current
];
325 public virtual object Pop() {
327 throw new InvalidOperationException();
331 object ret
= contents
[current
];
332 contents
[current
] = null;
337 // if we're down to capacity/4, go back to a
338 // lower array size. this should keep us from
339 // sucking down huge amounts of memory when
340 // putting large numbers of items in the Stack.
341 // if we're lower than 16, don't bother, since
342 // it will be more trouble than it's worth.
343 if (count
<= (capacity
/4) && count
> 16) {
351 public virtual void Push (Object obj
)
355 if (capacity
== count
) {
356 Resize(capacity
* 2);
362 contents
[current
] = obj
;
365 public virtual object[] ToArray() {
366 object[] ret
= new object[count
];
368 Array
.Copy(contents
, ret
, count
);
370 // ret needs to be in LIFO order