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