//  (C) Copyright Jeremy Siek 2004 

 //  Distributed under the Boost Software License, Version 1.0. (See

 //  accompanying file LICENSE_1_0.txt or copy at

 //  http://www.boost.org/LICENSE_1_0.txt)

 #ifndef BOOST_DETAIL_DISJOINT_SETS_HPP

 #define BOOST_DETAIL_DISJOINT_SETS_HPP

 namespace boost {

 namespace detail {

 template <class ParentPA, class Vertex>

 Vertex

 find_representative_with_path_halving(ParentPA p, Vertex v)

 { 

   Vertex parent = get(p, v);

   Vertex grandparent = get(p, parent);

   while (parent != grandparent) {

     put(p, v, grandparent);

     v =  grandparent;

     parent = get(p, v);

     grandparent = get(p, parent); 

   }

   return parent;

 }

 template <class ParentPA, class Vertex>

 Vertex

 find_representative_with_full_compression(ParentPA parent, Vertex v)

 {

   Vertex old = v;

   Vertex ancestor = get(parent, v);

   while (ancestor != v) {

     v = ancestor;

     ancestor = get(parent, v);

   }

   v = get(parent, old);

   while (ancestor != v) {

     put(parent, old, ancestor);

     old = v;

     v = get(parent, old);

   }

   return ancestor;

 }

 /* the postcondition of link sets is:

  component_representative(i) == component_representative(j)

  */

 template <class ParentPA, class RankPA, class Vertex, 

           class ComponentRepresentative>

 inline void

 link_sets(ParentPA p, RankPA rank, Vertex i, Vertex j,

           ComponentRepresentative comp_rep)

 {

   i = comp_rep(p, i);

   j = comp_rep(p, j);

   if (i == j) return;

   if (get(rank, i) > get(rank, j)) 

     put(p, j, i);

   else {

     put(p, i, j);

     if (get(rank, i) == get(rank, j)) 

       put(rank, j, get(rank, j) + 1);

   }

 }  

 // normalize components has the following postcondidition:

 // i >= p[i]

 // that is, the representative is the node with the smallest index in its class

 // as its precondition it it assumes that the node container is compressed

 template <class ParentPA, class Vertex>

 inline void

 normalize_node(ParentPA p, Vertex i)

 {

   if (i > get(p,i) || get(p, get(p,i)) != get(p,i))   

     put(p,i, get(p, get(p,i)));

   else {

     put(p, get(p,i), i);

     put(p, i, i);

   } 

 }

   } // namespace detail

 } // namespace boost

 #endif // BOOST_DETAIL_DISJOINT_SETS_HPP