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