-//
+//
// System.Collections.Queue
//
// Author:
-// Ricardo Fernández Pascual
+// Ricardo Fernández Pascual
+//
+// (C) 2001 Ricardo Fernández Pascual
+//
+
+//
+// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
//
-// (C) 2001 Ricardo Fernández Pascual
+// 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 {
+ [ComVisible(true)]
+ [System.Diagnostics.DebuggerDisplay ("Count={Count}")]
+ [System.Diagnostics.DebuggerTypeProxy (typeof (CollectionDebuggerView))]
[Serializable]
- public class Queue : ICollection, IEnumerable, ICloneable {
-
- private object[] contents;
- private int head = 0; // points to the first used slot
- private int count = 0;
- private int capacity;
- private float growFactor;
- private int modCount = 0;
+#if INSIDE_CORLIB
+ public
+#else
+ internal
+#endif
+ 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 (int capacity) : this (capacity, 2.0F) {}
+
public Queue(ICollection col) : this (col == null ? 32 : col.Count)
{
if (col == null)
throw new ArgumentNullException ("col");
- count = capacity;
- col.CopyTo (contents, 0);
+ // 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)
+ public Queue (int capacity, float growFactor) {
+ if (capacity < 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");
- capacity = initialCapacity;
- contents = new object[capacity];
+ _array = new object[capacity];
- this.growFactor = growFactor;
+ this._growFactor = (int)(growFactor * 100);
}
-
+
// from ICollection
public virtual int Count {
- get { return count; }
+ get { return _size; }
}
public virtual bool IsSynchronized {
if (array.Rank > 1
|| (index != 0 && index >= array.Length)
- || count > array.Length - index)
+ || _size > array.Length - index)
throw new ArgumentException ();
- int contents_length = contents.Length;
- int length_from_head = contents_length - head;
- // copy the contents of the circular array
- Array.Copy (contents, head, array, index,
- Math.Min (count, length_from_head));
- if (count > length_from_head)
- Array.Copy (contents, 0, array,
+ 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,
- count - length_from_head);
+ _size - length_from_head);
}
// from IEnumerable
public virtual object Clone () {
Queue newQueue;
- newQueue = new Queue (); // FIXME: improve this...
+ newQueue = new Queue (this._array.Length);
+ newQueue._growFactor = _growFactor;
- newQueue.contents = new object[this.contents.Length];
- Array.Copy (this.contents, 0, newQueue.contents, 0,
- this.contents.Length);
- newQueue.head = this.head;
- newQueue.count = this.count;
- newQueue.capacity = this.capacity;
- newQueue.growFactor = this.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;
}
- // FIXME: should override Equals?
-
- // from Queue spec
-
-/*
- public virtual bool IsReadOnly {
- get { return false; }
- }
-*/
-
public virtual void Clear () {
- modCount++;
- head = 0;
- count = 0;
- // FIXME: Should allocate a new contents array?
- // Should null the current array?
+ _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 + count;
+ int tail = _head + _size;
if (obj == null) {
- for (int i = head; i < tail; i++) {
- if (contents[i % capacity] == 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 (contents[i % capacity]))
+ for (int i = _head; i < tail; i++) {
+ if (obj.Equals (_array[i % _array.Length]))
return true;
}
}
public virtual object Dequeue ()
{
- modCount++;
- if (count < 1)
+ _version++;
+ if (_size < 1)
throw new InvalidOperationException ();
- object result = contents[head];
- head = (head + 1) % capacity;
- count--;
+ object result = _array[_head];
+ _array [_head] = null;
+ _head = (_head + 1) % _array.Length;
+ _size--;
return result;
}
public virtual void Enqueue (object obj) {
- modCount++;
- if (count == capacity)
+ _version++;
+ if (_size == _array.Length)
grow ();
- contents[(head + count) % capacity] = obj;
- count++;
+ _array[_tail] = obj;
+ _tail = (_tail+1) % _array.Length;
+ _size++;
}
public virtual object Peek () {
- if (count < 1)
+ if (_size < 1)
throw new InvalidOperationException ();
- return contents[head];
+ return _array[_head];
}
public static Queue Synchronized (Queue queue) {
if (queue == null) {
- throw new ArgumentNullException ();
+ throw new ArgumentNullException ("queue");
}
return new SyncQueue (queue);
}
public virtual object[] ToArray () {
- object[] ret = new object[count];
+ object[] ret = new object[_size];
CopyTo (ret, 0);
return ret;
}
public virtual void TrimToSize() {
- object[] trimmed = new object [count];
+ _version++;
+ object[] trimmed = new object [_size];
CopyTo (trimmed, 0);
- contents = trimmed;
+ _array = trimmed;
+ _head = 0;
+ _tail = 0;
}
// private methods
private void grow () {
- int newCapacity = (int) Math.Ceiling
- (contents.Length * growFactor);
+ int newCapacity = (_array.Length * _growFactor) / 100;
+ if (newCapacity < _array.Length + 1)
+ newCapacity = _array.Length + 1;
object[] newContents = new object[newCapacity];
CopyTo (newContents, 0);
- contents = newContents;
- capacity = newCapacity;
- head = 0;
+ _array = newContents;
+ _head = 0;
+ _tail = _head + _size;
}
// private classes
public override int Count {
get {
lock (queue) {
- return queue.count;
+ return queue.Count;
}
}
}
public override object Clone () {
lock (queue) {
- return queue.Clone ();
+ return new SyncQueue((Queue) queue.Clone ());
}
}
}
}
+ public override void TrimToSize () {
+ lock (queue) {
+ queue.TrimToSize ();
+ }
+ }
+
public override bool Contains (object obj) {
lock (queue) {
return queue.Contains (obj);
[Serializable]
private class QueueEnumerator : IEnumerator, ICloneable {
Queue queue;
- private int modCount;
+ private int _version;
private int current;
internal QueueEnumerator (Queue q) {
queue = q;
- modCount = q.modCount;
- current = -1; // one element before the head
+ _version = q._version;
+ current = -1; // one element before the _head
}
public object Clone ()
{
QueueEnumerator q = new QueueEnumerator (queue);
- q.modCount = modCount;
+ q._version = _version;
q.current = current;
return q;
}
public virtual object Current {
get {
- if (modCount != queue.modCount
+ if (_version != queue._version
|| current < 0
- || current >= queue.count)
+ || current >= queue._size)
throw new InvalidOperationException ();
- return queue.contents[(queue.head + current) % queue.contents.Length];
+ return queue._array[(queue._head + current) % queue._array.Length];
}
}
public virtual bool MoveNext () {
- if (modCount != queue.modCount) {
+ if (_version != queue._version) {
throw new InvalidOperationException ();
}
- if (current >= queue.count - 1) {
+ if (current >= queue._size - 1) {
+ current = Int32.MaxValue; // to late!
return false;
} else {
current++;
}
public virtual void Reset () {
- if (modCount != queue.modCount) {
+ if (_version != queue._version) {
throw new InvalidOperationException();
}
current = -1;
projects / mono.git / blobdiff