Changeset - r460:81d40f1c850c
« 457:561be4
497:8b5660 »
462:1cc281 »
461:1229dc »
gravatar
deba@inf.elte.hu
deba@inf.elte.hu
Bug fix in heap unionfind (ticket #197) The previous bugfix set the minimum value in internal nodes wrongly. It corrects the problem.
0 1 0
default
1 file changed with 4 insertions and 7 deletions:
lemon/unionfind.h
4
7
↑ Collapse diff ↑
lemon/unionfind.h
Ignore white space 8 line context
... ... 
@@ -1176,9 +1176,10 @@
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].item == nodes[pd].item) {
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);
... ... 
@@ -1219,9 +1220,10 @@
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].item == nodes[pd].item) {
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);
... ... 
@@ -1252,13 +1254,8 @@
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
	
		
    ///


			




        

    






    
    



    


    

     
    
0 comments (0 inline)