Wednesday, September 15, 2010

Simple priority queue with Qt

Recently in one of my Qt project I required to use priority queue and found that Qt framework dose not provide such container. Then I decided to write one my self.

Following is simple version of my actual implementation.

In code Queue class implement simple priority queue. Internally I am using QQueue as storage and created one helper structure which holds data and its priority. Actual work is done inside enqueue method, which check priority of item being inserted with other stored items and insert item at appropriate index.
#ifndef QUEUE_H
#define QUEUE_H

#include <QQueue>
#include <QDebug>

enum Priority {
    Normal = 0,
    High = 1
};

template<class T>
class Queue
{
public:

    Queue()
    {}

    void enqueue(Priority priority,T value)
    {
        Item<T> item(priority,value);
        for(int i = 0 ; i < _queue.count() ; ++i ) {
            const Item<T>& otherItem = _queue[i];
            if( priority > otherItem._priority )  {
                _queue.insert(i,item);
                return;
            }
        }
        _queue.append(item);
    }

    T dequeue()
    {
        const Item<T>& item = _queue.dequeue();
        return item._value;
    }

    int count()
    {
        return _queue.count();
    }

private:

    template<class C>
    struct Item
    {
        Priority _priority;
        C _value;

        Item(Priority priority, C value)
        {
            _priority = priority;
            _value = value;
        }
    };

    QQueue< Item<T > > _queue;

};

#endif // QUEUE_H

Some basic test code.
{
    //testing with int as value
    Queue<int> q;
    q.enqueue(High,1);
    q.enqueue(Normal,2);
    q.enqueue(High,3);
    q.enqueue(Normal,5);
    q.enqueue(Normal,6);
    q.enqueue(High,4);

    //output should be 1,3,4,2,5,6
    while( q.count() > 0 )
    {
        qDebug() << q.dequeue();
    }
}

3 comments:

  1. Thanx for snippet.

    1. Have you considered QPair instead of your Item?
    2. Have you considered QMultiMap instead of QQueue? Multimap sould provide better performance than QQueue, but items with same priority will be reversed if we do nothing with it.

    ReplyDelete
  2. Thanks for suggestion, true, my mind skipped QMultiMap. I don't know about performance much, but I could have implemented priority queue with multimap also.

    ReplyDelete
  3. FYI: Complexity algorithms used in Qt containers
    http://doc.qt.nokia.com/latest/containers.html#algorithmic-complexity

    You may be already know this: "...If there are multiple items for key in the map, the value of the most recently inserted one is returned..." (From Qt QMap::value reference.) So same priority tasks can be executed in backwards order.

    ReplyDelete