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