mcs/class/referencesource/mscorlib/system/collections/stack.cs

   1 // ==++==
   2 //
   3 //   Copyright (c) Microsoft Corporation.  All rights reserved.
   4 //
   5 // ==--==
   6 /*=============================================================================
   7 **
   8 ** Class: Stack
   9 **
  10 ** <OWNER>Microsoft</OWNER>
  11 **
  12 ** Purpose: An array implementation of a stack.
  13 **
  14 **
  15 =============================================================================*/
  16 namespace System.Collections {
  17     using System;
  18     using System.Security.Permissions;
  19     using System.Diagnostics;
  20     using System.Diagnostics.CodeAnalysis;
  21     using System.Diagnostics.Contracts;
  22
  23     // A simple stack of objects.  Internally it is implemented as an array,
  24     // so Push can be O(n).  Pop is O(1).
  25     [DebuggerTypeProxy(typeof(System.Collections.Stack.StackDebugView))]
  26     [DebuggerDisplay("Count = {Count}")]
  27 [System.Runtime.InteropServices.ComVisible(true)]
  28     [Serializable]
  29     public class Stack : ICollection, ICloneable {
  30         private Object[] _array;     // Storage for stack elements
  31         [ContractPublicPropertyName("Count")]
  32         private int _size;           // Number of items in the stack.
  33         private int _version;        // Used to keep enumerator in sync w/ collection.
  34         [NonSerialized]
  35         private Object _syncRoot;
  36
  37         private const int _defaultCapacity = 10;
  38
  39         public Stack() {
  40             _array = new Object[_defaultCapacity];
  41             _size = 0;
  42             _version = 0;
  43         }
  44
  45         // Create a stack with a specific initial capacity.  The initial capacity
  46         // must be a non-negative number.
  47         public Stack(int initialCapacity) {
  48             if (initialCapacity < 0)
  49                 throw new ArgumentOutOfRangeException("initialCapacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  50             Contract.EndContractBlock();
  51             if (initialCapacity < _defaultCapacity)
  52                 initialCapacity = _defaultCapacity;  // Simplify doubling logic in Push.
  53             _array = new Object[initialCapacity];
  54             _size = 0;
  55             _version = 0;
  56         }
  57
  58         // Fills a Stack with the contents of a particular collection.  The items are
  59         // pushed onto the stack in the same order they are read by the enumerator.
  60         //
  61         public Stack(ICollection col) : this((col==null ? 32 : col.Count))
  62         {
  63             if (col==null)
  64                 throw new ArgumentNullException("col");
  65             Contract.EndContractBlock();
  66             IEnumerator en = col.GetEnumerator();
  67             while(en.MoveNext())
  68                 Push(en.Current);
  69         }
  70
  71         public virtual int Count {
  72             get {
  73                 Contract.Ensures(Contract.Result<int>() >= 0);
  74                 return _size;
  75             }
  76         }
  77
  78         public virtual bool IsSynchronized {
  79             get { return false; }
  80         }
  81
  82         public virtual Object SyncRoot {
  83             get {
  84                 if( _syncRoot == null) {
  85                     System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
  86                 }
  87                 return _syncRoot;
  88             }
  89         }
  90
  91         // Removes all Objects from the Stack.
  92         public virtual void Clear() {
  93             Array.Clear(_array, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
  94             _size = 0;
  95             _version++;
  96         }
  97
  98         public virtual Object Clone() {
  99             Contract.Ensures(Contract.Result<Object>() != null);
 100
 101             Stack s = new Stack(_size);
 102             s._size = _size;
 103             Array.Copy(_array, 0, s._array, 0, _size);
 104             s._version = _version;
 105             return s;
 106         }
 107
 108         public virtual bool Contains(Object obj) {
 109             int count = _size;
 110
 111             while (count-- > 0) {
 112                 if (obj == null) {
 113                     if (_array[count] == null)
 114                         return true;
 115                 }
 116                 else if (_array[count] != null && _array[count].Equals(obj)) {
 117                     return true;
 118                 }
 119             }
 120             return false;
 121         }
 122
 123         // Copies the stack into an array.
 124         public virtual void CopyTo(Array array, int index) {
 125             if (array==null)
 126                 throw new ArgumentNullException("array");
 127             if (array.Rank != 1)
 128                 throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
 129             if (index < 0)
 130                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
 131             if (array.Length - index < _size)
 132                 throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
 133             Contract.EndContractBlock();
 134
 135             int i = 0;
 136             if (array is Object[]) {
 137                 Object[] objArray = (Object[]) array;
 138                 while(i < _size) {
 139                     objArray[i+index] = _array[_size-i-1];
 140                     i++;
 141                 }
 142             }
 143             else {
 144                 while(i < _size) {
 145                     array.SetValue(_array[_size-i-1], i+index);
 146                     i++;
 147                 }
 148             }
 149         }
 150
 151         // Returns an IEnumerator for this Stack.
 152         public virtual IEnumerator GetEnumerator() {
 153             Contract.Ensures(Contract.Result<IEnumerator>() != null);
 154             return new StackEnumerator(this);
 155         }
 156
 157         // Returns the top object on the stack without removing it.  If the stack
 158         // is empty, Peek throws an InvalidOperationException.
 159         public virtual Object Peek() {
 160             if (_size==0)
 161                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack"));
 162             Contract.EndContractBlock();
 163             return _array[_size-1];
 164         }
 165
 166         // Pops an item from the top of the stack.  If the stack is empty, Pop
 167         // throws an InvalidOperationException.
 168         public virtual Object Pop() {
 169             if (_size == 0)
 170                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack"));
 171             //Contract.Ensures(Count == Contract.OldValue(Count) - 1);
 172             Contract.EndContractBlock();
 173             _version++;
 174             Object obj = _array[--_size];
 175             _array[_size] = null;     // Free memory quicker.
 176             return obj;
 177         }
 178
 179         // Pushes an item to the top of the stack.
 180         //
 181         public virtual void Push(Object obj) {
 182             //Contract.Ensures(Count == Contract.OldValue(Count) + 1);
 183             if (_size == _array.Length) {
 184                 Object[] newArray = new Object[2*_array.Length];
 185                 Array.Copy(_array, 0, newArray, 0, _size);
 186                 _array = newArray;
 187             }
 188             _array[_size++] = obj;
 189             _version++;
 190         }
 191
 192         // Returns a synchronized Stack.
 193         //
 194         [HostProtection(Synchronization=true)]
 195         public static Stack Synchronized(Stack stack) {
 196             if (stack==null)
 197                 throw new ArgumentNullException("stack");
 198             Contract.Ensures(Contract.Result<Stack>() != null);
 199             Contract.EndContractBlock();
 200             return new SyncStack(stack);
 201         }
 202
 203
 204         // Copies the Stack to an array, in the same order Pop would return the items.
 205         public virtual Object[] ToArray()
 206         {
 207             Contract.Ensures(Contract.Result<Object[]>() != null);
 208
 209             Object[] objArray = new Object[_size];
 210             int i = 0;
 211             while(i < _size) {
 212                 objArray[i] = _array[_size-i-1];
 213                 i++;
 214             }
 215             return objArray;
 216         }
 217
 218         [Serializable]
 219         private class SyncStack : Stack
 220         {
 221             private Stack _s;
 222             private Object _root;
 223
 224             internal SyncStack(Stack stack) {
 225                 _s = stack;
 226                 _root = stack.SyncRoot;
 227             }
 228
 229             public override bool IsSynchronized {
 230                 get { return true; }
 231             }
 232
 233             public override Object SyncRoot {
 234                 get {
 235                     return _root;
 236                 }
 237             }
 238
 239             public override int Count {
 240                 get {
 241                     lock (_root) {
 242                         return _s.Count;
 243                     }
 244                 }
 245             }
 246
 247             public override bool Contains(Object obj) {
 248                 lock (_root) {
 249                     return _s.Contains(obj);
 250                 }
 251             }
 252
 253             public override Object Clone()
 254             {
 255                 lock (_root) {
 256                     return new SyncStack((Stack)_s.Clone());
 257                 }
 258             }
 259
 260             public override void Clear() {
 261                 lock (_root) {
 262                     _s.Clear();
 263                 }
 264             }
 265
 266             public override void CopyTo(Array array, int arrayIndex) {
 267                 lock (_root) {
 268                     _s.CopyTo(array, arrayIndex);
 269                 }
 270             }
 271
 272             public override void Push(Object value) {
 273                 lock (_root) {
 274                     _s.Push(value);
 275                 }
 276             }
 277
 278             [SuppressMessage("Microsoft.Contracts", "CC1055")]  // Thread safety problems with precondition - can't express the precondition as of Dev10.
 279             public override Object Pop() {
 280                 lock (_root) {
 281                     return _s.Pop();
 282                 }
 283             }
 284
 285             public override IEnumerator GetEnumerator() {
 286                 lock (_root) {
 287                     return _s.GetEnumerator();
 288                 }
 289             }
 290
 291             [SuppressMessage("Microsoft.Contracts", "CC1055")]  // Thread safety problems with precondition - can't express the precondition as of Dev10.
 292             public override Object Peek() {
 293                 lock (_root) {
 294                     return _s.Peek();
 295                 }
 296             }
 297
 298             public override Object[] ToArray() {
 299                 lock (_root) {
 300                     return _s.ToArray();
 301                 }
 302             }
 303         }
 304
 305
 306         [Serializable]
 307         private class StackEnumerator : IEnumerator, ICloneable
 308         {
 309             private Stack _stack;
 310             private int _index;
 311             private int _version;
 312             private Object currentElement;
 313
 314             internal StackEnumerator(Stack stack) {
 315                 _stack = stack;
 316                 _version = _stack._version;
 317                 _index = -2;
 318                 currentElement = null;
 319             }
 320
 321             public Object Clone()
 322             {
 323                 return MemberwiseClone();
 324             }
 325
 326             public virtual bool MoveNext() {
 327                 bool retval;
 328                 if (_version != _stack._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
 329                 if (_index == -2) {  // First call to enumerator.
 330                     _index = _stack._size-1;
 331                     retval = ( _index >= 0);
 332                     if (retval)
 333                         currentElement = _stack._array[_index];
 334                     return retval;
 335                 }
 336                 if (_index == -1) {  // End of enumeration.
 337                     return false;
 338                 }
 339
 340                 retval = (--_index >= 0);
 341                 if (retval)
 342                     currentElement = _stack._array[_index];
 343                 else
 344                     currentElement = null;
 345                 return retval;
 346             }
 347
 348             public virtual Object Current {
 349                 get {
 350                     if (_index == -2) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
 351                     if (_index == -1) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));
 352                     return currentElement;
 353                 }
 354             }
 355
 356             public virtual void Reset() {
 357                 if (_version != _stack._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
 358                 _index = -2;
 359                 currentElement = null;
 360             }
 361         }
 362
 363         internal class StackDebugView {
 364             private Stack stack;
 365
 366             public StackDebugView( Stack stack) {
 367                 if( stack == null)
 368                     throw new ArgumentNullException("stack");
 369                 Contract.EndContractBlock();
 370
 371                 this.stack = stack;
 372             }
 373
 374             [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
 375             public Object[] Items   {
 376                 get {
 377                     return stack.ToArray();
 378                 }
 379             }
 380         }
 381     }
 382 }