Ao.Collections

Ao.Collections

The Ao.Collections namespace contains two generic collection classes for double-ended queues and priority queues, respectively.

Double-Ended Queues

Just like the deque type in the C++ Standard Template Library, the Deque<T> class implements a double-ended queue that supports constant-time insertion and removal at either end.

Therefore, the Dequeu<T> class is internally based on a linked list.

var Q = new Deque<int>();

Push Back

Q.PushBack(1);
Q.PushBack(2);
Q.PushBack(3);

foreach (var x in Q)
{
    Console.WriteLine(x);
}

1
2
3

Push Front

Q.PushFront(4);
Q.PushFront(5);
Q.PushFront(6);

foreach (var x in Q)
{
    Console.WriteLine(x);
}

6
5
4
1
2
3

Pop Front

Q.PopFront();
Q.PopFront();

foreach (var x in Q)
{
    Console.WriteLine(x);
}

4
1
2
3

Pop Back

Q.PopBack();

foreach (var x in Q)
{
    Console.WriteLine(x);
}

4
1
2

Priority Queue

A priority queue is a widely used data structure, e.g. when dealing with a stream of incoming messages in such a way, that important messages are processed first.

The PriorityQueue<T> class is implemented as a minimum heap using a list for the items and a dictionary for the items’ indexes.

Push

var Q = new PriorityQueue<int>();

Q.Push(4);
Q.Push(2);
Q.Push(5);
Q.Push(1);
Q.Push(3);
Q.Push(6);

Console.WriteLine(Q.Peek());

1

Pop

Q.Pop();
Q.Pop();

Console.WriteLine(Q.Peek());

3

Priorities

In contrast to integers, other types’ priorities are not so obvious. When default-constructed, a priority queue will use a default comparer for comparisons.

public PriorityQueue() => Comparer = Comparer<T>.Default;

For custom value types or reference types, this most probably won’t do very well. Then, a custom comparer should be provided.

public class Message
{
    public DateTime Time { get; set; }

    public string Sender { get; set; }
}

public class MessageComparer : Comparer<Message>
{
    public override int Compare(Message x, Message y) => x.Time.CompareTo(y.Time);
}

var C = new MessageComparer();

var Q = new PriorityQueue<Message>(C);