boost/fusion/view/iterator_range/detail/segmented_iterator_range.hpp
/*=============================================================================
Copyright (c) 2011 Eric Niebler
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
==============================================================================*/
#if !defined(BOOST_FUSION_SEGMENTED_ITERATOR_RANGE_HPP_INCLUDED)
#define BOOST_FUSION_SEGMENTED_ITERATOR_RANGE_HPP_INCLUDED
#include <boost/mpl/assert.hpp>
#include <boost/type_traits/add_const.hpp>
#include <boost/type_traits/remove_reference.hpp>
#include <boost/fusion/support/tag_of.hpp>
#include <boost/fusion/sequence/intrinsic/begin.hpp>
#include <boost/fusion/sequence/intrinsic/end.hpp>
#include <boost/fusion/iterator/next.hpp>
#include <boost/fusion/iterator/deref.hpp>
#include <boost/fusion/sequence/intrinsic/segments.hpp>
#include <boost/fusion/algorithm/transformation/push_back.hpp>
#include <boost/fusion/algorithm/transformation/push_front.hpp>
#include <boost/fusion/iterator/equal_to.hpp>
#include <boost/fusion/container/list/detail/reverse_cons.hpp>
#include <boost/fusion/iterator/detail/segment_sequence.hpp>
// Invariants:
// - Each segmented iterator has a stack
// - Each value in the stack is an iterator range
// - The range at the top of the stack points to values
// - All other ranges point to ranges
// - The front of each range in the stack (besides the
// topmost) is the range above it
namespace boost { namespace fusion
{
template <typename First, typename Last>
struct iterator_range;
namespace result_of
{
template <typename Sequence, typename T>
struct push_back;
template <typename Sequence, typename T>
struct push_front;
}
template <typename Sequence, typename T>
typename result_of::push_back<Sequence const, T>::type
push_back(Sequence const& seq, T const& x);
template <typename Sequence, typename T>
typename result_of::push_front<Sequence const, T>::type
push_front(Sequence const& seq, T const& x);
}}
namespace boost { namespace fusion { namespace detail
{
//auto make_segment_sequence_front(stack_begin)
//{
// switch (size(stack_begin))
// {
// case 1:
// return nil;
// case 2:
// // car(cdr(stack_begin)) is a range over values.
// assert(end(front(car(stack_begin))) == end(car(cdr(stack_begin))));
// return iterator_range(begin(car(cdr(stack_begin))), end(front(car(stack_begin))));
// default:
// // car(cdr(stack_begin)) is a range over segments. We replace the
// // front with a view that is restricted.
// assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
// return segment_sequence(
// push_front(
// // The following could be a segment_sequence. It then gets wrapped
// // in a single_view, and push_front puts it in a join_view with the
// // following iterator_range.
// iterator_range(next(begin(car(cdr(stack_begin)))), end(segments(front(car(stack_begin))))),
// make_segment_sequence_front(cdr(stack_begin))));
// }
//}
template <typename Stack, std::size_t Size = Stack::size::value>
struct make_segment_sequence_front
{
// assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
BOOST_MPL_ASSERT((
result_of::equal_to<
typename result_of::end<
typename remove_reference<
typename add_const<
typename result_of::segments<
typename remove_reference<
typename add_const<
typename result_of::deref<
typename Stack::car_type::begin_type
>::type
>::type
>::type
>::type
>::type
>::type
>::type
, typename Stack::cdr_type::car_type::end_type
>));
typedef
iterator_range<
typename result_of::next<
typename Stack::cdr_type::car_type::begin_type
>::type
, typename result_of::end<
typename remove_reference<
typename add_const<
typename result_of::segments<
typename remove_reference<
typename add_const<
typename result_of::deref<
typename Stack::car_type::begin_type
>::type
>::type
>::type
>::type
>::type
>::type
>::type
>
rest_type;
typedef
make_segment_sequence_front<typename Stack::cdr_type>
recurse;
typedef
segment_sequence<
typename result_of::push_front<
rest_type const
, typename recurse::type
>::type
>
type;
static type call(Stack const& stack)
{
//return segment_sequence(
// push_front(
// iterator_range(next(begin(car(cdr(stack_begin)))), end(segments(front(car(stack_begin))))),
// make_segment_sequence_front(cdr(stack_begin))));
return type(
fusion::push_front(
rest_type(fusion::next(stack.cdr.car.first), fusion::end(fusion::segments(*stack.car.first)))
, recurse::call(stack.cdr)));
}
};
template <typename Stack>
struct make_segment_sequence_front<Stack, 2>
{
// assert(end(front(car(stack_begin))) == end(car(cdr(stack_begin))));
BOOST_MPL_ASSERT((
result_of::equal_to<
typename result_of::end<
typename remove_reference<
typename add_const<
typename result_of::deref<
typename Stack::car_type::begin_type
>::type
>::type
>::type
>::type
, typename Stack::cdr_type::car_type::end_type
>));
typedef
iterator_range<
typename Stack::cdr_type::car_type::begin_type
, typename result_of::end<
typename remove_reference<
typename add_const<
typename result_of::deref<
typename Stack::car_type::begin_type
>::type
>::type
>::type
>::type
>
type;
static type call(Stack const& stack)
{
// return iterator_range(begin(car(cdr(stack_begin))), end(front(car(stack_begin))));
return type(stack.cdr.car.first, fusion::end(*stack.car.first));
}
};
template <typename Stack>
struct make_segment_sequence_front<Stack, 1>
{
typedef typename Stack::cdr_type type; // nil
static type call(Stack const &stack)
{
return stack.cdr;
}
};
//auto make_segment_sequence_back(stack_end)
//{
// switch (size(stack_end))
// {
// case 1:
// return nil;
// case 2:
// // car(cdr(stack_back)) is a range over values.
// assert(end(front(car(stack_end))) == end(car(cdr(stack_end))));
// return iterator_range(begin(front(car(stack_end))), begin(car(cdr(stack_end))));
// default:
// // car(cdr(stack_begin)) is a range over segments. We replace the
// // back with a view that is restricted.
// assert(end(segments(front(car(stack_end)))) == end(car(cdr(stack_end))));
// return segment_sequence(
// push_back(
// iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))),
// make_segment_sequence_back(cdr(stack_end))));
// }
//}
template <typename Stack, std::size_t Size = Stack::size::value>
struct make_segment_sequence_back
{
// assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
BOOST_MPL_ASSERT((
result_of::equal_to<
typename result_of::end<
typename remove_reference<
typename add_const<
typename result_of::segments<
typename remove_reference<
typename add_const<
typename result_of::deref<
typename Stack::car_type::begin_type
>::type
>::type
>::type
>::type
>::type
>::type
>::type
, typename Stack::cdr_type::car_type::end_type
>));
typedef
iterator_range<
typename result_of::begin<
typename remove_reference<
typename add_const<
typename result_of::segments<
typename remove_reference<
typename add_const<
typename result_of::deref<
typename Stack::car_type::begin_type
>::type
>::type
>::type
>::type
>::type
>::type
>::type
, typename Stack::cdr_type::car_type::begin_type
>
rest_type;
typedef
make_segment_sequence_back<typename Stack::cdr_type>
recurse;
typedef
segment_sequence<
typename result_of::push_back<
rest_type const
, typename recurse::type
>::type
>
type;
static type call(Stack const& stack)
{
// return segment_sequence(
// push_back(
// iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))),
// make_segment_sequence_back(cdr(stack_end))));
return type(
fusion::push_back(
rest_type(fusion::begin(fusion::segments(*stack.car.first)), stack.cdr.car.first)
, recurse::call(stack.cdr)));
}
};
template <typename Stack>
struct make_segment_sequence_back<Stack, 2>
{
// assert(end(front(car(stack_end))) == end(car(cdr(stack_end))));
BOOST_MPL_ASSERT((
result_of::equal_to<
typename result_of::end<
typename remove_reference<
typename add_const<
typename result_of::deref<
typename Stack::car_type::begin_type
>::type
>::type
>::type
>::type
, typename Stack::cdr_type::car_type::end_type
>));
typedef
iterator_range<
typename result_of::begin<
typename remove_reference<
typename add_const<
typename result_of::deref<
typename Stack::car_type::begin_type
>::type
>::type
>::type
>::type
, typename Stack::cdr_type::car_type::begin_type
>
type;
static type call(Stack const& stack)
{
// return iterator_range(begin(front(car(stack_end))), begin(car(cdr(stack_end))));
return type(fusion::begin(*stack.car.first), stack.cdr.car.first);
}
};
template <typename Stack>
struct make_segment_sequence_back<Stack, 1>
{
typedef typename Stack::cdr_type type; // nil
static type call(Stack const& stack)
{
return stack.cdr;
}
};
//auto make_segmented_range_reduce(stack_begin, stack_end)
//{
// if (size(stack_begin) == 1 && size(stack_end) == 1)
// {
// return segment_sequence(
// single_view(
// iterator_range(begin(car(stack_begin)), begin(car(stack_end)))));
// }
// else
// {
// // We are in the case where both begin_stack and/or end_stack have
// // more than one element. Throw away any part of the tree where
// // begin and end refer to the same segment.
// if (begin(car(stack_begin)) == begin(car(stack_end)))
// {
// return make_segmented_range_reduce(cdr(stack_begin), cdr(stack_end));
// }
// else
// {
// // We are in the case where begin_stack and end_stack (a) have
// // more than one element each, and (b) they point to different
// // segments. We must construct a segmented sequence.
// return segment_sequence(
// push_back(
// push_front(
// iterator_range(
// fusion::next(begin(car(stack_begin))),
// begin(car(stack_end))), // a range of (possibly segmented) ranges.
// make_segment_sequence_front(stack_begin)), // should be a (possibly segmented) range.
// make_segment_sequence_back(stack_end))); // should be a (possibly segmented) range.
// }
// }
//}
template <
typename StackBegin
, typename StackEnd
, int StackBeginSize = StackBegin::size::value
, int StackEndSize = StackEnd::size::value>
struct make_segmented_range_reduce;
template <
typename StackBegin
, typename StackEnd
, bool SameSegment =
result_of::equal_to<
typename StackBegin::car_type::begin_type
, typename StackEnd::car_type::begin_type
>::type::value>
struct make_segmented_range_reduce2
{
typedef
iterator_range<
typename result_of::next<
typename StackBegin::car_type::begin_type
>::type
, typename StackEnd::car_type::begin_type
>
rest_type;
typedef
segment_sequence<
typename result_of::push_back<
typename result_of::push_front<
rest_type const
, typename make_segment_sequence_front<StackBegin>::type
>::type const
, typename make_segment_sequence_back<StackEnd>::type
>::type
>
type;
static type call(StackBegin stack_begin, StackEnd stack_end)
{
//return segment_sequence(
// push_back(
// push_front(
// iterator_range(
// fusion::next(begin(car(stack_begin))),
// begin(car(stack_end))), // a range of (possibly segmented) ranges.
// make_segment_sequence_front(stack_begin)), // should be a (possibly segmented) range.
// make_segment_sequence_back(stack_end))); // should be a (possibly segmented) range.
return type(
fusion::push_back(
fusion::push_front(
rest_type(fusion::next(stack_begin.car.first), stack_end.car.first)
, make_segment_sequence_front<StackBegin>::call(stack_begin))
, make_segment_sequence_back<StackEnd>::call(stack_end)));
}
};
template <typename StackBegin, typename StackEnd>
struct make_segmented_range_reduce2<StackBegin, StackEnd, true>
{
typedef
make_segmented_range_reduce<
typename StackBegin::cdr_type
, typename StackEnd::cdr_type
>
impl;
typedef
typename impl::type
type;
static type call(StackBegin stack_begin, StackEnd stack_end)
{
return impl::call(stack_begin.cdr, stack_end.cdr);
}
};
template <typename StackBegin, typename StackEnd, int StackBeginSize, int StackEndSize>
struct make_segmented_range_reduce
: make_segmented_range_reduce2<StackBegin, StackEnd>
{};
template <typename StackBegin, typename StackEnd>
struct make_segmented_range_reduce<StackBegin, StackEnd, 1, 1>
{
typedef
iterator_range<
typename StackBegin::car_type::begin_type
, typename StackEnd::car_type::begin_type
>
range_type;
typedef
single_view<range_type>
segment_type;
typedef
segment_sequence<segment_type>
type;
static type call(StackBegin stack_begin, StackEnd stack_end)
{
//return segment_sequence(
// single_view(
// iterator_range(begin(car(stack_begin)), begin(car(stack_end)))));
return type(segment_type(range_type(stack_begin.car.first, stack_end.car.first)));
}
};
//auto make_segmented_range(begin, end)
//{
// return make_segmented_range_reduce(reverse(begin.context), reverse(end.context));
//}
template <typename Begin, typename End>
struct make_segmented_range
{
typedef reverse_cons<typename Begin::context_type> reverse_begin_cons;
typedef reverse_cons<typename End::context_type> reverse_end_cons;
typedef
make_segmented_range_reduce<
typename reverse_begin_cons::type
, typename reverse_end_cons::type
>
impl;
typedef typename impl::type type;
static type call(Begin const& begin, End const& end)
{
return impl::call(
reverse_begin_cons::call(begin.context)
, reverse_end_cons::call(end.context));
}
};
}}}
#endif
