r462:1cc2818c03c0
Sun, 21 Dec 2008 20:46:35
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -1156,129 +1156,126 @@ |
| 1156 | 1156 |
} |
| 1157 | 1157 |
|
| 1158 | 1158 |
void popLeft(int id) {
|
| 1159 | 1159 |
nodes[id].size -= 1; |
| 1160 | 1160 |
int jd = nodes[id].left; |
| 1161 | 1161 |
nodes[nodes[jd].next].prev = -1; |
| 1162 | 1162 |
nodes[id].left = nodes[jd].next; |
| 1163 | 1163 |
} |
| 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 (nodes[jd]. |
|
| 1180 |
if (less(jd, nodes[jd].next) || |
|
| 1181 |
nodes[jd].item == nodes[pd].item) {
|
|
| 1181 | 1182 |
nodes[nodes[jd].next].prio = nodes[jd].prio; |
| 1182 | 1183 |
nodes[nodes[jd].next].item = nodes[jd].item; |
| 1183 | 1184 |
} |
| 1184 | 1185 |
popLeft(pd); |
| 1185 | 1186 |
deleteNode(jd); |
| 1186 | 1187 |
jd = pd; |
| 1187 | 1188 |
} else {
|
| 1188 | 1189 |
int ld = nodes[nodes[jd].next].left; |
| 1189 | 1190 |
popLeft(nodes[jd].next); |
| 1190 | 1191 |
pushRight(jd, ld); |
| 1191 | 1192 |
if (less(ld, nodes[jd].left) || |
| 1192 | 1193 |
nodes[ld].item == nodes[pd].item) {
|
| 1193 | 1194 |
nodes[jd].item = nodes[ld].item; |
| 1194 | 1195 |
nodes[jd].prio = nodes[ld].prio; |
| 1195 | 1196 |
} |
| 1196 | 1197 |
if (nodes[nodes[jd].next].item == nodes[ld].item) {
|
| 1197 | 1198 |
setPrio(nodes[jd].next); |
| 1198 | 1199 |
} |
| 1199 | 1200 |
jd = nodes[jd].left; |
| 1200 | 1201 |
} |
| 1201 | 1202 |
} |
| 1202 | 1203 |
} else {
|
| 1203 | 1204 |
jd = nodes[jd].left; |
| 1204 | 1205 |
} |
| 1205 | 1206 |
} |
| 1206 | 1207 |
} |
| 1207 | 1208 |
|
| 1208 | 1209 |
void repairRight(int id) {
|
| 1209 | 1210 |
int jd = ~(classes[id].parent); |
| 1210 | 1211 |
while (nodes[jd].right != -1) {
|
| 1211 | 1212 |
int kd = nodes[jd].right; |
| 1212 | 1213 |
if (nodes[jd].size == 1) {
|
| 1213 | 1214 |
if (nodes[jd].parent < 0) {
|
| 1214 | 1215 |
classes[id].parent = ~kd; |
| 1215 | 1216 |
classes[id].depth -= 1; |
| 1216 | 1217 |
nodes[kd].parent = ~id; |
| 1217 | 1218 |
deleteNode(jd); |
| 1218 | 1219 |
jd = kd; |
| 1219 | 1220 |
} else {
|
| 1220 | 1221 |
int pd = nodes[jd].parent; |
| 1221 | 1222 |
if (nodes[nodes[jd].prev].size < cmax) {
|
| 1222 | 1223 |
pushRight(nodes[jd].prev, nodes[jd].right); |
| 1223 |
if (nodes[jd]. |
|
| 1224 |
if (less(jd, nodes[jd].prev) || |
|
| 1225 |
nodes[jd].item == nodes[pd].item) {
|
|
| 1224 | 1226 |
nodes[nodes[jd].prev].prio = nodes[jd].prio; |
| 1225 | 1227 |
nodes[nodes[jd].prev].item = nodes[jd].item; |
| 1226 | 1228 |
} |
| 1227 | 1229 |
popRight(pd); |
| 1228 | 1230 |
deleteNode(jd); |
| 1229 | 1231 |
jd = pd; |
| 1230 | 1232 |
} else {
|
| 1231 | 1233 |
int ld = nodes[nodes[jd].prev].right; |
| 1232 | 1234 |
popRight(nodes[jd].prev); |
| 1233 | 1235 |
pushLeft(jd, ld); |
| 1234 | 1236 |
if (less(ld, nodes[jd].right) || |
| 1235 | 1237 |
nodes[ld].item == nodes[pd].item) {
|
| 1236 | 1238 |
nodes[jd].item = nodes[ld].item; |
| 1237 | 1239 |
nodes[jd].prio = nodes[ld].prio; |
| 1238 | 1240 |
} |
| 1239 | 1241 |
if (nodes[nodes[jd].prev].item == nodes[ld].item) {
|
| 1240 | 1242 |
setPrio(nodes[jd].prev); |
| 1241 | 1243 |
} |
| 1242 | 1244 |
jd = nodes[jd].right; |
| 1243 | 1245 |
} |
| 1244 | 1246 |
} |
| 1245 | 1247 |
} else {
|
| 1246 | 1248 |
jd = nodes[jd].right; |
| 1247 | 1249 |
} |
| 1248 | 1250 |
} |
| 1249 | 1251 |
} |
| 1250 | 1252 |
|
| 1251 | 1253 |
|
| 1252 | 1254 |
bool less(int id, int jd) const {
|
| 1253 | 1255 |
return comp(nodes[id].prio, nodes[jd].prio); |
| 1254 | 1256 |
} |
| 1255 | 1257 |
|
| 1256 |
bool equal(int id, int jd) const {
|
|
| 1257 |
return !less(id, jd) && !less(jd, id); |
|
| 1258 |
} |
|
| 1259 |
|
|
| 1260 |
|
|
| 1261 | 1258 |
public: |
| 1262 | 1259 |
|
| 1263 | 1260 |
/// \brief Returns true when the given class is alive. |
| 1264 | 1261 |
/// |
| 1265 | 1262 |
/// Returns true when the given class is alive, ie. the class is |
| 1266 | 1263 |
/// not nested into other class. |
| 1267 | 1264 |
bool alive(int cls) const {
|
| 1268 | 1265 |
return classes[cls].parent < 0; |
| 1269 | 1266 |
} |
| 1270 | 1267 |
|
| 1271 | 1268 |
/// \brief Returns true when the given class is trivial. |
| 1272 | 1269 |
/// |
| 1273 | 1270 |
/// Returns true when the given class is trivial, ie. the class |
| 1274 | 1271 |
/// contains just one item directly. |
| 1275 | 1272 |
bool trivial(int cls) const {
|
| 1276 | 1273 |
return classes[cls].left == -1; |
| 1277 | 1274 |
} |
| 1278 | 1275 |
|
| 1279 | 1276 |
/// \brief Constructs the union-find. |
| 1280 | 1277 |
/// |
| 1281 | 1278 |
/// Constructs the union-find. |
| 1282 | 1279 |
/// \brief _index The index map of the union-find. The data |
| 1283 | 1280 |
/// structure uses internally for store references. |
| 1284 | 1281 |
HeapUnionFind(ItemIntMap& _index) |
0 comments (0 inline)