epoc32/include/stdapis/boost/pending/detail/disjoint_sets.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
parent 3 e1b950c65cb4
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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