Changeset 2548:a3ba22ebccc6 in lemon-0.x for lemon/unionfind.h
- Timestamp:
- 12/28/07 12:00:51 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3425
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/unionfind.h
r2542 r2548 925 925 }; 926 926 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 927 1790 //! @} 928 1791
Note: See TracChangeset
for help on using the changeset viewer.