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