COIN-OR::LEMON - Graph Library

Changeset 2548:a3ba22ebccc6 in lemon-0.x for lemon/unionfind.h


Ignore:
Timestamp:
12/28/07 12:00:51 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3425
Message:

Edmond's Blossom shrinking algroithm:
MaxWeightedMatching?
MaxWeightedPerfectMatching?

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/unionfind.h

    r2542 r2548  
    925925  };
    926926
     927  /// \ingroup auxdat
     928  ///
     929  /// \brief A \e Union-Find data structure implementation which
     930  /// is able to store a priority for each item and retrieve the minimum of
     931  /// each class.
     932  ///
     933  /// A \e Union-Find data structure implementation which is able to
     934  /// store a priority for each item and retrieve the minimum of each
     935  /// class. In addition, it supports the joining and splitting the
     936  /// components. If you don't need this feature then you makes
     937  /// better to use the \ref UnionFind class which is more efficient.
     938  ///
     939  /// The union-find data strcuture based on a (2, 16)-tree with a
     940  /// tournament minimum selection on the internal nodes. The insert
     941  /// operation takes O(1), the find, set, decrease and increase takes
     942  /// O(log(n)), where n is the number of nodes in the current
     943  /// component.  The complexity of join and split is O(log(n)*k),
     944  /// where n is the sum of the number of the nodes and k is the
     945  /// number of joined components or the number of the components
     946  /// after the split.
     947  ///
     948  /// \pre You need to add all the elements by the \ref insert()
     949  /// method.
     950  ///
     951  template <typename _Value, typename _ItemIntMap,
     952            typename _Comp = std::less<_Value> >
     953  class HeapUnionFind {
     954  public:
     955   
     956    typedef _Value Value;
     957    typedef typename _ItemIntMap::Key Item;
     958
     959    typedef _ItemIntMap ItemIntMap;
     960
     961    typedef _Comp Comp;
     962
     963  private:
     964
     965    static const int cmax = 3;
     966
     967    ItemIntMap& index;
     968
     969    struct ClassNode {
     970      int parent;
     971      int depth;
     972
     973      int left, right;
     974      int next, prev;
     975    };
     976
     977    int first_class;
     978    int first_free_class;
     979    std::vector<ClassNode> classes;
     980
     981    int newClass() {
     982      if (first_free_class < 0) {
     983        int id = classes.size();
     984        classes.push_back(ClassNode());
     985        return id;
     986      } else {
     987        int id = first_free_class;
     988        first_free_class = classes[id].next;
     989        return id;
     990      }
     991    }
     992
     993    void deleteClass(int id) {
     994      classes[id].next = first_free_class;
     995      first_free_class = id;
     996    }
     997
     998    struct ItemNode {
     999      int parent;
     1000      Item item;
     1001      Value prio;
     1002      int next, prev;
     1003      int left, right;
     1004      int size;
     1005    };
     1006
     1007    int first_free_node;
     1008    std::vector<ItemNode> nodes;
     1009
     1010    int newNode() {
     1011      if (first_free_node < 0) {
     1012        int id = nodes.size();
     1013        nodes.push_back(ItemNode());
     1014        return id;
     1015      } else {
     1016        int id = first_free_node;
     1017        first_free_node = nodes[id].next;
     1018        return id;
     1019      }
     1020    }
     1021
     1022    void deleteNode(int id) {
     1023      nodes[id].next = first_free_node;
     1024      first_free_node = id;
     1025    }
     1026
     1027    Comp comp;
     1028
     1029    int findClass(int id) const {
     1030      int kd = id;
     1031      while (kd >= 0) {
     1032        kd = nodes[kd].parent;
     1033      }
     1034      return ~kd;
     1035    }
     1036
     1037    int leftNode(int id) const {
     1038      int kd = ~(classes[id].parent);
     1039      for (int i = 0; i < classes[id].depth; ++i) {
     1040        kd = nodes[kd].left;
     1041      }
     1042      return kd;
     1043    }
     1044
     1045    int nextNode(int id) const {
     1046      int depth = 0;
     1047      while (id >= 0 && nodes[id].next == -1) {
     1048        id = nodes[id].parent;
     1049        ++depth;
     1050      }
     1051      if (id < 0) {
     1052        return -1;
     1053      }
     1054      id = nodes[id].next;
     1055      while (depth--) {
     1056        id = nodes[id].left;     
     1057      }
     1058      return id;
     1059    }
     1060
     1061
     1062    void setPrio(int id) {
     1063      int jd = nodes[id].left;
     1064      nodes[id].prio = nodes[jd].prio;
     1065      nodes[id].item = nodes[jd].item;
     1066      jd = nodes[jd].next;
     1067      while (jd != -1) {
     1068        if (comp(nodes[jd].prio, nodes[id].prio)) {
     1069          nodes[id].prio = nodes[jd].prio;
     1070          nodes[id].item = nodes[jd].item;
     1071        }
     1072        jd = nodes[jd].next;
     1073      }
     1074    }
     1075
     1076    void push(int id, int jd) {
     1077      nodes[id].size = 1;
     1078      nodes[id].left = nodes[id].right = jd;
     1079      nodes[jd].next = nodes[jd].prev = -1;
     1080      nodes[jd].parent = id;
     1081    }
     1082
     1083    void pushAfter(int id, int jd) {
     1084      int kd = nodes[id].parent;
     1085      if (nodes[id].next != -1) {
     1086        nodes[nodes[id].next].prev = jd;
     1087        if (kd >= 0) {
     1088          nodes[kd].size += 1;
     1089        }
     1090      } else {
     1091        if (kd >= 0) {
     1092          nodes[kd].right = jd;
     1093          nodes[kd].size += 1;
     1094        }
     1095      }
     1096      nodes[jd].next = nodes[id].next;
     1097      nodes[jd].prev = id;
     1098      nodes[id].next = jd;
     1099      nodes[jd].parent = kd;
     1100    }
     1101
     1102    void pushRight(int id, int jd) {
     1103      nodes[id].size += 1;
     1104      nodes[jd].prev = nodes[id].right;
     1105      nodes[jd].next = -1;
     1106      nodes[nodes[id].right].next = jd;
     1107      nodes[id].right = jd;
     1108      nodes[jd].parent = id;
     1109    }
     1110
     1111    void popRight(int id) {
     1112      nodes[id].size -= 1;
     1113      int jd = nodes[id].right;
     1114      nodes[nodes[jd].prev].next = -1;
     1115      nodes[id].right = nodes[jd].prev;
     1116    }
     1117
     1118    void splice(int id, int jd) {
     1119      nodes[id].size += nodes[jd].size;
     1120      nodes[nodes[id].right].next = nodes[jd].left;
     1121      nodes[nodes[jd].left].prev = nodes[id].right;
     1122      int kd = nodes[jd].left;
     1123      while (kd != -1) {
     1124        nodes[kd].parent = id;
     1125        kd = nodes[kd].next;
     1126      }
     1127    }
     1128
     1129    void split(int id, int jd) {
     1130      int kd = nodes[id].parent;
     1131      nodes[kd].right = nodes[id].prev;
     1132      nodes[nodes[id].prev].next = -1;
     1133     
     1134      nodes[jd].left = id;
     1135      nodes[id].prev = -1;
     1136      int num = 0;
     1137      while (id != -1) {
     1138        nodes[id].parent = jd;
     1139        nodes[jd].right = id;
     1140        id = nodes[id].next;
     1141        ++num;
     1142      }     
     1143      nodes[kd].size -= num;
     1144      nodes[jd].size = num;
     1145    }
     1146
     1147    void pushLeft(int id, int jd) {
     1148      nodes[id].size += 1;
     1149      nodes[jd].next = nodes[id].left;
     1150      nodes[jd].prev = -1;
     1151      nodes[nodes[id].left].prev = jd;
     1152      nodes[id].left = jd;
     1153      nodes[jd].parent = id;
     1154    }
     1155
     1156    void popLeft(int id) {
     1157      nodes[id].size -= 1;
     1158      int jd = nodes[id].left;
     1159      nodes[nodes[jd].next].prev = -1;
     1160      nodes[id].left = nodes[jd].next;
     1161    }
     1162
     1163    void repairLeft(int id) {
     1164      int jd = ~(classes[id].parent);
     1165      while (nodes[jd].left != -1) {
     1166        int kd = nodes[jd].left;
     1167        if (nodes[jd].size == 1) {
     1168          if (nodes[jd].parent < 0) {
     1169            classes[id].parent = ~kd;
     1170            classes[id].depth -= 1;
     1171            nodes[kd].parent = ~id;
     1172            deleteNode(jd);
     1173            jd = kd;
     1174          } else {
     1175            int pd = nodes[jd].parent;
     1176            if (nodes[nodes[jd].next].size < cmax) {
     1177              pushLeft(nodes[jd].next, nodes[jd].left);
     1178              if (less(nodes[jd].left, nodes[jd].next)) {
     1179                nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
     1180                nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
     1181              }
     1182              popLeft(pd);
     1183              deleteNode(jd);
     1184              jd = pd;
     1185            } else {
     1186              int ld = nodes[nodes[jd].next].left;
     1187              popLeft(nodes[jd].next);
     1188              pushRight(jd, ld);
     1189              if (less(ld, nodes[jd].left)) {
     1190                nodes[jd].item = nodes[ld].item;
     1191                nodes[jd].prio = nodes[jd].prio;
     1192              }
     1193              if (nodes[nodes[jd].next].item == nodes[ld].item) {
     1194                setPrio(nodes[jd].next);
     1195              }
     1196              jd = nodes[jd].left;
     1197            }
     1198          }
     1199        } else {
     1200          jd = nodes[jd].left;
     1201        }
     1202      }
     1203    }   
     1204
     1205    void repairRight(int id) {
     1206      int jd = ~(classes[id].parent);
     1207      while (nodes[jd].right != -1) {
     1208        int kd = nodes[jd].right;
     1209        if (nodes[jd].size == 1) {
     1210          if (nodes[jd].parent < 0) {
     1211            classes[id].parent = ~kd;
     1212            classes[id].depth -= 1;
     1213            nodes[kd].parent = ~id;
     1214            deleteNode(jd);
     1215            jd = kd;
     1216          } else {
     1217            int pd = nodes[jd].parent;
     1218            if (nodes[nodes[jd].prev].size < cmax) {
     1219              pushRight(nodes[jd].prev, nodes[jd].right);
     1220              if (less(nodes[jd].right, nodes[jd].prev)) {
     1221                nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
     1222                nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
     1223              }
     1224              popRight(pd);
     1225              deleteNode(jd);
     1226              jd = pd;
     1227            } else {
     1228              int ld = nodes[nodes[jd].prev].right;
     1229              popRight(nodes[jd].prev);
     1230              pushLeft(jd, ld);
     1231              if (less(ld, nodes[jd].right)) {
     1232                nodes[jd].item = nodes[ld].item;
     1233                nodes[jd].prio = nodes[jd].prio;
     1234              }
     1235              if (nodes[nodes[jd].prev].item == nodes[ld].item) {
     1236                setPrio(nodes[jd].prev);
     1237              }
     1238              jd = nodes[jd].right;
     1239            }
     1240          }
     1241        } else {
     1242          jd = nodes[jd].right;
     1243        }
     1244      }
     1245    }
     1246
     1247
     1248    bool less(int id, int jd) const {
     1249      return comp(nodes[id].prio, nodes[jd].prio);
     1250    }
     1251
     1252    bool equal(int id, int jd) const {
     1253      return !less(id, jd) && !less(jd, id);
     1254    }
     1255
     1256
     1257  public:
     1258
     1259    /// \brief Returns true when the given class is alive.
     1260    ///
     1261    /// Returns true when the given class is alive, ie. the class is
     1262    /// not nested into other class.
     1263    bool alive(int cls) const {
     1264      return classes[cls].parent < 0;
     1265    }
     1266
     1267    /// \brief Returns true when the given class is trivial.
     1268    ///
     1269    /// Returns true when the given class is trivial, ie. the class
     1270    /// contains just one item directly.
     1271    bool trivial(int cls) const {
     1272      return classes[cls].left == -1;
     1273    }
     1274
     1275    /// \brief Constructs the union-find.
     1276    ///
     1277    /// Constructs the union-find. 
     1278    /// \brief _index The index map of the union-find. The data
     1279    /// structure uses internally for store references.
     1280    HeapUnionFind(ItemIntMap& _index)
     1281      : index(_index), first_class(-1),
     1282        first_free_class(-1), first_free_node(-1) {}
     1283
     1284    /// \brief Insert a new node into a new component.
     1285    ///
     1286    /// Insert a new node into a new component.
     1287    /// \param item The item of the new node.
     1288    /// \param prio The priority of the new node.
     1289    /// \return The class id of the one-item-heap.
     1290    int insert(const Item& item, const Value& prio) {
     1291      int id = newNode();
     1292      nodes[id].item = item;
     1293      nodes[id].prio = prio;
     1294      nodes[id].size = 0;
     1295
     1296      nodes[id].prev = -1;
     1297      nodes[id].next = -1;
     1298
     1299      nodes[id].left = -1;
     1300      nodes[id].right = -1;
     1301
     1302      nodes[id].item = item;
     1303      index[item] = id;
     1304     
     1305      int class_id = newClass();
     1306      classes[class_id].parent = ~id;
     1307      classes[class_id].depth = 0;
     1308
     1309      classes[class_id].left = -1;
     1310      classes[class_id].right = -1;
     1311     
     1312      if (first_class != -1) {
     1313        classes[first_class].prev = class_id;
     1314      }
     1315      classes[class_id].next = first_class;
     1316      classes[class_id].prev = -1;
     1317      first_class = class_id;
     1318
     1319      nodes[id].parent = ~class_id;
     1320     
     1321      return class_id;
     1322    }
     1323
     1324    /// \brief The class of the item.
     1325    ///
     1326    /// \return The alive class id of the item, which is not nested into
     1327    /// other classes.
     1328    ///
     1329    /// The time complexity is O(log(n)).
     1330    int find(const Item& item) const {
     1331      return findClass(index[item]);
     1332    }
     1333   
     1334    /// \brief Joins the classes.
     1335    ///
     1336    /// The current function joins the given classes. The parameter is
     1337    /// an STL range which should be contains valid class ids. The
     1338    /// time complexity is O(log(n)*k) where n is the overall number
     1339    /// of the joined nodes and k is the number of classes.
     1340    /// \return The class of the joined classes.
     1341    /// \pre The range should contain at least two class ids.
     1342    template <typename Iterator>
     1343    int join(Iterator begin, Iterator end) {
     1344      std::vector<int> cs;
     1345      for (Iterator it = begin; it != end; ++it) {
     1346        cs.push_back(*it);
     1347      }
     1348
     1349      int class_id = newClass();
     1350      { // creation union-find
     1351
     1352        if (first_class != -1) {
     1353          classes[first_class].prev = class_id;
     1354        }
     1355        classes[class_id].next = first_class;
     1356        classes[class_id].prev = -1;
     1357        first_class = class_id;
     1358
     1359        classes[class_id].depth = classes[cs[0]].depth;
     1360        classes[class_id].parent = classes[cs[0]].parent;
     1361        nodes[~(classes[class_id].parent)].parent = ~class_id;
     1362
     1363        int l = cs[0];
     1364
     1365        classes[class_id].left = l;
     1366        classes[class_id].right = l;
     1367
     1368        if (classes[l].next != -1) {
     1369          classes[classes[l].next].prev = classes[l].prev;
     1370        }
     1371        classes[classes[l].prev].next = classes[l].next;
     1372       
     1373        classes[l].prev = -1;
     1374        classes[l].next = -1;
     1375
     1376        classes[l].depth = leftNode(l);
     1377        classes[l].parent = class_id;
     1378       
     1379      }
     1380
     1381      { // merging of heap
     1382        int l = class_id;
     1383        for (int ci = 1; ci < int(cs.size()); ++ci) {
     1384          int r = cs[ci];
     1385          int rln = leftNode(r);
     1386          if (classes[l].depth > classes[r].depth) {
     1387            int id = ~(classes[l].parent);
     1388            for (int i = classes[r].depth + 1; i < classes[l].depth; ++i) {
     1389              id = nodes[id].right;
     1390            }
     1391            while (id >= 0 && nodes[id].size == cmax) {
     1392              int new_id = newNode();
     1393              int right_id = nodes[id].right;
     1394
     1395              popRight(id);
     1396              if (nodes[id].item == nodes[right_id].item) {
     1397                setPrio(id);
     1398              }
     1399              push(new_id, right_id);
     1400              pushRight(new_id, ~(classes[r].parent));
     1401              setPrio(new_id);
     1402
     1403              id = nodes[id].parent;
     1404              classes[r].parent = ~new_id;
     1405            }
     1406            if (id < 0) {
     1407              int new_parent = newNode();
     1408              nodes[new_parent].next = -1;
     1409              nodes[new_parent].prev = -1;
     1410              nodes[new_parent].parent = ~l;
     1411
     1412              push(new_parent, ~(classes[l].parent));
     1413              pushRight(new_parent, ~(classes[r].parent));
     1414              setPrio(new_parent);
     1415
     1416              classes[l].parent = ~new_parent;
     1417              classes[l].depth += 1;
     1418            } else {
     1419              pushRight(id, ~(classes[r].parent));
     1420              while (id >= 0 && less(~(classes[r].parent), id)) {
     1421                nodes[id].prio = nodes[~(classes[r].parent)].prio;
     1422                nodes[id].item = nodes[~(classes[r].parent)].item;
     1423                id = nodes[id].parent;
     1424              }
     1425            }
     1426          } else if (classes[r].depth > classes[l].depth) {
     1427            int id = ~(classes[r].parent);
     1428            for (int i = classes[l].depth + 1; i < classes[r].depth; ++i) {
     1429              id = nodes[id].left;
     1430            }
     1431            while (id >= 0 && nodes[id].size == cmax) {
     1432              int new_id = newNode();
     1433              int left_id = nodes[id].left;
     1434
     1435              popLeft(id);
     1436              if (nodes[id].prio == nodes[left_id].prio) {
     1437                setPrio(id);
     1438              }
     1439              push(new_id, left_id);
     1440              pushLeft(new_id, ~(classes[l].parent));
     1441              setPrio(new_id);
     1442
     1443              id = nodes[id].parent;
     1444              classes[l].parent = ~new_id;
     1445
     1446            }
     1447            if (id < 0) {
     1448              int new_parent = newNode();
     1449              nodes[new_parent].next = -1;
     1450              nodes[new_parent].prev = -1;
     1451              nodes[new_parent].parent = ~l;
     1452
     1453              push(new_parent, ~(classes[r].parent));
     1454              pushLeft(new_parent, ~(classes[l].parent));
     1455              setPrio(new_parent);
     1456             
     1457              classes[r].parent = ~new_parent;
     1458              classes[r].depth += 1;
     1459            } else {
     1460              pushLeft(id, ~(classes[l].parent));
     1461              while (id >= 0 && less(~(classes[l].parent), id)) {
     1462                nodes[id].prio = nodes[~(classes[l].parent)].prio;
     1463                nodes[id].item = nodes[~(classes[l].parent)].item;
     1464                id = nodes[id].parent;
     1465              }
     1466            }
     1467            nodes[~(classes[r].parent)].parent = ~l;
     1468            classes[l].parent = classes[r].parent;
     1469            classes[l].depth = classes[r].depth;
     1470          } else {
     1471            if (classes[l].depth != 0 &&
     1472                nodes[~(classes[l].parent)].size +
     1473                nodes[~(classes[r].parent)].size <= cmax) {
     1474              splice(~(classes[l].parent), ~(classes[r].parent));
     1475              deleteNode(~(classes[r].parent));
     1476              if (less(~(classes[r].parent), ~(classes[l].parent))) {
     1477                nodes[~(classes[l].parent)].prio =
     1478                  nodes[~(classes[r].parent)].prio;
     1479                nodes[~(classes[l].parent)].item =
     1480                  nodes[~(classes[r].parent)].item;
     1481              }
     1482            } else {
     1483              int new_parent = newNode();
     1484              nodes[new_parent].next = nodes[new_parent].prev = -1;
     1485              push(new_parent, ~(classes[l].parent));
     1486              pushRight(new_parent, ~(classes[r].parent));
     1487              setPrio(new_parent);
     1488           
     1489              classes[l].parent = ~new_parent;
     1490              classes[l].depth += 1;
     1491              nodes[new_parent].parent = ~l;
     1492            }
     1493          }
     1494          if (classes[r].next != -1) {
     1495            classes[classes[r].next].prev = classes[r].prev;
     1496          }
     1497          classes[classes[r].prev].next = classes[r].next;
     1498
     1499          classes[r].prev = classes[l].right;
     1500          classes[classes[l].right].next = r;
     1501          classes[l].right = r;
     1502          classes[r].parent = l;
     1503
     1504          classes[r].next = -1;
     1505          classes[r].depth = rln;
     1506        }
     1507      }
     1508      return class_id;
     1509    }
     1510
     1511    /// \brief Split the class to subclasses.
     1512    ///
     1513    /// The current function splits the given class. The join, which
     1514    /// made the current class, stored a reference to the
     1515    /// subclasses. The \c splitClass() member restores the classes
     1516    /// and creates the heaps. The parameter is an STL output iterator
     1517    /// which will be filled with the subclass ids. The time
     1518    /// complexity is O(log(n)*k) where n is the overall number of
     1519    /// nodes in the splitted classes and k is the number of the
     1520    /// classes.
     1521    template <typename Iterator>
     1522    void split(int cls, Iterator out) {
     1523      std::vector<int> cs;
     1524      { // splitting union-find
     1525        int id = cls;
     1526        int l = classes[id].left;
     1527
     1528        classes[l].parent = classes[id].parent;
     1529        classes[l].depth = classes[id].depth;
     1530
     1531        nodes[~(classes[l].parent)].parent = ~l;
     1532
     1533        *out++ = l;
     1534
     1535        while (l != -1) {
     1536          cs.push_back(l);
     1537          l = classes[l].next;
     1538        }
     1539
     1540        classes[classes[id].right].next = first_class;
     1541        classes[first_class].prev = classes[id].right;
     1542        first_class = classes[id].left;
     1543       
     1544        if (classes[id].next != -1) {
     1545          classes[classes[id].next].prev = classes[id].prev;
     1546        }
     1547        classes[classes[id].prev].next = classes[id].next;
     1548       
     1549        deleteClass(id);
     1550      }
     1551
     1552      {
     1553        for (int i = 1; i < int(cs.size()); ++i) {
     1554          int l = classes[cs[i]].depth;
     1555          while (nodes[nodes[l].parent].left == l) {
     1556            l = nodes[l].parent;
     1557          }
     1558          int r = l;   
     1559          while (nodes[l].parent >= 0) {
     1560            l = nodes[l].parent;
     1561            int new_node = newNode();
     1562
     1563            nodes[new_node].prev = -1;
     1564            nodes[new_node].next = -1;
     1565
     1566            split(r, new_node);
     1567            pushAfter(l, new_node);
     1568            setPrio(l);
     1569            setPrio(new_node);
     1570            r = new_node;
     1571          }
     1572          classes[cs[i]].parent = ~r;
     1573          classes[cs[i]].depth = classes[~(nodes[l].parent)].depth;
     1574          nodes[r].parent = ~cs[i];
     1575
     1576          nodes[l].next = -1;
     1577          nodes[r].prev = -1;
     1578
     1579          repairRight(~(nodes[l].parent));
     1580          repairLeft(cs[i]);
     1581         
     1582          *out++ = cs[i];
     1583        }
     1584      }
     1585    }
     1586
     1587    /// \brief Gives back the priority of the current item.
     1588    ///
     1589    /// \return Gives back the priority of the current item.
     1590    const Value& operator[](const Item& item) const {
     1591      return nodes[index[item]].prio;
     1592    }
     1593
     1594    /// \brief Sets the priority of the current item.
     1595    ///
     1596    /// Sets the priority of the current item.
     1597    void set(const Item& item, const Value& prio) {
     1598      if (comp(prio, nodes[index[item]].prio)) {
     1599        decrease(item, prio);
     1600      } else if (!comp(prio, nodes[index[item]].prio)) {
     1601        increase(item, prio);
     1602      }
     1603    }
     1604     
     1605    /// \brief Increase the priority of the current item.
     1606    ///
     1607    /// Increase the priority of the current item.
     1608    void increase(const Item& item, const Value& prio) {
     1609      int id = index[item];
     1610      int kd = nodes[id].parent;
     1611      nodes[id].prio = prio;
     1612      while (kd >= 0 && nodes[kd].item == item) {
     1613        setPrio(kd);
     1614        kd = nodes[kd].parent;
     1615      }
     1616    }
     1617
     1618    /// \brief Increase the priority of the current item.
     1619    ///
     1620    /// Increase the priority of the current item.
     1621    void decrease(const Item& item, const Value& prio) {
     1622      int id = index[item];
     1623      int kd = nodes[id].parent;
     1624      nodes[id].prio = prio;
     1625      while (kd >= 0 && less(id, kd)) {
     1626        nodes[kd].prio = prio;
     1627        nodes[kd].item = item;
     1628        kd = nodes[kd].parent;
     1629      }
     1630    }
     1631   
     1632    /// \brief Gives back the minimum priority of the class.
     1633    ///
     1634    /// \return Gives back the minimum priority of the class.
     1635    const Value& classPrio(int cls) const {
     1636      return nodes[~(classes[cls].parent)].prio;
     1637    }
     1638
     1639    /// \brief Gives back the minimum priority item of the class.
     1640    ///
     1641    /// \return Gives back the minimum priority item of the class.
     1642    const Item& classTop(int cls) const {
     1643      return nodes[~(classes[cls].parent)].item;
     1644    }
     1645
     1646    /// \brief Gives back a representant item of the class.
     1647    ///
     1648    /// The representant is indpendent from the priorities of the
     1649    /// items.
     1650    /// \return Gives back a representant item of the class.
     1651    const Item& classRep(int id) const {
     1652      int parent = classes[id].parent;
     1653      return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
     1654    }
     1655
     1656    /// \brief Lemon style iterator for the items of a class.
     1657    ///
     1658    /// ClassIt is a lemon style iterator for the components. It iterates
     1659    /// on the items of a class. By example if you want to iterate on
     1660    /// each items of each classes then you may write the next code.
     1661    ///\code
     1662    /// for (ClassIt cit(huf); cit != INVALID; ++cit) {
     1663    ///   std::cout << "Class: ";
     1664    ///   for (ItemIt iit(huf, cit); iit != INVALID; ++iit) {
     1665    ///     std::cout << toString(iit) << ' ' << std::endl;
     1666    ///   }
     1667    ///   std::cout << std::endl;
     1668    /// }
     1669    ///\endcode
     1670    class ItemIt {
     1671    private:
     1672
     1673      const HeapUnionFind* _huf;
     1674      int _id, _lid;
     1675     
     1676    public:
     1677
     1678      /// \brief Default constructor
     1679      ///
     1680      /// Default constructor
     1681      ItemIt() {}
     1682
     1683      ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
     1684        int id = cls;
     1685        int parent = _huf->classes[id].parent;
     1686        if (parent >= 0) {
     1687          _id = _huf->classes[id].depth;
     1688          if (_huf->classes[id].next != -1) {
     1689            _lid = _huf->classes[_huf->classes[id].next].depth;
     1690          } else {
     1691            _lid = -1;
     1692          }
     1693        } else {
     1694          _id = _huf->leftNode(id);
     1695          _lid = -1;
     1696        }
     1697      }
     1698     
     1699      /// \brief Increment operator
     1700      ///
     1701      /// It steps to the next item in the class.
     1702      ItemIt& operator++() {
     1703        _id = _huf->nextNode(_id);
     1704        return *this;
     1705      }
     1706
     1707      /// \brief Conversion operator
     1708      ///
     1709      /// It converts the iterator to the current item.
     1710      operator const Item&() const {
     1711        return _huf->nodes[_id].item;
     1712      }
     1713     
     1714      /// \brief Equality operator
     1715      ///
     1716      /// Equality operator
     1717      bool operator==(const ItemIt& i) {
     1718        return i._id == _id;
     1719      }
     1720
     1721      /// \brief Inequality operator
     1722      ///
     1723      /// Inequality operator
     1724      bool operator!=(const ItemIt& i) {
     1725        return i._id != _id;
     1726      }
     1727
     1728      /// \brief Equality operator
     1729      ///
     1730      /// Equality operator
     1731      bool operator==(Invalid) {
     1732        return _id == _lid;
     1733      }
     1734
     1735      /// \brief Inequality operator
     1736      ///
     1737      /// Inequality operator
     1738      bool operator!=(Invalid) {
     1739        return _id != _lid;
     1740      }
     1741     
     1742    };
     1743
     1744    /// \brief Class iterator
     1745    ///
     1746    /// The iterator stores
     1747    class ClassIt {
     1748    private:
     1749
     1750      const HeapUnionFind* _huf;
     1751      int _id;
     1752
     1753    public:
     1754
     1755      ClassIt(const HeapUnionFind& huf)
     1756        : _huf(&huf), _id(huf.first_class) {}
     1757
     1758      ClassIt(const HeapUnionFind& huf, int cls)
     1759        : _huf(&huf), _id(huf.classes[cls].left) {}
     1760
     1761      ClassIt(Invalid) : _huf(0), _id(-1) {}
     1762     
     1763      const ClassIt& operator++() {
     1764        _id = _huf->classes[_id].next;
     1765        return *this;
     1766      }
     1767
     1768      /// \brief Equality operator
     1769      ///
     1770      /// Equality operator
     1771      bool operator==(const ClassIt& i) {
     1772        return i._id == _id;
     1773      }
     1774
     1775      /// \brief Inequality operator
     1776      ///
     1777      /// Inequality operator
     1778      bool operator!=(const ClassIt& i) {
     1779        return i._id != _id;
     1780      }     
     1781     
     1782      operator int() const {
     1783        return _id;
     1784      }
     1785           
     1786    };
     1787
     1788  };
     1789
    9271790  //! @}
    9281791
Note: See TracChangeset for help on using the changeset viewer.