mcs/class/corlib/System.Collections/Queue.cs

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