?????????? ????????? - ??????????????? - /home/agenciai/public_html/cd38d8/pending.zip
???????
PK Q�!\ 6l\� � stringtok.hppnu �[��� // (C) Copyright Jeremy Siek 2004 // 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_STRINGTOK_HPP #define BOOST_STRINGTOK_HPP /* * stringtok.hpp -- Breaks a string into tokens. This is an example for lib3. * * Template function looks like this: * * template <typename Container> * void stringtok (Container &l, * string const &s, * char const * const ws = " \t\n"); * * A nondestructive version of strtok() that handles its own memory and can * be broken up by any character(s). Does all the work at once rather than * in an invocation loop like strtok() requires. * * Container is any type that supports push_back(a_string), although using * list<string> and deque<string> are indicated due to their O(1) push_back. * (I prefer deque<> because op[]/at() is available as well.) The first * parameter references an existing Container. * * s is the string to be tokenized. From the parameter declaration, it can * be seen that s is not affected. Since references-to-const may refer to * temporaries, you could use stringtok(some_container, readline("")) when * using the GNU readline library. * * The final parameter is an array of characters that serve as whitespace. * Whitespace characters default to one or more of tab, space, and newline, * in any combination. * * 'l' need not be empty on entry. On return, 'l' will have the token * strings appended. * * * [Example: * list<string> ls; * stringtok (ls, " this \t is\t\n a test "); * for (list<string>::const_iterator i = ls.begin(); * i != ls.end(); ++i) * { * cerr << ':' << (*i) << ":\n"; * } * * would print * :this: * :is: * :a: * :test: * -end example] * * pedwards@jaj.com May 1999 */ #include <string> #include <cstring> // for strchr /***************************************************************** * This is the only part of the implementation that I don't like. * It can probably be improved upon by the reader... */ inline bool isws(char c, char const* const wstr) { using namespace std; return (strchr(wstr, c) != NULL); } namespace boost { /***************************************************************** * Simplistic and quite Standard, but a bit slow. This should be * templatized on basic_string instead, or on a more generic StringT * that just happens to support ::size_type, .substr(), and so on. * I had hoped that "whitespace" would be a trait, but it isn't, so * the user must supply it. Enh, this lets them break up strings on * different things easier than traits would anyhow. */ template < typename Container > void stringtok( Container& l, std::string const& s, char const* const ws = " \t\n") { typedef std::string::size_type size_type; const size_type S = s.size(); size_type i = 0; while (i < S) { // eat leading whitespace while ((i < S) && (isws(s[i], ws))) ++i; if (i == S) return; // nothing left but WS // find end of word size_type j = i + 1; while ((j < S) && (!isws(s[j], ws))) ++j; // add word l.push_back(s.substr(i, j - i)); // set up for next loop i = j + 1; } } } // namespace boost #endif // BOOST_STRINGTOK_HPP PK Q�!\d�q�� � iterator_adaptors.hppnu �[��� // Copyright David Abrahams 2003. // 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) #include <boost/iterator_adaptors.hpp> PK Q�!\Tb��"Q "Q relaxed_heap.hppnu �[��� // Copyright 2004 The Trustees of Indiana University. // Use, modification and distribution is subject to 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) // Authors: Douglas Gregor // Andrew Lumsdaine #warning \ "Use of relaxed_heap is depreciated; please use the standard heap functions." #ifndef BOOST_RELAXED_HEAP_HEADER #define BOOST_RELAXED_HEAP_HEADER #include <boost/config/header_deprecated.hpp> BOOST_HEADER_DEPRECATED("the standard heap functions") #include <functional> #include <boost/property_map/property_map.hpp> #include <boost/optional.hpp> #include <vector> #include <climits> // for CHAR_BIT #include <boost/none.hpp> #ifdef BOOST_RELAXED_HEAP_DEBUG #include <iostream> #endif // BOOST_RELAXED_HEAP_DEBUG #if defined(BOOST_MSVC) #pragma warning(push) #pragma warning(disable : 4355) // complaint about using 'this' to #endif // initialize a member namespace boost { template < typename IndexedType, typename Compare = std::less< IndexedType >, typename ID = identity_property_map > class relaxed_heap { struct group; typedef relaxed_heap self_type; typedef std::size_t rank_type; public: typedef IndexedType value_type; typedef rank_type size_type; private: /** * The kind of key that a group has. The actual values are discussed * in-depth in the documentation of the @c kind field of the @c group * structure. Note that the order of the enumerators *IS* important * and must not be changed. */ enum group_key_kind { smallest_key, stored_key, largest_key }; struct group { explicit group(group_key_kind kind = largest_key) : kind(kind), parent(this), rank(0) { } /** The value associated with this group. This value is only valid * when @c kind!=largest_key (which indicates a deleted * element). Note that the use of boost::optional increases the * memory requirements slightly but does not result in extraneous * memory allocations or deallocations. The optional could be * eliminated when @c value_type is a model of * DefaultConstructible. */ ::boost::optional< value_type > value; /** * The kind of key stored at this group. This may be @c * smallest_key, which indicates that the key is infinitely small; * @c largest_key, which indicates that the key is infinitely * large; or @c stored_key, which means that the key is unknown, * but its relationship to other keys can be determined via the * comparison function object. */ group_key_kind kind; /// The parent of this group. Will only be NULL for the dummy root group group* parent; /// The rank of this group. Equivalent to the number of children in /// the group. rank_type rank; /** The children of this group. For the dummy root group, these are * the roots. This is an array of length log n containing pointers * to the child groups. */ group** children; }; size_type log_base_2(size_type n) // log2 is a macro on some platforms { size_type leading_zeroes = 0; do { size_type next = n << 1; if (n == (next >> 1)) { ++leading_zeroes; n = next; } else { break; } } while (true); return sizeof(size_type) * CHAR_BIT - leading_zeroes - 1; } public: relaxed_heap( size_type n, const Compare& compare = Compare(), const ID& id = ID()) : compare(compare), id(id), root(smallest_key), groups(n), smallest_value(0) { if (n == 0) { root.children = new group*[1]; return; } log_n = log_base_2(n); if (log_n == 0) log_n = 1; size_type g = n / log_n; if (n % log_n > 0) ++g; size_type log_g = log_base_2(g); size_type r = log_g; // Reserve an appropriate amount of space for data structures, so // that we do not need to expand them. index_to_group.resize(g); A.resize(r + 1, 0); root.rank = r + 1; root.children = new group*[(log_g + 1) * (g + 1)]; for (rank_type i = 0; i < r + 1; ++i) root.children[i] = 0; // Build initial heap size_type idx = 0; while (idx < g) { root.children[r] = &index_to_group[idx]; idx = build_tree(root, idx, r, log_g + 1); if (idx != g) r = static_cast< size_type >(log_base_2(g - idx)); } } ~relaxed_heap() { delete[] root.children; } void push(const value_type& x) { groups[get(id, x)] = x; update(x); } void update(const value_type& x) { group* a = &index_to_group[get(id, x) / log_n]; if (!a->value || *a->value == x || compare(x, *a->value)) { if (a != smallest_value) smallest_value = 0; a->kind = stored_key; a->value = x; promote(a); } } void remove(const value_type& x) { group* a = &index_to_group[get(id, x) / log_n]; assert(groups[get(id, x)]); a->value = x; a->kind = smallest_key; promote(a); smallest_value = a; pop(); } value_type& top() { find_smallest(); assert(smallest_value->value != none); return *smallest_value->value; } const value_type& top() const { find_smallest(); assert(smallest_value->value != none); return *smallest_value->value; } bool empty() const { find_smallest(); return !smallest_value || (smallest_value->kind == largest_key); } bool contains(const value_type& x) const { return static_cast< bool >(groups[get(id, x)]); } void pop() { // Fill in smallest_value. This is the group x. find_smallest(); group* x = smallest_value; smallest_value = 0; // Make x a leaf, giving it the smallest value within its group rank_type r = x->rank; group* p = x->parent; { assert(x->value != none); // Find x's group size_type start = get(id, *x->value) - get(id, *x->value) % log_n; size_type end = start + log_n; if (end > groups.size()) end = groups.size(); // Remove the smallest value from the group, and find the new // smallest value. groups[get(id, *x->value)].reset(); x->value.reset(); x->kind = largest_key; for (size_type i = start; i < end; ++i) { if (groups[i] && (!x->value || compare(*groups[i], *x->value))) { x->kind = stored_key; x->value = groups[i]; } } } x->rank = 0; // Combine prior children of x with x group* y = x; for (size_type c = 0; c < r; ++c) { group* child = x->children[c]; if (A[c] == child) A[c] = 0; y = combine(y, child); } // If we got back something other than x, let y take x's place if (y != x) { y->parent = p; p->children[r] = y; assert(r == y->rank); if (A[y->rank] == x) A[y->rank] = do_compare(y, p) ? y : 0; } } #ifdef BOOST_RELAXED_HEAP_DEBUG /************************************************************************* * Debugging support * *************************************************************************/ void dump_tree() { dump_tree(std::cout); } void dump_tree(std::ostream& out) { dump_tree(out, &root); } void dump_tree(std::ostream& out, group* p, bool in_progress = false) { if (!in_progress) { out << "digraph heap {\n" << " edge[dir=\"back\"];\n"; } size_type p_index = 0; if (p != &root) while (&index_to_group[p_index] != p) ++p_index; for (size_type i = 0; i < p->rank; ++i) { group* c = p->children[i]; if (c) { size_type c_index = 0; if (c != &root) while (&index_to_group[c_index] != c) ++c_index; out << " "; if (p == &root) out << 'p'; else out << p_index; out << " -> "; if (c == &root) out << 'p'; else out << c_index; if (A[c->rank] == c) out << " [style=\"dotted\"]"; out << ";\n"; dump_tree(out, c, true); // Emit node information out << " "; if (c == &root) out << 'p'; else out << c_index; out << " [label=\""; if (c == &root) out << 'p'; else out << c_index; out << ":"; size_type start = c_index * log_n; size_type end = start + log_n; if (end > groups.size()) end = groups.size(); while (start != end) { if (groups[start]) { out << " " << get(id, *groups[start]); if (*groups[start] == *c->value) out << "(*)"; } ++start; } out << '"'; if (do_compare(c, p)) { out << " "; if (c == &root) out << 'p'; else out << c_index; out << ", style=\"filled\", fillcolor=\"gray\""; } out << "];\n"; } else { assert(p->parent == p); } } if (!in_progress) out << "}\n"; } bool valid() { // Check that the ranks in the A array match the ranks of the // groups stored there. Also, the active groups must be the last // child of their parent. for (size_type r = 0; r < A.size(); ++r) { if (A[r] && A[r]->rank != r) return false; if (A[r] && A[r]->parent->children[A[r]->parent->rank - 1] != A[r]) return false; } // The root must have no value and a key of -Infinity if (root.kind != smallest_key) return false; return valid(&root); } bool valid(group* p) { for (size_type i = 0; i < p->rank; ++i) { group* c = p->children[i]; if (c) { // Check link structure if (c->parent != p) return false; if (c->rank != i) return false; // A bad group must be active if (do_compare(c, p) && A[i] != c) return false; // Check recursively if (!valid(c)) return false; } else { // Only the root may if (p != &root) return false; } } return true; } #endif // BOOST_RELAXED_HEAP_DEBUG private: size_type build_tree( group& parent, size_type idx, size_type r, size_type max_rank) { group& this_group = index_to_group[idx]; this_group.parent = &parent; ++idx; this_group.children = root.children + (idx * max_rank); this_group.rank = r; for (size_type i = 0; i < r; ++i) { this_group.children[i] = &index_to_group[idx]; idx = build_tree(this_group, idx, i, max_rank); } return idx; } void find_smallest() const { group** roots = root.children; if (!smallest_value) { std::size_t i; for (i = 0; i < root.rank; ++i) { if (roots[i] && (!smallest_value || do_compare(roots[i], smallest_value))) { smallest_value = roots[i]; } } for (i = 0; i < A.size(); ++i) { if (A[i] && (!smallest_value || do_compare(A[i], smallest_value))) smallest_value = A[i]; } } } bool do_compare(group* x, group* y) const { return (x->kind < y->kind || (x->kind == y->kind && x->kind == stored_key && compare(*x->value, *y->value))); } void promote(group* a) { assert(a != 0); rank_type r = a->rank; group* p = a->parent; assert(p != 0); if (do_compare(a, p)) { // s is the rank + 1 sibling group* s = p->rank > r + 1 ? p->children[r + 1] : 0; // If a is the last child of p if (r == p->rank - 1) { if (!A[r]) A[r] = a; else if (A[r] != a) pair_transform(a); } else { assert(s != 0); if (A[r + 1] == s) active_sibling_transform(a, s); else good_sibling_transform(a, s); } } } group* combine(group* a1, group* a2) { assert(a1->rank == a2->rank); if (do_compare(a2, a1)) do_swap(a1, a2); a1->children[a1->rank++] = a2; a2->parent = a1; clean(a1); return a1; } void clean(group* q) { if (2 > q->rank) return; group* qp = q->children[q->rank - 1]; rank_type s = q->rank - 2; group* x = q->children[s]; group* xp = qp->children[s]; assert(s == x->rank); // If x is active, swap x and xp if (A[s] == x) { q->children[s] = xp; xp->parent = q; qp->children[s] = x; x->parent = qp; } } void pair_transform(group* a) { #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 std::cerr << "- pair transform\n"; #endif rank_type r = a->rank; // p is a's parent group* p = a->parent; assert(p != 0); // g is p's parent (a's grandparent) group* g = p->parent; assert(g != 0); // a' <- A(r) assert(A[r] != 0); group* ap = A[r]; assert(ap != 0); // A(r) <- nil A[r] = 0; // let a' have parent p' group* pp = ap->parent; assert(pp != 0); // let a' have grandparent g' group* gp = pp->parent; assert(gp != 0); // Remove a and a' from their parents assert(ap == pp->children[pp->rank - 1]); // Guaranteed because ap is active --pp->rank; // Guaranteed by caller assert(a == p->children[p->rank - 1]); --p->rank; // Note: a, ap, p, pp all have rank r if (do_compare(pp, p)) { do_swap(a, ap); do_swap(p, pp); do_swap(g, gp); } // Assuming k(p) <= k(p') // make p' the rank r child of p assert(r == p->rank); p->children[p->rank++] = pp; pp->parent = p; // Combine a, ap into a rank r+1 group c group* c = combine(a, ap); // make c the rank r+1 child of g' assert(gp->rank > r + 1); gp->children[r + 1] = c; c->parent = gp; #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 std::cerr << "After pair transform...\n"; dump_tree(); #endif if (A[r + 1] == pp) A[r + 1] = c; else promote(c); } void active_sibling_transform(group* a, group* s) { #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 std::cerr << "- active sibling transform\n"; #endif group* p = a->parent; group* g = p->parent; // remove a, s from their parents assert(s->parent == p); assert(p->children[p->rank - 1] == s); --p->rank; assert(p->children[p->rank - 1] == a); --p->rank; rank_type r = a->rank; A[r + 1] = 0; a = combine(p, a); group* c = combine(a, s); // make c the rank r+2 child of g assert(g->children[r + 2] == p); g->children[r + 2] = c; c->parent = g; if (A[r + 2] == p) A[r + 2] = c; else promote(c); } void good_sibling_transform(group* a, group* s) { #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 std::cerr << "- good sibling transform\n"; #endif rank_type r = a->rank; group* c = s->children[s->rank - 1]; assert(c->rank == r); if (A[r] == c) { #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 std::cerr << "- good sibling pair transform\n"; #endif A[r] = 0; group* p = a->parent; // Remove c from its parent --s->rank; // Make s the rank r child of p s->parent = p; p->children[r] = s; // combine a, c and let the result by the rank r+1 child of p assert(p->rank > r + 1); group* x = combine(a, c); x->parent = p; p->children[r + 1] = x; if (A[r + 1] == s) A[r + 1] = x; else promote(x); #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 dump_tree(std::cerr); #endif // pair_transform(a); } else { // Clean operation group* p = a->parent; s->children[r] = a; a->parent = s; p->children[r] = c; c->parent = p; promote(a); } } static void do_swap(group*& x, group*& y) { group* tmp = x; x = y; y = tmp; } /// Function object that compares two values in the heap Compare compare; /// Mapping from values to indices in the range [0, n). ID id; /** The root group of the queue. This group is special because it will * never store a value, but it acts as a parent to all of the * roots. Thus, its list of children is the list of roots. */ group root; /** Mapping from the group index of a value to the group associated * with that value. If a value is not in the queue, then the "value" * field will be empty. */ std::vector< group > index_to_group; /** Flat data structure containing the values in each of the * groups. It will be indexed via the id of the values. The groups * are each log_n long, with the last group potentially being * smaller. */ std::vector< ::boost::optional< value_type > > groups; /** The list of active groups, indexed by rank. When A[r] is null, * there is no active group of rank r. Otherwise, A[r] is the active * group of rank r. */ std::vector< group* > A; /** The group containing the smallest value in the queue, which must * be either a root or an active group. If this group is null, then we * will need to search for this group when it is needed. */ mutable group* smallest_value; /// Cached value log_base_2(n) size_type log_n; }; } // end namespace boost #if defined(BOOST_MSVC) #pragma warning(pop) #endif #endif // BOOST_RELAXED_HEAP_HEADER PK Q�!\o=ۄp6 p6 property.hppnu �[��� // (C) Copyright Jeremy Siek 2004 // 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_PROPERTY_HPP #define BOOST_PROPERTY_HPP #include <boost/mpl/bool.hpp> #include <boost/mpl/if.hpp> #include <boost/mpl/has_xxx.hpp> #include <boost/utility/enable_if.hpp> #include <boost/type_traits.hpp> #include <boost/static_assert.hpp> namespace boost { struct no_property { }; template < class Tag, class T, class Base = no_property > struct property { typedef Base next_type; typedef Tag tag_type; typedef T value_type; property(const T& v = T()) : m_value(v) {} property(const T& v, const Base& b) : m_value(v), m_base(b) {} // copy constructor and assignment operator will be generated by compiler T m_value; Base m_base; }; // Kinds of properties namespace graph_introspect_detail { BOOST_MPL_HAS_XXX_TRAIT_DEF(kind) template < typename T, bool Cond > struct get_kind { typedef void type; }; template < typename T > struct get_kind< T, true > { typedef typename T::kind type; }; } // Having a default is to make this trait work for any type, not just valid // properties, to work around VC++ <= 10 bugs related to SFINAE in // compressed_sparse_row_graph's get functions and similar template < class PropertyTag > struct property_kind : graph_introspect_detail::get_kind< PropertyTag, graph_introspect_detail::has_kind< PropertyTag >::value > { }; // Some standard properties defined independently of Boost.Graph: enum vertex_all_t { vertex_all }; enum edge_all_t { edge_all }; enum graph_all_t { graph_all }; enum vertex_bundle_t { vertex_bundle }; enum edge_bundle_t { edge_bundle }; enum graph_bundle_t { graph_bundle }; // Code to look up one property in a property list: template < typename PList, typename PropName, typename Enable = void > struct lookup_one_property_internal { BOOST_STATIC_CONSTANT(bool, found = false); typedef void type; }; // Special-case properties (vertex_all, edge_all, graph_all) #define BGL_ALL_PROP(tag) \ template < typename T > struct lookup_one_property_internal< T, tag > \ { \ BOOST_STATIC_CONSTANT(bool, found = true); \ typedef T type; \ static T& lookup(T& x, tag) { return x; } \ static const T& lookup(const T& x, tag) { return x; } \ }; \ template < typename Tag, typename T, typename Base > \ struct lookup_one_property_internal< property< Tag, T, Base >, tag > \ { /* Avoid ambiguity */ \ BOOST_STATIC_CONSTANT(bool, found = true); \ typedef property< Tag, T, Base > type; \ static type& lookup(type& x, tag) { return x; } \ static const type& lookup(const type& x, tag) { return x; } \ }; BGL_ALL_PROP(vertex_all_t) BGL_ALL_PROP(edge_all_t) BGL_ALL_PROP(graph_all_t) #undef BGL_ALL_PROP // *_bundled; these need to be macros rather than inheritance to resolve // ambiguities #define BGL_DO_ONE_BUNDLE_TYPE(kind) \ template < typename T > \ struct lookup_one_property_internal< T, BOOST_JOIN(kind, _bundle_t) > \ { \ BOOST_STATIC_CONSTANT(bool, found = true); \ typedef T type; \ static T& lookup(T& x, BOOST_JOIN(kind, _bundle_t)) { return x; } \ static const T& lookup(const T& x, BOOST_JOIN(kind, _bundle_t)) \ { \ return x; \ } \ }; \ \ template < typename Tag, typename T, typename Base > \ struct lookup_one_property_internal< property< Tag, T, Base >, \ BOOST_JOIN(kind, _bundle_t) > \ : lookup_one_property_internal< Base, BOOST_JOIN(kind, _bundle_t) > \ { \ private: \ typedef lookup_one_property_internal< Base, \ BOOST_JOIN(kind, _bundle_t) > \ base_type; \ \ public: \ template < typename BundleTag > \ static typename lazy_enable_if_c< \ (base_type::found \ && (is_same< BundleTag, \ BOOST_JOIN(kind, _bundle_t) >::value)), \ add_reference< typename base_type::type > >::type \ lookup(property< Tag, T, Base >& p, BundleTag) \ { \ return base_type::lookup(p.m_base, BOOST_JOIN(kind, _bundle_t)()); \ } \ template < typename BundleTag > \ static typename lazy_enable_if_c< \ (base_type::found \ && (is_same< BundleTag, \ BOOST_JOIN(kind, _bundle_t) >::value)), \ add_reference< const typename base_type::type > >::type \ lookup(const property< Tag, T, Base >& p, BundleTag) \ { \ return base_type::lookup(p.m_base, BOOST_JOIN(kind, _bundle_t)()); \ } \ }; BGL_DO_ONE_BUNDLE_TYPE(vertex) BGL_DO_ONE_BUNDLE_TYPE(edge) BGL_DO_ONE_BUNDLE_TYPE(graph) #undef BGL_DO_ONE_BUNDLE_TYPE // Normal old-style properties; second case also handles chaining of bundled // property accesses template < typename Tag, typename T, typename Base > struct lookup_one_property_internal< boost::property< Tag, T, Base >, Tag > { BOOST_STATIC_CONSTANT(bool, found = true); typedef property< Tag, T, Base > prop; typedef T type; template < typename U > static typename enable_if< is_same< prop, U >, T& >::type lookup( U& prop, const Tag&) { return prop.m_value; } template < typename U > static typename enable_if< is_same< prop, U >, const T& >::type lookup( const U& prop, const Tag&) { return prop.m_value; } }; template < typename Tag, typename T, typename Base, typename PropName > struct lookup_one_property_internal< boost::property< Tag, T, Base >, PropName > : lookup_one_property_internal< Base, PropName > { private: typedef lookup_one_property_internal< Base, PropName > base_type; public: template < typename PL > static typename lazy_enable_if< is_same< PL, boost::property< Tag, T, Base > >, add_reference< typename base_type::type > >::type lookup(PL& prop, const PropName& tag) { return base_type::lookup(prop.m_base, tag); } template < typename PL > static typename lazy_enable_if< is_same< PL, boost::property< Tag, T, Base > >, add_reference< const typename base_type::type > >::type lookup(const PL& prop, const PropName& tag) { return base_type::lookup(prop.m_base, tag); } }; // Pointer-to-member access to bundled properties #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES template < typename T, typename TMaybeBase, typename R > struct lookup_one_property_internal< T, R TMaybeBase::*, typename enable_if< is_base_of< TMaybeBase, T > >::type > { BOOST_STATIC_CONSTANT(bool, found = true); typedef R type; static R& lookup(T& x, R TMaybeBase::*ptr) { return x.*ptr; } static const R& lookup(const T& x, R TMaybeBase::*ptr) { return x.*ptr; } }; #endif // Version of above handling const property lists properly template < typename T, typename Tag > struct lookup_one_property : lookup_one_property_internal< T, Tag > { }; template < typename T, typename Tag > struct lookup_one_property< const T, Tag > { BOOST_STATIC_CONSTANT( bool, found = (lookup_one_property_internal< T, Tag >::found)); typedef const typename lookup_one_property_internal< T, Tag >::type type; template < typename U > static typename lazy_enable_if< is_same< T, U >, add_reference< const typename lookup_one_property_internal< T, Tag >::type > >::type lookup(const U& p, Tag tag) { return lookup_one_property_internal< T, Tag >::lookup(p, tag); } }; // The BGL properties specialize property_kind and // property_num, and use enum's for the Property type (see // graph/properties.hpp), but the user may want to use a class // instead with a nested kind type and num. Also, we may want to // switch BGL back to using class types for properties at some point. template < class P > struct has_property : boost::mpl::true_ { }; template <> struct has_property< no_property > : boost::mpl::false_ { }; } // namespace boost #include <boost/pending/detail/property.hpp> namespace boost { template < class PropertyList, class Tag > struct property_value : lookup_one_property< PropertyList, Tag > { }; template < class PropertyList, class Tag > inline typename lookup_one_property< PropertyList, Tag >::type& get_property_value(PropertyList& p, Tag tag) { return lookup_one_property< PropertyList, Tag >::lookup(p, tag); } template < class PropertyList, class Tag > inline const typename lookup_one_property< PropertyList, Tag >::type& get_property_value(const PropertyList& p, Tag tag) { return lookup_one_property< PropertyList, Tag >::lookup(p, tag); } namespace detail { /** This trait returns true if T is no_property. */ template < typename T > struct is_no_property : mpl::bool_< is_same< T, no_property >::value > { }; template < typename PList, typename Tag > class lookup_one_property_f; template < typename PList, typename Tag, typename F > struct lookup_one_property_f_result; template < typename PList, typename Tag > struct lookup_one_property_f_result< PList, Tag, const lookup_one_property_f< PList, Tag >(PList) > { typedef typename lookup_one_property< PList, Tag >::type type; }; template < typename PList, typename Tag > struct lookup_one_property_f_result< PList, Tag, const lookup_one_property_f< PList, Tag >(PList&) > { typedef typename lookup_one_property< PList, Tag >::type& type; }; template < typename PList, typename Tag > struct lookup_one_property_f_result< PList, Tag, const lookup_one_property_f< PList, Tag >(const PList&) > { typedef const typename lookup_one_property< PList, Tag >::type& type; }; template < typename PList, typename Tag > class lookup_one_property_f { Tag tag; public: lookup_one_property_f(Tag tag) : tag(tag) {} template < typename F > struct result : lookup_one_property_f_result< PList, Tag, F > { }; typename lookup_one_property_f_result< PList, Tag, const lookup_one_property_f(PList&) >::type operator()(PList& pl) const { return lookup_one_property< PList, Tag >::lookup(pl, tag); } }; } // namespace detail namespace detail { // Stuff for directed_graph and undirected_graph to skip over their first // vertex_index and edge_index properties when providing vertex_all and // edge_all; make sure you know the exact structure of your properties if // you use there. struct remove_first_property { template < typename F > struct result { typedef typename boost::function_traits< F >::arg1_type a1; typedef typename boost::remove_reference< a1 >::type non_ref; typedef typename non_ref::next_type nx; typedef typename boost::mpl::if_< boost::is_const< non_ref >, boost::add_const< nx >, nx >::type with_const; typedef typename boost::add_reference< with_const >::type type; }; template < typename Prop > typename Prop::next_type& operator()(Prop& p) const { return p.m_base; } template < typename Prop > const typename Prop::next_type& operator()(const Prop& p) const { return p.m_base; } }; } } // namesapce boost #endif /* BOOST_PROPERTY_HPP */ PK Q�!\�߶Hs s disjoint_sets.hppnu �[��� // //======================================================================= // 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 PK Q�!\;�_�� � mutable_heap.hppnu �[��� // //======================================================================= // 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_GRAPH_DETAIL_MUTABLE_HEAP_H #define BOOST_GRAPH_DETAIL_MUTABLE_HEAP_H /* There are a few things wrong with this set of functions. ExternalData should be removed, it is not part of the core algorithm. It can be handled inside the tree nodes. The swap() should be replaced by assignment since its use is causing the number of memory references to double. The min_element should be replaced by a fixed length loop (fixed at d for d-heaps). The member functions of TreeNode should be changed to global functions. These functions will be replaced by those in heap_tree.h */ namespace boost { template < class TreeNode, class Compare, class ExternalData > inline TreeNode up_heap(TreeNode x, const Compare& comp, ExternalData& edata) { while (x.has_parent() && comp(x, x.parent())) x.swap(x.parent(), edata); return x; } template < class TreeNode, class Compare, class ExternalData > inline TreeNode down_heap(TreeNode x, const Compare& comp, ExternalData& edata) { while (x.children().size() > 0) { typename TreeNode::children_type::iterator child_iter = std::min_element(x.children().begin(), x.children().end(), comp); if (comp(*child_iter, x)) x.swap(*child_iter, edata); else break; } return x; } template < class TreeNode, class Compare, class ExternalData > inline void update_heap(TreeNode x, const Compare& comp, ExternalData& edata) { x = down_heap(x, comp, edata); (void)up_heap(x, comp, edata); } } #endif PK Q�!\3�y y bucket_sorter.hppnu �[��� // //======================================================================= // 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) //======================================================================= // // // Revision History: // 13 June 2001: Changed some names for clarity. (Jeremy Siek) // 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock) // #ifndef BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP #define BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP #include <vector> #include <cassert> #include <boost/limits.hpp> #include <boost/concept/assert.hpp> #include <boost/property_map/property_map.hpp> namespace boost { template < class BucketType, class ValueType, class Bucket, class ValueIndexMap > class bucket_sorter { BOOST_CONCEPT_ASSERT( (ReadablePropertyMapConcept< ValueIndexMap, ValueType >)); public: typedef BucketType bucket_type; typedef ValueType value_type; typedef typename std::vector< value_type >::size_type size_type; bucket_sorter(size_type _length, bucket_type _max_bucket, const Bucket& _bucket = Bucket(), const ValueIndexMap& _id = ValueIndexMap()) : head(_max_bucket, invalid_value()) , next(_length, invalid_value()) , prev(_length, invalid_value()) , id_to_value(_length) , bucket(_bucket) , id(_id) { } void remove(const value_type& x) { const size_type i = get(id, x); const size_type& next_node = next[i]; const size_type& prev_node = prev[i]; // check if i is the end of the bucket list if (next_node != invalid_value()) prev[next_node] = prev_node; // check if i is the begin of the bucket list if (prev_node != invalid_value()) next[prev_node] = next_node; else // need update head of current bucket list head[bucket[x]] = next_node; } void push(const value_type& x) { id_to_value[get(id, x)] = x; (*this)[bucket[x]].push(x); } void update(const value_type& x) { remove(x); (*this)[bucket[x]].push(x); } // private: // with KCC, the nested stack class is having access problems // despite the friend decl. static size_type invalid_value() { return (std::numeric_limits< size_type >::max)(); } typedef typename std::vector< size_type >::iterator Iter; typedef typename std::vector< value_type >::iterator IndexValueMap; public: friend class stack; class stack { public: stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v, const ValueIndexMap& _id) : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v), id(_id) { } // Avoid using default arg for ValueIndexMap so that the default // constructor of the ValueIndexMap is not required if not used. stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v) : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v) { } void push(const value_type& x) { const size_type new_head = get(id, x); const size_type current = head[bucket_id]; if (current != invalid_value()) prev[current] = new_head; prev[new_head] = invalid_value(); next[new_head] = current; head[bucket_id] = new_head; } void pop() { size_type current = head[bucket_id]; size_type next_node = next[current]; head[bucket_id] = next_node; if (next_node != invalid_value()) prev[next_node] = invalid_value(); } value_type& top() { return value[head[bucket_id]]; } const value_type& top() const { return value[head[bucket_id]]; } bool empty() const { return head[bucket_id] == invalid_value(); } private: bucket_type bucket_id; Iter head; Iter next; Iter prev; IndexValueMap value; ValueIndexMap id; }; stack operator[](const bucket_type& i) { assert(i < head.size()); return stack(i, head.begin(), next.begin(), prev.begin(), id_to_value.begin(), id); } protected: std::vector< size_type > head; std::vector< size_type > next; std::vector< size_type > prev; std::vector< value_type > id_to_value; Bucket bucket; ValueIndexMap id; }; } #endif PK Q�!\���R� � indirect_cmp.hppnu �[��� // //======================================================================= // 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_INDIRECT_CMP_HPP #define BOOST_INDIRECT_CMP_HPP #include <functional> #include <boost/config.hpp> #include <boost/property_map/property_map.hpp> namespace boost { //: indirect_cmp // // could also do this with compose_f_gx_hx, and the member binder... // //! category: functors //! component: type //! tparam: ReadablePropertyMap - a model of ReadablePropertyMap //! definition: functor.h template < class ReadablePropertyMap, class Compare > class indirect_cmp { public: typedef typename boost::property_traits< ReadablePropertyMap >::value_type T; typedef typename boost::property_traits< ReadablePropertyMap >::key_type K; typedef K first_argument_type; typedef K second_argument_type; typedef bool result_type; inline indirect_cmp( const ReadablePropertyMap& df, const Compare& c = Compare()) : d(df), cmp(c) { } template < class A, class B > inline bool operator()(const A& u, const B& v) const { const T& du = get(d, u); const T& dv = get(d, v); return cmp(du, dv); } protected: ReadablePropertyMap d; Compare cmp; }; template < typename Compare, typename ReadablePropertyMap > indirect_cmp< ReadablePropertyMap, Compare > make_indirect_cmp( const Compare& cmp, ReadablePropertyMap pmap) { indirect_cmp< ReadablePropertyMap, Compare > p(pmap, cmp); return p; } template < class ReadablePropertyMap > class indirect_pmap { public: typedef typename boost::property_traits< ReadablePropertyMap >::value_type T; typedef typename boost::property_traits< ReadablePropertyMap >::key_type K; typedef K argument_type; typedef T result_type; inline indirect_pmap(const ReadablePropertyMap& df) : d(df) {} inline T operator()(const K& u) const { return get(d, u); } protected: ReadablePropertyMap d; }; template < typename ReadablePropertyMap > indirect_pmap< ReadablePropertyMap > make_indirect_pmap( ReadablePropertyMap pmap) { indirect_pmap< ReadablePropertyMap > f(pmap); return f; } } // namespace boost #endif // GGCL_INDIRECT_CMP_HPP PK Q�!\�l��T �T container_traits.hppnu �[��� // (C) Copyright Jeremy Siek 2004 // (C) Copyright Thomas Claveirole 2010 // (C) Copyright Ignacy Gawedzki 2010 // 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_GRAPH_DETAIL_CONTAINER_TRAITS_H #define BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H // Sure would be nice to be able to forward declare these // instead of pulling in all the headers. Too bad that // is not legal. There ought to be a standard <stlfwd> header. -JGS #include <boost/next_prior.hpp> #include <algorithm> // for std::remove #include <utility> #include <vector> #include <list> #include <map> #include <set> #include <boost/unordered_set.hpp> #include <boost/unordered_map.hpp> #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET #include <unordered_set> #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP #include <unordered_map> #endif #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES #define BOOST_PENDING_FWD_TYPE(type) const type& #define BOOST_PENDING_FWD_VALUE(type, var) (var) #else #define BOOST_PENDING_FWD_TYPE(type) type&& #define BOOST_PENDING_FWD_VALUE(type, var) (std::forward< type >((var))) #endif // The content of this file is in 'graph_detail' because otherwise // there will be name clashes with // sandbox/boost/sequence_algo/container_traits.hpp // The 'detail' subnamespace will still cause problems. namespace boost { namespace graph_detail { //====================================================================== // Container Category Tags // // They use virtual inheritance because there are lots of // inheritance diamonds. struct container_tag { }; struct forward_container_tag : virtual public container_tag { }; struct reversible_container_tag : virtual public forward_container_tag { }; struct random_access_container_tag : virtual public reversible_container_tag { }; struct sequence_tag : virtual public forward_container_tag { }; struct associative_container_tag : virtual public forward_container_tag { }; struct sorted_associative_container_tag : virtual public associative_container_tag, virtual public reversible_container_tag { }; struct front_insertion_sequence_tag : virtual public sequence_tag { }; struct back_insertion_sequence_tag : virtual public sequence_tag { }; struct unique_associative_container_tag : virtual public associative_container_tag { }; struct multiple_associative_container_tag : virtual public associative_container_tag { }; struct simple_associative_container_tag : virtual public associative_container_tag { }; struct pair_associative_container_tag : virtual public associative_container_tag { }; //====================================================================== // Iterator Stability Tags // // Do mutating operations such as insert/erase/resize invalidate all // outstanding iterators? struct stable_tag { }; struct unstable_tag { }; //====================================================================== // Container Traits Class and container_category() function // don't use this unless there is partial specialization template < class Container > struct container_traits { typedef typename Container::category category; typedef typename Container::iterator_stability iterator_stability; }; // Use this as a compile-time assertion that X is stable inline void require_stable(stable_tag) {} // std::vector struct vector_tag : virtual public random_access_container_tag, virtual public back_insertion_sequence_tag { }; template < class T, class Alloc > vector_tag container_category(const std::vector< T, Alloc >&) { return vector_tag(); } template < class T, class Alloc > unstable_tag iterator_stability(const std::vector< T, Alloc >&) { return unstable_tag(); } template < class T, class Alloc > struct container_traits< std::vector< T, Alloc > > { typedef vector_tag category; typedef unstable_tag iterator_stability; }; // std::list struct list_tag : virtual public reversible_container_tag, virtual public back_insertion_sequence_tag // this causes problems for push_dispatch... // virtual public front_insertion_sequence_tag { }; template < class T, class Alloc > list_tag container_category(const std::list< T, Alloc >&) { return list_tag(); } template < class T, class Alloc > stable_tag iterator_stability(const std::list< T, Alloc >&) { return stable_tag(); } template < class T, class Alloc > struct container_traits< std::list< T, Alloc > > { typedef list_tag category; typedef stable_tag iterator_stability; }; // std::set struct set_tag : virtual public sorted_associative_container_tag, virtual public simple_associative_container_tag, virtual public unique_associative_container_tag { }; template < class Key, class Cmp, class Alloc > set_tag container_category(const std::set< Key, Cmp, Alloc >&) { return set_tag(); } template < class Key, class Cmp, class Alloc > stable_tag iterator_stability(const std::set< Key, Cmp, Alloc >&) { return stable_tag(); } template < class Key, class Cmp, class Alloc > struct container_traits< std::set< Key, Cmp, Alloc > > { typedef set_tag category; typedef stable_tag iterator_stability; }; // std::multiset struct multiset_tag : virtual public sorted_associative_container_tag, virtual public simple_associative_container_tag, virtual public multiple_associative_container_tag { }; template < class Key, class Cmp, class Alloc > multiset_tag container_category(const std::multiset< Key, Cmp, Alloc >&) { return multiset_tag(); } template < class Key, class Cmp, class Alloc > stable_tag iterator_stability(const std::multiset< Key, Cmp, Alloc >&) { return stable_tag(); } template < class Key, class Cmp, class Alloc > struct container_traits< std::multiset< Key, Cmp, Alloc > > { typedef multiset_tag category; typedef stable_tag iterator_stability; }; // deque // std::map struct map_tag : virtual public sorted_associative_container_tag, virtual public pair_associative_container_tag, virtual public unique_associative_container_tag { }; template < class Key, class T, class Cmp, class Alloc > struct container_traits< std::map< Key, T, Cmp, Alloc > > { typedef map_tag category; typedef stable_tag iterator_stability; }; template < class Key, class T, class Cmp, class Alloc > map_tag container_category(const std::map< Key, T, Cmp, Alloc >&) { return map_tag(); } template < class Key, class T, class Cmp, class Alloc > stable_tag iterator_stability(const std::map< Key, T, Cmp, Alloc >&) { return stable_tag(); } // std::multimap struct multimap_tag : virtual public sorted_associative_container_tag, virtual public pair_associative_container_tag, virtual public multiple_associative_container_tag { }; template < class Key, class T, class Cmp, class Alloc > struct container_traits< std::multimap< Key, T, Cmp, Alloc > > { typedef multimap_tag category; typedef stable_tag iterator_stability; }; template < class Key, class T, class Cmp, class Alloc > multimap_tag container_category(const std::multimap< Key, T, Cmp, Alloc >&) { return multimap_tag(); } template < class Key, class T, class Cmp, class Alloc > stable_tag iterator_stability(const std::multimap< Key, T, Cmp, Alloc >&) { return stable_tag(); } // hash_set, hash_map struct unordered_set_tag : virtual public simple_associative_container_tag, virtual public unique_associative_container_tag { }; struct unordered_multiset_tag : virtual public simple_associative_container_tag, virtual public multiple_associative_container_tag { }; struct unordered_map_tag : virtual public pair_associative_container_tag, virtual public unique_associative_container_tag { }; struct unordered_multimap_tag : virtual public pair_associative_container_tag, virtual public multiple_associative_container_tag { }; template < class Key, class Eq, class Hash, class Alloc > struct container_traits< boost::unordered_set< Key, Eq, Hash, Alloc > > { typedef unordered_set_tag category; typedef unstable_tag iterator_stability; }; template < class Key, class T, class Eq, class Hash, class Alloc > struct container_traits< boost::unordered_map< Key, T, Eq, Hash, Alloc > > { typedef unordered_map_tag category; typedef unstable_tag iterator_stability; }; template < class Key, class Eq, class Hash, class Alloc > struct container_traits< boost::unordered_multiset< Key, Eq, Hash, Alloc > > { typedef unordered_multiset_tag category; typedef unstable_tag iterator_stability; }; template < class Key, class T, class Eq, class Hash, class Alloc > struct container_traits< boost::unordered_multimap< Key, T, Eq, Hash, Alloc > > { typedef unordered_multimap_tag category; typedef unstable_tag iterator_stability; }; template < class Key, class Eq, class Hash, class Alloc > unordered_set_tag container_category( const boost::unordered_set< Key, Eq, Hash, Alloc >&) { return unordered_set_tag(); } template < class Key, class T, class Eq, class Hash, class Alloc > unordered_map_tag container_category( const boost::unordered_map< Key, T, Eq, Hash, Alloc >&) { return unordered_map_tag(); } template < class Key, class Eq, class Hash, class Alloc > unstable_tag iterator_stability( const boost::unordered_set< Key, Eq, Hash, Alloc >&) { return unstable_tag(); } template < class Key, class T, class Eq, class Hash, class Alloc > unstable_tag iterator_stability( const boost::unordered_map< Key, T, Eq, Hash, Alloc >&) { return unstable_tag(); } template < class Key, class Eq, class Hash, class Alloc > unordered_multiset_tag container_category( const boost::unordered_multiset< Key, Eq, Hash, Alloc >&) { return unordered_multiset_tag(); } template < class Key, class T, class Eq, class Hash, class Alloc > unordered_multimap_tag container_category( const boost::unordered_multimap< Key, T, Eq, Hash, Alloc >&) { return unordered_multimap_tag(); } template < class Key, class Eq, class Hash, class Alloc > unstable_tag iterator_stability( const boost::unordered_multiset< Key, Eq, Hash, Alloc >&) { return unstable_tag(); } template < class Key, class T, class Eq, class Hash, class Alloc > unstable_tag iterator_stability( const boost::unordered_multimap< Key, T, Eq, Hash, Alloc >&) { return unstable_tag(); } #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET template < class Key, class Eq, class Hash, class Alloc > struct container_traits< std::unordered_set< Key, Eq, Hash, Alloc > > { typedef unordered_set_tag category; typedef unstable_tag iterator_stability; }; #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP template < class Key, class T, class Eq, class Hash, class Alloc > struct container_traits< std::unordered_map< Key, T, Eq, Hash, Alloc > > { typedef unordered_map_tag category; typedef unstable_tag iterator_stability; }; #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET template < class Key, class Eq, class Hash, class Alloc > struct container_traits< std::unordered_multiset< Key, Eq, Hash, Alloc > > { typedef unordered_multiset_tag category; typedef unstable_tag iterator_stability; }; #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP template < class Key, class T, class Eq, class Hash, class Alloc > struct container_traits< std::unordered_multimap< Key, T, Eq, Hash, Alloc > > { typedef unordered_multimap_tag category; typedef unstable_tag iterator_stability; }; #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET template < class Key, class Eq, class Hash, class Alloc > unordered_set_tag container_category( const std::unordered_set< Key, Eq, Hash, Alloc >&) { return unordered_set_tag(); } #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP template < class Key, class T, class Eq, class Hash, class Alloc > unordered_map_tag container_category( const std::unordered_map< Key, T, Eq, Hash, Alloc >&) { return unordered_map_tag(); } #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET template < class Key, class Eq, class Hash, class Alloc > unstable_tag iterator_stability( const std::unordered_set< Key, Eq, Hash, Alloc >&) { return unstable_tag(); } #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP template < class Key, class T, class Eq, class Hash, class Alloc > unstable_tag iterator_stability( const std::unordered_map< Key, T, Eq, Hash, Alloc >&) { return unstable_tag(); } #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET template < class Key, class Eq, class Hash, class Alloc > unordered_multiset_tag container_category( const std::unordered_multiset< Key, Eq, Hash, Alloc >&) { return unordered_multiset_tag(); } #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP template < class Key, class T, class Eq, class Hash, class Alloc > unordered_multimap_tag container_category( const std::unordered_multimap< Key, T, Eq, Hash, Alloc >&) { return unordered_multimap_tag(); } #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET template < class Key, class Eq, class Hash, class Alloc > unstable_tag iterator_stability( const std::unordered_multiset< Key, Eq, Hash, Alloc >&) { return unstable_tag(); } #endif #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP template < class Key, class T, class Eq, class Hash, class Alloc > unstable_tag iterator_stability( const std::unordered_multimap< Key, T, Eq, Hash, Alloc >&) { return unstable_tag(); } #endif //=========================================================================== // Generalized Container Functions // Erase template < class Sequence, class T > void erase_dispatch(Sequence& c, const T& x, sequence_tag) { c.erase(std::remove(c.begin(), c.end(), x), c.end()); } template < class AssociativeContainer, class T > void erase_dispatch( AssociativeContainer& c, const T& x, associative_container_tag) { c.erase(x); } template < class Container, class T > void erase(Container& c, const T& x) { erase_dispatch(c, x, container_category(c)); } // Erase If template < class Sequence, class Predicate, class IteratorStability > void erase_if_dispatch( Sequence& c, Predicate p, sequence_tag, IteratorStability) { #if 0 c.erase(std::remove_if(c.begin(), c.end(), p), c.end()); #else if (!c.empty()) c.erase(std::remove_if(c.begin(), c.end(), p), c.end()); #endif } template < class AssociativeContainer, class Predicate > void erase_if_dispatch(AssociativeContainer& c, Predicate p, associative_container_tag, stable_tag) { typename AssociativeContainer::iterator i, next; for (i = next = c.begin(); next != c.end(); i = next) { ++next; if (p(*i)) c.erase(i); } } template < class AssociativeContainer, class Predicate > void erase_if_dispatch(AssociativeContainer& c, Predicate p, associative_container_tag, unstable_tag) { // This method is really slow, so hopefully we won't have any // associative containers with unstable iterators! // Is there a better way to do this? typename AssociativeContainer::iterator i; typename AssociativeContainer::size_type n = c.size(); while (n--) for (i = c.begin(); i != c.end(); ++i) if (p(*i)) { c.erase(i); break; } } template < class Container, class Predicate > void erase_if(Container& c, Predicate p) { erase_if_dispatch(c, p, container_category(c), iterator_stability(c)); } // Push template < class Container, class T > std::pair< typename Container::iterator, bool > push_dispatch( Container& c, BOOST_PENDING_FWD_TYPE(T) v, back_insertion_sequence_tag) { c.push_back(BOOST_PENDING_FWD_VALUE(T, v)); return std::make_pair(boost::prior(c.end()), true); } template < class Container, class T > std::pair< typename Container::iterator, bool > push_dispatch( Container& c, BOOST_PENDING_FWD_TYPE(T) v, front_insertion_sequence_tag) { c.push_front(BOOST_PENDING_FWD_VALUE(T, v)); return std::make_pair(c.begin(), true); } template < class AssociativeContainer, class T > std::pair< typename AssociativeContainer::iterator, bool > push_dispatch( AssociativeContainer& c, BOOST_PENDING_FWD_TYPE(T) v, unique_associative_container_tag) { return c.insert(BOOST_PENDING_FWD_VALUE(T, v)); } template < class AssociativeContainer, class T > std::pair< typename AssociativeContainer::iterator, bool > push_dispatch( AssociativeContainer& c, BOOST_PENDING_FWD_TYPE(T) v, multiple_associative_container_tag) { return std::make_pair(c.insert(BOOST_PENDING_FWD_VALUE(T, v)), true); } template < class Container, class T > std::pair< typename Container::iterator, bool > push( Container& c, BOOST_PENDING_FWD_TYPE(T) v) { return push_dispatch( c, BOOST_PENDING_FWD_VALUE(T, v), container_category(c)); } // Find template < class Container, class Value > typename Container::iterator find_dispatch( Container& c, const Value& value, container_tag) { return std::find(c.begin(), c.end(), value); } template < class AssociativeContainer, class Value > typename AssociativeContainer::iterator find_dispatch( AssociativeContainer& c, const Value& value, associative_container_tag) { return c.find(value); } template < class Container, class Value > typename Container::iterator find(Container& c, const Value& value) { return find_dispatch(c, value, graph_detail::container_category(c)); } // Find (const versions) template < class Container, class Value > typename Container::const_iterator find_dispatch( const Container& c, const Value& value, container_tag) { return std::find(c.begin(), c.end(), value); } template < class AssociativeContainer, class Value > typename AssociativeContainer::const_iterator find_dispatch( const AssociativeContainer& c, const Value& value, associative_container_tag) { return c.find(value); } template < class Container, class Value > typename Container::const_iterator find( const Container& c, const Value& value) { return find_dispatch(c, value, graph_detail::container_category(c)); } // Equal range #if 0 // Make the dispatch fail if c is not an Associative Container (and thus // doesn't have equal_range unless it is sorted, which we cannot check // statically and is not typically true for BGL's uses of this function). template <class Container, class LessThanComparable> std::pair<typename Container::iterator, typename Container::iterator> equal_range_dispatch(Container& c, const LessThanComparable& value, container_tag) { // c must be sorted for std::equal_range to behave properly. return std::equal_range(c.begin(), c.end(), value); } #endif template < class AssociativeContainer, class Value > std::pair< typename AssociativeContainer::iterator, typename AssociativeContainer::iterator > equal_range_dispatch( AssociativeContainer& c, const Value& value, associative_container_tag) { return c.equal_range(value); } template < class Container, class Value > std::pair< typename Container::iterator, typename Container::iterator > equal_range(Container& c, const Value& value) { return equal_range_dispatch( c, value, graph_detail::container_category(c)); } } } // namespace boost::graph_detail #undef BOOST_PENDING_FWD_TYPE #undef BOOST_PENDING_FWD_VALUE #endif // BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H PK Q�!\�=g� � integer_log2.hppnu �[��� #ifndef BOOST_PENDING_INTEGER_LOG2_HPP #define BOOST_PENDING_INTEGER_LOG2_HPP #include <boost/integer/integer_log2.hpp> #include <boost/config/header_deprecated.hpp> BOOST_HEADER_DEPRECATED("<boost/integer/integer_log2.hpp>"); #endif PK Q�!\F�PmT T queue.hppnu �[��� // (C) Copyright Jeremy Siek 2004 // 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_QUEUE_HPP #define BOOST_QUEUE_HPP #include <deque> #include <algorithm> namespace boost { template < class _Tp, class _Sequence = std::deque< _Tp > > class queue; template < class _Tp, class _Seq > inline bool operator==(const queue< _Tp, _Seq >&, const queue< _Tp, _Seq >&); template < class _Tp, class _Seq > inline bool operator<(const queue< _Tp, _Seq >&, const queue< _Tp, _Seq >&); template < class _Tp, class _Sequence > class queue { #ifndef BOOST_NO_MEMBER_TEMPLATE_FRIENDS template < class _Tp1, class _Seq1 > friend bool operator==( const queue< _Tp1, _Seq1 >&, const queue< _Tp1, _Seq1 >&); template < class _Tp1, class _Seq1 > friend bool operator<( const queue< _Tp1, _Seq1 >&, const queue< _Tp1, _Seq1 >&); #endif public: typedef typename _Sequence::value_type value_type; typedef typename _Sequence::size_type size_type; typedef _Sequence container_type; typedef typename _Sequence::reference reference; typedef typename _Sequence::const_reference const_reference; #ifndef BOOST_NO_MEMBER_TEMPLATE_FRIENDS protected: #endif _Sequence c; public: queue() : c() {} explicit queue(const _Sequence& __c) : c(__c) {} bool empty() const { return c.empty(); } size_type size() const { return c.size(); } reference front() { return c.front(); } const_reference front() const { return c.front(); } reference top() { return c.front(); } const_reference top() const { return c.front(); } reference back() { return c.back(); } const_reference back() const { return c.back(); } void push(const value_type& __x) { c.push_back(__x); } void pop() { c.pop_front(); } void swap(queue& other) { using std::swap; swap(c, other.c); } }; template < class _Tp, class _Sequence > bool operator==( const queue< _Tp, _Sequence >& __x, const queue< _Tp, _Sequence >& __y) { return __x.c == __y.c; } template < class _Tp, class _Sequence > bool operator<( const queue< _Tp, _Sequence >& __x, const queue< _Tp, _Sequence >& __y) { return __x.c < __y.c; } template < class _Tp, class _Sequence > bool operator!=( const queue< _Tp, _Sequence >& __x, const queue< _Tp, _Sequence >& __y) { return !(__x == __y); } template < class _Tp, class _Sequence > bool operator>( const queue< _Tp, _Sequence >& __x, const queue< _Tp, _Sequence >& __y) { return __y < __x; } template < class _Tp, class _Sequence > bool operator<=( const queue< _Tp, _Sequence >& __x, const queue< _Tp, _Sequence >& __y) { return !(__y < __x); } template < class _Tp, class _Sequence > bool operator>=( const queue< _Tp, _Sequence >& __x, const queue< _Tp, _Sequence >& __y) { return !(__x < __y); } template < class _Tp, class _Sequence > inline void swap(queue< _Tp, _Sequence >& __x, queue< _Tp, _Sequence >& __y) { __x.swap(__y); } } /* namespace boost */ #endif /* BOOST_QUEUE_HPP */ PK Q�!\,:�k� � iterator_tests.hppnu �[��� // Copyright David Abrahams and Jeremy Siek 2003. // 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_ITERATOR_TESTS_HPP # define BOOST_ITERATOR_TESTS_HPP // This is meant to be the beginnings of a comprehensive, generic // test suite for STL concepts such as iterators and containers. // // Revision History: // 28 Apr 2002 Fixed input iterator requirements. // For a == b a++ == b++ is no longer required. // See 24.1.1/3 for details. // (Thomas Witt) // 08 Feb 2001 Fixed bidirectional iterator test so that // --i is no longer a precondition. // (Jeremy Siek) // 04 Feb 2001 Added lvalue test, corrected preconditions // (David Abrahams) # include <iterator> # include <boost/static_assert.hpp> # include <boost/concept_archetype.hpp> // for detail::dummy_constructor # include <boost/implicit_cast.hpp> # include <boost/core/ignore_unused.hpp> # include <boost/core/lightweight_test.hpp> # include <boost/type_traits/is_same.hpp> # include <boost/type_traits/is_pointer.hpp> # include <boost/type_traits/is_reference.hpp> namespace boost { // use this for the value type struct dummyT { dummyT() { } dummyT(detail::dummy_constructor) { } dummyT(int x) : m_x(x) { } int foo() const { return m_x; } bool operator==(const dummyT& d) const { return m_x == d.m_x; } int m_x; }; } namespace boost { namespace iterators { // Tests whether type Iterator satisfies the requirements for a // TrivialIterator. // Preconditions: i != j, *i == val template <class Iterator, class T> void trivial_iterator_test(const Iterator i, const Iterator j, T val) { Iterator k; BOOST_TEST(i == i); BOOST_TEST(j == j); BOOST_TEST(i != j); #ifdef BOOST_NO_STD_ITERATOR_TRAITS T v = *i; #else typename std::iterator_traits<Iterator>::value_type v = *i; #endif BOOST_TEST(v == val); boost::ignore_unused(v); #if 0 // hmm, this will give a warning for transform_iterator... perhaps // this should be separated out into a stand-alone test since there // are several situations where it can't be used, like for // integer_range::iterator. BOOST_TEST(v == i->foo()); #endif k = i; BOOST_TEST(k == k); BOOST_TEST(k == i); BOOST_TEST(k != j); BOOST_TEST(*k == val); boost::ignore_unused(k); } // Preconditions: i != j template <class Iterator, class T> void mutable_trivial_iterator_test(const Iterator i, const Iterator j, T val) { *i = val; trivial_iterator_test(i, j, val); } // Preconditions: *i == v1, *++i == v2 template <class Iterator, class T> void input_iterator_test(Iterator i, T v1, T v2) { Iterator i1(i); BOOST_TEST(i == i1); BOOST_TEST(!(i != i1)); // I can see no generic way to create an input iterator // that is in the domain of== of i and != i. // The following works for istream_iterator but is not // guaranteed to work for arbitrary input iterators. // // Iterator i2; // // BOOST_TEST(i != i2); // BOOST_TEST(!(i == i2)); BOOST_TEST(*i1 == v1); BOOST_TEST(*i == v1); // we cannot test for equivalence of (void)++i & (void)i++ // as i is only guaranteed to be single pass. BOOST_TEST(*i++ == v1); boost::ignore_unused(i1); i1 = i; BOOST_TEST(i == i1); BOOST_TEST(!(i != i1)); BOOST_TEST(*i1 == v2); BOOST_TEST(*i == v2); boost::ignore_unused(i1); // i is dereferencable, so it must be incrementable. ++i; // how to test for operator-> ? } // how to test output iterator? template <bool is_pointer> struct lvalue_test { template <class Iterator> static void check(Iterator) { # ifndef BOOST_NO_STD_ITERATOR_TRAITS typedef typename std::iterator_traits<Iterator>::reference reference; typedef typename std::iterator_traits<Iterator>::value_type value_type; # else typedef typename Iterator::reference reference; typedef typename Iterator::value_type value_type; # endif BOOST_STATIC_ASSERT(boost::is_reference<reference>::value); BOOST_STATIC_ASSERT((boost::is_same<reference,value_type&>::value || boost::is_same<reference,const value_type&>::value )); } }; # ifdef BOOST_NO_STD_ITERATOR_TRAITS template <> struct lvalue_test<true> { template <class T> static void check(T) {} }; #endif template <class Iterator, class T> void forward_iterator_test(Iterator i, T v1, T v2) { input_iterator_test(i, v1, v2); Iterator i1 = i, i2 = i; BOOST_TEST(i == i1++); BOOST_TEST(i != ++i2); trivial_iterator_test(i, i1, v1); trivial_iterator_test(i, i2, v1); ++i; BOOST_TEST(i == i1); BOOST_TEST(i == i2); ++i1; ++i2; trivial_iterator_test(i, i1, v2); trivial_iterator_test(i, i2, v2); // borland doesn't allow non-type template parameters # if !defined(BOOST_BORLANDC) || (BOOST_BORLANDC > 0x551) lvalue_test<(boost::is_pointer<Iterator>::value)>::check(i); #endif } // Preconditions: *i == v1, *++i == v2 template <class Iterator, class T> void bidirectional_iterator_test(Iterator i, T v1, T v2) { forward_iterator_test(i, v1, v2); ++i; Iterator i1 = i, i2 = i; BOOST_TEST(i == i1--); BOOST_TEST(i != --i2); trivial_iterator_test(i, i1, v2); trivial_iterator_test(i, i2, v2); --i; BOOST_TEST(i == i1); BOOST_TEST(i == i2); ++i1; ++i2; trivial_iterator_test(i, i1, v1); trivial_iterator_test(i, i2, v1); } // mutable_bidirectional_iterator_test template <class U> struct undefined; // Preconditions: [i,i+N) is a valid range template <class Iterator, class TrueVals> void random_access_iterator_test(Iterator i, int N, TrueVals vals) { bidirectional_iterator_test(i, vals[0], vals[1]); const Iterator j = i; int c; typedef typename std::iterator_traits<Iterator>::value_type value_type; boost::ignore_unused<value_type>(); for (c = 0; c < N-1; ++c) { BOOST_TEST(i == j + c); BOOST_TEST(*i == vals[c]); BOOST_TEST(*i == boost::implicit_cast<value_type>(j[c])); BOOST_TEST(*i == *(j + c)); BOOST_TEST(*i == *(c + j)); ++i; BOOST_TEST(i > j); BOOST_TEST(i >= j); BOOST_TEST(j <= i); BOOST_TEST(j < i); } Iterator k = j + N - 1; for (c = 0; c < N-1; ++c) { BOOST_TEST(i == k - c); BOOST_TEST(*i == vals[N - 1 - c]); BOOST_TEST(*i == boost::implicit_cast<value_type>(j[N - 1 - c])); Iterator q = k - c; boost::ignore_unused(q); BOOST_TEST(*i == *q); BOOST_TEST(i > j); BOOST_TEST(i >= j); BOOST_TEST(j <= i); BOOST_TEST(j < i); --i; } } // Precondition: i != j template <class Iterator, class ConstIterator> void const_nonconst_iterator_test(Iterator i, ConstIterator j) { BOOST_TEST(i != j); BOOST_TEST(j != i); ConstIterator k(i); BOOST_TEST(k == i); BOOST_TEST(i == k); k = i; BOOST_TEST(k == i); BOOST_TEST(i == k); boost::ignore_unused(k); } } // namespace iterators using iterators::undefined; using iterators::trivial_iterator_test; using iterators::mutable_trivial_iterator_test; using iterators::input_iterator_test; using iterators::lvalue_test; using iterators::forward_iterator_test; using iterators::bidirectional_iterator_test; using iterators::random_access_iterator_test; using iterators::const_nonconst_iterator_test; } // namespace boost #endif // BOOST_ITERATOR_TESTS_HPP PK Q�!\�ԮFD D fenced_priority_queue.hppnu �[��� // (C) Copyright Jeremiah Willcock 2004 // 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_FENCED_PRIORITY_QUEUE_HPP #define BOOST_FENCED_PRIORITY_QUEUE_HPP #include <vector> #include <queue> #include <functional> #include <boost/pending/queue.hpp> // Fenced priority queue // Jeremiah Willcock // This class implements a fenced priority queue. This is similar to // a normal priority queue (sorts its members, and only returns the // first), except that members cannot be sorted around a "fence" that // can be placed into the buffer. This fence is inserted using the // fence() member function or (possibly) implicitly by the top() and // pop() methods, and is removed automatically when the elements // around it are popped. // The implementation is as follows: Q is an unsorted queue that // contains the already-sorted list data, and PQ is a priority queue // that contains new elements (since the last fence) that have yet to // be sorted. New elements are inserted into PQ, and a fence moves // all elements in PQ into the back of Q in sorted order. Elements // are then popped from the front of Q, and if that is empty the front // of PQ. namespace boost { template < class T, class Compare = std::less< T >, bool implicit_fence = true, class Buffer = boost::queue< T > > class fenced_priority_queue { public: typedef T value_type; typedef typename Buffer::size_type size_type; fenced_priority_queue(const Compare _comp = Compare()) : PQ(_comp) {} void push(const T& data); void pop(void); T& top(void); const T& top(void) const; size_type size(void) const; bool empty(void) const; void fence(void); private: void fence(void) const; // let them mutable to allow const version of top and the same // semantics with non-constant version. Rich Lee mutable std::priority_queue< T, std::vector< T >, Compare > PQ; mutable Buffer Q; }; template < class T, class Compare, bool implicit_fence, class Buffer > inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::push( const T& t) { // Push a new element after the last fence. This puts it into the // priority queue to be sorted with all other elements in its // partition. PQ.push(t); } template < class T, class Compare, bool implicit_fence, class Buffer > inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::pop( void) { // Pop one element from the front of the queue. Removes from the // already-sorted part of the queue if it is non-empty, otherwise // removes from the new-element priority queue. Runs an implicit // "fence" operation if the implicit_fence template argument is // true. if (implicit_fence) fence(); if (!Q.empty()) Q.pop(); else PQ.pop(); } template < class T, class Compare, bool implicit_fence, class Buffer > inline T& fenced_priority_queue< T, Compare, implicit_fence, Buffer >::top(void) { // Get the top element from the queue. This element comes from Q if // possible, otherwise from PQ. Causes an implicit "fence" // operation if the implicit_fence template argument is true. if (implicit_fence) fence(); if (!Q.empty()) return Q.top(); else // std::priority_queue only have const version of top. Rich Lee return const_cast< T& >(PQ.top()); } template < class T, class Compare, bool implicit_fence, class Buffer > inline const T& fenced_priority_queue< T, Compare, implicit_fence, Buffer >::top(void) const { if (implicit_fence) fence(); if (!Q.empty()) return Q.top(); else return PQ.top(); } template < class T, class Compare, bool implicit_fence, class Buffer > inline typename fenced_priority_queue< T, Compare, implicit_fence, Buffer >::size_type fenced_priority_queue< T, Compare, implicit_fence, Buffer >::size(void) const { // Returns the size of the queue (both parts together). return Q.size() + PQ.size(); } template < class T, class Compare, bool implicit_fence, class Buffer > inline bool fenced_priority_queue< T, Compare, implicit_fence, Buffer >::empty( void) const { // Returns if the queue is empty, i.e. both parts are empty. return Q.empty() && PQ.empty(); } template < class T, class Compare, bool implicit_fence, class Buffer > inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::fence( void) { // Perform a fence operation. Remove elements from PQ in sorted // order and insert them in the back of Q. while (!PQ.empty()) { Q.push(PQ.top()); PQ.pop(); } } template < class T, class Compare, bool implicit_fence, class Buffer > inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::fence( void) const { // Perform a fence operation. Remove elements from PQ in sorted // order and insert them in the back of Q. while (!PQ.empty()) { Q.push(PQ.top()); PQ.pop(); } } } #endif /* BOOST_FENCED_PRIORITY_QUEUE_HPP */ PK Q�!\� detail/property.hppnu �[��� // (C) Copyright Jeremy Siek 2004 // 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_DETAIL_PROPERTY_HPP #define BOOST_DETAIL_PROPERTY_HPP #include <utility> // for std::pair #include <boost/type_traits/same_traits.hpp> // for is_same namespace boost { namespace detail { struct error_property_not_found { }; } // namespace detail } // namespace boost #endif // BOOST_DETAIL_PROPERTY_HPP PK Q�!\#s�� detail/disjoint_sets.hppnu �[��� // (C) Copyright Jeremy Siek 2004 // 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_DETAIL_DISJOINT_SETS_HPP #define BOOST_DETAIL_DISJOINT_SETS_HPP namespace boost { namespace detail { template < class ParentPA, class Vertex > Vertex find_representative_with_path_halving(ParentPA p, Vertex v) { Vertex parent = get(p, v); Vertex grandparent = get(p, parent); while (parent != grandparent) { put(p, v, grandparent); v = grandparent; parent = get(p, v); grandparent = get(p, parent); } return parent; } template < class ParentPA, class Vertex > Vertex find_representative_with_full_compression(ParentPA parent, Vertex v) { Vertex old = v; Vertex ancestor = get(parent, v); while (ancestor != v) { v = ancestor; ancestor = get(parent, v); } v = get(parent, old); while (ancestor != v) { put(parent, old, ancestor); old = v; v = get(parent, old); } return ancestor; } /* the postcondition of link sets is: component_representative(i) == component_representative(j) */ template < class ParentPA, class RankPA, class Vertex, class ComponentRepresentative > inline void link_sets(ParentPA p, RankPA rank, Vertex i, Vertex j, ComponentRepresentative comp_rep) { i = comp_rep(p, i); j = comp_rep(p, j); if (i == j) return; if (get(rank, i) > get(rank, j)) put(p, j, i); else { put(p, i, j); if (get(rank, i) == get(rank, j)) put(rank, j, get(rank, j) + 1); } } // normalize components has the following postcondidition: // i >= p[i] // that is, the representative is the node with the smallest index in its // class as its precondition it it assumes that the node container is // compressed template < class ParentPA, class Vertex > inline void normalize_node(ParentPA p, Vertex i) { if (i > get(p, i) || get(p, get(p, i)) != get(p, i)) put(p, i, get(p, get(p, i))); else { put(p, get(p, i), i); put(p, i, i); } } } // namespace detail } // namespace boost #endif // BOOST_DETAIL_DISJOINT_SETS_HPP PK Q�!\�1�L L detail/int_iterator.hppnu �[��� // (C) Copyright Jeremy Siek 1999. // 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_INT_ITERATOR_H #define BOOST_INT_ITERATOR_H #if !defined BOOST_MSVC #include <boost/operators.hpp> #endif #include <iostream> #include <iterator> #include <cstddef> //using namespace std; #ifndef BOOST_NO_OPERATORS_IN_NAMESPACE namespace boost { namespace iterators { #endif // this should use random_access_iterator_helper but I've had // VC++ portablility problems with that. -JGS template <class IntT> class int_iterator { typedef int_iterator self; public: typedef std::random_access_iterator_tag iterator_category; typedef IntT value_type; typedef IntT& reference; typedef IntT* pointer; typedef std::ptrdiff_t difference_type; inline int_iterator() : _i(0) { } inline int_iterator(IntT i) : _i(i) { } inline int_iterator(const self& x) : _i(x._i) { } inline self& operator=(const self& x) { _i = x._i; return *this; } inline IntT operator*() { return _i; } inline IntT operator[](IntT n) { return _i + n; } inline self& operator++() { ++_i; return *this; } inline self operator++(int) { self t = *this; ++_i; return t; } inline self& operator+=(IntT n) { _i += n; return *this; } inline self operator+(IntT n) { self t = *this; t += n; return t; } inline self& operator--() { --_i; return *this; } inline self operator--(int) { self t = *this; --_i; return t; } inline self& operator-=(IntT n) { _i -= n; return *this; } inline IntT operator-(const self& x) const { return _i - x._i; } inline bool operator==(const self& x) const { return _i == x._i; } // vc++ had a problem finding != in random_access_iterator_helper // need to look into this... for now implementing everything here -JGS inline bool operator!=(const self& x) const { return _i != x._i; } inline bool operator<(const self& x) const { return _i < x._i; } inline bool operator<=(const self& x) const { return _i <= x._i; } inline bool operator>(const self& x) const { return _i > x._i; } inline bool operator>=(const self& x) const { return _i >= x._i; } protected: IntT _i; }; template <class IntT> inline int_iterator<IntT> operator+(IntT n, int_iterator<IntT> t) { t += n; return t; } #ifndef BOOST_NO_OPERATORS_IN_NAMESPACE } /* namespace iterators */ using iterators::int_iterator; } /* namespace boost */ #endif #ifdef BOOST_NO_OPERATORS_IN_NAMESPACE namespace boost { using ::int_iterator; namespace iterators { using ::int_iterator; }} #endif #endif /* BOOST_INT_ITERATOR_H */ PK Q�!\��� � mutable_queue.hppnu �[��� // //======================================================================= // 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_MUTABLE_QUEUE_HPP #define BOOST_MUTABLE_QUEUE_HPP #include <vector> #include <algorithm> #include <functional> #include <boost/property_map/property_map.hpp> #include <boost/pending/mutable_heap.hpp> #include <boost/pending/is_heap.hpp> #include <boost/graph/detail/array_binary_tree.hpp> #include <iterator> namespace boost { // The mutable queue whose elements are indexed // // This adaptor provides a special kind of priority queue that has // and update operation. This allows the ordering of the items to // change. After the ordering criteria for item x changes, one must // call the Q.update(x) // // In order to efficiently find x in the queue, a functor must be // provided to map value_type to a unique ID, which the // mutable_queue will then use to map to the location of the // item. The ID's generated must be between 0 and N, where N is the // value passed to the constructor of mutable_queue template < class IndexedType, class RandomAccessContainer = std::vector< IndexedType >, class Comp = std::less< typename RandomAccessContainer::value_type >, class ID = identity_property_map > class mutable_queue { public: typedef IndexedType value_type; typedef typename RandomAccessContainer::size_type size_type; protected: typedef typename RandomAccessContainer::iterator iterator; #if !defined BOOST_NO_STD_ITERATOR_TRAITS typedef array_binary_tree_node< iterator, ID > Node; #else typedef array_binary_tree_node< iterator, value_type, ID > Node; #endif typedef compare_array_node< RandomAccessContainer, Comp > Compare; typedef std::vector< size_type > IndexArray; public: typedef Compare value_compare; typedef ID id_generator; mutable_queue(size_type n, const Comp& x, const ID& _id) : index_array(n), comp(x), id(_id) { c.reserve(n); } template < class ForwardIterator > mutable_queue(ForwardIterator first, ForwardIterator last, const Comp& x, const ID& _id) : index_array(std::distance(first, last)), comp(x), id(_id) { while (first != last) { push(*first); ++first; } } bool empty() const { return c.empty(); } void pop() { value_type tmp = c.back(); c.back() = c.front(); c.front() = tmp; size_type id_f = get(id, c.back()); size_type id_b = get(id, tmp); size_type i = index_array[id_b]; index_array[id_b] = index_array[id_f]; index_array[id_f] = i; c.pop_back(); Node node(c.begin(), c.end(), c.begin(), id); down_heap(node, comp, index_array); } void push(const IndexedType& x) { c.push_back(x); /*set index-array*/ index_array[get(id, x)] = c.size() - 1; Node node(c.begin(), c.end(), c.end() - 1, id); up_heap(node, comp, index_array); } void update(const IndexedType& x) { size_type current_pos = index_array[get(id, x)]; c[current_pos] = x; Node node(c.begin(), c.end(), c.begin() + current_pos, id); update_heap(node, comp, index_array); } value_type& front() { return c.front(); } value_type& top() { return c.front(); } const value_type& front() const { return c.front(); } const value_type& top() const { return c.front(); } size_type size() const { return c.size(); } void clear() { c.clear(); } #if 0 // dwa 2003/7/11 - I don't know what compiler is supposed to // be able to compile this, but is_heap is not standard!! bool test() { return std::is_heap(c.begin(), c.end(), Comp()); } #endif protected: IndexArray index_array; Compare comp; RandomAccessContainer c; ID id; }; } #endif // BOOST_MUTABLE_QUEUE_HPP PK Q�!\�A R* * fibonacci_heap.hppnu �[��� // (C) Copyright Jeremy Siek 2004. // 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_FIBONACCI_HEAP_HPP #define BOOST_FIBONACCI_HEAP_HPP #if defined(__sgi) && !defined(__GNUC__) #include <math.h> #else #include <boost/config/no_tr1/cmath.hpp> #endif #include <iosfwd> #include <vector> #include <functional> #include <boost/config.hpp> #include <boost/property_map/property_map.hpp> // // An adaptation of Knuth's Fibonacci heap implementation // in "The Stanford Graph Base", pages 475-482. // namespace boost { template < class T, class Compare = std::less< T >, class ID = identity_property_map > class fibonacci_heap { typedef typename boost::property_traits< ID >::value_type size_type; typedef T value_type; protected: typedef fibonacci_heap self; typedef std::vector< size_type > LinkVec; typedef typename LinkVec::iterator LinkIter; public: fibonacci_heap( size_type n, const Compare& cmp, const ID& id = identity_property_map()) : _key(n) , _left(n) , _right(n) , _p(n) , _mark(n) , _degree(n) , _n(0) , _root(n) , _id(id) , _compare(cmp) , _child(n) , #if defined(BOOST_MSVC) || defined(__ICL) // need a new macro? new_roots(size_type(log(float(n))) + 5) { } #else new_roots(size_type(std::log(float(n))) + 5) { } #endif // 33 void push(const T& d) { ++_n; size_type v = get(_id, d); _key[v] = d; _p[v] = nil(); _degree[v] = 0; _mark[v] = false; _child[v] = nil(); if (_root == nil()) { _root = _left[v] = _right[v] = v; // std::cout << "root added" << std::endl; } else { size_type u = _left[_root]; _left[v] = u; _right[v] = _root; _left[_root] = _right[u] = v; if (_compare(d, _key[_root])) _root = v; // std::cout << "non-root node added" << std::endl; } } T& top() { return _key[_root]; } const T& top() const { return _key[_root]; } // 38 void pop() { --_n; int h = -1; size_type v, w; if (_root != nil()) { if (_degree[_root] == 0) { v = _right[_root]; } else { w = _child[_root]; v = _right[w]; _right[w] = _right[_root]; for (w = v; w != _right[_root]; w = _right[w]) _p[w] = nil(); } while (v != _root) { w = _right[v]; add_tree_to_new_roots(v, new_roots.begin(), h); v = w; } rebuild_root_list(new_roots.begin(), h); } } // 39 inline void add_tree_to_new_roots(size_type v, LinkIter new_roots, int& h) { int r; size_type u; r = _degree[v]; while (1) { if (h < r) { do { ++h; new_roots[h] = (h == r ? v : nil()); } while (h < r); break; } if (new_roots[r] == nil()) { new_roots[r] = v; break; } u = new_roots[r]; new_roots[r] = nil(); if (_compare(_key[u], _key[v])) { _degree[v] = r; _mark[v] = false; std::swap(u, v); } make_child(u, v, r); ++r; } _degree[v] = r; _mark[v] = false; } // 40 void make_child(size_type u, size_type v, size_type r) { if (r == 0) { _child[v] = u; _left[u] = u; _right[u] = u; } else { size_type t = _child[v]; _right[u] = _right[t]; _left[u] = t; _right[t] = u; _left[_right[u]] = u; } _p[u] = v; } // 41 inline void rebuild_root_list(LinkIter new_roots, int& h) { size_type u, v, w; if (h < 0) _root = nil(); else { T d; u = v = new_roots[h]; d = _key[u]; _root = u; for (h--; h >= 0; --h) if (new_roots[h] != nil()) { w = new_roots[h]; _left[w] = v; _right[v] = w; if (_compare(_key[w], d)) { _root = w; d = _key[w]; } v = w; } _right[v] = u; _left[u] = v; } } // 34 void update(const T& d) { size_type v = get(_id, d); assert(!_compare(_key[v], d)); _key[v] = d; size_type p = _p[v]; if (p == nil()) { if (_compare(d, _key[_root])) _root = v; } else if (_compare(d, _key[p])) while (1) { size_type r = _degree[p]; if (r >= 2) remove_from_family(v, p); insert_into_forest(v, d); size_type pp = _p[p]; if (pp == nil()) { --_degree[p]; break; } if (_mark[p] == false) { _mark[p] = true; --_degree[p]; break; } else --_degree[p]; v = p; p = pp; } } inline size_type size() const { return _n; } inline bool empty() const { return _n == 0; } void print(std::ostream& os) { if (_root != nil()) { size_type i = _root; do { print_recur(i, os); os << std::endl; i = _right[i]; } while (i != _root); } } protected: // 35 inline void remove_from_family(size_type v, size_type p) { size_type u = _left[v]; size_type w = _right[v]; _right[u] = w; _left[w] = u; if (_child[p] == v) _child[p] = w; } // 36 inline void insert_into_forest(size_type v, const T& d) { _p[v] = nil(); size_type u = _left[_root]; _left[v] = u; _right[v] = _root; _left[_root] = _right[u] = v; if (_compare(d, _key[_root])) _root = v; } void print_recur(size_type x, std::ostream& os) { if (x != nil()) { os << x; if (_degree[x] > 0) { os << "("; size_type i = _child[x]; do { print_recur(i, os); os << " "; i = _right[i]; } while (i != _child[x]); os << ")"; } } } size_type nil() const { return _left.size(); } std::vector< T > _key; LinkVec _left, _right, _p; std::vector< bool > _mark; LinkVec _degree; size_type _n, _root; ID _id; Compare _compare; LinkVec _child; LinkVec new_roots; }; } // namespace boost #endif // BOOST_FIBONACCI_HEAP_HPP PK Q�!\��] R R property_serialize.hppnu �[��� // (C) Copyright Jeremy Siek 2006 // 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_PROPERTY_SERIALIZE_HPP #define BOOST_PROPERTY_SERIALIZE_HPP #include <boost/pending/property.hpp> #include <boost/serialization/is_bitwise_serializable.hpp> #include <boost/serialization/base_object.hpp> #include <boost/serialization/nvp.hpp> namespace boost { template < class Archive > inline void serialize(Archive&, no_property&, const unsigned int) { } template < class Archive, class Tag, class T, class Base > void serialize( Archive& ar, property< Tag, T, Base >& prop, const unsigned int /*version*/) { ar& serialization::make_nvp("property_value", prop.m_value); ar& serialization::make_nvp("property_base", prop.m_base); } #ifdef BOOST_GRAPH_USE_MPI // Setting the serialization properties of boost::property<> and // boost::no_property to is_bitwise_serializable, object_serializable, // track_never only when BOOST_GRAPH_USE_MPI is defined is dubious. // // This changes the serialization format of these classes, and hence // of boost::adjacency_list, depending on whether BOOST_GRAPH_USE_MPI // is defined. // // These serialization properties should probably be set in either case. // // Unfortunately, doing that now will change the serialization format // of boost::adjacency_list in the non-MPI case, and could potentially // break software that reads files serialized with an older release. namespace mpi { // forward declaration, to avoid including mpi template < typename T > struct is_mpi_datatype; template < typename Tag, typename T, typename Base > struct is_mpi_datatype< property< Tag, T, Base > > : mpl::and_< is_mpi_datatype< T >, is_mpi_datatype< Base > > { }; } namespace serialization { template < typename Tag, typename T, typename Base > struct is_bitwise_serializable< property< Tag, T, Base > > : mpl::and_< is_bitwise_serializable< T >, is_bitwise_serializable< Base > > { }; template < typename Tag, typename T, typename Base > struct implementation_level< property< Tag, T, Base > > : mpl::int_< object_serializable > { }; template < typename Tag, typename T, typename Base > struct tracking_level< property< Tag, T, Base > > : mpl::int_< track_never > { }; } #endif // BOOST_GRAPH_USE_MPI } // end namespace boost #ifdef BOOST_GRAPH_USE_MPI namespace boost { namespace mpi { template <> struct is_mpi_datatype< boost::no_property > : mpl::true_ { }; } } // end namespace boost::mpi BOOST_IS_BITWISE_SERIALIZABLE(boost::no_property) BOOST_CLASS_IMPLEMENTATION(boost::no_property, object_serializable) BOOST_CLASS_TRACKING(boost::no_property, track_never) #endif // BOOST_GRAPH_USE_MPI #endif // BOOST_PROPERTY_SERIALIZE_HPP PK Q�!\.g1�� � is_heap.hppnu �[��� // //======================================================================= // 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) //======================================================================= // #if __KCC namespace std { template < class RandomAccessIterator, class Distance > bool __is_heap(RandomAccessIterator first, RandomAccessIterator last, Distance*) { const Distance n = last - first; Distance parent = 0; for (Distance child = 1; child < n; ++child) { if (first[parent] < first[child]) return false; if ((child & 1) == 0) ++parent; } return true; } template < class RandomAccessIterator > inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last) { return __is_heap(first, last, distance_type(first)); } template < class RandomAccessIterator, class Distance, class StrictWeakOrdering > bool __is_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp, Distance*) { const Distance n = last - first; Distance parent = 0; for (Distance child = 1; child < n; ++child) { if (comp(first[parent], first[child])) return false; if ((child & 1) == 0) ++parent; } return true; } template < class RandomAccessIterator, class StrictWeakOrdering > inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp) { return __is_heap(first, last, comp, distance_type(first)); } } #endif PK Q�!\ 6l\� � stringtok.hppnu �[��� PK Q�!\d�q�� � � iterator_adaptors.hppnu �[��� PK Q�!\Tb��"Q "Q relaxed_heap.hppnu �[��� PK Q�!\o=ۄp6 p6 w` property.hppnu �[��� PK Q�!\�߶Hs s #� disjoint_sets.hppnu �[��� PK Q�!\;�_�� � װ mutable_heap.hppnu �[��� PK Q�!\3�y y � bucket_sorter.hppnu �[��� PK Q�!\���R� � �� indirect_cmp.hppnu �[��� PK Q�!\�l��T �T �� container_traits.hppnu �[��� PK Q�!\�=g� � �* integer_log2.hppnu �[��� PK Q�!\F�PmT T #, queue.hppnu �[��� PK Q�!\,:�k� � �8 iterator_tests.hppnu �[��� PK Q�!\�ԮFD D �U fenced_priority_queue.hppnu �[��� PK Q�!\� |j detail/property.hppnu �[��� PK Q�!\#s�� �l detail/disjoint_sets.hppnu �[��� PK Q�!\�1�L L w detail/int_iterator.hppnu �[��� PK Q�!\��� � �� mutable_queue.hppnu �[��� PK Q�!\�A R* * y� fibonacci_heap.hppnu �[��� PK Q�!\��] R R � property_serialize.hppnu �[��� PK Q�!\.g1�� � }� is_heap.hppnu �[��� PK ^ ��
| ver. 1.6 |
Github
|
.
| PHP 8.2.30 | ??????????? ?????????: 0 |
proxy
|
phpinfo
|
???????????