C sharp:DequeOfT

From GPWiki
Jump to: navigation, search

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