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