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/pairing_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/pairing_heap.h

    r749 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
    24 ///\brief Pairing Heap implementation.
     23///\ingroup heaps
     24///\brief Pairing heap implementation.
    2525
    2626#include <vector>
     27#include <utility>
    2728#include <functional>
    2829#include <lemon/math.h>
    … …  
    3031namespace lemon {
    3132
    32   /// \ingroup auxdat
     33  /// \ingroup heaps
    3334  ///
    3435  ///\brief Pairing Heap.
    3536  ///
    36   ///This class implements the \e Pairing \e heap data structure. A \e heap
    37   ///is a data structure for storing items with specified values called \e
    38   ///priorities in such a way that finding the item with minimum priority is
    39   ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    40   ///one can change the priority of an item, add or erase an item, etc.
     37  /// This class implements the \e pairing \e heap data structure.
     38  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4139  ///
    42   ///The methods \ref increase and \ref erase are not efficient in a Pairing
    43   ///heap. In case of many calls to these operations, it is better to use a
    44   ///\ref BinHeap "binary heap".
     40  /// The methods \ref increase() and \ref erase() are not efficient
     41  /// in a pairing heap. In case of many calls of these operations,
     42  /// it is better to use other heap structure, e.g. \ref BinHeap
     43  /// "binary heap".
    4544  ///
    46   ///\param _Prio Type of the priority of the items.
    47   ///\param _ItemIntMap A read and writable Item int map, used internally
    48   ///to handle the cross references.
    49   ///\param _Compare A class for the ordering of the priorities. The
    50   ///default is \c std::less<_Prio>.
    51   ///
    52   ///\sa BinHeap
    53   ///\sa Dijkstra
    54   ///\author Dorian Batha
    55 
     45  /// \tparam PR Type of the priorities of the items.
     46  /// \tparam IM A read-writable item map with \c int values, used
     47  /// internally to handle the cross references.
     48  /// \tparam CMP A functor class for comparing the priorities.
     49  /// The default is \c std::less<PR>.
    5650#ifdef DOXYGEN
    57   template <typename _Prio,
    58             typename _ItemIntMap,
    59             typename _Compare>
     51  template <typename PR, typename IM, typename CMP>
    6052#else
    61   template <typename _Prio,
    62             typename _ItemIntMap,
    63             typename _Compare = std::less<_Prio> >
     53  template <typename PR, typename IM, typename CMP = std::less<PR> >
    6454#endif
    6555  class PairingHeap {
    6656  public:
    67     typedef _ItemIntMap ItemIntMap;
    68     typedef _Prio Prio;
     57    /// Type of the item-int map.
     58    typedef IM ItemIntMap;
     59    /// Type of the priorities.
     60    typedef PR Prio;
     61    /// Type of the items stored in the heap.
    6962    typedef typename ItemIntMap::Key Item;
    70     typedef std::pair<Item,Prio> Pair;
    71     typedef _Compare Compare;
     63    /// Functor type for comparing the priorities.
     64    typedef CMP Compare;
     65
     66    /// \brief Type to represent the states of the items.
     67    ///
     68    /// Each item has a state associated to it. It can be "in heap",
     69    /// "pre-heap" or "post-heap". The latter two are indifferent from the
     70    /// heap's point of view, but may be useful to the user.
     71    ///
     72    /// The item-int map must be initialized in such way that it assigns
     73    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
     74    enum State {
     75      IN_HEAP = 0,    ///< = 0.
     76      PRE_HEAP = -1,  ///< = -1.
     77      POST_HEAP = -2  ///< = -2.
     78    };
    7279
    7380  private:
    7481    class store;
    7582
    76     std::vector<store> container;
    77     int minimum;
    78     ItemIntMap &iimap;
    79     Compare comp;
    80     int num_items;
     83    std::vector<store> _data;
     84    int _min;
     85    ItemIntMap &_iim;
     86    Compare _comp;
     87    int _num_items;
    8188
    8289  public:
    83     ///Status of the nodes
    84     enum State {
    85       ///The node is in the heap
    86       IN_HEAP = 0,
    87       ///The node has never been in the heap
    88       PRE_HEAP = -1,
    89       ///The node was in the heap but it got out of it
    90       POST_HEAP = -2
    91     };
    92 
    93     /// \brief The constructor
    94     ///
    95     /// \c _iimap should be given to the constructor, since it is
    96     ///   used internally to handle the cross references.
    97     explicit PairingHeap(ItemIntMap &_iimap)
    98       : minimum(0), iimap(_iimap), num_items(0) {}
    99 
    100     /// \brief The constructor
    101     ///
    102     /// \c _iimap should be given to the constructor, since it is used
    103     /// internally to handle the cross references. \c _comp is an
    104     /// object for ordering of the priorities.
    105     PairingHeap(ItemIntMap &_iimap, const Compare &_comp)
    106       : minimum(0), iimap(_iimap), comp(_comp), num_items(0) {}
     90    /// \brief Constructor.
     91    ///
     92    /// Constructor.
     93    /// \param map A map that assigns \c int values to the items.
     94    /// It is used internally to handle the cross references.
     95    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     96    explicit PairingHeap(ItemIntMap &map)
     97      : _min(0), _iim(map), _num_items(0) {}
     98
     99    /// \brief Constructor.
     100    ///
     101    /// Constructor.
     102    /// \param map A map that assigns \c int values to the items.
     103    /// It is used internally to handle the cross references.
     104    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     105    /// \param comp The function object used for comparing the priorities.
     106    PairingHeap(ItemIntMap &map, const Compare &comp)
     107      : _min(0), _iim(map), _comp(comp), _num_items(0) {}
    107108
    108109    /// \brief The number of items stored in the heap.
    109110    ///
    110     /// Returns the number of items stored in the heap.
    111     int size() const { return num_items; }
    112 
    113     /// \brief Checks if the heap stores no items.
    114     ///
    115     ///   Returns \c true if and only if the heap stores no items.
    116     bool empty() const { return num_items==0; }
    117 
    118     /// \brief Make empty this heap.
    119     ///
    120     /// Make empty this heap. It does not change the cross reference
    121     /// map.  If you want to reuse a heap what is not surely empty you
    122     /// should first clear the heap and after that you should set the
    123     /// cross reference map for each item to \c PRE_HEAP.
     111    /// This function returns the number of items stored in the heap.
     112    int size() const { return _num_items; }
     113
     114    /// \brief Check if the heap is empty.
     115    ///
     116    /// This function returns \c true if the heap is empty.
     117    bool empty() const { return _num_items==0; }
     118
     119    /// \brief Make the heap empty.
     120    ///
     121    /// This functon makes the heap empty.
     122    /// It does not change the cross reference map. If you want to reuse
     123    /// a heap that is not surely empty, you should first clear it and
     124    /// then you should set the cross reference map to \c PRE_HEAP
     125    /// for each item.
    124126    void clear() {
    125       container.clear();
    126       minimum = 0;
    127       num_items = 0;
    128     }
    129 
    130     /// \brief \c item gets to the heap with priority \c value independently
    131     /// if \c item was already there.
    132     ///
    133     /// This method calls \ref push(\c item, \c value) if \c item is not
    134     /// stored in the heap and it calls \ref decrease(\c item, \c value) or
    135     /// \ref increase(\c item, \c value) otherwise.
     127      _data.clear();
     128      _min = 0;
     129      _num_items = 0;
     130    }
     131
     132    /// \brief Set the priority of an item or insert it, if it is
     133    /// not stored in the heap.
     134    ///
     135    /// This method sets the priority of the given item if it is
     136    /// already stored in the heap. Otherwise it inserts the given
     137    /// item into the heap with the given priority.
     138    /// \param item The item.
     139    /// \param value The priority.
    136140    void set (const Item& item, const Prio& value) {
    137       int i=iimap[item];
    138       if ( i>=0 && container[i].in ) {
    139         if ( comp(value, container[i].prio) ) decrease(item, value);
    140         if ( comp(container[i].prio, value) ) increase(item, value);
     141      int i=_iim[item];
     142      if ( i>=0 && _data[i].in ) {
     143        if ( _comp(value, _data[i].prio) ) decrease(item, value);
     144        if ( _comp(_data[i].prio, value) ) increase(item, value);
    141145      } else push(item, value);
    142146    }
    143147
    144     /// \brief Adds \c item to the heap with priority \c value.
    145     ///
    146     /// Adds \c item to the heap with priority \c value.
    147     /// \pre \c item must not be stored in the heap.
     148    /// \brief Insert an item into the heap with the given priority.
     149    ///
     150    /// This function inserts the given item into the heap with the
     151    /// given priority.
     152    /// \param item The item to insert.
     153    /// \param value The priority of the item.
     154    /// \pre \e item must not be stored in the heap.
    148155    void push (const Item& item, const Prio& value) {
    149       int i=iimap[item];
     156      int i=_iim[item];
    150157      if( i<0 ) {
    151         int s=container.size();
    152         iimap.set(item, s);
     158        int s=_data.size();
     159        _iim.set(item, s);
    153160        store st;
    154161        st.name=item;
    155         container.push_back(st);
     162        _data.push_back(st);
    156163        i=s;
    157164      } else {
    158         container[i].parent=container[i].child=-1;
    159         container[i].left_child=false;
    160         container[i].degree=0;
    161         container[i].in=true;
    162       }
    163 
    164       container[i].prio=value;
    165 
    166       if ( num_items!=0 ) {
    167         if ( comp( value, container[minimum].prio) ) {
    168           fuse(i,minimum);
    169           minimum=i;
    170         }
    171         else fuse(minimum,i);
    172       }
    173       else minimum=i;
    174 
    175       ++num_items;
    176     }
    177 
    178     /// \brief Returns the item with minimum priority relative to \c Compare.
    179     ///
    180     /// This method returns the item with minimum priority relative to \c
    181     /// Compare.
    182     /// \pre The heap must be nonempty.
    183     Item top() const { return container[minimum].name; }
    184 
    185     /// \brief Returns the minimum priority relative to \c Compare.
    186     ///
    187     /// It returns the minimum priority relative to \c Compare.
    188     /// \pre The heap must be nonempty.
    189     const Prio& prio() const { return container[minimum].prio; }
    190 
    191     /// \brief Returns the priority of \c item.
    192     ///
    193     /// It returns the priority of \c item.
    194     /// \pre \c item must be in the heap.
     165        _data[i].parent=_data[i].child=-1;
     166        _data[i].left_child=false;
     167        _data[i].degree=0;
     168        _data[i].in=true;
     169      }
     170
     171      _data[i].prio=value;
     172
     173      if ( _num_items!=0 ) {
     174        if ( _comp( value, _data[_min].prio) ) {
     175          fuse(i,_min);
     176          _min=i;
     177        }
     178        else fuse(_min,i);
     179      }
     180      else _min=i;
     181
     182      ++_num_items;
     183    }
     184
     185    /// \brief Return the item having minimum priority.
     186    ///
     187    /// This function returns the item having minimum priority.
     188    /// \pre The heap must be non-empty.
     189    Item top() const { return _data[_min].name; }
     190
     191    /// \brief The minimum priority.
     192    ///
     193    /// This function returns the minimum priority.
     194    /// \pre The heap must be non-empty.
     195    const Prio& prio() const { return _data[_min].prio; }
     196
     197    /// \brief The priority of the given item.
     198    ///
     199    /// This function returns the priority of the given item.
     200    /// \param item The item.
     201    /// \pre \e item must be in the heap.
    195202    const Prio& operator[](const Item& item) const {
    196       return container[iimap[item]].prio;
    197     }
    198 
    199     /// \brief Deletes the item with minimum priority relative to \c Compare.
    200     ///
    201     /// This method deletes the item with minimum priority relative to \c
    202     /// Compare from the heap.
     203      return _data[_iim[item]].prio;
     204    }
     205
     206    /// \brief Remove the item having minimum priority.
     207    ///
     208    /// This function removes the item having minimum priority.
    203209    /// \pre The heap must be non-empty.
    204210    void pop() {
    205       int TreeArray[num_items];
     211      int TreeArray[_num_items];
    206212      int i=0, num_child=0, child_right = 0;
    207       container[minimum].in=false;
    208 
    209       if( -1!=container[minimum].child ) {
    210         i=container[minimum].child;
     213      _data[_min].in=false;
     214
     215      if( -1!=_data[_min].child ) {
     216        i=_data[_min].child;
    211217        TreeArray[num_child] = i;
    212         container[i].parent = -1;
    213         container[minimum].child = -1;
     218        _data[i].parent = -1;
     219        _data[_min].child = -1;
    214220
    215221        ++num_child;
    216222        int ch=-1;
    217         while( container[i].child!=-1 ) {
    218           ch=container[i].child;
    219           if( container[ch].left_child && i==container[ch].parent ) {
     223        while( _data[i].child!=-1 ) {
     224          ch=_data[i].child;
     225          if( _data[ch].left_child && i==_data[ch].parent ) {
    220226            i=ch;
    221227            //break;
    222228          } else {
    223             if( container[ch].left_child ) {
    224               child_right=container[ch].parent;
    225               container[ch].parent = i;
    226               --container[i].degree;
     229            if( _data[ch].left_child ) {
     230              child_right=_data[ch].parent;
     231              _data[ch].parent = i;
     232              --_data[i].degree;
    227233            }
    228234            else {
    229235              child_right=ch;
    230               container[i].child=-1;
    231               container[i].degree=0;
     236              _data[i].child=-1;
     237              _data[i].degree=0;
    232238            }
    233             container[child_right].parent = -1;
     239            _data[child_right].parent = -1;
    234240            TreeArray[num_child] = child_right;
    235241            i = child_right;
    … …  
    240246        int other;
    241247        for( i=0; i<num_child-1; i+=2 ) {
    242           if ( !comp(container[TreeArray[i]].prio,
    243                      container[TreeArray[i+1]].prio) ) {
     248          if ( !_comp(_data[TreeArray[i]].prio,
     249                     _data[TreeArray[i+1]].prio) ) {
    244250            other=TreeArray[i];
    245251            TreeArray[i]=TreeArray[i+1];
    … …  
    251257        i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
    252258        while(i>=2) {
    253           if ( comp(container[TreeArray[i]].prio,
    254                     container[TreeArray[i-2]].prio) ) {
     259          if ( _comp(_data[TreeArray[i]].prio,
     260                    _data[TreeArray[i-2]].prio) ) {
    255261            other=TreeArray[i];
    256262            TreeArray[i]=TreeArray[i-2];
    … …  
    260266          i-=2;
    261267        }
    262         minimum = TreeArray[0];
     268        _min = TreeArray[0];
    263269      }
    264270
    265271      if ( 0==num_child ) {
    266         minimum = container[minimum].child;
    267       }
    268 
    269       if (minimum >= 0) container[minimum].left_child = false;
    270 
    271       --num_items;
    272     }
    273 
    274     /// \brief Deletes \c item from the heap.
    275     ///
    276     /// This method deletes \c item from the heap, if \c item was already
    277     /// stored in the heap. It is quite inefficient in Pairing heaps.
     272        _min = _data[_min].child;
     273      }
     274
     275      if (_min >= 0) _data[_min].left_child = false;
     276
     277      --_num_items;
     278    }
     279
     280    /// \brief Remove the given item from the heap.
     281    ///
     282    /// This function removes the given item from the heap if it is
     283    /// already stored.
     284    /// \param item The item to delete.
     285    /// \pre \e item must be in the heap.
    278286    void erase (const Item& item) {
    279       int i=iimap[item];
    280       if ( i>=0 && container[i].in ) {
    281         decrease( item, container[minimum].prio-1 );
     287      int i=_iim[item];
     288      if ( i>=0 && _data[i].in ) {
     289        decrease( item, _data[_min].prio-1 );
    282290        pop();
    283291      }
    284292    }
    285293
    286     /// \brief Decreases the priority of \c item to \c value.
    287     ///
    288     /// This method decreases the priority of \c item to \c value.
    289     /// \pre \c item must be stored in the heap with priority at least \c
    290     ///   value relative to \c Compare.
     294    /// \brief Decrease the priority of an item to the given value.
     295    ///
     296    /// This function decreases the priority of an item to the given value.
     297    /// \param item The item.
     298    /// \param value The priority.
     299    /// \pre \e item must be stored in the heap with priority at least \e value.
    291300    void decrease (Item item, const Prio& value) {
    292       int i=iimap[item];
    293       container[i].prio=value;
    294       int p=container[i].parent;
    295 
    296       if( container[i].left_child && i!=container[p].child ) {
    297         p=container[p].parent;
    298       }
    299 
    300       if ( p!=-1 && comp(value,container[p].prio) ) {
     301      int i=_iim[item];
     302      _data[i].prio=value;
     303      int p=_data[i].parent;
     304
     305      if( _data[i].left_child && i!=_data[p].child ) {
     306        p=_data[p].parent;
     307      }
     308
     309      if ( p!=-1 && _comp(value,_data[p].prio) ) {
    301310        cut(i,p);
    302         if ( comp(container[minimum].prio,value) ) {
    303           fuse(minimum,i);
     311        if ( _comp(_data[_min].prio,value) ) {
     312          fuse(_min,i);
    304313        } else {
    305           fuse(i,minimum);
    306           minimum=i;
    307         }
    308       }
    309     }
    310 
    311     /// \brief Increases the priority of \c item to \c value.
    312     ///
    313     /// This method sets the priority of \c item to \c value. Though
    314     /// there is no precondition on the priority of \c item, this
    315     /// method should be used only if it is indeed necessary to increase
    316     /// (relative to \c Compare) the priority of \c item, because this
    317     /// method is inefficient.
     314          fuse(i,_min);
     315          _min=i;
     316        }
     317      }
     318    }
     319
     320    /// \brief Increase the priority of an item to the given value.
     321    ///
     322    /// This function increases the priority of an item to the given value.
     323    /// \param item The item.
     324    /// \param value The priority.
     325    /// \pre \e item must be stored in the heap with priority at most \e value.
    318326    void increase (Item item, const Prio& value) {
    319327      erase(item);
    … …  
    321329    }
    322330
    323     /// \brief Returns if \c item is in, has already been in, or has never
    324     /// been in the heap.
    325     ///
    326     /// This method returns PRE_HEAP if \c item has never been in the
    327     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    328     /// otherwise. In the latter case it is possible that \c item will
    329     /// get back to the heap again.
     331    /// \brief Return the state of an item.
     332    ///
     333    /// This method returns \c PRE_HEAP if the given item has never
     334    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
     335    /// and \c POST_HEAP otherwise.
     336    /// In the latter case it is possible that the item will get back
     337    /// to the heap again.
     338    /// \param item The item.
    330339    State state(const Item &item) const {
    331       int i=iimap[item];
     340      int i=_iim[item];
    332341      if( i>=0 ) {
    333         if( container[i].in ) i=0;
     342        if( _data[i].in ) i=0;
    334343        else i=-2;
    335344      }
    … …  
    337346    }
    338347
    339     /// \brief Sets the state of the \c item in the heap.
    340     ///
    341     /// Sets the state of the \c item in the heap. It can be used to
    342     /// manually clear the heap when it is important to achive the
    343     /// better time complexity.
     348    /// \brief Set the state of an item in the heap.
     349    ///
     350    /// This function sets the state of the given item in the heap.
     351    /// It can be used to manually clear the heap when it is important
     352    /// to achive better time complexity.
    344353    /// \param i The item.
    345354    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    349358      case PRE_HEAP:
    350359        if (state(i) == IN_HEAP) erase(i);
    351         iimap[i]=st;
     360        _iim[i]=st;
    352361        break;
    353362      case IN_HEAP:
    … …  
    360369    void cut(int a, int b) {
    361370      int child_a;
    362       switch (container[a].degree) {
     371      switch (_data[a].degree) {
    363372        case 2:
    364           child_a = container[container[a].child].parent;
    365           if( container[a].left_child ) {
    366             container[child_a].left_child=true;
    367             container[b].child=child_a;
    368             container[child_a].parent=container[a].parent;
     373          child_a = _data[_data[a].child].parent;
     374          if( _data[a].left_child ) {
     375            _data[child_a].left_child=true;
     376            _data[b].child=child_a;
     377            _data[child_a].parent=_data[a].parent;
    369378          }
    370379          else {
    371             container[child_a].left_child=false;
    372             container[child_a].parent=b;
    373             if( a!=container[b].child )
    374               container[container[b].child].parent=child_a;
     380            _data[child_a].left_child=false;
     381            _data[child_a].parent=b;
     382            if( a!=_data[b].child )
     383              _data[_data[b].child].parent=child_a;
    375384            else
    376               container[b].child=child_a;
    377           }
    378           --container[a].degree;
    379           container[container[a].child].parent=a;
     385              _data[b].child=child_a;
     386          }
     387          --_data[a].degree;
     388          _data[_data[a].child].parent=a;
    380389          break;
    381390
    382391        case 1:
    383           child_a = container[a].child;
    384           if( !container[child_a].left_child ) {
    385             --container[a].degree;
    386             if( container[a].left_child ) {
    387               container[child_a].left_child=true;
    388               container[child_a].parent=container[a].parent;
    389               container[b].child=child_a;
     392          child_a = _data[a].child;
     393          if( !_data[child_a].left_child ) {
     394            --_data[a].degree;
     395            if( _data[a].left_child ) {
     396              _data[child_a].left_child=true;
     397              _data[child_a].parent=_data[a].parent;
     398              _data[b].child=child_a;
    390399            }
    391400            else {
    392               container[child_a].left_child=false;
    393               container[child_a].parent=b;
    394               if( a!=container[b].child )
    395                 container[container[b].child].parent=child_a;
     401              _data[child_a].left_child=false;
     402              _data[child_a].parent=b;
     403              if( a!=_data[b].child )
     404                _data[_data[b].child].parent=child_a;
    396405              else
    397                 container[b].child=child_a;
     406                _data[b].child=child_a;
    398407            }
    399             container[a].child=-1;
     408            _data[a].child=-1;
    400409          }
    401410          else {
    402             --container[b].degree;
    403             if( container[a].left_child ) {
    404               container[b].child =
    405                 (1==container[b].degree) ? container[a].parent : -1;
     411            --_data[b].degree;
     412            if( _data[a].left_child ) {
     413              _data[b].child =
     414                (1==_data[b].degree) ? _data[a].parent : -1;
    406415            } else {
    407               if (1==container[b].degree)
    408                 container[container[b].child].parent=b;
     416              if (1==_data[b].degree)
     417                _data[_data[b].child].parent=b;
    409418              else
    410                 container[b].child=-1;
     419                _data[b].child=-1;
    411420            }
    412421          }
    … …  
    414423
    415424        case 0:
    416           --container[b].degree;
    417           if( container[a].left_child ) {
    418             container[b].child =
    419               (0!=container[b].degree) ? container[a].parent : -1;
     425          --_data[b].degree;
     426          if( _data[a].left_child ) {
     427            _data[b].child =
     428              (0!=_data[b].degree) ? _data[a].parent : -1;
    420429          } else {
    421             if( 0!=container[b].degree )
    422               container[container[b].child].parent=b;
     430            if( 0!=_data[b].degree )
     431              _data[_data[b].child].parent=b;
    423432            else
    424               container[b].child=-1;
     433              _data[b].child=-1;
    425434          }
    426435          break;
    427436      }
    428       container[a].parent=-1;
    429       container[a].left_child=false;
     437      _data[a].parent=-1;
     438      _data[a].left_child=false;
    430439    }
    431440
    432441    void fuse(int a, int b) {
    433       int child_a = container[a].child;
    434       int child_b = container[b].child;
    435       container[a].child=b;
    436       container[b].parent=a;
    437       container[b].left_child=true;
     442      int child_a = _data[a].child;
     443      int child_b = _data[b].child;
     444      _data[a].child=b;
     445      _data[b].parent=a;
     446      _data[b].left_child=true;
    438447
    439448      if( -1!=child_a ) {
    440         container[b].child=child_a;
    441         container[child_a].parent=b;
    442         container[child_a].left_child=false;
    443         ++container[b].degree;
     449        _data[b].child=child_a;
     450        _data[child_a].parent=b;
     451        _data[child_a].left_child=false;
     452        ++_data[b].degree;
    444453
    445454        if( -1!=child_b ) {
    446            container[b].child=child_b;
    447            container[child_b].parent=child_a;
    448         }
    449       }
    450       else { ++container[a].degree; }
     455           _data[b].child=child_b;
     456           _data[child_b].parent=child_a;
     457        }
     458      }
     459      else { ++_data[a].degree; }
    451460    }
    452461
Note: See TracChangeset for help on using the changeset viewer.