lib

KOffice::PriorityQueue< T > Class Template Reference

#include <priorityqueue.h>

List of all members.


Detailed Description

template<class T>
class KOffice::PriorityQueue< T >

This PriorityQueue class is implemented as "upside down" heap, i.e.

the item with the smallest key is at the root of the heap. If you feel like using that class your template parameter has to have a public method "unsigned int key() const" which returns - surprise - the key. The supplied key must not be "negative." We use UINT_MAX as value to represent "infinity" for the shortest path algorithm. As this is a very specialized class we also demand a "void setIndex(int i)" method in order to tell nodes where they are located inside the heap. This is a very ugly approach, but it's the only way I see if you want to avoid a O(n) search for the item where you decreased the key :} Just to make it even worse we also use a "int index() const" method to fetch the index... well, you most likely would need one anyway ;) Note: This class is pointer based (like QPtr*) - if you create PriorityQueue<X> we actually operate on X* ! We don't care about deleting your pointers at all. We don't copy them, we don't create new ones,... - you own them, you have to delete them :)

In case you change a key value make sure to call keyDecreased and pass the item you touched. This is running in O(log n) according to Cormen...

All the ideas are stol^H^H^H^Hborrowed from "Introduction to Algorithms", Cormen et al

Author:
Werner Trobin <trobin@kde.org>

Definition at line 57 of file priorityqueue.h.


Public Member Functions

 PriorityQueue ()
 PriorityQueue (const PriorityQueue< T > &rhs)
 PriorityQueue (const QAsciiDict< T > &items)
 ~PriorityQueue ()
PriorityQueue< T > & operator= (const PriorityQueue< T > &rhs)
bool operator== (const PriorityQueue< T > &rhs)
unsigned int count () const
bool isEmpty () const
void insert (T *item)
void keyDecreased (T *item)
T * extractMinimum ()
void dump () const

Member Function Documentation

template<class T>
void KOffice::PriorityQueue< T >::dump (  )  const

For debugging.

Definition at line 148 of file priorityqueue.h.

template<class T>
void KOffice::PriorityQueue< T >::keyDecreased ( T *  item  ) 

Call this method after decreasing the key of the ith item.

The heap properties will no longer be valid if you either forget to call that method, or if you increase the key.

Definition at line 126 of file priorityqueue.h.


The documentation for this class was generated from the following file:
KDE Home | KDE Accessibility Home | Description of Access Keys