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();