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