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