2 // System.Collections.Queue
5 // Ricardo Fernández Pascual
7 // (C) 2001 Ricardo Fernández Pascual
11 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
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:
21 // The above copyright notice and this permission notice shall be
22 // included in all copies or substantial portions of the Software.
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.
34 using System.Collections;
35 using System.Runtime.InteropServices;
37 namespace System.Collections {
43 public class Queue : ICollection, IEnumerable, ICloneable {
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;
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)
57 throw new ArgumentNullException ("col");
59 // We have to do this because msft seems to call the
60 // enumerator rather than CopyTo. This affects classes
62 foreach (object o in col)
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");
72 _array = new object[initialCapacity];
74 this._growFactor = (int)(growFactor * 100);
79 public virtual int Count {
83 public virtual bool IsSynchronized {
87 public virtual object SyncRoot {
91 public virtual void CopyTo (Array array, int index)
94 throw new ArgumentNullException ("array");
97 throw new ArgumentOutOfRangeException ("index");
100 || (index != 0 && index >= array.Length)
101 || _size > array.Length - index)
102 throw new ArgumentException ();
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);
117 public virtual IEnumerator GetEnumerator () {
118 return new QueueEnumerator (this);
123 public virtual object Clone () {
126 newQueue = new Queue (this._array.Length);
127 newQueue._growFactor = _growFactor;
129 Array.Copy (this._array, 0, newQueue._array, 0,
131 newQueue._head = this._head;
132 newQueue._size = this._size;
133 newQueue._tail = this._tail;
138 public virtual void Clear () {
143 for (int length = _array.Length - 1; length >= 0; length--)
144 _array [length] = null;
147 public virtual bool Contains (object obj) {
148 int tail = _head + _size;
150 for (int i = _head; i < tail; i++) {
151 if (_array[i % _array.Length] == null)
155 for (int i = _head; i < tail; i++) {
156 if (obj.Equals (_array[i % _array.Length]))
163 public virtual object Dequeue ()
167 throw new InvalidOperationException ();
168 object result = _array[_head];
169 _array [_head] = null;
170 _head = (_head + 1) % _array.Length;
175 public virtual void Enqueue (object obj) {
177 if (_size == _array.Length)
180 _tail = (_tail+1) % _array.Length;
185 public virtual object Peek () {
187 throw new InvalidOperationException ();
188 return _array[_head];
191 public static Queue Synchronized (Queue queue) {
193 throw new ArgumentNullException ("queue");
195 return new SyncQueue (queue);
198 public virtual object[] ToArray () {
199 object[] ret = new object[_size];
204 public virtual void TrimToSize() {
206 object[] trimmed = new object [_size];
210 _tail = _head + _size;
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;
223 _tail = _head + _size;
228 private class SyncQueue : Queue {
231 internal SyncQueue (Queue queue) {
235 public override int Count {
243 public override bool IsSynchronized {
249 public override object SyncRoot {
251 return queue.SyncRoot;
255 public override void CopyTo (Array array, int index) {
257 queue.CopyTo (array, index);
261 public override IEnumerator GetEnumerator () {
263 return queue.GetEnumerator ();
267 public override object Clone () {
269 return new SyncQueue((Queue) queue.Clone ());
274 public override bool IsReadOnly {
277 return queue.IsReadOnly;
283 public override void Clear () {
289 public override void TrimToSize () {
295 public override bool Contains (object obj) {
297 return queue.Contains (obj);
301 public override object Dequeue () {
303 return queue.Dequeue ();
307 public override void Enqueue (object obj) {
313 public override object Peek () {
315 return queue.Peek ();
319 public override object[] ToArray () {
321 return queue.ToArray ();
327 private class QueueEnumerator : IEnumerator, ICloneable {
329 private int _version;
332 internal QueueEnumerator (Queue q) {
334 _version = q._version;
335 current = -1; // one element before the _head
338 public object Clone ()
340 QueueEnumerator q = new QueueEnumerator (queue);
341 q._version = _version;
346 public virtual object Current {
348 if (_version != queue._version
350 || current >= queue._size)
351 throw new InvalidOperationException ();
352 return queue._array[(queue._head + current) % queue._array.Length];
356 public virtual bool MoveNext () {
357 if (_version != queue._version) {
358 throw new InvalidOperationException ();
361 if (current >= queue._size - 1) {
362 current = Int32.MaxValue; // to late!
370 public virtual void Reset () {
371 if (_version != queue._version) {
372 throw new InvalidOperationException();