Changeset - r457:561be42c4b99
« 449:b0f74c
460:81d40f »
459:6c1ac1 »
458:bb022b »
gravatar
deba@inf.elte.hu
deba@inf.elte.hu
Bug fix in heap unionfind (ticket #197) The minimum item in the unionfind tree might become inconsistent when the split operation merges two subtrees which have equal keys. The current changeset fix the problem. It also fix a wrong index.
0 1 0
default
1 file changed with 28 insertions and 12 deletions:
lemon/unionfind.h
28
12
↑ Collapse diff ↑
lemon/unionfind.h
Show white space 12 line context
... ... 
@@ -1174,26 +1174,27 @@
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 
                nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
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[jd].prio;
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 
            }
... ... 
@@ -1216,26 +1217,27 @@
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 
                nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
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[jd].prio;
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 
            }
... ... 
@@ -1397,13 +1399,20 @@
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 
              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
	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();


			




	...
	...
	
		
@@ -1437,13 +1446,20 @@


			




	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
	
	
		
              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
	1461
	
		
              id = nodes[id].parent;


			




	1446
	1462
	
		
              classes[l].parent = ~new_id;


			




	1447
	1463
	
		

			




	1448
	1464
	
		
            }


			




	1449
	1465
	
		
            if (id < 0) {


			




        

    






    
    



    


    

     
    
0 comments (0 inline)