COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 209:765619b7cbb2 in lemon for lemon/unionfind.h


Ignore:
Timestamp:
07/13/08 20:51:02 (17 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/unionfind.h

    r103 r209  
    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 *
    55 * Copyright (C) 2003-2008
    … …  
    3939  /// \brief A \e Union-Find data structure implementation
    4040  ///
    41   /// The class implements the \e Union-Find data structure. 
     41  /// The class implements the \e Union-Find data structure.
    4242  /// The union operation uses rank heuristic, while
    4343  /// the find operation uses path compression.
    44   /// This is a very simple but efficient implementation, providing 
     44  /// This is a very simple but efficient implementation, providing
    4545  /// only four methods: join (union), find, insert and size.
    4646  /// For more features see the \ref UnionFindEnum class.
    … …  
    5151  ///
    5252  /// \pre You need to add all the elements by the \ref insert()
    53   /// method. 
     53  /// method.
    5454  template <typename _ItemIntMap>
    5555  class UnionFind {
    … …  
    112112    /// \brief Inserts a new element into the structure.
    113113    ///
    114     /// This method inserts a new element into the data structure. 
     114    /// This method inserts a new element into the data structure.
    115115    ///
    116116    /// The method returns the index of the new component.
    … …  
    124124    /// \brief Joining the components of element \e a and element \e b.
    125125    ///
    126     /// This is the \e union operation of the Union-Find structure. 
     126    /// This is the \e union operation of the Union-Find structure.
    127127    /// Joins the component of element \e a and component of
    128128    /// element \e b. If \e a and \e b are in the same component then
    … …  
    132132      int kb = repIndex(index[b]);
    133133
    134       if ( ka == kb ) 
    135         return false;
     134      if ( ka == kb )
     135        return false;
    136136
    137137      if (items[ka] < items[kb]) {
    138         items[ka] += items[kb];
    139         items[kb] = ka;
     138        items[ka] += items[kb];
     139        items[kb] = ka;
    140140      } else {
    141         items[kb] += items[ka];
    142         items[ka] = kb;
     141        items[kb] += items[ka];
     142        items[ka] = kb;
    143143      }
    144144      return true;
    … …  
    174174  class UnionFindEnum {
    175175  public:
    176    
     176
    177177    typedef _ItemIntMap ItemIntMap;
    178178    typedef typename ItemIntMap::Key Item;
    179179
    180180  private:
    181    
     181
    182182    ItemIntMap& index;
    183183
    … …  
    203203      int next, prev;
    204204    };
    205    
     205
    206206    std::vector<ClassT> classes;
    207207    int firstClass, firstFreeClass;
    … …  
    209209    int newClass() {
    210210      if (firstFreeClass == -1) {
    211         int cdx = classes.size();
    212         classes.push_back(ClassT());
    213         return cdx;
     211        int cdx = classes.size();
     212        classes.push_back(ClassT());
     213        return cdx;
    214214      } else {
    215         int cdx = firstFreeClass;
    216         firstFreeClass = classes[firstFreeClass].next;
    217         return cdx;
     215        int cdx = firstFreeClass;
     216        firstFreeClass = classes[firstFreeClass].next;
     217        return cdx;
    218218      }
    219219    }
    … …  
    221221    int newItem() {
    222222      if (firstFreeItem == -1) {
    223         int idx = items.size();
    224         items.push_back(ItemT());
    225         return idx;
     223        int idx = items.size();
     224        items.push_back(ItemT());
     225        return idx;
    226226      } else {
    227         int idx = firstFreeItem;
    228         firstFreeItem = items[firstFreeItem].next;
    229         return idx;
     227        int idx = firstFreeItem;
     228        firstFreeItem = items[firstFreeItem].next;
     229        return idx;
    230230      }
    231231    }
    … …  
    268268      items[items[idx].prev].next = items[idx].next;
    269269      items[items[idx].next].prev = items[idx].prev;
    270      
     270
    271271      items[idx].next = firstFreeItem;
    272272      firstFreeItem = idx;
    … …  
    279279      items[ak].prev = items[bk].prev;
    280280      items[bk].prev = tmp;
    281        
     281
    282282    }
    283283
    … …  
    289289      classes[cls].prev = -1;
    290290      firstClass = cls;
    291     } 
     291    }
    292292
    293293    void unlaceClass(int cls) {
    … …  
    300300        classes[classes[cls].next].prev = classes[cls].prev;
    301301      }
    302      
     302
    303303      classes[cls].next = firstFreeClass;
    304304      firstFreeClass = cls;
    305     } 
     305    }
    306306
    307307  public:
    308308
    309     UnionFindEnum(ItemIntMap& _index) 
    310       : index(_index), items(), firstFreeItem(-1), 
    311         firstClass(-1), firstFreeClass(-1) {}
    312    
     309    UnionFindEnum(ItemIntMap& _index)
     310      : index(_index), items(), firstFreeItem(-1),
     311        firstClass(-1), firstFreeClass(-1) {}
     312
    313313    /// \brief Inserts the given element into a new component.
    314314    ///
    … …  
    333333
    334334      firstClass = cdx;
    335      
     335
    336336      return cdx;
    337337    }
    … …  
    340340    ///
    341341    /// This methods inserts the element \e a into the component of the
    342     /// element \e comp. 
     342    /// element \e comp.
    343343    void insert(const Item& item, int cls) {
    344344      int rdx = classes[cls].firstItem;
    … …  
    373373    /// \brief Joining the component of element \e a and element \e b.
    374374    ///
    375     /// This is the \e union operation of the Union-Find structure. 
     375    /// This is the \e union operation of the Union-Find structure.
    376376    /// Joins the component of element \e a and component of
    377377    /// element \e b. If \e a and \e b are in the same component then
    … …  
    383383
    384384      if (ak == bk) {
    385         return -1;
     385        return -1;
    386386      }
    387387
    … …  
    392392
    393393      if (classes[acx].size > classes[bcx].size) {
    394         classes[acx].size += classes[bcx].size;
    395         items[bk].parent = ak;
     394        classes[acx].size += classes[bcx].size;
     395        items[bk].parent = ak;
    396396        unlaceClass(bcx);
    397         rcx = acx;
     397        rcx = acx;
    398398      } else {
    399         classes[bcx].size += classes[acx].size;
    400         items[ak].parent = bk;
     399        classes[bcx].size += classes[acx].size;
     400        items[ak].parent = bk;
    401401        unlaceClass(acx);
    402         rcx = bcx;
     402        rcx = bcx;
    403403      }
    404404      spliceItems(ak, bk);
    … …  
    414414    }
    415415
    416     /// \brief Splits up the component. 
     416    /// \brief Splits up the component.
    417417    ///
    418418    /// Splitting the component into singleton components (component
    … …  
    424424        int next = items[idx].next;
    425425
    426         singletonItem(idx);
    427 
    428         int cdx = newClass();       
     426        singletonItem(idx);
     427
     428        int cdx = newClass();
    429429        items[idx].parent = ~cdx;
    430430
    431         laceClass(cdx);
    432         classes[cdx].size = 1;
    433         classes[cdx].firstItem = idx;
    434        
     431        laceClass(cdx);
     432        classes[cdx].size = 1;
     433        classes[cdx].firstItem = idx;
     434
    435435        idx = next;
    436436      }
    … …  
    440440
    441441      classes[~(items[idx].parent)].size = 1;
    442      
     442
    443443    }
    444444
    … …  
    458458      int cdx = classIndex(idx);
    459459      if (idx == fdx) {
    460         unlaceClass(cdx);
    461         items[idx].next = firstFreeItem;
    462         firstFreeItem = idx;
    463         return;
     460        unlaceClass(cdx);
     461        items[idx].next = firstFreeItem;
     462        firstFreeItem = idx;
     463        return;
    464464      } else {
    465         classes[cdx].firstItem = fdx;
    466         --classes[cdx].size;
    467         items[fdx].parent = ~cdx;
    468 
    469         unlaceItem(idx);
    470         idx = items[fdx].next;
    471         while (idx != fdx) {
    472           items[idx].parent = fdx;
    473           idx = items[idx].next;
    474         }
    475          
     465        classes[cdx].firstItem = fdx;
     466        --classes[cdx].size;
     467        items[fdx].parent = ~cdx;
     468
     469        unlaceItem(idx);
     470        idx = items[fdx].next;
     471        while (idx != fdx) {
     472          items[idx].parent = fdx;
     473          idx = items[idx].next;
     474        }
     475
    476476      }
    477477
    … …  
    515515      /// Constructor to get invalid iterator
    516516      ClassIt(Invalid) : unionFind(0), cdx(-1) {}
    517      
     517
    518518      /// \brief Increment operator
    519519      ///
    … …  
    523523        return *this;
    524524      }
    525      
     525
    526526      /// \brief Conversion operator
    527527      ///
    … …  
    534534      ///
    535535      /// Equality operator
    536       bool operator==(const ClassIt& i) { 
     536      bool operator==(const ClassIt& i) {
    537537        return i.cdx == cdx;
    538538      }
    … …  
    541541      ///
    542542      /// Inequality operator
    543       bool operator!=(const ClassIt& i) { 
     543      bool operator!=(const ClassIt& i) {
    544544        return i.cdx != cdx;
    545545      }
    546      
     546
    547547    private:
    548548      const UnionFindEnum* unionFind;
    … …  
    578578      /// Constructor to get invalid iterator
    579579      ItemIt(Invalid) : unionFind(0), idx(-1) {}
    580      
     580
    581581      /// \brief Increment operator
    582582      ///
    … …  
    587587        return *this;
    588588      }
    589      
     589
    590590      /// \brief Conversion operator
    591591      ///
    … …  
    598598      ///
    599599      /// Equality operator
    600       bool operator==(const ItemIt& i) { 
     600      bool operator==(const ItemIt& i) {
    601601        return i.idx == idx;
    602602      }
    … …  
    605605      ///
    606606      /// Inequality operator
    607       bool operator!=(const ItemIt& i) { 
     607      bool operator!=(const ItemIt& i) {
    608608        return i.idx != idx;
    609609      }
    610      
     610
    611611    private:
    612612      const UnionFindEnum* unionFind;
    … …  
    631631  class ExtendFindEnum {
    632632  public:
    633    
     633
    634634    typedef _ItemIntMap ItemIntMap;
    635635    typedef typename ItemIntMap::Key Item;
    636636
    637637  private:
    638    
     638
    639639    ItemIntMap& index;
    640640
    … …  
    659659    int newClass() {
    660660      if (firstFreeClass != -1) {
    661         int cdx = firstFreeClass;
    662         firstFreeClass = classes[cdx].next;
    663         return cdx;
     661        int cdx = firstFreeClass;
     662        firstFreeClass = classes[cdx].next;
     663        return cdx;
    664664      } else {
    665         classes.push_back(ClassT());
    666         return classes.size() - 1;
     665        classes.push_back(ClassT());
     666        return classes.size() - 1;
    667667      }
    668668    }
    … …  
    670670    int newItem() {
    671671      if (firstFreeItem != -1) {
    672         int idx = firstFreeItem;
    673         firstFreeItem = items[idx].next;
    674         return idx;
     672        int idx = firstFreeItem;
     673        firstFreeItem = items[idx].next;
     674        return idx;
    675675      } else {
    676         items.push_back(ItemT());
    677         return items.size() - 1;
     676        items.push_back(ItemT());
     677        return items.size() - 1;
    678678      }
    679679    }
    … …  
    682682
    683683    /// \brief Constructor
    684     ExtendFindEnum(ItemIntMap& _index) 
    685       : index(_index), items(), firstFreeItem(-1), 
    686         classes(), firstClass(-1), firstFreeClass(-1) {}
    687    
     684    ExtendFindEnum(ItemIntMap& _index)
     685      : index(_index), items(), firstFreeItem(-1),
     686        classes(), firstClass(-1), firstFreeClass(-1) {}
     687
    688688    /// \brief Inserts the given element into a new component.
    689689    ///
    … …  
    695695      classes[cdx].next = firstClass;
    696696      if (firstClass != -1) {
    697         classes[firstClass].prev = cdx;
     697        classes[firstClass].prev = cdx;
    698698      }
    699699      firstClass = cdx;
    700      
     700
    701701      int idx = newItem();
    702702      items[idx].item = item;
    … …  
    708708
    709709      index.set(item, idx);
    710      
     710
    711711      return cdx;
    712712    }
    … …  
    751751      return items[classes[cls].firstItem].item;
    752752    }
    753    
     753
    754754    /// \brief Removes the given element from the structure.
    755755    ///
    … …  
    762762      int idx = index[item];
    763763      int cdx = items[idx].cls;
    764      
     764
    765765      if (idx == items[idx].next) {
    766         if (classes[cdx].prev != -1) {
    767           classes[classes[cdx].prev].next = classes[cdx].next;
    768         } else {
    769           firstClass = classes[cdx].next;
    770         }
    771         if (classes[cdx].next != -1) {
    772           classes[classes[cdx].next].prev = classes[cdx].prev;
    773         }
    774         classes[cdx].next = firstFreeClass;
    775         firstFreeClass = cdx;
     766        if (classes[cdx].prev != -1) {
     767          classes[classes[cdx].prev].next = classes[cdx].next;
     768        } else {
     769          firstClass = classes[cdx].next;
     770        }
     771        if (classes[cdx].next != -1) {
     772          classes[classes[cdx].next].prev = classes[cdx].prev;
     773        }
     774        classes[cdx].next = firstFreeClass;
     775        firstFreeClass = cdx;
    776776      } else {
    777         classes[cdx].firstItem = items[idx].next;
    778         items[items[idx].next].prev = items[idx].prev;
    779         items[items[idx].prev].next = items[idx].next;
     777        classes[cdx].firstItem = items[idx].next;
     778        items[items[idx].next].prev = items[idx].prev;
     779        items[items[idx].prev].next = items[idx].next;
    780780      }
    781781      items[idx].next = firstFreeItem;
    782782      firstFreeItem = idx;
    783        
    784     }   
    785 
    786    
     783
     784    }
     785
     786
    787787    /// \brief Removes the component of the given element from the structure.
    788788    ///
    … …  
    797797
    798798      if (classes[cdx].prev != -1) {
    799         classes[classes[cdx].prev].next = classes[cdx].next;
     799        classes[classes[cdx].prev].next = classes[cdx].next;
    800800      } else {
    801         firstClass = classes[cdx].next;
     801        firstClass = classes[cdx].next;
    802802      }
    803803      if (classes[cdx].next != -1) {
    804         classes[classes[cdx].next].prev = classes[cdx].prev;
     804        classes[classes[cdx].next].prev = classes[cdx].prev;
    805805      }
    806806      classes[cdx].next = firstFreeClass;
    … …  
    825825      /// Constructor to get invalid iterator
    826826      ClassIt(Invalid) : extendFind(0), cdx(-1) {}
    827      
     827
    828828      /// \brief Increment operator
    829829      ///
    … …  
    833833        return *this;
    834834      }
    835      
     835
    836836      /// \brief Conversion operator
    837837      ///
    … …  
    844844      ///
    845845      /// Equality operator
    846       bool operator==(const ClassIt& i) { 
     846      bool operator==(const ClassIt& i) {
    847847        return i.cdx == cdx;
    848848      }
    … …  
    851851      ///
    852852      /// Inequality operator
    853       bool operator!=(const ClassIt& i) { 
     853      bool operator!=(const ClassIt& i) {
    854854        return i.cdx != cdx;
    855855      }
    856      
     856
    857857    private:
    858858      const ExtendFindEnum* extendFind;
    … …  
    888888      /// Constructor to get invalid iterator
    889889      ItemIt(Invalid) : extendFind(0), idx(-1) {}
    890      
     890
    891891      /// \brief Increment operator
    892892      ///
    … …  
    894894      ItemIt& operator++() {
    895895        idx = extendFind->items[idx].next;
    896         if (fdx == idx) idx = -1;
     896        if (fdx == idx) idx = -1;
    897897        return *this;
    898898      }
    899      
     899
    900900      /// \brief Conversion operator
    901901      ///
    … …  
    908908      ///
    909909      /// Equality operator
    910       bool operator==(const ItemIt& i) { 
     910      bool operator==(const ItemIt& i) {
    911911        return i.idx == idx;
    912912      }
    … …  
    915915      ///
    916916      /// Inequality operator
    917       bool operator!=(const ItemIt& i) { 
     917      bool operator!=(const ItemIt& i) {
    918918        return i.idx != idx;
    919919      }
    920      
     920
    921921    private:
    922922      const ExtendFindEnum* extendFind;
    … …  
    950950  /// method.
    951951  ///
    952   template <typename _Value, typename _ItemIntMap, 
     952  template <typename _Value, typename _ItemIntMap,
    953953            typename _Comp = std::less<_Value> >
    954954  class HeapUnionFind {
    955955  public:
    956    
     956
    957957    typedef _Value Value;
    958958    typedef typename _ItemIntMap::Key Item;
    … …  
    10551055      id = nodes[id].next;
    10561056      while (depth--) {
    1057         id = nodes[id].left;     
     1057        id = nodes[id].left;
    10581058      }
    10591059      return id;
    … …  
    11331133      nodes[kd].right = nodes[id].prev;
    11341134      nodes[nodes[id].prev].next = -1;
    1135      
     1135
    11361136      nodes[jd].left = id;
    11371137      nodes[id].prev = -1;
    … …  
    11421142        id = nodes[id].next;
    11431143        ++num;
    1144       }     
     1144      }
    11451145      nodes[kd].size -= num;
    11461146      nodes[jd].size = num;
    … …  
    11661166      int jd = ~(classes[id].parent);
    11671167      while (nodes[jd].left != -1) {
    1168         int kd = nodes[jd].left;
    1169         if (nodes[jd].size == 1) {
    1170           if (nodes[jd].parent < 0) {
    1171             classes[id].parent = ~kd;
    1172             classes[id].depth -= 1;
    1173             nodes[kd].parent = ~id;
    1174             deleteNode(jd);
    1175             jd = kd;
    1176           } else {
    1177             int pd = nodes[jd].parent;
    1178             if (nodes[nodes[jd].next].size < cmax) {
    1179               pushLeft(nodes[jd].next, nodes[jd].left);
    1180               if (less(nodes[jd].left, nodes[jd].next)) {
    1181                 nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
    1182                 nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
    1183               }
    1184               popLeft(pd);
    1185               deleteNode(jd);
    1186               jd = pd;
    1187             } else {
    1188               int ld = nodes[nodes[jd].next].left;
    1189               popLeft(nodes[jd].next);
    1190               pushRight(jd, ld);
    1191               if (less(ld, nodes[jd].left)) {
    1192                 nodes[jd].item = nodes[ld].item;
    1193                 nodes[jd].prio = nodes[jd].prio;
    1194               }
    1195               if (nodes[nodes[jd].next].item == nodes[ld].item) {
    1196                 setPrio(nodes[jd].next);
    1197               }
    1198               jd = nodes[jd].left;
    1199             }
    1200           }
    1201         } else {
    1202           jd = nodes[jd].left;
    1203         }
    1204       }
    1205     }   
     1168        int kd = nodes[jd].left;
     1169        if (nodes[jd].size == 1) {
     1170          if (nodes[jd].parent < 0) {
     1171            classes[id].parent = ~kd;
     1172            classes[id].depth -= 1;
     1173            nodes[kd].parent = ~id;
     1174            deleteNode(jd);
     1175            jd = kd;
     1176          } else {
     1177            int pd = nodes[jd].parent;
     1178            if (nodes[nodes[jd].next].size < cmax) {
     1179              pushLeft(nodes[jd].next, nodes[jd].left);
     1180              if (less(nodes[jd].left, nodes[jd].next)) {
     1181                nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
     1182                nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
     1183              }
     1184              popLeft(pd);
     1185              deleteNode(jd);
     1186              jd = pd;
     1187            } else {
     1188              int ld = nodes[nodes[jd].next].left;
     1189              popLeft(nodes[jd].next);
     1190              pushRight(jd, ld);
     1191              if (less(ld, nodes[jd].left)) {
     1192                nodes[jd].item = nodes[ld].item;
     1193                nodes[jd].prio = nodes[jd].prio;
     1194              }
     1195              if (nodes[nodes[jd].next].item == nodes[ld].item) {
     1196                setPrio(nodes[jd].next);
     1197              }
     1198              jd = nodes[jd].left;
     1199            }
     1200          }
     1201        } else {
     1202          jd = nodes[jd].left;
     1203        }
     1204      }
     1205    }
    12061206
    12071207    void repairRight(int id) {
    12081208      int jd = ~(classes[id].parent);
    12091209      while (nodes[jd].right != -1) {
    1210         int kd = nodes[jd].right;
    1211         if (nodes[jd].size == 1) {
    1212           if (nodes[jd].parent < 0) {
    1213             classes[id].parent = ~kd;
    1214             classes[id].depth -= 1;
    1215             nodes[kd].parent = ~id;
    1216             deleteNode(jd);
    1217             jd = kd;
    1218           } else {
    1219             int pd = nodes[jd].parent;
    1220             if (nodes[nodes[jd].prev].size < cmax) {
    1221               pushRight(nodes[jd].prev, nodes[jd].right);
    1222               if (less(nodes[jd].right, nodes[jd].prev)) {
    1223                 nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
    1224                 nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
    1225               }
    1226               popRight(pd);
    1227               deleteNode(jd);
    1228               jd = pd;
    1229             } else {
    1230               int ld = nodes[nodes[jd].prev].right;
    1231               popRight(nodes[jd].prev);
    1232               pushLeft(jd, ld);
    1233               if (less(ld, nodes[jd].right)) {
    1234                 nodes[jd].item = nodes[ld].item;
    1235                 nodes[jd].prio = nodes[jd].prio;
    1236               }
    1237               if (nodes[nodes[jd].prev].item == nodes[ld].item) {
    1238                 setPrio(nodes[jd].prev);
    1239               }
    1240               jd = nodes[jd].right;
    1241             }
    1242           }
    1243         } else {
    1244           jd = nodes[jd].right;
    1245         }
     1210        int kd = nodes[jd].right;
     1211        if (nodes[jd].size == 1) {
     1212          if (nodes[jd].parent < 0) {
     1213            classes[id].parent = ~kd;
     1214            classes[id].depth -= 1;
     1215            nodes[kd].parent = ~id;
     1216            deleteNode(jd);
     1217            jd = kd;
     1218          } else {
     1219            int pd = nodes[jd].parent;
     1220            if (nodes[nodes[jd].prev].size < cmax) {
     1221              pushRight(nodes[jd].prev, nodes[jd].right);
     1222              if (less(nodes[jd].right, nodes[jd].prev)) {
     1223                nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
     1224                nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
     1225              }
     1226              popRight(pd);
     1227              deleteNode(jd);
     1228              jd = pd;
     1229            } else {
     1230              int ld = nodes[nodes[jd].prev].right;
     1231              popRight(nodes[jd].prev);
     1232              pushLeft(jd, ld);
     1233              if (less(ld, nodes[jd].right)) {
     1234                nodes[jd].item = nodes[ld].item;
     1235                nodes[jd].prio = nodes[jd].prio;
     1236              }
     1237              if (nodes[nodes[jd].prev].item == nodes[ld].item) {
     1238                setPrio(nodes[jd].prev);
     1239              }
     1240              jd = nodes[jd].right;
     1241            }
     1242          }
     1243        } else {
     1244          jd = nodes[jd].right;
     1245        }
    12461246      }
    12471247    }
    … …  
    12771277    /// \brief Constructs the union-find.
    12781278    ///
    1279     /// Constructs the union-find. 
     1279    /// Constructs the union-find.
    12801280    /// \brief _index The index map of the union-find. The data
    12811281    /// structure uses internally for store references.
    1282     HeapUnionFind(ItemIntMap& _index) 
    1283       : index(_index), first_class(-1), 
    1284         first_free_class(-1), first_free_node(-1) {}
     1282    HeapUnionFind(ItemIntMap& _index)
     1283      : index(_index), first_class(-1),
     1284        first_free_class(-1), first_free_node(-1) {}
    12851285
    12861286    /// \brief Insert a new node into a new component.
    … …  
    13041304      nodes[id].item = item;
    13051305      index[item] = id;
    1306      
     1306
    13071307      int class_id = newClass();
    13081308      classes[class_id].parent = ~id;
    … …  
    13111311      classes[class_id].left = -1;
    13121312      classes[class_id].right = -1;
    1313      
     1313
    13141314      if (first_class != -1) {
    13151315        classes[first_class].prev = class_id;
    … …  
    13201320
    13211321      nodes[id].parent = ~class_id;
    1322      
     1322
    13231323      return class_id;
    13241324    }
    … …  
    13331333      return findClass(index[item]);
    13341334    }
    1335    
     1335
    13361336    /// \brief Joins the classes.
    13371337    ///
    … …  
    13721372        }
    13731373        classes[classes[l].prev].next = classes[l].next;
    1374        
     1374
    13751375        classes[l].prev = -1;
    13761376        classes[l].next = -1;
    … …  
    13781378        classes[l].depth = leftNode(l);
    13791379        classes[l].parent = class_id;
    1380        
     1380
    13811381      }
    13821382
    … …  
    14561456              pushLeft(new_parent, ~(classes[l].parent));
    14571457              setPrio(new_parent);
    1458              
     1458
    14591459              classes[r].parent = ~new_parent;
    14601460              classes[r].depth += 1;
    … …  
    14711471            classes[l].depth = classes[r].depth;
    14721472          } else {
    1473             if (classes[l].depth != 0 && 
    1474                 nodes[~(classes[l].parent)].size + 
     1473            if (classes[l].depth != 0 &&
     1474                nodes[~(classes[l].parent)].size +
    14751475                nodes[~(classes[r].parent)].size <= cmax) {
    14761476              splice(~(classes[l].parent), ~(classes[r].parent));
    14771477              deleteNode(~(classes[r].parent));
    14781478              if (less(~(classes[r].parent), ~(classes[l].parent))) {
    1479                 nodes[~(classes[l].parent)].prio = 
     1479                nodes[~(classes[l].parent)].prio =
    14801480                  nodes[~(classes[r].parent)].prio;
    1481                 nodes[~(classes[l].parent)].item = 
     1481                nodes[~(classes[l].parent)].item =
    14821482                  nodes[~(classes[r].parent)].item;
    14831483              }
    … …  
    14881488              pushRight(new_parent, ~(classes[r].parent));
    14891489              setPrio(new_parent);
    1490            
     1490
    14911491              classes[l].parent = ~new_parent;
    14921492              classes[l].depth += 1;
    … …  
    15431543        classes[first_class].prev = classes[id].right;
    15441544        first_class = classes[id].left;
    1545        
     1545
    15461546        if (classes[id].next != -1) {
    15471547          classes[classes[id].next].prev = classes[id].prev;
    15481548        }
    15491549        classes[classes[id].prev].next = classes[id].next;
    1550        
     1550
    15511551        deleteClass(id);
    15521552      }
    … …  
    15581558            l = nodes[l].parent;
    15591559          }
    1560           int r = l;   
     1560          int r = l;
    15611561          while (nodes[l].parent >= 0) {
    15621562            l = nodes[l].parent;
    … …  
    15811581          repairRight(~(nodes[l].parent));
    15821582          repairLeft(cs[i]);
    1583          
     1583
    15841584          *out++ = cs[i];
    15851585        }
    … …  
    16041604      }
    16051605    }
    1606      
     1606
    16071607    /// \brief Increase the priority of the current item.
    16081608    ///
    … …  
    16311631      }
    16321632    }
    1633    
     1633
    16341634    /// \brief Gives back the minimum priority of the class.
    16351635    ///
    … …  
    16471647
    16481648    /// \brief Gives back a representant item of the class.
    1649     /// 
     1649    ///
    16501650    /// The representant is indpendent from the priorities of the
    1651     /// items. 
     1651    /// items.
    16521652    /// \return Gives back a representant item of the class.
    16531653    const Item& classRep(int id) const {
    … …  
    16751675      const HeapUnionFind* _huf;
    16761676      int _id, _lid;
    1677      
     1677
    16781678    public:
    16791679
    1680       /// \brief Default constructor 
    1681       ///
    1682       /// Default constructor 
     1680      /// \brief Default constructor
     1681      ///
     1682      /// Default constructor
    16831683      ItemIt() {}
    16841684
    … …  
    16961696          _id = _huf->leftNode(id);
    16971697          _lid = -1;
    1698         } 
    1699       }
    1700      
     1698        }
     1699      }
     1700
    17011701      /// \brief Increment operator
    17021702      ///
    … …  
    17131713        return _huf->nodes[_id].item;
    17141714      }
    1715      
     1715
    17161716      /// \brief Equality operator
    17171717      ///
    17181718      /// Equality operator
    1719       bool operator==(const ItemIt& i) { 
     1719      bool operator==(const ItemIt& i) {
    17201720        return i._id == _id;
    17211721      }
    … …  
    17241724      ///
    17251725      /// Inequality operator
    1726       bool operator!=(const ItemIt& i) { 
     1726      bool operator!=(const ItemIt& i) {
    17271727        return i._id != _id;
    17281728      }
    … …  
    17311731      ///
    17321732      /// Equality operator
    1733       bool operator==(Invalid) { 
     1733      bool operator==(Invalid) {
    17341734        return _id == _lid;
    17351735      }
    … …  
    17381738      ///
    17391739      /// Inequality operator
    1740       bool operator!=(Invalid) { 
     1740      bool operator!=(Invalid) {
    17411741        return _id != _lid;
    17421742      }
    1743      
     1743
    17441744    };
    17451745
    17461746    /// \brief Class iterator
    17471747    ///
    1748     /// The iterator stores 
     1748    /// The iterator stores
    17491749    class ClassIt {
    17501750    private:
    … …  
    17551755    public:
    17561756
    1757       ClassIt(const HeapUnionFind& huf) 
     1757      ClassIt(const HeapUnionFind& huf)
    17581758        : _huf(&huf), _id(huf.first_class) {}
    17591759
    1760       ClassIt(const HeapUnionFind& huf, int cls) 
     1760      ClassIt(const HeapUnionFind& huf, int cls)
    17611761        : _huf(&huf), _id(huf.classes[cls].left) {}
    17621762
    17631763      ClassIt(Invalid) : _huf(0), _id(-1) {}
    1764      
     1764
    17651765      const ClassIt& operator++() {
    17661766        _id = _huf->classes[_id].next;
    1767         return *this;
     1767        return *this;
    17681768      }
    17691769
    … …  
    17711771      ///
    17721772      /// Equality operator
    1773       bool operator==(const ClassIt& i) { 
     1773      bool operator==(const ClassIt& i) {
    17741774        return i._id == _id;
    17751775      }
    … …  
    17781778      ///
    17791779      /// Inequality operator
    1780       bool operator!=(const ClassIt& i) { 
     1780      bool operator!=(const ClassIt& i) {
    17811781        return i._id != _id;
    1782       }     
    1783      
     1782      }
     1783
    17841784      operator int() const {
    1785         return _id;
    1786       }
    1787            
     1785        return _id;
     1786      }
     1787
    17881788    };
    17891789
Note: See TracChangeset for help on using the changeset viewer.