C# Deque found on the web--thanks to The Game Programming Wiki

  • Thread starter Thread starter raylopez99
  • Start date Start date
R

raylopez99

One thing I like about C# / Csharp is that it's a "popular" language
so you have good samaritans like the one below who post code to be
freely used. For example, I could not find a deque in the C#/Csharp
generic library (just a stack), but I found one on the web, at the
cite below.

Deques are sometimes superior to stacks because you can pop an object
from the top, which is useful when you are iteratively traversing a
tree 'breadth wise' rather than 'depth wise' (when you would use a
stack instead).

I checked this code out and it works fine. You can also "step
through" the deque, peeking at the objects in the deque, since it's a
member of ICollection, as follows (given the below example):

int icountdeque_ = 0;
foreach (Object obj in deque) {
Console.Write(" peaking @ deque: {0}", (int)obj); //
write to screen
icountdeque_++; //tracks how many deque objects there
are, useful for loops
}

RL

Code reproduced below for future reference in case the Game
Programming Wiki somehow closes...

http://www.gpwiki.org/index.php?title=C_sharp:DequeOfT

//
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> : ICollection<T>
{
//Constants
private const int MIN_CAPACITY = 4;
//Fields
private int _capacity = MIN_CAPACITY;
private int _head = 0;
private int _tail = 0;
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 previousCapacity = _capacity;
_capacity = Math.Max(value, Math.Max(_count,
MIN_CAPACITY));
T[] temp = new T[_capacity];
if (_tail > _head)
{
Array.Copy(_data, _head, temp, 0, _tail + 1 -
_head);
_tail -= _head;
_head = 0;
}
else
{
Array.Copy(_data, 0, temp, 0, _tail + 1);
int length = previousCapacity - _head;
Array.Copy(_data, _head, temp, _capacity - length,
length);
_head = _capacity - length;
}
_data = temp;
}
}
/// <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="collection">A collection of items of type T.</
param>
public Deque(ICollection<T> collection)
{
Capacity = collection.Count;
foreach (T item in collection)
{
this.Add(item);
}
}
//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)
{
_count++;
if (_count > _capacity) Capacity *= 2;
if (_count > 1) _tail = Increment(_tail);
_data[_tail] = item;
}
/// <summary>
/// Removes an item from the tail of the deque.
/// </summary>
/// <returns>An item of type T.</returns>
public T RemoveFromTail()
{
_count--;
if (_count < 0)
{
throw new
InvalidOperationException("DequeEmptyException");
}
T item = _data[_tail];
_data[_tail] = default(T);
_tail = Decrement(_tail);
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("DequeEmptyException");
}
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) throw new
ArgumentOutOfRangeException("position");
return _data[(_head + position) % _capacity];
}
}
/// <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;
if (_head < _tail)
{
Array.Copy(_data, _head, array, arrayIndex, _tail + 1
- _head);
}
else
{
int headLength = _capacity - _head;
Array.Copy(_data, _head, array, arrayIndex,
headLength);
Array.Copy(_data, 0, array, arrayIndex + headLength,
_tail + 1);
}
}
/// <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)
{
_count--;
if (index >= _count) throw new
ArgumentOutOfRangeException("index");
int i = (_head + index) % _capacity;
T item = _data;
if (i < _head)
{
Array.Copy(_data, i + 1, _data, i, _tail - i);
_data[_tail] = default(T);
_tail = Decrement(_tail);
}
else
{
Array.Copy(_data, _head, _data, _head + 1, i - _head);
_data[_head] = default(T);
_head = Increment(_head);
}
return item;
}
/// <summary>
/// Clears all items from the deque.
/// </summary>
public void Clear()
{
Array.Clear(_data, 0, _capacity);
_head = 0;
_tail = 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;
}
}
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.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.Equals(item))
{
RemoveAt(i);
return true;
}
}
return false;
}
}
}
//

/*
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



*/
 
I'm probably missing something that you are requiring, but it would seem that
System.Collections.Generic.Queue does most of what you are looking for in a
class.
 
ModelBuilder said:
I'm probably missing something that you are requiring, but it would seem that
System.Collections.Generic.Queue does most of what you are looking for in a
class.
Click to expand...

Queue only lets you take from the front, not the front *or* back.

I've got a RandomAccessQueue class which is somewhat similar, but not
quite the same.
 
ModelBuilder said:
I'm probably missing something that you are requiring, but it would seem that
System.Collections.Generic.Queue does most of what you are looking for in a
class.
Click to expand...

And even uses the "proper" name for the data structure: "queue". :)

