1.1 --- a/src/work/johanna/unionfind.h	Thu Apr 29 16:30:39 2004 +0000
     1.2 +++ b/src/work/johanna/unionfind.h	Thu Apr 29 16:45:40 2004 +0000
     1.3 @@ -264,6 +264,26 @@
     1.4      }
     1.5  
     1.6      /**
     1.7 +     * \brief Insert the given element into the component of the others.
     1.8 +     *
     1.9 +     * This methods insert the element \e a into the component of the
    1.10 +     * element \e comp. 
    1.11 +     */
    1.12 +
    1.13 +    void insert(const T &a, const T &comp) {
    1.14 +      
    1.15 +      IIter clit = _find(m[comp]);
    1.16 +      ItemList &c = *clit->my_class;
    1.17 +      c.push_back(ItemType(a,0));
    1.18 +      IIter ai = c.end();
    1.19 +      --ai;
    1.20 +      ai->parent = clit;
    1.21 +      m.set(a, ai);
    1.22 +      ++clit->size;
    1.23 +    }
    1.24 +
    1.25 +
    1.26 +    /**
    1.27       * \brief Find the leader of the component of the given element.
    1.28       *
    1.29       * The method returns the leader of the component of the given element.
    1.30 @@ -385,6 +405,58 @@
    1.31        la->parent = ia;
    1.32      }
    1.33  
    1.34 +    /**
    1.35 +     * \brief Move the given element to an other component.
    1.36 +     *
    1.37 +     * This method moves the element \e a from its component
    1.38 +     * to the component of \e comp.
    1.39 +     * If \e a and \e comp are in the same component then
    1.40 +     * it returns false otherwise it returns true.
    1.41 +     */
    1.42 +
    1.43 +    bool move(const T &a, const T &comp) {
    1.44 +
    1.45 +      IIter ai = m[a];
    1.46 +      IIter lai = _find(ai);
    1.47 +      IIter clit = _find(m[comp]);
    1.48 +
    1.49 +      if (lai == clit)
    1.50 +	return false;
    1.51 +
    1.52 +      ItemList &c = *clit->my_class;
    1.53 +
    1.54 +      bool is_leader = (lai == ai);
    1.55 +      bool singleton = false;
    1.56 +
    1.57 +      if (is_leader) {
    1.58 +	++lai;
    1.59 +      }
    1.60 +
    1.61 +      c.splice(c.end(), *lai->my_class, ai);
    1.62 +
    1.63 +      if (is_leader) {
    1.64 +	if (ai->size == 1) {
    1.65 +	  classes.erase(ai->my_class);
    1.66 +	  singleton = true;
    1.67 +	}
    1.68 +	else {
    1.69 +	  lai->size = ai->size; 
    1.70 +	  lai->my_class = ai->my_class;	
    1.71 +	}
    1.72 +      }
    1.73 +      if (!singleton) {
    1.74 +	for (IIter i = lai; i != lai->my_class->end(); ++i)
    1.75 +	  i->parent = lai;
    1.76 +	--lai->size;
    1.77 +      }
    1.78 +
    1.79 +      ai->parent = clit;
    1.80 +      ai->my_class = 0;
    1.81 +      ++clit->size;
    1.82 +
    1.83 +      return true;
    1.84 +    }
    1.85 +
    1.86  
    1.87      /**
    1.88       * \brief Remove the given element from the structure.

     2.1 --- a/src/work/johanna/unionfind_test.cc	Thu Apr 29 16:30:39 2004 +0000
     2.2 +++ b/src/work/johanna/unionfind_test.cc	Thu Apr 29 16:45:40 2004 +0000
     2.3 @@ -69,15 +69,63 @@
     2.4    check(U.join(3,5));
     2.5    print(U);
     2.6  
     2.7 +  cout << "Inserting 8 to the component of 5 ..." << endl;
     2.8 +  U.insert(8,5);
     2.9 +  print(U);
    2.10 +
    2.11    cout << "size of the class of 4: " << U.size(4) << endl;
    2.12    check(U.size(4) == 3);
    2.13    cout << "size of the class of 5: " << U.size(5) << endl;
    2.14 -  check(U.size(5) == 2);
    2.15 +  check(U.size(5) == 3);
    2.16    cout << "size of the class of 6: " << U.size(6) << endl;
    2.17    check(U.size(6) == 1);
    2.18    cout << "size of the class of 2: " << U.size(2) << endl;
    2.19    check(U.size(2) == 3);
    2.20  
    2.21 +  cout << "Inserting 9 ..." << endl;
    2.22 +  U.insert(9);
    2.23 +  print(U);
    2.24 +  cout << "Inserting 10 to the component of 9 ..." << endl;
    2.25 +  U.insert(10,9);
    2.26 +  print(U);
    2.27 +
    2.28 +  cout << "Joining 8 and 10..." << endl;
    2.29 +  check(U.join(8,10));
    2.30 +  print(U);
    2.31 +
    2.32 +  cout << "Move 9 to the class of 4 ..." << endl;
    2.33 +  check(U.move(9,4));
    2.34 +  print(U);
    2.35 +
    2.36 +  cout << "Move 9 to the class of 2 ..." << endl;
    2.37 +  check(!U.move(9,2));
    2.38 +  print(U);
    2.39 +
    2.40 +  cout << "size of the class of 4: " << U.size(4) << endl;
    2.41 +  check(U.size(4) == 4);
    2.42 +  cout << "size of the class of 9: " << U.size(9) << endl;
    2.43 +  check(U.size(9) == 4);
    2.44 +  
    2.45 +  cout << "Move 5 to the class of 6 ..." << endl;
    2.46 +  check(U.move(5,6));
    2.47 +  print(U);
    2.48 +
    2.49 +  cout << "size of the class of 5: " << U.size(5) << endl;
    2.50 +  check(U.size(5) == 2);
    2.51 +  cout << "size of the class of 8: " << U.size(8) << endl;
    2.52 +  check(U.size(8) == 3);
    2.53 +
    2.54 +  cout << "Move 7 to the class of 10 ..." << endl;
    2.55 +  check(U.move(7,10));
    2.56 +  print(U);
    2.57 +
    2.58 +  cout << "size of the class of 7: " << U.size(7) << endl;
    2.59 +  check(U.size(7) == 4);
    2.60 +
    2.61 +  cout <<"erase 9: " << endl;
    2.62 +  U.erase(9);
    2.63 +  print(U);
    2.64 +
    2.65    cout <<"erase 1: " << endl;
    2.66    U.erase(1);
    2.67    print(U);
    2.68 @@ -96,8 +144,8 @@
    2.69    U.erase(6);
    2.70    print(U);
    2.71  
    2.72 -  cout << "split the class of 5: " << endl;
    2.73 -  U.split(5);
    2.74 +  cout << "split the class of 8: " << endl;
    2.75 +  U.split(8);
    2.76    print(U);
    2.77  
    2.78