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

   1 //
   2 // System.Collections.Generic.Stack
   3 //
   4 // Authors:
   5 //      Martin Baulig (martin@ximian.com)
   6 //      Ben Maurer (bmaurer@ximian.com)
   7 //
   8 // (C) 2003, 2004 Novell, Inc.
   9 //
  10
  11 //
  12 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  13 //
  14 // Permission is hereby granted, free of charge, to any person obtaining
  15 // a copy of this software and associated documentation files (the
  16 // "Software"), to deal in the Software without restriction, including
  17 // without limitation the rights to use, copy, modify, merge, publish,
  18 // distribute, sublicense, and/or sell copies of the Software, and to
  19 // permit persons to whom the Software is furnished to do so, subject to
  20 // the following conditions:
  21 //
  22 // The above copyright notice and this permission notice shall be
  23 // included in all copies or substantial portions of the Software.
  24 //
  25 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  26 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  27 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  28 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  29 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  30 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  31 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  32 //
  33
  34 using System;
  35 using System.Runtime.InteropServices;
  36 using System.Diagnostics;
  37
  38 namespace System.Collections.Generic
  39 {
  40         [ComVisible (false)]
  41         [Serializable]
  42         [DebuggerDisplay ("Count={Count}")]
  43         [DebuggerTypeProxy (typeof (CollectionDebuggerView))]
  44         public class Stack <T> : IEnumerable <T>, ICollection, IEnumerable
  45         {
  46                 T [] _array;
  47                 int _size;
  48                 int _version;
  49
  50                 private const int INITIAL_SIZE = 16;
  51
  52                 public Stack ()
  53                 {
  54                 }
  55
  56                 public Stack (int count)
  57                 {
  58                         if (count < 0)
  59                                 throw new ArgumentOutOfRangeException ("count");
  60
  61                         _array = new T [count];
  62                 }
  63
  64                 public Stack (IEnumerable <T> collection)
  65                 {
  66                         if (collection == null)
  67                                 throw new ArgumentNullException ("collection");
  68
  69                         ICollection <T> col = collection as ICollection <T>;
  70
  71                         if (col != null) {
  72                                 _size = col.Count;
  73                                 _array = new T [_size];
  74                                 col.CopyTo (_array, 0);
  75                         } else {
  76                                 foreach (T t in collection)
  77                                         Push (t);
  78                         }
  79                 }
  80
  81                 public void Clear ()
  82                 {
  83                         if (_array != null)
  84                                 Array.Clear (_array, 0, _array.Length);
  85
  86                         _size = 0;
  87                         _version ++;
  88                 }
  89
  90                 public bool Contains (T t)
  91                 {
  92                         return _array != null && Array.IndexOf (_array, t, 0, _size) != -1;
  93                 }
  94
  95                 public void CopyTo (T [] dest, int idx)
  96                 {
  97                         if (dest == null)
  98                                 throw new ArgumentNullException ("dest");
  99                         if (idx < 0)
 100                                 throw new ArgumentOutOfRangeException ("idx");
 101
 102                         // this gets copied in the order that it is poped
 103                         if (_array != null) {
 104                                 Array.Copy (_array, 0, dest, idx, _size);
 105                                 Array.Reverse (dest, idx, _size);
 106                         }
 107                 }
 108
 109                 public T Peek ()
 110                 {
 111                         if (_size == 0)
 112                                 throw new InvalidOperationException ();
 113
 114                         return _array [_size - 1];
 115                 }
 116
 117                 public T Pop ()
 118                 {
 119                         if (_size == 0)
 120                                 throw new InvalidOperationException ();
 121
 122                         _version ++;
 123                         T popped = _array [--_size];
 124                         // clear stuff out to make the GC happy
 125                         _array [_size] = default(T);
 126                         return popped;
 127                 }
 128
 129                 public void Push (T t)
 130                 {
 131                         if (_array == null || _size == _array.Length)
 132                                 Array.Resize <T> (ref _array, _size == 0 ? INITIAL_SIZE : 2 * _size);
 133
 134                         _version ++;
 135
 136                         _array [_size++] = t;
 137                 }
 138
 139                 public T [] ToArray ()
 140                 {
 141                         T [] copy = new T [_size];
 142                         CopyTo (copy, 0);
 143                         return copy;
 144                 }
 145
 146                 public void TrimExcess ()
 147                 {
 148                         if (_array != null && (_size < _array.Length * 0.9))
 149                                 Array.Resize <T> (ref _array, _size);
 150                         _version ++;
 151                 }
 152
 153                 public int Count {
 154                         get { return _size; }
 155                 }
 156
 157                 bool ICollection.IsSynchronized {
 158                         get { return false; }
 159                 }
 160
 161                 object ICollection.SyncRoot {
 162                         get { return this; }
 163                 }
 164
 165                 void ICollection.CopyTo (Array dest, int idx)
 166                 {
 167                         try {
 168                                 if (_array != null) {
 169                                         _array.CopyTo (dest, idx);
 170                                         Array.Reverse (dest, idx, _size);
 171                                 }
 172                         } catch (ArrayTypeMismatchException) {
 173                                 throw new ArgumentException ();
 174                         }
 175                 }
 176
 177                 public Enumerator GetEnumerator ()
 178                 {
 179                         return new Enumerator (this);
 180                 }
 181
 182                 IEnumerator <T> IEnumerable<T>.GetEnumerator ()
 183                 {
 184                         return GetEnumerator ();
 185                 }
 186
 187                 IEnumerator IEnumerable.GetEnumerator ()
 188                 {
 189                         return GetEnumerator ();
 190                 }
 191
 192                 [Serializable]
 193                 public struct Enumerator : IEnumerator <T>, IEnumerator, IDisposable {
 194                         const int NOT_STARTED = -2;
 195
 196                         // this MUST be -1, because we depend on it in move next.
 197                         // we just decr the _size, so, 0 - 1 == FINISHED
 198                         const int FINISHED = -1;
 199
 200                         Stack <T> parent;
 201                         int idx;
 202                         int _version;
 203
 204                         internal Enumerator (Stack <T> t)
 205                         {
 206                                 parent = t;
 207                                 idx = NOT_STARTED;
 208                                 _version = t._version;
 209                         }
 210
 211                         // for some fucked up reason, MSFT added a useless dispose to this class
 212                         // It means that in foreach, we must still do a try/finally. Broken, very
 213                         // broken.
 214                         public void Dispose ()
 215                         {
 216                                 idx = FINISHED;
 217                         }
 218
 219                         public bool MoveNext ()
 220                         {
 221                                 if (_version != parent._version)
 222                                         throw new InvalidOperationException ();
 223
 224                                 if (idx == -2)
 225                                         idx = parent._size;
 226
 227                                 return idx != FINISHED && -- idx != FINISHED;
 228                         }
 229
 230                         public T Current {
 231                                 get {
 232                                         if (idx < 0)
 233                                                 throw new InvalidOperationException ();
 234
 235                                         return parent._array [idx];
 236                                 }
 237                         }
 238
 239                         void IEnumerator.Reset ()
 240                         {
 241                                 if (_version != parent._version)
 242                                         throw new InvalidOperationException ();
 243
 244                                 idx = NOT_STARTED;
 245                         }
 246
 247                         object IEnumerator.Current {
 248                                 get { return Current; }
 249                         }
 250
 251                 }
 252         }
 253 }