epoc32/include/stdapis/boost/pending/disjoint_sets.hpp
branchSymbian3
changeset 4 837f303aceeb
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/pending/disjoint_sets.hpp	Wed Mar 31 12:33:34 2010 +0100
     1.3 @@ -0,0 +1,220 @@
     1.4 +//
     1.5 +//=======================================================================
     1.6 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     1.8 +//
     1.9 +// Distributed under the Boost Software License, Version 1.0. (See
    1.10 +// accompanying file LICENSE_1_0.txt or copy at
    1.11 +// http://www.boost.org/LICENSE_1_0.txt)
    1.12 +//=======================================================================
    1.13 +//
    1.14 +#ifndef BOOST_DISJOINT_SETS_HPP
    1.15 +#define BOOST_DISJOINT_SETS_HPP
    1.16 +
    1.17 +#include <vector>
    1.18 +#include <boost/graph/properties.hpp>
    1.19 +#include <boost/pending/detail/disjoint_sets.hpp>
    1.20 +
    1.21 +namespace boost {
    1.22 +
    1.23 +  struct find_with_path_halving {
    1.24 +    template <class ParentPA, class Vertex>
    1.25 +    Vertex operator()(ParentPA p, Vertex v) { 
    1.26 +      return detail::find_representative_with_path_halving(p, v);
    1.27 +    }
    1.28 +  };
    1.29 +
    1.30 +  struct find_with_full_path_compression {
    1.31 +    template <class ParentPA, class Vertex>
    1.32 +    Vertex operator()(ParentPA p, Vertex v){
    1.33 +      return detail::find_representative_with_full_compression(p, v);
    1.34 +    }
    1.35 +  };
    1.36 +
    1.37 +  // This is a generalized functor to provide disjoint sets operations
    1.38 +  // with "union by rank" and "path compression".  A disjoint-set data
    1.39 +  // structure maintains a collection S={S1, S2, ..., Sk} of disjoint
    1.40 +  // sets. Each set is identified by a representative, which is some
    1.41 +  // member of of the set. Sets are represented by rooted trees. Two
    1.42 +  // heuristics: "union by rank" and "path compression" are used to
    1.43 +  // speed up the operations.
    1.44 +
    1.45 +  // Disjoint Set requires two vertex properties for internal use.  A
    1.46 +  // RankPA and a ParentPA. The RankPA must map Vertex to some Integral type
    1.47 +  // (preferably the size_type associated with Vertex). The ParentPA
    1.48 +  // must map Vertex to Vertex.
    1.49 +  template <class RankPA, class ParentPA,
    1.50 +    class FindCompress = find_with_full_path_compression
    1.51 +    >
    1.52 +  class disjoint_sets {
    1.53 +    typedef disjoint_sets self;
    1.54 +    
    1.55 +    inline disjoint_sets() {}
    1.56 +  public:
    1.57 +    inline disjoint_sets(RankPA r, ParentPA p) 
    1.58 +      : rank(r), parent(p) {}
    1.59 +
    1.60 +    inline disjoint_sets(const self& c) 
    1.61 +      : rank(c.rank), parent(c.parent) {}
    1.62 +    
    1.63 +    // Make Set -- Create a singleton set containing vertex x
    1.64 +    template <class Element>
    1.65 +    inline void make_set(Element x)
    1.66 +    {
    1.67 +      put(parent, x, x);
    1.68 +      typedef typename property_traits<RankPA>::value_type R;
    1.69 +      put(rank, x, R());
    1.70 +    }
    1.71 +    
    1.72 +    // Link - union the two sets represented by vertex x and y
    1.73 +    template <class Element>
    1.74 +    inline void link(Element x, Element y)
    1.75 +    {
    1.76 +      detail::link_sets(parent, rank, x, y, rep);
    1.77 +    }
    1.78 +    
    1.79 +    // Union-Set - union the two sets containing vertex x and y 
    1.80 +    template <class Element>
    1.81 +    inline void union_set(Element x, Element y)
    1.82 +    {
    1.83 +      link(find_set(x), find_set(y));
    1.84 +    }
    1.85 +    
    1.86 +    // Find-Set - returns the Element representative of the set
    1.87 +    // containing Element x and applies path compression.
    1.88 +    template <class Element>
    1.89 +    inline Element find_set(Element x)
    1.90 +    {
    1.91 +      return rep(parent, x);
    1.92 +    }
    1.93 +
    1.94 +    template <class ElementIterator>
    1.95 +    inline std::size_t count_sets(ElementIterator first, ElementIterator last)
    1.96 +    {
    1.97 +      std::size_t count = 0;  
    1.98 +      for ( ; first != last; ++first)
    1.99 +      if (get(parent, *first) == *first)
   1.100 +        ++count;
   1.101 +      return count;
   1.102 +    }
   1.103 +
   1.104 +    template <class ElementIterator>
   1.105 +    inline void normalize_sets(ElementIterator first, ElementIterator last)
   1.106 +    {
   1.107 +      for (; first != last; ++first) 
   1.108 +        detail::normalize_node(parent, *first);
   1.109 +    }    
   1.110 +    
   1.111 +    template <class ElementIterator>
   1.112 +    inline void compress_sets(ElementIterator first, ElementIterator last)
   1.113 +    {
   1.114 +      for (; first != last; ++first) 
   1.115 +        detail::find_representative_with_full_compression(parent, *first);
   1.116 +    }    
   1.117 +  protected:
   1.118 +    RankPA rank;
   1.119 +    ParentPA parent;
   1.120 +    FindCompress rep;
   1.121 +  };
   1.122 +
   1.123 +
   1.124 +  
   1.125 +
   1.126 +  template <class ID = identity_property_map,
   1.127 +            class InverseID = identity_property_map,
   1.128 +            class FindCompress = find_with_full_path_compression
   1.129 +            >
   1.130 +  class disjoint_sets_with_storage
   1.131 +  {
   1.132 +    typedef typename property_traits<ID>::value_type Index;
   1.133 +    typedef std::vector<Index> ParentContainer;
   1.134 +    typedef std::vector<unsigned char> RankContainer;
   1.135 +  public:
   1.136 +    typedef typename ParentContainer::size_type size_type;
   1.137 +
   1.138 +    disjoint_sets_with_storage(size_type n = 0,
   1.139 +                               ID id_ = ID(),
   1.140 +                               InverseID inv = InverseID())
   1.141 +      : id(id_), id_to_vertex(inv), rank(n, 0), parent(n)
   1.142 +    {
   1.143 +      for (Index i = 0; i < n; ++i)
   1.144 +        parent[i] = i;
   1.145 +    }
   1.146 +    // note this is not normally needed
   1.147 +    template <class Element>
   1.148 +    inline void 
   1.149 +    make_set(Element x) {
   1.150 +      parent[x] = x;
   1.151 +      rank[x]   = 0;
   1.152 +    }
   1.153 +    template <class Element>
   1.154 +    inline void 
   1.155 +    link(Element x, Element y)
   1.156 +    {
   1.157 +      extend_sets(x,y);
   1.158 +      detail::link_sets(&parent[0], &rank[0], 
   1.159 +                        get(id,x), get(id,y), rep);
   1.160 +    }
   1.161 +    template <class Element>
   1.162 +    inline void 
   1.163 +    union_set(Element x, Element y) {
   1.164 +      Element rx = find_set(x);
   1.165 +      Element ry = find_set(y);
   1.166 +      link(rx, ry);
   1.167 +    }
   1.168 +    template <class Element>
   1.169 +    inline Element find_set(Element x) {
   1.170 +      return id_to_vertex[rep(&parent[0], get(id,x))];
   1.171 +    }
   1.172 +
   1.173 +    template <class ElementIterator>
   1.174 +    inline std::size_t count_sets(ElementIterator first, ElementIterator last)
   1.175 +    {
   1.176 +      std::size_t count = 0;  
   1.177 +      for ( ; first != last; ++first)
   1.178 +      if (parent[*first] == *first)
   1.179 +        ++count;
   1.180 +      return count;
   1.181 +    }
   1.182 +
   1.183 +    template <class ElementIterator>
   1.184 +    inline void normalize_sets(ElementIterator first, ElementIterator last)
   1.185 +    {
   1.186 +      for (; first != last; ++first) 
   1.187 +        detail::normalize_node(&parent[0], *first);
   1.188 +    }    
   1.189 +    
   1.190 +    template <class ElementIterator>
   1.191 +    inline void compress_sets(ElementIterator first, ElementIterator last)
   1.192 +    {
   1.193 +      for (; first != last; ++first) 
   1.194 +        detail::find_representative_with_full_compression(&parent[0],
   1.195 +                                                          *first);
   1.196 +    }    
   1.197 +
   1.198 +    const ParentContainer& parents() { return parent; }
   1.199 +
   1.200 +  protected:
   1.201 +
   1.202 +    template <class Element>
   1.203 +    inline void 
   1.204 +    extend_sets(Element x, Element y)
   1.205 +    {
   1.206 +      Index needed = get(id,x) > get(id,y) ? get(id,x) + 1 : get(id,y) + 1;
   1.207 +      if (needed > parent.size()) {
   1.208 +        rank.insert(rank.end(), needed - rank.size(), 0);
   1.209 +        for (Index k = parent.size(); k < needed; ++k)
   1.210 +        parent.push_back(k);
   1.211 +      } 
   1.212 +    }
   1.213 +
   1.214 +    ID id;
   1.215 +    InverseID id_to_vertex;
   1.216 +    RankContainer rank;
   1.217 +    ParentContainer parent;
   1.218 +    FindCompress rep;
   1.219 +  };
   1.220 +
   1.221 +} // namespace boost
   1.222 +
   1.223 +#endif // BOOST_DISJOINT_SETS_HPP