diff options
24 files changed, 4887 insertions, 0 deletions
diff --git a/ext/boost/iterator/counting_iterator.hpp b/ext/boost/iterator/counting_iterator.hpp new file mode 100644 index 0000000000..1298a31f55 --- /dev/null +++ b/ext/boost/iterator/counting_iterator.hpp @@ -0,0 +1,215 @@ +// 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) +#ifndef COUNTING_ITERATOR_DWA200348_HPP +# define COUNTING_ITERATOR_DWA200348_HPP + +# include <boost/iterator/iterator_adaptor.hpp> +# include <boost/detail/numeric_traits.hpp> +# include <boost/mpl/bool.hpp> +# include <boost/mpl/if.hpp> +# include <boost/mpl/identity.hpp> +# include <boost/mpl/eval_if.hpp> + +namespace boost { + +template < + class Incrementable + , class CategoryOrTraversal + , class Difference +> +class counting_iterator; + +namespace detail +{ + // Try to detect numeric types at compile time in ways compatible + // with the limitations of the compiler and library. + template <class T> + struct is_numeric_impl + { + // For a while, this wasn't true, but we rely on it below. This is a regression assert. + BOOST_STATIC_ASSERT(::boost::is_integral<char>::value); + +# ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS + + BOOST_STATIC_CONSTANT(bool, value = std::numeric_limits<T>::is_specialized); + +# else + +# if !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551)) + BOOST_STATIC_CONSTANT( + bool, value = ( + boost::is_convertible<int,T>::value + && boost::is_convertible<T,int>::value + )); +# else + BOOST_STATIC_CONSTANT(bool, value = ::boost::is_arithmetic<T>::value); +# endif + +# endif + }; + + template <class T> + struct is_numeric + : mpl::bool_<(::boost::detail::is_numeric_impl<T>::value)> + {}; + +# if defined(BOOST_HAS_LONG_LONG) + template <> + struct is_numeric< ::boost::long_long_type> + : mpl::true_ {}; + + template <> + struct is_numeric< ::boost::ulong_long_type> + : mpl::true_ {}; +# endif + + // Some compilers fail to have a numeric_limits specialization + template <> + struct is_numeric<wchar_t> + : mpl::true_ {}; + + template <class T> + struct numeric_difference + { + typedef typename boost::detail::numeric_traits<T>::difference_type type; + }; + + BOOST_STATIC_ASSERT(is_numeric<int>::value); + + template <class Incrementable, class CategoryOrTraversal, class Difference> + struct counting_iterator_base + { + typedef typename detail::ia_dflt_help< + CategoryOrTraversal + , mpl::eval_if< + is_numeric<Incrementable> + , mpl::identity<random_access_traversal_tag> + , iterator_traversal<Incrementable> + > + >::type traversal; + + typedef typename detail::ia_dflt_help< + Difference + , mpl::eval_if< + is_numeric<Incrementable> + , numeric_difference<Incrementable> + , iterator_difference<Incrementable> + > + >::type difference; + + typedef iterator_adaptor< + counting_iterator<Incrementable, CategoryOrTraversal, Difference> // self + , Incrementable // Base + , Incrementable // Value +# ifndef BOOST_ITERATOR_REF_CONSTNESS_KILLS_WRITABILITY + const // MSVC won't strip this. Instead we enable Thomas' + // criterion (see boost/iterator/detail/facade_iterator_category.hpp) +# endif + , traversal + , Incrementable const& // reference + , difference + > type; + }; + + // Template class distance_policy_select -- choose a policy for computing the + // distance between counting_iterators at compile-time based on whether or not + // the iterator wraps an integer or an iterator, using "poor man's partial + // specialization". + + template <bool is_integer> struct distance_policy_select; + + // A policy for wrapped iterators + template <class Difference, class Incrementable1, class Incrementable2> + struct iterator_distance + { + static Difference distance(Incrementable1 x, Incrementable2 y) + { + return y - x; + } + }; + + // A policy for wrapped numbers + template <class Difference, class Incrementable1, class Incrementable2> + struct number_distance + { + static Difference distance(Incrementable1 x, Incrementable2 y) + { + return numeric_distance(x, y); + } + }; +} + +template < + class Incrementable + , class CategoryOrTraversal = use_default + , class Difference = use_default +> +class counting_iterator + : public detail::counting_iterator_base< + Incrementable, CategoryOrTraversal, Difference + >::type +{ + typedef typename detail::counting_iterator_base< + Incrementable, CategoryOrTraversal, Difference + >::type super_t; + + friend class iterator_core_access; + + public: + typedef typename super_t::difference_type difference_type; + + counting_iterator() { } + + counting_iterator(counting_iterator const& rhs) : super_t(rhs.base()) {} + + counting_iterator(Incrementable x) + : super_t(x) + { + } + +# if 0 + template<class OtherIncrementable> + counting_iterator( + counting_iterator<OtherIncrementable, CategoryOrTraversal, Difference> const& t + , typename enable_if_convertible<OtherIncrementable, Incrementable>::type* = 0 + ) + : super_t(t.base()) + {} +# endif + + private: + + typename super_t::reference dereference() const + { + return this->base_reference(); + } + + template <class OtherIncrementable> + difference_type + distance_to(counting_iterator<OtherIncrementable, CategoryOrTraversal, Difference> const& y) const + { + typedef typename mpl::if_< + detail::is_numeric<Incrementable> + , detail::number_distance<difference_type, Incrementable, OtherIncrementable> + , detail::iterator_distance<difference_type, Incrementable, OtherIncrementable> + >::type d; + + return d::distance(this->base(), y.base()); + } +}; + +// Manufacture a counting iterator for an arbitrary incrementable type +template <class Incrementable> +inline counting_iterator<Incrementable> +make_counting_iterator(Incrementable x) +{ + typedef counting_iterator<Incrementable> result_t; + return result_t(x); +} + + +} // namespace boost::iterator + +#endif // COUNTING_ITERATOR_DWA200348_HPP diff --git a/ext/boost/iterator/detail/any_conversion_eater.hpp b/ext/boost/iterator/detail/any_conversion_eater.hpp new file mode 100644 index 0000000000..25fa644889 --- /dev/null +++ b/ext/boost/iterator/detail/any_conversion_eater.hpp @@ -0,0 +1,19 @@ +// Copyright David Abrahams 2003. 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) +#ifndef ANY_CONVERSION_EATER_DWA20031117_HPP +# define ANY_CONVERSION_EATER_DWA20031117_HPP + +namespace boost { namespace detail { + +// This type can be used in traits to "eat" up the one user-defined +// implicit conversion allowed. +struct any_conversion_eater +{ + template <class T> + any_conversion_eater(T const&); +}; + +}} // namespace boost::detail + +#endif // ANY_CONVERSION_EATER_DWA20031117_HPP diff --git a/ext/boost/iterator/detail/config_def.hpp b/ext/boost/iterator/detail/config_def.hpp new file mode 100644 index 0000000000..fa8d667d97 --- /dev/null +++ b/ext/boost/iterator/detail/config_def.hpp @@ -0,0 +1,137 @@ +// (C) Copyright David Abrahams 2002. +// (C) Copyright Jeremy Siek 2002. +// (C) Copyright Thomas Witt 2002. +// 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) + +// no include guard multiple inclusion intended + +// +// This is a temporary workaround until the bulk of this is +// available in boost config. +// 23/02/03 thw +// + +#include <boost/config.hpp> // for prior +#include <boost/detail/workaround.hpp> + +#ifdef BOOST_ITERATOR_CONFIG_DEF +# error you have nested config_def #inclusion. +#else +# define BOOST_ITERATOR_CONFIG_DEF +#endif + +// We enable this always now. Otherwise, the simple case in +// libs/iterator/test/constant_iterator_arrow.cpp fails to compile +// because the operator-> return is improperly deduced as a non-const +// pointer. +#if 1 || defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \ + || BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x531)) + +// Recall that in general, compilers without partial specialization +// can't strip constness. Consider counting_iterator, which normally +// passes a const Value to iterator_facade. As a result, any code +// which makes a std::vector of the iterator's value_type will fail +// when its allocator declares functions overloaded on reference and +// const_reference (the same type). +// +// Furthermore, Borland 5.5.1 drops constness in enough ways that we +// end up using a proxy for operator[] when we otherwise shouldn't. +// Using reference constness gives it an extra hint that it can +// return the value_type from operator[] directly, but is not +// strictly necessary. Not sure how best to resolve this one. + +# define BOOST_ITERATOR_REF_CONSTNESS_KILLS_WRITABILITY 1 + +#endif + +#if BOOST_WORKAROUND(BOOST_MSVC, <= 1300) \ + || BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x5A0)) \ + || (BOOST_WORKAROUND(BOOST_INTEL_CXX_VERSION, <= 700) && defined(_MSC_VER)) \ + || BOOST_WORKAROUND(__DECCXX_VER, BOOST_TESTED_AT(60590042)) \ + || BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x590)) + +# define BOOST_NO_LVALUE_RETURN_DETECTION + +# if 0 // test code + struct v {}; + + typedef char (&no)[3]; + + template <class T> + no foo(T const&, ...); + + template <class T> + char foo(T&, int); + + + struct value_iterator + { + v operator*() const; + }; + + template <class T> + struct lvalue_deref_helper + { + static T& x; + enum { value = (sizeof(foo(*x,0)) == 1) }; + }; + + int z2[(lvalue_deref_helper<v*>::value == 1) ? 1 : -1]; + int z[(lvalue_deref_helper<value_iterator>::value) == 1 ? -1 : 1 ]; +# endif + +#endif + +#if BOOST_WORKAROUND(__MWERKS__, <=0x2407) +# define BOOST_NO_IS_CONVERTIBLE // "is_convertible doesn't work for simple types" +#endif + +#if BOOST_WORKAROUND(__GNUC__, == 2) \ + || BOOST_WORKAROUND(__GNUC__, == 3) && BOOST_WORKAROUND(__GNUC_MINOR__, < 4) && !defined(__EDG_VERSION__) \ + || BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551)) +# define BOOST_NO_IS_CONVERTIBLE_TEMPLATE // The following program fails to compile: + +# if 0 // test code + #include <boost/type_traits/is_convertible.hpp> + template <class T> + struct foo + { + foo(T); + + template <class U> + foo(foo<U> const& other) : p(other.p) { } + + T p; + }; + + bool x = boost::is_convertible<foo<int const*>, foo<int*> >::value; +# endif + +#endif + + +#if !defined(BOOST_MSVC) && (defined(BOOST_NO_SFINAE) || defined(BOOST_NO_IS_CONVERTIBLE) || defined(BOOST_NO_IS_CONVERTIBLE_TEMPLATE)) +# define BOOST_NO_STRICT_ITERATOR_INTEROPERABILITY +#endif + +# if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300) +# define BOOST_ARG_DEPENDENT_TYPENAME typename +# else +# define BOOST_ARG_DEPENDENT_TYPENAME +# endif + +# if BOOST_WORKAROUND(__GNUC__, == 2) && BOOST_WORKAROUND(__GNUC_MINOR__, BOOST_TESTED_AT(95)) \ + || BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) + +// GCC-2.95 eagerly instantiates templated constructors and conversion +// operators in convertibility checks, causing premature errors. +// +// Borland's problems are harder to diagnose due to lack of an +// instantiation stack backtrace. They may be due in part to the fact +// that it drops cv-qualification willy-nilly in templates. +# define BOOST_NO_ONE_WAY_ITERATOR_INTEROP +# endif + +// no include guard; multiple inclusion intended diff --git a/ext/boost/iterator/detail/config_undef.hpp b/ext/boost/iterator/detail/config_undef.hpp new file mode 100644 index 0000000000..9dcd1d525f --- /dev/null +++ b/ext/boost/iterator/detail/config_undef.hpp @@ -0,0 +1,25 @@ +// (C) Copyright Thomas Witt 2002. +// 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) + +// no include guard multiple inclusion intended + +// +// This is a temporary workaround until the bulk of this is +// available in boost config. +// 23/02/03 thw +// + +#undef BOOST_NO_IS_CONVERTIBLE +#undef BOOST_NO_IS_CONVERTIBLE_TEMPLATE +#undef BOOST_NO_STRICT_ITERATOR_INTEROPERABILITY +#undef BOOST_ARG_DEPENDENT_TYPENAME +#undef BOOST_NO_LVALUE_RETURN_DETECTION +#undef BOOST_NO_ONE_WAY_ITERATOR_INTEROP + +#ifdef BOOST_ITERATOR_CONFIG_DEF +# undef BOOST_ITERATOR_CONFIG_DEF +#else +# error missing or nested #include config_def +#endif diff --git a/ext/boost/iterator/detail/enable_if.hpp b/ext/boost/iterator/detail/enable_if.hpp new file mode 100644 index 0000000000..0fd36fc4bc --- /dev/null +++ b/ext/boost/iterator/detail/enable_if.hpp @@ -0,0 +1,86 @@ +// (C) Copyright David Abrahams 2002. +// (C) Copyright Jeremy Siek 2002. +// (C) Copyright Thomas Witt 2002. +// 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_ENABLE_IF_23022003THW_HPP +#define BOOST_ENABLE_IF_23022003THW_HPP + +#include <boost/detail/workaround.hpp> +#include <boost/mpl/identity.hpp> + +#include <boost/iterator/detail/config_def.hpp> + +// +// Boost iterators uses its own enable_if cause we need +// special semantics for deficient compilers. +// 23/02/03 thw +// + +namespace boost +{ + + namespace iterators + { + // + // Base machinery for all kinds of enable if + // + template<bool> + struct enabled + { + template<typename T> + struct base + { + typedef T type; + }; + }; + + // + // For compilers that don't support "Substitution Failure Is Not An Error" + // enable_if falls back to always enabled. See comments + // on operator implementation for consequences. + // + template<> + struct enabled<false> + { + template<typename T> + struct base + { +#ifdef BOOST_NO_SFINAE + + typedef T type; + + // This way to do it would give a nice error message containing + // invalid overload, but has the big disadvantage that + // there is no reference to user code in the error message. + // + // struct invalid_overload; + // typedef invalid_overload type; + // +#endif + }; + }; + + + template <class Cond, + class Return> + struct enable_if +# if !defined(BOOST_NO_SFINAE) && !defined(BOOST_NO_IS_CONVERTIBLE) + : enabled<(Cond::value)>::template base<Return> +# else + : mpl::identity<Return> +# endif + { +# if BOOST_WORKAROUND(BOOST_MSVC, < 1300) + typedef Return type; +# endif + }; + + } // namespace iterators + +} // namespace boost + +#include <boost/iterator/detail/config_undef.hpp> + +#endif // BOOST_ENABLE_IF_23022003THW_HPP diff --git a/ext/boost/iterator/detail/facade_iterator_category.hpp b/ext/boost/iterator/detail/facade_iterator_category.hpp new file mode 100644 index 0000000000..2c4771d5aa --- /dev/null +++ b/ext/boost/iterator/detail/facade_iterator_category.hpp @@ -0,0 +1,200 @@ +// Copyright David Abrahams 2003. 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) +#ifndef FACADE_ITERATOR_CATEGORY_DWA20031118_HPP +# define FACADE_ITERATOR_CATEGORY_DWA20031118_HPP + +# include <boost/iterator/iterator_categories.hpp> + +# include <boost/mpl/or.hpp> // used in iterator_tag inheritance logic +# include <boost/mpl/and.hpp> +# include <boost/mpl/if.hpp> +# include <boost/mpl/eval_if.hpp> +# include <boost/mpl/identity.hpp> +# include <boost/mpl/assert.hpp> + +# include <boost/type_traits/is_same.hpp> +# include <boost/type_traits/is_const.hpp> +# include <boost/type_traits/is_reference.hpp> +# include <boost/type_traits/is_convertible.hpp> + +# include <boost/type_traits/is_same.hpp> + +# include <boost/iterator/detail/config_def.hpp> // try to keep this last + +# ifdef BOOST_ITERATOR_REF_CONSTNESS_KILLS_WRITABILITY +# include <boost/detail/indirect_traits.hpp> +# endif + +// +// iterator_category deduction for iterator_facade +// + +// forward declaration +namespace boost { struct use_default; } + +namespace boost { namespace detail { + +struct input_output_iterator_tag + : std::input_iterator_tag +{ + // Using inheritance for only input_iterator_tag helps to avoid + // ambiguities when a stdlib implementation dispatches on a + // function which is overloaded on both input_iterator_tag and + // output_iterator_tag, as STLPort does, in its __valid_range + // function. I claim it's better to avoid the ambiguity in these + // cases. + operator std::output_iterator_tag() const + { + return std::output_iterator_tag(); + } +}; + +// +// True iff the user has explicitly disabled writability of this +// iterator. Pass the iterator_facade's Value parameter and its +// nested ::reference type. +// +template <class ValueParam, class Reference> +struct iterator_writability_disabled +# ifdef BOOST_ITERATOR_REF_CONSTNESS_KILLS_WRITABILITY // Adding Thomas' logic? + : mpl::or_< + is_const<Reference> + , boost::detail::indirect_traits::is_reference_to_const<Reference> + , is_const<ValueParam> + > +# else + : is_const<ValueParam> +# endif +{}; + + +// +// Convert an iterator_facade's traversal category, Value parameter, +// and ::reference type to an appropriate old-style category. +// +// If writability has been disabled per the above metafunction, the +// result will not be convertible to output_iterator_tag. +// +// Otherwise, if Traversal == single_pass_traversal_tag, the following +// conditions will result in a tag that is convertible both to +// input_iterator_tag and output_iterator_tag: +// +// 1. Reference is a reference to non-const +// 2. Reference is not a reference and is convertible to Value +// +template <class Traversal, class ValueParam, class Reference> +struct iterator_facade_default_category + : mpl::eval_if< + mpl::and_< + is_reference<Reference> + , is_convertible<Traversal,forward_traversal_tag> + > + , mpl::eval_if< + is_convertible<Traversal,random_access_traversal_tag> + , mpl::identity<std::random_access_iterator_tag> + , mpl::if_< + is_convertible<Traversal,bidirectional_traversal_tag> + , std::bidirectional_iterator_tag + , std::forward_iterator_tag + > + > + , typename mpl::eval_if< + mpl::and_< + is_convertible<Traversal, single_pass_traversal_tag> + + // check for readability + , is_convertible<Reference, ValueParam> + > + , mpl::identity<std::input_iterator_tag> + , mpl::identity<Traversal> + > + > +{ +}; + +// True iff T is convertible to an old-style iterator category. +template <class T> +struct is_iterator_category + : mpl::or_< + is_convertible<T,std::input_iterator_tag> + , is_convertible<T,std::output_iterator_tag> + > +{ +}; + +template <class T> +struct is_iterator_traversal + : is_convertible<T,incrementable_traversal_tag> +{}; + +// +// A composite iterator_category tag convertible to Category (a pure +// old-style category) and Traversal (a pure traversal tag). +// Traversal must be a strict increase of the traversal power given by +// Category. +// +template <class Category, class Traversal> +struct iterator_category_with_traversal + : Category, Traversal +{ +# if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300) + // Make sure this isn't used to build any categories where + // convertibility to Traversal is redundant. Should just use the + // Category element in that case. + BOOST_MPL_ASSERT_NOT(( + is_convertible< + typename iterator_category_to_traversal<Category>::type + , Traversal + >)); + + BOOST_MPL_ASSERT((is_iterator_category<Category>)); + BOOST_MPL_ASSERT_NOT((is_iterator_category<Traversal>)); + BOOST_MPL_ASSERT_NOT((is_iterator_traversal<Category>)); +# if !BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1310)) + BOOST_MPL_ASSERT((is_iterator_traversal<Traversal>)); +# endif +# endif +}; + +// Computes an iterator_category tag whose traversal is Traversal and +// which is appropriate for an iterator +template <class Traversal, class ValueParam, class Reference> +struct facade_iterator_category_impl +{ +# if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300) + BOOST_MPL_ASSERT_NOT((is_iterator_category<Traversal>)); +# endif + + typedef typename iterator_facade_default_category< + Traversal,ValueParam,Reference + >::type category; + + typedef typename mpl::if_< + is_same< + Traversal + , typename iterator_category_to_traversal<category>::type + > + , category + , iterator_category_with_traversal<category,Traversal> + >::type type; +}; + +// +// Compute an iterator_category for iterator_facade +// +template <class CategoryOrTraversal, class ValueParam, class Reference> +struct facade_iterator_category + : mpl::eval_if< + is_iterator_category<CategoryOrTraversal> + , mpl::identity<CategoryOrTraversal> // old-style categories are fine as-is + , facade_iterator_category_impl<CategoryOrTraversal,ValueParam,Reference> + > +{ +}; + +}} // namespace boost::detail + +# include <boost/iterator/detail/config_undef.hpp> + +#endif // FACADE_ITERATOR_CATEGORY_DWA20031118_HPP diff --git a/ext/boost/iterator/detail/minimum_category.hpp b/ext/boost/iterator/detail/minimum_category.hpp new file mode 100644 index 0000000000..96501ddd46 --- /dev/null +++ b/ext/boost/iterator/detail/minimum_category.hpp @@ -0,0 +1,116 @@ +// Copyright David Abrahams 2003. 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) +#ifndef MINIMUM_CATEGORY_DWA20031119_HPP +# define MINIMUM_CATEGORY_DWA20031119_HPP + +# include <boost/type_traits/is_convertible.hpp> +# include <boost/type_traits/is_same.hpp> + +# include <boost/mpl/aux_/lambda_support.hpp> + +namespace boost { namespace detail { +// +// Returns the minimum category type or error_type +// if T1 and T2 are unrelated. +// +// For compilers not supporting is_convertible this only +// works with the new boost return and traversal category +// types. The exact boost _types_ are required. No derived types +// will work. +// +// +template <bool GreaterEqual, bool LessEqual> +struct minimum_category_impl +# if BOOST_WORKAROUND(BOOST_MSVC, < 1300) +{ + template <class T1, class T2> struct apply + { + typedef T2 type; + }; + typedef void type; +} +# endif +; + +template <class T1, class T2> +struct error_not_related_by_convertibility; + +template <> +struct minimum_category_impl<true,false> +{ + template <class T1, class T2> struct apply + { + typedef T2 type; + }; +}; + +template <> +struct minimum_category_impl<false,true> +{ + template <class T1, class T2> struct apply + { + typedef T1 type; + }; +}; + +template <> +struct minimum_category_impl<true,true> +{ + template <class T1, class T2> struct apply + { + BOOST_STATIC_ASSERT((is_same<T1,T2>::value)); + typedef T1 type; + }; +}; + +template <> +struct minimum_category_impl<false,false> +{ + template <class T1, class T2> struct apply + : error_not_related_by_convertibility<T1,T2> + { + }; +}; + +template <class T1 = mpl::_1, class T2 = mpl::_2> +struct minimum_category +{ + typedef minimum_category_impl< +# if BOOST_WORKAROUND(BOOST_MSVC, < 1300) // ETI workaround + is_same<T2,int>::value || +# endif + ::boost::is_convertible<T1,T2>::value + , ::boost::is_convertible<T2,T1>::value +# if BOOST_WORKAROUND(BOOST_MSVC, < 1300) // ETI workaround + || is_same<T1,int>::value +# endif + > outer; + + typedef typename outer::template apply<T1,T2> inner; + typedef typename inner::type type; + + BOOST_MPL_AUX_LAMBDA_SUPPORT(2,minimum_category,(T1,T2)) +}; + +template <> +struct minimum_category<mpl::_1,mpl::_2> +{ + template <class T1, class T2> + struct apply : minimum_category<T1,T2> + {}; + + BOOST_MPL_AUX_LAMBDA_SUPPORT_SPEC(2,minimum_category,(mpl::_1,mpl::_2)) +}; + +# if BOOST_WORKAROUND(BOOST_MSVC, < 1300) // ETI workaround +template <> +struct minimum_category<int,int> +{ + typedef int type; +}; +# endif + +}} // namespace boost::detail + +#endif // MINIMUM_CATEGORY_DWA20031119_HPP diff --git a/ext/boost/iterator/filter_iterator.hpp b/ext/boost/iterator/filter_iterator.hpp new file mode 100644 index 0000000000..14d640bf09 --- /dev/null +++ b/ext/boost/iterator/filter_iterator.hpp @@ -0,0 +1,135 @@ +// (C) Copyright David Abrahams 2002. +// (C) Copyright Jeremy Siek 2002. +// (C) Copyright Thomas Witt 2002. +// 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_FILTER_ITERATOR_23022003THW_HPP +#define BOOST_FILTER_ITERATOR_23022003THW_HPP + +#include <boost/iterator.hpp> +#include <boost/iterator/iterator_adaptor.hpp> +#include <boost/iterator/iterator_categories.hpp> + +#include <boost/type_traits/is_class.hpp> +#include <boost/static_assert.hpp> + +namespace boost +{ + template <class Predicate, class Iterator> + class filter_iterator; + + namespace detail + { + template <class Predicate, class Iterator> + struct filter_iterator_base + { + typedef iterator_adaptor< + filter_iterator<Predicate, Iterator> + , Iterator + , use_default + , typename mpl::if_< + is_convertible< + typename iterator_traversal<Iterator>::type + , random_access_traversal_tag + > + , bidirectional_traversal_tag + , use_default + >::type + > type; + }; + } + + template <class Predicate, class Iterator> + class filter_iterator + : public detail::filter_iterator_base<Predicate, Iterator>::type + { + typedef typename detail::filter_iterator_base< + Predicate, Iterator + >::type super_t; + + friend class iterator_core_access; + + public: + filter_iterator() { } + + filter_iterator(Predicate f, Iterator x, Iterator end_ = Iterator()) + : super_t(x), m_predicate(f), m_end(end_) + { + satisfy_predicate(); + } + + filter_iterator(Iterator x, Iterator end_ = Iterator()) + : super_t(x), m_predicate(), m_end(end_) + { + // Pro8 is a little too aggressive about instantiating the + // body of this function. +#if !BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3003)) + // Don't allow use of this constructor if Predicate is a + // function pointer type, since it will be 0. + BOOST_STATIC_ASSERT(is_class<Predicate>::value); +#endif + satisfy_predicate(); + } + + template<class OtherIterator> + filter_iterator( + filter_iterator<Predicate, OtherIterator> const& t + , typename enable_if_convertible<OtherIterator, Iterator>::type* = 0 + ) + : super_t(t.base()), m_predicate(t.predicate()), m_end(t.end()) {} + + Predicate predicate() const { return m_predicate; } + + Iterator end() const { return m_end; } + + private: + void increment() + { + ++(this->base_reference()); + satisfy_predicate(); + } + + void decrement() + { + while(!this->m_predicate(*--(this->base_reference()))){}; + } + + void satisfy_predicate() + { + while (this->base() != this->m_end && !this->m_predicate(*this->base())) + ++(this->base_reference()); + } + + // Probably should be the initial base class so it can be + // optimized away via EBO if it is an empty class. + Predicate m_predicate; + Iterator m_end; + }; + + template <class Predicate, class Iterator> + filter_iterator<Predicate,Iterator> + make_filter_iterator(Predicate f, Iterator x, Iterator end = Iterator()) + { + return filter_iterator<Predicate,Iterator>(f,x,end); + } + + template <class Predicate, class Iterator> + filter_iterator<Predicate,Iterator> + make_filter_iterator( + typename iterators::enable_if< + is_class<Predicate> + , Iterator + >::type x + , Iterator end = Iterator() +#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) + , Predicate* = 0 +#endif + ) + { + return filter_iterator<Predicate,Iterator>(x,end); + } + +} // namespace boost + +#endif // BOOST_FILTER_ITERATOR_23022003THW_HPP diff --git a/ext/boost/iterator/indirect_iterator.hpp b/ext/boost/iterator/indirect_iterator.hpp new file mode 100644 index 0000000000..abff7e7634 --- /dev/null +++ b/ext/boost/iterator/indirect_iterator.hpp @@ -0,0 +1,139 @@ +// (C) Copyright David Abrahams 2002. +// (C) Copyright Jeremy Siek 2002. +// (C) Copyright Thomas Witt 2002. +// 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_ITERATOR_23022003THW_HPP +#define BOOST_INDIRECT_ITERATOR_23022003THW_HPP + +#include <boost/iterator.hpp> +#include <boost/iterator/iterator_adaptor.hpp> + +#include <boost/pointee.hpp> +#include <boost/indirect_reference.hpp> +#include <boost/detail/iterator.hpp> + +#include <boost/detail/indirect_traits.hpp> + +#include <boost/type_traits/is_same.hpp> +#include <boost/type_traits/add_reference.hpp> + +#include <boost/mpl/bool.hpp> +#include <boost/mpl/identity.hpp> +#include <boost/mpl/eval_if.hpp> +#include <boost/mpl/not.hpp> +#include <boost/mpl/has_xxx.hpp> + +#ifdef BOOST_MPL_CFG_NO_HAS_XXX +# include <boost/shared_ptr.hpp> +# include <boost/scoped_ptr.hpp> +# include <boost/mpl/bool.hpp> +# include <memory> +#endif + +#include <boost/iterator/detail/config_def.hpp> // must be last #include + +namespace boost +{ + template <class Iter, class Value, class Category, class Reference, class Difference> + class indirect_iterator; + + namespace detail + { + template <class Iter, class Value, class Category, class Reference, class Difference> + struct indirect_base + { + typedef typename iterator_traits<Iter>::value_type dereferenceable; + + typedef iterator_adaptor< + indirect_iterator<Iter, Value, Category, Reference, Difference> + , Iter + , typename ia_dflt_help< + Value, pointee<dereferenceable> + >::type + , Category + , typename ia_dflt_help< + Reference + , mpl::eval_if< + is_same<Value,use_default> + , indirect_reference<dereferenceable> + , add_reference<Value> + > + >::type + , Difference + > type; + }; + + template <> + struct indirect_base<int, int, int, int, int> {}; + } // namespace detail + + + template < + class Iterator + , class Value = use_default + , class Category = use_default + , class Reference = use_default + , class Difference = use_default + > + class indirect_iterator + : public detail::indirect_base< + Iterator, Value, Category, Reference, Difference + >::type + { + typedef typename detail::indirect_base< + Iterator, Value, Category, Reference, Difference + >::type super_t; + + friend class iterator_core_access; + + public: + indirect_iterator() {} + + indirect_iterator(Iterator iter) + : super_t(iter) {} + + template < + class Iterator2, class Value2, class Category2 + , class Reference2, class Difference2 + > + indirect_iterator( + indirect_iterator< + Iterator2, Value2, Category2, Reference2, Difference2 + > const& y + , typename enable_if_convertible<Iterator2, Iterator>::type* = 0 + ) + : super_t(y.base()) + {} + + private: + typename super_t::reference dereference() const + { +# if BOOST_WORKAROUND(__BORLANDC__, < 0x5A0 ) + return const_cast<super_t::reference>(**this->base()); +# else + return **this->base(); +# endif + } + }; + + template <class Iter> + inline + indirect_iterator<Iter> make_indirect_iterator(Iter x) + { + return indirect_iterator<Iter>(x); + } + + template <class Traits, class Iter> + inline + indirect_iterator<Iter,Traits> make_indirect_iterator(Iter x, Traits* = 0) + { + return indirect_iterator<Iter, Traits>(x); + } + +} // namespace boost + +#include <boost/iterator/detail/config_undef.hpp> + +#endif // BOOST_INDIRECT_ITERATOR_23022003THW_HPP diff --git a/ext/boost/iterator/interoperable.hpp b/ext/boost/iterator/interoperable.hpp new file mode 100644 index 0000000000..c13dd9b47b --- /dev/null +++ b/ext/boost/iterator/interoperable.hpp @@ -0,0 +1,50 @@ +// (C) Copyright David Abrahams 2002. +// (C) Copyright Jeremy Siek 2002. +// (C) Copyright Thomas Witt 2002. +// 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_INTEROPERABLE_23022003THW_HPP +# define BOOST_INTEROPERABLE_23022003THW_HPP + +# include <boost/mpl/bool.hpp> +# include <boost/mpl/or.hpp> + +# include <boost/type_traits/is_convertible.hpp> + +# include <boost/iterator/detail/config_def.hpp> // must appear last + +namespace boost +{ + + // + // Meta function that determines whether two + // iterator types are considered interoperable. + // + // Two iterator types A,B are considered interoperable if either + // A is convertible to B or vice versa. + // This interoperability definition is in sync with the + // standards requirements on constant/mutable container + // iterators (23.1 [lib.container.requirements]). + // + // For compilers that don't support is_convertible + // is_interoperable gives false positives. See comments + // on operator implementation for consequences. + // + template <typename A, typename B> + struct is_interoperable +# ifdef BOOST_NO_STRICT_ITERATOR_INTEROPERABILITY + : mpl::true_ +# else + : mpl::or_< + is_convertible< A, B > + , is_convertible< B, A > > +# endif + { + }; + +} // namespace boost + +# include <boost/iterator/detail/config_undef.hpp> + +#endif // BOOST_INTEROPERABLE_23022003THW_HPP diff --git a/ext/boost/iterator/is_lvalue_iterator.hpp b/ext/boost/iterator/is_lvalue_iterator.hpp new file mode 100644 index 0000000000..3beb90df6d --- /dev/null +++ b/ext/boost/iterator/is_lvalue_iterator.hpp @@ -0,0 +1,150 @@ +// Copyright David Abrahams 2003. 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) +#ifndef IS_LVALUE_ITERATOR_DWA2003112_HPP +# define IS_LVALUE_ITERATOR_DWA2003112_HPP + +#include <boost/iterator.hpp> + +#include <boost/detail/workaround.hpp> +#include <boost/detail/iterator.hpp> + +#include <boost/iterator/detail/any_conversion_eater.hpp> + +// should be the last #includes +#include <boost/type_traits/detail/bool_trait_def.hpp> +#include <boost/iterator/detail/config_def.hpp> + +#ifndef BOOST_NO_IS_CONVERTIBLE + +namespace boost { + +namespace detail +{ +#ifndef BOOST_NO_LVALUE_RETURN_DETECTION + // Calling lvalue_preserver( <expression>, 0 ) returns a reference + // to the expression's result if <expression> is an lvalue, or + // not_an_lvalue() otherwise. + struct not_an_lvalue {}; + + template <class T> + T& lvalue_preserver(T&, int); + + template <class U> + not_an_lvalue lvalue_preserver(U const&, ...); + +# define BOOST_LVALUE_PRESERVER(expr) detail::lvalue_preserver(expr,0) + +#else + +# define BOOST_LVALUE_PRESERVER(expr) expr + +#endif + + // Guts of is_lvalue_iterator. Value is the iterator's value_type + // and the result is computed in the nested rebind template. + template <class Value> + struct is_lvalue_iterator_impl + { + // Eat implicit conversions so we don't report true for things + // convertible to Value const& + struct conversion_eater + { + conversion_eater(Value&); + }; + + static char tester(conversion_eater, int); + static char (& tester(any_conversion_eater, ...) )[2]; + + template <class It> + struct rebind + { + static It& x; + + BOOST_STATIC_CONSTANT( + bool + , value = ( + sizeof( + is_lvalue_iterator_impl<Value>::tester( + BOOST_LVALUE_PRESERVER(*x), 0 + ) + ) == 1 + ) + ); + }; + }; + +#undef BOOST_LVALUE_PRESERVER + + // + // void specializations to handle std input and output iterators + // + template <> + struct is_lvalue_iterator_impl<void> + { + template <class It> + struct rebind : boost::mpl::false_ + {}; + }; + +#ifndef BOOST_NO_CV_VOID_SPECIALIZATIONS + template <> + struct is_lvalue_iterator_impl<const void> + { + template <class It> + struct rebind : boost::mpl::false_ + {}; + }; + + template <> + struct is_lvalue_iterator_impl<volatile void> + { + template <class It> + struct rebind : boost::mpl::false_ + {}; + }; + + template <> + struct is_lvalue_iterator_impl<const volatile void> + { + template <class It> + struct rebind : boost::mpl::false_ + {}; + }; +#endif + + // + // This level of dispatching is required for Borland. We might save + // an instantiation by removing it for others. + // + template <class It> + struct is_readable_lvalue_iterator_impl + : is_lvalue_iterator_impl< + BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<It>::value_type const + >::template rebind<It> + {}; + + template <class It> + struct is_non_const_lvalue_iterator_impl + : is_lvalue_iterator_impl< + BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<It>::value_type + >::template rebind<It> + {}; +} // namespace detail + +// Define the trait with full mpl lambda capability and various broken +// compiler workarounds +BOOST_TT_AUX_BOOL_TRAIT_DEF1( + is_lvalue_iterator,T,::boost::detail::is_readable_lvalue_iterator_impl<T>::value) + +BOOST_TT_AUX_BOOL_TRAIT_DEF1( + is_non_const_lvalue_iterator,T,::boost::detail::is_non_const_lvalue_iterator_impl<T>::value) + +} // namespace boost + +#endif + +#include <boost/iterator/detail/config_undef.hpp> +#include <boost/type_traits/detail/bool_trait_undef.hpp> + +#endif // IS_LVALUE_ITERATOR_DWA2003112_HPP diff --git a/ext/boost/iterator/is_readable_iterator.hpp b/ext/boost/iterator/is_readable_iterator.hpp new file mode 100644 index 0000000000..60d6ff07f5 --- /dev/null +++ b/ext/boost/iterator/is_readable_iterator.hpp @@ -0,0 +1,108 @@ +// Copyright David Abrahams 2003. 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) +#ifndef IS_READABLE_ITERATOR_DWA2003112_HPP +# define IS_READABLE_ITERATOR_DWA2003112_HPP + +#include <boost/mpl/bool.hpp> +#include <boost/detail/iterator.hpp> + +#include <boost/type_traits/detail/bool_trait_def.hpp> +#include <boost/iterator/detail/any_conversion_eater.hpp> + +// should be the last #include +#include <boost/iterator/detail/config_def.hpp> + +#ifndef BOOST_NO_IS_CONVERTIBLE + +namespace boost { + +namespace detail +{ + // Guts of is_readable_iterator. Value is the iterator's value_type + // and the result is computed in the nested rebind template. + template <class Value> + struct is_readable_iterator_impl + { + static char tester(Value&, int); + static char (& tester(any_conversion_eater, ...) )[2]; + + template <class It> + struct rebind + { + static It& x; + + BOOST_STATIC_CONSTANT( + bool + , value = ( + sizeof( + is_readable_iterator_impl<Value>::tester(*x, 1) + ) == 1 + ) + ); + }; + }; + +#undef BOOST_READABLE_PRESERVER + + // + // void specializations to handle std input and output iterators + // + template <> + struct is_readable_iterator_impl<void> + { + template <class It> + struct rebind : boost::mpl::false_ + {}; + }; + +#ifndef BOOST_NO_CV_VOID_SPECIALIZATIONS + template <> + struct is_readable_iterator_impl<const void> + { + template <class It> + struct rebind : boost::mpl::false_ + {}; + }; + + template <> + struct is_readable_iterator_impl<volatile void> + { + template <class It> + struct rebind : boost::mpl::false_ + {}; + }; + + template <> + struct is_readable_iterator_impl<const volatile void> + { + template <class It> + struct rebind : boost::mpl::false_ + {}; + }; +#endif + + // + // This level of dispatching is required for Borland. We might save + // an instantiation by removing it for others. + // + template <class It> + struct is_readable_iterator_impl2 + : is_readable_iterator_impl< + BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<It>::value_type const + >::template rebind<It> + {}; +} // namespace detail + +// Define the trait with full mpl lambda capability and various broken +// compiler workarounds +BOOST_TT_AUX_BOOL_TRAIT_DEF1( + is_readable_iterator,T,::boost::detail::is_readable_iterator_impl2<T>::value) + +} // namespace boost + +#endif + +#include <boost/iterator/detail/config_undef.hpp> + +#endif // IS_READABLE_ITERATOR_DWA2003112_HPP diff --git a/ext/boost/iterator/iterator_adaptor.hpp b/ext/boost/iterator/iterator_adaptor.hpp new file mode 100644 index 0000000000..27b08ff018 --- /dev/null +++ b/ext/boost/iterator/iterator_adaptor.hpp @@ -0,0 +1,371 @@ +// (C) Copyright David Abrahams 2002. +// (C) Copyright Jeremy Siek 2002. +// (C) Copyright Thomas Witt 2002. +// 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_ADAPTOR_23022003THW_HPP +#define BOOST_ITERATOR_ADAPTOR_23022003THW_HPP + +#include <boost/static_assert.hpp> +#include <boost/iterator.hpp> +#include <boost/detail/iterator.hpp> + +#include <boost/iterator/iterator_categories.hpp> +#include <boost/iterator/iterator_facade.hpp> +#include <boost/iterator/detail/enable_if.hpp> + +#include <boost/mpl/and.hpp> +#include <boost/mpl/not.hpp> +#include <boost/mpl/or.hpp> + +#include <boost/type_traits/is_same.hpp> +#include <boost/type_traits/is_convertible.hpp> + +#ifdef BOOST_ITERATOR_REF_CONSTNESS_KILLS_WRITABILITY +# include <boost/type_traits/remove_reference.hpp> + +# if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x610)) +# include <boost/type_traits/add_reference.hpp> +# endif + +#else +# include <boost/type_traits/add_reference.hpp> +#endif + +#include <boost/iterator/detail/config_def.hpp> + +#include <boost/iterator/iterator_traits.hpp> + +namespace boost +{ + // Used as a default template argument internally, merely to + // indicate "use the default", this can also be passed by users + // explicitly in order to specify that the default should be used. + struct use_default; + +# ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + // the incompleteness of use_default causes massive problems for + // is_convertible (naturally). This workaround is fortunately not + // needed for vc6/vc7. + template<class To> + struct is_convertible<use_default,To> + : mpl::false_ {}; +# endif + + namespace detail + { + + // + // Result type used in enable_if_convertible meta function. + // This can be an incomplete type, as only pointers to + // enable_if_convertible< ... >::type are used. + // We could have used void for this, but conversion to + // void* is just to easy. + // + struct enable_type; + } + + + // + // enable_if for use in adapted iterators constructors. + // + // In order to provide interoperability between adapted constant and + // mutable iterators, adapted iterators will usually provide templated + // conversion constructors of the following form + // + // template <class BaseIterator> + // class adapted_iterator : + // public iterator_adaptor< adapted_iterator<Iterator>, Iterator > + // { + // public: + // + // ... + // + // template <class OtherIterator> + // adapted_iterator( + // OtherIterator const& it + // , typename enable_if_convertible<OtherIterator, Iterator>::type* = 0); + // + // ... + // }; + // + // enable_if_convertible is used to remove those overloads from the overload + // set that cannot be instantiated. For all practical purposes only overloads + // for constant/mutable interaction will remain. This has the advantage that + // meta functions like boost::is_convertible do not return false positives, + // as they can only look at the signature of the conversion constructor + // and not at the actual instantiation. + // + // enable_if_interoperable can be safely used in user code. It falls back to + // always enabled for compilers that don't support enable_if or is_convertible. + // There is no need for compiler specific workarounds in user code. + // + // The operators implementation relies on boost::is_convertible not returning + // false positives for user/library defined iterator types. See comments + // on operator implementation for consequences. + // +# if BOOST_WORKAROUND(BOOST_MSVC, <= 1300) + + template<typename From, typename To> + struct enable_if_convertible + { + typedef typename mpl::if_< + mpl::or_< + is_same<From,To> + , is_convertible<From, To> + > + , boost::detail::enable_type + , int& + >::type type; + }; + +# elif defined(BOOST_NO_IS_CONVERTIBLE) || defined(BOOST_NO_SFINAE) + + template <class From, class To> + struct enable_if_convertible + { + typedef boost::detail::enable_type type; + }; + +# elif BOOST_WORKAROUND(_MSC_FULL_VER, BOOST_TESTED_AT(13102292)) && BOOST_MSVC > 1300 + + // For some reason vc7.1 needs us to "cut off" instantiation + // of is_convertible in a few cases. + template<typename From, typename To> + struct enable_if_convertible + : iterators::enable_if< + mpl::or_< + is_same<From,To> + , is_convertible<From, To> + > + , boost::detail::enable_type + > + {}; + +# else + + template<typename From, typename To> + struct enable_if_convertible + : iterators::enable_if< + is_convertible<From, To> + , boost::detail::enable_type + > + {}; + +# endif + + // + // Default template argument handling for iterator_adaptor + // + namespace detail + { + // If T is use_default, return the result of invoking + // DefaultNullaryFn, otherwise return T. + template <class T, class DefaultNullaryFn> + struct ia_dflt_help + : mpl::eval_if< + is_same<T, use_default> + , DefaultNullaryFn + , mpl::identity<T> + > + { + }; + + // A metafunction which computes an iterator_adaptor's base class, + // a specialization of iterator_facade. + template < + class Derived + , class Base + , class Value + , class Traversal + , class Reference + , class Difference + > + struct iterator_adaptor_base + { + typedef iterator_facade< + Derived + +# ifdef BOOST_ITERATOR_REF_CONSTNESS_KILLS_WRITABILITY + , typename boost::detail::ia_dflt_help< + Value + , mpl::eval_if< + is_same<Reference,use_default> + , iterator_value<Base> + , remove_reference<Reference> + > + >::type +# else + , typename boost::detail::ia_dflt_help< + Value, iterator_value<Base> + >::type +# endif + + , typename boost::detail::ia_dflt_help< + Traversal + , iterator_traversal<Base> + >::type + + , typename boost::detail::ia_dflt_help< + Reference + , mpl::eval_if< + is_same<Value,use_default> + , iterator_reference<Base> + , add_reference<Value> + > + >::type + + , typename boost::detail::ia_dflt_help< + Difference, iterator_difference<Base> + >::type + > + type; + }; + + // workaround for aC++ CR JAGaf33512 + template <class Tr1, class Tr2> + inline void iterator_adaptor_assert_traversal () + { + BOOST_STATIC_ASSERT((is_convertible<Tr1, Tr2>::value)); + } + } + + // + // Iterator Adaptor + // + // The parameter ordering changed slightly with respect to former + // versions of iterator_adaptor The idea is that when the user needs + // to fiddle with the reference type it is highly likely that the + // iterator category has to be adjusted as well. Any of the + // following four template arguments may be ommitted or explicitly + // replaced by use_default. + // + // Value - if supplied, the value_type of the resulting iterator, unless + // const. If const, a conforming compiler strips constness for the + // value_type. If not supplied, iterator_traits<Base>::value_type is used + // + // Category - the traversal category of the resulting iterator. If not + // supplied, iterator_traversal<Base>::type is used. + // + // Reference - the reference type of the resulting iterator, and in + // particular, the result type of operator*(). If not supplied but + // Value is supplied, Value& is used. Otherwise + // iterator_traits<Base>::reference is used. + // + // Difference - the difference_type of the resulting iterator. If not + // supplied, iterator_traits<Base>::difference_type is used. + // + template < + class Derived + , class Base + , class Value = use_default + , class Traversal = use_default + , class Reference = use_default + , class Difference = use_default + > + class iterator_adaptor + : public boost::detail::iterator_adaptor_base< + Derived, Base, Value, Traversal, Reference, Difference + >::type + { + friend class iterator_core_access; + + protected: + typedef typename boost::detail::iterator_adaptor_base< + Derived, Base, Value, Traversal, Reference, Difference + >::type super_t; + public: + iterator_adaptor() {} + + explicit iterator_adaptor(Base const &iter) + : m_iterator(iter) + { + } + + typedef Base base_type; + + Base const& base() const + { return m_iterator; } + + protected: + // for convenience in derived classes + typedef iterator_adaptor<Derived,Base,Value,Traversal,Reference,Difference> iterator_adaptor_; + + // + // lvalue access to the Base object for Derived + // + Base const& base_reference() const + { return m_iterator; } + + Base& base_reference() + { return m_iterator; } + + private: + // + // Core iterator interface for iterator_facade. This is private + // to prevent temptation for Derived classes to use it, which + // will often result in an error. Derived classes should use + // base_reference(), above, to get direct access to m_iterator. + // + typename super_t::reference dereference() const + { return *m_iterator; } + + template < + class OtherDerived, class OtherIterator, class V, class C, class R, class D + > + bool equal(iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D> const& x) const + { + // Maybe readd with same_distance + // BOOST_STATIC_ASSERT( + // (detail::same_category_and_difference<Derived,OtherDerived>::value) + // ); + return m_iterator == x.base(); + } + + typedef typename iterator_category_to_traversal< + typename super_t::iterator_category + >::type my_traversal; + +# define BOOST_ITERATOR_ADAPTOR_ASSERT_TRAVERSAL(cat) \ + boost::detail::iterator_adaptor_assert_traversal<my_traversal, cat>(); + + void advance(typename super_t::difference_type n) + { + BOOST_ITERATOR_ADAPTOR_ASSERT_TRAVERSAL(random_access_traversal_tag) + m_iterator += n; + } + + void increment() { ++m_iterator; } + + void decrement() + { + BOOST_ITERATOR_ADAPTOR_ASSERT_TRAVERSAL(bidirectional_traversal_tag) + --m_iterator; + } + + template < + class OtherDerived, class OtherIterator, class V, class C, class R, class D + > + typename super_t::difference_type distance_to( + iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D> const& y) const + { + BOOST_ITERATOR_ADAPTOR_ASSERT_TRAVERSAL(random_access_traversal_tag) + // Maybe readd with same_distance + // BOOST_STATIC_ASSERT( + // (detail::same_category_and_difference<Derived,OtherDerived>::value) + // ); + return y.base() - m_iterator; + } + +# undef BOOST_ITERATOR_ADAPTOR_ASSERT_TRAVERSAL + + private: // data members + Base m_iterator; + }; + +} // namespace boost + +#include <boost/iterator/detail/config_undef.hpp> + +#endif // BOOST_ITERATOR_ADAPTOR_23022003THW_HPP diff --git a/ext/boost/iterator/iterator_archetypes.hpp b/ext/boost/iterator/iterator_archetypes.hpp new file mode 100644 index 0000000000..039de1cf74 --- /dev/null +++ b/ext/boost/iterator/iterator_archetypes.hpp @@ -0,0 +1,515 @@ +// (C) Copyright Jeremy Siek 2002. +// 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_ARCHETYPES_HPP +#define BOOST_ITERATOR_ARCHETYPES_HPP + +#include <boost/iterator/iterator_categories.hpp> +#include <boost/operators.hpp> +#include <boost/static_assert.hpp> +#include <boost/iterator.hpp> + +#include <boost/iterator/detail/facade_iterator_category.hpp> + +#include <boost/type_traits/is_const.hpp> +#include <boost/type_traits/add_const.hpp> +#include <boost/type_traits/remove_const.hpp> +#include <boost/type_traits/remove_cv.hpp> + +#include <boost/concept_archetype.hpp> + +#include <boost/mpl/aux_/msvc_eti_base.hpp> +#include <boost/mpl/bitand.hpp> +#include <boost/mpl/int.hpp> +#include <boost/mpl/equal_to.hpp> +#include <boost/mpl/if.hpp> +#include <boost/mpl/eval_if.hpp> +#include <boost/mpl/and.hpp> +#include <boost/mpl/identity.hpp> + +#include <cstddef> + +namespace boost { + +template <class Value, class AccessCategory> +struct access_archetype; + +template <class Derived, class Value, class AccessCategory, class TraversalCategory> +struct traversal_archetype; + +namespace iterator_archetypes +{ + enum { + readable_iterator_bit = 1 + , writable_iterator_bit = 2 + , swappable_iterator_bit = 4 + , lvalue_iterator_bit = 8 + }; + + // Not quite tags, since dispatching wouldn't work. + typedef mpl::int_<readable_iterator_bit>::type readable_iterator_t; + typedef mpl::int_<writable_iterator_bit>::type writable_iterator_t; + + typedef mpl::int_< + (readable_iterator_bit|writable_iterator_bit) + >::type readable_writable_iterator_t; + + typedef mpl::int_< + (readable_iterator_bit|lvalue_iterator_bit) + >::type readable_lvalue_iterator_t; + + typedef mpl::int_< + (lvalue_iterator_bit|writable_iterator_bit) + >::type writable_lvalue_iterator_t; + + typedef mpl::int_<swappable_iterator_bit>::type swappable_iterator_t; + typedef mpl::int_<lvalue_iterator_bit>::type lvalue_iterator_t; + + template <class Derived, class Base> + struct has_access + : mpl::equal_to< + mpl::bitand_<Derived,Base> + , Base + > + {}; +} + +namespace detail +{ + template <class T> + struct assign_proxy + { + assign_proxy& operator=(T) { return *this; } + }; + + template <class T> + struct read_proxy + { + operator T() { return static_object<T>::get(); } + }; + + template <class T> + struct read_write_proxy + : read_proxy<T> // Use to inherit from assign_proxy, but that doesn't work. -JGS + { + read_write_proxy& operator=(T) { return *this; } + }; + + template <class T> + struct arrow_proxy + { + T const* operator->() const { return 0; } + }; + + struct no_operator_brackets {}; + + template <class ValueType> + struct readable_operator_brackets + { + read_proxy<ValueType> operator[](std::ptrdiff_t n) const { return read_proxy<ValueType>(); } + }; + + template <class ValueType> + struct writable_operator_brackets + { + read_write_proxy<ValueType> operator[](std::ptrdiff_t n) const { return read_write_proxy<ValueType>(); } + }; + + template <class Value, class AccessCategory, class TraversalCategory> + struct operator_brackets + : mpl::aux::msvc_eti_base< + typename mpl::eval_if< + is_convertible<TraversalCategory, random_access_traversal_tag> + , mpl::eval_if< + iterator_archetypes::has_access< + AccessCategory + , iterator_archetypes::writable_iterator_t + > + , mpl::identity<writable_operator_brackets<Value> > + , mpl::if_< + iterator_archetypes::has_access< + AccessCategory + , iterator_archetypes::readable_iterator_t + > + , readable_operator_brackets<Value> + , no_operator_brackets + > + > + , mpl::identity<no_operator_brackets> + >::type + >::type + {}; + + template <class TraversalCategory> + struct traversal_archetype_impl + { + template <class Derived,class Value> struct archetype; + }; + + // Constructor argument for those iterators that + // are not default constructible + struct ctor_arg {}; + + template <class Derived, class Value, class TraversalCategory> + struct traversal_archetype_ + : mpl::aux::msvc_eti_base< + typename traversal_archetype_impl<TraversalCategory>::template archetype<Derived,Value> + >::type + { + typedef typename + traversal_archetype_impl<TraversalCategory>::template archetype<Derived,Value> + base; + + traversal_archetype_() {} + + traversal_archetype_(ctor_arg arg) + : base(arg) + {} + }; + + template <> + struct traversal_archetype_impl<incrementable_traversal_tag> + { + template<class Derived, class Value> + struct archetype + { + explicit archetype(ctor_arg) {} + + struct bogus { }; // This use to be void, but that causes trouble for iterator_facade. Need more research. -JGS + typedef bogus difference_type; + + Derived& operator++() { return (Derived&)static_object<Derived>::get(); } + Derived operator++(int) const { return (Derived&)static_object<Derived>::get(); } + }; + }; + + template <> + struct traversal_archetype_impl<single_pass_traversal_tag> + { + template<class Derived, class Value> + struct archetype + : public equality_comparable< traversal_archetype_<Derived, Value, single_pass_traversal_tag> >, + public traversal_archetype_<Derived, Value, incrementable_traversal_tag> + { + explicit archetype(ctor_arg arg) + : traversal_archetype_<Derived, Value, incrementable_traversal_tag>(arg) + {} + + typedef std::ptrdiff_t difference_type; + }; + }; + + template <class Derived, class Value> + bool operator==(traversal_archetype_<Derived, Value, single_pass_traversal_tag> const&, + traversal_archetype_<Derived, Value, single_pass_traversal_tag> const&) { return true; } + +#if BOOST_WORKAROUND(BOOST_MSVC, <= 1300) + // doesn't seem to pick up != from equality_comparable + template <class Derived, class Value> + bool operator!=(traversal_archetype_<Derived, Value, single_pass_traversal_tag> const&, + traversal_archetype_<Derived, Value, single_pass_traversal_tag> const&) { return true; } +#endif + template <> + struct traversal_archetype_impl<forward_traversal_tag> + { + template<class Derived, class Value> + struct archetype + : public traversal_archetype_<Derived, Value, single_pass_traversal_tag> + { + archetype() + : traversal_archetype_<Derived, Value, single_pass_traversal_tag>(ctor_arg()) + {} + }; + }; + + template <> + struct traversal_archetype_impl<bidirectional_traversal_tag> + { + template<class Derived, class Value> + struct archetype + : public traversal_archetype_<Derived, Value, forward_traversal_tag> + { + Derived& operator--() { return static_object<Derived>::get(); } + Derived operator--(int) const { return static_object<Derived>::get(); } + }; + }; + + template <> + struct traversal_archetype_impl<random_access_traversal_tag> + { + template<class Derived, class Value> + struct archetype + : public traversal_archetype_<Derived, Value, bidirectional_traversal_tag> + { + Derived& operator+=(std::ptrdiff_t) { return static_object<Derived>::get(); } + Derived& operator-=(std::ptrdiff_t) { return static_object<Derived>::get(); } + }; + }; + + template <class Derived, class Value> + Derived& operator+(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, + std::ptrdiff_t) { return static_object<Derived>::get(); } + + template <class Derived, class Value> + Derived& operator+(std::ptrdiff_t, + traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) + { return static_object<Derived>::get(); } + + template <class Derived, class Value> + Derived& operator-(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, + std::ptrdiff_t) + { return static_object<Derived>::get(); } + + template <class Derived, class Value> + std::ptrdiff_t operator-(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, + traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) + { return 0; } + + template <class Derived, class Value> + bool operator<(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, + traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) + { return true; } + + template <class Derived, class Value> + bool operator>(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, + traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) + { return true; } + + template <class Derived, class Value> + bool operator<=(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, + traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) + { return true; } + + template <class Derived, class Value> + bool operator>=(traversal_archetype_<Derived, Value, random_access_traversal_tag> const&, + traversal_archetype_<Derived, Value, random_access_traversal_tag> const&) + { return true; } + + struct bogus_type; + + template <class Value> + struct convertible_type + : mpl::if_< is_const<Value>, + typename remove_const<Value>::type, + bogus_type > + {}; + +} // namespace detail + + +template <class> struct undefined; + +template <class AccessCategory> +struct iterator_access_archetype_impl +{ + template <class Value> struct archetype; +}; + +template <class Value, class AccessCategory> +struct iterator_access_archetype + : mpl::aux::msvc_eti_base< + typename iterator_access_archetype_impl< + AccessCategory + >::template archetype<Value> + >::type +{ +}; + +template <> +struct iterator_access_archetype_impl< + iterator_archetypes::readable_iterator_t +> +{ + template <class Value> + struct archetype + { + typedef typename remove_cv<Value>::type value_type; + typedef Value reference; + typedef Value* pointer; + + value_type operator*() const { return static_object<value_type>::get(); } + + detail::arrow_proxy<Value> operator->() const { return detail::arrow_proxy<Value>(); } + }; +}; + +template <> +struct iterator_access_archetype_impl< + iterator_archetypes::writable_iterator_t +> +{ + template <class Value> + struct archetype + { +# if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300) + BOOST_STATIC_ASSERT(!is_const<Value>::value); +# endif + typedef void value_type; + typedef void reference; + typedef void pointer; + + detail::assign_proxy<Value> operator*() const { return detail::assign_proxy<Value>(); } + }; +}; + +template <> +struct iterator_access_archetype_impl< + iterator_archetypes::readable_writable_iterator_t +> +{ + template <class Value> + struct archetype + : public virtual iterator_access_archetype< + Value, iterator_archetypes::readable_iterator_t + > + { + typedef detail::read_write_proxy<Value> reference; + + detail::read_write_proxy<Value> operator*() const { return detail::read_write_proxy<Value>(); } + }; +}; + +template <> +struct iterator_access_archetype_impl<iterator_archetypes::readable_lvalue_iterator_t> +{ + template <class Value> + struct archetype + : public virtual iterator_access_archetype< + Value, iterator_archetypes::readable_iterator_t + > + { + typedef Value& reference; + + Value& operator*() const { return static_object<Value>::get(); } + Value* operator->() const { return 0; } + }; +}; + +template <> +struct iterator_access_archetype_impl<iterator_archetypes::writable_lvalue_iterator_t> +{ + template <class Value> + struct archetype + : public virtual iterator_access_archetype< + Value, iterator_archetypes::readable_lvalue_iterator_t + > + { +# if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300) + BOOST_STATIC_ASSERT((!is_const<Value>::value)); +# endif + }; +}; + + +template <class Value, class AccessCategory, class TraversalCategory> +struct iterator_archetype; + +template <class Value, class AccessCategory, class TraversalCategory> +struct traversal_archetype_base + : detail::operator_brackets< + typename remove_cv<Value>::type + , AccessCategory + , TraversalCategory + > + , detail::traversal_archetype_< + iterator_archetype<Value, AccessCategory, TraversalCategory> + , Value + , TraversalCategory + > +{ +}; + +namespace detail +{ + template <class Value, class AccessCategory, class TraversalCategory> + struct iterator_archetype_base + : iterator_access_archetype<Value, AccessCategory> + , traversal_archetype_base<Value, AccessCategory, TraversalCategory> + { + typedef iterator_access_archetype<Value, AccessCategory> access; + + typedef typename detail::facade_iterator_category< + TraversalCategory + , typename mpl::eval_if< + iterator_archetypes::has_access< + AccessCategory, iterator_archetypes::writable_iterator_t + > + , remove_const<Value> + , add_const<Value> + >::type + , typename access::reference + >::type iterator_category; + + // Needed for some broken libraries (see below) + typedef boost::iterator< + iterator_category + , Value + , typename traversal_archetype_base< + Value, AccessCategory, TraversalCategory + >::difference_type + , typename access::pointer + , typename access::reference + > workaround_iterator_base; + }; +} + +template <class Value, class AccessCategory, class TraversalCategory> +struct iterator_archetype + : public detail::iterator_archetype_base<Value, AccessCategory, TraversalCategory> + + // These broken libraries require derivation from std::iterator + // (or related magic) in order to handle iter_swap and other + // iterator operations +# if BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, < 310) \ + || BOOST_WORKAROUND(_RWSTD_VER, BOOST_TESTED_AT(0x20101)) + , public detail::iterator_archetype_base< + Value, AccessCategory, TraversalCategory + >::workaround_iterator_base +# endif +{ + // Derivation from std::iterator above caused references to nested + // types to be ambiguous, so now we have to redeclare them all + // here. +# if BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, < 310) \ + || BOOST_WORKAROUND(_RWSTD_VER, BOOST_TESTED_AT(0x20101)) + + typedef detail::iterator_archetype_base< + Value,AccessCategory,TraversalCategory + > base; + + typedef typename base::value_type value_type; + typedef typename base::reference reference; + typedef typename base::pointer pointer; + typedef typename base::difference_type difference_type; + typedef typename base::iterator_category iterator_category; +# endif + + iterator_archetype() { } + iterator_archetype(iterator_archetype const& x) + : detail::iterator_archetype_base< + Value + , AccessCategory + , TraversalCategory + >(x) + {} + + iterator_archetype& operator=(iterator_archetype const&) + { return *this; } + +# if 0 + // Optional conversion from mutable + iterator_archetype( + iterator_archetype< + typename detail::convertible_type<Value>::type + , AccessCategory + , TraversalCategory> const& + ); +# endif +}; + +} // namespace boost + + +#endif // BOOST_ITERATOR_ARCHETYPES_HPP diff --git a/ext/boost/iterator/iterator_categories.hpp b/ext/boost/iterator/iterator_categories.hpp new file mode 100644 index 0000000000..1740d9818a --- /dev/null +++ b/ext/boost/iterator/iterator_categories.hpp @@ -0,0 +1,188 @@ +// (C) Copyright Jeremy Siek 2002. +// 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_CATEGORIES_HPP +# define BOOST_ITERATOR_CATEGORIES_HPP + +# include <boost/config.hpp> +# include <boost/detail/iterator.hpp> +# include <boost/iterator/detail/config_def.hpp> + +# include <boost/detail/workaround.hpp> + +# include <boost/mpl/eval_if.hpp> +# include <boost/mpl/identity.hpp> +# include <boost/mpl/placeholders.hpp> +# include <boost/mpl/aux_/lambda_support.hpp> + +# include <boost/type_traits/is_convertible.hpp> + +# include <boost/static_assert.hpp> + +namespace boost { + +// +// Traversal Categories +// + +struct no_traversal_tag {}; + +struct incrementable_traversal_tag + : no_traversal_tag +{ +// incrementable_traversal_tag() {} +// incrementable_traversal_tag(std::output_iterator_tag const&) {}; +}; + +struct single_pass_traversal_tag + : incrementable_traversal_tag +{ +// single_pass_traversal_tag() {} +// single_pass_traversal_tag(std::input_iterator_tag const&) {}; +}; + +struct forward_traversal_tag + : single_pass_traversal_tag +{ +// forward_traversal_tag() {} +// forward_traversal_tag(std::forward_iterator_tag const&) {}; +}; + +struct bidirectional_traversal_tag + : forward_traversal_tag +{ +// bidirectional_traversal_tag() {}; +// bidirectional_traversal_tag(std::bidirectional_iterator_tag const&) {}; +}; + +struct random_access_traversal_tag + : bidirectional_traversal_tag +{ +// random_access_traversal_tag() {}; +// random_access_traversal_tag(std::random_access_iterator_tag const&) {}; +}; + +namespace detail +{ + // + // Convert a "strictly old-style" iterator category to a traversal + // tag. This is broken out into a separate metafunction to reduce + // the cost of instantiating iterator_category_to_traversal, below, + // for new-style types. + // + template <class Cat> + struct old_category_to_traversal + : mpl::eval_if< + is_convertible<Cat,std::random_access_iterator_tag> + , mpl::identity<random_access_traversal_tag> + , mpl::eval_if< + is_convertible<Cat,std::bidirectional_iterator_tag> + , mpl::identity<bidirectional_traversal_tag> + , mpl::eval_if< + is_convertible<Cat,std::forward_iterator_tag> + , mpl::identity<forward_traversal_tag> + , mpl::eval_if< + is_convertible<Cat,std::input_iterator_tag> + , mpl::identity<single_pass_traversal_tag> + , mpl::eval_if< + is_convertible<Cat,std::output_iterator_tag> + , mpl::identity<incrementable_traversal_tag> + , void + > + > + > + > + > + {}; + +# if BOOST_WORKAROUND(BOOST_MSVC, < 1300) + template <> + struct old_category_to_traversal<int> + { + typedef int type; + }; +# endif + + template <class Traversal> + struct pure_traversal_tag + : mpl::eval_if< + is_convertible<Traversal,random_access_traversal_tag> + , mpl::identity<random_access_traversal_tag> + , mpl::eval_if< + is_convertible<Traversal,bidirectional_traversal_tag> + , mpl::identity<bidirectional_traversal_tag> + , mpl::eval_if< + is_convertible<Traversal,forward_traversal_tag> + , mpl::identity<forward_traversal_tag> + , mpl::eval_if< + is_convertible<Traversal,single_pass_traversal_tag> + , mpl::identity<single_pass_traversal_tag> + , mpl::eval_if< + is_convertible<Traversal,incrementable_traversal_tag> + , mpl::identity<incrementable_traversal_tag> + , void + > + > + > + > + > + { + }; + +# if BOOST_WORKAROUND(BOOST_MSVC, < 1300) + template <> + struct pure_traversal_tag<int> + { + typedef int type; + }; +# endif + +} // namespace detail + + +// +// Convert an iterator category into a traversal tag +// +template <class Cat> +struct iterator_category_to_traversal + : mpl::eval_if< // if already convertible to a traversal tag, we're done. + is_convertible<Cat,incrementable_traversal_tag> + , mpl::identity<Cat> + , boost::detail::old_category_to_traversal<Cat> + > +{}; + +// Trait to get an iterator's traversal category +template <class Iterator = mpl::_1> +struct iterator_traversal + : iterator_category_to_traversal< + typename boost::detail::iterator_traits<Iterator>::iterator_category + > +{}; + +# ifdef BOOST_MPL_CFG_NO_FULL_LAMBDA_SUPPORT +// Hack because BOOST_MPL_AUX_LAMBDA_SUPPORT doesn't seem to work +// out well. Instantiating the nested apply template also +// requires instantiating iterator_traits on the +// placeholder. Instead we just specialize it as a metafunction +// class. +template <> +struct iterator_traversal<mpl::_1> +{ + template <class T> + struct apply : iterator_traversal<T> + {}; +}; +template <> +struct iterator_traversal<mpl::_> + : iterator_traversal<mpl::_1> +{}; +# endif + +} // namespace boost + +#include <boost/iterator/detail/config_undef.hpp> + +#endif // BOOST_ITERATOR_CATEGORIES_HPP diff --git a/ext/boost/iterator/iterator_concepts.hpp b/ext/boost/iterator/iterator_concepts.hpp new file mode 100644 index 0000000000..ced1112a61 --- /dev/null +++ b/ext/boost/iterator/iterator_concepts.hpp @@ -0,0 +1,284 @@ +// (C) Copyright Jeremy Siek 2002. +// 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_CONCEPTS_HPP +#define BOOST_ITERATOR_CONCEPTS_HPP + +#include <boost/concept_check.hpp> +#include <boost/iterator/iterator_categories.hpp> + +// Use boost::detail::iterator_traits to work around some MSVC/Dinkumware problems. +#include <boost/detail/iterator.hpp> + +#include <boost/type_traits/is_same.hpp> +#include <boost/type_traits/is_integral.hpp> + +#include <boost/mpl/bool.hpp> +#include <boost/mpl/if.hpp> +#include <boost/mpl/and.hpp> +#include <boost/mpl/or.hpp> + +#include <boost/static_assert.hpp> + +// Use boost/limits to work around missing limits headers on some compilers +#include <boost/limits.hpp> +#include <boost/config.hpp> + +#include <algorithm> + +#include <boost/concept/detail/concept_def.hpp> + +namespace boost_concepts +{ + // Used a different namespace here (instead of "boost") so that the + // concept descriptions do not take for granted the names in + // namespace boost. + + //=========================================================================== + // Iterator Access Concepts + + BOOST_concept(ReadableIterator,(Iterator)) + : boost::Assignable<Iterator> + , boost::CopyConstructible<Iterator> + + { + typedef BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type value_type; + typedef BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::reference reference; + + BOOST_CONCEPT_USAGE(ReadableIterator) + { + + value_type v = *i; + boost::ignore_unused_variable_warning(v); + } + private: + Iterator i; + }; + + template < + typename Iterator + , typename ValueType = BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type + > + struct WritableIterator + : boost::CopyConstructible<Iterator> + { + BOOST_CONCEPT_USAGE(WritableIterator) + { + *i = v; + } + private: + ValueType v; + Iterator i; + }; + + template < + typename Iterator + , typename ValueType = BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type + > + struct WritableIteratorConcept : WritableIterator<Iterator,ValueType> {}; + + BOOST_concept(SwappableIterator,(Iterator)) + { + BOOST_CONCEPT_USAGE(SwappableIterator) + { + std::iter_swap(i1, i2); + } + private: + Iterator i1; + Iterator i2; + }; + + BOOST_concept(LvalueIterator,(Iterator)) + { + typedef typename boost::detail::iterator_traits<Iterator>::value_type value_type; + + BOOST_CONCEPT_USAGE(LvalueIterator) + { + value_type& r = const_cast<value_type&>(*i); + boost::ignore_unused_variable_warning(r); + } + private: + Iterator i; + }; + + + //=========================================================================== + // Iterator Traversal Concepts + + BOOST_concept(IncrementableIterator,(Iterator)) + : boost::Assignable<Iterator> + , boost::CopyConstructible<Iterator> + { + typedef typename boost::iterator_traversal<Iterator>::type traversal_category; + + BOOST_CONCEPT_ASSERT(( + boost::Convertible< + traversal_category + , boost::incrementable_traversal_tag + >)); + + BOOST_CONCEPT_USAGE(IncrementableIterator) + { + ++i; + (void)i++; + } + private: + Iterator i; + }; + + BOOST_concept(SinglePassIterator,(Iterator)) + : IncrementableIterator<Iterator> + , boost::EqualityComparable<Iterator> + + { + BOOST_CONCEPT_ASSERT(( + boost::Convertible< + BOOST_DEDUCED_TYPENAME SinglePassIterator::traversal_category + , boost::single_pass_traversal_tag + > )); + }; + + BOOST_concept(ForwardTraversal,(Iterator)) + : SinglePassIterator<Iterator> + , boost::DefaultConstructible<Iterator> + { + typedef typename boost::detail::iterator_traits<Iterator>::difference_type difference_type; + + BOOST_MPL_ASSERT((boost::is_integral<difference_type>)); + BOOST_MPL_ASSERT_RELATION(std::numeric_limits<difference_type>::is_signed, ==, true); + + BOOST_CONCEPT_ASSERT(( + boost::Convertible< + BOOST_DEDUCED_TYPENAME ForwardTraversal::traversal_category + , boost::forward_traversal_tag + > )); + }; + + BOOST_concept(BidirectionalTraversal,(Iterator)) + : ForwardTraversal<Iterator> + { + BOOST_CONCEPT_ASSERT(( + boost::Convertible< + BOOST_DEDUCED_TYPENAME BidirectionalTraversal::traversal_category + , boost::bidirectional_traversal_tag + > )); + + BOOST_CONCEPT_USAGE(BidirectionalTraversal) + { + --i; + (void)i--; + } + private: + Iterator i; + }; + + BOOST_concept(RandomAccessTraversal,(Iterator)) + : BidirectionalTraversal<Iterator> + { + BOOST_CONCEPT_ASSERT(( + boost::Convertible< + BOOST_DEDUCED_TYPENAME RandomAccessTraversal::traversal_category + , boost::random_access_traversal_tag + > )); + + BOOST_CONCEPT_USAGE(RandomAccessTraversal) + { + i += n; + i = i + n; + i = n + i; + i -= n; + i = i - n; + n = i - j; + } + + private: + typename BidirectionalTraversal<Iterator>::difference_type n; + Iterator i, j; + }; + + //=========================================================================== + // Iterator Interoperability + + namespace detail + { + template <typename Iterator1, typename Iterator2> + void interop_single_pass_constraints(Iterator1 const& i1, Iterator2 const& i2) + { + bool b; + b = i1 == i2; + b = i1 != i2; + + b = i2 == i1; + b = i2 != i1; + boost::ignore_unused_variable_warning(b); + } + + template <typename Iterator1, typename Iterator2> + void interop_rand_access_constraints( + Iterator1 const& i1, Iterator2 const& i2, + boost::random_access_traversal_tag, boost::random_access_traversal_tag) + { + bool b; + typename boost::detail::iterator_traits<Iterator2>::difference_type n; + b = i1 < i2; + b = i1 <= i2; + b = i1 > i2; + b = i1 >= i2; + n = i1 - i2; + + b = i2 < i1; + b = i2 <= i1; + b = i2 > i1; + b = i2 >= i1; + n = i2 - i1; + boost::ignore_unused_variable_warning(b); + boost::ignore_unused_variable_warning(n); + } + + template <typename Iterator1, typename Iterator2> + void interop_rand_access_constraints( + Iterator1 const&, Iterator2 const&, + boost::single_pass_traversal_tag, boost::single_pass_traversal_tag) + { } + + } // namespace detail + + BOOST_concept(InteroperableIterator,(Iterator)(ConstIterator)) + { + private: + typedef typename boost::detail::pure_traversal_tag< + typename boost::iterator_traversal< + Iterator + >::type + >::type traversal_category; + + typedef typename boost::detail::pure_traversal_tag< + typename boost::iterator_traversal< + ConstIterator + >::type + >::type const_traversal_category; + + public: + BOOST_CONCEPT_ASSERT((SinglePassIterator<Iterator>)); + BOOST_CONCEPT_ASSERT((SinglePassIterator<ConstIterator>)); + + BOOST_CONCEPT_USAGE(InteroperableIterator) + { + detail::interop_single_pass_constraints(i, ci); + detail::interop_rand_access_constraints(i, ci, traversal_category(), const_traversal_category()); + + ci = i; + } + + private: + Iterator i; + ConstIterator ci; + }; + +} // namespace boost_concepts + +#include <boost/concept/detail/concept_undef.hpp> + +#endif // BOOST_ITERATOR_CONCEPTS_HPP diff --git a/ext/boost/iterator/iterator_facade.hpp b/ext/boost/iterator/iterator_facade.hpp new file mode 100644 index 0000000000..967d60f2ba --- /dev/null +++ b/ext/boost/iterator/iterator_facade.hpp @@ -0,0 +1,878 @@ +// (C) Copyright David Abrahams 2002. +// (C) Copyright Jeremy Siek 2002. +// (C) Copyright Thomas Witt 2002. +// 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_FACADE_23022003THW_HPP +#define BOOST_ITERATOR_FACADE_23022003THW_HPP + +#include <boost/iterator.hpp> +#include <boost/iterator/interoperable.hpp> +#include <boost/iterator/iterator_traits.hpp> + +#include <boost/iterator/detail/facade_iterator_category.hpp> +#include <boost/iterator/detail/enable_if.hpp> + +#include <boost/implicit_cast.hpp> +#include <boost/static_assert.hpp> + +#include <boost/type_traits/is_same.hpp> +#include <boost/type_traits/add_const.hpp> +#include <boost/type_traits/add_pointer.hpp> +#include <boost/type_traits/remove_const.hpp> +#include <boost/type_traits/remove_reference.hpp> +#include <boost/type_traits/is_convertible.hpp> +#include <boost/type_traits/is_pod.hpp> + +#include <boost/mpl/eval_if.hpp> +#include <boost/mpl/if.hpp> +#include <boost/mpl/or.hpp> +#include <boost/mpl/and.hpp> +#include <boost/mpl/not.hpp> +#include <boost/mpl/always.hpp> +#include <boost/mpl/apply.hpp> +#include <boost/mpl/identity.hpp> + +#include <boost/iterator/detail/config_def.hpp> // this goes last + +namespace boost +{ + // This forward declaration is required for the friend declaration + // in iterator_core_access + template <class I, class V, class TC, class R, class D> class iterator_facade; + + namespace detail + { + // A binary metafunction class that always returns bool. VC6 + // ICEs on mpl::always<bool>, probably because of the default + // parameters. + struct always_bool2 + { + template <class T, class U> + struct apply + { + typedef bool type; + }; + }; + + // + // enable if for use in operator implementation. + // + template < + class Facade1 + , class Facade2 + , class Return + > + struct enable_if_interoperable +#if BOOST_WORKAROUND(BOOST_MSVC, <= 1300) + { + typedef typename mpl::if_< + mpl::or_< + is_convertible<Facade1, Facade2> + , is_convertible<Facade2, Facade1> + > + , Return + , int[3] + >::type type; + }; +#else + : ::boost::iterators::enable_if< + mpl::or_< + is_convertible<Facade1, Facade2> + , is_convertible<Facade2, Facade1> + > + , Return + > + {}; +#endif + + // + // Generates associated types for an iterator_facade with the + // given parameters. + // + template < + class ValueParam + , class CategoryOrTraversal + , class Reference + , class Difference + > + struct iterator_facade_types + { + typedef typename facade_iterator_category< + CategoryOrTraversal, ValueParam, Reference + >::type iterator_category; + + typedef typename remove_const<ValueParam>::type value_type; + + typedef typename mpl::eval_if< + boost::detail::iterator_writability_disabled<ValueParam,Reference> + , add_pointer<const value_type> + , add_pointer<value_type> + >::type pointer; + +# if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \ + && (BOOST_WORKAROUND(_STLPORT_VERSION, BOOST_TESTED_AT(0x452)) \ + || BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, BOOST_TESTED_AT(310))) \ + || BOOST_WORKAROUND(BOOST_RWSTD_VER, BOOST_TESTED_AT(0x20101)) \ + || BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, <= 310) + + // To interoperate with some broken library/compiler + // combinations, user-defined iterators must be derived from + // std::iterator. It is possible to implement a standard + // library for broken compilers without this limitation. +# define BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE 1 + + typedef + iterator<iterator_category, value_type, Difference, pointer, Reference> + base; +# endif + }; + + // iterators whose dereference operators reference the same value + // for all iterators into the same sequence (like many input + // iterators) need help with their postfix ++: the referenced + // value must be read and stored away before the increment occurs + // so that *a++ yields the originally referenced element and not + // the next one. + template <class Iterator> + class postfix_increment_proxy + { + typedef typename iterator_value<Iterator>::type value_type; + public: + explicit postfix_increment_proxy(Iterator const& x) + : stored_value(*x) + {} + + // Returning a mutable reference allows nonsense like + // (*r++).mutate(), but it imposes fewer assumptions about the + // behavior of the value_type. In particular, recall taht + // (*r).mutate() is legal if operator* returns by value. + value_type& + operator*() const + { + return this->stored_value; + } + private: + mutable value_type stored_value; + }; + + // + // In general, we can't determine that such an iterator isn't + // writable -- we also need to store a copy of the old iterator so + // that it can be written into. + template <class Iterator> + class writable_postfix_increment_proxy + { + typedef typename iterator_value<Iterator>::type value_type; + public: + explicit writable_postfix_increment_proxy(Iterator const& x) + : stored_value(*x) + , stored_iterator(x) + {} + + // Dereferencing must return a proxy so that both *r++ = o and + // value_type(*r++) can work. In this case, *r is the same as + // *r++, and the conversion operator below is used to ensure + // readability. + writable_postfix_increment_proxy const& + operator*() const + { + return *this; + } + + // Provides readability of *r++ + operator value_type&() const + { + return stored_value; + } + + // Provides writability of *r++ + template <class T> + T const& operator=(T const& x) const + { + *this->stored_iterator = x; + return x; + } + + // This overload just in case only non-const objects are writable + template <class T> + T& operator=(T& x) const + { + *this->stored_iterator = x; + return x; + } + + // Provides X(r++) + operator Iterator const&() const + { + return stored_iterator; + } + + private: + mutable value_type stored_value; + Iterator stored_iterator; + }; + +# ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + + template <class Reference, class Value> + struct is_non_proxy_reference_impl + { + static Reference r; + + template <class R> + static typename mpl::if_< + is_convertible< + R const volatile* + , Value const volatile* + > + , char[1] + , char[2] + >::type& helper(R const&); + + BOOST_STATIC_CONSTANT(bool, value = sizeof(helper(r)) == 1); + }; + + template <class Reference, class Value> + struct is_non_proxy_reference + : mpl::bool_< + is_non_proxy_reference_impl<Reference, Value>::value + > + {}; +# else + template <class Reference, class Value> + struct is_non_proxy_reference + : is_convertible< + typename remove_reference<Reference>::type + const volatile* + , Value const volatile* + > + {}; +# endif + + // A metafunction to choose the result type of postfix ++ + // + // Because the C++98 input iterator requirements say that *r++ has + // type T (value_type), implementations of some standard + // algorithms like lexicographical_compare may use constructions + // like: + // + // *r++ < *s++ + // + // If *r++ returns a proxy (as required if r is writable but not + // multipass), this sort of expression will fail unless the proxy + // supports the operator<. Since there are any number of such + // operations, we're not going to try to support them. Therefore, + // even if r++ returns a proxy, *r++ will only return a proxy if + // *r also returns a proxy. + template <class Iterator, class Value, class Reference, class CategoryOrTraversal> + struct postfix_increment_result + : mpl::eval_if< + mpl::and_< + // A proxy is only needed for readable iterators + is_convertible<Reference,Value const&> + + // No multipass iterator can have values that disappear + // before positions can be re-visited + , mpl::not_< + is_convertible< + typename iterator_category_to_traversal<CategoryOrTraversal>::type + , forward_traversal_tag + > + > + > + , mpl::if_< + is_non_proxy_reference<Reference,Value> + , postfix_increment_proxy<Iterator> + , writable_postfix_increment_proxy<Iterator> + > + , mpl::identity<Iterator> + > + {}; + + // operator->() needs special support for input iterators to strictly meet the + // standard's requirements. If *i is not a reference type, we must still + // produce a lvalue to which a pointer can be formed. We do that by + // returning an instantiation of this special proxy class template. + template <class T> + struct operator_arrow_proxy + { + operator_arrow_proxy(T const* px) : m_value(*px) {} + T* operator->() const { return &m_value; } + // This function is needed for MWCW and BCC, which won't call operator-> + // again automatically per 13.3.1.2 para 8 + operator T*() const { return &m_value; } + mutable T m_value; + }; + + // A metafunction that gets the result type for operator->. Also + // has a static function make() which builds the result from a + // Reference + template <class ValueType, class Reference, class Pointer> + struct operator_arrow_result + { + // CWPro8.3 won't accept "operator_arrow_result::type", and we + // need that type below, so metafunction forwarding would be a + // losing proposition here. + typedef typename mpl::if_< + is_reference<Reference> + , Pointer + , operator_arrow_proxy<ValueType> + >::type type; + + static type make(Reference x) + { + return implicit_cast<type>(&x); + } + }; + +# if BOOST_WORKAROUND(BOOST_MSVC, < 1300) + // Deal with ETI + template<> + struct operator_arrow_result<int, int, int> + { + typedef int type; + }; +# endif + + // A proxy return type for operator[], needed to deal with + // iterators that may invalidate referents upon destruction. + // Consider the temporary iterator in *(a + n) + template <class Iterator> + class operator_brackets_proxy + { + // Iterator is actually an iterator_facade, so we do not have to + // go through iterator_traits to access the traits. + typedef typename Iterator::reference reference; + typedef typename Iterator::value_type value_type; + + public: + operator_brackets_proxy(Iterator const& iter) + : m_iter(iter) + {} + + operator reference() const + { + return *m_iter; + } + + operator_brackets_proxy& operator=(value_type const& val) + { + *m_iter = val; + return *this; + } + + private: + Iterator m_iter; + }; + + // A metafunction that determines whether operator[] must return a + // proxy, or whether it can simply return a copy of the value_type. + template <class ValueType, class Reference> + struct use_operator_brackets_proxy + : mpl::not_< + mpl::and_< + // Really we want an is_copy_constructible trait here, + // but is_POD will have to suffice in the meantime. + boost::is_POD<ValueType> + , iterator_writability_disabled<ValueType,Reference> + > + > + {}; + + template <class Iterator, class Value, class Reference> + struct operator_brackets_result + { + typedef typename mpl::if_< + use_operator_brackets_proxy<Value,Reference> + , operator_brackets_proxy<Iterator> + , Value + >::type type; + }; + + template <class Iterator> + operator_brackets_proxy<Iterator> make_operator_brackets_result(Iterator const& iter, mpl::true_) + { + return operator_brackets_proxy<Iterator>(iter); + } + + template <class Iterator> + typename Iterator::value_type make_operator_brackets_result(Iterator const& iter, mpl::false_) + { + return *iter; + } + + struct choose_difference_type + { + template <class I1, class I2> + struct apply + : +# ifdef BOOST_NO_ONE_WAY_ITERATOR_INTEROP + iterator_difference<I1> +# elif BOOST_WORKAROUND(BOOST_MSVC, < 1300) + mpl::if_< + is_convertible<I2,I1> + , typename I1::difference_type + , typename I2::difference_type + > +# else + mpl::eval_if< + is_convertible<I2,I1> + , iterator_difference<I1> + , iterator_difference<I2> + > +# endif + {}; + + }; + } // namespace detail + + + // Macros which describe the declarations of binary operators +# ifdef BOOST_NO_STRICT_ITERATOR_INTEROPERABILITY +# define BOOST_ITERATOR_FACADE_INTEROP_HEAD(prefix, op, result_type) \ + template < \ + class Derived1, class V1, class TC1, class Reference1, class Difference1 \ + , class Derived2, class V2, class TC2, class Reference2, class Difference2 \ + > \ + prefix typename mpl::apply2<result_type,Derived1,Derived2>::type \ + operator op( \ + iterator_facade<Derived1, V1, TC1, Reference1, Difference1> const& lhs \ + , iterator_facade<Derived2, V2, TC2, Reference2, Difference2> const& rhs) +# else +# define BOOST_ITERATOR_FACADE_INTEROP_HEAD(prefix, op, result_type) \ + template < \ + class Derived1, class V1, class TC1, class Reference1, class Difference1 \ + , class Derived2, class V2, class TC2, class Reference2, class Difference2 \ + > \ + prefix typename boost::detail::enable_if_interoperable< \ + Derived1, Derived2 \ + , typename mpl::apply2<result_type,Derived1,Derived2>::type \ + >::type \ + operator op( \ + iterator_facade<Derived1, V1, TC1, Reference1, Difference1> const& lhs \ + , iterator_facade<Derived2, V2, TC2, Reference2, Difference2> const& rhs) +# endif + +# define BOOST_ITERATOR_FACADE_PLUS_HEAD(prefix,args) \ + template <class Derived, class V, class TC, class R, class D> \ + prefix Derived operator+ args + + // + // Helper class for granting access to the iterator core interface. + // + // The simple core interface is used by iterator_facade. The core + // interface of a user/library defined iterator type should not be made public + // so that it does not clutter the public interface. Instead iterator_core_access + // should be made friend so that iterator_facade can access the core + // interface through iterator_core_access. + // + class iterator_core_access + { +# if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + // Tasteless as this may seem, making all members public allows member templates + // to work in the absence of member template friends. + public: +# else + + template <class I, class V, class TC, class R, class D> friend class iterator_facade; + +# define BOOST_ITERATOR_FACADE_RELATION(op) \ + BOOST_ITERATOR_FACADE_INTEROP_HEAD(friend,op, boost::detail::always_bool2); + + BOOST_ITERATOR_FACADE_RELATION(==) + BOOST_ITERATOR_FACADE_RELATION(!=) + + BOOST_ITERATOR_FACADE_RELATION(<) + BOOST_ITERATOR_FACADE_RELATION(>) + BOOST_ITERATOR_FACADE_RELATION(<=) + BOOST_ITERATOR_FACADE_RELATION(>=) +# undef BOOST_ITERATOR_FACADE_RELATION + + BOOST_ITERATOR_FACADE_INTEROP_HEAD( + friend, -, boost::detail::choose_difference_type) + ; + + BOOST_ITERATOR_FACADE_PLUS_HEAD( + friend inline + , (iterator_facade<Derived, V, TC, R, D> const& + , typename Derived::difference_type) + ) + ; + + BOOST_ITERATOR_FACADE_PLUS_HEAD( + friend inline + , (typename Derived::difference_type + , iterator_facade<Derived, V, TC, R, D> const&) + ) + ; + +# endif + + template <class Facade> + static typename Facade::reference dereference(Facade const& f) + { + return f.dereference(); + } + + template <class Facade> + static void increment(Facade& f) + { + f.increment(); + } + + template <class Facade> + static void decrement(Facade& f) + { + f.decrement(); + } + + template <class Facade1, class Facade2> + static bool equal(Facade1 const& f1, Facade2 const& f2, mpl::true_) + { + return f1.equal(f2); + } + + template <class Facade1, class Facade2> + static bool equal(Facade1 const& f1, Facade2 const& f2, mpl::false_) + { + return f2.equal(f1); + } + + template <class Facade> + static void advance(Facade& f, typename Facade::difference_type n) + { + f.advance(n); + } + + template <class Facade1, class Facade2> + static typename Facade1::difference_type distance_from( + Facade1 const& f1, Facade2 const& f2, mpl::true_) + { + return -f1.distance_to(f2); + } + + template <class Facade1, class Facade2> + static typename Facade2::difference_type distance_from( + Facade1 const& f1, Facade2 const& f2, mpl::false_) + { + return f2.distance_to(f1); + } + + // + // Curiously Recurring Template interface. + // + template <class I, class V, class TC, class R, class D> + static I& derived(iterator_facade<I,V,TC,R,D>& facade) + { + return *static_cast<I*>(&facade); + } + + template <class I, class V, class TC, class R, class D> + static I const& derived(iterator_facade<I,V,TC,R,D> const& facade) + { + return *static_cast<I const*>(&facade); + } + + private: + // objects of this class are useless + iterator_core_access(); //undefined + }; + + // + // iterator_facade - use as a public base class for defining new + // standard-conforming iterators. + // + template < + class Derived // The derived iterator type being constructed + , class Value + , class CategoryOrTraversal + , class Reference = Value& + , class Difference = std::ptrdiff_t + > + class iterator_facade +# ifdef BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE + : public boost::detail::iterator_facade_types< + Value, CategoryOrTraversal, Reference, Difference + >::base +# undef BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE +# endif + { + private: + // + // Curiously Recurring Template interface. + // + Derived& derived() + { + return *static_cast<Derived*>(this); + } + + Derived const& derived() const + { + return *static_cast<Derived const*>(this); + } + + typedef boost::detail::iterator_facade_types< + Value, CategoryOrTraversal, Reference, Difference + > associated_types; + + protected: + // For use by derived classes + typedef iterator_facade<Derived,Value,CategoryOrTraversal,Reference,Difference> iterator_facade_; + + public: + + typedef typename associated_types::value_type value_type; + typedef Reference reference; + typedef Difference difference_type; + typedef typename associated_types::pointer pointer; + typedef typename associated_types::iterator_category iterator_category; + + reference operator*() const + { + return iterator_core_access::dereference(this->derived()); + } + + typename boost::detail::operator_arrow_result< + value_type + , reference + , pointer + >::type + operator->() const + { + return boost::detail::operator_arrow_result< + value_type + , reference + , pointer + >::make(*this->derived()); + } + + typename boost::detail::operator_brackets_result<Derived,Value,reference>::type + operator[](difference_type n) const + { + typedef boost::detail::use_operator_brackets_proxy<Value,Reference> use_proxy; + + return boost::detail::make_operator_brackets_result<Derived>( + this->derived() + n + , use_proxy() + ); + } + + Derived& operator++() + { + iterator_core_access::increment(this->derived()); + return this->derived(); + } + +# if BOOST_WORKAROUND(BOOST_MSVC, < 1300) + typename boost::detail::postfix_increment_result<Derived,Value,Reference,CategoryOrTraversal>::type + operator++(int) + { + typename boost::detail::postfix_increment_result<Derived,Value,Reference,CategoryOrTraversal>::type + tmp(this->derived()); + ++*this; + return tmp; + } +# endif + + Derived& operator--() + { + iterator_core_access::decrement(this->derived()); + return this->derived(); + } + + Derived operator--(int) + { + Derived tmp(this->derived()); + --*this; + return tmp; + } + + Derived& operator+=(difference_type n) + { + iterator_core_access::advance(this->derived(), n); + return this->derived(); + } + + Derived& operator-=(difference_type n) + { + iterator_core_access::advance(this->derived(), -n); + return this->derived(); + } + + Derived operator-(difference_type x) const + { + Derived result(this->derived()); + return result -= x; + } + +# if BOOST_WORKAROUND(BOOST_MSVC, < 1300) + // There appears to be a bug which trashes the data of classes + // derived from iterator_facade when they are assigned unless we + // define this assignment operator. This bug is only revealed + // (so far) in STLPort debug mode, but it's clearly a codegen + // problem so we apply the workaround for all MSVC6. + iterator_facade& operator=(iterator_facade const&) + { + return *this; + } +# endif + }; + +# if !BOOST_WORKAROUND(BOOST_MSVC, < 1300) + template <class I, class V, class TC, class R, class D> + inline typename boost::detail::postfix_increment_result<I,V,R,TC>::type + operator++( + iterator_facade<I,V,TC,R,D>& i + , int + ) + { + typename boost::detail::postfix_increment_result<I,V,R,TC>::type + tmp(*static_cast<I*>(&i)); + + ++i; + + return tmp; + } +# endif + + + // + // Comparison operator implementation. The library supplied operators + // enables the user to provide fully interoperable constant/mutable + // iterator types. I.e. the library provides all operators + // for all mutable/constant iterator combinations. + // + // Note though that this kind of interoperability for constant/mutable + // iterators is not required by the standard for container iterators. + // All the standard asks for is a conversion mutable -> constant. + // Most standard library implementations nowadays provide fully interoperable + // iterator implementations, but there are still heavily used implementations + // that do not provide them. (Actually it's even worse, they do not provide + // them for only a few iterators.) + // + // ?? Maybe a BOOST_ITERATOR_NO_FULL_INTEROPERABILITY macro should + // enable the user to turn off mixed type operators + // + // The library takes care to provide only the right operator overloads. + // I.e. + // + // bool operator==(Iterator, Iterator); + // bool operator==(ConstIterator, Iterator); + // bool operator==(Iterator, ConstIterator); + // bool operator==(ConstIterator, ConstIterator); + // + // ... + // + // In order to do so it uses c++ idioms that are not yet widely supported + // by current compiler releases. The library is designed to degrade gracefully + // in the face of compiler deficiencies. In general compiler + // deficiencies result in less strict error checking and more obscure + // error messages, functionality is not affected. + // + // For full operation compiler support for "Substitution Failure Is Not An Error" + // (aka. enable_if) and boost::is_convertible is required. + // + // The following problems occur if support is lacking. + // + // Pseudo code + // + // --------------- + // AdaptorA<Iterator1> a1; + // AdaptorA<Iterator2> a2; + // + // // This will result in a no such overload error in full operation + // // If enable_if or is_convertible is not supported + // // The instantiation will fail with an error hopefully indicating that + // // there is no operator== for Iterator1, Iterator2 + // // The same will happen if no enable_if is used to remove + // // false overloads from the templated conversion constructor + // // of AdaptorA. + // + // a1 == a2; + // ---------------- + // + // AdaptorA<Iterator> a; + // AdaptorB<Iterator> b; + // + // // This will result in a no such overload error in full operation + // // If enable_if is not supported the static assert used + // // in the operator implementation will fail. + // // This will accidently work if is_convertible is not supported. + // + // a == b; + // ---------------- + // + +# ifdef BOOST_NO_ONE_WAY_ITERATOR_INTEROP +# define BOOST_ITERATOR_CONVERTIBLE(a,b) mpl::true_() +# else +# define BOOST_ITERATOR_CONVERTIBLE(a,b) is_convertible<a,b>() +# endif + +# define BOOST_ITERATOR_FACADE_INTEROP(op, result_type, return_prefix, base_op) \ + BOOST_ITERATOR_FACADE_INTEROP_HEAD(inline, op, result_type) \ + { \ + /* For those compilers that do not support enable_if */ \ + BOOST_STATIC_ASSERT(( \ + is_interoperable< Derived1, Derived2 >::value \ + )); \ + return_prefix iterator_core_access::base_op( \ + *static_cast<Derived1 const*>(&lhs) \ + , *static_cast<Derived2 const*>(&rhs) \ + , BOOST_ITERATOR_CONVERTIBLE(Derived2,Derived1) \ + ); \ + } + +# define BOOST_ITERATOR_FACADE_RELATION(op, return_prefix, base_op) \ + BOOST_ITERATOR_FACADE_INTEROP( \ + op \ + , boost::detail::always_bool2 \ + , return_prefix \ + , base_op \ + ) + + BOOST_ITERATOR_FACADE_RELATION(==, return, equal) + BOOST_ITERATOR_FACADE_RELATION(!=, return !, equal) + + BOOST_ITERATOR_FACADE_RELATION(<, return 0 >, distance_from) + BOOST_ITERATOR_FACADE_RELATION(>, return 0 <, distance_from) + BOOST_ITERATOR_FACADE_RELATION(<=, return 0 >=, distance_from) + BOOST_ITERATOR_FACADE_RELATION(>=, return 0 <=, distance_from) +# undef BOOST_ITERATOR_FACADE_RELATION + + // operator- requires an additional part in the static assertion + BOOST_ITERATOR_FACADE_INTEROP( + - + , boost::detail::choose_difference_type + , return + , distance_from + ) +# undef BOOST_ITERATOR_FACADE_INTEROP +# undef BOOST_ITERATOR_FACADE_INTEROP_HEAD + +# define BOOST_ITERATOR_FACADE_PLUS(args) \ + BOOST_ITERATOR_FACADE_PLUS_HEAD(inline, args) \ + { \ + Derived tmp(static_cast<Derived const&>(i)); \ + return tmp += n; \ + } + +BOOST_ITERATOR_FACADE_PLUS(( + iterator_facade<Derived, V, TC, R, D> const& i + , typename Derived::difference_type n +)) + +BOOST_ITERATOR_FACADE_PLUS(( + typename Derived::difference_type n + , iterator_facade<Derived, V, TC, R, D> const& i +)) +# undef BOOST_ITERATOR_FACADE_PLUS +# undef BOOST_ITERATOR_FACADE_PLUS_HEAD + +} // namespace boost + +#include <boost/iterator/detail/config_undef.hpp> + +#endif // BOOST_ITERATOR_FACADE_23022003THW_HPP diff --git a/ext/boost/iterator/iterator_traits.hpp b/ext/boost/iterator/iterator_traits.hpp new file mode 100644 index 0000000000..960970e8db --- /dev/null +++ b/ext/boost/iterator/iterator_traits.hpp @@ -0,0 +1,92 @@ +// 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) +#ifndef ITERATOR_TRAITS_DWA200347_HPP +# define ITERATOR_TRAITS_DWA200347_HPP + +# include <boost/detail/iterator.hpp> +# include <boost/detail/workaround.hpp> + +namespace boost { + +// Unfortunately, g++ 2.95.x chokes when we define a class template +// iterator_category which has the same name as its +// std::iterator_category() function, probably due in part to the +// "std:: is visible globally" hack it uses. Use +// BOOST_ITERATOR_CATEGORY to write code that's portable to older +// GCCs. + +# if BOOST_WORKAROUND(__GNUC__, <= 2) +# define BOOST_ITERATOR_CATEGORY iterator_category_ +# else +# define BOOST_ITERATOR_CATEGORY iterator_category +# endif + + +template <class Iterator> +struct iterator_value +{ + typedef typename boost::detail::iterator_traits<Iterator>::value_type type; +}; + +template <class Iterator> +struct iterator_reference +{ + typedef typename boost::detail::iterator_traits<Iterator>::reference type; +}; + + +template <class Iterator> +struct iterator_pointer +{ + typedef typename boost::detail::iterator_traits<Iterator>::pointer type; +}; + +template <class Iterator> +struct iterator_difference +{ + typedef typename boost::detail::iterator_traits<Iterator>::difference_type type; +}; + +template <class Iterator> +struct BOOST_ITERATOR_CATEGORY +{ + typedef typename boost::detail::iterator_traits<Iterator>::iterator_category type; +}; + +# if BOOST_WORKAROUND(BOOST_MSVC, < 1300) +template <> +struct iterator_value<int> +{ + typedef void type; +}; + +template <> +struct iterator_reference<int> +{ + typedef void type; +}; + +template <> +struct iterator_pointer<int> +{ + typedef void type; +}; + +template <> +struct iterator_difference<int> +{ + typedef void type; +}; + +template <> +struct BOOST_ITERATOR_CATEGORY<int> +{ + typedef void type; +}; +# endif + +} // namespace boost::iterator + +#endif // ITERATOR_TRAITS_DWA200347_HPP diff --git a/ext/boost/iterator/new_iterator_tests.hpp b/ext/boost/iterator/new_iterator_tests.hpp new file mode 100644 index 0000000000..caad700aef --- /dev/null +++ b/ext/boost/iterator/new_iterator_tests.hpp @@ -0,0 +1,264 @@ +#ifndef BOOST_NEW_ITERATOR_TESTS_HPP +# define BOOST_NEW_ITERATOR_TESTS_HPP + +// +// Copyright (c) David Abrahams 2001. +// Copyright (c) Jeremy Siek 2001-2003. +// Copyright (c) Thomas Witt 2002. +// +// 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) +// + +// This is meant to be the beginnings of a comprehensive, generic +// test suite for STL concepts such as iterators and containers. +// +// Revision History: +// 28 Oct 2002 Started update for new iterator categories +// (Jeremy Siek) +// 28 Apr 2002 Fixed input iterator requirements. +// For a == b a++ == b++ is no longer required. +// See 24.1.1/3 for details. +// (Thomas Witt) +// 08 Feb 2001 Fixed bidirectional iterator test so that +// --i is no longer a precondition. +// (Jeremy Siek) +// 04 Feb 2001 Added lvalue test, corrected preconditions +// (David Abrahams) + +# include <iterator> +# include <boost/type_traits.hpp> +# include <boost/static_assert.hpp> +# include <boost/concept_archetype.hpp> // for detail::dummy_constructor +# include <boost/detail/iterator.hpp> +# include <boost/pending/iterator_tests.hpp> +# include <boost/iterator/is_readable_iterator.hpp> +# include <boost/iterator/is_lvalue_iterator.hpp> + +# include <boost/iterator/detail/config_def.hpp> +# include <boost/detail/is_incrementable.hpp> +# include <boost/detail/lightweight_test.hpp> + +namespace boost { + + +// Do separate tests for *i++ so we can treat, e.g., smart pointers, +// as readable and/or writable iterators. +template <class Iterator, class T> +void readable_iterator_traversal_test(Iterator i1, T v, mpl::true_) +{ + T v2(*i1++); + BOOST_TEST(v == v2); +} + +template <class Iterator, class T> +void readable_iterator_traversal_test(const Iterator i1, T v, mpl::false_) +{} + +template <class Iterator, class T> +void writable_iterator_traversal_test(Iterator i1, T v, mpl::true_) +{ + ++i1; // we just wrote into that position + *i1++ = v; + Iterator x(i1++); + (void)x; +} + +template <class Iterator, class T> +void writable_iterator_traversal_test(const Iterator i1, T v, mpl::false_) +{} + + +// Preconditions: *i == v +template <class Iterator, class T> +void readable_iterator_test(const Iterator i1, T v) +{ + Iterator i2(i1); // Copy Constructible + typedef typename detail::iterator_traits<Iterator>::reference ref_t; + ref_t r1 = *i1; + ref_t r2 = *i2; + T v1 = r1; + T v2 = r2; + BOOST_TEST(v1 == v); + BOOST_TEST(v2 == v); + +# if !BOOST_WORKAROUND(__MWERKS__, <= 0x2407) + readable_iterator_traversal_test(i1, v, detail::is_postfix_incrementable<Iterator>()); + + // I think we don't really need this as it checks the same things as + // the above code. + BOOST_STATIC_ASSERT(is_readable_iterator<Iterator>::value); +# endif +} + +template <class Iterator, class T> +void writable_iterator_test(Iterator i, T v, T v2) +{ + Iterator i2(i); // Copy Constructible + *i2 = v; + +# if !BOOST_WORKAROUND(__MWERKS__, <= 0x2407) + writable_iterator_traversal_test( + i, v2, mpl::and_< + detail::is_incrementable<Iterator> + , detail::is_postfix_incrementable<Iterator> + >()); +# endif +} + +template <class Iterator> +void swappable_iterator_test(Iterator i, Iterator j) +{ + Iterator i2(i), j2(j); + typename detail::iterator_traits<Iterator>::value_type bi = *i, bj = *j; + iter_swap(i2, j2); + typename detail::iterator_traits<Iterator>::value_type ai = *i, aj = *j; + BOOST_TEST(bi == aj && bj == ai); +} + +template <class Iterator, class T> +void constant_lvalue_iterator_test(Iterator i, T v1) +{ + Iterator i2(i); + typedef typename detail::iterator_traits<Iterator>::value_type value_type; + typedef typename detail::iterator_traits<Iterator>::reference reference; + BOOST_STATIC_ASSERT((is_same<const value_type&, reference>::value)); + const T& v2 = *i2; + BOOST_TEST(v1 == v2); +# ifndef BOOST_NO_LVALUE_RETURN_DETECTION + BOOST_STATIC_ASSERT(is_lvalue_iterator<Iterator>::value); + BOOST_STATIC_ASSERT(!is_non_const_lvalue_iterator<Iterator>::value); +# endif +} + +template <class Iterator, class T> +void non_const_lvalue_iterator_test(Iterator i, T v1, T v2) +{ + Iterator i2(i); + typedef typename detail::iterator_traits<Iterator>::value_type value_type; + typedef typename detail::iterator_traits<Iterator>::reference reference; + BOOST_STATIC_ASSERT((is_same<value_type&, reference>::value)); + T& v3 = *i2; + BOOST_TEST(v1 == v3); + + // A non-const lvalue iterator is not neccessarily writable, but we + // are assuming the value_type is assignable here + *i = v2; + + T& v4 = *i2; + BOOST_TEST(v2 == v4); +# ifndef BOOST_NO_LVALUE_RETURN_DETECTION + BOOST_STATIC_ASSERT(is_lvalue_iterator<Iterator>::value); + BOOST_STATIC_ASSERT(is_non_const_lvalue_iterator<Iterator>::value); +# endif +} + +template <class Iterator, class T> +void forward_readable_iterator_test(Iterator i, Iterator j, T val1, T val2) +{ + Iterator i2; + Iterator i3(i); + i2 = i; + BOOST_TEST(i2 == i3); + BOOST_TEST(i != j); + BOOST_TEST(i2 != j); + readable_iterator_test(i, val1); + readable_iterator_test(i2, val1); + readable_iterator_test(i3, val1); + + BOOST_TEST(i == i2++); + BOOST_TEST(i != ++i3); + + readable_iterator_test(i2, val2); + readable_iterator_test(i3, val2); + + readable_iterator_test(i, val1); +} + +template <class Iterator, class T> +void forward_swappable_iterator_test(Iterator i, Iterator j, T val1, T val2) +{ + forward_readable_iterator_test(i, j, val1, val2); + Iterator i2 = i; + ++i2; + swappable_iterator_test(i, i2); +} + +// bidirectional +// Preconditions: *i == v1, *++i == v2 +template <class Iterator, class T> +void bidirectional_readable_iterator_test(Iterator i, T v1, T v2) +{ + Iterator j(i); + ++j; + forward_readable_iterator_test(i, j, v1, v2); + ++i; + + Iterator i1 = i, i2 = i; + + BOOST_TEST(i == i1--); + BOOST_TEST(i != --i2); + + readable_iterator_test(i, v2); + readable_iterator_test(i1, v1); + readable_iterator_test(i2, v1); + + --i; + BOOST_TEST(i == i1); + BOOST_TEST(i == i2); + ++i1; + ++i2; + + readable_iterator_test(i, v1); + readable_iterator_test(i1, v2); + readable_iterator_test(i2, v2); +} + +// random access +// Preconditions: [i,i+N) is a valid range +template <class Iterator, class TrueVals> +void random_access_readable_iterator_test(Iterator i, int N, TrueVals vals) +{ + bidirectional_readable_iterator_test(i, vals[0], vals[1]); + const Iterator j = i; + int c; + + for (c = 0; c < N-1; ++c) + { + BOOST_TEST(i == j + c); + BOOST_TEST(*i == vals[c]); + typename detail::iterator_traits<Iterator>::value_type x = j[c]; + BOOST_TEST(*i == x); + BOOST_TEST(*i == *(j + c)); + BOOST_TEST(*i == *(c + j)); + ++i; + BOOST_TEST(i > j); + BOOST_TEST(i >= j); + BOOST_TEST(j <= i); + BOOST_TEST(j < i); + } + + Iterator k = j + N - 1; + for (c = 0; c < N-1; ++c) + { + BOOST_TEST(i == k - c); + BOOST_TEST(*i == vals[N - 1 - c]); + typename detail::iterator_traits<Iterator>::value_type x = j[N - 1 - c]; + BOOST_TEST(*i == x); + Iterator q = k - c; + BOOST_TEST(*i == *q); + BOOST_TEST(i > j); + BOOST_TEST(i >= j); + BOOST_TEST(j <= i); + BOOST_TEST(j < i); + --i; + } +} + +} // namespace boost + +# include <boost/iterator/detail/config_undef.hpp> + +#endif // BOOST_NEW_ITERATOR_TESTS_HPP diff --git a/ext/boost/iterator/permutation_iterator.hpp b/ext/boost/iterator/permutation_iterator.hpp new file mode 100644 index 0000000000..23d11986da --- /dev/null +++ b/ext/boost/iterator/permutation_iterator.hpp @@ -0,0 +1,72 @@ +// (C) Copyright Toon Knapen 2001. +// (C) Copyright David Abrahams 2003. +// (C) Copyright Roland Richter 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_PERMUTATION_ITERATOR_HPP +#define BOOST_PERMUTATION_ITERATOR_HPP + +#include <iterator> + +#include <boost/iterator/iterator_adaptor.hpp> + + +namespace boost +{ + +template< class ElementIterator + , class IndexIterator> +class permutation_iterator + : public iterator_adaptor< + permutation_iterator<ElementIterator, IndexIterator> + , IndexIterator, typename detail::iterator_traits<ElementIterator>::value_type + , use_default, typename detail::iterator_traits<ElementIterator>::reference> +{ + typedef iterator_adaptor< + permutation_iterator<ElementIterator, IndexIterator> + , IndexIterator, typename detail::iterator_traits<ElementIterator>::value_type + , use_default, typename detail::iterator_traits<ElementIterator>::reference> super_t; + + friend class iterator_core_access; + +public: + permutation_iterator() : m_elt_iter() {} + + explicit permutation_iterator(ElementIterator x, IndexIterator y) + : super_t(y), m_elt_iter(x) {} + + template<class OtherElementIterator, class OtherIndexIterator> + permutation_iterator( + permutation_iterator<OtherElementIterator, OtherIndexIterator> const& r + , typename enable_if_convertible<OtherElementIterator, ElementIterator>::type* = 0 + , typename enable_if_convertible<OtherIndexIterator, IndexIterator>::type* = 0 + ) + : super_t(r.base()), m_elt_iter(r.m_elt_iter) + {} + +private: + typename super_t::reference dereference() const + { return *(m_elt_iter + *this->base()); } + +#ifndef BOOST_NO_MEMBER_TEMPLATE_FRIENDS + template <class,class> friend class permutation_iterator; +#else + public: +#endif + ElementIterator m_elt_iter; +}; + + +template <class ElementIterator, class IndexIterator> +permutation_iterator<ElementIterator, IndexIterator> +make_permutation_iterator( ElementIterator e, IndexIterator i ) +{ + return permutation_iterator<ElementIterator, IndexIterator>( e, i ); +} + + +} // namespace boost + +#endif diff --git a/ext/boost/iterator/reverse_iterator.hpp b/ext/boost/iterator/reverse_iterator.hpp new file mode 100644 index 0000000000..97b6b4861d --- /dev/null +++ b/ext/boost/iterator/reverse_iterator.hpp @@ -0,0 +1,69 @@ +// (C) Copyright David Abrahams 2002. +// (C) Copyright Jeremy Siek 2002. +// (C) Copyright Thomas Witt 2002. +// 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_REVERSE_ITERATOR_23022003THW_HPP +#define BOOST_REVERSE_ITERATOR_23022003THW_HPP + +#include <boost/iterator.hpp> +#include <boost/utility.hpp> +#include <boost/iterator/iterator_adaptor.hpp> + +namespace boost +{ + + // + // + // + template <class Iterator> + class reverse_iterator + : public iterator_adaptor< reverse_iterator<Iterator>, Iterator > + { + typedef iterator_adaptor< reverse_iterator<Iterator>, Iterator > super_t; + + friend class iterator_core_access; + + public: + reverse_iterator() {} + + explicit reverse_iterator(Iterator x) + : super_t(x) {} + + template<class OtherIterator> + reverse_iterator( + reverse_iterator<OtherIterator> const& r + , typename enable_if_convertible<OtherIterator, Iterator>::type* = 0 + ) + : super_t(r.base()) + {} + + private: + typename super_t::reference dereference() const { return *boost::prior(this->base()); } + + void increment() { --this->base_reference(); } + void decrement() { ++this->base_reference(); } + + void advance(typename super_t::difference_type n) + { + this->base_reference() += -n; + } + + template <class OtherIterator> + typename super_t::difference_type + distance_to(reverse_iterator<OtherIterator> const& y) const + { + return this->base_reference() - y.base(); + } + }; + + template <class BidirectionalIterator> + reverse_iterator<BidirectionalIterator> make_reverse_iterator(BidirectionalIterator x) + { + return reverse_iterator<BidirectionalIterator>(x); + } + +} // namespace boost + +#endif // BOOST_REVERSE_ITERATOR_23022003THW_HPP diff --git a/ext/boost/iterator/transform_iterator.hpp b/ext/boost/iterator/transform_iterator.hpp new file mode 100644 index 0000000000..e449a8b0d3 --- /dev/null +++ b/ext/boost/iterator/transform_iterator.hpp @@ -0,0 +1,188 @@ +// (C) Copyright David Abrahams 2002. +// (C) Copyright Jeremy Siek 2002. +// (C) Copyright Thomas Witt 2002. +// 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_TRANSFORM_ITERATOR_23022003THW_HPP +#define BOOST_TRANSFORM_ITERATOR_23022003THW_HPP + +#include <boost/function.hpp> +#include <boost/iterator.hpp> +#include <boost/iterator/detail/enable_if.hpp> +#include <boost/iterator/iterator_adaptor.hpp> +#include <boost/iterator/iterator_categories.hpp> +#include <boost/mpl/not.hpp> +#include <boost/mpl/bool.hpp> +#include <boost/type_traits/function_traits.hpp> +#include <boost/type_traits/is_const.hpp> +#include <boost/type_traits/is_class.hpp> +#include <boost/type_traits/is_function.hpp> +#include <boost/type_traits/is_reference.hpp> +#include <boost/type_traits/remove_const.hpp> +#include <boost/type_traits/remove_reference.hpp> + +#if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1310)) +# include <boost/type_traits/is_base_and_derived.hpp> + +#endif +#include <boost/iterator/detail/config_def.hpp> + + +namespace boost +{ + template <class UnaryFunction, class Iterator, class Reference = use_default, class Value = use_default> + class transform_iterator; + + namespace detail + { + + template <class UnaryFunc> + struct function_object_result + { + typedef typename UnaryFunc::result_type type; + }; + +#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + template <class Return, class Argument> + struct function_object_result<Return(*)(Argument)> + { + typedef Return type; + }; +#endif + + // Compute the iterator_adaptor instantiation to be used for transform_iterator + template <class UnaryFunc, class Iterator, class Reference, class Value> + struct transform_iterator_base + { + private: + // By default, dereferencing the iterator yields the same as + // the function. Do we need to adjust the way + // function_object_result is computed for the standard + // proposal (e.g. using Doug's result_of)? + typedef typename ia_dflt_help< + Reference + , function_object_result<UnaryFunc> + >::type reference; + + // To get the default for Value: remove any reference on the + // result type, but retain any constness to signal + // non-writability. Note that if we adopt Thomas' suggestion + // to key non-writability *only* on the Reference argument, + // we'd need to strip constness here as well. + typedef typename ia_dflt_help< + Value + , remove_reference<reference> + >::type cv_value_type; + + public: + typedef iterator_adaptor< + transform_iterator<UnaryFunc, Iterator, Reference, Value> + , Iterator + , cv_value_type + , use_default // Leave the traversal category alone + , reference + > type; + }; + } + + template <class UnaryFunc, class Iterator, class Reference, class Value> + class transform_iterator + : public boost::detail::transform_iterator_base<UnaryFunc, Iterator, Reference, Value>::type + { + typedef typename + boost::detail::transform_iterator_base<UnaryFunc, Iterator, Reference, Value>::type + super_t; + + friend class iterator_core_access; + + public: + transform_iterator() { } + + transform_iterator(Iterator const& x, UnaryFunc f) + : super_t(x), m_f(f) { } + + explicit transform_iterator(Iterator const& x) + : super_t(x) + { + // Pro8 is a little too aggressive about instantiating the + // body of this function. +#if !BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3003)) + // don't provide this constructor if UnaryFunc is a + // function pointer type, since it will be 0. Too dangerous. + BOOST_STATIC_ASSERT(is_class<UnaryFunc>::value); +#endif + } + + template< + class OtherUnaryFunction + , class OtherIterator + , class OtherReference + , class OtherValue> + transform_iterator( + transform_iterator<OtherUnaryFunction, OtherIterator, OtherReference, OtherValue> const& t + , typename enable_if_convertible<OtherIterator, Iterator>::type* = 0 +#if !BOOST_WORKAROUND(BOOST_MSVC, == 1310) + , typename enable_if_convertible<OtherUnaryFunction, UnaryFunc>::type* = 0 +#endif + ) + : super_t(t.base()), m_f(t.functor()) + {} + + UnaryFunc functor() const + { return m_f; } + + private: + typename super_t::reference dereference() const + { return m_f(*this->base()); } + + // Probably should be the initial base class so it can be + // optimized away via EBO if it is an empty class. + UnaryFunc m_f; + }; + + template <class UnaryFunc, class Iterator> + transform_iterator<UnaryFunc, Iterator> + make_transform_iterator(Iterator it, UnaryFunc fun) + { + return transform_iterator<UnaryFunc, Iterator>(it, fun); + } + + // Version which allows explicit specification of the UnaryFunc + // type. + // + // This generator is not provided if UnaryFunc is a function + // pointer type, because it's too dangerous: the default-constructed + // function pointer in the iterator be 0, leading to a runtime + // crash. + template <class UnaryFunc, class Iterator> +#if BOOST_WORKAROUND(BOOST_MSVC, <= 1300) + typename mpl::if_< +#else + typename iterators::enable_if< +#endif + is_class<UnaryFunc> // We should probably find a cheaper test than is_class<> + , transform_iterator<UnaryFunc, Iterator> +#if BOOST_WORKAROUND(BOOST_MSVC, <= 1300) + , int[3] +#endif + >::type + make_transform_iterator(Iterator it) + { + return transform_iterator<UnaryFunc, Iterator>(it, UnaryFunc()); + } + +#if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION ) && !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) + template <class Return, class Argument, class Iterator> + transform_iterator< Return (*)(Argument), Iterator, Return> + make_transform_iterator(Iterator it, Return (*fun)(Argument)) + { + return transform_iterator<Return (*)(Argument), Iterator, Return>(it, fun); + } +#endif + +} // namespace boost + +#include <boost/iterator/detail/config_undef.hpp> + +#endif // BOOST_TRANSFORM_ITERATOR_23022003THW_HPP diff --git a/ext/boost/iterator/zip_iterator.hpp b/ext/boost/iterator/zip_iterator.hpp new file mode 100644 index 0000000000..f3896ad955 --- /dev/null +++ b/ext/boost/iterator/zip_iterator.hpp @@ -0,0 +1,585 @@ +// Copyright David Abrahams and Thomas Becker 2000-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_ZIP_ITERATOR_TMB_07_13_2003_HPP_ +# define BOOST_ZIP_ITERATOR_TMB_07_13_2003_HPP_ + +#include <stddef.h> +#include <boost/iterator.hpp> +#include <boost/iterator/iterator_traits.hpp> +#include <boost/iterator/iterator_facade.hpp> +#include <boost/iterator/iterator_adaptor.hpp> // for enable_if_convertible +#include <boost/iterator/iterator_categories.hpp> +#include <boost/detail/iterator.hpp> + +#include <boost/iterator/detail/minimum_category.hpp> + +#include <boost/tuple/tuple.hpp> + +#include <boost/type_traits/is_same.hpp> +#include <boost/mpl/and.hpp> +#include <boost/mpl/apply.hpp> +#include <boost/mpl/eval_if.hpp> +#include <boost/mpl/lambda.hpp> +#include <boost/mpl/placeholders.hpp> +#include <boost/mpl/aux_/lambda_support.hpp> + +namespace boost { + + // Zip iterator forward declaration for zip_iterator_base + template<typename IteratorTuple> + class zip_iterator; + + // One important design goal of the zip_iterator is to isolate all + // functionality whose implementation relies on the current tuple + // implementation. This goal has been achieved as follows: Inside + // the namespace detail there is a namespace tuple_impl_specific. + // This namespace encapsulates all functionality that is specific + // to the current Boost tuple implementation. More precisely, the + // namespace tuple_impl_specific provides the following tuple + // algorithms and meta-algorithms for the current Boost tuple + // implementation: + // + // tuple_meta_transform + // tuple_meta_accumulate + // tuple_transform + // tuple_for_each + // + // If the tuple implementation changes, all that needs to be + // replaced is the implementation of these four (meta-)algorithms. + + namespace detail + { + + // Functors to be used with tuple algorithms + // + template<typename DiffType> + class advance_iterator + { + public: + advance_iterator(DiffType step) : m_step(step) {} + + template<typename Iterator> + void operator()(Iterator& it) const + { it += m_step; } + + private: + DiffType m_step; + }; + // + struct increment_iterator + { + template<typename Iterator> + void operator()(Iterator& it) + { ++it; } + }; + // + struct decrement_iterator + { + template<typename Iterator> + void operator()(Iterator& it) + { --it; } + }; + // + struct dereference_iterator + { + template<typename Iterator> + struct apply + { + typedef typename + iterator_traits<Iterator>::reference + type; + }; + + template<typename Iterator> + typename apply<Iterator>::type operator()(Iterator const& it) + { return *it; } + }; + + + // The namespace tuple_impl_specific provides two meta- + // algorithms and two algorithms for tuples. + // + namespace tuple_impl_specific + { + // Meta-transform algorithm for tuples + // + template<typename Tuple, class UnaryMetaFun> + struct tuple_meta_transform; + + template<typename Tuple, class UnaryMetaFun> + struct tuple_meta_transform_impl + { + typedef tuples::cons< + typename mpl::apply1< + typename mpl::lambda<UnaryMetaFun>::type + , typename Tuple::head_type + >::type + , typename tuple_meta_transform< + typename Tuple::tail_type + , UnaryMetaFun + >::type + > type; + }; + + template<typename Tuple, class UnaryMetaFun> + struct tuple_meta_transform + : mpl::eval_if< + boost::is_same<Tuple, tuples::null_type> + , mpl::identity<tuples::null_type> + , tuple_meta_transform_impl<Tuple, UnaryMetaFun> + > + { + }; + + // Meta-accumulate algorithm for tuples. Note: The template + // parameter StartType corresponds to the initial value in + // ordinary accumulation. + // + template<class Tuple, class BinaryMetaFun, class StartType> + struct tuple_meta_accumulate; + + template< + typename Tuple + , class BinaryMetaFun + , typename StartType + > + struct tuple_meta_accumulate_impl + { + typedef typename mpl::apply2< + typename mpl::lambda<BinaryMetaFun>::type + , typename Tuple::head_type + , typename tuple_meta_accumulate< + typename Tuple::tail_type + , BinaryMetaFun + , StartType + >::type + >::type type; + }; + + template< + typename Tuple + , class BinaryMetaFun + , typename StartType + > + struct tuple_meta_accumulate + : mpl::eval_if< +#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) + mpl::or_< +#endif + boost::is_same<Tuple, tuples::null_type> +#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) + , boost::is_same<Tuple,int> + > +#endif + , mpl::identity<StartType> + , tuple_meta_accumulate_impl< + Tuple + , BinaryMetaFun + , StartType + > + > + { + }; + +#if defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) \ + || ( \ + BOOST_WORKAROUND(BOOST_INTEL_CXX_VERSION, != 0) && defined(_MSC_VER) \ + ) +// Not sure why intel's partial ordering fails in this case, but I'm +// assuming int's an MSVC bug-compatibility feature. + +# define BOOST_TUPLE_ALGO_DISPATCH +# define BOOST_TUPLE_ALGO(algo) algo##_impl +# define BOOST_TUPLE_ALGO_TERMINATOR , int +# define BOOST_TUPLE_ALGO_RECURSE , ... +#else +# define BOOST_TUPLE_ALGO(algo) algo +# define BOOST_TUPLE_ALGO_TERMINATOR +# define BOOST_TUPLE_ALGO_RECURSE +#endif + + // transform algorithm for tuples. The template parameter Fun + // must be a unary functor which is also a unary metafunction + // class that computes its return type based on its argument + // type. For example: + // + // struct to_ptr + // { + // template <class Arg> + // struct apply + // { + // typedef Arg* type; + // } + // + // template <class Arg> + // Arg* operator()(Arg x); + // }; + template<typename Fun> + tuples::null_type BOOST_TUPLE_ALGO(tuple_transform) + (tuples::null_type const&, Fun BOOST_TUPLE_ALGO_TERMINATOR) + { return tuples::null_type(); } + + template<typename Tuple, typename Fun> + typename tuple_meta_transform< + Tuple + , Fun + >::type + + BOOST_TUPLE_ALGO(tuple_transform)( + const Tuple& t, + Fun f + BOOST_TUPLE_ALGO_RECURSE + ) + { + typedef typename tuple_meta_transform< + BOOST_DEDUCED_TYPENAME Tuple::tail_type + , Fun + >::type transformed_tail_type; + + return tuples::cons< + BOOST_DEDUCED_TYPENAME mpl::apply1< + Fun, BOOST_DEDUCED_TYPENAME Tuple::head_type + >::type + , transformed_tail_type + >( + f(boost::tuples::get<0>(t)), tuple_transform(t.get_tail(), f) + ); + } + +#ifdef BOOST_TUPLE_ALGO_DISPATCH + template<typename Tuple, typename Fun> + typename tuple_meta_transform< + Tuple + , Fun + >::type + + tuple_transform( + const Tuple& t, + Fun f + ) + { + return tuple_transform_impl(t, f, 1); + } +#endif + + // for_each algorithm for tuples. + // + template<typename Fun> + Fun BOOST_TUPLE_ALGO(tuple_for_each)( + tuples::null_type + , Fun f BOOST_TUPLE_ALGO_TERMINATOR + ) + { return f; } + + + template<typename Tuple, typename Fun> + Fun BOOST_TUPLE_ALGO(tuple_for_each)( + Tuple& t + , Fun f BOOST_TUPLE_ALGO_RECURSE) + { + f( t.get_head() ); + return tuple_for_each(t.get_tail(), f); + } + +#ifdef BOOST_TUPLE_ALGO_DISPATCH + template<typename Tuple, typename Fun> + Fun + tuple_for_each( + Tuple& t, + Fun f + ) + { + return tuple_for_each_impl(t, f, 1); + } +#endif + + // Equality of tuples. NOTE: "==" for tuples currently (7/2003) + // has problems under some compilers, so I just do my own. + // No point in bringing in a bunch of #ifdefs here. This is + // going to go away with the next tuple implementation anyway. + // + inline bool tuple_equal(tuples::null_type, tuples::null_type) + { return true; } + + template<typename Tuple1, typename Tuple2> + bool tuple_equal( + Tuple1 const& t1, + Tuple2 const& t2 + ) + { + return t1.get_head() == t2.get_head() && + tuple_equal(t1.get_tail(), t2.get_tail()); + } + } + // + // end namespace tuple_impl_specific + + template<typename Iterator> + struct iterator_reference + { + typedef typename iterator_traits<Iterator>::reference type; + }; + +#ifdef BOOST_MPL_CFG_NO_FULL_LAMBDA_SUPPORT + // Hack because BOOST_MPL_AUX_LAMBDA_SUPPORT doesn't seem to work + // out well. Instantiating the nested apply template also + // requires instantiating iterator_traits on the + // placeholder. Instead we just specialize it as a metafunction + // class. + template<> + struct iterator_reference<mpl::_1> + { + template <class T> + struct apply : iterator_reference<T> {}; + }; +#endif + + // Metafunction to obtain the type of the tuple whose element types + // are the reference types of an iterator tuple. + // + template<typename IteratorTuple> + struct tuple_of_references + : tuple_impl_specific::tuple_meta_transform< + IteratorTuple, + iterator_reference<mpl::_1> + > + { + }; + + // Metafunction to obtain the minimal traversal tag in a tuple + // of iterators. + // + template<typename IteratorTuple> + struct minimum_traversal_category_in_iterator_tuple + { + typedef typename tuple_impl_specific::tuple_meta_transform< + IteratorTuple + , iterator_traversal<> + >::type tuple_of_traversal_tags; + + typedef typename tuple_impl_specific::tuple_meta_accumulate< + tuple_of_traversal_tags + , minimum_category<> + , random_access_traversal_tag + >::type type; + }; + +#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) // ETI workaround + template <> + struct minimum_traversal_category_in_iterator_tuple<int> + { + typedef int type; + }; +#endif + + // We need to call tuple_meta_accumulate with mpl::and_ as the + // accumulating functor. To this end, we need to wrap it into + // a struct that has exactly two arguments (that is, template + // parameters) and not five, like mpl::and_ does. + // + template<typename Arg1, typename Arg2> + struct and_with_two_args + : mpl::and_<Arg1, Arg2> + { + }; + +# ifdef BOOST_MPL_CFG_NO_FULL_LAMBDA_SUPPORT + // Hack because BOOST_MPL_AUX_LAMBDA_SUPPORT doesn't seem to work + // out well. In this case I think it's an MPL bug + template<> + struct and_with_two_args<mpl::_1,mpl::_2> + { + template <class A1, class A2> + struct apply : mpl::and_<A1,A2> + {}; + }; +# endif + + /////////////////////////////////////////////////////////////////// + // + // Class zip_iterator_base + // + // Builds and exposes the iterator facade type from which the zip + // iterator will be derived. + // + template<typename IteratorTuple> + struct zip_iterator_base + { + private: + // Reference type is the type of the tuple obtained from the + // iterators' reference types. + typedef typename + detail::tuple_of_references<IteratorTuple>::type reference; + + // Value type is the same as reference type. + typedef reference value_type; + + // Difference type is the first iterator's difference type + typedef typename iterator_traits< + typename tuples::element<0, IteratorTuple>::type + >::difference_type difference_type; + + // Traversal catetgory is the minimum traversal category in the + // iterator tuple. + typedef typename + detail::minimum_traversal_category_in_iterator_tuple< + IteratorTuple + >::type traversal_category; + public: + + // The iterator facade type from which the zip iterator will + // be derived. + typedef iterator_facade< + zip_iterator<IteratorTuple>, + value_type, + traversal_category, + reference, + difference_type + > type; + }; + + template <> + struct zip_iterator_base<int> + { + typedef int type; + }; + } + + ///////////////////////////////////////////////////////////////////// + // + // zip_iterator class definition + // + template<typename IteratorTuple> + class zip_iterator : + public detail::zip_iterator_base<IteratorTuple>::type + { + + // Typedef super_t as our base class. + typedef typename + detail::zip_iterator_base<IteratorTuple>::type super_t; + + // iterator_core_access is the iterator's best friend. + friend class iterator_core_access; + + public: + + // Construction + // ============ + + // Default constructor + zip_iterator() { } + + // Constructor from iterator tuple + zip_iterator(IteratorTuple iterator_tuple) + : m_iterator_tuple(iterator_tuple) + { } + + // Copy constructor + template<typename OtherIteratorTuple> + zip_iterator( + const zip_iterator<OtherIteratorTuple>& other, + typename enable_if_convertible< + OtherIteratorTuple, + IteratorTuple + >::type* = 0 + ) : m_iterator_tuple(other.get_iterator_tuple()) + {} + + // Get method for the iterator tuple. + const IteratorTuple& get_iterator_tuple() const + { return m_iterator_tuple; } + + private: + + // Implementation of Iterator Operations + // ===================================== + + // Dereferencing returns a tuple built from the dereferenced + // iterators in the iterator tuple. + typename super_t::reference dereference() const + { + return detail::tuple_impl_specific::tuple_transform( + get_iterator_tuple(), + detail::dereference_iterator() + ); + } + + // Two zip iterators are equal if all iterators in the iterator + // tuple are equal. NOTE: It should be possible to implement this + // as + // + // return get_iterator_tuple() == other.get_iterator_tuple(); + // + // but equality of tuples currently (7/2003) does not compile + // under several compilers. No point in bringing in a bunch + // of #ifdefs here. + // + template<typename OtherIteratorTuple> + bool equal(const zip_iterator<OtherIteratorTuple>& other) const + { + return detail::tuple_impl_specific::tuple_equal( + get_iterator_tuple(), + other.get_iterator_tuple() + ); + } + + // Advancing a zip iterator means to advance all iterators in the + // iterator tuple. + void advance(typename super_t::difference_type n) + { + detail::tuple_impl_specific::tuple_for_each( + m_iterator_tuple, + detail::advance_iterator<BOOST_DEDUCED_TYPENAME super_t::difference_type>(n) + ); + } + // Incrementing a zip iterator means to increment all iterators in + // the iterator tuple. + void increment() + { + detail::tuple_impl_specific::tuple_for_each( + m_iterator_tuple, + detail::increment_iterator() + ); + } + + // Decrementing a zip iterator means to decrement all iterators in + // the iterator tuple. + void decrement() + { + detail::tuple_impl_specific::tuple_for_each( + m_iterator_tuple, + detail::decrement_iterator() + ); + } + + // Distance is calculated using the first iterator in the tuple. + template<typename OtherIteratorTuple> + typename super_t::difference_type distance_to( + const zip_iterator<OtherIteratorTuple>& other + ) const + { + return boost::tuples::get<0>(other.get_iterator_tuple()) - + boost::tuples::get<0>(this->get_iterator_tuple()); + } + + // Data Members + // ============ + + // The iterator tuple. + IteratorTuple m_iterator_tuple; + + }; + + // Make function for zip iterator + // + template<typename IteratorTuple> + zip_iterator<IteratorTuple> + make_zip_iterator(IteratorTuple t) + { return zip_iterator<IteratorTuple>(t); } + +} + +#endif diff --git a/tools/import_boost.sh b/tools/import_boost.sh index 39bd9fc53c..b5ced8ac4d 100755 --- a/tools/import_boost.sh +++ b/tools/import_boost.sh @@ -24,6 +24,7 @@ boost/concept boost/detail boost/exception boost/function +boost/iterator boost/mpl boost/preprocessor boost/range |