|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;
namespace System.Collections.Generic
{
/// <summary>
/// Represents a first-in, first-out collection of objects.
/// </summary>
/// <remarks>
/// Implemented as a circular buffer, so <see cref="Enqueue(T)"/> and <see cref="Dequeue"/> are typically <c>O(1)</c>.
/// </remarks>
[DebuggerTypeProxy(typeof(QueueDebugView<>))]
[DebuggerDisplay("Count = {Count}")]
[Serializable]
[TypeForwardedFrom("System, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")]
public class Queue<T> : IEnumerable<T>,
ICollection,
IReadOnlyCollection<T>
{
private T[] _array;
private int _head; // The index from which to dequeue if the queue isn't empty.
private int _tail; // The index at which to enqueue if the queue isn't full.
private int _size; // Number of elements.
private int _version;
// Creates a queue with room for capacity objects. The default initial
// capacity and grow factor are used.
public Queue()
{
_array = [];
}
// Creates a queue with room for capacity objects. The default grow factor
// is used.
public Queue(int capacity)
{
ArgumentOutOfRangeException.ThrowIfNegative(capacity);
_array = new T[capacity];
}
// Fills a Queue with the elements of an ICollection. Uses the enumerator
// to get each of the elements.
public Queue(IEnumerable<T> collection)
{
ArgumentNullException.ThrowIfNull(collection);
_array = EnumerableHelpers.ToArray(collection, out _size);
if (_size != _array.Length) _tail = _size;
}
public int Count => _size;
/// <summary>
/// Gets the total numbers of elements the internal data structure can hold without resizing.
/// </summary>
public int Capacity => _array.Length;
/// <inheritdoc cref="ICollection.IsSynchronized" />
bool ICollection.IsSynchronized => false;
object ICollection.SyncRoot => this;
// Removes all Objects from the queue.
public void Clear()
{
if (_size != 0)
{
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
if (_head < _tail)
{
Array.Clear(_array, _head, _size);
}
else
{
Array.Clear(_array, _head, _array.Length - _head);
Array.Clear(_array, 0, _tail);
}
}
_size = 0;
}
_head = 0;
_tail = 0;
_version++;
}
// CopyTo copies a collection into an Array, starting at a particular
// index into the array.
public void CopyTo(T[] array, int arrayIndex)
{
ArgumentNullException.ThrowIfNull(array);
if (arrayIndex < 0 || arrayIndex > array.Length)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_IndexMustBeLessOrEqual);
}
if (array.Length - arrayIndex < _size)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
}
int numToCopy = _size;
if (numToCopy == 0) return;
int firstPart = Math.Min(_array.Length - _head, numToCopy);
Array.Copy(_array, _head, array, arrayIndex, firstPart);
numToCopy -= firstPart;
if (numToCopy > 0)
{
Array.Copy(_array, 0, array, arrayIndex + _array.Length - _head, numToCopy);
}
}
void ICollection.CopyTo(Array array, int index)
{
ArgumentNullException.ThrowIfNull(array);
if (array.Rank != 1)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported, ExceptionArgument.array);
}
if (array.GetLowerBound(0) != 0)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound, ExceptionArgument.array);
}
int arrayLen = array.Length;
if (index < 0 || index > arrayLen)
{
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessOrEqualException();
}
if (arrayLen - index < _size)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
}
int numToCopy = _size;
if (numToCopy == 0) return;
try
{
int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy;
Array.Copy(_array, _head, array, index, firstPart);
numToCopy -= firstPart;
if (numToCopy > 0)
{
Array.Copy(_array, 0, array, index + _array.Length - _head, numToCopy);
}
}
catch (ArrayTypeMismatchException)
{
ThrowHelper.ThrowArgumentException_Argument_IncompatibleArrayType();
}
}
// Adds item to the tail of the queue.
public void Enqueue(T item)
{
if (_size == _array.Length)
{
Grow(_size + 1);
}
_array[_tail] = item;
MoveNext(ref _tail);
_size++;
_version++;
}
// GetEnumerator returns an IEnumerator over this Queue. This
// Enumerator will support removing.
public Enumerator GetEnumerator() => new Enumerator(this);
/// <internalonly/>
IEnumerator<T> IEnumerable<T>.GetEnumerator() =>
Count == 0 ? SZGenericArrayEnumerator<T>.Empty :
GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => ((IEnumerable<T>)this).GetEnumerator();
// Removes the object at the head of the queue and returns it. If the queue
// is empty, this method throws an
// InvalidOperationException.
public T Dequeue()
{
int head = _head;
T[] array = _array;
if (_size == 0)
{
ThrowForEmptyQueue();
}
T removed = array[head];
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
array[head] = default!;
}
MoveNext(ref _head);
_size--;
_version++;
return removed;
}
public bool TryDequeue([MaybeNullWhen(false)] out T result)
{
int head = _head;
T[] array = _array;
if (_size == 0)
{
result = default;
return false;
}
result = array[head];
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
array[head] = default!;
}
MoveNext(ref _head);
_size--;
_version++;
return true;
}
// Returns the object at the head of the queue. The object remains in the
// queue. If the queue is empty, this method throws an
// InvalidOperationException.
public T Peek()
{
if (_size == 0)
{
ThrowForEmptyQueue();
}
return _array[_head];
}
public bool TryPeek([MaybeNullWhen(false)] out T result)
{
if (_size == 0)
{
result = default;
return false;
}
result = _array[_head];
return true;
}
// Returns true if the queue contains at least one object equal to item.
// Equality is determined using EqualityComparer<T>.Default.Equals().
public bool Contains(T item)
{
if (_size == 0)
{
return false;
}
if (_head < _tail)
{
return Array.IndexOf(_array, item, _head, _size) >= 0;
}
// We've wrapped around. Check both partitions, the least recently enqueued first.
return
Array.IndexOf(_array, item, _head, _array.Length - _head) >= 0 ||
Array.IndexOf(_array, item, 0, _tail) >= 0;
}
// Iterates over the objects in the queue, returning an array of the
// objects in the Queue, or an empty array if the queue is empty.
// The order of elements in the array is first in to last in, the same
// order produced by successive calls to Dequeue.
public T[] ToArray()
{
if (_size == 0)
{
return [];
}
T[] arr = new T[_size];
if (_head < _tail)
{
Array.Copy(_array, _head, arr, 0, _size);
}
else
{
Array.Copy(_array, _head, arr, 0, _array.Length - _head);
Array.Copy(_array, 0, arr, _array.Length - _head, _tail);
}
return arr;
}
// PRIVATE Grows or shrinks the buffer to hold capacity objects. Capacity
// must be >= _size.
private void SetCapacity(int capacity)
{
Debug.Assert(capacity >= _size);
T[] newarray = new T[capacity];
if (_size > 0)
{
if (_head < _tail)
{
Array.Copy(_array, _head, newarray, 0, _size);
}
else
{
Array.Copy(_array, _head, newarray, 0, _array.Length - _head);
Array.Copy(_array, 0, newarray, _array.Length - _head, _tail);
}
}
_array = newarray;
_head = 0;
_tail = (_size == capacity) ? 0 : _size;
_version++;
}
// Increments the index wrapping it if necessary.
private void MoveNext(ref int index)
{
// It is tempting to use the remainder operator here but it is actually much slower
// than a simple comparison and a rarely taken branch.
// JIT produces better code than with ternary operator ?:
int tmp = index + 1;
if (tmp == _array.Length)
{
tmp = 0;
}
index = tmp;
}
private void ThrowForEmptyQueue()
{
Debug.Assert(_size == 0);
throw new InvalidOperationException(SR.InvalidOperation_EmptyQueue);
}
public void TrimExcess()
{
int threshold = (int)(_array.Length * 0.9);
if (_size < threshold)
{
SetCapacity(_size);
}
}
/// <summary>
/// Sets the capacity of a <see cref="Queue{T}"/> object to the specified number of entries.
/// </summary>
/// <param name="capacity">The new capacity.</param>
/// <exception cref="ArgumentOutOfRangeException">Passed capacity is lower than entries count.</exception>
public void TrimExcess(int capacity)
{
ArgumentOutOfRangeException.ThrowIfNegative(capacity);
ArgumentOutOfRangeException.ThrowIfLessThan(capacity, _size);
if (capacity == _array.Length)
return;
SetCapacity(capacity);
}
/// <summary>
/// Ensures that the capacity of this Queue is at least the specified <paramref name="capacity"/>.
/// </summary>
/// <param name="capacity">The minimum capacity to ensure.</param>
/// <returns>The new capacity of this queue.</returns>
public int EnsureCapacity(int capacity)
{
ArgumentOutOfRangeException.ThrowIfNegative(capacity);
if (_array.Length < capacity)
{
Grow(capacity);
}
return _array.Length;
}
private void Grow(int capacity)
{
Debug.Assert(_array.Length < capacity);
const int GrowFactor = 2;
const int MinimumGrow = 4;
int newcapacity = GrowFactor * _array.Length;
// Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
// Note that this check works even when _items.Length overflowed thanks to the (uint) cast
if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength;
// Ensure minimum growth is respected.
newcapacity = Math.Max(newcapacity, _array.Length + MinimumGrow);
// If the computed capacity is still less than specified, set to the original argument.
// Capacities exceeding Array.MaxLength will be surfaced as OutOfMemoryException by Array.Resize.
if (newcapacity < capacity) newcapacity = capacity;
SetCapacity(newcapacity);
}
// Implements an enumerator for a Queue. The enumerator uses the
// internal version number of the list to ensure that no modifications are
// made to the list while an enumeration is in progress.
public struct Enumerator : IEnumerator<T>,
IEnumerator
{
private readonly Queue<T> _queue;
private readonly int _version;
private int _i;
private T? _currentElement;
internal Enumerator(Queue<T> queue)
{
_queue = queue;
_version = queue._version;
_i = -1;
_currentElement = default;
}
public void Dispose()
{
_i = -2;
_currentElement = default;
}
public bool MoveNext()
{
if (_version != _queue._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
Queue<T> q = _queue;
int size = q._size;
int offset = _i + 1;
if ((uint)offset < (uint)size)
{
_i = offset;
T[] array = q._array;
int index = q._head + offset;
if ((uint)index < (uint)array.Length)
{
_currentElement = array[index];
}
else
{
// The index has wrapped around the end of the array. Shift the index and then
// get the current element. It is tempting to dedup this dereferencing with that
// in the if block above, but the if block above avoids a bounds check for the
// accesses that are in that portion, whereas these still incur it.
index -= array.Length;
_currentElement = array[index];
}
return true;
}
_i = -2;
_currentElement = default;
return false;
}
public T Current => _currentElement!;
object? IEnumerator.Current => Current;
void IEnumerator.Reset()
{
if (_version != _queue._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
_i = -1;
_currentElement = default;
}
}
}
}
|