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.
35 using System
.Runtime
.InteropServices
;
36 using System
.Diagnostics
;
38 namespace System
.Collections
.Generic
42 [DebuggerDisplay ("Count={Count}")]
43 [DebuggerTypeProxy (typeof (CollectionDebuggerView
))]
44 public class Queue
<T
> : IEnumerable
<T
>, ICollection
, IEnumerable
57 public Queue (int count
)
60 throw new ArgumentOutOfRangeException ("count");
62 _array
= new T
[count
];
65 public Queue (IEnumerable
<T
> collection
)
67 if (collection
== null)
68 throw new ArgumentNullException ("collection");
70 var icoll
= collection
as ICollection
<T
>;
71 var size
= icoll
!= null ? icoll
.Count
: 0;
73 _array
= new T
[size
];
75 foreach (T t
in collection
)
81 Array
.Clear (_array
, 0, _array
.Length
);
83 _head
= _tail
= _size
= 0;
87 public bool Contains (T item
)
102 public void CopyTo (T
[] array
, int idx
)
105 throw new ArgumentNullException ();
107 ((ICollection
) this).CopyTo (array
, idx
);
110 void ICollection
.CopyTo (Array array
, int idx
)
113 throw new ArgumentNullException ();
115 if ((uint) idx
> (uint) array
.Length
)
116 throw new ArgumentOutOfRangeException ();
118 if (array
.Length
- idx
< _size
)
119 throw new ArgumentOutOfRangeException ();
125 int contents_length
= _array
.Length
;
126 int length_from_head
= contents_length
- _head
;
128 Array
.Copy (_array
, _head
, array
, idx
, Math
.Min (_size
, length_from_head
));
129 if (_size
> length_from_head
)
130 Array
.Copy (_array
, 0, array
,
131 idx
+ length_from_head
,
132 _size
- length_from_head
);
133 } catch (ArrayTypeMismatchException
) {
134 throw new ArgumentException ();
142 // clear stuff out to make the GC happy
143 _array
[_head
] = default (T
);
145 if (++_head
== _array
.Length
)
156 throw new InvalidOperationException ();
158 return _array
[_head
];
161 public void Enqueue (T item
)
163 if (_size
== _array
.Length
|| _tail
== _array
.Length
)
164 SetCapacity (Math
.Max (Math
.Max (_size
, _tail
) * 2, 4));
166 _array
[_tail
] = item
;
168 if (++_tail
== _array
.Length
)
175 public T
[] ToArray ()
177 T
[] t
= new T
[_size
];
182 public void TrimExcess ()
184 if (_size
< _array
.Length
* 0.9)
188 void SetCapacity (int new_size
)
190 if (new_size
== _array
.Length
)
193 if (new_size
< _size
)
194 throw new InvalidOperationException ("shouldnt happen");
196 T
[] new_data
= new T
[new_size
];
198 CopyTo (new_data
, 0);
207 get { return _size; }
210 bool ICollection
.IsSynchronized
{
211 get { return false; }
214 object ICollection
.SyncRoot
{
218 public Enumerator
GetEnumerator ()
220 return new Enumerator (this);
223 IEnumerator
<T
> IEnumerable
<T
>.GetEnumerator ()
225 return GetEnumerator ();
228 IEnumerator IEnumerable
.GetEnumerator ()
230 return GetEnumerator ();
234 public struct Enumerator
: IEnumerator
<T
>, IEnumerator
, IDisposable
{
235 const int NOT_STARTED
= -2;
237 // this MUST be -1, because we depend on it in move next.
238 // we just decr the _size, so, 0 - 1 == FINISHED
239 const int FINISHED
= -1;
245 internal Enumerator (Queue
<T
> q
)
252 // for some fucked up reason, MSFT added a useless dispose to this class
253 // It means that in foreach, we must still do a try/finally. Broken, very
255 public void Dispose ()
260 public bool MoveNext ()
262 if (ver
!= q
._version
)
263 throw new InvalidOperationException ();
265 if (idx
== NOT_STARTED
)
268 return idx
!= FINISHED
&& -- idx
!= FINISHED
;
274 throw new InvalidOperationException ();
276 return q
._array
[(q
._size
- 1 - idx
+ q
._head
) % q
._array
.Length
];
280 void IEnumerator
.Reset ()
282 if (ver
!= q
._version
)
283 throw new InvalidOperationException ();
288 object IEnumerator
.Current
{
289 get { return Current; }