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