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