src/work/johanna/unionfind.h
changeset 482 dce64ce044d6
parent 462 0ab31578af67
equal deleted inserted replaced
4:9164eefa975a 5:2ff614740f81
   262       m.set(a, ai);
   262       m.set(a, ai);
   263 
   263 
   264     }
   264     }
   265 
   265 
   266     /**
   266     /**
       
   267      * \brief Insert the given element into the component of the others.
       
   268      *
       
   269      * This methods insert the element \e a into the component of the
       
   270      * element \e comp. 
       
   271      */
       
   272 
       
   273     void insert(const T &a, const T &comp) {
       
   274       
       
   275       IIter clit = _find(m[comp]);
       
   276       ItemList &c = *clit->my_class;
       
   277       c.push_back(ItemType(a,0));
       
   278       IIter ai = c.end();
       
   279       --ai;
       
   280       ai->parent = clit;
       
   281       m.set(a, ai);
       
   282       ++clit->size;
       
   283     }
       
   284 
       
   285 
       
   286     /**
   267      * \brief Find the leader of the component of the given element.
   287      * \brief Find the leader of the component of the given element.
   268      *
   288      *
   269      * The method returns the leader of the component of the given element.
   289      * The method returns the leader of the component of the given element.
   270      */
   290      */
   271 
   291 
   381       CIter l = ia->my_class;
   401       CIter l = ia->my_class;
   382       l->splice(l->begin(),*l,ia);
   402       l->splice(l->begin(),*l,ia);
   383 
   403 
   384       ia->parent = ia;
   404       ia->parent = ia;
   385       la->parent = ia;
   405       la->parent = ia;
       
   406     }
       
   407 
       
   408     /**
       
   409      * \brief Move the given element to an other component.
       
   410      *
       
   411      * This method moves the element \e a from its component
       
   412      * to the component of \e comp.
       
   413      * If \e a and \e comp are in the same component then
       
   414      * it returns false otherwise it returns true.
       
   415      */
       
   416 
       
   417     bool move(const T &a, const T &comp) {
       
   418 
       
   419       IIter ai = m[a];
       
   420       IIter lai = _find(ai);
       
   421       IIter clit = _find(m[comp]);
       
   422 
       
   423       if (lai == clit)
       
   424 	return false;
       
   425 
       
   426       ItemList &c = *clit->my_class;
       
   427 
       
   428       bool is_leader = (lai == ai);
       
   429       bool singleton = false;
       
   430 
       
   431       if (is_leader) {
       
   432 	++lai;
       
   433       }
       
   434 
       
   435       c.splice(c.end(), *lai->my_class, ai);
       
   436 
       
   437       if (is_leader) {
       
   438 	if (ai->size == 1) {
       
   439 	  classes.erase(ai->my_class);
       
   440 	  singleton = true;
       
   441 	}
       
   442 	else {
       
   443 	  lai->size = ai->size; 
       
   444 	  lai->my_class = ai->my_class;	
       
   445 	}
       
   446       }
       
   447       if (!singleton) {
       
   448 	for (IIter i = lai; i != lai->my_class->end(); ++i)
       
   449 	  i->parent = lai;
       
   450 	--lai->size;
       
   451       }
       
   452 
       
   453       ai->parent = clit;
       
   454       ai->my_class = 0;
       
   455       ++clit->size;
       
   456 
       
   457       return true;
   386     }
   458     }
   387 
   459 
   388 
   460 
   389     /**
   461     /**
   390      * \brief Remove the given element from the structure.
   462      * \brief Remove the given element from the structure.