r460:81d40f1c850c
Sun, 21 Dec 2008 20:45:25
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -1164,33 +1164,34 @@ |
| 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) {
|
| ... | ... |
@@ -1207,70 +1208,66 @@ |
| 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; |
0 comments (0 inline)