priorityqueue.h
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
This file is part of the documentation for lib Library Version 1.4.2.