← Back to branch summary

~ubuntu-branches/ubuntu/breezy/koffice/breezy

« back to all changes in this revision

Viewing changes to lib/kofficecore/priorityqueue.h

  • Committer: Bazaar Package Importer
  • Author(s): Ben Burton
  • Date: 2004-05-09 11:33:00 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20040509113300-vfrdadqsvjfuhn3b
Tags: 1:1.3.1-1
http://bugs.debian.org/246623
http://bugs.debian.org/246209
http://bugs.debian.org/221256
http://bugs.debian.org/227568
* New upstream bugfix release.
* Built against newer imagemagick (closes: #246623).
* Made koffice-libs/kformula recommend/depend on latex-xft-fonts, which
  provides mathematical fonts that the formula editor can use.  Also
  patched the kformula part to make these fonts the default.
* Changed kword menu hint from "WordProcessors" to "Word processors"
  (closes: #246209).
* Spellchecker configuration is now fixed (closes: #221256, #227568).

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/kofficecore/priorityqueue.h
 
1
/* This file is part of the KOffice libraries
 
2
   Copyright (C) 2001 Werner Trobin <trobin@kde.org>
 
3
 
 
4
   This library is free software; you can redistribute it and/or
 
5
   modify it under the terms of the GNU Library General Public
 
6
   License version 2 as published by the Free Software Foundation.
 
7
 
 
8
   This library is distributed in the hope that it will be useful,
 
9
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
11
   Library General Public License for more details.
 
12
 
 
13
   You should have received a copy of the GNU Library General Public License
 
14
   along with this library; see the file COPYING.LIB.  If not, write to
 
15
   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 
16
   Boston, MA 02111-1307, USA.
 
17
*/
 
18
 
 
19
#ifndef priority_queue_h
 
20
#define priority_queue_h
 
21
 
 
22
#include <vector>
 
23
#include <qstring.h>
 
24
#include <qasciidict.h>
 
25
#include <kdebug.h>
 
26
 
 
27
// Better put all those internal classes in some namespace to avoid clashes
 
28
// as the names are quite generic
 
29
namespace KOffice {
 
30
 
 
31
    /**
 
32
     * This PriorityQueue class is implemented as "upside down" heap, i.e. the item
 
33
     * with the \b smallest key is at the root of the heap.
 
34
     * If you feel like using that class your template parameter has to have a public
 
35
     * method "unsigned int key() const" which returns - surprise - the key. The
 
36
     * supplied key must not be "negative." We use UINT_MAX as value to represent
 
37
     * "infinity" for the shortest path algorithm.
 
38
     * As this is a very specialized class we also demand a "void setIndex(int i)"
 
39
     * method in order to tell nodes where they are located inside the heap. This is
 
40
     * a very ugly approach, but it's the only way I see if you want to avoid a O(n)
 
41
     * search for the item where you decreased the key :}
 
42
     * Just to make it even worse we also use a "int index() const" method
 
43
     * to fetch the index... well, you most likely would need one anyway ;)
 
44
     * Note: This class is pointer based (like QPtr*) - if you create PriorityQueue<X>
 
45
     * we actually operate on X* ! We don't care about deleting your pointers at all.
 
46
     * We don't copy them, we don't create new ones,... - you own them, you have
 
47
     * to delete them :)
 
48
     *
 
49
     * In case you change a key value make sure to call keyDecreased and pass the
 
50
     * item you touched. This is running in O(log n) according to Cormen...
 
51
     *
 
52
     * All the ideas are stol^H^H^H^Hborrowed from "Introduction to Algorithms",
 
53
     * Cormen et al
 
54
     *
 
55
     * @author Werner Trobin <trobin@kde.org>
 
56
     */
 
57
    template<class T> class PriorityQueue {
 
58
 
 
59
    public:
 
60
        PriorityQueue() {}
 
61
        PriorityQueue( const PriorityQueue<T>& rhs ) : m_vector( rhs.m_vector ) {}
 
62
        PriorityQueue( const QAsciiDict<T>& items );
 
63
        ~PriorityQueue() {}
 
64
 
 
65
        PriorityQueue<T> &operator=( const PriorityQueue<T>& rhs ) { m_vector = rhs.m_vector; return *this; }
 
66
        bool operator==( const PriorityQueue<T>& rhs ) { return m_vector == rhs.m_vector; }
 
67
 
 
68
        unsigned int count() const { return m_vector.size(); }
 
69
        bool isEmpty() const { return m_vector.empty(); }
 
70
 
 
71
        void insert( T* item );
 
72
 
 
73
        /**
 
74
         * Call this method after decreasing the key of the ith item. The heap
 
75
         * properties will no longer be valid if you either forget to call that
 
76
         * method, or if you \b increase the key.
 
77
         */
 
78
        void keyDecreased( T* item );
 
79
 
 
80
        T* extractMinimum();
 
81
 
 
82
        /**
 
83
         * For debugging
 
84
         */
 
85
        void dump() const;
 
86
 
 
87
    private:
 
88
        // Note: We have to use a 1-based index here, and we get/return 0-based ones
 
89
        int parent( int i ) { return ( ( i + 1 ) >> 1 ) - 1; }
 
90
        int left( int i ) { return ( ( i + 1 ) << 1 ) - 1; }
 
91
        int right( int i ) { return ( i + 1 ) << 1; }
 
92
 
 
93
        void heapify( int i );
 
94
        // item is !=0 for sure
 
95
        void bubbleUp( T* item, int i );
 
96
        // Builds the heap in the vector in O(n)
 
97
        void buildHeap();
 
98
 
 
99
        std::vector<T*> m_vector;
 
100
    };
 
101
 
 
102
    template<class T>
 
103
    PriorityQueue<T>::PriorityQueue( const QAsciiDict<T>& items ) : m_vector( items.count() )
 
104
    {
 
105
        // First put all items into the vector
 
106
        QAsciiDictIterator<T> it( items );
 
107
        for ( int i = 0; it.current(); ++it, ++i ) {
 
108
            it.current()->setIndex( i );
 
109
            m_vector[ i ] = it.current();
 
110
        }
 
111
        // Then build a heap in that vector
 
112
        buildHeap();
 
113
    }
 
114
 
 
115
    template<class T>
 
116
    void PriorityQueue<T>::insert( T* item )
 
117
    {
 
118
        if ( !item )
 
119
            return;
 
120
        int i = static_cast<int>( m_vector.size() );
 
121
        m_vector.push_back( 0 ); // extend the vector by one item. i == index to the last item
 
122
        bubbleUp( item, i );
 
123
    }
 
124
 
 
125
    template<class T>
 
126
    void PriorityQueue<T>::keyDecreased( T* item )
 
127
    {
 
128
        if ( !item )
 
129
            return;
 
130
        bubbleUp( item, item->index() );
 
131
    }
 
132
 
 
133
    template<class T>
 
134
    T* PriorityQueue<T>::extractMinimum()
 
135
    {
 
136
        if ( m_vector.size() < 1 )
 
137
            return 0;
 
138
        T *min = m_vector[ 0 ];
 
139
        m_vector[ 0 ] = m_vector[ m_vector.size() - 1 ];
 
140
        // update the index
 
141
        m_vector[ 0 ]->setIndex( 0 );
 
142
        m_vector.pop_back();
 
143
        heapify( 0 );
 
144
        return min;
 
145
    }
 
146
 
 
147
    template<class T>
 
148
    void PriorityQueue<T>::dump() const
 
149
    {
 
150
        kdDebug( 30500 ) << "++++++++++ PriorityQueue::dump ++++++++++" << endl;
 
151
        QString out;
 
152
        int size = static_cast<int>( m_vector.size() );
 
153
        for ( int i = 0; i < size; ++i ) {
 
154
            if ( m_vector[ i ]->index() != i )
 
155
                out += " ERROR: index out of sync. Should be " + QString::number( i ) + ", is " +
 
156
                       QString::number( m_vector[ i ]->index() ) + ". ";
 
157
            out += QString::number( m_vector[ i ]->key() );
 
158
            out += ", ";
 
159
        }
 
160
        if ( out.isEmpty() )
 
161
            out = "(empty)";
 
162
        kdDebug( 30500 ) << out << endl;
 
163
        kdDebug( 30500 ) << "++++++++++ PriorityQueue::dump (done) ++++++++++" << endl;
 
164
    }
 
165
 
 
166
    template<class T>
 
167
    void PriorityQueue<T>::heapify( int i )
 
168
    {
 
169
        int l = left( i ), r = right( i ), size = static_cast<int>( m_vector.size() );
 
170
        int smallest;
 
171
 
 
172
        if ( l < size && m_vector[ l ]->key() < m_vector[ i ]->key() )
 
173
            smallest = l;
 
174
        else
 
175
            smallest = i;
 
176
        if ( r < size && m_vector[ r ]->key() < m_vector[ smallest ]->key() )
 
177
            smallest = r;
 
178
 
 
179
        if ( smallest != i ) {
 
180
            T* tmp = m_vector[ i ];
 
181
            m_vector[ i ] = m_vector[ smallest ];
 
182
            // update indices
 
183
            m_vector[ i ]->setIndex( i );
 
184
            tmp->setIndex( smallest );
 
185
            m_vector[ smallest ] = tmp;
 
186
            heapify( smallest );
 
187
        }
 
188
    }
 
189
 
 
190
    template<class T>
 
191
    void PriorityQueue<T>::bubbleUp( T* item, int i )
 
192
    {
 
193
        int p = parent( i );
 
194
        while ( i > 0 && m_vector[ p ]->key() > item->key() ) {
 
195
            // update the index first
 
196
            m_vector[ p ]->setIndex( i );
 
197
            // then move it there
 
198
            m_vector[ i ] = m_vector[ p ];
 
199
            i = p;
 
200
            p = parent( i );
 
201
        }
 
202
        item->setIndex( i );
 
203
        m_vector[ i ] = item;
 
204
    }
 
205
 
 
206
    template<class T>
 
207
    void PriorityQueue<T>::buildHeap()
 
208
    {
 
209
        // from size() / 2 down to 1
 
210
        for ( int i = ( m_vector.size() >> 1 ) - 1; i >= 0; --i )
 
211
            heapify( i );
 
212
    }
 
213
 
 
214
} // namespace KOffice
 
215
 
 
216
#endif // priority_queue_h