-//\r
-// System.Collections.Queue\r
-//\r
-// Author:\r
-// Ricardo Fernández Pascual\r
-//\r
-// (C) 2001 Ricardo Fernández Pascual\r
-//\r
-\r
-using System;\r
-using System.Collections;\r
-\r
-namespace System.Collections {\r
-\r
- [Serializable]\r
- public class Queue : ICollection, IEnumerable, ICloneable {\r
-\r
- private object[] contents;\r
- private int head = 0; // points to the first used slot\r
- private int count = 0;\r
- private int capacity = 16;\r
- private float growFactor = 2.0F;\r
- private int modCount = 0;\r
-\r
- public Queue () {\r
- contents = new object[capacity];\r
- }\r
-\r
- public Queue (ICollection collection) {\r
- capacity = collection.Count;\r
- contents = new object[capacity];\r
- count = capacity;\r
- collection.CopyTo (contents, 0);\r
- }\r
-\r
- public Queue (int initialCapacity) {\r
- capacity = initialCapacity;\r
- contents = new object[capacity];\r
- }\r
-\r
- public Queue (int initialCapacity, float growFactor) {\r
- capacity = initialCapacity;\r
- contents = new object[capacity];\r
- // LAMESPEC: The spec says nothing, but I think this \r
- // should throw an exception if growFactor <= 1.0\r
- this.growFactor = growFactor;\r
- }\r
- \r
- // from ICollection\r
-\r
- public virtual int Count {\r
- get { return count; }\r
- }\r
-\r
- public virtual bool IsSynchronized {\r
- get { return false; }\r
- }\r
-\r
- public virtual object SyncRoot {\r
- get { return this; }\r
- }\r
-\r
- public virtual void CopyTo (Array array, int index) {\r
- if (array == null) {\r
- throw new ArgumentNullException ();\r
- }\r
-\r
- if (index < 0) {\r
- throw new ArgumentOutOfRangeException ();\r
- }\r
-\r
- if (array.Rank > 1 \r
- || index >= array.Length \r
- || count > array.Length - index) {\r
- throw new ArgumentException ();\r
- }\r
- \r
- int contents_length = contents.Length;\r
- int length_from_head = contents_length - head;\r
- // copy the contents of the circular array\r
- Array.Copy (contents, head, array, index,\r
- Math.Min (count, length_from_head));\r
- if (count > length_from_head)\r
- Array.Copy (contents, 0, array, \r
- index + length_from_head,\r
- count - length_from_head);\r
- }\r
-\r
- // from IEnumerable\r
- \r
- public virtual IEnumerator GetEnumerator () {\r
- return new QueueEnumerator (this);\r
- }\r
-\r
- // from ICloneable\r
- \r
- public virtual object Clone () {\r
- Queue newQueue;\r
- \r
- newQueue = new Queue (); // FIXME: improve this...\r
- \r
- newQueue.contents = new object[this.contents.Length];\r
- Array.Copy (this.contents, 0, newQueue.contents, 0,\r
- this.contents.Length);\r
- newQueue.head = this.head;\r
- newQueue.count = this.count;\r
- newQueue.capacity = this.capacity;\r
- newQueue.growFactor = this.growFactor;\r
-\r
- return newQueue;\r
- }\r
-\r
- // FIXME: should override Equals?\r
-\r
- // from Queue spec\r
-\r
-/*\r
- public virtual bool IsReadOnly {\r
- get { return false; }\r
- }\r
-*/\r
-\r
- public virtual void Clear () {\r
- modCount++;\r
- head = 0;\r
- count = 0;\r
- // FIXME: Should allocate a new contents array? \r
- // Should null the current array?\r
- }\r
-\r
- public virtual bool Contains (object obj) {\r
- int tail = head + count;\r
- if (obj == null) {\r
- for (int i = head; i < tail; i++) {\r
- if (contents[i % capacity] == null) \r
- return true;\r
- }\r
- } else {\r
- for (int i = head; i < tail; i++) {\r
- if (obj.Equals (contents[i % capacity]))\r
- return true;\r
- }\r
- }\r
- return false;\r
- }\r
- \r
- public virtual object Dequeue ()\r
- {\r
- modCount++;\r
- if (count < 1)\r
- throw new InvalidOperationException ();\r
- object result = contents[head];\r
- head = (head + 1) % capacity;\r
- count--;\r
- return result;\r
- }\r
-\r
- public virtual void Enqueue (object obj) {\r
- modCount++;\r
- if (count == contents.Length) \r
- grow ();\r
- contents[(head + count) % contents.Length] = obj;\r
- count++;\r
- }\r
-\r
- public virtual object Peek () {\r
- if (count < 1)\r
- throw new InvalidOperationException ();\r
- return contents[head];\r
- }\r
-\r
- public static Queue Synchronized (Queue queue) {\r
- if (queue == null) {\r
- throw new ArgumentNullException ();\r
- }\r
- return new SyncQueue (queue);\r
- }\r
-\r
- public virtual object[] ToArray () {\r
- object[] ret = new object[count];\r
- CopyTo (ret, 0);\r
- return ret;\r
- }\r
-\r
- public virtual void TrimToSize() {\r
- object[] trimmed = new object [count];\r
- CopyTo (trimmed, 0);\r
- contents = trimmed;\r
- }\r
-\r
- // private methods\r
-\r
- private void grow () {\r
- int newCapacity = (int) Math.Ceiling\r
- (contents.Length * growFactor);\r
- object[] newContents = new object[newCapacity];\r
- CopyTo (newContents, 0);\r
- contents = newContents;\r
- head = 0;\r
- }\r
-\r
- // private classes\r
-\r
- private class SyncQueue : Queue {\r
- Queue queue;\r
- \r
- internal SyncQueue (Queue queue) {\r
- this.queue = queue;\r
- }\r
- \r
- public override int Count {\r
- get { \r
- lock (queue) {\r
- return queue.count; \r
- }\r
- }\r
- }\r
-\r
- public override bool IsSynchronized {\r
- get { \r
- lock (queue) {\r
- return queue.IsSynchronized;\r
- }\r
- }\r
- }\r
-\r
- public override object SyncRoot {\r
- get { \r
- return queue.SyncRoot; \r
- }\r
- }\r
-\r
- public override void CopyTo (Array array, int index) {\r
- lock (queue) {\r
- queue.CopyTo (array, index);\r
- }\r
- }\r
- \r
- public override IEnumerator GetEnumerator () {\r
- lock (queue) {\r
- return queue.GetEnumerator ();\r
- }\r
- }\r
- \r
- public override object Clone () {\r
- lock (queue) {\r
- return queue.Clone ();\r
- }\r
- }\r
- \r
-/*\r
- public override bool IsReadOnly {\r
- get { \r
- lock (queue) {\r
- return queue.IsReadOnly;\r
- }\r
- }\r
- }\r
-*/\r
-\r
- public override void Clear () {\r
- lock (queue) {\r
- queue.Clear ();\r
- }\r
- }\r
-\r
- public override bool Contains (object obj) {\r
- lock (queue) {\r
- return queue.Contains (obj);\r
- }\r
- }\r
- \r
- public override object Dequeue () {\r
- lock (queue) {\r
- return queue.Dequeue ();\r
- }\r
- }\r
- \r
- public override void Enqueue (object obj) {\r
- lock (queue) {\r
- queue.Enqueue (obj);\r
- }\r
- }\r
-\r
- public override object Peek () {\r
- lock (queue) {\r
- return queue.Peek ();\r
- }\r
- }\r
-\r
- public override object[] ToArray () {\r
- lock (queue) {\r
- return queue.ToArray ();\r
- }\r
- }\r
- }\r
-\r
- [Serializable]\r
- private class QueueEnumerator : IEnumerator {\r
- Queue queue;\r
- private int modCount;\r
- private int current;\r
-\r
- internal QueueEnumerator (Queue q) {\r
- queue = q;\r
- modCount = q.modCount;\r
- current = -1; // one element before the head\r
- }\r
-\r
- public virtual object Current {\r
- get {\r
- if (modCount != queue.modCount \r
- || current < 0\r
- || current >= queue.count)\r
- throw new InvalidOperationException ();\r
- return queue.contents[(queue.head + current) % queue.contents.Length];\r
- }\r
- }\r
-\r
- public virtual bool MoveNext () {\r
- if (modCount != queue.modCount) {\r
- throw new InvalidOperationException ();\r
- }\r
-\r
- if (current >= queue.count - 1) {\r
- return false;\r
- } else {\r
- current++;\r
- return true;\r
- }\r
- }\r
-\r
- public virtual void Reset () {\r
- if (modCount != queue.modCount) {\r
- throw new InvalidOperationException();\r
- }\r
- current = -1;\r
- }\r
- }\r
- }\r
-}\r
-\r
+//
+// System.Collections.Queue
+//
+// Author:
+// Ricardo Fernández Pascual
+//
+// (C) 2001 Ricardo Fernández Pascual
+//
+
+//
+// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
+
+using System;
+using System.Collections;
+using System.Runtime.InteropServices;
+
+namespace System.Collections {
+
+#if NET_2_0
+ [ComVisible(true)]
+#endif
+ [Serializable]
+ public class Queue : ICollection, IEnumerable, ICloneable {
+
+ private object[] _array;
+ private int _head = 0; // points to the first used slot
+ private int _size = 0;
+ private int _tail = 0;
+ private int _growFactor;
+ private int _version = 0;
+
+ public Queue () : this (32, 2.0F) {}
+ public Queue (int initialCapacity) : this (initialCapacity, 2.0F) {}
+ public Queue(ICollection col) : this (col == null ? 32 : col.Count)
+ {
+ if (col == null)
+ throw new ArgumentNullException ("col");
+
+ // We have to do this because msft seems to call the
+ // enumerator rather than CopyTo. This affects classes
+ // like bitarray.
+ foreach (object o in col)
+ Enqueue (o);
+ }
+
+ public Queue (int initialCapacity, float growFactor) {
+ if (initialCapacity < 0)
+ throw new ArgumentOutOfRangeException("capacity", "Needs a non-negative number");
+ if (!(growFactor >= 1.0F && growFactor <= 10.0F))
+ throw new ArgumentOutOfRangeException("growFactor", "Queue growth factor must be between 1.0 and 10.0, inclusive");
+
+ _array = new object[initialCapacity];
+
+ this._growFactor = (int)(growFactor * 100);
+ }
+
+ // from ICollection
+
+ public virtual int Count {
+ get { return _size; }
+ }
+
+ public virtual bool IsSynchronized {
+ get { return false; }
+ }
+
+ public virtual object SyncRoot {
+ get { return this; }
+ }
+
+ public virtual void CopyTo (Array array, int index)
+ {
+ if (array == null)
+ throw new ArgumentNullException ("array");
+
+ if (index < 0)
+ throw new ArgumentOutOfRangeException ("index");
+
+ if (array.Rank > 1
+ || (index != 0 && index >= array.Length)
+ || _size > array.Length - index)
+ throw new ArgumentException ();
+
+ int contents_length = _array.Length;
+ int length_from_head = contents_length - _head;
+ // copy the _array of the circular array
+ Array.Copy (_array, _head, array, index,
+ Math.Min (_size, length_from_head));
+ if (_size > length_from_head)
+ Array.Copy (_array, 0, array,
+ index + length_from_head,
+ _size - length_from_head);
+ }
+
+ // from IEnumerable
+
+ public virtual IEnumerator GetEnumerator () {
+ return new QueueEnumerator (this);
+ }
+
+ // from ICloneable
+
+ public virtual object Clone () {
+ Queue newQueue;
+
+ newQueue = new Queue (this._array.Length);
+ newQueue._growFactor = _growFactor;
+
+ Array.Copy (this._array, 0, newQueue._array, 0,
+ this._array.Length);
+ newQueue._head = this._head;
+ newQueue._size = this._size;
+ newQueue._tail = this._tail;
+
+ return newQueue;
+ }
+
+ public virtual void Clear () {
+ _version++;
+ _head = 0;
+ _size = 0;
+ _tail = 0;
+ for (int length = _array.Length - 1; length >= 0; length--)
+ _array [length] = null;
+ }
+
+ public virtual bool Contains (object obj) {
+ int tail = _head + _size;
+ if (obj == null) {
+ for (int i = _head; i < tail; i++) {
+ if (_array[i % _array.Length] == null)
+ return true;
+ }
+ } else {
+ for (int i = _head; i < tail; i++) {
+ if (obj.Equals (_array[i % _array.Length]))
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public virtual object Dequeue ()
+ {
+ _version++;
+ if (_size < 1)
+ throw new InvalidOperationException ();
+ object result = _array[_head];
+ _array [_head] = null;
+ _head = (_head + 1) % _array.Length;
+ _size--;
+ return result;
+ }
+
+ public virtual void Enqueue (object obj) {
+ _version++;
+ if (_size == _array.Length)
+ grow ();
+ _array[_tail] = obj;
+ _tail = (_tail+1) % _array.Length;
+ _size++;
+
+ }
+
+ public virtual object Peek () {
+ if (_size < 1)
+ throw new InvalidOperationException ();
+ return _array[_head];
+ }
+
+ public static Queue Synchronized (Queue queue) {
+ if (queue == null) {
+ throw new ArgumentNullException ("queue");
+ }
+ return new SyncQueue (queue);
+ }
+
+ public virtual object[] ToArray () {
+ object[] ret = new object[_size];
+ CopyTo (ret, 0);
+ return ret;
+ }
+
+ public virtual void TrimToSize() {
+ _version++;
+ object[] trimmed = new object [_size];
+ CopyTo (trimmed, 0);
+ _array = trimmed;
+ _head = 0;
+ _tail = _head + _size;
+ }
+
+ // private methods
+
+ private void grow () {
+ int newCapacity = (_array.Length * _growFactor) / 100;
+ if (newCapacity < _array.Length + 1)
+ newCapacity = _array.Length + 1;
+ object[] newContents = new object[newCapacity];
+ CopyTo (newContents, 0);
+ _array = newContents;
+ _head = 0;
+ _tail = _head + _size;
+ }
+
+ // private classes
+
+ private class SyncQueue : Queue {
+ Queue queue;
+
+ internal SyncQueue (Queue queue) {
+ this.queue = queue;
+ }
+
+ public override int Count {
+ get {
+ lock (queue) {
+ return queue.Count;
+ }
+ }
+ }
+
+ public override bool IsSynchronized {
+ get {
+ return true;
+ }
+ }
+
+ public override object SyncRoot {
+ get {
+ return queue.SyncRoot;
+ }
+ }
+
+ public override void CopyTo (Array array, int index) {
+ lock (queue) {
+ queue.CopyTo (array, index);
+ }
+ }
+
+ public override IEnumerator GetEnumerator () {
+ lock (queue) {
+ return queue.GetEnumerator ();
+ }
+ }
+
+ public override object Clone () {
+ lock (queue) {
+ return new SyncQueue((Queue) queue.Clone ());
+ }
+ }
+
+/*
+ public override bool IsReadOnly {
+ get {
+ lock (queue) {
+ return queue.IsReadOnly;
+ }
+ }
+ }
+*/
+
+ public override void Clear () {
+ lock (queue) {
+ queue.Clear ();
+ }
+ }
+
+ public override void TrimToSize () {
+ lock (queue) {
+ queue.TrimToSize ();
+ }
+ }
+
+ public override bool Contains (object obj) {
+ lock (queue) {
+ return queue.Contains (obj);
+ }
+ }
+
+ public override object Dequeue () {
+ lock (queue) {
+ return queue.Dequeue ();
+ }
+ }
+
+ public override void Enqueue (object obj) {
+ lock (queue) {
+ queue.Enqueue (obj);
+ }
+ }
+
+ public override object Peek () {
+ lock (queue) {
+ return queue.Peek ();
+ }
+ }
+
+ public override object[] ToArray () {
+ lock (queue) {
+ return queue.ToArray ();
+ }
+ }
+ }
+
+ [Serializable]
+ private class QueueEnumerator : IEnumerator, ICloneable {
+ Queue queue;
+ private int _version;
+ private int current;
+
+ internal QueueEnumerator (Queue q) {
+ queue = q;
+ _version = q._version;
+ current = -1; // one element before the _head
+ }
+
+ public object Clone ()
+ {
+ QueueEnumerator q = new QueueEnumerator (queue);
+ q._version = _version;
+ q.current = current;
+ return q;
+ }
+
+ public virtual object Current {
+ get {
+ if (_version != queue._version
+ || current < 0
+ || current >= queue._size)
+ throw new InvalidOperationException ();
+ return queue._array[(queue._head + current) % queue._array.Length];
+ }
+ }
+
+ public virtual bool MoveNext () {
+ if (_version != queue._version) {
+ throw new InvalidOperationException ();
+ }
+
+ if (current >= queue._size - 1) {
+ current = Int32.MaxValue; // to late!
+ return false;
+ } else {
+ current++;
+ return true;
+ }
+ }
+
+ public virtual void Reset () {
+ if (_version != queue._version) {
+ throw new InvalidOperationException();
+ }
+ current = -1;
+ }
+ }
+ }
+}
+