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