r436:561be42c4b99
Sun, 21 Dec 2008 00:13:02
[Not Reviewed]
0 comments (0 inline)
0
1
0
28
12
| ... | ... |
@@ -1164,88 +1164,90 @@ |
| 1164 | 1164 |
|
| 1165 | 1165 |
void repairLeft(int id) {
|
| 1166 | 1166 |
int jd = ~(classes[id].parent); |
| 1167 | 1167 |
while (nodes[jd].left != -1) {
|
| 1168 | 1168 |
int kd = nodes[jd].left; |
| 1169 | 1169 |
if (nodes[jd].size == 1) {
|
| 1170 | 1170 |
if (nodes[jd].parent < 0) {
|
| 1171 | 1171 |
classes[id].parent = ~kd; |
| 1172 | 1172 |
classes[id].depth -= 1; |
| 1173 | 1173 |
nodes[kd].parent = ~id; |
| 1174 | 1174 |
deleteNode(jd); |
| 1175 | 1175 |
jd = kd; |
| 1176 | 1176 |
} else {
|
| 1177 | 1177 |
int pd = nodes[jd].parent; |
| 1178 | 1178 |
if (nodes[nodes[jd].next].size < cmax) {
|
| 1179 | 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 |
|
|
| 1180 |
if (nodes[jd].item == nodes[pd].item) {
|
|
| 1181 |
nodes[nodes[jd].next].prio = nodes[jd].prio; |
|
| 1182 |
nodes[nodes[jd].next].item = nodes[jd].item; |
|
| 1183 | 1183 |
} |
| 1184 | 1184 |
popLeft(pd); |
| 1185 | 1185 |
deleteNode(jd); |
| 1186 | 1186 |
jd = pd; |
| 1187 | 1187 |
} else {
|
| 1188 | 1188 |
int ld = nodes[nodes[jd].next].left; |
| 1189 | 1189 |
popLeft(nodes[jd].next); |
| 1190 | 1190 |
pushRight(jd, ld); |
| 1191 |
if (less(ld, nodes[jd].left) |
|
| 1191 |
if (less(ld, nodes[jd].left) || |
|
| 1192 |
nodes[ld].item == nodes[pd].item) {
|
|
| 1192 | 1193 |
nodes[jd].item = nodes[ld].item; |
| 1193 |
nodes[jd].prio = nodes[ |
|
| 1194 |
nodes[jd].prio = nodes[ld].prio; |
|
| 1194 | 1195 |
} |
| 1195 | 1196 |
if (nodes[nodes[jd].next].item == nodes[ld].item) {
|
| 1196 | 1197 |
setPrio(nodes[jd].next); |
| 1197 | 1198 |
} |
| 1198 | 1199 |
jd = nodes[jd].left; |
| 1199 | 1200 |
} |
| 1200 | 1201 |
} |
| 1201 | 1202 |
} else {
|
| 1202 | 1203 |
jd = nodes[jd].left; |
| 1203 | 1204 |
} |
| 1204 | 1205 |
} |
| 1205 | 1206 |
} |
| 1206 | 1207 |
|
| 1207 | 1208 |
void repairRight(int id) {
|
| 1208 | 1209 |
int jd = ~(classes[id].parent); |
| 1209 | 1210 |
while (nodes[jd].right != -1) {
|
| 1210 | 1211 |
int kd = nodes[jd].right; |
| 1211 | 1212 |
if (nodes[jd].size == 1) {
|
| 1212 | 1213 |
if (nodes[jd].parent < 0) {
|
| 1213 | 1214 |
classes[id].parent = ~kd; |
| 1214 | 1215 |
classes[id].depth -= 1; |
| 1215 | 1216 |
nodes[kd].parent = ~id; |
| 1216 | 1217 |
deleteNode(jd); |
| 1217 | 1218 |
jd = kd; |
| 1218 | 1219 |
} else {
|
| 1219 | 1220 |
int pd = nodes[jd].parent; |
| 1220 | 1221 |
if (nodes[nodes[jd].prev].size < cmax) {
|
| 1221 | 1222 |
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 |
|
|
| 1223 |
if (nodes[jd].item == nodes[pd].item) {
|
|
| 1224 |
nodes[nodes[jd].prev].prio = nodes[jd].prio; |
|
| 1225 |
nodes[nodes[jd].prev].item = nodes[jd].item; |
|
| 1225 | 1226 |
} |
| 1226 | 1227 |
popRight(pd); |
| 1227 | 1228 |
deleteNode(jd); |
| 1228 | 1229 |
jd = pd; |
| 1229 | 1230 |
} else {
|
| 1230 | 1231 |
int ld = nodes[nodes[jd].prev].right; |
| 1231 | 1232 |
popRight(nodes[jd].prev); |
| 1232 | 1233 |
pushLeft(jd, ld); |
| 1233 |
if (less(ld, nodes[jd].right) |
|
| 1234 |
if (less(ld, nodes[jd].right) || |
|
| 1235 |
nodes[ld].item == nodes[pd].item) {
|
|
| 1234 | 1236 |
nodes[jd].item = nodes[ld].item; |
| 1235 |
nodes[jd].prio = nodes[ |
|
| 1237 |
nodes[jd].prio = nodes[ld].prio; |
|
| 1236 | 1238 |
} |
| 1237 | 1239 |
if (nodes[nodes[jd].prev].item == nodes[ld].item) {
|
| 1238 | 1240 |
setPrio(nodes[jd].prev); |
| 1239 | 1241 |
} |
| 1240 | 1242 |
jd = nodes[jd].right; |
| 1241 | 1243 |
} |
| 1242 | 1244 |
} |
| 1243 | 1245 |
} else {
|
| 1244 | 1246 |
jd = nodes[jd].right; |
| 1245 | 1247 |
} |
| 1246 | 1248 |
} |
| 1247 | 1249 |
} |
| 1248 | 1250 |
|
| 1249 | 1251 |
|
| 1250 | 1252 |
bool less(int id, int jd) const {
|
| 1251 | 1253 |
return comp(nodes[id].prio, nodes[jd].prio); |
| ... | ... |
@@ -1387,33 +1389,40 @@ |
| 1387 | 1389 |
int rln = leftNode(r); |
| 1388 | 1390 |
if (classes[l].depth > classes[r].depth) {
|
| 1389 | 1391 |
int id = ~(classes[l].parent); |
| 1390 | 1392 |
for (int i = classes[r].depth + 1; i < classes[l].depth; ++i) {
|
| 1391 | 1393 |
id = nodes[id].right; |
| 1392 | 1394 |
} |
| 1393 | 1395 |
while (id >= 0 && nodes[id].size == cmax) {
|
| 1394 | 1396 |
int new_id = newNode(); |
| 1395 | 1397 |
int right_id = nodes[id].right; |
| 1396 | 1398 |
|
| 1397 | 1399 |
popRight(id); |
| 1398 | 1400 |
if (nodes[id].item == nodes[right_id].item) {
|
| 1399 | 1401 |
setPrio(id); |
| 1400 | 1402 |
} |
| 1401 | 1403 |
push(new_id, right_id); |
| 1402 | 1404 |
pushRight(new_id, ~(classes[r].parent)); |
| 1403 |
|
|
| 1405 |
|
|
| 1406 |
if (less(~classes[r].parent, right_id)) {
|
|
| 1407 |
nodes[new_id].item = nodes[~classes[r].parent].item; |
|
| 1408 |
nodes[new_id].prio = nodes[~classes[r].parent].prio; |
|
| 1409 |
} else {
|
|
| 1410 |
nodes[new_id].item = nodes[right_id].item; |
|
| 1411 |
nodes[new_id].prio = nodes[right_id].prio; |
|
| 1412 |
} |
|
| 1404 | 1413 |
|
| 1405 | 1414 |
id = nodes[id].parent; |
| 1406 | 1415 |
classes[r].parent = ~new_id; |
| 1407 | 1416 |
} |
| 1408 | 1417 |
if (id < 0) {
|
| 1409 | 1418 |
int new_parent = newNode(); |
| 1410 | 1419 |
nodes[new_parent].next = -1; |
| 1411 | 1420 |
nodes[new_parent].prev = -1; |
| 1412 | 1421 |
nodes[new_parent].parent = ~l; |
| 1413 | 1422 |
|
| 1414 | 1423 |
push(new_parent, ~(classes[l].parent)); |
| 1415 | 1424 |
pushRight(new_parent, ~(classes[r].parent)); |
| 1416 | 1425 |
setPrio(new_parent); |
| 1417 | 1426 |
|
| 1418 | 1427 |
classes[l].parent = ~new_parent; |
| 1419 | 1428 |
classes[l].depth += 1; |
| ... | ... |
@@ -1427,33 +1436,40 @@ |
| 1427 | 1436 |
} |
| 1428 | 1437 |
} else if (classes[r].depth > classes[l].depth) {
|
| 1429 | 1438 |
int id = ~(classes[r].parent); |
| 1430 | 1439 |
for (int i = classes[l].depth + 1; i < classes[r].depth; ++i) {
|
| 1431 | 1440 |
id = nodes[id].left; |
| 1432 | 1441 |
} |
| 1433 | 1442 |
while (id >= 0 && nodes[id].size == cmax) {
|
| 1434 | 1443 |
int new_id = newNode(); |
| 1435 | 1444 |
int left_id = nodes[id].left; |
| 1436 | 1445 |
|
| 1437 | 1446 |
popLeft(id); |
| 1438 | 1447 |
if (nodes[id].prio == nodes[left_id].prio) {
|
| 1439 | 1448 |
setPrio(id); |
| 1440 | 1449 |
} |
| 1441 | 1450 |
push(new_id, left_id); |
| 1442 | 1451 |
pushLeft(new_id, ~(classes[l].parent)); |
| 1443 |
|
|
| 1452 |
|
|
| 1453 |
if (less(~classes[l].parent, left_id)) {
|
|
| 1454 |
nodes[new_id].item = nodes[~classes[l].parent].item; |
|
| 1455 |
nodes[new_id].prio = nodes[~classes[l].parent].prio; |
|
| 1456 |
} else {
|
|
| 1457 |
nodes[new_id].item = nodes[left_id].item; |
|
| 1458 |
nodes[new_id].prio = nodes[left_id].prio; |
|
| 1459 |
} |
|
| 1444 | 1460 |
|
| 1445 | 1461 |
id = nodes[id].parent; |
| 1446 | 1462 |
classes[l].parent = ~new_id; |
| 1447 | 1463 |
|
| 1448 | 1464 |
} |
| 1449 | 1465 |
if (id < 0) {
|
| 1450 | 1466 |
int new_parent = newNode(); |
| 1451 | 1467 |
nodes[new_parent].next = -1; |
| 1452 | 1468 |
nodes[new_parent].prev = -1; |
| 1453 | 1469 |
nodes[new_parent].parent = ~l; |
| 1454 | 1470 |
|
| 1455 | 1471 |
push(new_parent, ~(classes[r].parent)); |
| 1456 | 1472 |
pushLeft(new_parent, ~(classes[l].parent)); |
| 1457 | 1473 |
setPrio(new_parent); |
| 1458 | 1474 |
|
| 1459 | 1475 |
classes[r].parent = ~new_parent; |
0 comments (0 inline)