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