922 int idx, fdx; |
922 int idx, fdx; |
923 }; |
923 }; |
924 |
924 |
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 |
929 } //namespace lemon |
1792 } //namespace lemon |
930 |
1793 |
931 #endif //LEMON_UNION_FIND_H |
1794 #endif //LEMON_UNION_FIND_H |