--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/epoc32/include/stdapis/boost/pending/disjoint_sets.hpp Wed Mar 31 12:33:34 2010 +0100
@@ -0,0 +1,220 @@
+//
+//=======================================================================
+// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+//
+#ifndef BOOST_DISJOINT_SETS_HPP
+#define BOOST_DISJOINT_SETS_HPP
+
+#include <vector>
+#include <boost/graph/properties.hpp>
+#include <boost/pending/detail/disjoint_sets.hpp>
+
+namespace boost {
+
+ struct find_with_path_halving {
+ template <class ParentPA, class Vertex>
+ Vertex operator()(ParentPA p, Vertex v) {
+ return detail::find_representative_with_path_halving(p, v);
+ }
+ };
+
+ struct find_with_full_path_compression {
+ template <class ParentPA, class Vertex>
+ Vertex operator()(ParentPA p, Vertex v){
+ return detail::find_representative_with_full_compression(p, v);
+ }
+ };
+
+ // This is a generalized functor to provide disjoint sets operations
+ // with "union by rank" and "path compression". A disjoint-set data
+ // structure maintains a collection S={S1, S2, ..., Sk} of disjoint
+ // sets. Each set is identified by a representative, which is some
+ // member of of the set. Sets are represented by rooted trees. Two
+ // heuristics: "union by rank" and "path compression" are used to
+ // speed up the operations.
+
+ // Disjoint Set requires two vertex properties for internal use. A
+ // RankPA and a ParentPA. The RankPA must map Vertex to some Integral type
+ // (preferably the size_type associated with Vertex). The ParentPA
+ // must map Vertex to Vertex.
+ template <class RankPA, class ParentPA,
+ class FindCompress = find_with_full_path_compression
+ >
+ class disjoint_sets {
+ typedef disjoint_sets self;
+
+ inline disjoint_sets() {}
+ public:
+ inline disjoint_sets(RankPA r, ParentPA p)
+ : rank(r), parent(p) {}
+
+ inline disjoint_sets(const self& c)
+ : rank(c.rank), parent(c.parent) {}
+
+ // Make Set -- Create a singleton set containing vertex x
+ template <class Element>
+ inline void make_set(Element x)
+ {
+ put(parent, x, x);
+ typedef typename property_traits<RankPA>::value_type R;
+ put(rank, x, R());
+ }
+
+ // Link - union the two sets represented by vertex x and y
+ template <class Element>
+ inline void link(Element x, Element y)
+ {
+ detail::link_sets(parent, rank, x, y, rep);
+ }
+
+ // Union-Set - union the two sets containing vertex x and y
+ template <class Element>
+ inline void union_set(Element x, Element y)
+ {
+ link(find_set(x), find_set(y));
+ }
+
+ // Find-Set - returns the Element representative of the set
+ // containing Element x and applies path compression.
+ template <class Element>
+ inline Element find_set(Element x)
+ {
+ return rep(parent, x);
+ }
+
+ template <class ElementIterator>
+ inline std::size_t count_sets(ElementIterator first, ElementIterator last)
+ {
+ std::size_t count = 0;
+ for ( ; first != last; ++first)
+ if (get(parent, *first) == *first)
+ ++count;
+ return count;
+ }
+
+ template <class ElementIterator>
+ inline void normalize_sets(ElementIterator first, ElementIterator last)
+ {
+ for (; first != last; ++first)
+ detail::normalize_node(parent, *first);
+ }
+
+ template <class ElementIterator>
+ inline void compress_sets(ElementIterator first, ElementIterator last)
+ {
+ for (; first != last; ++first)
+ detail::find_representative_with_full_compression(parent, *first);
+ }
+ protected:
+ RankPA rank;
+ ParentPA parent;
+ FindCompress rep;
+ };
+
+
+
+
+ template <class ID = identity_property_map,
+ class InverseID = identity_property_map,
+ class FindCompress = find_with_full_path_compression
+ >
+ class disjoint_sets_with_storage
+ {
+ typedef typename property_traits<ID>::value_type Index;
+ typedef std::vector<Index> ParentContainer;
+ typedef std::vector<unsigned char> RankContainer;
+ public:
+ typedef typename ParentContainer::size_type size_type;
+
+ disjoint_sets_with_storage(size_type n = 0,
+ ID id_ = ID(),
+ InverseID inv = InverseID())
+ : id(id_), id_to_vertex(inv), rank(n, 0), parent(n)
+ {
+ for (Index i = 0; i < n; ++i)
+ parent[i] = i;
+ }
+ // note this is not normally needed
+ template <class Element>
+ inline void
+ make_set(Element x) {
+ parent[x] = x;
+ rank[x] = 0;
+ }
+ template <class Element>
+ inline void
+ link(Element x, Element y)
+ {
+ extend_sets(x,y);
+ detail::link_sets(&parent[0], &rank[0],
+ get(id,x), get(id,y), rep);
+ }
+ template <class Element>
+ inline void
+ union_set(Element x, Element y) {
+ Element rx = find_set(x);
+ Element ry = find_set(y);
+ link(rx, ry);
+ }
+ template <class Element>
+ inline Element find_set(Element x) {
+ return id_to_vertex[rep(&parent[0], get(id,x))];
+ }
+
+ template <class ElementIterator>
+ inline std::size_t count_sets(ElementIterator first, ElementIterator last)
+ {
+ std::size_t count = 0;
+ for ( ; first != last; ++first)
+ if (parent[*first] == *first)
+ ++count;
+ return count;
+ }
+
+ template <class ElementIterator>
+ inline void normalize_sets(ElementIterator first, ElementIterator last)
+ {
+ for (; first != last; ++first)
+ detail::normalize_node(&parent[0], *first);
+ }
+
+ template <class ElementIterator>
+ inline void compress_sets(ElementIterator first, ElementIterator last)
+ {
+ for (; first != last; ++first)
+ detail::find_representative_with_full_compression(&parent[0],
+ *first);
+ }
+
+ const ParentContainer& parents() { return parent; }
+
+ protected:
+
+ template <class Element>
+ inline void
+ extend_sets(Element x, Element y)
+ {
+ Index needed = get(id,x) > get(id,y) ? get(id,x) + 1 : get(id,y) + 1;
+ if (needed > parent.size()) {
+ rank.insert(rank.end(), needed - rank.size(), 0);
+ for (Index k = parent.size(); k < needed; ++k)
+ parent.push_back(k);
+ }
+ }
+
+ ID id;
+ InverseID id_to_vertex;
+ RankContainer rank;
+ ParentContainer parent;
+ FindCompress rep;
+ };
+
+} // namespace boost
+
+#endif // BOOST_DISJOINT_SETS_HPP