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