alpar@906: /* -*- C++ -*- alpar@921: * src/lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library klao@39: * alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@906: * (Egervary Combinatorial Optimization Research Group, EGRES). klao@39: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. klao@39: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. klao@39: * klao@39: */ klao@39: alpar@921: #ifndef LEMON_BIN_HEAP_H alpar@921: #define LEMON_BIN_HEAP_H klao@37: klao@491: ///\ingroup auxdat klao@274: ///\file klao@274: ///\brief Binary Heap implementation. alpar@906: ///\todo It should be documented. klao@274: klao@37: #include <vector> klao@37: #include <utility> klao@37: #include <functional> klao@37: alpar@921: namespace lemon { klao@37: alpar@430: /// \addtogroup auxdat alpar@430: /// @{ alpar@430: alpar@430: /// A Binary Heap implementation. alpar@967: alpar@967: ///\todo Please document... alpar@967: /// alpar@967: ///\sa FibHeap alpar@967: ///\sa Dijkstra klao@172: template <typename Item, typename Prio, typename ItemIntMap, klao@172: typename Compare = std::less<Prio> > klao@37: class BinHeap { klao@37: klao@37: public: klao@172: typedef Item ItemType; klao@37: // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot... klao@172: typedef Prio PrioType; klao@172: typedef std::pair<ItemType,PrioType> PairType; klao@172: typedef ItemIntMap ItemIntMapType; klao@172: typedef Compare PrioCompare; klao@37: klao@37: /** klao@172: * Each Item element have a state associated to it. It may be "in heap", klao@37: * "pre heap" or "post heap". The later two are indifferent from the klao@37: * heap's point of view, but may be useful to the user. klao@37: * klao@172: * The ItemIntMap _should_ be initialized in such way, that it maps klao@37: * PRE_HEAP (-1) to any element to be put in the heap... klao@37: */ klao@274: ///\todo it is used nowhere klao@274: /// klao@39: enum state_enum { klao@37: IN_HEAP = 0, klao@37: PRE_HEAP = -1, klao@37: POST_HEAP = -2 klao@37: }; klao@37: klao@37: private: klao@37: std::vector<PairType> data; klao@37: Compare comp; klao@37: // FIXME: jo ez igy??? klao@172: ItemIntMap &iim; klao@37: klao@37: public: alpar@967: ///\e deba@1185: explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {} alpar@967: ///\e deba@1191: BinHeap(ItemIntMap &_iim, const Compare &_comp) deba@1185: : iim(_iim), comp(_comp) {} klao@37: klao@37: alpar@967: ///\e klao@37: int size() const { return data.size(); } alpar@967: ///\e klao@41: bool empty() const { return data.empty(); } klao@37: klao@37: private: klao@37: static int parent(int i) { return (i-1)/2; } klao@37: static int second_child(int i) { return 2*i+2; } klao@214: bool less(const PairType &p1, const PairType &p2) const { klao@37: return comp(p1.second, p2.second); klao@37: } klao@37: klao@37: int bubble_up(int hole, PairType p); klao@37: int bubble_down(int hole, PairType p, int length); klao@37: klao@37: void move(const PairType &p, int i) { klao@37: data[i] = p; klao@172: iim.set(p.first, i); klao@37: } klao@37: klao@41: void rmidx(int h) { klao@41: int n = data.size()-1; klao@41: if( h>=0 && h<=n ) { klao@172: iim.set(data[h].first, POST_HEAP); klao@41: if ( h<n ) { klao@41: bubble_down(h, data[n], n); klao@41: } klao@41: data.pop_back(); klao@41: } klao@41: } klao@41: klao@37: public: alpar@967: ///\e klao@37: void push(const PairType &p) { klao@37: int n = data.size(); klao@37: data.resize(n+1); klao@37: bubble_up(n, p); klao@37: } alpar@967: ///\e klao@172: void push(const Item &i, const Prio &p) { push(PairType(i,p)); } klao@37: alpar@967: ///\e klao@172: Item top() const { klao@37: return data[0].first; klao@37: } klao@274: /// Returns the prio of the top element of the heap. klao@274: Prio prio() const { klao@37: return data[0].second; klao@37: } klao@37: alpar@967: ///\e klao@37: void pop() { klao@41: rmidx(0); klao@41: } klao@41: alpar@967: ///\e klao@172: void erase(const Item &i) { jacint@221: rmidx(iim[i]); klao@37: } klao@37: alpar@967: ///\e klao@274: Prio operator[](const Item &i) const { jacint@221: int idx = iim[i]; klao@37: return data[idx].second; klao@37: } klao@274: alpar@967: ///\e klao@172: void set(const Item &i, const Prio &p) { jacint@221: int idx = iim[i]; klao@37: if( idx < 0 ) { klao@172: push(i,p); klao@37: } klao@172: else if( comp(p, data[idx].second) ) { klao@172: bubble_up(idx, PairType(i,p)); klao@37: } klao@37: else { klao@172: bubble_down(idx, PairType(i,p), data.size()); klao@37: } klao@37: } klao@37: alpar@967: ///\e klao@172: void decrease(const Item &i, const Prio &p) { jacint@221: int idx = iim[i]; klao@172: bubble_up(idx, PairType(i,p)); klao@37: } alpar@967: ///\e klao@172: void increase(const Item &i, const Prio &p) { jacint@221: int idx = iim[i]; klao@172: bubble_down(idx, PairType(i,p), data.size()); klao@37: } klao@37: alpar@967: ///\e klao@172: state_enum state(const Item &i) const { jacint@221: int s = iim[i]; klao@39: if( s>=0 ) klao@39: s=0; klao@39: return state_enum(s); klao@39: } klao@39: klao@37: }; // class BinHeap klao@37: klao@37: klao@37: template <typename K, typename V, typename M, typename C> klao@37: int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) { klao@37: int par = parent(hole); klao@37: while( hole>0 && less(p,data[par]) ) { klao@37: move(data[par],hole); klao@37: hole = par; klao@37: par = parent(hole); klao@37: } klao@37: move(p, hole); klao@37: return hole; klao@37: } klao@37: klao@37: template <typename K, typename V, typename M, typename C> klao@37: int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) { klao@37: int child = second_child(hole); klao@37: while(child < length) { klao@37: if( less(data[child-1], data[child]) ) { klao@37: --child; klao@37: } klao@37: if( !less(data[child], p) ) klao@37: goto ok; klao@37: move(data[child], hole); klao@37: hole = child; klao@37: child = second_child(hole); klao@37: } klao@37: child--; klao@37: if( child<length && less(data[child], p) ) { klao@37: move(data[child], hole); klao@37: hole=child; klao@37: } klao@37: ok: klao@37: move(p, hole); klao@37: return hole; klao@37: } klao@37: alpar@430: ///@} alpar@430: alpar@921: } // namespace lemon klao@37: alpar@921: #endif // LEMON_BIN_HEAP_H