diff -r d8863141824d -r fb261e3a9a0f src/include/bin_heap.h --- a/src/include/bin_heap.h Thu May 06 09:26:23 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,246 +0,0 @@ -// -*- C++ -*- // - -/* FIXME: Copyright ... - * - * This implementation is heavily based on STL's heap functions and - * the similar class by Alpar Juttner in IKTA... - */ - -/****** - * - * BinHeap - * - * Ez az osztaly item-prioritas parok tarolasara alkalmas binaris kupacot - * valosit meg. - * A kupacban legfolul mindig az a par talalhato, amiben a prioritas a - * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz - * lett keszitve...) - * - * Megjegyzes: a kupacos temakorokben a prioritast kulcsnak szoktak nevezni, - * de mivel ez zavaro tud lenni a property-map-es kulcs-ertek szohasznalata - * miatt, megprobaltunk valami semleges elnevezeseket kitalalni. - * - * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami - * az itemekhez egy int-et tud tarolni (ezzel tudom megkeresni az illeto - * elemet a kupacban a csokkentes es hasonlo muveletekhez). - * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek - * is elnie kell. (???) - * - * Ketfele modon hasznalhato: - * Lusta mod: - * set(Item, Prio) metodussal pakolunk a kupacba, - * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor - * csokkentettunk-e rajta, vagy noveltunk. - * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen - * minden szobajovo kulcs ertekre, -1 -es ertekkel! - * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal: - * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0, - * mar kikerult a kupacbol POST_HEAP=-2). - * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak - * meg meg tudja mondani a "legkisebb" prioritasu elemet. De csak nagyjabol, - * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk... - * - * Kozvetlen mod: - * push(Item, Prio) metodussal belerakunk a kupacba (ha az illeto kulcs mar - * benn volt, akkor gaz). - * increase/decrease(Item i, Prio new_prio) metodusokkal lehet - * novelni/csokkenteni az illeto elemhez tartozo prioritast. (Ha nem volt - * megbenne a kupacban az illeto elem, vagy nem abba az iranyba valtoztattad - * az erteket, amerre mondtad -- gaz). - * - * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni. - * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac - * hasznal. :-)) - * - * - * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi) - * - */ - - -#ifndef BIN_HEAP_HH -#define BIN_HEAP_HH - -///\ingroup auxdat -///\file -///\brief Binary Heap implementation. - -#include -#include -#include - -namespace hugo { - - /// \addtogroup auxdat - /// @{ - - /// A Binary Heap implementation. - template > - class BinHeap { - - public: - typedef Item ItemType; - // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot... - typedef Prio PrioType; - typedef std::pair PairType; - typedef ItemIntMap ItemIntMapType; - typedef Compare PrioCompare; - - /** - * Each Item element have a state associated to it. It may be "in heap", - * "pre heap" or "post heap". The later two are indifferent from the - * heap's point of view, but may be useful to the user. - * - * The ItemIntMap _should_ be initialized in such way, that it maps - * PRE_HEAP (-1) to any element to be put in the heap... - */ - ///\todo it is used nowhere - /// - enum state_enum { - IN_HEAP = 0, - PRE_HEAP = -1, - POST_HEAP = -2 - }; - - private: - std::vector data; - Compare comp; - // FIXME: jo ez igy??? - ItemIntMap &iim; - - public: - BinHeap(ItemIntMap &_iim) : iim(_iim) {} - BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {} - - - int size() const { return data.size(); } - bool empty() const { return data.empty(); } - - private: - static int parent(int i) { return (i-1)/2; } - static int second_child(int i) { return 2*i+2; } - bool less(const PairType &p1, const PairType &p2) const { - return comp(p1.second, p2.second); - } - - int bubble_up(int hole, PairType p); - int bubble_down(int hole, PairType p, int length); - - void move(const PairType &p, int i) { - data[i] = p; - iim.set(p.first, i); - } - - void rmidx(int h) { - int n = data.size()-1; - if( h>=0 && h<=n ) { - iim.set(data[h].first, POST_HEAP); - if ( h=0 ) - s=0; - return state_enum(s); - } - - }; // class BinHeap - - - template - int BinHeap::bubble_up(int hole, PairType p) { - int par = parent(hole); - while( hole>0 && less(p,data[par]) ) { - move(data[par],hole); - hole = par; - par = parent(hole); - } - move(p, hole); - return hole; - } - - template - int BinHeap::bubble_down(int hole, PairType p, int length) { - int child = second_child(hole); - while(child < length) { - if( less(data[child-1], data[child]) ) { - --child; - } - if( !less(data[child], p) ) - goto ok; - move(data[child], hole); - hole = child; - child = second_child(hole); - } - child--; - if( child