//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement
// contained in the file "License.txt" accompanying this file.
//******************************
using System;
using System.Collections.Generic;
using System.Collections;
// CONSIDER: always create a small initial buffer, so that the checks in Add for a null buffer aren't needed. This
// would improve performance slightly, but make empty Deque's take more memory.
namespace Wintellect.PowerCollections
{
/// <summary>
/// <para>The Deque class implements a type of list known as a Double Ended Queue. A Deque
/// is quite similar to a List, in that items have indices (starting at 0), and the item at any
/// index can be efficiently retrieved. The difference between a List and a Deque lies in the
/// efficiency of inserting elements at the beginning. In a List, items can be efficiently added
/// to the end, but inserting an item at the beginning of the List is slow, taking time
/// proportional to the size of the List. In a Deque, items can be added to the beginning
/// or end equally efficiently, regardless of the number of items in the Deque. As a trade-off
/// for this increased flexibility, Deque is somewhat slower than List (but still constant time) when
/// being indexed to get or retrieve elements. </para>
/// </summary>
/// <remarks>
/// <para>The Deque class can also be used as a more flexible alternative to the Queue
/// and Stack classes. Deque is as efficient as Queue and Stack for adding or removing items,
/// but is more flexible: it allows access
/// to all items in the queue, and allows adding or removing from either end.</para>
/// <para>Deque is implemented as a ring buffer, which is grown as necessary. The size
/// of the buffer is doubled whenever the existing capacity is too small to hold all the
/// elements.</para>
/// </remarks>
/// <typeparam name="T">The type of items stored in the Deque.</typeparam>
[Serializable]
public class Deque<T> : ListBase<T>, ICloneable
{
// The initial size of the buffer.
private const int INITIAL_SIZE = 8;
// A ring buffer containing all the items in the deque. Shrinks or grows as needed.
// Except temporarily during an add, there is always at least one empty item.
private T[] buffer;
// Index of the first item (index 0) in the deque.
// Always in the range 0 through buffer.Length - 1.
private int start;
// Index just beyond the last item in the deque. If equal to start, the deque is empty.
// Always in the range 0 through buffer.Length - 1.
private int end;
// Holds the change stamp for the collection.
private int changeStamp;
/// <summary>
/// Must be called whenever there is a structural change in the tree. Causes
/// changeStamp to be changed, which causes any in-progress enumerations
/// to throw exceptions.
/// </summary>
private void StopEnumerations()
{
++changeStamp;
}
/// <summary>
/// Checks the given stamp against the current change stamp. If different, the
/// collection has changed during enumeration and an InvalidOperationException
/// must be thrown
/// </summary>
/// <param name="startStamp">changeStamp at the start of the enumeration.</param>
private void CheckEnumerationStamp(int startStamp)
{
if (startStamp != changeStamp) {
throw new InvalidOperationException(Strings.ChangeDuringEnumeration);
}
}
/// <summary>
/// Create a new Deque that is initially empty.
/// </summary>
public Deque()
{
}
/// <summary>
/// Create a new Deque initialized with the items from the passed collection,
/// in order.
/// </summary>
/// <param name="collection">A collection of items to initialize the Deque with.</param>
public Deque(IEnumerable<T> collection)
{
AddManyToBack(collection);
}
/// <summary>
/// Gets the number of items currently stored in the Deque. The last item
/// in the Deque has index Count-1.
/// </summary>
/// <remarks>Getting the count of items in the Deque takes a small constant
/// amount of time.</remarks>
/// <value>The number of items stored in this Deque.</value>
public sealed override int Count
{
get {
if (end >= start)
return end - start;
else
return end + buffer.Length - start;
}
}
/// <summary>
/// Copies all the items in the Deque into an array.
/// </summary>
/// <param name="array">Array to copy to.</param>
/// <param name="arrayIndex">Starting index in <paramref name="array"/> to copy to.</param>
public sealed override void CopyTo(T[] array, int arrayIndex)
{
if (array == null)
throw new ArgumentNullException("array");
// This override is provided to give a more efficient implementation to CopyTo than
// the default one provided by CollectionBase.
int length = (buffer == null) ? 0 : buffer.Length;
if (start > end) {
Array.Copy(buffer, start, array, arrayIndex, length - start);
Array.Copy(buffer, 0, array, arrayIndex + length - start, end);
}
else {
if (end > start)
Array.Copy(buffer, start, array, arrayIndex, end - start);
}
}
/// <summary>
/// Gets or sets the capacity of the Deque. The Capacity is the number of
/// items that this Deque can hold without expanding its internal buffer. Since
/// Deque will automatically expand its buffer when necessary, in almost all cases
/// it is unnecessary to worry about the capacity. However, if it is known that a
/// Deque will contain exactly 1000 items eventually, it can slightly improve
/// efficiency to set the capacity to 1000 up front, so that the Deque does not
/// have to expand automatically.
/// </summary>
/// <value>The number of items that this Deque can hold without expanding its
/// internal buffer.</value>
/// <exception cref="ArgumentOutOfRangeException">The capacity is being set
/// to less than Count, or to too large a value.</exception>
public int Capacity
{
get
{
if (buffer == null)
return 0;
else
return buffer.Length - 1;
}
set
{
if (value < Count)
throw new ArgumentOutOfRangeException("value", Strings.CapacityLessThanCount);
if (value > int.MaxValue - 1)
throw new ArgumentOutOfRangeException("value");
if (value == Capacity)
return;
T[] newBuffer = new T[value + 1];
CopyTo(newBuffer, 0);
end = Count;
start = 0;
buffer = newBuffer;
}
}
/// <summary>
/// Trims the amount of memory used by the Deque by changing
/// the Capacity to be equal to Count. If no more items will be added
/// to the Deque, calling TrimToSize will reduce the amount of memory
/// used by the Deque.
/// </summary>
public void TrimToSize()
{
Capacity = Count;
}
/// <summary>
/// Removes all items from the Deque.
/// </summary>
/// <remarks>Clearing the Deque takes a small constant amount of time, regardless of
/// how many items are currently in the Deque.</remarks>
public sealed override void Clear()
{
StopEnumerations();
buffer = null;
start = end = 0;
}
/// <summary>
/// Gets or sets an item at a particular index in the Deque.
/// </summary>
/// <remarks>Getting or setting the item at a particular index takes a small constant amount
/// of time, no matter what index is used.</remarks>
/// <param name="index">The index of the item to retrieve or change. The front item has index 0, and
/// the back item has index Count-1.</param>
/// <returns>The value at the indicated index.</returns>
/// <exception cref="ArgumentOutOfRangeException">The index is less than zero or greater than or equal
/// to Count.</exception>
public sealed override T this[int index]
{
get
{
int i = index + start;
if (i < start) // handles both the case where index < 0, or the above addition overflow to a negative number.
throw new ArgumentOutOfRangeException("index");
if (end >= start) {
if (i >= end)
throw new ArgumentOutOfRangeException("index");
return buffer[i];
}
else {
int length = buffer.Length;
if (i >= length) {
i -= length;
if (i >= end)
throw new ArgumentOutOfRangeException("index");
}
return buffer[i];
}
}
set
{
// Like List<T>, we stop enumerations after a set operation. There is no
// technical reason to do this, however.
StopEnumerations();
int i = index + start;
if (i < start) // handles both the case where index < 0, or the above addition overflow to a negative number.
throw new ArgumentOutOfRangeException("index");
if (end >= start) {
if (i >= end)
throw new ArgumentOutOfRangeException("index");
buffer[i] = value;
}
else {
int length = buffer.Length;
if (i >= length) {
i -= length;
if (i >= end)
throw new ArgumentOutOfRangeException("index");
}
buffer[i] = value;
}
}
}
/// <summary>
/// Enumerates all of the items in the list, in order. The item at index 0
/// is enumerated first, then the item at index 1, and so on. If the items
/// are added to or removed from the Deque during enumeration, the
/// enumeration ends with an InvalidOperationException.
/// </summary>
/// <returns>An IEnumerator<T> that enumerates all the
/// items in the list.</returns>
/// <exception cref="InvalidOperationException">The Deque has an item added or deleted during the enumeration.</exception>
public sealed override IEnumerator<T> GetEnumerator()
{
int startStamp = changeStamp;
int count = Count;
for (int i = 0; i < count; ++i) {
yield return this[i];
CheckEnumerationStamp(startStamp);
}
}
/// <summary>
/// Creates the initial buffer and initialized the Deque to contain one initial
/// item.
/// </summary>
/// <param name="firstItem">First and only item for the Deque.</param>
private void CreateInitialBuffer(T firstItem)
{
// The buffer hasn't been created yet.
buffer = new T[INITIAL_SIZE];
start = 0;
end = 1;
buffer[0] = firstItem;
return;
}
/// <summary>
/// Inserts a new item at the given index in the Deque. All items at indexes
/// equal to or greater than <paramref name="index"/> move up one index
/// in the Deque.
/// </summary>
/// <remarks>The amount of time to insert an item in the Deque is proportional
/// to the distance of index from the closest end of the Deque:
/// O(Min(<paramref name="index"/>, Count - <paramref name="index"/>)).
/// Thus, inserting an item at the front or end of the Deque is always fast; the middle of
/// of the Deque is the slowest place to insert.
/// </remarks>
/// <param name="index">The index in the Deque to insert the item at. After the
/// insertion, the inserted item is located at this index. The
/// front item in the Deque has index 0.</param>
/// <param name="item">The item to insert at the given index.</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
/// less than zero or greater than Count.</exception>
public sealed override void Insert(int index, T item)
{
StopEnumerations();
int count = Count;
if (index < 0 || index > Count)
throw new ArgumentOutOfRangeException("index");
if (buffer == null) {
// The buffer hasn't been created yet.
CreateInitialBuffer(item);
return;
}
int length = buffer.Length;
int i; // The location the new item was placed at.
if (index < count / 2) {
// Inserting into the first half of the list. Move items with
// lower index down in the buffer.
start -= 1;
if (start < 0)
start += length;
i = index + start;
if (i >= length) {
i -= length;
if (length - 1 > start)
Array.Copy(buffer, start + 1, buffer, start, length - 1 - start);
buffer[length - 1] = buffer[0]; // unneeded if end == 0, but doesn't hurt
if (i > 0)
Array.Copy(buffer, 1, buffer, 0, i);
}
else {
if (i > start)
Array.Copy(buffer, start + 1, buffer, start, i - start);
}
}
else {
// Inserting into the last half of the list. Move items with higher
// index up in the buffer.
i = index + start;
if (i >= length)
i -= length;
if (i <= end) {
if (end > i)
Array.Copy(buffer, i, buffer, i + 1, end - i);
end += 1;
if (end >= length)
end -= length;
}
else {
if (end > 0)
Array.Copy(buffer, 0, buffer, 1, end);
buffer[0] = buffer[length - 1];
if (length - 1 > i)
Array.Copy(buffer, i, buffer, i + 1, length - 1 - i);
end += 1;
}
}
buffer[i] = item;
if (start == end)
IncreaseBuffer();
}
/// <summary>
/// Inserts a collection of items at the given index in the Deque. All items at indexes
/// equal to or greater than <paramref name="index"/> increase their indices in the Deque
/// by the number of items inserted.
/// </summary>
/// <remarks>The amount of time to insert a collection in the Deque is proportional
/// to the distance of index from the closest end of the Deque, plus the number of items
/// inserted (M):
/// O(M + Min(<paramref name="index"/>, Count - <paramref name="index"/>)).
/// </remarks>
/// <param name="index">The index in the Deque to insert the collection at. After the
/// insertion, the first item of the inserted collection is located at this index. The
/// front item in the Deque has index 0.</param>
/// <param name="collection">The collection of items to insert at the given index.</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
/// less than zero or greater than Count.</exception>
public void InsertRange(int index, IEnumerable<T> collection)
{
if (collection == null)
throw new ArgumentNullException("collection");
StopEnumerations();
int count = Count;
if (index < 0 || index > Count)
throw new ArgumentOutOfRangeException("index");
// We need an ICollection, because we need the count of the collection.
// If needed, copy the items to a temporary list.
ICollection<T> coll;
if (collection is ICollection<T>)
coll = (ICollection<T>) collection;
else {
coll = new List<T>(collection);
}
if (coll.Count == 0)
return; // nothing to do.
// Create enough capacity in the list for the new items.
if (Capacity < Count + coll.Count)
Capacity = Count + coll.Count;
int length = buffer.Length;
int s, d;
if (index < count / 2) {
// Inserting into the first half of the list. Move items with
// lower index down in the buffer.
s = start;
d = s - coll.Count;
if (d < 0)
d += length;
start = d;
int c = index;
while (c > 0) {
int chunk = c;
if (length - d < chunk)
chunk = length - d;
if (length - s < chunk)
chunk = length - s;
Array.Copy(buffer, s, buffer, d, chunk);
c -= chunk;
if ((d += chunk) >= length)
d -= length;
if ((s += chunk) >= length)
s -= length;
}
}
else {
// Inserting into the last half of the list. Move items with higher
// index up in the buffer.
s = end;
d = s + coll.Count;
if (d >= length)
d -= length;
end = d;
int move = count - index; // number of items at end to move
int c = move;
while (c > 0) {
int chunk = c;
if (d > 0 && d < chunk)
chunk = d;
if (s > 0 && s < chunk)
chunk = s;
if ((d -= chunk) < 0)
d += length;
if ((s -= chunk) < 0)
s += length;
Array.Copy(buffer, s, buffer, d, chunk);
c -= chunk;
}
d -= coll.Count;
if (d < 0)
d += length;
}
// Copy the items into the space vacated, which starts at d.
foreach (T item in coll) {
buffer[d] = item;
if (++d >= length)
d -= length;
}
}
/// <summary>
/// Removes the item at the given index in the Deque. All items at indexes
/// greater than <paramref name="index"/> move down one index
/// in the Deque.
/// </summary>
/// <remarks>The amount of time to delete an item in the Deque is proportional
/// to the distance of index from the closest end of the Deque:
/// O(Min(<paramref name="index"/>, Count - 1 - <paramref name="index"/>)).
/// Thus, deleting an item at the front or end of the Deque is always fast; the middle of
/// of the Deque is the slowest place to delete.
/// </remarks>
/// <param name="index">The index in the list to remove the item at. The
/// first item in the list has index 0.</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
/// less than zero or greater than or equal to Count.</exception>
public sealed override void RemoveAt(int index)
{
StopEnumerations();
int count = Count;
if (index < 0 || index >= count)
throw new ArgumentOutOfRangeException("index");
int length = buffer.Length;
int i; // index of removed item
if (index < count / 2) {
// Removing in the first half of the list. Move items with
// lower index up in the buffer.
i = index + start;
if (i >= length) {
i -= length;
if (i > 0)
Array.Copy(buffer, 0, buffer, 1, i);
buffer[0] = buffer[length - 1];
if (length - 1 > start)
Array.Copy(buffer, start, buffer, start + 1, length - 1 - start);
}
else {
if (i > start)
Array.Copy(buffer, start, buffer, start + 1, i - start);
}
buffer[start] = default(T);
start += 1;
if (start >= length)
start -= length;
}
else {
// Removing in the second half of the list. Move items with
// higher indexes down in the buffer.
i = index + start;
if (i >= length)
i -= length;
end -= 1;
if (end < 0)
end = length - 1;
if (i <= end) {
if (end > i)
Array.Copy(buffer, i + 1, buffer, i, end - i);
}
else {
if (length - 1 > i)
Array.Copy(buffer, i + 1, buffer, i, length - 1 - i);
buffer[length - 1] = buffer[0];
if (end > 0)
Array.Copy(buffer, 1, buffer, 0, end);
}
buffer[end] = default(T);
}
}
/// <summary>
/// Removes a range of items at the given index in the Deque. All items at indexes
/// greater than <paramref name="index"/> move down <paramref name="count"/> indices
/// in the Deque.
/// </summary>
/// <remarks>The amount of time to delete <paramref name="count"/> items in the Deque is proportional
/// to the distance to the closest end of the Deque:
/// O(Min(<paramref name="index"/>, Count - <paramref name="index"/> - <paramref name="count"/>)).
/// </remarks>
/// <param name="index">The index in the list to remove the range at. The
/// first item in the list has index 0.</param>
/// <param name="count">The number of items to remove.</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
/// less than zero or greater than or equal to Count, or <paramref name="count"/> is less than zero
/// or too large.</exception>
public void RemoveRange(int index, int count)
{
StopEnumerations();
int dequeCount = Count;
if (index < 0 || index >= dequeCount)
throw new ArgumentOutOfRangeException("index");
if (count < 0 || count > dequeCount - index)
throw new ArgumentOutOfRangeException("count");
if (count == 0)
return;
int length = buffer.Length;
int s, d;
if (index < dequeCount / 2) {
// Removing in the first half of the list. Move items with
// lower index up in the buffer.
s = start + index;
if (s >= length)
s -= length;
d = s + count;
if (d >= length)
d -= length;
int c = index;
while (c > 0) {
int chunk = c;
if (d > 0 && d < chunk)
chunk = d;
if (s > 0 && s < chunk)
chunk = s;
if ((d -= chunk) < 0)
d += length;
if ((s -= chunk) < 0)
s += length;
Array.Copy(buffer, s, buffer, d, chunk);
c -= chunk;
}
// At this point, s == start
for (c = 0; c < count; ++c) {
buffer[s] = default(T);
if (++s >= length)
s -= length;
}
start = s;
}
else {
// Removing in the second half of the list. Move items with
// higher indexes down in the buffer.
int move = dequeCount - index - count;
s = end - move;
if (s < 0)
s += length;
d = s - count;
if (d < 0)
d += length;
int c = move;
while (c > 0) {
int chunk = c;
if (length - d < chunk)
chunk = length - d;
if (length - s < chunk)
chunk = length - s;
Array.Copy(buffer, s, buffer, d, chunk);
c -= chunk;
if ((d += chunk) >= length)
d -= length;
if ((s += chunk) >= length)
s -= length;
}
// At this point, s == end.
for (c = 0; c < count; ++c) {
if (--s < 0)
s += length;
buffer[s] = default(T);
}
end = s;
}
}
/// <summary>
/// Increase the amount of buffer space. When calling this method, the Deque
/// must not be empty. If start and end are equal, that indicates a completely
/// full Deque.
/// </summary>
private void IncreaseBuffer()
{
int count = Count;
int length = buffer.Length;
T[] newBuffer = new T[length * 2];
if (start >= end) {
Array.Copy(buffer, start, newBuffer, 0, length - start);
Array.Copy(buffer, 0, newBuffer, length - start, end);
end = end + length - start;
start = 0;
}
else {
Array.Copy(buffer, start, newBuffer, 0, end - start);
end = end - start;
start = 0;
}
buffer = newBuffer;
}
/// <summary>
/// Adds an item to the front of the Deque. The indices of all existing items
/// in the Deque are increased by 1. This method is
/// equivalent to <c>Insert(0, item)</c> but is a little more
/// efficient.
/// </summary>
/// <remarks>Adding an item to the front of the Deque takes
/// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
/// <param name="item">The item to add.</param>
public void AddToFront(T item)
{
StopEnumerations();
if (buffer == null) {
// The buffer hasn't been created yet.
CreateInitialBuffer(item);
return;
}
if (--start < 0)
start += buffer.Length;
buffer[start] = item;
if (start == end)
IncreaseBuffer();
}
/// <summary>
/// Adds a collection of items to the front of the Deque. The indices of all existing items
/// in the Deque are increased by the number of items inserted. The first item in the added collection becomes the
/// first item in the Deque.
/// </summary>
/// <remarks>This method takes time O(M), where M is the number of items in the
/// <paramref name="collection"/>.</remarks>
/// <param name="collection">The collection of items to add.</param>
public void AddManyToFront(IEnumerable<T> collection)
{
if (collection == null)
throw new ArgumentNullException("collection");
InsertRange(0, collection);
}
/// <summary>
/// Adds an item to the back of the Deque. The indices of all existing items
/// in the Deque are unchanged. This method is
/// equivalent to <c>Insert(Count, item)</c> but is a little more
/// efficient.
/// </summary>
/// <remarks>Adding an item to the back of the Deque takes
/// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
/// <param name="item">The item to add.</param>
public void AddToBack(T item)
{
StopEnumerations();
if (buffer == null) {
// The buffer hasn't been created yet.
CreateInitialBuffer(item);
return;
}
buffer[end] = item;
if (++end >= buffer.Length)
end -= buffer.Length;
if (start == end)
IncreaseBuffer();
}
/// <summary>
/// Adds an item to the back of the Deque. The indices of all existing items
/// in the Deque are unchanged. This method is
/// equivalent to <c>AddToBack(item)</c>.
/// </summary>
/// <remarks>Adding an item to the back of the Deque takes
/// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
/// <param name="item">The item to add.</param>
public sealed override void Add(T item)
{
AddToBack(item);
}
/// <summary>
/// Adds a collection of items to the back of the Deque. The indices of all existing items
/// in the Deque are unchanged. The last item in the added collection becomes the
/// last item in the Deque.
/// </summary>
/// <remarks>This method takes time O(M), where M is the number of items in the
/// <paramref name="collection"/>.</remarks>
/// <param name="collection">The collection of item to add.</param>
public void AddManyToBack(IEnumerable<T> collection)
{
if (collection == null)
throw new ArgumentNullException("collection");
foreach (T item in collection)
AddToBack(item);
}
/// <summary>
/// Removes an item from the front of the Deque. The indices of all existing items
/// in the Deque are decreased by 1. This method is
/// equivalent to <c>RemoveAt(0)</c> but is a little more
/// efficient.
/// </summary>
/// <remarks>Removing an item from the front of the Deque takes
/// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
/// <returns>The item that was removed.</returns>
/// <exception cref="InvalidOperationException">The Deque is empty.</exception>
public T RemoveFromFront()
{
if (start == end)
throw new InvalidOperationException(Strings.CollectionIsEmpty);
StopEnumerations();
T item = buffer[start];
buffer[start] = default(T);
if (++start >= buffer.Length)
start -= buffer.Length;
return item;
}
/// <summary>
/// Removes an item from the back of the Deque. The indices of all existing items
/// in the Deque are unchanged. This method is
/// equivalent to <c>RemoveAt(Count-1)</c> but is a little more
/// efficient.
/// </summary>
/// <remarks>Removing an item from the back of the Deque takes
/// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
/// <exception cref="InvalidOperationException">The Deque is empty.</exception>
public T RemoveFromBack()
{
if (start == end)
throw new InvalidOperationException(Strings.CollectionIsEmpty);
StopEnumerations();
if (--end < 0)
end += buffer.Length;
T item = buffer[end];
buffer[end] = default(T);
return item;
}
/// <summary>
/// Retreives the item currently at the front of the Deque. The Deque is
/// unchanged. This method is
/// equivalent to <c>deque[0]</c> (except that a different exception is thrown).
/// </summary>
/// <remarks>Retreiving the item at the front of the Deque takes
/// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
/// <returns>The item at the front of the Deque.</returns>
/// <exception cref="InvalidOperationException">The Deque is empty.</exception>
public T GetAtFront()
{
if (start == end)
throw new InvalidOperationException(Strings.CollectionIsEmpty);
return buffer[start];
}
/// <summary>
/// Retreives the item currently at the back of the Deque. The Deque is
/// unchanged. This method is
/// equivalent to <c>deque[deque.Count - 1]</c> (except that a different exception is thrown).
/// </summary>
/// <remarks>Retreiving the item at the back of the Deque takes
/// a small constant amount of time, regardless of how many items are in the Deque.</remarks>
/// <returns>The item at the back of the Deque.</returns>
/// <exception cref="InvalidOperationException">The Deque is empty.</exception>
public T GetAtBack()
{
if (start == end)
throw new InvalidOperationException(Strings.CollectionIsEmpty);
if (end == 0)
return buffer[buffer.Length - 1];
else
return buffer[end - 1];
}
/// <summary>
/// Creates a new Deque that is a copy of this one.
/// </summary>
/// <remarks>Copying a Deque takes O(N) time, where N is the number of items in this Deque..</remarks>
/// <returns>A copy of the current deque.</returns>
public Deque<T> Clone()
{
return new Deque<T>(this);
}
/// <summary>
/// Creates a new Deque that is a copy of this one.
/// </summary>
/// <remarks>Copying a Deque takes O(N) time, where N is the number of items in this Deque..</remarks>
/// <returns>A copy of the current deque.</returns>
object ICloneable.Clone()
{
return this.Clone();
}
/// <summary>
/// Makes a deep clone of this Deque. A new Deque is created with a clone of
/// each element of this set, by calling ICloneable.Clone on each element. If T is
/// a value type, then each element is copied as if by simple assignment.
/// </summary>
/// <remarks><para>If T is a reference type, it must implement
/// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
/// <para>Cloning the Deque takes time O(N), where N is the number of items in the Deque.</para></remarks>
/// <returns>The cloned Deque.</returns>
/// <exception cref="InvalidOperationException">T is a reference type that does not implement ICloneable.</exception>
public Deque<T> CloneContents()
{
bool itemIsValueType;
if (!Util.IsCloneableType(typeof(T), out itemIsValueType))
throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, typeof(T).FullName));
Deque<T> clone = new Deque<T>();
// Clone each item, and add it to the new ordered set.
foreach (T item in this) {
T itemClone;
if (itemIsValueType)
itemClone = item;
else {
if (item == null)
itemClone = default(T); // Really null, because we know T is a reference type
else
itemClone = (T)(((ICloneable)item).Clone());
}
clone.AddToBack(itemClone);
}
return clone;
}
#if DEBUG
/// <summary>
/// Print out the internal state of the Deque for debugging.
/// </summary>
internal void Print()
{
Console.WriteLine("length={0} start={1} end={2}", buffer.Length, start, end);
for (int i = 0; i < buffer.Length; ++i) {
if (i == start)
Console.Write("start-> ");
else
Console.Write(" ");
if (i == end)
Console.Write("end-> ");
else
Console.Write(" ");
Console.WriteLine("{0,4} {1}", i, buffer[i]);
}
Console.WriteLine();
}
#endif // DEBUG
}
}
Submit an article or tip