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 using System;
  11 using System.Collections;
  12
  13 namespace System.Collections {
  14
  15         [Serializable]
  16         public class Queue : ICollection, IEnumerable, ICloneable {
  17
  18                 private object[] contents;
  19                 private int head = 0;   // points to the first used slot
  20                 private int count = 0;
  21                 private int capacity = 16;
  22                 private float growFactor = 2.0F;
  23                 private int modCount = 0;
  24
  25                 public Queue () {
  26                         contents = new object[capacity];
  27                 }
  28
  29                 public Queue (ICollection collection) {
  30                         capacity = collection.Count;
  31                         contents = new object[capacity];
  32                         count = capacity;
  33                         collection.CopyTo (contents, 0);
  34                 }
  35
  36                 public Queue (int initialCapacity) {
  37                         capacity = initialCapacity;
  38                         contents = new object[capacity];
  39                 }
  40
  41                 public Queue (int initialCapacity, float growFactor) {
  42                         capacity = initialCapacity;
  43                         contents = new object[capacity];
  44                         // LAMESPEC: The spec says nothing, but I think this
  45                         // should throw an exception if growFactor <= 1.0
  46                         this.growFactor = growFactor;
  47                 }
  48
  49                 // from ICollection
  50
  51                 public virtual int Count {
  52                         get { return count; }
  53                 }
  54
  55                 public virtual bool IsSynchronized {
  56                         get { return false; }
  57                 }
  58
  59                 public virtual object SyncRoot {
  60                         get { return this; }
  61                 }
  62
  63                 public virtual void CopyTo (Array array, int index) {
  64                         if (array == null) {
  65                                 throw new ArgumentNullException ();
  66                         }
  67
  68                         if (index < 0) {
  69                                 throw new ArgumentOutOfRangeException ();
  70                         }
  71
  72                         if (array.Rank > 1
  73                             || index >= array.Length
  74                             || count > array.Length - index) {
  75                                 throw new ArgumentException ();
  76                         }
  77
  78                         int contents_length = contents.Length;
  79                         int length_from_head = contents_length - head;
  80                         // copy the contents of the circular array
  81                         Array.Copy (contents, head, array, index,
  82                                     Math.Min (count, length_from_head));
  83                         if (count >  length_from_head)
  84                                 Array.Copy (contents, 0, array,
  85                                             index + length_from_head,
  86                                             count - length_from_head);
  87                 }
  88
  89                 // from IEnumerable
  90
  91                 public virtual IEnumerator GetEnumerator () {
  92                         return new QueueEnumerator (this);
  93                 }
  94
  95                 // from ICloneable
  96
  97                 public virtual object Clone () {
  98                         Queue newQueue;
  99
 100                         newQueue = new Queue (); // FIXME: improve this...
 101
 102                         newQueue.contents = new object[this.contents.Length];
 103                         Array.Copy (this.contents, 0, newQueue.contents, 0,
 104                                     this.contents.Length);
 105                         newQueue.head = this.head;
 106                         newQueue.count = this.count;
 107                         newQueue.capacity = this.capacity;
 108                         newQueue.growFactor = this.growFactor;
 109
 110                         return newQueue;
 111                 }
 112
 113                 // FIXME: should override Equals?
 114
 115                 // from Queue spec
 116
 117 /*
 118                 public virtual bool IsReadOnly {
 119                         get { return false; }
 120                 }
 121 */
 122
 123                 public virtual void Clear () {
 124                         modCount++;
 125                         head = 0;
 126                         count = 0;
 127                         // FIXME: Should allocate a new contents array?
 128                         //        Should null the current array?
 129                 }
 130
 131                 public virtual bool Contains (object obj) {
 132                         int tail = head + count;
 133                         if (obj == null) {
 134                                 for (int i = head; i < tail; i++) {
 135                                         if (contents[i % capacity] == null)
 136                                                 return true;
 137                                 }
 138                         } else {
 139                                 for (int i = head; i < tail; i++) {
 140                                         if (obj.Equals (contents[i % capacity]))
 141                                                 return true;
 142                                 }
 143                         }
 144                         return false;
 145                 }
 146
 147                 public virtual object Dequeue ()
 148                 {
 149                         modCount++;
 150                         if (count < 1)
 151                                 throw new InvalidOperationException ();
 152                         object result = contents[head];
 153                         head = (head + 1) % capacity;
 154                         count--;
 155                         return result;
 156                 }
 157
 158                 public virtual void Enqueue (object obj) {
 159                         modCount++;
 160                         if (count == capacity)
 161                                 grow ();
 162                         contents[(head + count) % capacity] = obj;
 163                         count++;
 164
 165                 }
 166
 167                 public virtual object Peek () {
 168                         if (count < 1)
 169                                 throw new InvalidOperationException ();
 170                         return contents[head];
 171                 }
 172
 173                 public static Queue Synchronized (Queue queue) {
 174                         if (queue == null) {
 175                                 throw new ArgumentNullException ();
 176                         }
 177                         return new SyncQueue (queue);
 178                 }
 179
 180                 public virtual object[] ToArray () {
 181                         object[] ret = new object[count];
 182                         CopyTo (ret, 0);
 183                         return ret;
 184                 }
 185
 186                 public virtual void TrimToSize() {
 187                         object[] trimmed = new object [count];
 188                         CopyTo (trimmed, 0);
 189                         contents = trimmed;
 190                 }
 191
 192                 // private methods
 193
 194                 private void grow () {
 195                         int newCapacity = (int) Math.Ceiling
 196                                 (contents.Length * growFactor);
 197                         object[] newContents = new object[newCapacity];
 198                         CopyTo (newContents, 0);
 199                         contents = newContents;
 200                         capacity = newCapacity;
 201                         head = 0;
 202                 }
 203
 204                 // private classes
 205
 206                 private class SyncQueue : Queue {
 207                         Queue queue;
 208
 209                         internal SyncQueue (Queue queue) {
 210                                 this.queue = queue;
 211                         }
 212
 213                         public override int Count {
 214                                 get {
 215                                         lock (queue) {
 216                                                 return queue.count;
 217                                         }
 218                                 }
 219                         }
 220
 221                         public override bool IsSynchronized {
 222                                 get {
 223                                         return true;
 224                                 }
 225                         }
 226
 227                         public override object SyncRoot {
 228                                 get {
 229                                         return queue.SyncRoot;
 230                                 }
 231                         }
 232
 233                         public override void CopyTo (Array array, int index) {
 234                                 lock (queue) {
 235                                         queue.CopyTo (array, index);
 236                                 }
 237                         }
 238
 239                         public override IEnumerator GetEnumerator () {
 240                                 lock (queue) {
 241                                         return queue.GetEnumerator ();
 242                                 }
 243                         }
 244
 245                         public override object Clone () {
 246                                 lock (queue) {
 247                                         return queue.Clone ();
 248                                 }
 249                         }
 250
 251 /*
 252                         public override bool IsReadOnly {
 253                                 get {
 254                                         lock (queue) {
 255                                                 return queue.IsReadOnly;
 256                                         }
 257                                 }
 258                         }
 259 */
 260
 261                         public override void Clear () {
 262                                 lock (queue) {
 263                                         queue.Clear ();
 264                                 }
 265                         }
 266
 267                         public override bool Contains (object obj) {
 268                                 lock (queue) {
 269                                         return queue.Contains (obj);
 270                                 }
 271                         }
 272
 273                         public override object Dequeue () {
 274                                 lock (queue) {
 275                                         return queue.Dequeue ();
 276                                 }
 277                         }
 278
 279                         public override void Enqueue (object obj) {
 280                                 lock (queue) {
 281                                         queue.Enqueue (obj);
 282                                 }
 283                         }
 284
 285                         public override object Peek () {
 286                                 lock (queue) {
 287                                         return queue.Peek ();
 288                                 }
 289                         }
 290
 291                         public override object[] ToArray () {
 292                                 lock (queue) {
 293                                         return queue.ToArray ();
 294                                 }
 295                         }
 296                 }
 297
 298                 [Serializable]
 299                 private class QueueEnumerator : IEnumerator, ICloneable {
 300                         Queue queue;
 301                         private int modCount;
 302                         private int current;
 303
 304                         internal QueueEnumerator (Queue q) {
 305                                 queue = q;
 306                                 modCount = q.modCount;
 307                                 current = -1;  // one element before the head
 308                         }
 309
 310                         public object Clone ()
 311                         {
 312                                 QueueEnumerator q = new QueueEnumerator (queue);
 313                                 q.modCount = modCount;
 314                                 q.current = current;
 315                                 return q;
 316                         }
 317
 318                         public virtual object Current {
 319                                 get {
 320                                         if (modCount != queue.modCount
 321                                             || current < 0
 322                                             || current >= queue.count)
 323                                                 throw new InvalidOperationException ();
 324                                         return queue.contents[(queue.head + current) % queue.contents.Length];
 325                                 }
 326                         }
 327
 328                         public virtual bool MoveNext () {
 329                                 if (modCount != queue.modCount) {
 330                                         throw new InvalidOperationException ();
 331                                 }
 332
 333                                 if (current >= queue.count - 1) {
 334                                         return false;
 335                                 } else {
 336                                         current++;
 337                                         return true;
 338                                 }
 339                         }
 340
 341                         public virtual void Reset () {
 342                                 if (modCount != queue.modCount) {
 343                                         throw new InvalidOperationException();
 344                                 }
 345                                 current = -1;
 346                         }
 347                 }
 348         }
 349 }
 350