COIN-OR::LEMON - Graph Library

Changeset 758:28cfac049a6a in lemon


Ignore:
Timestamp:
07/08/09 17:47:01 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Unify member names in heaps (#299)

The following renamings are made.

Public members:

Private members:

  • bubble_up() -> bubbleUp()
  • bubble_down() -> bubbleDown()
  • second_child() -> secondChild()
  • makeroot() -> makeRoot()
  • relocate_last() -> relocateLast()
  • data -> _data
  • boxes -> _boxes
Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/bin_heap.h

    r757 r758  
    125125    static int parent(int i) { return (i-1)/2; } 
    126126 
    127     static int second_child(int i) { return 2*i+2; } 
     127    static int secondChild(int i) { return 2*i+2; } 
    128128    bool less(const Pair &p1, const Pair &p2) const { 
    129129      return _comp(p1.second, p2.second); 
    130130    } 
    131131 
    132     int bubble_up(int hole, Pair p) { 
     132    int bubbleUp(int hole, Pair p) { 
    133133      int par = parent(hole); 
    134134      while( hole>0 && less(p,_data[par]) ) { 
     
    141141    } 
    142142 
    143     int bubble_down(int hole, Pair p, int length) { 
    144       int child = second_child(hole); 
     143    int bubbleDown(int hole, Pair p, int length) { 
     144      int child = secondChild(hole); 
    145145      while(child < length) { 
    146146        if( less(_data[child-1], _data[child]) ) { 
     
    151151        move(_data[child], hole); 
    152152        hole = child; 
    153         child = second_child(hole); 
     153        child = secondChild(hole); 
    154154      } 
    155155      child--; 
     
    179179      int n = _data.size(); 
    180180      _data.resize(n+1); 
    181       bubble_up(n, p); 
     181      bubbleUp(n, p); 
    182182    } 
    183183 
     
    215215      _iim.set(_data[0].first, POST_HEAP); 
    216216      if (n > 0) { 
    217         bubble_down(0, _data[n], n); 
     217        bubbleDown(0, _data[n], n); 
    218218      } 
    219219      _data.pop_back(); 
     
    231231      _iim.set(_data[h].first, POST_HEAP); 
    232232      if( h < n ) { 
    233         if ( bubble_up(h, _data[n]) == h) { 
    234           bubble_down(h, _data[n], n); 
     233        if ( bubbleUp(h, _data[n]) == h) { 
     234          bubbleDown(h, _data[n], n); 
    235235        } 
    236236      } 
     
    262262      } 
    263263      else if( _comp(p, _data[idx].second) ) { 
    264         bubble_up(idx, Pair(i,p)); 
     264        bubbleUp(idx, Pair(i,p)); 
    265265      } 
    266266      else { 
    267         bubble_down(idx, Pair(i,p), _data.size()); 
     267        bubbleDown(idx, Pair(i,p), _data.size()); 
    268268      } 
    269269    } 
     
    277277    void decrease(const Item &i, const Prio &p) { 
    278278      int idx = _iim[i]; 
    279       bubble_up(idx, Pair(i,p)); 
     279      bubbleUp(idx, Pair(i,p)); 
    280280    } 
    281281 
     
    288288    void increase(const Item &i, const Prio &p) { 
    289289      int idx = _iim[i]; 
    290       bubble_down(idx, Pair(i,p), _data.size()); 
     290      bubbleDown(idx, Pair(i,p), _data.size()); 
    291291    } 
    292292 
  • lemon/bucket_heap.h

    r757 r758  
    143143  private: 
    144144 
    145     void relocate_last(int idx) { 
     145    void relocateLast(int idx) { 
    146146      if (idx + 1 < int(_data.size())) { 
    147147        _data[idx] = _data.back(); 
     
    244244      _iim[_data[idx].item] = -2; 
    245245      unlace(idx); 
    246       relocate_last(idx); 
     246      relocateLast(idx); 
    247247    } 
    248248 
     
    257257      _iim[_data[idx].item] = -2; 
    258258      unlace(idx); 
    259       relocate_last(idx); 
     259      relocateLast(idx); 
    260260    } 
    261261 
  • lemon/fib_heap.h

    r757 r758  
    189189        _data[_minimum].in=false; 
    190190        if ( _data[_minimum].degree!=0 ) { 
    191           makeroot(_data[_minimum].child); 
     191          makeRoot(_data[_minimum].child); 
    192192          _minimum=_data[_minimum].child; 
    193193          balance(); 
     
    202202          int last_child=_data[child].left_neighbor; 
    203203 
    204           makeroot(child); 
     204          makeRoot(child); 
    205205 
    206206          _data[left].right_neighbor=child; 
     
    373373    } 
    374374 
    375     void makeroot(int c) { 
     375    void makeRoot(int c) { 
    376376      int s=c; 
    377377      do { 
  • lemon/radix_heap.h

    r757 r758  
    5959    /// RadixHeap with a priority smaller than the last erased one. 
    6060    /// \see RadixHeap 
    61     class UnderFlowPriorityError : public Exception { 
     61    class PriorityUnderflowError : public Exception { 
    6262    public: 
    6363      virtual const char* what() const throw() { 
    64         return "lemon::RadixHeap::UnderFlowPriorityError"; 
     64        return "lemon::RadixHeap::PriorityUnderflowError"; 
    6565      } 
    6666    }; 
     
    9595    }; 
    9696 
    97     std::vector<RadixItem> data; 
    98     std::vector<RadixBox> boxes; 
     97    std::vector<RadixItem> _data; 
     98    std::vector<RadixBox> _boxes; 
    9999 
    100100    ItemIntMap &_iim; 
     
    113113      : _iim(map) 
    114114    { 
    115       boxes.push_back(RadixBox(minimum, 1)); 
    116       boxes.push_back(RadixBox(minimum + 1, 1)); 
    117       while (lower(boxes.size() - 1, capacity + minimum - 1)) { 
     115      _boxes.push_back(RadixBox(minimum, 1)); 
     116      _boxes.push_back(RadixBox(minimum + 1, 1)); 
     117      while (lower(_boxes.size() - 1, capacity + minimum - 1)) { 
    118118        extend(); 
    119119      } 
     
    123123    /// 
    124124    /// This function returns the number of items stored in the heap. 
    125     int size() const { return data.size(); } 
     125    int size() const { return _data.size(); } 
    126126 
    127127    /// \brief Check if the heap is empty. 
    128128    /// 
    129129    /// This function returns \c true if the heap is empty. 
    130     bool empty() const { return data.empty(); } 
     130    bool empty() const { return _data.empty(); } 
    131131 
    132132    /// \brief Make the heap empty. 
     
    140140    /// \param capacity The capacity of the heap. 
    141141    void clear(int minimum = 0, int capacity = 0) { 
    142       data.clear(); boxes.clear(); 
    143       boxes.push_back(RadixBox(minimum, 1)); 
    144       boxes.push_back(RadixBox(minimum + 1, 1)); 
    145       while (lower(boxes.size() - 1, capacity + minimum - 1)) { 
     142      _data.clear(); _boxes.clear(); 
     143      _boxes.push_back(RadixBox(minimum, 1)); 
     144      _boxes.push_back(RadixBox(minimum + 1, 1)); 
     145      while (lower(_boxes.size() - 1, capacity + minimum - 1)) { 
    146146        extend(); 
    147147      } 
     
    151151 
    152152    bool upper(int box, Prio pr) { 
    153       return pr < boxes[box].min; 
     153      return pr < _boxes[box].min; 
    154154    } 
    155155 
    156156    bool lower(int box, Prio pr) { 
    157       return pr >= boxes[box].min + boxes[box].size; 
     157      return pr >= _boxes[box].min + _boxes[box].size; 
    158158    } 
    159159 
    160160    // Remove item from the box list 
    161161    void remove(int index) { 
    162       if (data[index].prev >= 0) { 
    163         data[data[index].prev].next = data[index].next; 
     162      if (_data[index].prev >= 0) { 
     163        _data[_data[index].prev].next = _data[index].next; 
    164164      } else { 
    165         boxes[data[index].box].first = data[index].next; 
    166       } 
    167       if (data[index].next >= 0) { 
    168         data[data[index].next].prev = data[index].prev; 
     165        _boxes[_data[index].box].first = _data[index].next; 
     166      } 
     167      if (_data[index].next >= 0) { 
     168        _data[_data[index].next].prev = _data[index].prev; 
    169169      } 
    170170    } 
     
    172172    // Insert item into the box list 
    173173    void insert(int box, int index) { 
    174       if (boxes[box].first == -1) { 
    175         boxes[box].first = index; 
    176         data[index].next = data[index].prev = -1; 
     174      if (_boxes[box].first == -1) { 
     175        _boxes[box].first = index; 
     176        _data[index].next = _data[index].prev = -1; 
    177177      } else { 
    178         data[index].next = boxes[box].first; 
    179         data[boxes[box].first].prev = index; 
    180         data[index].prev = -1; 
    181         boxes[box].first = index; 
    182       } 
    183       data[index].box = box; 
     178        _data[index].next = _boxes[box].first; 
     179        _data[_boxes[box].first].prev = index; 
     180        _data[index].prev = -1; 
     181        _boxes[box].first = index; 
     182      } 
     183      _data[index].box = box; 
    184184    } 
    185185 
    186186    // Add a new box to the box list 
    187187    void extend() { 
    188       int min = boxes.back().min + boxes.back().size; 
    189       int bs = 2 * boxes.back().size; 
    190       boxes.push_back(RadixBox(min, bs)); 
     188      int min = _boxes.back().min + _boxes.back().size; 
     189      int bs = 2 * _boxes.back().size; 
     190      _boxes.push_back(RadixBox(min, bs)); 
    191191    } 
    192192 
    193193    // Move an item up into the proper box. 
    194     void bubble_up(int index) { 
    195       if (!lower(data[index].box, data[index].prio)) return; 
     194    void bubbleUp(int index) { 
     195      if (!lower(_data[index].box, _data[index].prio)) return; 
    196196      remove(index); 
    197       int box = findUp(data[index].box, data[index].prio); 
     197      int box = findUp(_data[index].box, _data[index].prio); 
    198198      insert(box, index); 
    199199    } 
     
    202202    int findUp(int start, int pr) { 
    203203      while (lower(start, pr)) { 
    204         if (++start == int(boxes.size())) { 
     204        if (++start == int(_boxes.size())) { 
    205205          extend(); 
    206206        } 
     
    210210 
    211211    // Move an item down into the proper box 
    212     void bubble_down(int index) { 
    213       if (!upper(data[index].box, data[index].prio)) return; 
     212    void bubbleDown(int index) { 
     213      if (!upper(_data[index].box, _data[index].prio)) return; 
    214214      remove(index); 
    215       int box = findDown(data[index].box, data[index].prio); 
     215      int box = findDown(_data[index].box, _data[index].prio); 
    216216      insert(box, index); 
    217217    } 
     
    220220    int findDown(int start, int pr) { 
    221221      while (upper(start, pr)) { 
    222         if (--start < 0) throw UnderFlowPriorityError(); 
     222        if (--start < 0) throw PriorityUnderflowError(); 
    223223      } 
    224224      return start; 
     
    228228    int findFirst() { 
    229229      int first = 0; 
    230       while (boxes[first].first == -1) ++first; 
     230      while (_boxes[first].first == -1) ++first; 
    231231      return first; 
    232232    } 
     
    234234    // Gives back the minimum priority of the given box 
    235235    int minValue(int box) { 
    236       int min = data[boxes[box].first].prio; 
    237       for (int k = boxes[box].first; k != -1; k = data[k].next) { 
    238         if (data[k].prio < min) min = data[k].prio; 
     236      int min = _data[_boxes[box].first].prio; 
     237      for (int k = _boxes[box].first; k != -1; k = _data[k].next) { 
     238        if (_data[k].prio < min) min = _data[k].prio; 
    239239      } 
    240240      return min; 
     
    247247      int min = minValue(box); 
    248248      for (int i = 0; i <= box; ++i) { 
    249         boxes[i].min = min; 
    250         min += boxes[i].size; 
    251       } 
    252       int curr = boxes[box].first, next; 
     249        _boxes[i].min = min; 
     250        min += _boxes[i].size; 
     251      } 
     252      int curr = _boxes[box].first, next; 
    253253      while (curr != -1) { 
    254         next = data[curr].next; 
    255         bubble_down(curr); 
     254        next = _data[curr].next; 
     255        bubbleDown(curr); 
    256256        curr = next; 
    257257      } 
    258258    } 
    259259 
    260     void relocate_last(int index) { 
    261       if (index != int(data.size()) - 1) { 
    262         data[index] = data.back(); 
    263         if (data[index].prev != -1) { 
    264           data[data[index].prev].next = index; 
     260    void relocateLast(int index) { 
     261      if (index != int(_data.size()) - 1) { 
     262        _data[index] = _data.back(); 
     263        if (_data[index].prev != -1) { 
     264          _data[_data[index].prev].next = index; 
    265265        } else { 
    266           boxes[data[index].box].first = index; 
     266          _boxes[_data[index].box].first = index; 
    267267        } 
    268         if (data[index].next != -1) { 
    269           data[data[index].next].prev = index; 
     268        if (_data[index].next != -1) { 
     269          _data[_data[index].next].prev = index; 
    270270        } 
    271         _iim[data[index].item] = index; 
    272       } 
    273       data.pop_back(); 
     271        _iim[_data[index].item] = index; 
     272      } 
     273      _data.pop_back(); 
    274274    } 
    275275 
     
    285285    /// \warning This method may throw an \c UnderFlowPriorityException. 
    286286    void push(const Item &i, const Prio &p) { 
    287       int n = data.size(); 
     287      int n = _data.size(); 
    288288      _iim.set(i, n); 
    289       data.push_back(RadixItem(i, p)); 
    290       while (lower(boxes.size() - 1, p)) { 
     289      _data.push_back(RadixItem(i, p)); 
     290      while (lower(_boxes.size() - 1, p)) { 
    291291        extend(); 
    292292      } 
    293       int box = findDown(boxes.size() - 1, p); 
     293      int box = findDown(_boxes.size() - 1, p); 
    294294      insert(box, n); 
    295295    } 
     
    301301    Item top() const { 
    302302      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 
    303       return data[boxes[0].first].item; 
     303      return _data[_boxes[0].first].item; 
    304304    } 
    305305 
     
    310310    Prio prio() const { 
    311311      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 
    312       return data[boxes[0].first].prio; 
     312      return _data[_boxes[0].first].prio; 
    313313     } 
    314314 
     
    319319    void pop() { 
    320320      moveDown(); 
    321       int index = boxes[0].first; 
    322       _iim[data[index].item] = POST_HEAP; 
     321      int index = _boxes[0].first; 
     322      _iim[_data[index].item] = POST_HEAP; 
    323323      remove(index); 
    324       relocate_last(index); 
     324      relocateLast(index); 
    325325    } 
    326326 
     
    335335      _iim[i] = POST_HEAP; 
    336336      remove(index); 
    337       relocate_last(index); 
     337      relocateLast(index); 
    338338   } 
    339339 
     
    345345    Prio operator[](const Item &i) const { 
    346346      int idx = _iim[i]; 
    347       return data[idx].prio; 
     347      return _data[idx].prio; 
    348348    } 
    349349 
     
    363363        push(i, p); 
    364364      } 
    365       else if( p >= data[idx].prio ) { 
    366         data[idx].prio = p; 
    367         bubble_up(idx); 
     365      else if( p >= _data[idx].prio ) { 
     366        _data[idx].prio = p; 
     367        bubbleUp(idx); 
    368368      } else { 
    369         data[idx].prio = p; 
    370         bubble_down(idx); 
     369        _data[idx].prio = p; 
     370        bubbleDown(idx); 
    371371      } 
    372372    } 
     
    381381    void decrease(const Item &i, const Prio &p) { 
    382382      int idx = _iim[i]; 
    383       data[idx].prio = p; 
    384       bubble_down(idx); 
     383      _data[idx].prio = p; 
     384      bubbleDown(idx); 
    385385    } 
    386386 
     
    393393    void increase(const Item &i, const Prio &p) { 
    394394      int idx = _iim[i]; 
    395       data[idx].prio = p; 
    396       bubble_up(idx); 
     395      _data[idx].prio = p; 
     396      bubbleUp(idx); 
    397397    } 
    398398 
Note: See TracChangeset for help on using the changeset viewer.