epoc32/include/stdapis/boost/pending/detail/disjoint_sets.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:27:01 +0100
branchSymbian2
changeset 3 e1b950c65cb4
parent 2 epoc32/include/stdapis/boost/pending/disjoint_sets.hpp@2fe1408b6811
child 4 837f303aceeb
permissions -rw-r--r--
Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
     1 //
     2 //=======================================================================
     3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     5 //
     6 // Distributed under the Boost Software License, Version 1.0. (See
     7 // accompanying file LICENSE_1_0.txt or copy at
     8 // http://www.boost.org/LICENSE_1_0.txt)
     9 //=======================================================================
    10 //
    11 #ifndef BOOST_DISJOINT_SETS_HPP
    12 #define BOOST_DISJOINT_SETS_HPP
    13 
    14 #include <vector>
    15 #include <boost/graph/properties.hpp>
    16 #include <boost/pending/detail/disjoint_sets.hpp>
    17 
    18 namespace boost {
    19 
    20   struct find_with_path_halving {
    21     template <class ParentPA, class Vertex>
    22     Vertex operator()(ParentPA p, Vertex v) { 
    23       return detail::find_representative_with_path_halving(p, v);
    24     }
    25   };
    26 
    27   struct find_with_full_path_compression {
    28     template <class ParentPA, class Vertex>
    29     Vertex operator()(ParentPA p, Vertex v){
    30       return detail::find_representative_with_full_compression(p, v);
    31     }
    32   };
    33 
    34   // This is a generalized functor to provide disjoint sets operations
    35   // with "union by rank" and "path compression".  A disjoint-set data
    36   // structure maintains a collection S={S1, S2, ..., Sk} of disjoint
    37   // sets. Each set is identified by a representative, which is some
    38   // member of of the set. Sets are represented by rooted trees. Two
    39   // heuristics: "union by rank" and "path compression" are used to
    40   // speed up the operations.
    41 
    42   // Disjoint Set requires two vertex properties for internal use.  A
    43   // RankPA and a ParentPA. The RankPA must map Vertex to some Integral type
    44   // (preferably the size_type associated with Vertex). The ParentPA
    45   // must map Vertex to Vertex.
    46   template <class RankPA, class ParentPA,
    47     class FindCompress = find_with_full_path_compression
    48     >
    49   class disjoint_sets {
    50     typedef disjoint_sets self;
    51     
    52     inline disjoint_sets() {}
    53   public:
    54     inline disjoint_sets(RankPA r, ParentPA p) 
    55       : rank(r), parent(p) {}
    56 
    57     inline disjoint_sets(const self& c) 
    58       : rank(c.rank), parent(c.parent) {}
    59     
    60     // Make Set -- Create a singleton set containing vertex x
    61     template <class Element>
    62     inline void make_set(Element x)
    63     {
    64       put(parent, x, x);
    65       typedef typename property_traits<RankPA>::value_type R;
    66       put(rank, x, R());
    67     }
    68     
    69     // Link - union the two sets represented by vertex x and y
    70     template <class Element>
    71     inline void link(Element x, Element y)
    72     {
    73       detail::link_sets(parent, rank, x, y, rep);
    74     }
    75     
    76     // Union-Set - union the two sets containing vertex x and y 
    77     template <class Element>
    78     inline void union_set(Element x, Element y)
    79     {
    80       link(find_set(x), find_set(y));
    81     }
    82     
    83     // Find-Set - returns the Element representative of the set
    84     // containing Element x and applies path compression.
    85     template <class Element>
    86     inline Element find_set(Element x)
    87     {
    88       return rep(parent, x);
    89     }
    90 
    91     template <class ElementIterator>
    92     inline std::size_t count_sets(ElementIterator first, ElementIterator last)
    93     {
    94       std::size_t count = 0;  
    95       for ( ; first != last; ++first)
    96       if (get(parent, *first) == *first)
    97         ++count;
    98       return count;
    99     }
   100 
   101     template <class ElementIterator>
   102     inline void normalize_sets(ElementIterator first, ElementIterator last)
   103     {
   104       for (; first != last; ++first) 
   105         detail::normalize_node(parent, *first);
   106     }    
   107     
   108     template <class ElementIterator>
   109     inline void compress_sets(ElementIterator first, ElementIterator last)
   110     {
   111       for (; first != last; ++first) 
   112         detail::find_representative_with_full_compression(parent, *first);
   113     }    
   114   protected:
   115     RankPA rank;
   116     ParentPA parent;
   117     FindCompress rep;
   118   };
   119 
   120 
   121   
   122 
   123   template <class ID = identity_property_map,
   124             class InverseID = identity_property_map,
   125             class FindCompress = find_with_full_path_compression
   126             >
   127   class disjoint_sets_with_storage
   128   {
   129     typedef typename property_traits<ID>::value_type Index;
   130     typedef std::vector<Index> ParentContainer;
   131     typedef std::vector<unsigned char> RankContainer;
   132   public:
   133     typedef typename ParentContainer::size_type size_type;
   134 
   135     disjoint_sets_with_storage(size_type n = 0,
   136                                ID id_ = ID(),
   137                                InverseID inv = InverseID())
   138       : id(id_), id_to_vertex(inv), rank(n, 0), parent(n)
   139     {
   140       for (Index i = 0; i < n; ++i)
   141         parent[i] = i;
   142     }
   143     // note this is not normally needed
   144     template <class Element>
   145     inline void 
   146     make_set(Element x) {
   147       parent[x] = x;
   148       rank[x]   = 0;
   149     }
   150     template <class Element>
   151     inline void 
   152     link(Element x, Element y)
   153     {
   154       extend_sets(x,y);
   155       detail::link_sets(&parent[0], &rank[0], 
   156                         get(id,x), get(id,y), rep);
   157     }
   158     template <class Element>
   159     inline void 
   160     union_set(Element x, Element y) {
   161       Element rx = find_set(x);
   162       Element ry = find_set(y);
   163       link(rx, ry);
   164     }
   165     template <class Element>
   166     inline Element find_set(Element x) {
   167       return id_to_vertex[rep(&parent[0], get(id,x))];
   168     }
   169 
   170     template <class ElementIterator>
   171     inline std::size_t count_sets(ElementIterator first, ElementIterator last)
   172     {
   173       std::size_t count = 0;  
   174       for ( ; first != last; ++first)
   175       if (parent[*first] == *first)
   176         ++count;
   177       return count;
   178     }
   179 
   180     template <class ElementIterator>
   181     inline void normalize_sets(ElementIterator first, ElementIterator last)
   182     {
   183       for (; first != last; ++first) 
   184         detail::normalize_node(&parent[0], *first);
   185     }    
   186     
   187     template <class ElementIterator>
   188     inline void compress_sets(ElementIterator first, ElementIterator last)
   189     {
   190       for (; first != last; ++first) 
   191         detail::find_representative_with_full_compression(&parent[0],
   192                                                           *first);
   193     }    
   194 
   195     const ParentContainer& parents() { return parent; }
   196 
   197   protected:
   198 
   199     template <class Element>
   200     inline void 
   201     extend_sets(Element x, Element y)
   202     {
   203       Index needed = get(id,x) > get(id,y) ? get(id,x) + 1 : get(id,y) + 1;
   204       if (needed > parent.size()) {
   205         rank.insert(rank.end(), needed - rank.size(), 0);
   206         for (Index k = parent.size(); k < needed; ++k)
   207         parent.push_back(k);
   208       } 
   209     }
   210 
   211     ID id;
   212     InverseID id_to_vertex;
   213     RankContainer rank;
   214     ParentContainer parent;
   215     FindCompress rep;
   216   };
   217 
   218 } // namespace boost
   219 
   220 #endif // BOOST_DISJOINT_SETS_HPP