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                         if (newCapacity < _array.Length + 1)
 212                                 newCapacity = _array.Length + 1;
 213                         object[] newContents = new object[newCapacity];
 214                         CopyTo (newContents, 0);
 215                         _array = newContents;
 216                         _head = 0;
 217                         _tail = _head + _size;
 218                 }
 219
 220                 // private classes
 221
 222                 private class SyncQueue : Queue {
 223                         Queue queue;
 224
 225                         internal SyncQueue (Queue queue) {
 226                                 this.queue = queue;
 227                         }
 228
 229                         public override int Count {
 230                                 get {
 231                                         lock (queue) {
 232                                                 return queue.Count;
 233                                         }
 234                                 }
 235                         }
 236
 237                         public override bool IsSynchronized {
 238                                 get {
 239                                         return true;
 240                                 }
 241                         }
 242
 243                         public override object SyncRoot {
 244                                 get {
 245                                         return queue.SyncRoot;
 246                                 }
 247                         }
 248
 249                         public override void CopyTo (Array array, int index) {
 250                                 lock (queue) {
 251                                         queue.CopyTo (array, index);
 252                                 }
 253                         }
 254
 255                         public override IEnumerator GetEnumerator () {
 256                                 lock (queue) {
 257                                         return queue.GetEnumerator ();
 258                                 }
 259                         }
 260
 261                         public override object Clone () {
 262                                 lock (queue) {
 263                                         return new SyncQueue((Queue) queue.Clone ());
 264                                 }
 265                         }
 266
 267 /*
 268                         public override bool IsReadOnly {
 269                                 get {
 270                                         lock (queue) {
 271                                                 return queue.IsReadOnly;
 272                                         }
 273                                 }
 274                         }
 275 */
 276
 277                         public override void Clear () {
 278                                 lock (queue) {
 279                                         queue.Clear ();
 280                                 }
 281                         }
 282
 283                         public override void TrimToSize () {
 284                                 lock (queue) {
 285                                         queue.TrimToSize ();
 286                                 }
 287                         }
 288
 289                         public override bool Contains (object obj) {
 290                                 lock (queue) {
 291                                         return queue.Contains (obj);
 292                                 }
 293                         }
 294
 295                         public override object Dequeue () {
 296                                 lock (queue) {
 297                                         return queue.Dequeue ();
 298                                 }
 299                         }
 300
 301                         public override void Enqueue (object obj) {
 302                                 lock (queue) {
 303                                         queue.Enqueue (obj);
 304                                 }
 305                         }
 306
 307                         public override object Peek () {
 308                                 lock (queue) {
 309                                         return queue.Peek ();
 310                                 }
 311                         }
 312
 313                         public override object[] ToArray () {
 314                                 lock (queue) {
 315                                         return queue.ToArray ();
 316                                 }
 317                         }
 318                 }
 319
 320                 [Serializable]
 321                 private class QueueEnumerator : IEnumerator, ICloneable {
 322                         Queue queue;
 323                         private int _version;
 324                         private int current;
 325
 326                         internal QueueEnumerator (Queue q) {
 327                                 queue = q;
 328                                 _version = q._version;
 329                                 current = -1;  // one element before the _head
 330                         }
 331
 332                         public object Clone ()
 333                         {
 334                                 QueueEnumerator q = new QueueEnumerator (queue);
 335                                 q._version = _version;
 336                                 q.current = current;
 337                                 return q;
 338                         }
 339
 340                         public virtual object Current {
 341                                 get {
 342                                         if (_version != queue._version
 343                                             || current < 0
 344                                             || current >= queue._size)
 345                                                 throw new InvalidOperationException ();
 346                                         return queue._array[(queue._head + current) % queue._array.Length];
 347                                 }
 348                         }
 349
 350                         public virtual bool MoveNext () {
 351                                 if (_version != queue._version) {
 352                                         throw new InvalidOperationException ();
 353                                 }
 354
 355                                 if (current >= queue._size - 1) {
 356                                         current = Int32.MaxValue; // to late!
 357                                         return false;
 358                                 } else {
 359                                         current++;
 360                                         return true;
 361                                 }
 362                         }
 363
 364                         public virtual void Reset () {
 365                                 if (_version != queue._version) {
 366                                         throw new InvalidOperationException();
 367                                 }
 368                                 current = -1;
 369                         }
 370                 }
 371         }
 372 }
 373