← Back to branch summary

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

« back to all changes in this revision

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

  • 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.h
 
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
#ifndef PAIRING_HEAP_H_
 
19
#define PAIRING_HEAP_H_
 
20
#include <stdlib.h>
 
21
#include <fstream>
 
22
// Pairing heap class
 
23
//
 
24
// CONSTRUCTION: with no parameters
 
25
//
 
26
// ******************PUBLIC OPERATIONS*********************
 
27
// PairNode & insert( x ) --> Insert x
 
28
// deleteMin( minItem )   --> Remove (and optionally return) smallest item
 
29
// T findMin( )  --> Return smallest item
 
30
// bool isEmpty( )        --> Return true if empty; else false
 
31
// bool isFull( )         --> Return true if empty; else false
 
32
// void makeEmpty( )      --> Remove all items
 
33
// void decreaseKey( PairNode p, newVal )
 
34
//                        --> Decrease value in node p
 
35
// ******************ERRORS********************************
 
36
// Throws Underflow as warranted
 
37
 
 
38
 
 
39
// Node and forward declaration because g++ does
 
40
// not understand nested classes.
 
41
template <class T> 
 
42
class PairingHeap;
 
43
 
 
44
template <class T>
 
45
std::ostream& operator<< (std::ostream &os,const PairingHeap<T> &b);
 
46
 
 
47
template <class T>
 
48
class PairNode
 
49
{
 
50
        friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
 
51
        T   element;
 
52
        PairNode    *leftChild;
 
53
        PairNode    *nextSibling;
 
54
        PairNode    *prev;
 
55
 
 
56
        PairNode( const T & theElement ) :
 
57
                element( theElement ),
 
58
                leftChild(NULL), nextSibling(NULL), prev(NULL)
 
59
        { }
 
60
        friend class PairingHeap<T>;
 
61
};
 
62
 
 
63
template <class T>
 
64
class Comparator
 
65
{
 
66
public:
 
67
        virtual bool isLessThan(T const &lhs, T const &rhs) const = 0;
 
68
};
 
69
 
 
70
template <class T>
 
71
class PairingHeap
 
72
{
 
73
        friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
 
74
public:
 
75
        PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) );
 
76
        PairingHeap( const PairingHeap & rhs );
 
77
    virtual ~PairingHeap( );
 
78
 
 
79
        bool isEmpty( ) const;
 
80
        bool isFull( ) const;
 
81
        int size();
 
82
 
 
83
        PairNode<T> *insert( const T & x );
 
84
        const T & findMin( ) const;
 
85
        void deleteMin( );
 
86
        const T extractMin( ) {
 
87
                T v = findMin();
 
88
                deleteMin();
 
89
                return v;
 
90
        }
 
91
        void makeEmpty( );
 
92
        void decreaseKey( PairNode<T> *p, const T & newVal );
 
93
        void merge( PairingHeap<T> *rhs )
 
94
        {       
 
95
                PairNode<T> *broot=rhs->getRoot();
 
96
                if (root == NULL) {
 
97
                        if(broot != NULL) {
 
98
                                root = broot;
 
99
                        }
 
100
                } else {
 
101
                        compareAndLink(root, broot);
 
102
                }
 
103
                counter+=rhs->size();
 
104
        }
 
105
 
 
106
        const PairingHeap & operator=( const PairingHeap & rhs );
 
107
protected:
 
108
        PairNode<T> * getRoot() {
 
109
                PairNode<T> *r=root;
 
110
                root=NULL;
 
111
                return r;
 
112
        }
 
113
private:
 
114
        PairNode<T> *root;
 
115
        bool (*lessThan)(T const &lhs, T const &rhs);
 
116
        int counter;
 
117
        void reclaimMemory( PairNode<T> *t ) const;
 
118
        void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const;
 
119
        PairNode<T> * combineSiblings( PairNode<T> *firstSibling ) const;
 
120
        PairNode<T> * clone( PairNode<T> * t ) const;
 
121
};
 
122
 
 
123
#include "PairingHeap.cpp"
 
124
#endif