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

   1 //
   2 // System.Collections.Generic.Queue
   3 //
   4 // Author:
   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 Queue<T> : IEnumerable <T>, ICollection, IEnumerable
  43         {
  44                 T [] data;
  45                 int head;
  46                 int tail;
  47                 int size;
  48                 int version;
  49                 int defaultCapacity;
  50
  51                 private readonly static int INITIAL_SIZE = 16;
  52
  53                 public Queue ()
  54                 {
  55                         defaultCapacity = INITIAL_SIZE;
  56                 }
  57
  58                 public Queue (int count)
  59                 {
  60                         if (count < 0)
  61                                 throw new ArgumentOutOfRangeException ("count");
  62
  63                         defaultCapacity = count;
  64                         data = new T [count];
  65                 }
  66
  67                 public Queue (IEnumerable <T> collection)
  68                 {
  69                         if (collection == null)
  70                                 throw new ArgumentNullException ("collection");
  71
  72                         foreach (T t in collection)
  73                                 Enqueue (t);
  74                         defaultCapacity = size;
  75                 }
  76
  77                 public void Clear ()
  78                 {
  79                         if (data != null)
  80                                 Array.Clear (data, 0, data.Length);
  81
  82                         head = tail = size = 0;
  83                 }
  84
  85                 public bool Contains (T item)
  86                 {
  87                         if (item == null) {
  88                                 foreach (T t in this)
  89                                         if (t == null)
  90                                                 return true;
  91                         } else {
  92                                 foreach (T t in this)
  93                                         if (item.Equals (t))
  94                                                 return true;
  95                         }
  96
  97                         return false;
  98                 }
  99
 100                 public void CopyTo (T [] array, int idx)
 101                 {
 102                         if (array == null)
 103                                 throw new ArgumentNullException ();
 104
 105                         if ((uint) idx > (uint) array.Length)
 106                                 throw new ArgumentOutOfRangeException ();
 107
 108                         if (array.Length - idx < size)
 109                                 throw new ArgumentOutOfRangeException ();
 110
 111                         if (size == 0)
 112                                 return;
 113
 114                         int contents_length = data.Length;
 115                         int length_from_head = contents_length - head;
 116
 117                         Array.Copy (data, head, array, idx, Math.Min (size, length_from_head));
 118                         if (size > length_from_head)
 119                                 Array.Copy (data, 0, array,
 120                                             idx  + length_from_head,
 121                                             size - length_from_head);
 122
 123                 }
 124
 125                 void ICollection.CopyTo (Array array, int idx)
 126                 {
 127                         if (array == null)
 128                                 throw new ArgumentNullException ();
 129
 130                         if ((uint) idx < (uint) array.Length)
 131                                 throw new ArgumentOutOfRangeException ();
 132
 133                         if (array.Length - idx < size)
 134                                 throw new ArgumentOutOfRangeException ();
 135
 136                         if (size == 0)
 137                                 return;
 138
 139                         try {
 140                                 int contents_length = data.Length;
 141                                 int length_from_head = contents_length - head;
 142
 143                                 Array.Copy (data, head, array, idx, Math.Min (size, length_from_head));
 144                                 if (size > length_from_head)
 145                                         Array.Copy (data, 0, array,
 146                                                     idx  + length_from_head,
 147                                                     size - length_from_head);
 148                         } catch (ArrayTypeMismatchException) {
 149                                 throw new ArgumentException ();
 150                         }
 151                 }
 152
 153                 public T Dequeue ()
 154                 {
 155                         T ret = Peek ();
 156
 157                         // clear stuff out to make the GC happy
 158                         data [head] = default (T);
 159
 160                         if (++head == data.Length)
 161                                 head = 0;
 162                         size --;
 163                         version ++;
 164
 165                         return ret;
 166                 }
 167
 168                 public T Peek ()
 169                 {
 170                         if (size == 0)
 171                                 throw new InvalidOperationException ();
 172
 173                         return data [head];
 174                 }
 175
 176                 public void Enqueue (T item)
 177                 {
 178                         if (data == null || size == data.Length)
 179                                 SetCapacity (Math.Max (size * 2, 4));
 180
 181                         data [tail] = item;
 182
 183                         if (++tail == data.Length)
 184                                 tail = 0;
 185
 186                         size ++;
 187                         version ++;
 188                 }
 189
 190                 public T [] ToArray ()
 191                 {
 192                         T [] t = new T [size];
 193                         CopyTo (t, 0);
 194                         return t;
 195                 }
 196
 197                 public void TrimExcess ()
 198                 {
 199                         if (data != null && (size < data.Length * 0.9))
 200                                 Array.Resize <T> (ref data, size == 0 ? defaultCapacity : size);
 201                 }
 202
 203                 void SetCapacity (int new_size)
 204                 {
 205                         if (data != null && new_size == data.Length)
 206                                 return;
 207
 208                         if (new_size < size)
 209                                 throw new InvalidOperationException ("shouldnt happen");
 210
 211                         T [] new_data = new T [new_size];
 212                         if (size > 0)
 213                                 CopyTo (new_data, 0);
 214
 215                         data = new_data;
 216                         tail = size;
 217                         head = 0;
 218                         version ++;
 219                 }
 220
 221                 public int Count {
 222                         get { return size; }
 223                 }
 224
 225                 bool ICollection.IsSynchronized {
 226                         get { return false; }
 227                 }
 228
 229                 object ICollection.SyncRoot {
 230                         get { return this; }
 231                 }
 232
 233                 public Enumerator GetEnumerator ()
 234                 {
 235                         return new Enumerator (this);
 236                 }
 237
 238                 IEnumerator <T> IEnumerable<T>.GetEnumerator ()
 239                 {
 240                         return GetEnumerator ();
 241                 }
 242
 243                 IEnumerator IEnumerable.GetEnumerator ()
 244                 {
 245                         return GetEnumerator ();
 246                 }
 247
 248                 [Serializable]
 249                 public struct Enumerator : IEnumerator <T>, IEnumerator, IDisposable {
 250                         const int NOT_STARTED = -2;
 251
 252                         // this MUST be -1, because we depend on it in move next.
 253                         // we just decr the size, so, 0 - 1 == FINISHED
 254                         const int FINISHED = -1;
 255
 256                         Queue <T> q;
 257                         int idx;
 258                         int ver;
 259
 260                         internal Enumerator (Queue <T> q)
 261                         {
 262                                 this.q = q;
 263                                 idx = NOT_STARTED;
 264                                 ver = q.version;
 265                         }
 266
 267                         // for some fucked up reason, MSFT added a useless dispose to this class
 268                         // It means that in foreach, we must still do a try/finally. Broken, very
 269                         // broken.
 270                         public void Dispose ()
 271                         {
 272                                 idx = NOT_STARTED;
 273                         }
 274
 275                         public bool MoveNext ()
 276                         {
 277                                 if (ver != q.version)
 278                                         throw new InvalidOperationException ();
 279
 280                                 if (idx == NOT_STARTED)
 281                                         idx = q.size;
 282
 283                                 return idx != FINISHED && -- idx != FINISHED;
 284                         }
 285
 286                         public T Current {
 287                                 get {
 288                                         if (idx < 0)
 289                                                 throw new InvalidOperationException ();
 290
 291                                         return q.data [(q.size - 1 - idx + q.head) % q.data.Length];
 292                                 }
 293                         }
 294
 295                         void IEnumerator.Reset ()
 296                         {
 297                                 if (ver != q.version)
 298                                         throw new InvalidOperationException ();
 299
 300                                 idx = NOT_STARTED;
 301                         }
 302
 303                         object IEnumerator.Current {
 304                                 get { return Current; }
 305                         }
 306
 307                 }
 308         }
 309 }
 310 #endif