C sharp:DequeOfT
From GPWiki
Note: The correct name of this page is C#:Deque<T>; however, due to technical restrictions it is represented as C_sharp:DequeOfT instead.
The folllowing code is a C# implementation of a generic double-ended queue (or deque). Implements ICollection<T> and IEnumerable<T> so you can use the foreach keyword to iterate through the items. Has operations AddToHead, AddToTail, RemoveFromHead, RemoveFromTail, PeekHead, PeakTail.
Code
using System;
using System.Collections.Generic;
namespace GPWiki {
/// <summary>
/// A double-ended queue. Provides fast insertion and removal from the head or tail end,
/// and fast indexed access.
/// </summary>
/// <typeparam name="T">The type of item to store in the deque.</typeparam>
public class Deque<T> : IList<T>
{
//Constants
private const int Min_Capacity = 4;
//Fields
private int _head = 0;
private int _capacity = Min_Capacity;
private int _count;
private T[] _data;
/// <summary>
/// Gets the number of items in the deque.
/// </summary>
public int Count
{
get { return _count; }
}
/// <summary>
/// Gets or sets the capacity of the deque. If the count exceeds the
/// capacity, the capacity will be automatically increased.
/// </summary>
public int Capacity
{
get { return _capacity; }
set
{
int newCapacity = Math.Max(value, Math.Max(_count, Min_Capacity));
T[] temp = new T[newCapacity];
int length = Math.Min(_capacity - _head, _count);
Array.Copy(_data, _head, temp, 0, length);
Array.Copy(_data, 0, temp, length, _count - length);
_data = temp;
_head = 0;
_capacity = newCapacity;
}
}
/// <summary>
/// Creates a new deque.
/// </summary>
public Deque()
{
_data = new T[_capacity];
}
/// <summary>
/// Creates a new deque.
/// </summary>
/// <param name="capacity">The initial capacity to give the deque.</param>
public Deque(int capacity)
{
_capacity = capacity;
_data = new T[_capacity];
}
/// <summary>
/// Creates a new deque from a collection.
/// </summary>
/// <param name="items">A collection of items of type T.</param>
public Deque(ICollection<T> items)
{
Capacity = items.Count;
foreach (T item in items)
{
this.Add(item);
}
}
private int Tail
{
get { return (_head + _count) % _capacity; }
}
//Increments (and wraps if necessary) an index
private int Increment(int index)
{
return (index + 1) % _capacity;
}
//Decrements (and wraps if necessary) an index
private int Decrement(int index)
{
return (index + _capacity - 1) % _capacity;
}
/// <summary>
/// Adds an item to the tail end of the deque.
/// </summary>
/// <param name="item">The item to be added.</param>
public void AddToTail(T item)
{
if (_count + 1> _capacity) Capacity *= 2;
_data[Tail] = item;
_count++;
}
/// <summary>
/// Removes an item from the tail of the deque.
/// </summary>
/// <returns>An item of type T.</returns>
public T RemoveFromTail()
{
if (_count < 0)
{
throw new InvalidOperationException("Deque is empty.");
}
T item = _data[Tail];
_data[Tail] = default(T);
_count--;
return item;
}
/// <summary>
/// Adds an item to the head of the deque.
/// </summary>
/// <param name="item">The item to be added.</param>
public void AddToHead(T item)
{
_count++;
if (_count > _capacity) Capacity *= 2;
if (_count > 1) _head = Decrement(_head);
_data[_head] = item;
}
/// <summary>
/// Removes an item from the head of the deque.
/// </summary>
/// <returns>An item of type T.</returns>
public T RemoveFromHead()
{
_count--;
if (_count < 0)
{
throw new InvalidOperationException("Deque is empty.");
}
T item = _data[_head];
_data[_head] = default(T);
_head = Increment(_head);
return item;
}
/// <summary>
/// Gets the item at the head of the deque.
/// </summary>
/// <returns>An item of type T.</returns>
public T PeekHead()
{
return _data[_head];
}
/// <summary>
/// Gets the item at the tail of the deque.
/// </summary>
/// <returns>An item of type T.</returns>
public T PeekTail()
{
return _data[Tail];
}
/// <summary>
/// Gets the item at the specified position.
/// </summary>
/// <param name="position">The position of the item to return.</param>
/// <returns>An item of type T.</returns>
public T this[int position]
{
get
{
if (position >= _count || position < 0) throw new ArgumentOutOfRangeException("position");
return _data[(_head + position) % _capacity];
}
set
{
if (position >= _count || position < 0) throw new ArgumentOutOfRangeException("position");
_data[(_head + position) % _capacity] = value;
}
}
/// <summary>
/// Creates an array of the items in the deque.
/// </summary>
/// <returns>An array of type T.</returns>
public T[] ToArray()
{
T[] array = new T[_count];
CopyTo(array, 0);
return array;
}
/// <summary>
/// Copies the deque to an array at the specified index.
/// </summary>
/// <param name="array">One dimensional array that is the destination of the copied elements.</param>
/// <param name="arrayIndex">The zero-based index at which copying begins.</param>
public void CopyTo(T[] array, int arrayIndex)
{
if (_count == 0) return;
int length = Math.Min(_capacity - _head, _count);
Array.Copy(_data, _head, array, 0, length);
Array.Copy(_data, 0, array, length, _count - length);
}
/// <summary>
/// Gets and removes an item at the specified index.
/// </summary>
/// <param name="index">The index at which to remove the item.</param>
/// <returns>An item of type T.</returns>
public T RemoveAt(int index)
{
if (index >= _count) throw new ArgumentOutOfRangeException("index");
int i = (_head + index) % _capacity;
T item = _data[i];
if (i < _head)
{
Array.Copy(_data, i + 1, _data, i, Tail - i);
_data[Tail] = default(T);
}
else
{
Array.Copy(_data, _head, _data, _head + 1, i - _head);
_data[_head] = default(T);
_head = Increment(_head);
}
_count--;
return item;
}
/// <summary>
/// Clears all items from the deque.
/// </summary>
public void Clear()
{
Array.Clear(_data, 0, _capacity);
_head = 0;
_count = 0;
}
/// <summary>
/// Gets an enumerator for the deque.
/// </summary>
/// <returns>An IEnumerator of type T.</returns>
public System.Collections.Generic.IEnumerator<T> GetEnumerator()
{
for (int i = 0; i < _count; i++)
{
yield return this[i];
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
/// <summary>
/// Adds an item to the tail of the deque.
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
AddToTail(item);
}
/// <summary>
/// Checks to see if the deque contains the specified item.
/// </summary>
/// <param name="item">The item to search the deque for.</param>
/// <returns>A boolean, true if deque contains item.</returns>
public bool Contains(T item)
{
for (int i = 0; i < this.Count; i++)
{
if (this[i].Equals(item))
{
return true;
}
}
return false;
}
/// <summary>
/// Gets whether or not the deque is readonly.
/// </summary>
public bool IsReadOnly
{
get { return false; }
}
/// <summary>
/// Removes an item from the deque.
/// </summary>
/// <param name="item">The item to be removed.</param>
/// <returns>Boolean true if the item was removed.</returns>
public bool Remove(T item)
{
for (int i = 0; i < this.Count; i++)
{
if (this[i].Equals(item))
{
RemoveAt(i);
return true;
}
}
return false;
}
/// <summary>
/// Gets the first index of an item in the list.
/// </summary>
/// <param name="item">The item to locate.</param>
/// <returns>The integer index of the item.</returns>
public int IndexOf(T item)
{
for (int i = 0; i < this.Count; i++)
{
if (this[i].Equals(item))
{
return i;
}
}
throw new InvalidOperationException("Item not found.");
}
/// <summary>
/// Inserts an item at the specified index.
/// </summary>
/// <param name="index">The index at which to insert the item.</param>
/// <param name="item">The item to insert.</param>
public void Insert(int index, T item)
{
if (index > _count || index < 0) throw new ArgumentOutOfRangeException("index");
_count++;
if (_count > _capacity) Capacity *= 2;
int split = _capacity - _head;
int i = (_head + index) % _capacity;
if (index < split)
{
Array.Copy(_data, i, _data, i + 1, _count - index);
}
else
{
Array.Copy(_data, _head, _data, _head - 1, index);
}
_data[i] = item;
}
void IList<T>.RemoveAt(int index)
{
RemoveAt(index);
}
}
}
Usage
Using the deque is simple. Just add and removes items from either end. Or you can access items by index.
Deque<int> deque = new Deque<int>();
deque.AddToTail(1);
deque.AddToTail(2);
deque.AddToTail(3);
deque.AddToTail(4);
deque.AddToTail(5);
deque.AddToTail(6);
deque.AddToTail(7);
int index3 = deque[3]; // return the item at index 3 in the deque. (i.e "4")
int last = deque.RemoveFromTail(); //remove and return the item at the tail of list. (i.e "7")
int first = deque.RemoveFromHead(); //remove and return the item at the head of the list (i.e. "1")
//deque will now contain 2,3,4,5,6
