Warning, file /office/calligra/libs/main/PriorityQueue_p.h was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).
0001 /* This file is part of the Calligra libraries 0002 Copyright (C) 2001 Werner Trobin <trobin@kde.org> 0003 0004 This library is free software; you can redistribute it and/or 0005 modify it under the terms of the GNU Library General Public 0006 License version 2 as published by the Free Software Foundation. 0007 0008 This library is distributed in the hope that it will be useful, 0009 but WITHOUT ANY WARRANTY; without even the implied warranty of 0010 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0011 Library General Public License for more details. 0012 0013 You should have received a copy of the GNU Library General Public License 0014 along with this library; see the file COPYING.LIB. If not, write to 0015 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0016 * Boston, MA 02110-1301, USA. 0017 */ 0018 0019 #ifndef priority_queue_h 0020 #define priority_queue_h 0021 0022 #include <vector> 0023 #include <QString> 0024 #include <QHash> 0025 #include <MainDebug.h> 0026 0027 // Better put all those internal classes in some namespace to avoid clashes 0028 // as the names are quite generic 0029 namespace CalligraFilter 0030 { 0031 0032 /** 0033 * This PriorityQueue class is implemented as "upside down" heap, i.e. the item 0034 * with the \b smallest key is at the root of the heap. 0035 * If you feel like using that class your template parameter has to have a public 0036 * method "unsigned int key() const" which returns - surprise - the key. The 0037 * supplied key must not be "negative." We use UINT_MAX as value to represent 0038 * "infinity" for the shortest path algorithm. 0039 * As this is a very specialized class we also demand a "void setIndex(int i)" 0040 * method in order to tell nodes where they are located inside the heap. This is 0041 * a very ugly approach, but it's the only way I see if you want to avoid a O(n) 0042 * search for the item where you decreased the key :} 0043 * Just to make it even worse we also use a "int index() const" method 0044 * to fetch the index... well, you most likely would need one anyway ;) 0045 * Note: This class is pointer based (like QPtr*) - if you create PriorityQueue<X> 0046 * we actually operate on X* ! We don't care about deleting your pointers at all. 0047 * We don't copy them, we don't create new ones,... - you own them, you have 0048 * to delete them :) 0049 * 0050 * In case you change a key value make sure to call keyDecreased and pass the 0051 * item you touched. This is running in O(log n) according to Cormen... 0052 * 0053 * All the ideas are stol^H^H^H^Hborrowed from "Introduction to Algorithms", 0054 * Cormen et al 0055 * 0056 * @author Werner Trobin <trobin@kde.org> 0057 */ 0058 template<class T> class PriorityQueue 0059 { 0060 0061 public: 0062 PriorityQueue() {} 0063 PriorityQueue(const PriorityQueue<T>& rhs) : m_vector(rhs.m_vector) {} 0064 PriorityQueue(const QHash<QByteArray, T*>& items); 0065 ~PriorityQueue() {} 0066 0067 PriorityQueue<T> &operator=(const PriorityQueue<T>& rhs) { 0068 m_vector = rhs.m_vector; return *this; 0069 } 0070 bool operator==(const PriorityQueue<T>& rhs) { 0071 return m_vector == rhs.m_vector; 0072 } 0073 0074 unsigned int count() const { 0075 return m_vector.size(); 0076 } 0077 bool isEmpty() const { 0078 return m_vector.empty(); 0079 } 0080 0081 void insert(T* item); 0082 0083 /** 0084 * Call this method after decreasing the key of the ith item. The heap 0085 * properties will no longer be valid if you either forget to call that 0086 * method, or if you \b increase the key. 0087 */ 0088 void keyDecreased(T* item); 0089 0090 T* extractMinimum(); 0091 0092 /** 0093 * For debugging 0094 */ 0095 void dump() const; 0096 0097 private: 0098 // Note: We have to use a 1-based index here, and we get/return 0-based ones 0099 int parent(int i) { 0100 return ((i + 1) >> 1) - 1; 0101 } 0102 int left(int i) { 0103 return ((i + 1) << 1) - 1; 0104 } 0105 int right(int i) { 0106 return (i + 1) << 1; 0107 } 0108 0109 void heapify(int i); 0110 // item is !=0 for sure 0111 void bubbleUp(T* item, int i); 0112 // Builds the heap in the vector in O(n) 0113 void buildHeap(); 0114 0115 std::vector<T*> m_vector; 0116 }; 0117 0118 template<class T> 0119 PriorityQueue<T>::PriorityQueue(const QHash<QByteArray, T*>& items) 0120 : m_vector(items.count()) 0121 { 0122 // First put all items into the vector 0123 int i = 0; 0124 foreach(T* item, items) { 0125 item->setIndex(i); 0126 m_vector[i] = item; 0127 ++i; 0128 } 0129 // Then build a heap in that vector 0130 buildHeap(); 0131 } 0132 0133 template<class T> 0134 void PriorityQueue<T>::insert(T* item) 0135 { 0136 if (!item) 0137 return; 0138 int i = static_cast<int>(m_vector.size()); 0139 m_vector.push_back(0); // extend the vector by one item. i == index to the last item 0140 bubbleUp(item, i); 0141 } 0142 0143 template<class T> 0144 void PriorityQueue<T>::keyDecreased(T* item) 0145 { 0146 if (!item) 0147 return; 0148 bubbleUp(item, item->index()); 0149 } 0150 0151 template<class T> 0152 T* PriorityQueue<T>::extractMinimum() 0153 { 0154 if (m_vector.size() < 1) 0155 return 0; 0156 T *min = m_vector[ 0 ]; 0157 m_vector[ 0 ] = m_vector[ m_vector.size() - 1 ]; 0158 // update the index 0159 m_vector[ 0 ]->setIndex(0); 0160 m_vector.pop_back(); 0161 heapify(0); 0162 return min; 0163 } 0164 0165 template<class T> 0166 void PriorityQueue<T>::dump() const 0167 { 0168 debugFilter << "++++++++++ PriorityQueue::dump ++++++++++"; 0169 QString out; 0170 int size = static_cast<int>(m_vector.size()); 0171 for (int i = 0; i < size; ++i) { 0172 if (m_vector[ i ]->index() != i) 0173 out += " ERROR: index out of sync. Should be " + QString::number(i) + ", is " + 0174 QString::number(m_vector[ i ]->index()) + ". "; 0175 out += QString::number(m_vector[ i ]->key()) + ", "; 0176 } 0177 if (out.isEmpty()) 0178 out = "(empty)"; 0179 debugFilter << out; 0180 debugFilter << "++++++++++ PriorityQueue::dump (done) ++++++++++"; 0181 } 0182 0183 template<class T> 0184 void PriorityQueue<T>::heapify(int i) 0185 { 0186 int l = left(i); 0187 int r = right(i); 0188 int size = static_cast<int>(m_vector.size()); 0189 int smallest; 0190 0191 if (l < size && i < size && m_vector[ l ]->key() < m_vector[ i ]->key()) 0192 smallest = l; 0193 else 0194 smallest = i; 0195 0196 if (r < size && m_vector[ r ]->key() < m_vector[ smallest ]->key()) 0197 smallest = r; 0198 0199 if (smallest != i) { 0200 T* tmp = m_vector[ i ]; 0201 m_vector[ i ] = m_vector[ smallest ]; 0202 // update indices 0203 m_vector[ i ]->setIndex(i); 0204 tmp->setIndex(smallest); 0205 m_vector[ smallest ] = tmp; 0206 heapify(smallest); 0207 } 0208 } 0209 0210 template<class T> 0211 void PriorityQueue<T>::bubbleUp(T* item, int i) 0212 { 0213 int p = parent(i); 0214 while (i > 0 && m_vector[ p ]->key() > item->key()) { 0215 // update the index first 0216 m_vector[ p ]->setIndex(i); 0217 // then move it there 0218 m_vector[ i ] = m_vector[ p ]; 0219 i = p; 0220 p = parent(i); 0221 } 0222 item->setIndex(i); 0223 m_vector[ i ] = item; 0224 } 0225 0226 template<class T> 0227 void PriorityQueue<T>::buildHeap() 0228 { 0229 // from size() / 2 down to 1 0230 for (int i = (m_vector.size() >> 1) - 1; i >= 0; --i) 0231 heapify(i); 0232 } 0233 0234 } // namespace Calligra 0235 0236 #endif // priority_queue_h