The one thing you can't do with a Queue<> is look at any element other
than the next one to be dequeued. You can peek at that element without
removing it, but you can't look at any other. The posted class offers
more inspection mechanisms than .NET's queue classes.

However, I'd argue that if you find yourself needing to look at an
element other than the first one, then your design isn't really using a
queue, and thus a queue data structure is the wrong one to use (use a
LinkedList<> instead, for example, which also allows easy removal from
front, removal from back, and inspection of all elements within).

So, yes...if one finds themselves needing a queue, I agree that the
Queue<> class, which already exists in .NET, is the correct one to use
(or if pre-.NET 2.0, the non-generic System.Collections.Queue class)

Pete
 
OK, I get it now. I haven't tried to use a Queue in a non-queue way. Thanks
for clarifying!
 
Peter Duniho said:
And even uses the "proper" name for the data structure: "queue". :)

The one thing you can't do with a Queue<> is look at any element other
than the next one to be dequeued. You can peek at that element without
removing it, but you can't look at any other. The posted class offers
more inspection mechanisms than .NET's queue classes.

However, I'd argue that if you find yourself needing to look at an
element other than the first one, then your design isn't really using a
queue, and thus a queue data structure is the wrong one to use (use a
LinkedList<> instead, for example, which also allows easy removal from
front, removal from back, and inspection of all elements within).

So, yes...if one finds themselves needing a queue, I agree that the
Queue<> class, which already exists in .NET, is the correct one to use
(or if pre-.NET 2.0, the non-generic System.Collections.Queue class)
Click to expand...

Let me give the example of my own use of RandomAccessQueue, which sort
of explains its purpose.

I have a thread-pool. You can add items to the work queue of a thread-
pool, and normally that work queue is viewed as a perfectly normal
queue. However, sometimes I also need to insert items into the queue,
if a priority is specified - items with a higher priority need to get
executed first.

I *could* have used LinkedList for this (except that I originally wrote
it before 2.0, of course) but it feels more like a "queue with
occasional random access" than a normal linked list. (Finding the right
point to insert a new item is also quicker this way than with a linked
list.)
 
Jon said:
[...]
I *could* have used LinkedList for this (except that I originally wrote
it before 2.0, of course) but it feels more like a "queue with
occasional random access" than a normal linked list. (Finding the right
point to insert a new item is also quicker this way than with a linked
list.)
Click to expand...

Well, you are free to call it a queue, of course. But it's not really a
queue, at least not a pure one. :)

I'm curious what it is about your implementation that makes insertion of
new items faster than if using a linked list?

Pete
 
Peter Duniho said:
Jon said:
[...]
I *could* have used LinkedList for this (except that I originally wrote
it before 2.0, of course) but it feels more like a "queue with
occasional random access" than a normal linked list. (Finding the right
point to insert a new item is also quicker this way than with a linked
list.)
Click to expand...

Well, you are free to call it a queue, of course. But it's not really a
queue, at least not a pure one. :)

I'm curious what it is about your implementation that makes insertion of
new items faster than if using a linked list?
Click to expand...

The queue is ordered by priority, so it can use a binary search to find
the correct insertion point. Binary search on a linked list isn't
terribly fast :)

Admittedly it won't matter unless you've got thousands of items on the
queue...
 
Jon said:
The queue is ordered by priority, so it can use a binary search to find
the correct insertion point. Binary search on a linked list isn't
terribly fast :)
Click to expand...

Well, not on an actual linked list. On a SortedList, it'd be fast, but
then you have problems with insertions and removals and keeping the tree
balanced, that sort of thing.
Admittedly it won't matter unless you've got thousands of items on the
queue...
Click to expand...

Nope. And I'd suggest that a more traditional approach, maintaining an
ordered list of queues would work fine too (assuming that for a given
priority, tasks are still FIFO). The ordered list could be a SortedList
if one wants, but I think a regular list (linked or otherwise)
maintained by insertion sort would be fine, given that the number of
unique priorities is likely to be low.

You could have your queues and eat them too. :)

Pete
 
I'm probably missing something that you are requiring, but it would seem that
System.Collections.Generic.Queue does most of what you are looking for in a
class.
Click to expand...

Thanks ModelBuilder. I did not realize that a generic "Queue" class
existed (and I even searched for it in the massive Help file of Visual
Studio--maybe I misspelled it).

I like the generic Queue better since it's authorized. The deque
posted originally seems to work, but I've noticed the "Count" function
seems to be off by one when storing user defined classes (it seems--
I've not really checked it, but that seemed to be the case in a demo
program I wrote), but in any event it's not a big deal since you can
iterrate in the deque class much safer using IEnumerable/IEnumerator,
which works fine as far as I can tell.

RL
 
Back
Top