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
52 private const int INITIAL_SIZE = 16;
58 public Queue (int count)
61 throw new ArgumentOutOfRangeException ("count");
63 _array = new T [count];
66 public Queue (IEnumerable <T> collection)
68 if (collection == null)
69 throw new ArgumentNullException ("collection");
71 foreach (T t in collection)
78 Array.Clear (_array, 0, _array.Length);
80 _head = _tail = _size = 0;
84 public bool Contains (T item)
99 public void CopyTo (T [] array, int idx)
102 throw new ArgumentNullException ();
104 ((ICollection) this).CopyTo (array, idx);
107 void ICollection.CopyTo (Array array, int idx)
110 throw new ArgumentNullException ();
112 if ((uint) idx > (uint) array.Length)
113 throw new ArgumentOutOfRangeException ();
115 if (array.Length - idx < _size)
116 throw new ArgumentOutOfRangeException ();
122 int contents_length = _array.Length;
123 int length_from_head = contents_length - _head;
125 Array.Copy (_array, _head, array, idx, Math.Min (_size, length_from_head));
126 if (_size > length_from_head)
127 Array.Copy (_array, 0, array,
128 idx + length_from_head,
129 _size - length_from_head);
130 } catch (ArrayTypeMismatchException) {
131 throw new ArgumentException ();
139 // clear stuff out to make the GC happy
140 _array [_head] = default (T);
142 if (++_head == _array.Length)
153 throw new InvalidOperationException ();
155 return _array [_head];
158 public void Enqueue (T item)
160 if (_array == null || _size == _array.Length)
161 SetCapacity (Math.Max (_size * 2, 4));
163 _array [_tail] = item;
165 if (++_tail == _array.Length)
172 public T [] ToArray ()
174 T [] t = new T [_size];
179 public void TrimExcess ()
181 if (_array != null && (_size < _array.Length * 0.9))
185 void SetCapacity (int new_size)
187 if (_array != null && new_size == _array.Length)
190 if (new_size < _size)
191 throw new InvalidOperationException ("shouldnt happen");
193 T [] new_data = new T [new_size];
195 CopyTo (new_data, 0);
204 get { return _size; }
207 bool ICollection.IsSynchronized {
208 get { return false; }
211 object ICollection.SyncRoot {
215 public Enumerator GetEnumerator ()
217 return new Enumerator (this);
220 IEnumerator <T> IEnumerable<T>.GetEnumerator ()
222 return GetEnumerator ();
225 IEnumerator IEnumerable.GetEnumerator ()
227 return GetEnumerator ();
231 public struct Enumerator : IEnumerator <T>, IEnumerator, IDisposable {
232 const int NOT_STARTED = -2;
234 // this MUST be -1, because we depend on it in move next.
235 // we just decr the _size, so, 0 - 1 == FINISHED
236 const int FINISHED = -1;
242 internal Enumerator (Queue <T> q)
249 // for some fucked up reason, MSFT added a useless dispose to this class
250 // It means that in foreach, we must still do a try/finally. Broken, very
252 public void Dispose ()
257 public bool MoveNext ()
259 if (ver != q._version)
260 throw new InvalidOperationException ();
262 if (idx == NOT_STARTED)
265 return idx != FINISHED && -- idx != FINISHED;
271 throw new InvalidOperationException ();
273 return q._array [(q._size - 1 - idx + q._head) % q._array.Length];
277 void IEnumerator.Reset ()
279 if (ver != q._version)
280 throw new InvalidOperationException ();
285 object IEnumerator.Current {
286 get { return Current; }