I followed the directions given in this question (the answer by Jason) in order to write my PriorityQueue<T> using a SortedList. I understand that the count field within this class is used to ensure unique priorities and to preserve the enqueue order among the same priority.
However, when count reaches its maximum value and I sum 1 to it, the latter will starts again from 0, so the priority of the subsequent items would be higher than the priority of the previous items. Using this approach I could need for a way to "securely" reset the counter count... In fact, suppose to have the following queue state (in the format priority | count | item):
0 | 123 | A
0 | 345 | B
1 | 234 | C
2 | 200 | D
Now suppose the counter limit has reached, so I have to reset it to 0: as a consequence, the next inserted item will have counter 0: for example, if I insert an element with priority equal to 1, it will be wrongly inserted before 1 | 234 | D
0 | 123 | A
0 | 345 | B
1 | 000 | new element
1 | 234 | C
2 | 200 | D
The problem of the priority can be solved by implementing an heap: I created an Heap class, then I used Heap<KeyValuePair<TPriority, TElement> and a custom PriorityComparer in order to sort elements by TPriority.
Given TPriority as an int and TElement as a string, the PriorityComparer is as follows:
public class MyComparer : IComparer<KeyValuePair<int, string>>
{
public int Compare(KeyValuePair<int, string> x, KeyValuePair<int, string> y)
{
return x.Key.CompareTo(y.Key);
}
}
...
int capacity = 10;
Heap<KeyValuePair<int, string>> queue;
queue = new Heap<KeyValuePair<int, string>>(capacity, new PriorityComparer());
...
UPDATE
In this way (using the PriorityComparer), I have succeeded to implement a priority queue.
Now I'd like to add support to modify its behavior at runtime, ie switch from FIFO to priority sorting and vice-versa. Since my implementation of priority queue has an IComparer field, I think it is sufficient to add a Comparer property to edit this field, like as follows:
public IComparer
{
set
{
this._comparer = value;
}
}
In the meantime I thought I'd take a different approach: instead of using a binary heap to manage priorities, I could wrap different queues (each queue refers to a given priority) as follows.
public class PriorityQueue<T, int>
{
private Queue<T> _defaultQueue;
private bool _priority;
private SortedList<int, Queue<T>> _priorityQueues;
public PriorityQueue(int capacity)
{
this._defaultQueue = new Queue<T>(capacity);
this._priority = false;
this._priorityQueues = new SortedList<int, Queue<T>>(0);
}
public void PriorityEnable()
{
this._priority = true;
}
public void PriorityDisable()
{
this._priority = false;
}
public void Enqueue(T item)
{
if (this._priority)
{
// enqueue to one of the queues
// with associated priority
// ...
}
else this._defaultQueue.Enqueue(item);
}
public T Dequeue()
{
if (this._priority)
{
// dequeue from one of the queues
// with associated priority and
// return
// ...
}
return this._defaultQueue.Dequeue();
}
}
- How to manage the transition from FIFO mode to priority mode when there are still elements in the default queue? I could copy them in the priority queues based on the item priority... Other better solutions?
- How to manage the transition from priority mode to FIFO mode? In this case, I would have several priority queues, which may contain elements, but no longer have to manage them according to priority and not even know the original order of arrival...
- How can I manage the capacity of the different queues?
- What about the performances of the above two solutions? Which does use more memory?
