← Back to branch summary

~ubuntu-branches/debian/experimental/inkscape/experimental

« back to all changes in this revision

Viewing changes to src/libvpsc/pairingheap/PairingHeap.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Thomas Viehmann
  • Date: 2008-09-09 23:29:02 UTC
  • mfrom: (1.1.7 upstream)
  • Revision ID: james.westby@ubuntu.com-20080909232902-c50iujhk1w79u8e7
Tags: 0.46-2.1
http://bugs.debian.org/487623
* Non-maintainer upload.
* Add upstream patch fixing a crash in the open dialog
  in the zh_CN.utf8 locale. Closes: #487623.
  Thanks to Luca Bruno for the patch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libvpsc/pairingheap/PairingHeap.cpp
 
1
/**
 
2
 * \brief Pairing heap datastructure implementation
 
3
 *
 
4
 * Based on example code in "Data structures and Algorithm Analysis in C++"
 
5
 * by Mark Allen Weiss, used and released under the LGPL by permission
 
6
 * of the author.
 
7
 *
 
8
 * No promises about correctness.  Use at your own risk!
 
9
 *
 
10
 * Authors:
 
11
 *   Mark Allen Weiss
 
12
 *   Tim Dwyer <tgdwyer@gmail.com>
 
13
 *
 
14
 * Copyright (C) 2005 Authors
 
15
 *
 
16
 * Released under GNU LGPL.  Read the file 'COPYING' for more information.
 
17
 */
 
18
 
 
19
#include <vector>
 
20
#include <list>
 
21
#include "dsexceptions.h"
 
22
#include "PairingHeap.h"
 
23
 
 
24
#ifndef PAIRING_HEAP_CPP
 
25
#define PAIRING_HEAP_CPP
 
26
using namespace std;
 
27
/**
 
28
* Construct the pairing heap.
 
29
*/
 
30
template <class T>
 
31
PairingHeap<T>::PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) )
 
32
{
 
33
        root = NULL;
 
34
        counter=0;
 
35
        this->lessThan=lessThan;
 
36
}
 
37
 
 
38
 
 
39
/**
 
40
* Copy constructor
 
41
*/
 
42
template <class T>
 
43
PairingHeap<T>::PairingHeap( const PairingHeap<T> & rhs )
 
44
{
 
45
        root = NULL;
 
46
        counter=rhs->size();
 
47
        *this = rhs;
 
48
}
 
49
 
 
50
/**
 
51
* Destroy the leftist heap.
 
52
*/
 
53
template <class T>
 
54
PairingHeap<T>::~PairingHeap( )
 
55
{
 
56
        makeEmpty( );
 
57
}
 
58
 
 
59
/**
 
60
* Insert item x into the priority queue, maintaining heap order.
 
61
* Return a pointer to the node containing the new item.
 
62
*/
 
63
template <class T>
 
64
PairNode<T> *
 
65
PairingHeap<T>::insert( const T & x )
 
66
{
 
67
        PairNode<T> *newNode = new PairNode<T>( x );
 
68
 
 
69
        if( root == NULL )
 
70
                root = newNode;
 
71
        else
 
72
                compareAndLink( root, newNode );
 
73
        counter++;
 
74
        return newNode;
 
75
}
 
76
template <class T>
 
77
int PairingHeap<T>::size() {
 
78
        return counter;
 
79
}
 
80
/**
 
81
* Find the smallest item in the priority queue.
 
82
* Return the smallest item, or throw Underflow if empty.
 
83
*/
 
84
template <class T>
 
85
const T & PairingHeap<T>::findMin( ) const
 
86
{
 
87
        if( isEmpty( ) )
 
88
                throw Underflow( );
 
89
        return root->element;
 
90
}
 
91
/**
 
92
 * Remove the smallest item from the priority queue.
 
93
 * Throws Underflow if empty.
 
94
 */
 
95
template <class T>
 
96
void PairingHeap<T>::deleteMin( )
 
97
{
 
98
    if( isEmpty( ) )
 
99
        throw Underflow( );
 
100
 
 
101
    PairNode<T> *oldRoot = root;
 
102
 
 
103
    if( root->leftChild == NULL )
 
104
        root = NULL;
 
105
    else
 
106
        root = combineSiblings( root->leftChild );
 
107
        counter--;
 
108
    delete oldRoot;
 
109
}
 
