1175 jd = kd; |
1175 jd = kd; |
1176 } else { |
1176 } else { |
1177 int pd = nodes[jd].parent; |
1177 int pd = nodes[jd].parent; |
1178 if (nodes[nodes[jd].next].size < cmax) { |
1178 if (nodes[nodes[jd].next].size < cmax) { |
1179 pushLeft(nodes[jd].next, nodes[jd].left); |
1179 pushLeft(nodes[jd].next, nodes[jd].left); |
1180 if (less(nodes[jd].left, nodes[jd].next)) { |
1180 if (nodes[jd].item == nodes[pd].item) { |
1181 nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio; |
1181 nodes[nodes[jd].next].prio = nodes[jd].prio; |
1182 nodes[nodes[jd].next].item = nodes[nodes[jd].left].item; |
1182 nodes[nodes[jd].next].item = nodes[jd].item; |
1183 } |
1183 } |
1184 popLeft(pd); |
1184 popLeft(pd); |
1185 deleteNode(jd); |
1185 deleteNode(jd); |
1186 jd = pd; |
1186 jd = pd; |
1187 } else { |
1187 } else { |
1188 int ld = nodes[nodes[jd].next].left; |
1188 int ld = nodes[nodes[jd].next].left; |
1189 popLeft(nodes[jd].next); |
1189 popLeft(nodes[jd].next); |
1190 pushRight(jd, ld); |
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 nodes[jd].item = nodes[ld].item; |
1193 nodes[jd].item = nodes[ld].item; |
1193 nodes[jd].prio = nodes[jd].prio; |
1194 nodes[jd].prio = nodes[ld].prio; |
1194 } |
1195 } |
1195 if (nodes[nodes[jd].next].item == nodes[ld].item) { |
1196 if (nodes[nodes[jd].next].item == nodes[ld].item) { |
1196 setPrio(nodes[jd].next); |
1197 setPrio(nodes[jd].next); |
1197 } |
1198 } |
1198 jd = nodes[jd].left; |
1199 jd = nodes[jd].left; |
1217 jd = kd; |
1218 jd = kd; |
1218 } else { |
1219 } else { |
1219 int pd = nodes[jd].parent; |
1220 int pd = nodes[jd].parent; |
1220 if (nodes[nodes[jd].prev].size < cmax) { |
1221 if (nodes[nodes[jd].prev].size < cmax) { |
1221 pushRight(nodes[jd].prev, nodes[jd].right); |
1222 pushRight(nodes[jd].prev, nodes[jd].right); |
1222 if (less(nodes[jd].right, nodes[jd].prev)) { |
1223 if (nodes[jd].item == nodes[pd].item) { |
1223 nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio; |
1224 nodes[nodes[jd].prev].prio = nodes[jd].prio; |
1224 nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item; |
1225 nodes[nodes[jd].prev].item = nodes[jd].item; |
1225 } |
1226 } |
1226 popRight(pd); |
1227 popRight(pd); |
1227 deleteNode(jd); |
1228 deleteNode(jd); |
1228 jd = pd; |
1229 jd = pd; |
1229 } else { |
1230 } else { |
1230 int ld = nodes[nodes[jd].prev].right; |
1231 int ld = nodes[nodes[jd].prev].right; |
1231 popRight(nodes[jd].prev); |
1232 popRight(nodes[jd].prev); |
1232 pushLeft(jd, ld); |
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 nodes[jd].item = nodes[ld].item; |
1236 nodes[jd].item = nodes[ld].item; |
1235 nodes[jd].prio = nodes[jd].prio; |
1237 nodes[jd].prio = nodes[ld].prio; |
1236 } |
1238 } |
1237 if (nodes[nodes[jd].prev].item == nodes[ld].item) { |
1239 if (nodes[nodes[jd].prev].item == nodes[ld].item) { |
1238 setPrio(nodes[jd].prev); |
1240 setPrio(nodes[jd].prev); |
1239 } |
1241 } |
1240 jd = nodes[jd].right; |
1242 jd = nodes[jd].right; |
1398 if (nodes[id].item == nodes[right_id].item) { |
1400 if (nodes[id].item == nodes[right_id].item) { |
1399 setPrio(id); |
1401 setPrio(id); |
1400 } |
1402 } |
1401 push(new_id, right_id); |
1403 push(new_id, right_id); |
1402 pushRight(new_id, ~(classes[r].parent)); |
1404 pushRight(new_id, ~(classes[r].parent)); |
1403 setPrio(new_id); |
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 id = nodes[id].parent; |
1414 id = nodes[id].parent; |
1406 classes[r].parent = ~new_id; |
1415 classes[r].parent = ~new_id; |
1407 } |
1416 } |
1408 if (id < 0) { |
1417 if (id < 0) { |
1438 if (nodes[id].prio == nodes[left_id].prio) { |
1447 if (nodes[id].prio == nodes[left_id].prio) { |
1439 setPrio(id); |
1448 setPrio(id); |
1440 } |
1449 } |
1441 push(new_id, left_id); |
1450 push(new_id, left_id); |
1442 pushLeft(new_id, ~(classes[l].parent)); |
1451 pushLeft(new_id, ~(classes[l].parent)); |
1443 setPrio(new_id); |
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 id = nodes[id].parent; |
1461 id = nodes[id].parent; |
1446 classes[l].parent = ~new_id; |
1462 classes[l].parent = ~new_id; |
1447 |
1463 |
1448 } |
1464 } |