COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 750:bb3392fe91f2 in lemon for lemon/binom_heap.h


Ignore:
Timestamp:
07/09/09 04:07:08 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improve and unify the doc + names in the new heaps (#301)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/binom_heap.h

    r748 r750  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2121
    2222///\file
    23 ///\ingroup auxdat
     23///\ingroup heaps
    2424///\brief Binomial Heap implementation.
    2525
    2626#include <vector>
     27#include <utility>
    2728#include <functional>
    2829#include <lemon/math.h>
    … …  
    3132namespace lemon {
    3233
    33   /// \ingroup auxdat
     34  /// \ingroup heaps
    3435  ///
    35   ///\brief Binomial Heap.
     36  ///\brief Binomial heap data structure.
    3637  ///
    37   ///This class implements the \e Binomial \e heap data structure. A \e heap
    38   ///is a data structure for storing items with specified values called \e
    39   ///priorities in such a way that finding the item with minimum priority is
    40   ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    41   ///one can change the priority of an item, add or erase an item, etc.
     38  /// This class implements the \e binomial \e heap data structure.
     39  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4240  ///
    43   ///The methods \ref increase and \ref erase are not efficient in a Binomial
    44   ///heap. In case of many calls to these operations, it is better to use a
    45   ///\ref BinHeap "binary heap".
     41  /// The methods \ref increase() and \ref erase() are not efficient
     42  /// in a binomial heap. In case of many calls of these operations,
     43  /// it is better to use other heap structure, e.g. \ref BinHeap
     44  /// "binary heap".
    4645  ///
    47   ///\param _Prio Type of the priority of the items.
    48   ///\param _ItemIntMap A read and writable Item int map, used internally
    49   ///to handle the cross references.
    50   ///\param _Compare A class for the ordering of the priorities. The
    51   ///default is \c std::less<_Prio>.
    52   ///
    53   ///\sa BinHeap
    54   ///\sa Dijkstra
    55   ///\author Dorian Batha
    56 
     46  /// \tparam PR Type of the priorities of the items.
     47  /// \tparam IM A read-writable item map with \c int values, used
     48  /// internally to handle the cross references.
     49  /// \tparam CMP A functor class for comparing the priorities.
     50  /// The default is \c std::less<PR>.
    5751#ifdef DOXYGEN
    58   template <typename _Prio,
    59             typename _ItemIntMap,
    60             typename _Compare>
     52  template <typename PR, typename IM, typename CMP>
    6153#else
    62   template <typename _Prio,
    63             typename _ItemIntMap,
    64             typename _Compare = std::less<_Prio> >
     54  template <typename PR, typename IM, typename CMP = std::less<PR> >
    6555#endif
    6656  class BinomHeap {
    6757  public:
    68     typedef _ItemIntMap ItemIntMap;
    69     typedef _Prio Prio;
     58    /// Type of the item-int map.
     59    typedef IM ItemIntMap;
     60    /// Type of the priorities.
     61    typedef PR Prio;
     62    /// Type of the items stored in the heap.
    7063    typedef typename ItemIntMap::Key Item;
    71     typedef std::pair<Item,Prio> Pair;
    72     typedef _Compare Compare;
     64    /// Functor type for comparing the priorities.
     65    typedef CMP Compare;
     66
     67    /// \brief Type to represent the states of the items.
     68    ///
     69    /// Each item has a state associated to it. It can be "in heap",
     70    /// "pre-heap" or "post-heap". The latter two are indifferent from the
     71    /// heap's point of view, but may be useful to the user.
     72    ///
     73    /// The item-int map must be initialized in such way that it assigns
     74    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
     75    enum State {
     76      IN_HEAP = 0,    ///< = 0.
     77      PRE_HEAP = -1,  ///< = -1.
     78      POST_HEAP = -2  ///< = -2.
     79    };
    7380
    7481  private:
    7582    class store;
    7683
    77     std::vector<store> container;
    78     int minimum, head;
    79     ItemIntMap &iimap;
    80     Compare comp;
    81     int num_items;
     84    std::vector<store> _data;
     85    int _min, _head;
     86    ItemIntMap &_iim;
     87    Compare _comp;
     88    int _num_items;
    8289
    8390  public:
    84     ///Status of the nodes
    85     enum State {
    86       ///The node is in the heap
    87       IN_HEAP = 0,
    88       ///The node has never been in the heap
    89       PRE_HEAP = -1,
    90       ///The node was in the heap but it got out of it
    91       POST_HEAP = -2
    92     };
    93 
    94     /// \brief The constructor
    95     ///
    96     /// \c _iimap should be given to the constructor, since it is
    97     ///   used internally to handle the cross references.
    98     explicit BinomHeap(ItemIntMap &_iimap)
    99       : minimum(0), head(-1), iimap(_iimap), num_items() {}
    100 
    101     /// \brief The constructor
    102     ///
    103     /// \c _iimap should be given to the constructor, since it is used
    104     /// internally to handle the cross references. \c _comp is an
    105     /// object for ordering of the priorities.
    106     BinomHeap(ItemIntMap &_iimap, const Compare &_comp)
    107       : minimum(0), head(-1), iimap(_iimap), comp(_comp), num_items() {}
     91    /// \brief Constructor.
     92    ///
     93    /// Constructor.
     94    /// \param map A map that assigns \c int values to the items.
     95    /// It is used internally to handle the cross references.
     96    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     97    explicit BinomHeap(ItemIntMap &map)
     98      : _min(0), _head(-1), _iim(map), _num_items(0) {}
     99
     100    /// \brief Constructor.
     101    ///
     102    /// Constructor.
     103    /// \param map A map that assigns \c int values to the items.
     104    /// It is used internally to handle the cross references.
     105    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     106    /// \param comp The function object used for comparing the priorities.
     107    BinomHeap(ItemIntMap &map, const Compare &comp)
     108      : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
    108109
    109110    /// \brief The number of items stored in the heap.
    110111    ///
    111     /// Returns the number of items stored in the heap.
    112     int size() const { return num_items; }
    113 
    114     /// \brief Checks if the heap stores no items.
    115     ///
    116     ///   Returns \c true if and only if the heap stores no items.
    117     bool empty() const { return num_items==0; }
    118 
    119     /// \brief Make empty this heap.
    120     ///
    121     /// Make empty this heap. It does not change the cross reference
    122     /// map.  If you want to reuse a heap what is not surely empty you
    123     /// should first clear the heap and after that you should set the
    124     /// cross reference map for each item to \c PRE_HEAP.
     112    /// This function returns the number of items stored in the heap.
     113    int size() const { return _num_items; }
     114
     115    /// \brief Check if the heap is empty.
     116    ///
     117    /// This function returns \c true if the heap is empty.
     118    bool empty() const { return _num_items==0; }
     119
     120    /// \brief Make the heap empty.
     121    ///
     122    /// This functon makes the heap empty.
     123    /// It does not change the cross reference map. If you want to reuse
     124    /// a heap that is not surely empty, you should first clear it and
     125    /// then you should set the cross reference map to \c PRE_HEAP
     126    /// for each item.
    125127    void clear() {
    126       container.clear(); minimum=0; num_items=0; head=-1;
    127     }
    128 
    129     /// \brief \c item gets to the heap with priority \c value independently
    130     /// if \c item was already there.
    131     ///
    132     /// This method calls \ref push(\c item, \c value) if \c item is not
    133     /// stored in the heap and it calls \ref decrease(\c item, \c value) or
    134     /// \ref increase(\c item, \c value) otherwise.
     128      _data.clear(); _min=0; _num_items=0; _head=-1;
     129    }
     130
     131    /// \brief Set the priority of an item or insert it, if it is
     132    /// not stored in the heap.
     133    ///
     134    /// This method sets the priority of the given item if it is
     135    /// already stored in the heap. Otherwise it inserts the given
     136    /// item into the heap with the given priority.
     137    /// \param item The item.
     138    /// \param value The priority.
    135139    void set (const Item& item, const Prio& value) {
    136       int i=iimap[item];
    137       if ( i >= 0 && container[i].in ) {
    138         if ( comp(value, container[i].prio) ) decrease(item, value);
    139         if ( comp(container[i].prio, value) ) increase(item, value);
     140      int i=_iim[item];
     141      if ( i >= 0 && _data[i].in ) {
     142        if ( _comp(value, _data[i].prio) ) decrease(item, value);
     143        if ( _comp(_data[i].prio, value) ) increase(item, value);
    140144      } else push(item, value);
    141145    }
    142146
    143     /// \brief Adds \c item to the heap with priority \c value.
    144     ///
    145     /// Adds \c item to the heap with priority \c value.
    146     /// \pre \c item must not be stored in the heap.
     147    /// \brief Insert an item into the heap with the given priority.
     148    ///
     149    /// This function inserts the given item into the heap with the
     150    /// given priority.
     151    /// \param item The item to insert.
     152    /// \param value The priority of the item.
     153    /// \pre \e item must not be stored in the heap.
    147154    void push (const Item& item, const Prio& value) {
    148       int i=iimap[item];
     155      int i=_iim[item];
    149156      if ( i<0 ) {
    150         int s=container.size();
    151         iimap.set( item,s );
     157        int s=_data.size();
     158        _iim.set( item,s );
    152159        store st;
    153160        st.name=item;
    154         container.push_back(st);
     161        _data.push_back(st);
    155162        i=s;
    156163      }
    157164      else {
    158         container[i].parent=container[i].right_neighbor=container[i].child=-1;
    159         container[i].degree=0;
    160         container[i].in=true;
    161       }
    162       container[i].prio=value;
    163 
    164       if( 0==num_items ) { head=i; minimum=i; }
     165        _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
     166        _data[i].degree=0;
     167        _data[i].in=true;
     168      }
     169      _data[i].prio=value;
     170
     171      if( 0==_num_items ) { _head=i; _min=i; }
    165172      else { merge(i); }
    166173
    167       minimum = find_min();
    168 
    169       ++num_items;
    170     }
    171 
    172     /// \brief Returns the item with minimum priority relative to \c Compare.
    173     ///
    174     /// This method returns the item with minimum priority relative to \c
    175     /// Compare.
    176     /// \pre The heap must be nonempty.
    177     Item top() const { return container[minimum].name; }
    178 
    179     /// \brief Returns the minimum priority relative to \c Compare.
    180     ///
    181     /// It returns the minimum priority relative to \c Compare.
    182     /// \pre The heap must be nonempty.
    183     const Prio& prio() const { return container[minimum].prio; }
    184 
    185     /// \brief Returns the priority of \c item.
    186     ///
    187     /// It returns the priority of \c item.
    188     /// \pre \c item must be in the heap.
     174      _min = findMin();
     175
     176      ++_num_items;
     177    }
     178
     179    /// \brief Return the item having minimum priority.
     180    ///
     181    /// This function returns the item having minimum priority.
     182    /// \pre The heap must be non-empty.
     183    Item top() const { return _data[_min].name; }
     184
     185    /// \brief The minimum priority.
     186    ///
     187    /// This function returns the minimum priority.
     188    /// \pre The heap must be non-empty.
     189    Prio prio() const { return _data[_min].prio; }
     190
     191    /// \brief The priority of the given item.
     192    ///
     193    /// This function returns the priority of the given item.
     194    /// \param item The item.
     195    /// \pre \e item must be in the heap.
    189196    const Prio& operator[](const Item& item) const {
    190       return container[iimap[item]].prio;
    191     }
    192 
    193     /// \brief Deletes the item with minimum priority relative to \c Compare.
    194     ///
    195     /// This method deletes the item with minimum priority relative to \c
    196     /// Compare from the heap.
     197      return _data[_iim[item]].prio;
     198    }
     199
     200    /// \brief Remove the item having minimum priority.
     201    ///
     202    /// This function removes the item having minimum priority.
    197203    /// \pre The heap must be non-empty.
    198204    void pop() {
    199       container[minimum].in=false;
     205      _data[_min].in=false;
    200206
    201207      int head_child=-1;
    202       if ( container[minimum].child!=-1 ) {
    203         int child=container[minimum].child;
     208      if ( _data[_min].child!=-1 ) {
     209        int child=_data[_min].child;
    204210        int neighb;
    205211        int prev=-1;
    206212        while( child!=-1 ) {
    207           neighb=container[child].right_neighbor;
    208           container[child].parent=-1;
    209           container[child].right_neighbor=prev;
     213          neighb=_data[child].right_neighbor;
     214          _data[child].parent=-1;
     215          _data[child].right_neighbor=prev;
    210216          head_child=child;
    211217          prev=child;
    … …  
    215221
    216222      // The first case is that there are only one root.
    217       if ( -1==container[head].right_neighbor ) {
    218         head=head_child;
     223      if ( -1==_data[_head].right_neighbor ) {
     224        _head=head_child;
    219225      }
    220226      // The case where there are more roots.
    221227      else {
    222         if( head!=minimum )  { unlace(minimum); }
    223         else { head=container[head].right_neighbor; }
     228        if( _head!=_min )  { unlace(_min); }
     229        else { _head=_data[_head].right_neighbor; }
    224230
    225231        merge(head_child);
    226232      }
    227       minimum=find_min();
    228       --num_items;
    229     }
    230 
    231     /// \brief Deletes \c item from the heap.
    232     ///
    233     /// This method deletes \c item from the heap, if \c item was already
    234     /// stored in the heap. It is quite inefficient in Binomial heaps.
     233      _min=findMin();
     234      --_num_items;
     235    }
     236
     237    /// \brief Remove the given item from the heap.
     238    ///
     239    /// This function removes the given item from the heap if it is
     240    /// already stored.
     241    /// \param item The item to delete.
     242    /// \pre \e item must be in the heap.
    235243    void erase (const Item& item) {
    236       int i=iimap[item];
    237       if ( i >= 0 && container[i].in ) {
    238         decrease( item, container[minimum].prio-1 );
     244      int i=_iim[item];
     245      if ( i >= 0 && _data[i].in ) {
     246        decrease( item, _data[_min].prio-1 );
    239247        pop();
    240248      }
    241249    }
    242250
    243     /// \brief Decreases the priority of \c item to \c value.
    244     ///
    245     /// This method decreases the priority of \c item to \c value.
    246     /// \pre \c item must be stored in the heap with priority at least \c
    247     ///   value relative to \c Compare.
     251    /// \brief Decrease the priority of an item to the given value.
     252    ///
     253    /// This function decreases the priority of an item to the given value.
     254    /// \param item The item.
     255    /// \param value The priority.
     256    /// \pre \e item must be stored in the heap with priority at least \e value.
    248257    void decrease (Item item, const Prio& value) {
    249       int i=iimap[item];
    250 
    251       if( comp( value,container[i].prio ) ) {
    252         container[i].prio=value;
    253 
    254         int p_loc=container[i].parent, loc=i;
     258      int i=_iim[item];
     259
     260      if( _comp( value,_data[i].prio ) ) {
     261        _data[i].prio=value;
     262
     263        int p_loc=_data[i].parent, loc=i;
    255264        int parent, child, neighb;
    256265
    257         while( -1!=p_loc && comp(container[loc].prio,container[p_loc].prio) ) {
     266        while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) {
    258267
    259268          // parent set for other loc_child
    260           child=container[loc].child;
     269          child=_data[loc].child;
    261270          while( -1!=child ) {
    262             container[child].parent=p_loc;
    263             child=container[child].right_neighbor;
     271            _data[child].parent=p_loc;
     272            child=_data[child].right_neighbor;
    264273          }
    265274
    266275          // parent set for other p_loc_child
    267           child=container[p_loc].child;
     276          child=_data[p_loc].child;
    268277          while( -1!=child ) {
    269             container[child].parent=loc;
    270             child=container[child].right_neighbor;
    271           }
    272 
    273           child=container[p_loc].child;
    274           container[p_loc].child=container[loc].child;
     278            _data[child].parent=loc;
     279            child=_data[child].right_neighbor;
     280          }
     281
     282          child=_data[p_loc].child;
     283          _data[p_loc].child=_data[loc].child;
    275284          if( child==loc )
    276285            child=p_loc;
    277           container[loc].child=child;
     286          _data[loc].child=child;
    278287
    279288          // left_neighb set for p_loc
    280           if( container[loc].child!=p_loc ) {
    281             while( container[child].right_neighbor!=loc )
    282               child=container[child].right_neighbor;
    283             container[child].right_neighbor=p_loc;
     289          if( _data[loc].child!=p_loc ) {
     290            while( _data[child].right_neighbor!=loc )
     291              child=_data[child].right_neighbor;
     292            _data[child].right_neighbor=p_loc;
    284293          }
    285294
    286295          // left_neighb set for loc
    287           parent=container[p_loc].parent;
    288           if( -1!=parent ) child=container[parent].child;
    289           else child=head;
     296          parent=_data[p_loc].parent;
     297          if( -1!=parent ) child=_data[parent].child;
     298          else child=_head;
    290299
    291300          if( child!=p_loc ) {
    292             while( container[child].right_neighbor!=p_loc )
    293               child=container[child].right_neighbor;
    294             container[child].right_neighbor=loc;
    295           }
    296 
    297           neighb=container[p_loc].right_neighbor;
    298           container[p_loc].right_neighbor=container[loc].right_neighbor;
    299           container[loc].right_neighbor=neighb;
    300 
    301           container[p_loc].parent=loc;
    302           container[loc].parent=parent;
    303 
    304           if( -1!=parent && container[parent].child==p_loc )
    305             container[parent].child=loc;
     301            while( _data[child].right_neighbor!=p_loc )
     302              child=_data[child].right_neighbor;
     303            _data[child].right_neighbor=loc;
     304          }
     305
     306          neighb=_data[p_loc].right_neighbor;
     307          _data[p_loc].right_neighbor=_data[loc].right_neighbor;
     308          _data[loc].right_neighbor=neighb;
     309
     310          _data[p_loc].parent=loc;
     311          _data[loc].parent=parent;
     312
     313          if( -1!=parent && _data[parent].child==p_loc )
     314            _data[parent].child=loc;
    306315
    307316          /*if new parent will be the first root*/
    308           if( head==p_loc )
    309             head=loc;
    310 
    311           p_loc=container[loc].parent;
    312         }
    313       }
    314       if( comp(value,container[minimum].prio) ) {
    315         minimum=i;
    316       }
    317     }
    318 
    319     /// \brief Increases the priority of \c item to \c value.
    320     ///
    321     /// This method sets the priority of \c item to \c value. Though
    322     /// there is no precondition on the priority of \c item, this
    323     /// method should be used only if it is indeed necessary to increase
    324     /// (relative to \c Compare) the priority of \c item, because this
    325     /// method is inefficient.
     317          if( _head==p_loc )
     318            _head=loc;
     319
     320          p_loc=_data[loc].parent;
     321        }
     322      }
     323      if( _comp(value,_data[_min].prio) ) {
     324        _min=i;
     325      }
     326    }
     327
     328    /// \brief Increase the priority of an item to the given value.
     329    ///
     330    /// This function increases the priority of an item to the given value.
     331    /// \param item The item.
     332    /// \param value The priority.
     333    /// \pre \e item must be stored in the heap with priority at most \e value.
    326334    void increase (Item item, const Prio& value) {
    327335      erase(item);
    … …  
    329337    }
    330338
    331 
    332     /// \brief Returns if \c item is in, has already been in, or has never
    333     /// been in the heap.
    334     ///
    335     /// This method returns PRE_HEAP if \c item has never been in the
    336     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    337     /// otherwise. In the latter case it is possible that \c item will
    338     /// get back to the heap again.
     339    /// \brief Return the state of an item.
     340    ///
     341    /// This method returns \c PRE_HEAP if the given item has never
     342    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
     343    /// and \c POST_HEAP otherwise.
     344    /// In the latter case it is possible that the item will get back
     345    /// to the heap again.
     346    /// \param item The item.
    339347    State state(const Item &item) const {
    340       int i=iimap[item];
     348      int i=_iim[item];
    341349      if( i>=0 ) {
    342         if ( container[i].in ) i=0;
     350        if ( _data[i].in ) i=0;
    343351        else i=-2;
    344352      }
    … …  
    346354    }
    347355
    348     /// \brief Sets the state of the \c item in the heap.
    349     ///
    350     /// Sets the state of the \c item in the heap. It can be used to
    351     /// manually clear the heap when it is important to achive the
    352     /// better time complexity.
     356    /// \brief Set the state of an item in the heap.
     357    ///
     358    /// This function sets the state of the given item in the heap.
     359    /// It can be used to manually clear the heap when it is important
     360    /// to achive better time complexity.
    353361    /// \param i The item.
    354362    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    360368          erase(i);
    361369        }
    362         iimap[i] = st;
     370        _iim[i] = st;
    363371        break;
    364372      case IN_HEAP:
    … …  
    368376
    369377  private:
    370     int find_min() {
     378    int findMin() {
    371379      int min_loc=-1, min_val;
    372       int x=head;
     380      int x=_head;
    373381      if( x!=-1 ) {
    374         min_val=container[x].prio;
     382        min_val=_data[x].prio;
    375383        min_loc=x;
    376         x=container[x].right_neighbor;
     384        x=_data[x].right_neighbor;
    377385
    378386        while( x!=-1 ) {
    379           if( comp( container[x].prio,min_val ) ) {
    380             min_val=container[x].prio;
     387          if( _comp( _data[x].prio,min_val ) ) {
     388            min_val=_data[x].prio;
    381389            min_loc=x;
    382390          }
    383           x=container[x].right_neighbor;
     391          x=_data[x].right_neighbor;
    384392        }
    385393      }
    … …  
    390398      interleave(a);
    391399
    392       int x=head;
     400      int x=_head;
    393401      if( -1!=x ) {
    394         int x_prev=-1, x_next=container[x].right_neighbor;
     402        int x_prev=-1, x_next=_data[x].right_neighbor;
    395403        while( -1!=x_next ) {
    396           if( container[x].degree!=container[x_next].degree || ( -1!=container[x_next].right_neighbor && container[container[x_next].right_neighbor].degree==container[x].degree ) ) {
     404          if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
    397405            x_prev=x;
    398406            x=x_next;
    399407          }
    400408          else {
    401             if( comp(container[x].prio,container[x_next].prio) ) {
    402               container[x].right_neighbor=container[x_next].right_neighbor;
     409            if( _comp(_data[x].prio,_data[x_next].prio) ) {
     410              _data[x].right_neighbor=_data[x_next].right_neighbor;
    403411              fuse(x_next,x);
    404412            }
    405413            else {
    406               if( -1==x_prev ) { head=x_next; }
     414              if( -1==x_prev ) { _head=x_next; }
    407415              else {
    408                 container[x_prev].right_neighbor=x_next;
     416                _data[x_prev].right_neighbor=x_next;
    409417              }
    410418              fuse(x,x_next);
    … …  
    412420            }
    413421          }
    414           x_next=container[x].right_neighbor;
     422          x_next=_data[x].right_neighbor;
    415423        }
    416424      }
    … …  
    420428      int other=-1, head_other=-1;
    421429
    422       while( -1!=a || -1!=head ) {
     430      while( -1!=a || -1!=_head ) {
    423431        if( -1==a ) {
    424432          if( -1==head_other ) {
    425             head_other=head;
     433            head_other=_head;
    426434          }
    427435          else {
    428             container[other].right_neighbor=head;
    429           }
    430           head=-1;
    431         }
    432         else if( -1==head ) {
     436            _data[other].right_neighbor=_head;
     437          }
     438          _head=-1;
     439        }
     440        else if( -1==_head ) {
    433441          if( -1==head_other ) {
    434442            head_other=a;
    435443          }
    436444          else {
    437             container[other].right_neighbor=a;
     445            _data[other].right_neighbor=a;
    438446          }
    439447          a=-1;
    440448        }
    441449        else {
    442           if( container[a].degree<container[head].degree ) {
     450          if( _data[a].degree<_data[_head].degree ) {
    443451            if( -1==head_other ) {
    444452              head_other=a;
    445453            }
    446454            else {
    447               container[other].right_neighbor=a;
     455              _data[other].right_neighbor=a;
    448456            }
    449457            other=a;
    450             a=container[a].right_neighbor;
     458            a=_data[a].right_neighbor;
    451459          }
    452460          else {
    453461            if( -1==head_other ) {
    454               head_other=head;
     462              head_other=_head;
    455463            }
    456464            else {
    457               container[other].right_neighbor=head;
     465              _data[other].right_neighbor=_head;
    458466            }
    459             other=head;
    460             head=container[head].right_neighbor;
    461           }
    462         }
    463       }
    464       head=head_other;
     467            other=_head;
     468            _head=_data[_head].right_neighbor;
     469          }
     470        }
     471      }
     472      _head=head_other;
    465473    }
    466474
    467475    // Lacing a under b
    468476    void fuse(int a, int b) {
    469       container[a].parent=b;
    470       container[a].right_neighbor=container[b].child;
    471       container[b].child=a;
    472 
    473       ++container[b].degree;
     477      _data[a].parent=b;
     478      _data[a].right_neighbor=_data[b].child;
     479      _data[b].child=a;
     480
     481      ++_data[b].degree;
    474482    }
    475483
    476484    // It is invoked only if a has siblings.
    477485    void unlace(int a) {
    478       int neighb=container[a].right_neighbor;
    479       int other=head;
    480 
    481       while( container[other].right_neighbor!=a )
    482         other=container[other].right_neighbor;
    483       container[other].right_neighbor=neighb;
     486      int neighb=_data[a].right_neighbor;
     487      int other=_head;
     488
     489      while( _data[other].right_neighbor!=a )
     490        other=_data[other].right_neighbor;
     491      _data[other].right_neighbor=neighb;
    484492    }
    485493
Note: See TracChangeset for help on using the changeset viewer.