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

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