110
 
 
111
/**
 
112
* Test if the priority queue is logically empty.
 
113
* Returns true if empty, false otherwise.
 
114
*/
 
115
template <class T>
 
116
bool PairingHeap<T>::isEmpty( ) const
 
117
{
 
118
        return root == NULL;
 
119
}
 
120
 
 
121
/**
 
122
* Test if the priority queue is logically full.
 
123
* Returns false in this implementation.
 
124
*/
 
125
template <class T>
 
126
bool PairingHeap<T>::isFull( ) const
 
127
{
 
128
        return false;
 
129
}
 
130
 
 
131
/**
 
132
* Make the priority queue logically empty.
 
133
*/
 
134
template <class T>
 
135
void PairingHeap<T>::makeEmpty( )
 
136
{
 
137
        reclaimMemory( root );
 
138
        root = NULL;
 
139
}
 
140
 
 
141
/**
 
142
* Deep copy.
 
143
*/
 
144
template <class T>
 
145
const PairingHeap<T> &
 
146
PairingHeap<T>::operator=( const PairingHeap<T> & rhs )
 
147
{
 
148
        if( this != &rhs )
 
149
        {
 
150
                makeEmpty( );
 
151
                root = clone( rhs.root );
 
152
        }
 
153
 
 
154
        return *this;
 
155
}
 
156
 
 
157
/**
 
158
* Internal method to make the tree empty.
 
159
* WARNING: This is prone to running out of stack space.
 
160
*/
 
161
template <class T>
 
162
void PairingHeap<T>::reclaimMemory( PairNode<T> * t ) const
 
163
{
 
164
        if( t != NULL )
 
165
        {
 
166
                reclaimMemory( t->leftChild );
 
167
                reclaimMemory( t->nextSibling );
 
168
                delete t;
 
169
        }
 
170
}
 
171
 
 
172
/**
 
173
* Change the value of the item stored in the pairing heap.
 
174
* Does nothing if newVal is larger than currently stored value.
 
175
* p points to a node returned by insert.
 
176
* newVal is the new value, which must be smaller
 
177
*    than the currently stored value.
 
178
*/
 
179
template <class T>
 
180
void PairingHeap<T>::decreaseKey( PairNode<T> *p,
 
181
                                                                                  const T & newVal )
 
182
{
 
183
        if( lessThan(p->element,newVal) )
 
184
                return;    // newVal cannot be bigger
 
185
        p->element = newVal;
 
186
        if( p != root )
 
187
        {
 
188
                if( p->nextSibling != NULL )
 
189
                        p->nextSibling->prev = p->prev;
 
190
                if( p->prev->leftChild == p )
 
191
                        p->prev->leftChild = p->nextSibling;
 
192
                else
 
193
                        p->prev->nextSibling = p->nextSibling;
 
194
 
 
195
                p->nextSibling = NULL;
 
196
                compareAndLink( root, p );
 
197
        }
 
198
}
 
199
 
 
200
/**
 
201
* Internal method that is the basic operation to maintain order.
 
202
* Links first and second together to satisfy heap order.
 
203
* first is root of tree 1, which may not be NULL.
 
204
*    first->nextSibling MUST be NULL on entry.
 
205
* second is root of tree 2, which may be NULL.
 
206
* first becomes the result of the tree merge.
 
207
*/
 
208
template <class T>
 
209
void PairingHeap<T>::
 
210
compareAndLink( PairNode<T> * & first,
 
211
                           PairNode<T> *second ) const
 
212
{
 
213
        if( second == NULL )
 
214
                return;
 
215
        if( lessThan(second->element,first->element) )
 
216
        {
 
217
                // Attach first as leftmost child of second
 
218
                second->prev = first->prev;
 
219
                first->prev = second;
 
220
                first->nextSibling = second->leftChild;
 
221
                if( first->nextSibling != NULL )
 
222
                        first->nextSibling->prev = first;
 
223
                second->leftChild = first;
 
224
                first = second;
 
225
        }
 
226
        else
 
227
        {
 
228
                // Attach second as leftmost child of first
 
229
                second->prev = first;
 
230
                first->nextSibling = second->nextSibling;
 
231
                if( first->nextSibling != NULL )
 
232
                        first->nextSibling->prev = first;
 
233
                second->nextSibling = first->leftChild;
 
234
                if( second->nextSibling != NULL )
 
235
                        second->nextSibling->prev = second;
 
236
                first->leftChild = second;
 
237
        }
 
238
}
 
