COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2547:f393a8162688 in lemon-0.x


Ignore:
Timestamp:
12/27/07 14:40:16 (16 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3424
Message:

Renaming state_enum to State
Removing "Type" suffix from typedefs
Moving implementation into the class definition

Location:
lemon
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • lemon/bin_heap.h

    r2546 r2547  
    4040  ///one can change the priority of an item, add or erase an item, etc.
    4141  ///
    42   ///\param Prio Type of the priority of the items.
    43   ///\param ItemIntMap A read and writable Item int map, used internally
     42  ///\param _Prio Type of the priority of the items.
     43  ///\param _ItemIntMap A read and writable Item int map, used internally
    4444  ///to handle the cross references.
    45   ///\param Compare A class for the ordering of the priorities. The
    46   ///default is \c std::less<Prio>.
     45  ///\param _Compare A class for the ordering of the priorities. The
     46  ///default is \c std::less<_Prio>.
    4747  ///
    4848  ///\sa FibHeap
    4949  ///\sa Dijkstra
    50   template <typename Prio, typename ItemIntMap,
    51             typename Compare = std::less<Prio> >
     50  template <typename _Prio, typename _ItemIntMap,
     51            typename _Compare = std::less<_Prio> >
    5252  class BinHeap {
    5353
    5454  public:
    55     typedef typename ItemIntMap::Key         ItemType;
    56     typedef Prio                             PrioType;
    57     typedef std::pair<ItemType,PrioType>     PairType;
    58     typedef ItemIntMap                       ItemIntMapType;
    59     typedef Compare                          PrioCompare;
     55    typedef _ItemIntMap ItemIntMap;
     56    typedef _Prio Prio;
     57    typedef typename ItemIntMap::Key Item;
     58    typedef std::pair<Item,Prio> Pair;
     59    typedef _Compare Compare;
    6060
    6161    /// \brief Type to represent the items states.
    … …  
    6767    /// The ItemIntMap \e should be initialized in such way that it maps
    6868    /// PRE_HEAP (-1) to any element to be put in the heap...
    69     enum state_enum {
     69    enum State {
    7070      IN_HEAP = 0,
    7171      PRE_HEAP = -1,
    … …  
    7474
    7575  private:
    76     std::vector<PairType> data;
     76    std::vector<Pair> data;
    7777    Compare comp;
    7878    ItemIntMap &iim;
    … …  
    123123
    124124    static int second_child(int i) { return 2*i+2; }
    125     bool less(const PairType &p1, const PairType &p2) const {
     125    bool less(const Pair &p1, const Pair &p2) const {
    126126      return comp(p1.second, p2.second);
    127127    }
    128128
    129     int bubble_up(int hole, PairType p) {
     129    int bubble_up(int hole, Pair p) {
    130130      int par = parent(hole);
    131131      while( hole>0 && less(p,data[par]) ) {
    … …  
    138138    }
    139139
    140     int bubble_down(int hole, PairType p, int length) {
     140    int bubble_down(int hole, Pair p, int length) {
    141141      int child = second_child(hole);
    142142      while(child < length) {
    … …  
    160160    }
    161161
    162     void move(const PairType &p, int i) {
     162    void move(const Pair &p, int i) {
    163163      data[i] = p;
    164164      iim.set(p.first, i);
    … …  
    170170    /// Adds \c p.first to the heap with priority \c p.second.
    171171    /// \param p The pair to insert.
    172     void push(const PairType &p) {
     172    void push(const Pair &p) {
    173173      int n = data.size();
    174174      data.resize(n+1);
    … …  
    181181    /// \param i The item to insert.
    182182    /// \param p The priority of the item.
    183     void push(const ItemType &i, const Prio &p) { push(PairType(i,p)); }
     183    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    184184
    185185    /// \brief Returns the item with minimum priority relative to \c Compare.
    … …  
    188188    /// Compare. 
    189189    /// \pre The heap must be nonempty. 
    190     ItemType top() const {
     190    Item top() const {
    191191      return data[0].first;
    192192    }
    … …  
    219219    /// \param i The item to erase.
    220220    /// \pre The item should be in the heap.
    221     void erase(const ItemType &i) {
     221    void erase(const Item &i) {
    222222      int h = iim[i];
    223223      int n = data.size()-1;
    … …  
    237237    /// \pre \c i must be in the heap.
    238238    /// \param i The item.
    239     Prio operator[](const ItemType &i) const {
     239    Prio operator[](const Item &i) const {
    240240      int idx = iim[i];
    241241      return data[idx].second;
    … …  
    249249    /// \param i The item.
    250250    /// \param p The priority.
    251     void set(const ItemType &i, const Prio &p) {
     251    void set(const Item &i, const Prio &p) {
    252252      int idx = iim[i];
    253253      if( idx < 0 ) {
    … …  
    255255      }
    256256      else if( comp(p, data[idx].second) ) {
    257         bubble_up(idx, PairType(i,p));
     257        bubble_up(idx, Pair(i,p));
    258258      }
    259259      else {
    260         bubble_down(idx, PairType(i,p), data.size());
     260        bubble_down(idx, Pair(i,p), data.size());
    261261      }
    262262    }
    … …  
    269269    /// \param i The item.
    270270    /// \param p The priority.
    271     void decrease(const ItemType &i, const Prio &p) {
     271    void decrease(const Item &i, const Prio &p) {
    272272      int idx = iim[i];
    273       bubble_up(idx, PairType(i,p));
     273      bubble_up(idx, Pair(i,p));
    274274    }
    275275   
    … …  
    281281    /// \param i The item.
    282282    /// \param p The priority.
    283     void increase(const ItemType &i, const Prio &p) {
     283    void increase(const Item &i, const Prio &p) {
    284284      int idx = iim[i];
    285       bubble_down(idx, PairType(i,p), data.size());
     285      bubble_down(idx, Pair(i,p), data.size());
    286286    }
    287287
    … …  
    294294    /// get back to the heap again.
    295295    /// \param i The item.
    296     state_enum state(const ItemType &i) const {
     296    State state(const Item &i) const {
    297297      int s = iim[i];
    298298      if( s>=0 )
    299299        s=0;
    300       return state_enum(s);
     300      return State(s);
    301301    }
    302302
    … …  
    308308    /// \param i The item.
    309309    /// \param st The state. It should not be \c IN_HEAP.
    310     void state(const ItemType& i, state_enum st) {
     310    void state(const Item& i, State st) {
    311311      switch (st) {
    312312      case POST_HEAP:

  • lemon/bucket_heap.h

    r2391 r2547  
    5050
    5151  public:
     52    /// \e
    5253    typedef typename _ItemIntMap::Key Item;
     54    /// \e
    5355    typedef int Prio;
     56    /// \e
    5457    typedef std::pair<Item, Prio> Pair;
     58    /// \e
    5559    typedef _ItemIntMap ItemIntMap;
    5660
    … …  
    6367    /// The ItemIntMap \e should be initialized in such way that it maps
    6468    /// PRE_HEAP (-1) to any element to be put in the heap...
    65     enum state_enum {
     69    enum State {
    6670      IN_HEAP = 0,
    6771      PRE_HEAP = -1,
    … …  
    279283    /// get back to the heap again.
    280284    /// \param i The item.
    281     state_enum state(const Item &i) const {
     285    State state(const Item &i) const {
    282286      int idx = index[i];
    283287      if (idx >= 0) idx = 0;
    284       return state_enum(idx);
     288      return State(idx);
    285289    }
    286290
    … …  
    292296    /// \param i The item.
    293297    /// \param st The state. It should not be \c IN_HEAP.
    294     void state(const Item& i, state_enum st) {
     298    void state(const Item& i, State st) {
    295299      switch (st) {
    296300      case POST_HEAP:
    … …  
    335339    typedef _ItemIntMap ItemIntMap;
    336340
    337     enum state_enum {
     341    enum State {
    338342      IN_HEAP = 0,
    339343      PRE_HEAP = -1,
    … …  
    473477    }
    474478
    475     state_enum state(const Item &i) const {
     479    State state(const Item &i) const {
    476480      int idx = index[i];
    477481      if (idx >= 0) idx = 0;
    478       return state_enum(idx);
    479     }
    480 
    481     void state(const Item& i, state_enum st) {
     482      return State(idx);
     483    }
     484
     485    void state(const Item& i, State st) {
    482486      switch (st) {
    483487      case POST_HEAP:
    … …  
    547551    /// The ItemIntMap \e should be initialized in such way that it maps
    548552    /// PRE_HEAP (-1) to any element to be put in the heap...
    549     enum state_enum {
     553    enum State {
    550554      IN_HEAP = 0,
    551555      PRE_HEAP = -1,
    … …  
    684688    /// get back to the heap again.
    685689    /// \param i The item.
    686     state_enum state(const Item &i) const {
     690    State state(const Item &i) const {
    687691      int idx = index[i];
    688692      if (idx >= 0) idx = 0;
    689       return state_enum(idx);
     693      return State(idx);
    690694    }
    691695
    … …  
    717721    typedef _ItemIntMap ItemIntMap;
    718722
    719     enum state_enum {
     723    enum State {
    720724      IN_HEAP = 0,
    721725      PRE_HEAP = -1,
    … …  
    799803    }
    800804
    801     state_enum state(const Item &i) const {
     805    State state(const Item &i) const {
    802806      int idx = index[i];
    803807      if (idx >= 0) idx = 0;
    804       return state_enum(idx);
     808      return State(idx);
    805809    }
    806810

  • lemon/concepts/heap.h

    r2391 r2547  
    5353      /// The ItemIntMap _should_ be initialized in such way, that it maps
    5454      /// PRE_HEAP (-1) to any element to be put in the heap...
    55       enum state_enum {
     55      enum State {
    5656        IN_HEAP = 0,
    5757        PRE_HEAP = -1,
    … …  
    156156      /// get back to the heap again.
    157157      /// \param i The item.
    158       state_enum state(const Item &i) const {}
     158      State state(const Item &i) const {}
    159159
    160160      /// \brief Sets the state of the \c item in the heap.
    … …  
    165165      /// \param i The item.
    166166      /// \param st The state. It should not be \c IN_HEAP.
    167       void state(const Item& i, state_enum st) {}
     167      void state(const Item& i, State st) {}
    168168
    169169
    … …  
    182182          ignore_unused_variable_warning(prio);
    183183
    184           typedef typename _Heap::state_enum state_enum;
    185           state_enum state;
     184          typedef typename _Heap::State State;
     185          State state;
    186186
    187187          ignore_unused_variable_warning(state);

  • lemon/fib_heap.h

    r2529 r2547  
    4242  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
    4343  ///heap. In case of many calls to these operations, it is better to use a
    44   ///\e binary \e heap.
     44  ///\ref BinHeap "binary heap".
    4545  ///
    46   ///\param Prio Type of the priority of the items.
    47   ///\param ItemIntMap A read and writable Item int map, used internally
     46  ///\param _Prio Type of the priority of the items.
     47  ///\param _ItemIntMap A read and writable Item int map, used internally
    4848  ///to handle the cross references.
    49   ///\param Compare A class for the ordering of the priorities. The
    50   ///default is \c std::less<Prio>.
     49  ///\param _Compare A class for the ordering of the priorities. The
     50  ///default is \c std::less<_Prio>.
    5151  ///
    5252  ///\sa BinHeap
    … …  
    5555 
    5656#ifdef DOXYGEN
    57   template <typename Prio,
    58             typename ItemIntMap,
    59             typename Compare>
     57  template <typename _Prio,
     58            typename _ItemIntMap,
     59            typename _Compare>
    6060#else
    61   template <typename Prio,
    62             typename ItemIntMap,
    63             typename Compare = std::less<Prio> >
     61  template <typename _Prio,
     62            typename _ItemIntMap,
     63            typename _Compare = std::less<_Prio> >
    6464#endif
    6565  class FibHeap {
    6666  public:
     67    typedef _ItemIntMap ItemIntMap;
     68    typedef _Prio Prio;
    6769    typedef typename ItemIntMap::Key Item;
    68     typedef Prio PrioType;
     70    typedef std::pair<Item,Prio> Pair;
     71    typedef _Compare Compare;
    6972   
    7073  private:
    … …  
    7982  public:
    8083    ///Status of the nodes
    81     enum state_enum {
     84    enum State {
    8285      ///The node is in the heap
    8386      IN_HEAP = 0,
    … …  
    100103    /// internally to handle the cross references. \c _comp is an
    101104    /// object for ordering of the priorities.
    102     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
    103                   iimap(_iimap), comp(_comp), num_items() {}
     105    FibHeap(ItemIntMap &_iimap, const Compare &_comp)
     106      : minimum(0), iimap(_iimap), comp(_comp), num_items() {}
    104107   
    105108    /// \brief The number of items stored in the heap.
    … …  
    129132    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
    130133    /// \ref increase(\c item, \c value) otherwise.
    131     void set (Item const item, PrioType const value);
     134    void set (const Item& item, const Prio& value) {
     135      int i=iimap[item];
     136      if ( i >= 0 && container[i].in ) {
     137        if ( comp(value, container[i].prio) ) decrease(item, value);
     138        if ( comp(container[i].prio, value) ) increase(item, value);
     139      } else push(item, value);
     140    }
    132141   
    133142    /// \brief Adds \c item to the heap with priority \c value.
    … …  
    135144    /// Adds \c item to the heap with priority \c value.
    136145    /// \pre \c item must not be stored in the heap.
    137     void push (Item const item, PrioType const value);
    138    
    139     /// \brief Returns the item with minimum priority relative to \c Compare.
    140     ///
    141     /// This method returns the item with minimum priority relative to \c
    142     /// Compare. 
    143     /// \pre The heap must be nonempty. 
    144     Item top() const { return container[minimum].name; }
    145 
    146     /// \brief Returns the minimum priority relative to \c Compare.
    147     ///
    148     /// It returns the minimum priority relative to \c Compare.
    149     /// \pre The heap must be nonempty.
    150     PrioType prio() const { return container[minimum].prio; }
    151    
    152     /// \brief Returns the priority of \c item.
    153     ///
    154     /// This function returns the priority of \c item.
    155     /// \pre \c item must be in the heap.
    156     PrioType& operator[](const Item& item) {
    157       return container[iimap[item]].prio;
    158     }
    159    
    160     /// \brief Returns the priority of \c item.
    161     ///
    162     /// It returns the priority of \c item.
    163     /// \pre \c item must be in the heap.
    164     const PrioType& operator[](const Item& item) const {
    165       return container[iimap[item]].prio;
    166     }
    167 
    168 
    169     /// \brief Deletes the item with minimum priority relative to \c Compare.
    170     ///
    171     /// This method deletes the item with minimum priority relative to \c
    172     /// Compare from the heap. 
    173     /// \pre The heap must be non-empty. 
    174     void pop();
    175 
    176     /// \brief Deletes \c item from the heap.
    177     ///
    178     /// This method deletes \c item from the heap, if \c item was already
    179     /// stored in the heap. It is quite inefficient in Fibonacci heaps.
    180     void erase (const Item& item);
    181 
    182     /// \brief Decreases the priority of \c item to \c value.
    183     ///
    184     /// This method decreases the priority of \c item to \c value.
    185     /// \pre \c item must be stored in the heap with priority at least \c
    186     ///   value relative to \c Compare.
    187     void decrease (Item item, PrioType const value);
    188 
    189     /// \brief Increases the priority of \c item to \c value.
    190     ///
    191     /// This method sets the priority of \c item to \c value. Though
    192     /// there is no precondition on the priority of \c item, this
    193     /// method should be used only if it is indeed necessary to increase
    194     /// (relative to \c Compare) the priority of \c item, because this
    195     /// method is inefficient.
    196     void increase (Item item, PrioType const value) {
    197       erase(item);
    198       push(item, value);
    199     }
    200 
    201 
    202     /// \brief Returns if \c item is in, has already been in, or has never
    203     /// been in the heap.
    204     ///
    205     /// This method returns PRE_HEAP if \c item has never been in the
    206     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    207     /// otherwise. In the latter case it is possible that \c item will
    208     /// get back to the heap again.
    209     state_enum state(const Item &item) const {
    210       int i=iimap[item];
    211       if( i>=0 ) {
    212         if ( container[i].in ) i=0;
    213         else i=-2;
    214       }
    215       return state_enum(i);
    216     }   
    217 
    218     /// \brief Sets the state of the \c item in the heap.
    219     ///
    220     /// Sets the state of the \c item in the heap. It can be used to
    221     /// manually clear the heap when it is important to achive the
    222     /// better time complexity.
    223     /// \param i The item.
    224     /// \param st The state. It should not be \c IN_HEAP.
    225     void state(const Item& i, state_enum st) {
    226       switch (st) {
    227       case POST_HEAP:
    228       case PRE_HEAP:
    229         if (state(i) == IN_HEAP) {
    230           erase(i);
    231         }
    232         iimap[i] = st;
    233         break;
    234       case IN_HEAP:
    235         break;
    236       }
    237     }
    238    
    239   private:
    240    
    241     void balance();
    242     void makeroot(int c);
    243     void cut(int a, int b);
    244     void cascade(int a);
    245     void fuse(int a, int b);
    246     void unlace(int a);
    247 
    248 
    249     class store {
    250       friend class FibHeap;
    251      
    252       Item name;
    253       int parent;
    254       int left_neighbor;
    255       int right_neighbor;
    256       int child;
    257       int degree; 
    258       bool marked;
    259       bool in;
    260       PrioType prio;
    261      
    262       store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
    263     };
    264   };   
    265  
    266 
    267 
    268     // **********************************************************************
    269     //  IMPLEMENTATIONS
    270     // **********************************************************************
    271    
    272   template <typename Prio, typename ItemIntMap,
    273     typename Compare>
    274   void FibHeap<Prio, ItemIntMap, Compare>::set
    275   (Item const item, PrioType const value)
    276   {
    277     int i=iimap[item];
    278     if ( i >= 0 && container[i].in ) {
    279       if ( comp(value, container[i].prio) ) decrease(item, value);
    280       if ( comp(container[i].prio, value) ) increase(item, value);
    281     } else push(item, value);
    282   }
    283    
    284   template <typename Prio, typename ItemIntMap,
    285     typename Compare>
    286   void FibHeap<Prio, ItemIntMap, Compare>::push
    287   (Item const item, PrioType const value) {
     146    void push (const Item& item, const Prio& value) {
    288147      int i=iimap[item];     
    289148      if ( i < 0 ) {
    … …  
    315174    }
    316175   
    317   template <typename Prio, typename ItemIntMap,
    318     typename Compare>
    319   void FibHeap<Prio, ItemIntMap, Compare>::pop() {
     176    /// \brief Returns the item with minimum priority relative to \c Compare.
     177    ///
     178    /// This method returns the item with minimum priority relative to \c
     179    /// Compare. 
     180    /// \pre The heap must be nonempty. 
     181    Item top() const { return container[minimum].name; }
     182
     183    /// \brief Returns the minimum priority relative to \c Compare.
     184    ///
     185    /// It returns the minimum priority relative to \c Compare.
     186    /// \pre The heap must be nonempty.
     187    const Prio& prio() const { return container[minimum].prio; }
     188       
     189    /// \brief Returns the priority of \c item.
     190    ///
     191    /// It returns the priority of \c item.
     192    /// \pre \c item must be in the heap.
     193    const Prio& operator[](const Item& item) const {
     194      return container[iimap[item]].prio;
     195    }
     196
     197    /// \brief Deletes the item with minimum priority relative to \c Compare.
     198    ///
     199    /// This method deletes the item with minimum priority relative to \c
     200    /// Compare from the heap. 
     201    /// \pre The heap must be non-empty. 
     202    void pop() {
    320203      /*The first case is that there are only one root.*/
    321204      if ( container[minimum].left_neighbor==minimum ) {
    … …  
    334217          int child=container[minimum].child;
    335218          int last_child=container[child].left_neighbor;
    336        
     219         
    337220          makeroot(child);
    338221         
    … …  
    348231    }
    349232
    350 
    351   template <typename Prio, typename ItemIntMap,
    352     typename Compare>
    353   void FibHeap<Prio, ItemIntMap, Compare>::erase
    354   (const Item& item) {
     233    /// \brief Deletes \c item from the heap.
     234    ///
     235    /// This method deletes \c item from the heap, if \c item was already
     236    /// stored in the heap. It is quite inefficient in Fibonacci heaps.
     237    void erase (const Item& item) {
    355238      int i=iimap[item];
    356239     
    … …  
    364247        pop();
    365248      }
    366   }
    367    
    368   template <typename Prio, typename ItemIntMap,
    369     typename Compare>
    370   void FibHeap<Prio, ItemIntMap, Compare>::decrease
    371   (Item item, PrioType const value) {
     249    }
     250
     251    /// \brief Decreases the priority of \c item to \c value.
     252    ///
     253    /// This method decreases the priority of \c item to \c value.
     254    /// \pre \c item must be stored in the heap with priority at least \c
     255    ///   value relative to \c Compare.
     256    void decrease (Item item, const Prio& value) {
    372257      int i=iimap[item];
    373258      container[i].prio=value;
    … …  
    379264      }     
    380265      if ( comp(value, container[minimum].prio) ) minimum=i;
    381   }
    382  
    383 
    384   template <typename Prio, typename ItemIntMap,
    385     typename Compare>
    386   void FibHeap<Prio, ItemIntMap, Compare>::balance() {     
    387 
    388     int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
     266    }
     267
     268    /// \brief Increases the priority of \c item to \c value.
     269    ///
     270    /// This method sets the priority of \c item to \c value. Though
     271    /// there is no precondition on the priority of \c item, this
     272    /// method should be used only if it is indeed necessary to increase
     273    /// (relative to \c Compare) the priority of \c item, because this
     274    /// method is inefficient.
     275    void increase (Item item, const Prio& value) {
     276      erase(item);
     277      push(item, value);
     278    }
     279
     280
     281    /// \brief Returns if \c item is in, has already been in, or has never
     282    /// been in the heap.
     283    ///
     284    /// This method returns PRE_HEAP if \c item has never been in the
     285    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     286    /// otherwise. In the latter case it is possible that \c item will
     287    /// get back to the heap again.
     288    State state(const Item &item) const {
     289      int i=iimap[item];
     290      if( i>=0 ) {
     291        if ( container[i].in ) i=0;
     292        else i=-2;
     293      }
     294      return State(i);
     295    }   
     296
     297    /// \brief Sets the state of the \c item in the heap.
     298    ///
     299    /// Sets the state of the \c item in the heap. It can be used to
     300    /// manually clear the heap when it is important to achive the
     301    /// better time complexity.
     302    /// \param i The item.
     303    /// \param st The state. It should not be \c IN_HEAP.
     304    void state(const Item& i, State st) {
     305      switch (st) {
     306      case POST_HEAP:
     307      case PRE_HEAP:
     308        if (state(i) == IN_HEAP) {
     309          erase(i);
     310        }
     311        iimap[i] = st;
     312        break;
     313      case IN_HEAP:
     314        break;
     315      }
     316    }
     317   
     318  private:
     319   
     320    void balance() {
     321
     322      int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
    389323 
    390     std::vector<int> A(maxdeg,-1);
    391    
    392     /*
    393      *Recall that now minimum does not point to the minimum prio element.
    394      *We set minimum to this during balance().
    395      */
    396     int anchor=container[minimum].left_neighbor;
    397     int next=minimum;
    398     bool end=false;
     324      std::vector<int> A(maxdeg,-1);
     325   
     326      /*
     327       *Recall that now minimum does not point to the minimum prio element.
     328       *We set minimum to this during balance().
     329       */
     330      int anchor=container[minimum].left_neighbor;
     331      int next=minimum;
     332      bool end=false;
    399333       
    400        do {
     334      do {
    401335        int active=next;
    402336        if ( anchor==active ) end=true;
    … …  
    415349        }       
    416350        A[d]=active;
    417        } while ( !end );
    418 
    419 
    420        while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
    421        int s=minimum;
    422        int m=minimum;
    423        do { 
    424          if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
    425          s=container[s].right_neighbor;
    426        } while ( s != m );
    427     }
    428 
    429   template <typename Prio, typename ItemIntMap,
    430     typename Compare>
    431   void FibHeap<Prio, ItemIntMap, Compare>::makeroot
    432   (int c) {
     351      } while ( !end );
     352
     353
     354      while ( container[minimum].parent >=0 )
     355        minimum=container[minimum].parent;
     356      int s=minimum;
     357      int m=minimum;
     358      do { 
     359        if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
     360        s=container[s].right_neighbor;
     361      } while ( s != m );
     362    }
     363
     364    void makeroot(int c) {
    433365      int s=c;
    434366      do { 
    … …  
    437369      } while ( s != c );
    438370    }
    439  
    440  
    441   template <typename Prio, typename ItemIntMap,
    442     typename Compare>
    443   void FibHeap<Prio, ItemIntMap, Compare>::cut
    444   (int a, int b) {   
    445     /*
    446      *Replacing a from the children of b.
    447      */
    448     --container[b].degree;
    449    
    450     if ( container[b].degree !=0 ) {
    451       int child=container[b].child;
    452       if ( child==a )
    453         container[b].child=container[child].right_neighbor;
    454       unlace(a);
    455     }
    456    
    457    
    458     /*Lacing a to the roots.*/
    459     int right=container[minimum].right_neighbor;
    460     container[minimum].right_neighbor=a;
    461     container[a].left_neighbor=minimum;
    462     container[a].right_neighbor=right;
    463     container[right].left_neighbor=a;
    464    
    465     container[a].parent=-1;
    466     container[a].marked=false;
    467   }
    468  
    469 
    470   template <typename Prio, typename ItemIntMap,
    471     typename Compare>
    472   void FibHeap<Prio, ItemIntMap, Compare>::cascade
    473   (int a)
    474     {
     371
     372    void cut(int a, int b) {
     373      /*
     374       *Replacing a from the children of b.
     375       */
     376      --container[b].degree;
     377   
     378      if ( container[b].degree !=0 ) {
     379        int child=container[b].child;
     380        if ( child==a )
     381          container[b].child=container[child].right_neighbor;
     382        unlace(a);
     383      }
     384   
     385   
     386      /*Lacing a to the roots.*/
     387      int right=container[minimum].right_neighbor;
     388      container[minimum].right_neighbor=a;
     389      container[a].left_neighbor=minimum;
     390      container[a].right_neighbor=right;
     391      container[right].left_neighbor=a;
     392   
     393      container[a].parent=-1;
     394      container[a].marked=false;
     395    }
     396
     397    void cascade(int a) {
    475398      if ( container[a].parent!=-1 ) {
    476399        int p=container[a].parent;
    … …  
    484407    }
    485408
    486 
    487   template <typename Prio, typename ItemIntMap,
    488     typename Compare>
    489   void FibHeap<Prio, ItemIntMap, Compare>::fuse
    490   (int a, int b) {
     409    void fuse(int a, int b) {
    491410      unlace(b);
    492411     
    … …  
    512431    }
    513432
    514  
    515   /*
    516    *It is invoked only if a has siblings.
    517    */
    518   template <typename Prio, typename ItemIntMap,
    519     typename Compare>
    520   void FibHeap<Prio, ItemIntMap, Compare>::unlace
    521   (int a) {     
     433    /*
     434     *It is invoked only if a has siblings.
     435     */
     436    void unlace(int a) {
    522437      int leftn=container[a].left_neighbor;
    523438      int rightn=container[a].right_neighbor;
    524439      container[leftn].right_neighbor=rightn;
    525440      container[rightn].left_neighbor=leftn;
    526   }
    527  
     441    }
     442
     443
     444    class store {
     445      friend class FibHeap;
     446     
     447      Item name;
     448      int parent;
     449      int left_neighbor;
     450      int right_neighbor;
     451      int child;
     452      int degree; 
     453      bool marked;
     454      bool in;
     455      Prio prio;
     456     
     457      store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
     458    };
     459  };   
    528460
    529461} //namespace lemon

  • lemon/radix_heap.h

    r2391 r2547  
    2929namespace lemon {
    3030
    31   /// \brief Exception thrown by RadixHeap.
    32   /// 
    33   /// This Exception is thrown when a smaller priority
    34   /// is inserted into the \e RadixHeap then the last time erased.
    35   /// \see RadixHeap
    36   /// \author Balazs Dezso
    37 
    38   class UnderFlowPriorityError : public RuntimeError {
    39   public:
    40     virtual const char* what() const throw() {
    41       return "lemon::UnderFlowPriorityError";
    42     } 
    43   };
    4431
    4532  /// \ingroup auxdata
    … …  
    7057    typedef _ItemIntMap ItemIntMap;
    7158
     59    /// \brief Exception thrown by RadixHeap.
     60    /// 
     61    /// This Exception is thrown when a smaller priority
     62    /// is inserted into the \e RadixHeap then the last time erased.
     63    /// \see RadixHeap
     64    /// \author Balazs Dezso
     65   
     66    class UnderFlowPriorityError : public RuntimeError {
     67    public:
     68      virtual const char* what() const throw() {
     69        return "lemon::RadixHeap::UnderFlowPriorityError";
     70      } 
     71    };
     72
    7273    /// \brief Type to represent the items states.
    7374    ///
    … …  
    7879    /// The ItemIntMap \e should be initialized in such way that it maps
    7980    /// PRE_HEAP (-1) to any element to be put in the heap...
    80     enum state_enum {
     81    enum State {
    8182      IN_HEAP = 0,
    8283      PRE_HEAP = -1,
    … …  
    402403    /// get back to the heap again.
    403404    /// \param i The item.
    404     state_enum state(const Item &i) const {
     405    State state(const Item &i) const {
    405406      int s = iim[i];
    406407      if( s >= 0 ) s = 0;
    407       return state_enum(s);
     408      return State(s);
    408409    }
    409410
    … …  
    415416    /// \param i The item.
    416417    /// \param st The state. It should not be \c IN_HEAP.
    417     void state(const Item& i, state_enum st) {
     418    void state(const Item& i, State st) {
    418419      switch (st) {
    419420      case POST_HEAP:
Note: See TracChangeset for help on using the changeset viewer.