1.1 --- a/epoc32/include/stdapis/boost/pending/disjoint_sets.hpp Tue Mar 16 16:12:26 2010 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,220 +0,0 @@
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