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 //
  11 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  12 //
  13 // Permission is hereby granted, free of charge, to any person obtaining
  14 // a copy of this software and associated documentation files (the
  15 // "Software"), to deal in the Software without restriction, including
  16 // without limitation the rights to use, copy, modify, merge, publish,
  17 // distribute, sublicense, and/or sell copies of the Software, and to
  18 // permit persons to whom the Software is furnished to do so, subject to
  19 // the following conditions:
  20 //
  21 // The above copyright notice and this permission notice shall be
  22 // included in all copies or substantial portions of the Software.
  23 //
  24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  31 //
  32
  33 using System;
  34 using System.Collections;
  35
  36 namespace System.Collections {
  37
  38         [Serializable]
  39         public class Queue : ICollection, IEnumerable, ICloneable {
  40
  41                 private object[] _array;
  42                 private int _head = 0;   // points to the first used slot
  43                 private int _size = 0;
  44                 private int _tail = 0;
  45                 private int _growFactor;
  46                 private int _version = 0;
  47
  48                 public Queue () : this (32, 2.0F) {}
  49                 public Queue (int initialCapacity) : this (initialCapacity, 2.0F) {}
  50                 public Queue(ICollection col) : this (col == null ? 32 : col.Count)
  51                 {
  52                         if (col == null)
  53                                 throw new ArgumentNullException ("col");
  54
  55                         // We have to do this because msft seems to call the
  56                         // enumerator rather than CopyTo. This affects classes
  57                         // like bitarray.
  58                         foreach (object o in col)
  59                                 Enqueue (o);
  60                 }
  61
  62                 public Queue (int initialCapacity, float growFactor) {
  63                         if (initialCapacity < 0)
  64                                 throw new ArgumentOutOfRangeException("capacity", "Needs a non-negative number");
  65                         if (!(growFactor >= 1.0F && growFactor <= 10.0F))
  66                                 throw new ArgumentOutOfRangeException("growFactor", "Queue growth factor must be between 1.0 and 10.0, inclusive");
  67
  68                         _array = new object[initialCapacity];
  69
  70                         this._growFactor = (int)(growFactor * 100);
  71                 }
  72
  73                 // from ICollection
  74
  75                 public virtual int Count {
  76                         get { return _size; }
  77                 }
  78
  79                 public virtual bool IsSynchronized {
  80                         get { return false; }
  81                 }
  82
  83                 public virtual object SyncRoot {
  84                         get { return this; }
  85                 }
  86
  87                 public virtual void CopyTo (Array array, int index)
  88                 {
  89                         if (array == null)
  90                                 throw new ArgumentNullException ("array");
  91
  92                         if (index < 0)
  93                                 throw new ArgumentOutOfRangeException ("index");
  94
  95                         if (array.Rank > 1
  96                             || (index != 0 && index >= array.Length)
  97                             || _size > array.Length - index)
  98                                 throw new ArgumentException ();
  99
 100                         int contents_length = _array.Length;
 101                         int length_from_head = contents_length - _head;
 102                         // copy the _array of the circular array
 103                         Array.Copy (_array, _head, array, index,
 104                                     Math.Min (_size, length_from_head));
 105                         if (_size >  length_from_head)
 106                                 Array.Copy (_array, 0, array,
 107                                             index + length_from_head,
 108                                             _size - length_from_head);
 109                 }
 110
 111                 // from IEnumerable
 112
 113                 public virtual IEnumerator GetEnumerator () {
 114                         return new QueueEnumerator (this);
 115                 }
 116
 117                 // from ICloneable
 118
 119                 public virtual object Clone () {
 120                         Queue newQueue;
 121
 122                         newQueue = new Queue (this._array.Length);
 123                         newQueue._growFactor = _growFactor;
 124
 125                         Array.Copy (this._array, 0, newQueue._array, 0,
 126                                     this._array.Length);
 127                         newQueue._head = this._head;
 128                         newQueue._size = this._size;
 129                         newQueue._tail = this._tail;
 130
 131                         return newQueue;
 132                 }
 133
 134                 public virtual void Clear () {
 135                         _version++;
 136                         _head = 0;
 137                         _size = 0;
 138                         _tail = 0;
 139                         for (int length = _array.Length - 1; length >= 0; length--)
 140                                 _array [length] = null;
 141                 }
 142
 143                 public virtual bool Contains (object obj) {
 144                         int tail = _head + _size;
 145                         if (obj == null) {
 146                                 for (int i = _head; i < tail; i++) {
 147                                         if (_array[i % _array.Length] == null)
 148                                                 return true;
 149                                 }
 150                         } else {
 151                                 for (int i = _head; i < tail; i++) {
 152                                         if (obj.Equals (_array[i % _array.Length]))
 153                                                 return true;
 154                                 }
 155                         }
 156                         return false;
 157                 }
 158
 159                 public virtual object Dequeue ()
 160                 {
 161                         _version++;
 162                         if (_size < 1)
 163                                 throw new InvalidOperationException ();
 164                         object result = _array[_head];
 165                         _array [_head] = null;
 166                         _head = (_head + 1) % _array.Length;
 167                         _size--;
 168                         return result;
 169                 }
 170
 171                 public virtual void Enqueue (object obj) {
 172                         _version++;
 173                         if (_size == _array.Length)
 174                                 grow ();
 175                         _array[_tail] = obj;
 176                         _tail = (_tail+1) % _array.Length;
 177                         _size++;
 178
 179                 }
 180
 181                 public virtual object Peek () {
 182                         if (_size < 1)
 183                                 throw new InvalidOperationException ();
 184                         return _array[_head];
 185                 }
 186
 187                 public static Queue Synchronized (Queue queue) {
 188                         if (queue == null) {
 189                                 throw new ArgumentNullException ("queue");
 190                         }
 191                         return new SyncQueue (queue);
 192                 }
 193
 194                 public virtual object[] ToArray () {
 195                         object[] ret = new object[_size];
 196                         CopyTo (ret, 0);
 197                         return ret;
 198                 }
 199
 200                 public virtual void TrimToSize() {
 201                         _version++;
 202                         object[] trimmed = new object [_size];
 203                         CopyTo (trimmed, 0);
 204                         _array = trimmed;
 205                         _head = 0;
 206                         _tail = _head + _size;
 207                 }
 208
 209                 // private methods
 210
 211                 private void grow () {
 212                         int newCapacity = (_array.Length * _growFactor) / 100;
 213                         if (newCapacity < _array.Length + 1)
 214                                 newCapacity = _array.Length + 1;
 215                         object[] newContents = new object[newCapacity];
 216                         CopyTo (newContents, 0);
 217                         _array = newContents;
 218                         _head = 0;
 219                         _tail = _head + _size;
 220                 }
 221
 222                 // private classes
 223
 224                 private class SyncQueue : Queue {
 225                         Queue queue;
 226
 227                         internal SyncQueue (Queue queue) {
 228                                 this.queue = queue;
 229                         }
 230
 231                         public override int Count {
 232                                 get {
 233                                         lock (queue) {
 234                                                 return queue.Count;
 235                                         }
 236                                 }
 237                         }
 238
 239                         public override bool IsSynchronized {
 240                                 get {
 241                                         return true;
 242                                 }
 243                         }
 244
 245                         public override object SyncRoot {
 246                                 get {
 247                                         return queue.SyncRoot;
 248                                 }
 249                         }
 250
 251                         public override void CopyTo (Array array, int index) {
 252                                 lock (queue) {
 253                                         queue.CopyTo (array, index);
 254                                 }
 255                         }
 256
 257                         public override IEnumerator GetEnumerator () {
 258                                 lock (queue) {
 259                                         return queue.GetEnumerator ();
 260                                 }
 261                         }
 262
 263                         public override object Clone () {
 264                                 lock (queue) {
 265                                         return new SyncQueue((Queue) queue.Clone ());
 266                                 }
 267                         }
 268
 269 /*
 270                         public override bool IsReadOnly {
 271                                 get {
 272                                         lock (queue) {
 273                                                 return queue.IsReadOnly;
 274                                         }
 275                                 }
 276                         }
 277 */
 278
 279                         public override void Clear () {
 280                                 lock (queue) {
 281                                         queue.Clear ();
 282                                 }
 283                         }
 284
 285                         public override void TrimToSize () {
 286                                 lock (queue) {
 287                                         queue.TrimToSize ();
 288                                 }
 289                         }
 290
 291                         public override bool Contains (object obj) {
 292                                 lock (queue) {
 293                                         return queue.Contains (obj);
 294                                 }
 295                         }
 296
 297                         public override object Dequeue () {
 298                                 lock (queue) {
 299                                         return queue.Dequeue ();
 300                                 }
 301                         }
 302
 303                         public override void Enqueue (object obj) {
 304                                 lock (queue) {
 305                                         queue.Enqueue (obj);
 306                                 }
 307                         }
 308
 309                         public override object Peek () {
 310                                 lock (queue) {
 311                                         return queue.Peek ();
 312                                 }
 313                         }
 314
 315                         public override object[] ToArray () {
 316                                 lock (queue) {
 317                                         return queue.ToArray ();
 318                                 }
 319                         }
 320                 }
 321
 322                 [Serializable]
 323                 private class QueueEnumerator : IEnumerator, ICloneable {
 324                         Queue queue;
 325                         private int _version;
 326                         private int current;
 327
 328                         internal QueueEnumerator (Queue q) {
 329                                 queue = q;
 330                                 _version = q._version;
 331                                 current = -1;  // one element before the _head
 332                         }
 333
 334                         public object Clone ()
 335                         {
 336                                 QueueEnumerator q = new QueueEnumerator (queue);
 337                                 q._version = _version;
 338                                 q.current = current;
 339                                 return q;
 340                         }
 341
 342                         public virtual object Current {
 343                                 get {
 344                                         if (_version != queue._version
 345                                             || current < 0
 346                                             || current >= queue._size)
 347                                                 throw new InvalidOperationException ();
 348                                         return queue._array[(queue._head + current) % queue._array.Length];
 349                                 }
 350                         }
 351
 352                         public virtual bool MoveNext () {
 353                                 if (_version != queue._version) {
 354                                         throw new InvalidOperationException ();
 355                                 }
 356
 357                                 if (current >= queue._size - 1) {
 358                                         current = Int32.MaxValue; // to late!
 359                                         return false;
 360                                 } else {
 361                                         current++;
 362                                         return true;
 363                                 }
 364                         }
 365
 366                         public virtual void Reset () {
 367                                 if (_version != queue._version) {
 368                                         throw new InvalidOperationException();
 369                                 }
 370                                 current = -1;
 371                         }
 372                 }
 373         }
 374 }
 375