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

   1 //
   2 // System.Collections.Queue
   3 //
   4 // Author:
   5 //    Ricardo Fernández Pascual
   6 //
   7 // (C) 2001 Ricardo Fernández Pascual
   8 //
   9
  10 using System;
  11 using System.Collections;
  12
  13 namespace System.Collections {
  14
  15         [Serializable]
  16         public class Queue : ICollection, IEnumerable, ICloneable {
  17
  18                 private object[] _array;
  19                 private int _head = 0;   // points to the first used slot
  20                 private int _size = 0;
  21                 private int _tail = 0;
  22                 private int _growFactor;
  23                 private int _version = 0;
  24
  25                 public Queue () : this (32, 2.0F) {}
  26                 public Queue (int initialCapacity) : this (initialCapacity, 2.0F) {}
  27                 public Queue(ICollection col) : this (col == null ? 32 : col.Count)
  28                 {
  29                         if (col == null)
  30                                 throw new ArgumentNullException ("col");
  31
  32                         _size = _array.Length;
  33                         _tail = _size;
  34                         col.CopyTo (_array, 0);
  35                 }
  36
  37                 public Queue (int initialCapacity, float growFactor) {
  38                         if (initialCapacity < 0)
  39                                 throw new ArgumentOutOfRangeException("capacity", "Needs a non-negative number");
  40                         if (!(growFactor >= 1.0F && growFactor <= 10.0F))
  41                                 throw new ArgumentOutOfRangeException("growFactor", "Queue growth factor must be between 1.0 and 10.0, inclusive");
  42
  43                         _array = new object[initialCapacity];
  44
  45                         this._growFactor = (int)(growFactor * 100);
  46                 }
  47
  48                 // from ICollection
  49
  50                 public virtual int Count {
  51                         get { return _size; }
  52                 }
  53
  54                 public virtual bool IsSynchronized {
  55                         get { return false; }
  56                 }
  57
  58                 public virtual object SyncRoot {
  59                         get { return this; }
  60                 }
  61
  62                 public virtual void CopyTo (Array array, int index)
  63                 {
  64                         if (array == null)
  65                                 throw new ArgumentNullException ("array");
  66
  67                         if (index < 0)
  68                                 throw new ArgumentOutOfRangeException ("index");
  69
  70                         if (array.Rank > 1
  71                             || (index != 0 && index >= array.Length)
  72                             || _size > array.Length - index)
  73                                 throw new ArgumentException ();
  74
  75                         int contents_length = _array.Length;
  76                         int length_from_head = contents_length - _head;
  77                         // copy the _array of the circular array
  78                         Array.Copy (_array, _head, array, index,
  79                                     Math.Min (_size, length_from_head));
  80                         if (_size >  length_from_head)
  81                                 Array.Copy (_array, 0, array,
  82                                             index + length_from_head,
  83                                             _size - length_from_head);
  84                 }
  85
  86                 // from IEnumerable
  87
  88                 public virtual IEnumerator GetEnumerator () {
  89                         return new QueueEnumerator (this);
  90                 }
  91
  92                 // from ICloneable
  93
  94                 public virtual object Clone () {
  95                         Queue newQueue;
  96
  97                         newQueue = new Queue (this._array.Length);
  98                         newQueue._growFactor = _growFactor;
  99
 100                         Array.Copy (this._array, 0, newQueue._array, 0,
 101                                     this._array.Length);
 102                         newQueue._head = this._head;
 103                         newQueue._size = this._size;
 104                         newQueue._tail = this._tail;
 105
 106                         return newQueue;
 107                 }
 108
 109                 public virtual void Clear () {
 110                         _version++;
 111                         _head = 0;
 112                         _size = 0;
 113                         _tail = 0;
 114                         for (int length = _array.Length - 1; length >= 0; length--)
 115                                 _array [length] = null;
 116                 }
 117
 118                 public virtual bool Contains (object obj) {
 119                         int tail = _head + _size;
 120                         if (obj == null) {
 121                                 for (int i = _head; i < tail; i++) {
 122                                         if (_array[i % _array.Length] == null)
 123                                                 return true;
 124                                 }
 125                         } else {
 126                                 for (int i = _head; i < tail; i++) {
 127                                         if (obj.Equals (_array[i % _array.Length]))
 128                                                 return true;
 129                                 }
 130                         }
 131                         return false;
 132                 }
 133
 134                 public virtual object Dequeue ()
 135                 {
 136                         _version++;
 137                         if (_size < 1)
 138                                 throw new InvalidOperationException ();
 139                         object result = _array[_head];
 140                         _array [_head] = null;
 141                         _head = (_head + 1) % _array.Length;
 142                         _size--;
 143                         return result;
 144                 }
 145
 146                 public virtual void Enqueue (object obj) {
 147                         _version++;
 148                         if (_size == _array.Length)
 149                                 grow ();
 150                         _array[_tail] = obj;
 151                         _tail = (_tail+1) % _array.Length;
 152                         _size++;
 153
 154                 }
 155
 156                 public virtual object Peek () {
 157                         if (_size < 1)
 158                                 throw new InvalidOperationException ();
 159                         return _array[_head];
 160                 }
 161
 162                 public static Queue Synchronized (Queue queue) {
 163                         if (queue == null) {
 164                                 throw new ArgumentNullException ("queue");
 165                         }
 166                         return new SyncQueue (queue);
 167                 }
 168
 169                 public virtual object[] ToArray () {
 170                         object[] ret = new object[_size];
 171                         CopyTo (ret, 0);
 172                         return ret;
 173                 }
 174
 175                 public virtual void TrimToSize() {
 176                         _version++;
 177                         object[] trimmed = new object [_size];
 178                         CopyTo (trimmed, 0);
 179                         _array = trimmed;
 180                         _head = 0;
 181                         _tail = _head + _size;
 182                 }
 183
 184                 // private methods
 185
 186                 private void grow () {
 187                         int newCapacity = (_array.Length * _growFactor) / 100;
 188                         object[] newContents = new object[newCapacity];
 189                         CopyTo (newContents, 0);
 190                         _array = newContents;
 191                         _head = 0;
 192                         _tail = _head + _size;
 193                 }
 194
 195                 // private classes
 196
 197                 private class SyncQueue : Queue {
 198                         Queue queue;
 199
 200                         internal SyncQueue (Queue queue) {
 201                                 this.queue = queue;
 202                         }
 203
 204                         public override int Count {
 205                                 get {
 206                                         lock (queue) {
 207                                                 return queue._size;
 208                                         }
 209                                 }
 210                         }
 211
 212                         public override bool IsSynchronized {
 213                                 get {
 214                                         return true;
 215                                 }
 216                         }
 217
 218                         public override object SyncRoot {
 219                                 get {
 220                                         return queue.SyncRoot;
 221                                 }
 222                         }
 223
 224                         public override void CopyTo (Array array, int index) {
 225                                 lock (queue) {
 226                                         queue.CopyTo (array, index);
 227                                 }
 228                         }
 229
 230                         public override IEnumerator GetEnumerator () {
 231                                 lock (queue) {
 232                                         return queue.GetEnumerator ();
 233                                 }
 234                         }
 235
 236                         public override object Clone () {
 237                                 lock (queue) {
 238                                         return new SyncQueue((Queue) queue.Clone ());
 239                                 }
 240                         }
 241
 242 /*
 243                         public override bool IsReadOnly {
 244                                 get {
 245                                         lock (queue) {
 246                                                 return queue.IsReadOnly;
 247                                         }
 248                                 }
 249                         }
 250 */
 251
 252                         public override void Clear () {
 253                                 lock (queue) {
 254                                         queue.Clear ();
 255                                 }
 256                         }
 257
 258                         public override void TrimToSize () {
 259                                 lock (queue) {
 260                                         queue.TrimToSize ();
 261                                 }
 262                         }
 263
 264                         public override bool Contains (object obj) {
 265                                 lock (queue) {
 266                                         return queue.Contains (obj);
 267                                 }
 268                         }
 269
 270                         public override object Dequeue () {
 271                                 lock (queue) {
 272                                         return queue.Dequeue ();
 273                                 }
 274                         }
 275
 276                         public override void Enqueue (object obj) {
 277                                 lock (queue) {
 278                                         queue.Enqueue (obj);
 279                                 }
 280                         }
 281
 282                         public override object Peek () {
 283                                 lock (queue) {
 284                                         return queue.Peek ();
 285                                 }
 286                         }
 287
 288                         public override object[] ToArray () {
 289                                 lock (queue) {
 290                                         return queue.ToArray ();
 291                                 }
 292                         }
 293                 }
 294
 295                 [Serializable]
 296                 private class QueueEnumerator : IEnumerator, ICloneable {
 297                         Queue queue;
 298                         private int _version;
 299                         private int current;
 300
 301                         internal QueueEnumerator (Queue q) {
 302                                 queue = q;
 303                                 _version = q._version;
 304                                 current = -1;  // one element before the _head
 305                         }
 306
 307                         public object Clone ()
 308                         {
 309                                 QueueEnumerator q = new QueueEnumerator (queue);
 310                                 q._version = _version;
 311                                 q.current = current;
 312                                 return q;
 313                         }
 314
 315                         public virtual object Current {
 316                                 get {
 317                                         if (_version != queue._version
 318                                             || current < 0
 319                                             || current >= queue._size)
 320                                                 throw new InvalidOperationException ();
 321                                         return queue._array[(queue._head + current) % queue._array.Length];
 322                                 }
 323                         }
 324
 325                         public virtual bool MoveNext () {
 326                                 if (_version != queue._version) {
 327                                         throw new InvalidOperationException ();
 328                                 }
 329
 330                                 if (current >= queue._size - 1) {
 331                                         return false;
 332                                 } else {
 333                                         current++;
 334                                         return true;
 335                                 }
 336                         }
 337
 338                         public virtual void Reset () {
 339                                 if (_version != queue._version) {
 340                                         throw new InvalidOperationException();
 341                                 }
 342                                 current = -1;
 343                         }
 344                 }
 345         }
 346 }
 347