00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
#ifndef priority_queue_h
00020
#define priority_queue_h
00021
00022
#include <vector>
00023
#include <qstring.h>
00024
#include <qasciidict.h>
00025
#include <kdebug.h>
00026
00027
00028
00029
namespace KOffice {
00030
00057 template<
class T>
class PriorityQueue {
00058
00059
public:
00060
PriorityQueue() {}
00061
PriorityQueue(
const PriorityQueue<T>& rhs ) : m_vector( rhs.
m_vector ) {}
00062
PriorityQueue(
const QAsciiDict<T>& items );
00063 ~
PriorityQueue() {}
00064
00065
PriorityQueue<T> &operator=(
const PriorityQueue<T>& rhs ) { m_vector = rhs.
m_vector;
return *
this; }
00066
bool operator==(
const PriorityQueue<T>& rhs ) {
return m_vector == rhs.
m_vector; }
00067
00068
unsigned int count()
const {
return m_vector.size(); }
00069
bool isEmpty()
const {
return m_vector.empty(); }
00070
00071
void insert( T* item );
00072
00078
void keyDecreased( T* item );
00079
00080 T* extractMinimum();
00081
00085
void dump()
const;
00086
00087
private:
00088
00089
int parent(
int i ) {
return ( ( i + 1 ) >> 1 ) - 1; }
00090
int left(
int i ) {
return ( ( i + 1 ) << 1 ) - 1; }
00091
int right(
int i ) {
return ( i + 1 ) << 1; }
00092
00093
void heapify(
int i );
00094
00095
void bubbleUp( T* item,
int i );
00096
00097
void buildHeap();
00098
00099 std::vector<T*> m_vector;
00100 };
00101
00102
template<
class T>
00103
PriorityQueue<T>::PriorityQueue(
const QAsciiDict<T>& items ) : m_vector( items.count() )
00104 {
00105
00106
QAsciiDictIterator<T> it( items );
00107
for (
int i = 0; it.current(); ++it, ++i ) {
00108 it.current()->setIndex( i );
00109 m_vector[ i ] = it.current();
00110 }
00111
00112 buildHeap();
00113 }
00114
00115
template<
class T>
00116
void PriorityQueue<T>::insert( T* item )
00117 {
00118
if ( !item )
00119
return;
00120
int i = static_cast<int>( m_vector.size() );
00121 m_vector.push_back( 0 );
00122 bubbleUp( item, i );
00123 }
00124
00125
template<
class T>
00126 void PriorityQueue<T>::keyDecreased( T* item )
00127 {
00128
if ( !item )
00129
return;
00130 bubbleUp( item, item->index() );
00131 }
00132
00133
template<
class T>
00134 T*
PriorityQueue<T>::extractMinimum()
00135 {
00136
if ( m_vector.size() < 1 )
00137
return 0;
00138 T *min = m_vector[ 0 ];
00139 m_vector[ 0 ] = m_vector[ m_vector.size() - 1 ];
00140
00141 m_vector[ 0 ]->setIndex( 0 );
00142 m_vector.pop_back();
00143 heapify( 0 );
00144
return min;
00145 }
00146
00147
template<
class T>
00148 void PriorityQueue<T>::dump()
const
00149
{
00150 kdDebug( 30500 ) <<
"++++++++++ PriorityQueue::dump ++++++++++" << endl;
00151
QString out;
00152
int size = static_cast<int>( m_vector.size() );
00153
for (
int i = 0; i < size; ++i ) {
00154
if ( m_vector[ i ]->index() != i )
00155 out +=
" ERROR: index out of sync. Should be " + QString::number( i ) +
", is " +
00156 QString::number( m_vector[ i ]->index() ) +
". ";
00157 out += QString::number( m_vector[ i ]->key() );
00158 out +=
", ";
00159 }
00160
if ( out.isEmpty() )
00161 out =
"(empty)";
00162 kdDebug( 30500 ) << out << endl;
00163 kdDebug( 30500 ) <<
"++++++++++ PriorityQueue::dump (done) ++++++++++" << endl;
00164 }
00165
00166
template<
class T>
00167
void PriorityQueue<T>::heapify(
int i )
00168 {
00169
int l = left( i ), r = right( i ), size = static_cast<int>( m_vector.size() );
00170
int smallest;
00171
00172
if ( l < size && m_vector[ l ]->key() < m_vector[ i ]->key() )
00173 smallest = l;
00174
else
00175 smallest = i;
00176
if ( r < size && m_vector[ r ]->key() < m_vector[ smallest ]->key() )
00177 smallest = r;
00178
00179
if ( smallest != i ) {
00180 T* tmp = m_vector[ i ];
00181 m_vector[ i ] = m_vector[ smallest ];
00182
00183 m_vector[ i ]->setIndex( i );
00184 tmp->setIndex( smallest );
00185 m_vector[ smallest ] = tmp;
00186 heapify( smallest );
00187 }
00188 }
00189
00190
template<
class T>
00191
void PriorityQueue<T>::bubbleUp( T* item,
int i )
00192 {
00193
int p = parent( i );
00194
while ( i > 0 && m_vector[ p ]->key() > item->key() ) {
00195
00196 m_vector[ p ]->setIndex( i );
00197
00198 m_vector[ i ] = m_vector[ p ];
00199 i = p;
00200 p = parent( i );
00201 }
00202 item->setIndex( i );
00203 m_vector[ i ] = item;
00204 }
00205
00206
template<
class T>
00207
void PriorityQueue<T>::buildHeap()
00208 {
00209
00210
for (
int i = ( m_vector.size() >> 1 ) - 1; i >= 0; --i )
00211 heapify( i );
00212 }
00213
00214 }
00215
00216
#endif // priority_queue_h