239
 
 
240
/**
 
241
* Internal method that implements two-pass merging.
 
242
* firstSibling the root of the conglomerate;
 
243
*     assumed not NULL.
 
244
*/
 
245
template <class T>
 
246
PairNode<T> *
 
247
PairingHeap<T>::combineSiblings( PairNode<T> *firstSibling ) const
 
248
{
 
249
        if( firstSibling->nextSibling == NULL )
 
250
                return firstSibling;
 
251
 
 
252
        // Allocate the array
 
253
        static vector<PairNode<T> *> treeArray( 5 );
 
254
 
 
255
        // Store the subtrees in an array
 
256
        int numSiblings = 0;
 
257
        for( ; firstSibling != NULL; numSiblings++ )
 
258
        {
 
259
                if( numSiblings == (int)treeArray.size( ) )
 
260
                        treeArray.resize( numSiblings * 2 );
 
261
                treeArray[ numSiblings ] = firstSibling;
 
262
                firstSibling->prev->nextSibling = NULL;  // break links
 
263
                firstSibling = firstSibling->nextSibling;
 
264
        }
 
265
        if( numSiblings == (int)treeArray.size( ) )
 
266
                treeArray.resize( numSiblings + 1 );
 
267
        treeArray[ numSiblings ] = NULL;
 
268
 
 
269
        // Combine subtrees two at a time, going left to right
 
270
        int i = 0;
 
271
        for( ; i + 1 < numSiblings; i += 2 )
 
272
                compareAndLink( treeArray[ i ], treeArray[ i + 1 ] );
 
273
 
 
274
        int j = i - 2;
 
275
 
 
276
        // j has the result of last compareAndLink.
 
277
        // If an odd number of trees, get the last one.
 
278
        if( j == numSiblings - 3 )
 
279
                compareAndLink( treeArray[ j ], treeArray[ j + 2 ] );
 
280
 
 
281
        // Now go right to left, merging last tree with
 
282
        // next to last. The result becomes the new last.
 
283
        for( ; j >= 2; j -= 2 )
 
284
                compareAndLink( treeArray[ j - 2 ], treeArray[ j ] );
 
285
        return treeArray[ 0 ];
 
286
}
 
287
 
 
288
/**
 
289
* Internal method to clone subtree.
 
290
* WARNING: This is prone to running out of stack space.
 
291
*/
 
292
template <class T>
 
293
PairNode<T> *
 
294
PairingHeap<T>::clone( PairNode<T> * t ) const
 
295
{
 
296
        if( t == NULL ) 
 
297
                return NULL;
 
298
        else
 
299
        {
 
300
                PairNode<T> *p = new PairNode<T>( t->element );
 
301
                if( ( p->leftChild = clone( t->leftChild ) ) != NULL )
 
302
                        p->leftChild->prev = p;
 
303
                if( ( p->nextSibling = clone( t->nextSibling ) ) != NULL )
 
304
                        p->nextSibling->prev = p;
 
305
                return p;
 
306
        }
 
307
}
 
308
template <class T>
 
309
ostream& operator <<(ostream &os, const PairingHeap<T> &b)
 
310
{
 
311
        os<<"Heap:";
 
312
        if (b.root != NULL) {
 
313
                PairNode<T> *r = b.root;
 
314
                list<PairNode<T>*> q;
 
315
                q.push_back(r);
 
316
                while (!q.empty()) {
 
317
                        r = q.front();
 
318
                        q.pop_front();
 
319
                        if (r->leftChild != NULL) {
 
320
                                os << *r->element << ">";
 
321
                                PairNode<T> *c = r->leftChild;
 
322
                                while (c != NULL) {
 
323
                                        q.push_back(c);
 
324
                                        os << "," << *c->element;
 
325
                                        c = c->nextSibling;
 
326
                                }
 
327
                                os << "|";
 
328
                        }
 
329
                }
 
330
        }
 
331
    return os;
 
332
}
 
333
#endif