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 6 line context
... ... 
@@ -1177,9 +1177,9 @@
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);
... ... 
@@ -1188,9 +1188,10 @@
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);
... ... 
@@ -1219,9 +1220,9 @@
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);
... ... 
@@ -1230,9 +1231,10 @@
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);
... ... 
@@ -1400,7 +1402,14 @@
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;


			




	...
	...
	
		
@@ -1440,7 +1449,14 @@


			




	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;


			




        

    






    
    



    


    

     
    
0 comments (0 inline)