From 0e4d7b3c2bcff6ddbdb285db3b5be221e1251cdb Mon Sep 17 00:00:00 2001 From: bangerth Date: Sat, 20 Sep 2008 02:40:23 +0000 Subject: [PATCH] Add pending directory, necessary for some older compilers. git-svn-id: https://svn.dealii.org/trunk@16868 0785d39b-7218-0410-832d-ea1e28bc413d --- .../include/boost/pending/bucket_sorter.hpp | 134 ++++ .../boost/pending/container_traits.hpp | 425 ++++++++++++ .../boost/include/boost/pending/cstddef.hpp | 16 + .../boost/include/boost/pending/ct_if.hpp | 43 ++ .../boost/pending/detail/disjoint_sets.hpp | 88 +++ .../boost/pending/detail/int_iterator.hpp | 74 ++ .../include/boost/pending/detail/property.hpp | 160 +++++ .../include/boost/pending/disjoint_sets.hpp | 220 ++++++ .../boost/pending/fenced_priority_queue.hpp | 152 +++++ .../include/boost/pending/fibonacci_heap.hpp | 271 ++++++++ .../include/boost/pending/indirect_cmp.hpp | 86 +++ .../include/boost/pending/integer_log2.hpp | 116 ++++ .../include/boost/pending/integer_range.hpp | 59 ++ .../boost/include/boost/pending/is_heap.hpp | 62 ++ .../boost/pending/iterator_adaptors.hpp | 6 + .../include/boost/pending/iterator_tests.hpp | 268 ++++++++ .../include/boost/pending/lowest_bit.hpp | 41 ++ .../include/boost/pending/mutable_heap.hpp | 64 ++ .../include/boost/pending/mutable_queue.hpp | 135 ++++ .../boost/include/boost/pending/property.hpp | 132 ++++ .../boost/pending/property_serialize.hpp | 28 + .../boost/include/boost/pending/queue.hpp | 118 ++++ .../include/boost/pending/relaxed_heap.hpp | 644 ++++++++++++++++++ .../boost/include/boost/pending/stringtok.hpp | 116 ++++ 24 files changed, 3458 insertions(+) create mode 100644 deal.II/contrib/boost/include/boost/pending/bucket_sorter.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/container_traits.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/cstddef.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/ct_if.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/detail/disjoint_sets.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/detail/int_iterator.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/detail/property.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/disjoint_sets.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/fenced_priority_queue.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/fibonacci_heap.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/indirect_cmp.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/integer_log2.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/integer_range.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/is_heap.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/iterator_adaptors.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/iterator_tests.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/lowest_bit.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/mutable_heap.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/mutable_queue.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/property.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/property_serialize.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/queue.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/relaxed_heap.hpp create mode 100644 deal.II/contrib/boost/include/boost/pending/stringtok.hpp diff --git a/deal.II/contrib/boost/include/boost/pending/bucket_sorter.hpp b/deal.II/contrib/boost/include/boost/pending/bucket_sorter.hpp new file mode 100644 index 0000000000..8b7926d2df --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/bucket_sorter.hpp @@ -0,0 +1,134 @@ +// +//======================================================================= +// 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 header. (JMaddock) +// +#ifndef BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP +#define BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP + +#include +#include +#include + +namespace boost { + + template + class bucket_sorter { + public: + typedef BucketType bucket_type; + typedef ValueType value_type; + typedef typename std::vector::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::max)(); + } + + typedef typename std::vector::iterator Iter; + typedef typename std::vector::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 head; + std::vector next; + std::vector prev; + std::vector id_to_value; + Bucket bucket; + ValueIndexMap id; + }; + +} + +#endif diff --git a/deal.II/contrib/boost/include/boost/pending/container_traits.hpp b/deal.II/contrib/boost/include/boost/pending/container_traits.hpp new file mode 100644 index 0000000000..571eedb1c1 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/container_traits.hpp @@ -0,0 +1,425 @@ +// (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_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 header. -JGS + +#include + +#include // for std::remove +#include +#include +#include +#include + +#if !defined BOOST_NO_HASH +# ifdef BOOST_HASH_SET_HEADER +# include BOOST_HASH_SET_HEADER +# else +# include +# endif +# ifdef BOOST_HASH_MAP_HEADER +# include BOOST_HASH_MAP_HEADER +# else +# include +# endif +#endif + +#if !defined BOOST_NO_SLIST +# ifdef BOOST_SLIST_HEADER +# include BOOST_SLIST_HEADER +# else +# include +# endif +#endif + +#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) +// Stay out of the way of concept checking class templates +# define Container Container_ +# define AssociativeContainer AssociativeContainer_ +#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 + +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + // don't use this unless there is partial specialization + template + struct container_traits { + typedef typename Container::category category; + typedef typename Container::iterator_stability iterator_stability; + }; +#endif + + // 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 + vector_tag container_category(const std::vector&) + { return vector_tag(); } + + template + unstable_tag iterator_stability(const std::vector&) + { return unstable_tag(); } + +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + template + struct container_traits< std::vector > { + typedef vector_tag category; + typedef unstable_tag iterator_stability; + }; +#endif + + // 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 + list_tag container_category(const std::list&) + { return list_tag(); } + + template + stable_tag iterator_stability(const std::list&) + { return stable_tag(); } + +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + template + struct container_traits< std::list > { + typedef list_tag category; + typedef stable_tag iterator_stability; + }; +#endif + + + // std::slist +#ifndef BOOST_NO_SLIST +# ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + template + struct container_traits > { + typedef front_insertion_sequence_tag category; + typedef stable_tag iterator_stability; + }; +#endif + template + front_insertion_sequence_tag container_category( + const BOOST_STD_EXTENSION_NAMESPACE::slist& + ) + { return front_insertion_sequence_tag(); } + + template + stable_tag iterator_stability( + const BOOST_STD_EXTENSION_NAMESPACE::slist&) + { return stable_tag(); } +#endif + + + // std::set + struct set_tag : + virtual public sorted_associative_container_tag, + virtual public simple_associative_container_tag, + virtual public unique_associative_container_tag + { }; + + template + set_tag container_category(const std::set&) + { return set_tag(); } + + template + stable_tag iterator_stability(const std::set&) + { return stable_tag(); } + +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + template + struct container_traits< std::set > { + typedef set_tag category; + typedef stable_tag iterator_stability; + }; +#endif + + // std::multiset + struct multiset_tag : + virtual public sorted_associative_container_tag, + virtual public simple_associative_container_tag, + virtual public multiple_associative_container_tag + { }; + + template + multiset_tag container_category(const std::multiset&) + { return multiset_tag(); } + + template + stable_tag iterator_stability(const std::multiset&) + { return stable_tag(); } + +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + template + struct container_traits< std::multiset > { + typedef multiset_tag category; + typedef stable_tag iterator_stability; + }; +#endif + + // deque + + // std::map + struct map_tag : + virtual public sorted_associative_container_tag, + virtual public pair_associative_container_tag, + virtual public unique_associative_container_tag + { }; + +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + template + struct container_traits< std::map > { + typedef map_tag category; + typedef stable_tag iterator_stability; + }; +#endif + + template + map_tag container_category(const std::map&) + { return map_tag(); } + + template + stable_tag iterator_stability(const std::map&) + { 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 + { }; + +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + template + struct container_traits< std::multimap > { + typedef multimap_tag category; + typedef stable_tag iterator_stability; + }; +#endif + + template + multimap_tag container_category(const std::multimap&) + { return multimap_tag(); } + + template + stable_tag iterator_stability(const std::multimap&) + { return stable_tag(); } + + + // hash_set, hash_map + +#ifndef BOOST_NO_HASH +#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + template + struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_set > { + typedef set_tag category; + typedef stable_tag iterator_stability; // is this right? + }; + template + struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_map > { + typedef map_tag category; + typedef stable_tag iterator_stability; // is this right? + }; +#endif + template + set_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_set&) + { return set_tag(); } + + template + map_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_map&) + { return map_tag(); } + + template + stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_set&) + { return stable_tag(); } + + template + stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_map&) + { return stable_tag(); } +#endif + + + + //=========================================================================== + // Generalized Container Functions + + + // Erase + template + void erase_dispatch(Sequence& c, const T& x, + sequence_tag) + { + c.erase(std::remove(c.begin(), c.end(), x), c.end()); + } + + template + void erase_dispatch(AssociativeContainer& c, const T& x, + associative_container_tag) + { + c.erase(x); + } + template + void erase(Container& c, const T& x) + { + erase_dispatch(c, x, container_category(c)); + } + + // Erase If + template + 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 + 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 + 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 + void erase_if(Container& c, Predicate p) + { + erase_if_dispatch(c, p, container_category(c), iterator_stability(c)); + } + + // Push + template + std::pair + push_dispatch(Container& c, const T& v, back_insertion_sequence_tag) + { + c.push_back(v); + return std::make_pair(boost::prior(c.end()), true); + } + + template + std::pair + push_dispatch(Container& c, const T& v, front_insertion_sequence_tag) + { + c.push_front(v); + return std::make_pair(c.begin(), true); + } + + template + std::pair + push_dispatch(AssociativeContainer& c, const T& v, + unique_associative_container_tag) + { + return c.insert(v); + } + + template + std::pair + push_dispatch(AssociativeContainer& c, const T& v, + multiple_associative_container_tag) + { + return std::make_pair(c.insert(v), true); + } + + template + std::pair + push(Container& c, const T& v) + { + return push_dispatch(c, v, container_category(c)); + } + +}} // namespace boost::graph_detail + +#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) +// Stay out of the way of concept checking class templates +# undef Container +# undef AssociativeContainer +#endif + +#endif // BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H diff --git a/deal.II/contrib/boost/include/boost/pending/cstddef.hpp b/deal.II/contrib/boost/include/boost/pending/cstddef.hpp new file mode 100644 index 0000000000..440629e265 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/cstddef.hpp @@ -0,0 +1,16 @@ +// -*- C++ -*- forwarding header. +// (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_CSTDDEF_HPP +#define BOOST_CSTDDEF_HPP + +#if defined(__sgi) && !defined(__GNUC__) +# include +#else +# include +#endif + +#endif diff --git a/deal.II/contrib/boost/include/boost/pending/ct_if.hpp b/deal.II/contrib/boost/include/boost/pending/ct_if.hpp new file mode 100644 index 0000000000..a9b801e57f --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/ct_if.hpp @@ -0,0 +1,43 @@ +// (C) Copyright Jeremy Siek 2000. +// 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) + +// This header replaces the implementation of ct_if that preceded the +// introduction of Boost.MPL with a facade that defers to that reviewed and +// accepted library. + +// Author: Ronald Garcia +// Date: 20 October, 2006 + + +#ifndef BOOST_CT_IF_HPP +#define BOOST_CT_IF_HPP + + +// A stub implementation in terms of Boost.MPL + +#include +#include +#include +// true_type and false_type are used by applications of ct_if +#include + +namespace boost { + + template + struct ct_and : boost::mpl::and_ {}; + + template + struct ct_not : mpl::not_ {}; + + template + struct ct_if : mpl::if_c {}; + + template + struct ct_if_t : mpl::if_ {}; + +} // namespace boost + +#endif // BOOST_CT_IF_HPP + diff --git a/deal.II/contrib/boost/include/boost/pending/detail/disjoint_sets.hpp b/deal.II/contrib/boost/include/boost/pending/detail/disjoint_sets.hpp new file mode 100644 index 0000000000..6d1ec3ac7e --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/detail/disjoint_sets.hpp @@ -0,0 +1,88 @@ +// (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 +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 +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 +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 +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 diff --git a/deal.II/contrib/boost/include/boost/pending/detail/int_iterator.hpp b/deal.II/contrib/boost/include/boost/pending/detail/int_iterator.hpp new file mode 100644 index 0000000000..e3bae34ce7 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/detail/int_iterator.hpp @@ -0,0 +1,74 @@ +// (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 + +#include +#if !defined BOOST_MSVC +#include +#endif +#include +//using namespace std; + +#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE +namespace boost { +#endif + +// this should use random_access_iterator_helper but I've had +// VC++ portablility problems with that. -JGS +template +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 +inline int_iterator +operator+(IntT n, int_iterator t) { t += n; return t; } + +#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE +} /* namespace boost */ +#endif + +#ifdef BOOST_NO_OPERATORS_IN_NAMESPACE +namespace boost { + using ::int_iterator; +} +#endif + + +#endif /* BOOST_INT_ITERATOR_H */ diff --git a/deal.II/contrib/boost/include/boost/pending/detail/property.hpp b/deal.II/contrib/boost/include/boost/pending/detail/property.hpp new file mode 100644 index 0000000000..09e8866cf6 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/detail/property.hpp @@ -0,0 +1,160 @@ +// (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 // for std::pair +#include // for is_same + +namespace boost { + + namespace detail { + + template + struct same_property { + enum { value = is_same::value }; + }; + + struct error_property_not_found { }; + + template + struct property_value_dispatch { + template + inline static T& get_value(PropertyTag& p, T*, Tag) { + return p.m_value; + } + template + inline static const T& const_get_value(const PropertyTag& p, T*, Tag) { + return p.m_value; + } + }; + + template + struct property_value_end { + template struct result { typedef T type; }; + + template + inline static T& get_value(PropertyList& p, T* t, Tag tag) { + typedef typename PropertyList::next_type Next; + typedef typename Next::tag_type Next_tag; + enum { match = same_property::value }; + return property_value_dispatch + ::get_value(static_cast(p), t, tag); + } + template + inline static const T& const_get_value(const PropertyList& p, T* t, Tag tag) { + typedef typename PropertyList::next_type Next; + typedef typename Next::tag_type Next_tag; + enum { match = same_property::value }; + return property_value_dispatch + ::const_get_value(static_cast(p), t, tag); + } + }; + template <> + struct property_value_end { + template struct result { + typedef detail::error_property_not_found type; + }; + + // Stop the recursion and return error + template + inline static detail::error_property_not_found& + get_value(no_property&, T*, Tag) { + static error_property_not_found s_prop_not_found; + return s_prop_not_found; + } + template + inline static const detail::error_property_not_found& + const_get_value(const no_property&, T*, Tag) { + static error_property_not_found s_prop_not_found; + return s_prop_not_found; + } + }; + + template <> + struct property_value_dispatch<0> { + template + inline static typename property_value_end::template result::type& + get_value(PropertyList& p, T* t, Tag tag) { + return property_value_end::get_value(p, t, tag); + } + template + inline static const typename property_value_end::template result::type& + const_get_value(const PropertyList& p, T* t, Tag tag) { + return property_value_end::const_get_value(p, t, tag); + } + }; + + template + struct build_property_tag_value_alist + { + typedef typename PropertyList::next_type NextProperty; + typedef typename PropertyList::value_type Value; + typedef typename PropertyList::tag_type Tag; + typedef typename build_property_tag_value_alist::type Next; + typedef std::pair< std::pair, Next> type; + }; + template <> + struct build_property_tag_value_alist + { + typedef no_property type; + }; + +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + template + struct extract_value { + typedef error_property_not_found type; + }; + template + struct extract_value< std::pair,Rest>, Tag2> { + typedef typename extract_value::type type; + }; + template + struct extract_value< std::pair,Rest>, Tag> { + typedef Value type; + }; +#else + // VC++ workaround: + // The main idea here is to replace partial specialization with + // nested template member classes. Of course there is the + // further complication that the outer class of the nested + // template class cannot itself be a template class. + // Hence the need for the ev_selector. -JGS + + struct recursive_extract; + struct end_extract; + + template + struct ev_selector { typedef recursive_extract type; }; + template <> + struct ev_selector { typedef end_extract type; }; + + struct recursive_extract { + template + struct bind_ { + typedef typename TagValueAList::first_type AListFirst; + typedef typename AListFirst::first_type Tag2; + typedef typename AListFirst::second_type Value; + enum { match = same_property::value }; + typedef typename TagValueAList::second_type Next; + typedef typename ev_selector::type Extractor; + typedef typename boost::ct_if< match, Value, + typename Extractor::template bind_::type + >::type type; + }; + }; + struct end_extract { + template + struct bind_ { + typedef error_property_not_found type; + }; + }; +#endif //!defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + + } // namespace detail +} // namespace boost + +#endif // BOOST_DETAIL_PROPERTY_HPP diff --git a/deal.II/contrib/boost/include/boost/pending/disjoint_sets.hpp b/deal.II/contrib/boost/include/boost/pending/disjoint_sets.hpp new file mode 100644 index 0000000000..e64bc2b713 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/disjoint_sets.hpp @@ -0,0 +1,220 @@ +// +//======================================================================= +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame. +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +//======================================================================= +// +#ifndef BOOST_DISJOINT_SETS_HPP +#define BOOST_DISJOINT_SETS_HPP + +#include +#include +#include + +namespace boost { + + struct find_with_path_halving { + template + Vertex operator()(ParentPA p, Vertex v) { + return detail::find_representative_with_path_halving(p, v); + } + }; + + struct find_with_full_path_compression { + template + 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 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 + inline void make_set(Element x) + { + put(parent, x, x); + typedef typename property_traits::value_type R; + put(rank, x, R()); + } + + // Link - union the two sets represented by vertex x and y + template + 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 + 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 + inline Element find_set(Element x) + { + return rep(parent, x); + } + + template + 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 + inline void normalize_sets(ElementIterator first, ElementIterator last) + { + for (; first != last; ++first) + detail::normalize_node(parent, *first); + } + + template + 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 disjoint_sets_with_storage + { + typedef typename property_traits::value_type Index; + typedef std::vector ParentContainer; + typedef std::vector 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 + inline void + make_set(Element x) { + parent[x] = x; + rank[x] = 0; + } + template + 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 + inline void + union_set(Element x, Element y) { + Element rx = find_set(x); + Element ry = find_set(y); + link(rx, ry); + } + template + inline Element find_set(Element x) { + return id_to_vertex[rep(&parent[0], get(id,x))]; + } + + template + 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 + inline void normalize_sets(ElementIterator first, ElementIterator last) + { + for (; first != last; ++first) + detail::normalize_node(&parent[0], *first); + } + + template + 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 + 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 diff --git a/deal.II/contrib/boost/include/boost/pending/fenced_priority_queue.hpp b/deal.II/contrib/boost/include/boost/pending/fenced_priority_queue.hpp new file mode 100644 index 0000000000..4d4e3aff94 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/fenced_priority_queue.hpp @@ -0,0 +1,152 @@ +// (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 +#include +#include +#include + +// 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, bool implicit_fence = true, + class Buffer = boost::queue > + 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, Compare> PQ; + mutable Buffer Q; + }; + + template + inline void + fenced_priority_queue:: + 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 + inline void fenced_priority_queue:: + 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 + inline T& fenced_priority_queue:: + 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(PQ.top()); + } + + template + inline const T& + fenced_priority_queue:: + top(void) const { + if (implicit_fence) fence(); + if ( !Q.empty() ) + return Q.top(); + else + return PQ.top(); + } + + template + inline typename fenced_priority_queue::size_type + fenced_priority_queue:: + size(void) const { + // Returns the size of the queue (both parts together). + return Q.size() + PQ.size(); + } + + template + inline bool + fenced_priority_queue:: + empty(void) const { + // Returns if the queue is empty, i.e. both parts are empty. + return Q.empty() && PQ.empty(); + } + + template + inline void + fenced_priority_queue:: + 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 + inline void + fenced_priority_queue:: + 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 */ diff --git a/deal.II/contrib/boost/include/boost/pending/fibonacci_heap.hpp b/deal.II/contrib/boost/include/boost/pending/fibonacci_heap.hpp new file mode 100644 index 0000000000..76f28a8a02 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/fibonacci_heap.hpp @@ -0,0 +1,271 @@ +// (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 +#else +# include +#endif +#include +#include +#include +#include +#include + +// +// An adaptation of Knuth's Fibonacci heap implementation +// in "The Stanford Graph Base", pages 475-482. +// + +namespace boost { + + +template , + class ID = identity_property_map> +class fibonacci_heap +{ + typedef typename boost::property_traits::value_type size_type; + typedef T value_type; +protected: + typedef fibonacci_heap self; + typedef std::vector 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 _key; + LinkVec _left, _right, _p; + std::vector _mark; + LinkVec _degree; + size_type _n, _root; + ID _id; + Compare _compare; + LinkVec _child; + LinkVec new_roots; +}; + +} // namespace boost + + +#endif // BOOST_FIBONACCI_HEAP_HPP diff --git a/deal.II/contrib/boost/include/boost/pending/indirect_cmp.hpp b/deal.II/contrib/boost/include/boost/pending/indirect_cmp.hpp new file mode 100644 index 0000000000..c97594933f --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/indirect_cmp.hpp @@ -0,0 +1,86 @@ +// +//======================================================================= +// 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 +#include +#include + +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 indirect_cmp { + public: + typedef typename boost::property_traits::value_type T; + typedef typename boost::property_traits::key_type K; + typedef K first_argument_type; + typedef K second_argument_type; + typedef T result_type; + inline indirect_cmp(const ReadablePropertyMap& df, const Compare& c = Compare()) + : d(df), cmp(c) { } + + template + inline bool + operator()(const A& u, const B& v) const { + T du = get(d, u), dv = get(d, v); + return cmp(du, dv); + } + protected: + ReadablePropertyMap d; + Compare cmp; + }; + + template + indirect_cmp + make_indirect_cmp(const Compare& cmp, ReadablePropertyMap pmap) { + indirect_cmp p(pmap, cmp); + return p; + } + + template + class indirect_pmap { + public: + typedef typename boost::property_traits::value_type T; + typedef typename boost::property_traits::key_type K; + typedef K argument_type; + typedef T result_type; + inline indirect_pmap(const ReadablePropertyMap& df) + : d(df) { } + + inline bool operator()(const K& u) const { + return get(d, u); + } + protected: + ReadablePropertyMap d; + }; + + template + indirect_pmap + make_indirect_pmap(ReadablePropertyMap pmap) { + indirect_pmap f(pmap); + return f; + } + + +} // namespace boost + + +#endif // GGCL_INDIRECT_CMP_HPP diff --git a/deal.II/contrib/boost/include/boost/pending/integer_log2.hpp b/deal.II/contrib/boost/include/boost/pending/integer_log2.hpp new file mode 100644 index 0000000000..74e41794b6 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/integer_log2.hpp @@ -0,0 +1,116 @@ +// ------------------------------------- +// integer_log2.hpp +// +// Gives the integer part of the logarithm, in base 2, of a +// given number. Behavior is undefined if the argument is <= 0. +// +// +// (C) Copyright Gennaro Prota 2003 - 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) +// +// ------------------------------------------------------ +// +// $Id: integer_log2.hpp 41369 2007-11-25 18:07:19Z bemandawes $ + + +#ifndef BOOST_INTEGER_LOG2_HPP_GP_20030301 +#define BOOST_INTEGER_LOG2_HPP_GP_20030301 + +#include +#ifdef __BORLANDC__ +#include +#endif +#include "boost/limits.hpp" +#include "boost/config.hpp" + + +namespace boost { + namespace detail { + + template + int integer_log2_impl(T x, int n) { + + int result = 0; + + while (x != 1) { + + const T t = x >> n; + if (t) { + result += n; + x = t; + } + n /= 2; + + } + + return result; + } + + + + // helper to find the maximum power of two + // less than p (more involved than necessary, + // to avoid PTS) + // + template + struct max_pow2_less { + + enum { c = 2*n < p }; + + BOOST_STATIC_CONSTANT(int, value = + c ? (max_pow2_less< c*p, 2*c*n>::value) : n); + + }; + + template <> + struct max_pow2_less<0, 0> { + + BOOST_STATIC_CONSTANT(int, value = 0); + }; + + // this template is here just for Borland :( + // we could simply rely on numeric_limits but sometimes + // Borland tries to use numeric_limits, because + // of its usual const-related problems in argument deduction + // - gps + template + struct width { + +#ifdef __BORLANDC__ + BOOST_STATIC_CONSTANT(int, value = sizeof(T) * CHAR_BIT); +#else + BOOST_STATIC_CONSTANT(int, value = (std::numeric_limits::digits)); +#endif + + }; + + } // detail + + + // --------- + // integer_log2 + // --------------- + // + template + int integer_log2(T x) { + + assert(x > 0); + + const int n = detail::max_pow2_less< + detail::width :: value, 4 + > :: value; + + return detail::integer_log2_impl(x, n); + + } + + + +} + + + +#endif // include guard diff --git a/deal.II/contrib/boost/include/boost/pending/integer_range.hpp b/deal.II/contrib/boost/include/boost/pending/integer_range.hpp new file mode 100644 index 0000000000..229cbd8880 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/integer_range.hpp @@ -0,0 +1,59 @@ +// (C) Copyright David Abrahams and Jeremy Siek 2000-2001. +// 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: +// 04 Jan 2001 Factored counting_iterator stuff into +// boost/counting_iterator.hpp (David Abrahams) + +#ifndef BOOST_INTEGER_RANGE_HPP_ +#define BOOST_INTEGER_RANGE_HPP_ + +#include +#include +#include + +namespace boost { + +//============================================================================= +// Counting Iterator and Integer Range Class + +template +struct integer_range { + typedef counting_iterator iterator; + + typedef iterator const_iterator; + typedef IntegerType value_type; + typedef std::ptrdiff_t difference_type; + typedef IntegerType reference; + typedef IntegerType const_reference; + typedef const IntegerType* pointer; + typedef const IntegerType* const_pointer; + typedef IntegerType size_type; + + integer_range(IntegerType start, IntegerType finish) + : m_start(start), m_finish(finish) { } + + iterator begin() const { return iterator(m_start); } + iterator end() const { return iterator(m_finish); } + size_type size() const { return m_finish - m_start; } + bool empty() const { return m_finish == m_start; } + void swap(integer_range& x) { + std::swap(m_start, x.m_start); + std::swap(m_finish, x.m_finish); + } +protected: + IntegerType m_start, m_finish; +}; + +template +inline integer_range +make_integer_range(IntegerType first, IntegerType last) +{ + return integer_range(first, last); +} + +} // namespace boost + +#endif // BOOST_INTEGER_RANGE_HPP_ diff --git a/deal.II/contrib/boost/include/boost/pending/is_heap.hpp b/deal.II/contrib/boost/include/boost/pending/is_heap.hpp new file mode 100644 index 0000000000..b2e4b00694 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/is_heap.hpp @@ -0,0 +1,62 @@ +// +//======================================================================= +// 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 +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 +inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last) +{ + return __is_heap(first, last, distance_type(first)); +} + + +template +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 +inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last, + StrictWeakOrdering comp) +{ + return __is_heap(first, last, comp, distance_type(first)); +} + +} +#endif diff --git a/deal.II/contrib/boost/include/boost/pending/iterator_adaptors.hpp b/deal.II/contrib/boost/include/boost/pending/iterator_adaptors.hpp new file mode 100644 index 0000000000..2256e81240 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/iterator_adaptors.hpp @@ -0,0 +1,6 @@ +// 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 diff --git a/deal.II/contrib/boost/include/boost/pending/iterator_tests.hpp b/deal.II/contrib/boost/include/boost/pending/iterator_tests.hpp new file mode 100644 index 0000000000..dd5fe2ddd6 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/iterator_tests.hpp @@ -0,0 +1,268 @@ +// 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 +# include +# include +# include +# include // for detail::dummy_constructor +# include +# include + +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; +}; + +} + +BOOST_TT_BROKEN_COMPILER_SPEC(boost::dummyT) + +namespace boost { + +// Tests whether type Iterator satisfies the requirements for a +// TrivialIterator. +// Preconditions: i != j, *i == val +template +void trivial_iterator_test(const Iterator i, const Iterator j, T val) +{ + Iterator k; + assert(i == i); + assert(j == j); + assert(i != j); +#ifdef BOOST_NO_STD_ITERATOR_TRAITS + T v = *i; +#else + typename std::iterator_traits::value_type v = *i; +#endif + assert(v == val); +#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. + assert(v == i->foo()); +#endif + k = i; + assert(k == k); + assert(k == i); + assert(k != j); + assert(*k == val); +} + + +// Preconditions: i != j +template +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 +void input_iterator_test(Iterator i, T v1, T v2) +{ + Iterator i1(i); + + assert(i == i1); + assert(!(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; + // + // assert(i != i2); + // assert(!(i == i2)); + + assert(*i1 == v1); + assert(*i == v1); + + // we cannot test for equivalence of (void)++i & (void)i++ + // as i is only guaranteed to be single pass. + assert(*i++ == v1); + + i1 = i; + + assert(i == i1); + assert(!(i != i1)); + + assert(*i1 == v2); + assert(*i == v2); + + // i is dereferencable, so it must be incrementable. + ++i; + + // how to test for operator-> ? +} + +// how to test output iterator? + + +template struct lvalue_test +{ + template static void check(Iterator) + { +# ifndef BOOST_NO_STD_ITERATOR_TRAITS + typedef typename std::iterator_traits::reference reference; + typedef typename std::iterator_traits::value_type value_type; +# else + typedef typename Iterator::reference reference; + typedef typename Iterator::value_type value_type; +# endif + BOOST_STATIC_ASSERT(boost::is_reference::value); + BOOST_STATIC_ASSERT((boost::is_same::value + || boost::is_same::value + )); + } +}; + +# ifdef BOOST_NO_STD_ITERATOR_TRAITS +template <> struct lvalue_test { + template static void check(T) {} +}; +#endif + +template +void forward_iterator_test(Iterator i, T v1, T v2) +{ + input_iterator_test(i, v1, v2); + + Iterator i1 = i, i2 = i; + + assert(i == i1++); + assert(i != ++i2); + + trivial_iterator_test(i, i1, v1); + trivial_iterator_test(i, i2, v1); + + ++i; + assert(i == i1); + assert(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(__BORLANDC__) || (__BORLANDC__ > 0x551) + lvalue_test<(boost::is_pointer::value)>::check(i); +#endif +} + +// Preconditions: *i == v1, *++i == v2 +template +void bidirectional_iterator_test(Iterator i, T v1, T v2) +{ + forward_iterator_test(i, v1, v2); + ++i; + + Iterator i1 = i, i2 = i; + + assert(i == i1--); + assert(i != --i2); + + trivial_iterator_test(i, i1, v2); + trivial_iterator_test(i, i2, v2); + + --i; + assert(i == i1); + assert(i == i2); + ++i1; + ++i2; + + trivial_iterator_test(i, i1, v1); + trivial_iterator_test(i, i2, v1); +} + +// mutable_bidirectional_iterator_test + +template struct undefined; + +// Preconditions: [i,i+N) is a valid range +template +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 boost::detail::iterator_traits::value_type value_type; + + for (c = 0; c < N-1; ++c) { + assert(i == j + c); + assert(*i == vals[c]); + assert(*i == boost::implicit_cast(j[c])); + assert(*i == *(j + c)); + assert(*i == *(c + j)); + ++i; + assert(i > j); + assert(i >= j); + assert(j <= i); + assert(j < i); + } + + Iterator k = j + N - 1; + for (c = 0; c < N-1; ++c) { + assert(i == k - c); + assert(*i == vals[N - 1 - c]); + assert(*i == boost::implicit_cast(j[N - 1 - c])); + Iterator q = k - c; + assert(*i == *q); + assert(i > j); + assert(i >= j); + assert(j <= i); + assert(j < i); + --i; + } +} + +// Precondition: i != j +template +void const_nonconst_iterator_test(Iterator i, ConstIterator j) +{ + assert(i != j); + assert(j != i); + + ConstIterator k(i); + assert(k == i); + assert(i == k); + + k = i; + assert(k == i); + assert(i == k); +} + +} // namespace boost + +#endif // BOOST_ITERATOR_TESTS_HPP diff --git a/deal.II/contrib/boost/include/boost/pending/lowest_bit.hpp b/deal.II/contrib/boost/include/boost/pending/lowest_bit.hpp new file mode 100644 index 0000000000..449a22e302 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/lowest_bit.hpp @@ -0,0 +1,41 @@ +// ------------------------------------- +// lowest_bit.hpp +// +// Position of the lowest bit 'on' +// +// (C) Copyright Gennaro Prota 2003 - 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) +// +// ------------------------------------------------------ +// +// $Id: lowest_bit.hpp 41369 2007-11-25 18:07:19Z bemandawes $ + +#ifndef BOOST_LOWEST_BIT_HPP_GP_20030301 +#define BOOST_LOWEST_BIT_HPP_GP_20030301 + +#include +#include "boost/pending/integer_log2.hpp" + + +namespace boost { + + template + int lowest_bit(T x) { + + assert(x >= 1); // PRE + + // clear all bits on except the rightmost one, + // then calculate the logarithm base 2 + // + return boost::integer_log2( x - ( x & (x-1) ) ); + + } + + +} + + +#endif // include guard diff --git a/deal.II/contrib/boost/include/boost/pending/mutable_heap.hpp b/deal.II/contrib/boost/include/boost/pending/mutable_heap.hpp new file mode 100644 index 0000000000..bbc8188190 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/mutable_heap.hpp @@ -0,0 +1,64 @@ +// +//======================================================================= +// 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 + 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 + 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 + inline void update_heap(TreeNode x, const Compare& comp, ExternalData& edata) { + x = down_heap(x, comp, edata); + (void)up_heap(x, comp, edata); + } + +} +#endif diff --git a/deal.II/contrib/boost/include/boost/pending/mutable_queue.hpp b/deal.II/contrib/boost/include/boost/pending/mutable_queue.hpp new file mode 100644 index 0000000000..b0f1073f12 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/mutable_queue.hpp @@ -0,0 +1,135 @@ +// +//======================================================================= +// 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 +#include +#include +#include +#include +#include +#include +#include + +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 Comp = std::less, + 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 adstl::array_binary_tree_node Node; +#else + typedef adstl::array_binary_tree_node Node; +#endif + typedef adstl::compare_array_node Compare; + typedef std::vector 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 + 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 diff --git a/deal.II/contrib/boost/include/boost/pending/property.hpp b/deal.II/contrib/boost/include/boost/pending/property.hpp new file mode 100644 index 0000000000..f4d2cb91ea --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/property.hpp @@ -0,0 +1,132 @@ +// (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 + +namespace boost { + + struct no_property { + typedef no_property tag_type; + typedef no_property next_type; + typedef no_property value_type; + enum { num = 0 }; + typedef void kind; + }; + + template + struct property : public Base { + typedef Base next_type; + typedef Tag tag_type; + typedef T value_type; +#if BOOST_WORKAROUND (__GNUC__, < 3) + property() { } +#else + property() : m_value() { } +#endif + property(const T& v) : m_value(v) { } + property(const T& v, const Base& b) : Base(b), m_value(v) { } + // copy constructor and assignment operator will be generated by compiler + + T m_value; + }; + + // 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 + struct property_kind { + typedef typename PropertyTag::kind type; + }; + + template + struct has_property { + BOOST_STATIC_CONSTANT(bool, value = true); + typedef true_type type; + }; + template <> + struct has_property { + BOOST_STATIC_CONSTANT(bool, value = false); + typedef false_type type; + }; + +} // namespace boost + +#include + +namespace boost { + + template + struct property_value { +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + typedef typename detail::build_property_tag_value_alist::type AList; + typedef typename detail::extract_value::type type; +#else + typedef typename detail::build_property_tag_value_alist::type AList; + typedef typename detail::ev_selector::type Extractor; + typedef typename Extractor::template bind_::type type; +#endif + }; + + template + inline typename property_value, Tag2>::type& + get_property_value(property& p, Tag2 tag2) { + BOOST_STATIC_CONSTANT(bool, + match = (detail::same_property::value)); + typedef property Prop; + typedef typename property_value::type T2; + T2* t2 = 0; + typedef detail::property_value_dispatch Dispatcher; + return Dispatcher::get_value(p, t2, tag2); + } + template + inline + const typename property_value, Tag2>::type& + get_property_value(const property& p, Tag2 tag2) { + BOOST_STATIC_CONSTANT(bool, + match = (detail::same_property::value)); + typedef property Prop; + typedef typename property_value::type T2; + T2* t2 = 0; + typedef detail::property_value_dispatch Dispatcher; + return Dispatcher::const_get_value(p, t2, tag2); + } + + namespace detail { +#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) + template + struct retag_property_list + { + typedef property type; + typedef FinalType retagged; + }; + + template + struct retag_property_list > + { + private: + typedef retag_property_list next; + + public: + typedef property type; + typedef typename next::retagged retagged; + }; + + template + struct retag_property_list + { + typedef no_property type; + typedef no_property retagged; + }; +#endif + } +} // namesapce boost + +#endif /* BOOST_PROPERTY_HPP */ diff --git a/deal.II/contrib/boost/include/boost/pending/property_serialize.hpp b/deal.II/contrib/boost/include/boost/pending/property_serialize.hpp new file mode 100644 index 0000000000..5ec9c984fa --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/property_serialize.hpp @@ -0,0 +1,28 @@ +// (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 + +#include +#include + +namespace boost { + template + inline void serialize(Archive&, no_property&, const unsigned int) { } + + template + void + serialize(Archive& ar, property& prop, + const unsigned int version) + { + ar & serialization::make_nvp( "property_base" , boost::serialization::base_object(prop) ); + ar & serialization::make_nvp( "property_value" , prop.m_value ); + } +} // end namespace boost + +#endif // BOOST_PROPERTY_SERIALIZE_HPP diff --git a/deal.II/contrib/boost/include/boost/pending/queue.hpp b/deal.II/contrib/boost/include/boost/pending/queue.hpp new file mode 100644 index 0000000000..f5f5b6336e --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/queue.hpp @@ -0,0 +1,118 @@ +// (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 +#include + +namespace boost { + +template > +class queue; + +template +inline bool operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&); + +template +inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&); + + +template +class queue { + +#ifndef BOOST_NO_MEMBER_TEMPLATE_FRIENDS + template + friend bool operator== (const queue<_Tp1, _Seq1>&, + const queue<_Tp1, _Seq1>&); + template + 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 +bool +operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) +{ + return __x.c == __y.c; +} + +template +bool +operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) +{ + return __x.c < __y.c; +} + +template +bool +operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) +{ + return !(__x == __y); +} + +template +bool +operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) +{ + return __y < __x; +} + +template +bool +operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) +{ + return !(__y < __x); +} + +template +bool +operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) +{ + return !(__x < __y); +} + +template +inline void +swap(queue<_Tp, _Sequence>& __x, queue<_Tp, _Sequence>& __y) +{ __x.swap(__y); } + +} /* namespace boost */ + +#endif /* BOOST_QUEUE_HPP */ diff --git a/deal.II/contrib/boost/include/boost/pending/relaxed_heap.hpp b/deal.II/contrib/boost/include/boost/pending/relaxed_heap.hpp new file mode 100644 index 0000000000..727009a6a4 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/relaxed_heap.hpp @@ -0,0 +1,644 @@ +// 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 +#ifndef BOOST_RELAXED_HEAP_HEADER +#define BOOST_RELAXED_HEAP_HEADER + +#include +#include +#include +#include +#include // for CHAR_BIT +#include + +#ifdef BOOST_RELAXED_HEAP_DEBUG +# include +#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 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; + + /** + * 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(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)] != 0); + 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 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 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 > 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 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 diff --git a/deal.II/contrib/boost/include/boost/pending/stringtok.hpp b/deal.II/contrib/boost/include/boost/pending/stringtok.hpp new file mode 100644 index 0000000000..3b8e5e3249 --- /dev/null +++ b/deal.II/contrib/boost/include/boost/pending/stringtok.hpp @@ -0,0 +1,116 @@ +// (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 + * 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 and deque 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 ls; + * stringtok (ls, " this \t is\t\n a test "); + * for (list::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 +#include // 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 +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 -- 2.39.5