1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
/* This file is part of the KOffice libraries
Copyright (C) 2001 Werner Trobin <[email protected]>
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License version 2 as published by the Free Software Foundation.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Library General Public License for more details.
You should have received a copy of the GNU Library General Public License
along with this library; see the file COPYING.LIB. If not, write to
the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*/
#ifndef priority_queue_h
#define priority_queue_h
#include <vector>
#include <tqstring.h>
#include <tqasciidict.h>
#include <kdebug.h>
// Better put all those internal classes in some namespace to avoid clashes
// as the names are quite generic
namespace KOffice {
/**
* This PriorityQueue class is implemented as "upside down" heap, i.e. the item
* with the \b 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 TQPtr*) - 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 <[email protected]>
*/
template<class T> class PriorityQueue {
public:
PriorityQueue() {}
PriorityQueue( const PriorityQueue<T>& rhs ) : m_vector( rhs.m_vector ) {}
PriorityQueue( const TQAsciiDict<T>& items );
~PriorityQueue() {}
PriorityQueue<T> &operator=( const PriorityQueue<T>& rhs ) { m_vector = rhs.m_vector; return *this; }
bool operator==( const PriorityQueue<T>& rhs ) { return m_vector == rhs.m_vector; }
unsigned int count() const { return m_vector.size(); }
bool isEmpty() const { return m_vector.empty(); }
void insert( 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 \b increase the key.
*/
void keyDecreased( T* item );
T* extractMinimum();
/**
* For debugging
*/
void dump() const;
private:
// Note: We have to use a 1-based index here, and we get/return 0-based ones
int parent( int i ) { return ( ( i + 1 ) >> 1 ) - 1; }
int left( int i ) { return ( ( i + 1 ) << 1 ) - 1; }
int right( int i ) { return ( i + 1 ) << 1; }
void heapify( int i );
// item is !=0 for sure
void bubbleUp( T* item, int i );
// Builds the heap in the vector in O(n)
void buildHeap();
std::vector<T*> m_vector;
};
template<class T>
PriorityQueue<T>::PriorityQueue( const TQAsciiDict<T>& items ) : m_vector( items.count() )
{
// First put all items into the vector
TQAsciiDictIterator<T> it( items );
for ( int i = 0; it.current(); ++it, ++i ) {
it.current()->setIndex( i );
m_vector[ i ] = it.current();
}
// Then build a heap in that vector
buildHeap();
}
template<class T>
void PriorityQueue<T>::insert( T* item )
{
if ( !item )
return;
int i = static_cast<int>( m_vector.size() );
m_vector.push_back( 0 ); // extend the vector by one item. i == index to the last item
bubbleUp( item, i );
}
template<class T>
void PriorityQueue<T>::keyDecreased( T* item )
{
if ( !item )
return;
bubbleUp( item, item->index() );
}
template<class T>
T* PriorityQueue<T>::extractMinimum()
{
if ( m_vector.size() < 1 )
return 0;
T *min = m_vector[ 0 ];
m_vector[ 0 ] = m_vector[ m_vector.size() - 1 ];
// update the index
m_vector[ 0 ]->setIndex( 0 );
m_vector.pop_back();
heapify( 0 );
return min;
}
template<class T>
void PriorityQueue<T>::dump() const
{
kdDebug( 30500 ) << "++++++++++ PriorityQueue::dump ++++++++++" << endl;
TQString out;
int size = static_cast<int>( m_vector.size() );
for ( int i = 0; i < size; ++i ) {
if ( m_vector[ i ]->index() != i )
out += " ERROR: index out of sync. Should be " + TQString::number( i ) + ", is " +
TQString::number( m_vector[ i ]->index() ) + ". ";
out += TQString::number( m_vector[ i ]->key() );
out += ", ";
}
if ( out.isEmpty() )
out = "(empty)";
kdDebug( 30500 ) << out << endl;
kdDebug( 30500 ) << "++++++++++ PriorityQueue::dump (done) ++++++++++" << endl;
}
template<class T>
void PriorityQueue<T>::heapify( int i )
{
int l = left( i ), r = right( i ), size = static_cast<int>( m_vector.size() );
int smallest;
if ( l < size && m_vector[ l ]->key() < m_vector[ i ]->key() )
smallest = l;
else
smallest = i;
if ( r < size && m_vector[ r ]->key() < m_vector[ smallest ]->key() )
smallest = r;
if ( smallest != i ) {
T* tmp = m_vector[ i ];
m_vector[ i ] = m_vector[ smallest ];
// update indices
m_vector[ i ]->setIndex( i );
tmp->setIndex( smallest );
m_vector[ smallest ] = tmp;
heapify( smallest );
}
}
template<class T>
void PriorityQueue<T>::bubbleUp( T* item, int i )
{
int p = parent( i );
while ( i > 0 && m_vector[ p ]->key() > item->key() ) {
// update the index first
m_vector[ p ]->setIndex( i );
// then move it there
m_vector[ i ] = m_vector[ p ];
i = p;
p = parent( i );
}
item->setIndex( i );
m_vector[ i ] = item;
}
template<class T>
void PriorityQueue<T>::buildHeap()
{
// from size() / 2 down to 1
for ( int i = ( m_vector.size() >> 1 ) - 1; i >= 0; --i )
heapify( i );
}
} // namespace KOffice
#endif // priority_queue_h
|
