mcs/class/corlib/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 #if NET_2_0
  35 using System;
  36 using System.Runtime.InteropServices;
  37
  38 namespace System.Collections.Generic
  39 {
  40         [CLSCompliant (false)]
  41         [ComVisible (false)]
  42         public class Stack <T> : ICollection <T>, IEnumerable <T>, ICollection, IEnumerable {
  43
  44                 T [] data;
  45                 int size;
  46                 int ver;
  47
  48                 public Stack ()
  49                 {
  50                 }
  51
  52                 public Stack (int count)
  53                 {
  54                         if (count < 0)
  55                                 throw new ArgumentOutOfRangeException ("count");
  56
  57                         data = new T [count];
  58                 }
  59
  60                 public Stack (IEnumerable <T> collection)
  61                 {
  62                         if (collection == null)
  63                                 throw new ArgumentNullException ("collection");
  64
  65                         ICollection <T> col = collection as ICollection <T>;
  66
  67
  68                         if (col != null) {
  69                                 size = col.Count;
  70                                 data = new T [size];
  71                                 col.CopyTo (data, 0);
  72                         } else {
  73 #if GMCS_FIXED
  74                                 foreach (T t in collection)
  75                                         Push (t);
  76 #endif
  77                         }
  78                 }
  79
  80                 public void Clear ()
  81                 {
  82                         if (data != null)
  83                                 Array.Clear (data, 0, data.Length);
  84
  85                         size = 0;
  86                         ver ++;
  87                 }
  88
  89                 public bool Contains (T t)
  90                 {
  91                         return data != null && Array.IndexOf (data, t, 0, size) != -1;
  92                 }
  93
  94                 public void CopyTo (T [] dest, int idx)
  95                 {
  96                         // this gets copied in the order that it is poped
  97                         if (data != null) {
  98                                 data.CopyTo (dest, idx);
  99                                 Array.Reverse (dest, idx, size);
 100                         }
 101                 }
 102
 103                 public T Peek ()
 104                 {
 105                         if (size == 0)
 106                                 throw new InvalidOperationException ();
 107
 108                         ver ++;
 109
 110                         return data [size - 1];
 111                 }
 112
 113                 public T Pop ()
 114                 {
 115                         if (size == 0)
 116                                 throw new InvalidOperationException ();
 117
 118                         ver ++;
 119
 120                         return data [-- size];
 121                 }
 122
 123                 public void Push (T t)
 124                 {
 125                         if (size == 0 || size == data.Length)
 126                                 Array.Resize <T> (ref data, size == 0 ? 10 : 2 * size);
 127
 128                         ver ++;
 129
 130                         data [++ size] = t;
 131                 }
 132
 133                 public T [] ToArray ()
 134                 {
 135                         T [] copy = new T [size];
 136                         CopyTo (copy, 0);
 137                         return copy;
 138                 }
 139
 140                 public void TrimToSize ()
 141                 {
 142                         // for some broken reason, msft increments the version here
 143                         ver ++;
 144
 145                         if (size == 0)
 146                                 data = null;
 147                         else
 148                                 Array.Resize <T> (ref data, size);
 149                 }
 150
 151                 public int Count {
 152                         get { return size; }
 153                 }
 154
 155                 bool ICollection <T>.IsReadOnly {
 156                         get { return false; }
 157                 }
 158
 159                 bool ICollection.IsSynchronized {
 160                         get { return false; }
 161                 }
 162
 163                 object ICollection.SyncRoot {
 164                         get { return this; }
 165                 }
 166
 167                 void ICollection <T>.Add (T t)
 168                 {
 169                         Push (t);
 170                 }
 171
 172                 bool ICollection <T>.Remove (T t)
 173                 {
 174                         throw new InvalidOperationException ("");
 175                 }
 176
 177                 void ICollection.CopyTo (Array dest, int idx)
 178                 {
 179                         try {
 180                                 if (data != null) {
 181                                         data.CopyTo (dest, idx);
 182                                         Array.Reverse (dest, idx, size);
 183                                 }
 184                         } catch (ArrayTypeMismatchException) {
 185                                 throw new ArgumentException ();
 186                         }
 187                 }
 188
 189                 public Enumerator <T> GetEnumerator ()
 190                 {
 191                         return new Enumerator <T> (this);
 192                 }
 193
 194                 IEnumerator <T> IEnumerable<T>.GetEnumerator ()
 195                 {
 196                         return GetEnumerator ();
 197                 }
 198
 199                 IEnumerator IEnumerable.GetEnumerator ()
 200                 {
 201                         return GetEnumerator ();
 202                 }
 203
 204                 public struct Enumerator <T> : IEnumerator <T>, IEnumerator, IDisposable {
 205                         const int NOT_STARTED = -2;
 206
 207                         // this MUST be -1, because we depend on it in move next.
 208                         // we just decr the size, so, 0 - 1 == FINISHED
 209                         const int FINISHED = -1;
 210
 211                         Stack <T> parent;
 212                         int idx;
 213                         int ver;
 214
 215                         internal Enumerator (Stack <T> t)
 216                         {
 217                                 parent = t;
 218                                 idx = NOT_STARTED;
 219                                 ver = t.ver;
 220                         }
 221
 222                         // for some fucked up reason, MSFT added a useless dispose to this class
 223                         // It means that in foreach, we must still do a try/finally. Broken, very
 224                         // broken.
 225                         public void Dispose ()
 226                         {
 227                                 idx = NOT_STARTED;
 228                         }
 229
 230                         public bool MoveNext ()
 231                         {
 232                                 if (ver != parent.ver)
 233                                         throw new InvalidOperationException ();
 234
 235                                 if (idx == -2)
 236                                         idx = parent.size;
 237
 238                                 return idx != FINISHED && -- idx != FINISHED;
 239                         }
 240
 241                         public T Current {
 242                                 get {
 243                                         if (idx < 0)
 244                                                 throw new InvalidOperationException ();
 245
 246                                         return parent.data [idx];
 247                                 }
 248                         }
 249
 250                         void IEnumerator.Reset ()
 251                         {
 252                                 if (ver != parent.ver)
 253                                         throw new InvalidOperationException ();
 254
 255                                 idx = NOT_STARTED;
 256                         }
 257
 258                         object IEnumerator.Current {
 259                                 get { return Current; }
 260                         }
 261
 262                 }
 263         }
 264 }
 265 #endif