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
... ... 
@@ -1179,5 +1179,5 @@
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 
              }
... ... 
@@ -1190,5 +1190,6 @@
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 
              }
... ... 
@@ -1221,5 +1222,5 @@
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 
              }
... ... 
@@ -1232,5 +1233,6 @@
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 
              }
... ... 
@@ -1402,3 +1404,10 @@
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
	
		

			




	...
	...
	
		
@@ -1442,3 +1451,10 @@


			




	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
	
		

			




        

    






    
    



    


    

     
    
0 comments (0 inline)