COIN-OR::LEMON - Graph Library

Changeset 172:c645f4a2a6ae in lemon-0.x for src/include/bin_heap.hh


Ignore:
Timestamp:
03/11/04 20:24:28 (16 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@245
Message:

Uj kupac nevezektan

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/include/bin_heap.hh

    r114 r172  
    77/******
    88 *
    9  * BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
    10  *
    11  * Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
     9 * BinHeap<ItemType, PrioType, ItemIntMap, [PrioCompare]>
     10 *
     11 * Ez az osztaly item-prioritas parok tarolasara alkalmas binaris kupacot
    1212 * valosit meg.
    13  * A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a
     13 * A kupacban legfolul mindig az a par talalhato, amiben a prioritas a
    1414 * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
    1515 * lett keszitve...)
    1616 *
    17  * Megjegyzes: egy kicsit gyanus nekem, hogy a kupacos temakorben nem
    18  * azt hivjak kulcsnak, amit most en annak nevezek. :) En olyan
    19  * property_map -os ertelemben hasznalom.
     17 * Megjegyzes: a kupacos temakorokben a prioritast kulcsnak szoktak nevezni,
     18 * de mivel ez zavaro tud lenni a property-map-es kulcs-ertek szohasznalata
     19 * miatt, megprobaltunk valami semleges elnevezeseket kitalalni.
    2020 *
    2121 * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
    22  * a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto
     22 * az itemekhez egy int-et tud tarolni (ezzel tudom megkeresni az illeto
    2323 * elemet a kupacban a csokkentes es hasonlo muveletekhez).
    2424 * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
     
    2727 * Ketfele modon hasznalhato:
    2828 * Lusta mod:
    29  * put(Key, Value) metodussal pakolunk a kupacba,
     29 * set(Item, Prio) metodussal pakolunk a kupacba,
    3030 * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
    3131 * csokkentettunk-e rajta, vagy noveltunk.
     
    3636 *  mar kikerult a kupacbol POST_HEAP=-2).
    3737 * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
    38  * meg meg tudja mondani a "legkisebb" erteku elemet. De csak nagyjabol,
     38 * meg meg tudja mondani a "legkisebb" prioritasu elemet. De csak nagyjabol,
    3939 * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
    4040 *
    4141 * Kozvetlen mod:
    42  * push(Key, Value) metodussal belerakunk a kupacba (ha az illeto kulcs mar
     42 * push(Item, Prio) metodussal belerakunk a kupacba (ha az illeto kulcs mar
    4343 * benn volt, akkor gaz).
    44  * increase/decrease(Key k, Value new_value) metodusokkal lehet
    45  * novelni/csokkenteni az illeto kulcshoz tartozo erteket. (Ha nem volt meg
    46  * benne a kupacban az illeto kulcs, vagy nem abba az iranyba valtoztattad
     44 * increase/decrease(Item i, Prio new_prio) metodusokkal lehet
     45 * novelni/csokkenteni az illeto elemhez tartozo prioritast. (Ha nem volt
     46 * megbenne a kupacban az illeto elem, vagy nem abba az iranyba valtoztattad
    4747 * az erteket, amerre mondtad -- gaz).
    4848 *
     
    6666namespace hugo {
    6767
    68   template <typename Key, typename Val, typename KeyIntMap,
    69             typename Compare = std::less<Val> >
     68  template <typename Item, typename Prio, typename ItemIntMap,
     69            typename Compare = std::less<Prio> >
    7070  class BinHeap {
    7171
    7272  public:
    73     typedef Key              KeyType;
     73    typedef Item                             ItemType;
    7474    // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
    75     typedef Val              ValueType;
    76     typedef std::pair<KeyType,ValueType>     PairType;
    77     typedef KeyIntMap        KeyIntMapType;
    78     typedef Compare          ValueCompare;
     75    typedef Prio                             PrioType;
     76    typedef std::pair<ItemType,PrioType>     PairType;
     77    typedef ItemIntMap                       ItemIntMapType;
     78    typedef Compare                          PrioCompare;
    7979
    8080    /**
    81      * Each Key element have a state associated to it. It may be "in heap",
     81     * Each Item element have a state associated to it. It may be "in heap",
    8282     * "pre heap" or "post heap". The later two are indifferent from the
    8383     * heap's point of view, but may be useful to the user.
    8484     *
    85      * The KeyIntMap _should_ be initialized in such way, that it maps
     85     * The ItemIntMap _should_ be initialized in such way, that it maps
    8686     * PRE_HEAP (-1) to any element to be put in the heap...
    8787     */
     
    9696    Compare comp;
    9797    // FIXME: jo ez igy???
    98     KeyIntMap &kim;
     98    ItemIntMap &iim;
    9999
    100100  public:
    101     BinHeap(KeyIntMap &_kim) : kim(_kim) {}
    102     BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
     101    BinHeap(ItemIntMap &_iim) : iim(_iim) {}
     102    BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
    103103
    104104
     
    118118    void move(const PairType &p, int i) {
    119119      data[i] = p;
    120       kim.put(p.first, i);
     120      iim.set(p.first, i);
    121121    }
    122122
     
    124124      int n = data.size()-1;
    125125      if( h>=0 && h<=n ) {
    126         kim.put(data[h].first, POST_HEAP);
     126        iim.set(data[h].first, POST_HEAP);
    127127        if ( h<n ) {
    128128          bubble_down(h, data[n], n);
     
    138138      bubble_up(n, p);
    139139    }
    140     void push(const Key &k, const Val &v) { push(PairType(k,v)); }
    141 
    142     Key top() const {
     140    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
     141
     142    Item top() const {
    143143      // FIXME: test size>0 ?
    144144      return data[0].first;
    145145    }
    146     Val topValue() const {
     146    Prio topPrio() const {
    147147      // FIXME: test size>0 ?
    148148      return data[0].second;
     
    153153    }
    154154
    155     void erase(const Key &k) {
    156       rmidx(kim.get(k));
    157     }
    158 
    159     const Val get(const Key &k) const {
    160       int idx = kim.get(k);
     155    void erase(const Item &i) {
     156      rmidx(iim.get(i));
     157    }
     158
     159    const Prio get(const Item &i) const {
     160      int idx = iim.get(i);
    161161      return data[idx].second;
    162162    }
    163     void put(const Key &k, const Val &v) {
    164       int idx = kim.get(k);
     163    void set(const Item &i, const Prio &p) {
     164      int idx = iim.get(i);
    165165      if( idx < 0 ) {
    166         push(k,v);
    167       }
    168       else if( comp(v, data[idx].second) ) {
    169         bubble_up(idx, PairType(k,v));
     166        push(i,p);
     167      }
     168      else if( comp(p, data[idx].second) ) {
     169        bubble_up(idx, PairType(i,p));
    170170      }
    171171      else {
    172         bubble_down(idx, PairType(k,v), data.size());
    173       }
    174     }
    175 
    176     void decrease(const Key &k, const Val &v) {
    177       int idx = kim.get(k);
    178       bubble_up(idx, PairType(k,v));
    179     }
    180     void increase(const Key &k, const Val &v) {
    181       int idx = kim.get(k);
    182       bubble_down(idx, PairType(k,v), data.size());
    183     }
    184 
    185     state_enum state(const Key &k) const {
    186       int s = kim.get(k);
     172        bubble_down(idx, PairType(i,p), data.size());
     173      }
     174    }
     175
     176    void decrease(const Item &i, const Prio &p) {
     177      int idx = iim.get(i);
     178      bubble_up(idx, PairType(i,p));
     179    }
     180    void increase(const Item &i, const Prio &p) {
     181      int idx = iim.get(i);
     182      bubble_down(idx, PairType(i,p), data.size());
     183    }
     184
     185    state_enum state(const Item &i) const {
     186      int s = iim.get(i);
    187187      if( s>=0 )
    188188        s=0;
Note: See TracChangeset for help on using the changeset viewer.