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