1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/quad_heap.h Tue Dec 20 18:15:14 2011 +0100
1.3 @@ -0,0 +1,343 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_QUAD_HEAP_H
1.23 +#define LEMON_QUAD_HEAP_H
1.24 +
1.25 +///\ingroup heaps
1.26 +///\file
1.27 +///\brief Fourary (quaternary) heap implementation.
1.28 +
1.29 +#include <vector>
1.30 +#include <utility>
1.31 +#include <functional>
1.32 +
1.33 +namespace lemon {
1.34 +
1.35 + /// \ingroup heaps
1.36 + ///
1.37 + ///\brief Fourary (quaternary) heap data structure.
1.38 + ///
1.39 + /// This class implements the \e Fourary (\e quaternary) \e heap
1.40 + /// data structure.
1.41 + /// It fully conforms to the \ref concepts::Heap "heap concept".
1.42 + ///
1.43 + /// The fourary heap is a specialization of the \ref DHeap "D-ary heap"
1.44 + /// for <tt>D=4</tt>. It is similar to the \ref BinHeap "binary heap",
1.45 + /// but its nodes have at most four children, instead of two.
1.46 + ///
1.47 + /// \tparam PR Type of the priorities of the items.
1.48 + /// \tparam IM A read-writable item map with \c int values, used
1.49 + /// internally to handle the cross references.
1.50 + /// \tparam CMP A functor class for comparing the priorities.
1.51 + /// The default is \c std::less<PR>.
1.52 + ///
1.53 + ///\sa BinHeap
1.54 + ///\sa DHeap
1.55 +#ifdef DOXYGEN
1.56 + template <typename PR, typename IM, typename CMP>
1.57 +#else
1.58 + template <typename PR, typename IM, typename CMP = std::less<PR> >
1.59 +#endif
1.60 + class QuadHeap {
1.61 + public:
1.62 + /// Type of the item-int map.
1.63 + typedef IM ItemIntMap;
1.64 + /// Type of the priorities.
1.65 + typedef PR Prio;
1.66 + /// Type of the items stored in the heap.
1.67 + typedef typename ItemIntMap::Key Item;
1.68 + /// Type of the item-priority pairs.
1.69 + typedef std::pair<Item,Prio> Pair;
1.70 + /// Functor type for comparing the priorities.
1.71 + typedef CMP Compare;
1.72 +
1.73 + /// \brief Type to represent the states of the items.
1.74 + ///
1.75 + /// Each item has a state associated to it. It can be "in heap",
1.76 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
1.77 + /// heap's point of view, but may be useful to the user.
1.78 + ///
1.79 + /// The item-int map must be initialized in such way that it assigns
1.80 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
1.81 + enum State {
1.82 + IN_HEAP = 0, ///< = 0.
1.83 + PRE_HEAP = -1, ///< = -1.
1.84 + POST_HEAP = -2 ///< = -2.
1.85 + };
1.86 +
1.87 + private:
1.88 + std::vector<Pair> _data;
1.89 + Compare _comp;
1.90 + ItemIntMap &_iim;
1.91 +
1.92 + public:
1.93 + /// \brief Constructor.
1.94 + ///
1.95 + /// Constructor.
1.96 + /// \param map A map that assigns \c int values to the items.
1.97 + /// It is used internally to handle the cross references.
1.98 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
1.99 + explicit QuadHeap(ItemIntMap &map) : _iim(map) {}
1.100 +
1.101 + /// \brief Constructor.
1.102 + ///
1.103 + /// Constructor.
1.104 + /// \param map A map that assigns \c int values to the items.
1.105 + /// It is used internally to handle the cross references.
1.106 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
1.107 + /// \param comp The function object used for comparing the priorities.
1.108 + QuadHeap(ItemIntMap &map, const Compare &comp)
1.109 + : _iim(map), _comp(comp) {}
1.110 +
1.111 + /// \brief The number of items stored in the heap.
1.112 + ///
1.113 + /// This function returns the number of items stored in the heap.
1.114 + int size() const { return _data.size(); }
1.115 +
1.116 + /// \brief Check if the heap is empty.
1.117 + ///
1.118 + /// This function returns \c true if the heap is empty.
1.119 + bool empty() const { return _data.empty(); }
1.120 +
1.121 + /// \brief Make the heap empty.
1.122 + ///
1.123 + /// This functon makes the heap empty.
1.124 + /// It does not change the cross reference map. If you want to reuse
1.125 + /// a heap that is not surely empty, you should first clear it and
1.126 + /// then you should set the cross reference map to \c PRE_HEAP
1.127 + /// for each item.
1.128 + void clear() { _data.clear(); }
1.129 +
1.130 + private:
1.131 + static int parent(int i) { return (i-1)/4; }
1.132 + static int firstChild(int i) { return 4*i+1; }
1.133 +
1.134 + bool less(const Pair &p1, const Pair &p2) const {
1.135 + return _comp(p1.second, p2.second);
1.136 + }
1.137 +
1.138 + void bubbleUp(int hole, Pair p) {
1.139 + int par = parent(hole);
1.140 + while( hole>0 && less(p,_data[par]) ) {
1.141 + move(_data[par],hole);
1.142 + hole = par;
1.143 + par = parent(hole);
1.144 + }
1.145 + move(p, hole);
1.146 + }
1.147 +
1.148 + void bubbleDown(int hole, Pair p, int length) {
1.149 + if( length>1 ) {
1.150 + int child = firstChild(hole);
1.151 + while( child+3<length ) {
1.152 + int min=child;
1.153 + if( less(_data[++child], _data[min]) ) min=child;
1.154 + if( less(_data[++child], _data[min]) ) min=child;
1.155 + if( less(_data[++child], _data[min]) ) min=child;
1.156 + if( !less(_data[min], p) )
1.157 + goto ok;
1.158 + move(_data[min], hole);
1.159 + hole = min;
1.160 + child = firstChild(hole);
1.161 + }
1.162 + if ( child<length ) {
1.163 + int min = child;
1.164 + if( ++child<length && less(_data[child], _data[min]) ) min=child;
1.165 + if( ++child<length && less(_data[child], _data[min]) ) min=child;
1.166 + if( less(_data[min], p) ) {
1.167 + move(_data[min], hole);
1.168 + hole = min;
1.169 + }
1.170 + }
1.171 + }
1.172 + ok:
1.173 + move(p, hole);
1.174 + }
1.175 +
1.176 + void move(const Pair &p, int i) {
1.177 + _data[i] = p;
1.178 + _iim.set(p.first, i);
1.179 + }
1.180 +
1.181 + public:
1.182 + /// \brief Insert a pair of item and priority into the heap.
1.183 + ///
1.184 + /// This function inserts \c p.first to the heap with priority
1.185 + /// \c p.second.
1.186 + /// \param p The pair to insert.
1.187 + /// \pre \c p.first must not be stored in the heap.
1.188 + void push(const Pair &p) {
1.189 + int n = _data.size();
1.190 + _data.resize(n+1);
1.191 + bubbleUp(n, p);
1.192 + }
1.193 +
1.194 + /// \brief Insert an item into the heap with the given priority.
1.195 + ///
1.196 + /// This function inserts the given item into the heap with the
1.197 + /// given priority.
1.198 + /// \param i The item to insert.
1.199 + /// \param p The priority of the item.
1.200 + /// \pre \e i must not be stored in the heap.
1.201 + void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
1.202 +
1.203 + /// \brief Return the item having minimum priority.
1.204 + ///
1.205 + /// This function returns the item having minimum priority.
1.206 + /// \pre The heap must be non-empty.
1.207 + Item top() const { return _data[0].first; }
1.208 +
1.209 + /// \brief The minimum priority.
1.210 + ///
1.211 + /// This function returns the minimum priority.
1.212 + /// \pre The heap must be non-empty.
1.213 + Prio prio() const { return _data[0].second; }
1.214 +
1.215 + /// \brief Remove the item having minimum priority.
1.216 + ///
1.217 + /// This function removes the item having minimum priority.
1.218 + /// \pre The heap must be non-empty.
1.219 + void pop() {
1.220 + int n = _data.size()-1;
1.221 + _iim.set(_data[0].first, POST_HEAP);
1.222 + if (n>0) bubbleDown(0, _data[n], n);
1.223 + _data.pop_back();
1.224 + }
1.225 +
1.226 + /// \brief Remove the given item from the heap.
1.227 + ///
1.228 + /// This function removes the given item from the heap if it is
1.229 + /// already stored.
1.230 + /// \param i The item to delete.
1.231 + /// \pre \e i must be in the heap.
1.232 + void erase(const Item &i) {
1.233 + int h = _iim[i];
1.234 + int n = _data.size()-1;
1.235 + _iim.set(_data[h].first, POST_HEAP);
1.236 + if( h<n ) {
1.237 + if( less(_data[parent(h)], _data[n]) )
1.238 + bubbleDown(h, _data[n], n);
1.239 + else
1.240 + bubbleUp(h, _data[n]);
1.241 + }
1.242 + _data.pop_back();
1.243 + }
1.244 +
1.245 + /// \brief The priority of the given item.
1.246 + ///
1.247 + /// This function returns the priority of the given item.
1.248 + /// \param i The item.
1.249 + /// \pre \e i must be in the heap.
1.250 + Prio operator[](const Item &i) const {
1.251 + int idx = _iim[i];
1.252 + return _data[idx].second;
1.253 + }
1.254 +
1.255 + /// \brief Set the priority of an item or insert it, if it is
1.256 + /// not stored in the heap.
1.257 + ///
1.258 + /// This method sets the priority of the given item if it is
1.259 + /// already stored in the heap. Otherwise it inserts the given
1.260 + /// item into the heap with the given priority.
1.261 + /// \param i The item.
1.262 + /// \param p The priority.
1.263 + void set(const Item &i, const Prio &p) {
1.264 + int idx = _iim[i];
1.265 + if( idx < 0 )
1.266 + push(i,p);
1.267 + else if( _comp(p, _data[idx].second) )
1.268 + bubbleUp(idx, Pair(i,p));
1.269 + else
1.270 + bubbleDown(idx, Pair(i,p), _data.size());
1.271 + }
1.272 +
1.273 + /// \brief Decrease the priority of an item to the given value.
1.274 + ///
1.275 + /// This function decreases the priority of an item to the given value.
1.276 + /// \param i The item.
1.277 + /// \param p The priority.
1.278 + /// \pre \e i must be stored in the heap with priority at least \e p.
1.279 + void decrease(const Item &i, const Prio &p) {
1.280 + int idx = _iim[i];
1.281 + bubbleUp(idx, Pair(i,p));
1.282 + }
1.283 +
1.284 + /// \brief Increase the priority of an item to the given value.
1.285 + ///
1.286 + /// This function increases the priority of an item to the given value.
1.287 + /// \param i The item.
1.288 + /// \param p The priority.
1.289 + /// \pre \e i must be stored in the heap with priority at most \e p.
1.290 + void increase(const Item &i, const Prio &p) {
1.291 + int idx = _iim[i];
1.292 + bubbleDown(idx, Pair(i,p), _data.size());
1.293 + }
1.294 +
1.295 + /// \brief Return the state of an item.
1.296 + ///
1.297 + /// This method returns \c PRE_HEAP if the given item has never
1.298 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
1.299 + /// and \c POST_HEAP otherwise.
1.300 + /// In the latter case it is possible that the item will get back
1.301 + /// to the heap again.
1.302 + /// \param i The item.
1.303 + State state(const Item &i) const {
1.304 + int s = _iim[i];
1.305 + if (s>=0) s=0;
1.306 + return State(s);
1.307 + }
1.308 +
1.309 + /// \brief Set the state of an item in the heap.
1.310 + ///
1.311 + /// This function sets the state of the given item in the heap.
1.312 + /// It can be used to manually clear the heap when it is important
1.313 + /// to achive better time complexity.
1.314 + /// \param i The item.
1.315 + /// \param st The state. It should not be \c IN_HEAP.
1.316 + void state(const Item& i, State st) {
1.317 + switch (st) {
1.318 + case POST_HEAP:
1.319 + case PRE_HEAP:
1.320 + if (state(i) == IN_HEAP) erase(i);
1.321 + _iim[i] = st;
1.322 + break;
1.323 + case IN_HEAP:
1.324 + break;
1.325 + }
1.326 + }
1.327 +
1.328 + /// \brief Replace an item in the heap.
1.329 + ///
1.330 + /// This function replaces item \c i with item \c j.
1.331 + /// Item \c i must be in the heap, while \c j must be out of the heap.
1.332 + /// After calling this method, item \c i will be out of the
1.333 + /// heap and \c j will be in the heap with the same prioriority
1.334 + /// as item \c i had before.
1.335 + void replace(const Item& i, const Item& j) {
1.336 + int idx = _iim[i];
1.337 + _iim.set(i, _iim[j]);
1.338 + _iim.set(j, idx);
1.339 + _data[idx].first = j;
1.340 + }
1.341 +
1.342 + }; // class QuadHeap
1.343 +
1.344 +} // namespace lemon
1.345 +
1.346 +#endif // LEMON_FOURARY_HEAP_H