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;
36 namespace System.Collections {
39 public class Queue : ICollection, IEnumerable, ICloneable {
41 private object[] _array;
42 private int _head = 0; // points to the first used slot
43 private int _size = 0;
44 private int _tail = 0;
45 private int _growFactor;
46 private int _version = 0;
48 public Queue () : this (32, 2.0F) {}
49 public Queue (int initialCapacity) : this (initialCapacity, 2.0F) {}
50 public Queue(ICollection col) : this (col == null ? 32 : col.Count)
53 throw new ArgumentNullException ("col");
55 _size = _array.Length;
57 col.CopyTo (_array, 0);
60 public Queue (int initialCapacity, float growFactor) {
61 if (initialCapacity < 0)
62 throw new ArgumentOutOfRangeException("capacity", "Needs a non-negative number");
63 if (!(growFactor >= 1.0F && growFactor <= 10.0F))
64 throw new ArgumentOutOfRangeException("growFactor", "Queue growth factor must be between 1.0 and 10.0, inclusive");
66 _array = new object[initialCapacity];
68 this._growFactor = (int)(growFactor * 100);
73 public virtual int Count {
77 public virtual bool IsSynchronized {
81 public virtual object SyncRoot {
85 public virtual void CopyTo (Array array, int index)
88 throw new ArgumentNullException ("array");
91 throw new ArgumentOutOfRangeException ("index");
94 || (index != 0 && index >= array.Length)
95 || _size > array.Length - index)
96 throw new ArgumentException ();
98 int contents_length = _array.Length;
99 int length_from_head = contents_length - _head;
100 // copy the _array of the circular array
101 Array.Copy (_array, _head, array, index,
102 Math.Min (_size, length_from_head));
103 if (_size > length_from_head)
104 Array.Copy (_array, 0, array,
105 index + length_from_head,
106 _size - length_from_head);
111 public virtual IEnumerator GetEnumerator () {
112 return new QueueEnumerator (this);
117 public virtual object Clone () {
120 newQueue = new Queue (this._array.Length);
121 newQueue._growFactor = _growFactor;
123 Array.Copy (this._array, 0, newQueue._array, 0,
125 newQueue._head = this._head;
126 newQueue._size = this._size;
127 newQueue._tail = this._tail;
132 public virtual void Clear () {
137 for (int length = _array.Length - 1; length >= 0; length--)
138 _array [length] = null;
141 public virtual bool Contains (object obj) {
142 int tail = _head + _size;
144 for (int i = _head; i < tail; i++) {
145 if (_array[i % _array.Length] == null)
149 for (int i = _head; i < tail; i++) {
150 if (obj.Equals (_array[i % _array.Length]))
157 public virtual object Dequeue ()
161 throw new InvalidOperationException ();
162 object result = _array[_head];
163 _array [_head] = null;
164 _head = (_head + 1) % _array.Length;
169 public virtual void Enqueue (object obj) {
171 if (_size == _array.Length)
174 _tail = (_tail+1) % _array.Length;
179 public virtual object Peek () {
181 throw new InvalidOperationException ();
182 return _array[_head];
185 public static Queue Synchronized (Queue queue) {
187 throw new ArgumentNullException ("queue");
189 return new SyncQueue (queue);
192 public virtual object[] ToArray () {
193 object[] ret = new object[_size];
198 public virtual void TrimToSize() {
200 object[] trimmed = new object [_size];
204 _tail = _head + _size;
209 private void grow () {
210 int newCapacity = (_array.Length * _growFactor) / 100;
211 object[] newContents = new object[newCapacity];
212 CopyTo (newContents, 0);
213 _array = newContents;
215 _tail = _head + _size;
220 private class SyncQueue : Queue {
223 internal SyncQueue (Queue queue) {
227 public override int Count {
235 public override bool IsSynchronized {
241 public override object SyncRoot {
243 return queue.SyncRoot;
247 public override void CopyTo (Array array, int index) {
249 queue.CopyTo (array, index);
253 public override IEnumerator GetEnumerator () {
255 return queue.GetEnumerator ();
259 public override object Clone () {
261 return new SyncQueue((Queue) queue.Clone ());
266 public override bool IsReadOnly {
269 return queue.IsReadOnly;
275 public override void Clear () {
281 public override void TrimToSize () {
287 public override bool Contains (object obj) {
289 return queue.Contains (obj);
293 public override object Dequeue () {
295 return queue.Dequeue ();
299 public override void Enqueue (object obj) {
305 public override object Peek () {
307 return queue.Peek ();
311 public override object[] ToArray () {
313 return queue.ToArray ();
319 private class QueueEnumerator : IEnumerator, ICloneable {
321 private int _version;
324 internal QueueEnumerator (Queue q) {
326 _version = q._version;
327 current = -1; // one element before the _head
330 public object Clone ()
332 QueueEnumerator q = new QueueEnumerator (queue);
333 q._version = _version;
338 public virtual object Current {
340 if (_version != queue._version
342 || current >= queue._size)
343 throw new InvalidOperationException ();
344 return queue._array[(queue._head + current) % queue._array.Length];
348 public virtual bool MoveNext () {
349 if (_version != queue._version) {
350 throw new InvalidOperationException ();
353 if (current >= queue._size - 1) {
354 current = Int32.MaxValue; // to late!
362 public virtual void Reset () {
363 if (_version != queue._version) {
364 throw new InvalidOperationException();