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