2 // System.Collections.Generic.Queue
5 // Martin Baulig (martin@ximian.com)
6 // Ben Maurer (bmaurer@ximian.com)
8 // (C) 2003, 2004 Novell, Inc.
12 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
14 // Permission is hereby granted, free of charge, to any person obtaining
15 // a copy of this software and associated documentation files (the
16 // "Software"), to deal in the Software without restriction, including
17 // without limitation the rights to use, copy, modify, merge, publish,
18 // distribute, sublicense, and/or sell copies of the Software, and to
19 // permit persons to whom the Software is furnished to do so, subject to
20 // the following conditions:
22 // The above copyright notice and this permission notice shall be
23 // included in all copies or substantial portions of the Software.
25 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
26 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
27 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
28 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
29 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
30 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
31 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 using System
.Runtime
.InteropServices
;
38 namespace System
.Collections
.Generic
42 public class Queue
<T
> : IEnumerable
<T
>, ICollection
, IEnumerable
51 private readonly static int INITIAL_SIZE
= 16;
55 defaultCapacity
= INITIAL_SIZE
;
58 public Queue (int count
)
61 throw new ArgumentOutOfRangeException ("count");
63 defaultCapacity
= count
;
67 public Queue (IEnumerable
<T
> collection
)
69 if (collection
== null)
70 throw new ArgumentNullException ("collection");
72 foreach (T t
in collection
)
74 defaultCapacity
= size
;
80 Array
.Clear (data
, 0, data
.Length
);
82 head
= tail
= size
= 0;
85 public bool Contains (T item
)
100 public void CopyTo (T
[] array
, int idx
)
103 throw new ArgumentNullException ();
105 if ((uint) idx
> (uint) array
.Length
)
106 throw new ArgumentOutOfRangeException ();
108 if (array
.Length
- idx
< size
)
109 throw new ArgumentOutOfRangeException ();
114 int contents_length
= data
.Length
;
115 int length_from_head
= contents_length
- head
;
117 Array
.Copy (data
, head
, array
, idx
, Math
.Min (size
, length_from_head
));
118 if (size
> length_from_head
)
119 Array
.Copy (data
, 0, array
,
120 idx
+ length_from_head
,
121 size
- length_from_head
);
125 void ICollection
.CopyTo (Array array
, int idx
)
128 throw new ArgumentNullException ();
130 if ((uint) idx
< (uint) array
.Length
)
131 throw new ArgumentOutOfRangeException ();
133 if (array
.Length
- idx
< size
)
134 throw new ArgumentOutOfRangeException ();
140 int contents_length
= data
.Length
;
141 int length_from_head
= contents_length
- head
;
143 Array
.Copy (data
, head
, array
, idx
, Math
.Min (size
, length_from_head
));
144 if (size
> length_from_head
)
145 Array
.Copy (data
, 0, array
,
146 idx
+ length_from_head
,
147 size
- length_from_head
);
148 } catch (ArrayTypeMismatchException
) {
149 throw new ArgumentException ();
157 // clear stuff out to make the GC happy
158 data
[head
] = default (T
);
160 if (++head
== data
.Length
)
171 throw new InvalidOperationException ();
176 public void Enqueue (T item
)
178 if (data
== null || size
== data
.Length
)
179 SetCapacity (Math
.Max (size
* 2, 4));
183 if (++tail
== data
.Length
)
190 public T
[] ToArray ()
192 T
[] t
= new T
[size
];
197 public void TrimExcess ()
199 if (data
!= null && (size
< data
.Length
* 0.9))
200 Array
.Resize
<T
> (ref data
, size
== 0 ? defaultCapacity
: size
);
203 void SetCapacity (int new_size
)
205 if (data
!= null && new_size
== data
.Length
)
209 throw new InvalidOperationException ("shouldnt happen");
211 T
[] new_data
= new T
[new_size
];
213 CopyTo (new_data
, 0);
225 bool ICollection
.IsSynchronized
{
226 get { return false; }
229 object ICollection
.SyncRoot
{
233 public Enumerator
GetEnumerator ()
235 return new Enumerator (this);
238 IEnumerator
<T
> IEnumerable
<T
>.GetEnumerator ()
240 return GetEnumerator ();
243 IEnumerator IEnumerable
.GetEnumerator ()
245 return GetEnumerator ();
249 public struct Enumerator
: IEnumerator
<T
>, IEnumerator
, IDisposable
{
250 const int NOT_STARTED
= -2;
252 // this MUST be -1, because we depend on it in move next.
253 // we just decr the size, so, 0 - 1 == FINISHED
254 const int FINISHED
= -1;
260 internal Enumerator (Queue
<T
> q
)
267 // for some fucked up reason, MSFT added a useless dispose to this class
268 // It means that in foreach, we must still do a try/finally. Broken, very
270 public void Dispose ()
275 public bool MoveNext ()
277 if (ver
!= q
.version
)
278 throw new InvalidOperationException ();
280 if (idx
== NOT_STARTED
)
283 return idx
!= FINISHED
&& -- idx
!= FINISHED
;
289 throw new InvalidOperationException ();
291 return q
.data
[(q
.size
- 1 - idx
+ q
.head
) % q
.data
.Length
];
295 void IEnumerator
.Reset ()
297 if (ver
!= q
.version
)
298 throw new InvalidOperationException ();
303 object IEnumerator
.Current
{
304 get { return Current; }