ceph/src/boost/boost/pending/detail/disjoint_sets.hpp

   1 //  (C) Copyright Jeremy Siek 2004
   2 //  Distributed under the Boost Software License, Version 1.0. (See
   3 //  accompanying file LICENSE_1_0.txt or copy at
   4 //  http://www.boost.org/LICENSE_1_0.txt)
   5
   6 #ifndef BOOST_DETAIL_DISJOINT_SETS_HPP
   7 #define BOOST_DETAIL_DISJOINT_SETS_HPP
   8
   9 namespace boost {
  10
  11 namespace detail {
  12
  13 template <class ParentPA, class Vertex>
  14 Vertex
  15 find_representative_with_path_halving(ParentPA p, Vertex v)
  16 {
  17   Vertex parent = get(p, v);
  18   Vertex grandparent = get(p, parent);
  19   while (parent != grandparent) {
  20     put(p, v, grandparent);
  21     v =  grandparent;
  22     parent = get(p, v);
  23     grandparent = get(p, parent);
  24   }
  25   return parent;
  26 }
  27
  28 template <class ParentPA, class Vertex>
  29 Vertex
  30 find_representative_with_full_compression(ParentPA parent, Vertex v)
  31 {
  32   Vertex old = v;
  33   Vertex ancestor = get(parent, v);
  34   while (ancestor != v) {
  35     v = ancestor;
  36     ancestor = get(parent, v);
  37   }
  38   v = get(parent, old);
  39   while (ancestor != v) {
  40     put(parent, old, ancestor);
  41     old = v;
  42     v = get(parent, old);
  43   }
  44   return ancestor;
  45 }
  46
  47 /* the postcondition of link sets is:
  48  component_representative(i) == component_representative(j)
  49  */
  50 template <class ParentPA, class RankPA, class Vertex,
  51           class ComponentRepresentative>
  52 inline void
  53 link_sets(ParentPA p, RankPA rank, Vertex i, Vertex j,
  54           ComponentRepresentative comp_rep)
  55 {
  56   i = comp_rep(p, i);
  57   j = comp_rep(p, j);
  58   if (i == j) return;
  59   if (get(rank, i) > get(rank, j))
  60     put(p, j, i);
  61   else {
  62     put(p, i, j);
  63     if (get(rank, i) == get(rank, j))
  64       put(rank, j, get(rank, j) + 1);
  65   }
  66 }
  67
  68 // normalize components has the following postcondidition:
  69 // i >= p[i]
  70 // that is, the representative is the node with the smallest index in its class
  71 // as its precondition it it assumes that the node container is compressed
  72
  73 template <class ParentPA, class Vertex>
  74 inline void
  75 normalize_node(ParentPA p, Vertex i)
  76 {
  77   if (i > get(p,i) || get(p, get(p,i)) != get(p,i))
  78     put(p,i, get(p, get(p,i)));
  79   else {
  80     put(p, get(p,i), i);
  81     put(p, i, i);
  82   }
  83 }
  84
  85   } // namespace detail
  86 } // namespace boost
  87
  88 #endif // BOOST_DETAIL_DISJOINT_SETS_HPP