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

   1 //
   2 // System.Collections.Stack
   3 //
   4 // Author:
   5 //    Garrett Rooney (rooneg@electricjellyfish.net)
   6 //
   7 // (C) 2001 Garrett Rooney
   8 //
   9
  10 //
  11 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  12 //
  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:
  20 //
  21 // The above copyright notice and this permission notice shall be
  22 // included in all copies or substantial portions of the Software.
  23 //
  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.
  31 //
  32
  33 using System.Runtime.InteropServices;
  34
  35 namespace System.Collections {
  36
  37 #if NET_2_0
  38         [ComVisible(true)]
  39 #endif
  40         [Serializable]
  41         public class Stack : ICollection, IEnumerable, ICloneable {
  42
  43                 // properties
  44                 private object[] contents;
  45                 private int current = -1;
  46                 private int count = 0;
  47                 private int capacity;
  48                 private int modCount = 0;
  49
  50                 private void Resize(int ncapacity) {
  51
  52                         ncapacity = Math.Max (ncapacity, 16);
  53                         object[] ncontents = new object[ncapacity];
  54
  55                         Array.Copy(contents, ncontents, count);
  56
  57                         capacity = ncapacity;
  58                         contents = ncontents;
  59                 }
  60
  61                 public Stack () : this (16) {}
  62
  63                 public Stack(ICollection col) : this (col == null ? 16 : col.Count) {
  64                         if (col == null)
  65                                 throw new ArgumentNullException("col");
  66
  67                         // We have to do this because msft seems to call the
  68                         // enumerator rather than CopyTo. This affects classes
  69                         // like bitarray.
  70                         foreach (object o in col)
  71                                 Push (o);
  72                 }
  73
  74                 public Stack (int initialCapacity) {
  75                         if (initialCapacity < 0)
  76                                 throw new ArgumentOutOfRangeException ("initialCapacity");
  77
  78                         capacity = Math.Max (initialCapacity, 16);
  79                         contents = new object[capacity];
  80                 }
  81
  82                 [Serializable]
  83                 private class SyncStack : Stack {
  84
  85                         Stack stack;
  86
  87                         internal SyncStack(Stack s) {
  88                                 stack = s;
  89                         }
  90
  91                         public override int Count {
  92                                 get {
  93                                         lock (stack) {
  94                                                 return stack.Count;
  95                                         }
  96                                 }
  97                         }
  98
  99 /*
 100                         public override bool IsReadOnly {
 101                                 get {
 102                                         lock (stack) {
 103                                                 return stack.IsReadOnly;
 104                                         }
 105                                 }
 106                         }
 107 */
 108
 109                         public override bool IsSynchronized {
 110                                 get { return true; }
 111                         }
 112
 113                         public override object SyncRoot {
 114                                 get { return stack.SyncRoot; }
 115                         }
 116
 117                         public override void Clear() {
 118                                 lock(stack) { stack.Clear(); }
 119                         }
 120
 121                         public override object Clone() {
 122                                 lock (stack) {
 123                                         return Stack.Synchronized((Stack)stack.Clone());
 124                                 }
 125                         }
 126
 127                         public override bool Contains(object obj) {
 128                                 lock (stack) { return stack.Contains(obj); }
 129                         }
 130
 131                         public override void CopyTo(Array array, int index) {
 132                                 lock (stack) { stack.CopyTo(array, index); }
 133                         }
 134
 135                         public override IEnumerator GetEnumerator() {
 136                                 lock (stack) {
 137                                         return new Enumerator(stack);
 138                                 }
 139                         }
 140
 141                         public override object Peek() {
 142                                 lock (stack) { return stack.Peek(); }
 143                         }
 144
 145                         public override object Pop() {
 146                                 lock (stack) { return stack.Pop(); }
 147                         }
 148
 149                         public override void Push(object obj) {
 150                                 lock (stack) { stack.Push(obj); }
 151                         }
 152
 153                         public override object[] ToArray() {
 154                                 lock (stack) { return stack.ToArray(); }
 155                         }
 156                 }
 157
 158                 public static Stack Synchronized(Stack s) {
 159                         if (s == null) {
 160                                 throw new ArgumentNullException();
 161                         }
 162
 163                         return new SyncStack(s);
 164                 }
 165
 166                 public virtual int Count {
 167                         get { return count; }
 168                 }
 169
 170 /*
 171                 public virtual bool IsReadOnly {
 172                         get { return false; }
 173                 }
 174 */
 175
 176                 public virtual bool IsSynchronized {
 177                         get { return false; }
 178                 }
 179
 180                 public virtual object SyncRoot {
 181                         get { return this; }
 182                 }
 183
 184                 public virtual void Clear() {
 185                         modCount++;
 186
 187                         for (int i = 0; i < count; i++) {
 188                                 contents[i] = null;
 189                         }
 190
 191                         count = 0;
 192                         current = -1;
 193                 }
 194
 195                 public virtual object Clone() {
 196                         Stack stack = new Stack (contents);
 197                         stack.current = current;
 198                         stack.count = count;
 199                         return stack;
 200                 }
 201
 202                 public virtual bool Contains(object obj) {
 203                         if (count == 0)
 204                                 return false;
 205
 206                         if (obj == null) {
 207                                         for (int i = 0; i < count; i++) {
 208                                                 if (contents[i] == null)
 209                                                         return true;
 210                                         }
 211                         } else {
 212                                         for (int i = 0; i < count; i++) {
 213                                                 if (obj.Equals (contents[i]))
 214                                                         return true;
 215                                         }
 216                         }
 217
 218                         return false;
 219                 }
 220
 221                 public virtual void CopyTo (Array array, int index) {
 222                         if (array == null) {
 223                                 throw new ArgumentNullException("array");
 224                         }
 225
 226                         if (index < 0) {
 227                                 throw new ArgumentOutOfRangeException("index");
 228                         }
 229
 230                         if (array.Rank > 1 ||
 231                             array.Length > 0 && index >= array.Length ||
 232                             count > array.Length - index) {
 233                                 throw new ArgumentException();
 234                         }
 235
 236                         for (int i = current; i != -1; i--) {
 237                                 array.SetValue(contents[i],
 238                                                count - (i + 1) + index);
 239                         }
 240                 }
 241
 242                 private class Enumerator : IEnumerator, ICloneable {
 243
 244                         const int EOF = -1;
 245                         const int BOF = -2;
 246
 247                         Stack stack;
 248                         private int modCount;
 249                         private int current;
 250
 251                         internal Enumerator(Stack s) {
 252                                 stack = s;
 253                                 modCount = s.modCount;
 254                                 current = BOF;
 255                         }
 256
 257                         public object Clone ()
 258                         {
 259                                 return MemberwiseClone ();
 260                         }
 261
 262                         public virtual object Current {
 263                                 get {
 264                                         if (modCount != stack.modCount
 265                                             || current == BOF
 266                                             || current == EOF
 267                                             || current > stack.count)
 268                                                 throw new InvalidOperationException();
 269                                         return stack.contents[current];
 270                                 }
 271                         }
 272
 273                         public virtual bool MoveNext() {
 274                                 if (modCount != stack.modCount)
 275                                         throw new InvalidOperationException();
 276
 277                                 switch (current) {
 278                                 case BOF:
 279                                         current = stack.current;
 280                                         return current != -1;
 281
 282                                 case EOF:
 283                                         return false;
 284
 285                                 default:
 286                                         current--;
 287                                         return current != -1;
 288                                 }
 289                         }
 290
 291                         public virtual void Reset() {
 292                                 if (modCount != stack.modCount) {
 293                                         throw new InvalidOperationException();
 294                                 }
 295
 296                                 current = BOF;
 297                         }
 298                 }
 299
 300                 public virtual IEnumerator GetEnumerator() {
 301                         return new Enumerator(this);
 302                 }
 303
 304                 public virtual object Peek() {
 305                         if (current == -1) {
 306                                 throw new InvalidOperationException();
 307                         } else {
 308                                 return contents[current];
 309                         }
 310                 }
 311
 312                 public virtual object Pop() {
 313                         if (current == -1) {
 314                                 throw new InvalidOperationException();
 315                         } else {
 316                                 modCount++;
 317
 318                                 object ret = contents[current];
 319                                 contents [current] = null;
 320
 321                                 count--;
 322                                 current--;
 323
 324                                 // if we're down to capacity/4, go back to a
 325                                 // lower array size.  this should keep us from
 326                                 // sucking down huge amounts of memory when
 327                                 // putting large numbers of items in the Stack.
 328                                 // if we're lower than 16, don't bother, since
 329                                 // it will be more trouble than it's worth.
 330                                 if (count <= (capacity/4) && count > 16) {
 331                                         Resize(capacity/2);
 332                                 }
 333
 334                                 return ret;
 335                         }
 336                 }
 337
 338                 public virtual void Push(Object o) {
 339                         modCount++;
 340
 341                         if (capacity == count) {
 342                                 Resize(capacity * 2);
 343                         }
 344
 345                         count++;
 346                         current++;
 347
 348                         contents[current] = o;
 349                 }
 350
 351                 public virtual object[] ToArray() {
 352                         object[] ret = new object[count];
 353
 354                         Array.Copy(contents, ret, count);
 355
 356                         // ret needs to be in LIFO order
 357                         Array.Reverse(ret);
 358
 359                         return ret;
 360                 }
 361         }
 362 }