/*============================================================================= | |
Copyright (c) 2006 Eric Niebler | |
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 FUSION_SEGMENTED_ITERATOR_EAN_05032006_1027 | |
#define FUSION_SEGMENTED_ITERATOR_EAN_05032006_1027 | |
#include <boost/mpl/if.hpp> | |
#include <boost/mpl/int.hpp> | |
#include <boost/mpl/not.hpp> | |
#include <boost/mpl/assert.hpp> | |
#include <boost/mpl/next_prior.hpp> | |
#include <boost/mpl/placeholders.hpp> | |
#include <boost/type_traits/is_same.hpp> | |
#include <boost/type_traits/is_reference.hpp> | |
#include <boost/type_traits/remove_reference.hpp> | |
#include <boost/fusion/support/tag_of.hpp> | |
#include <boost/fusion/support/is_sequence.hpp> | |
#include <boost/fusion/view/filter_view.hpp> | |
#include <boost/fusion/container/list/cons.hpp> // for nil | |
#include <boost/fusion/container/generation/make_cons.hpp> | |
#include <boost/fusion/iterator/advance.hpp> | |
#include <boost/fusion/iterator/distance.hpp> | |
#include <boost/fusion/sequence/intrinsic/ext_/segments.hpp> | |
#include <boost/fusion/support/ext_/is_segmented.hpp> | |
namespace boost { namespace fusion | |
{ | |
struct fusion_sequence_tag; | |
namespace detail | |
{ | |
using mpl::_; | |
using mpl::not_; | |
//////////////////////////////////////////////////////////////////////////// | |
template<typename Sequence> | |
struct is_empty | |
: result_of::equal_to< | |
typename result_of::begin<Sequence>::type | |
, typename result_of::end<Sequence>::type | |
> | |
{}; | |
template<typename Sequence> | |
struct is_empty<Sequence &> | |
: is_empty<Sequence> | |
{}; | |
//////////////////////////////////////////////////////////////////////////// | |
struct not_is_empty_pred | |
{ | |
template<typename Sequence> | |
struct apply | |
: not_<is_empty<Sequence> > | |
{}; | |
}; | |
struct segmented_range_tag; | |
//////////////////////////////////////////////////////////////////////////// | |
template<typename Sequence, typename Index, bool IsSegmented> | |
struct segmented_range | |
: sequence_base<segmented_range<Sequence, Index, IsSegmented> > | |
{ | |
BOOST_MPL_ASSERT_NOT((is_reference<Sequence>)); | |
typedef mpl::bool_<IsSegmented> is_segmented; | |
typedef segmented_range_tag fusion_tag; | |
typedef fusion_sequence_tag tag; // this gets picked up by MPL | |
typedef mpl::true_ is_view; | |
// If this is a range of segments, skip over the empty ones | |
typedef typename mpl::if_< | |
is_segmented | |
, filter_view<Sequence, not_is_empty_pred> | |
, Sequence | |
>::type sequence_non_ref_type; | |
typedef typename mpl::if_< | |
traits::is_view<sequence_non_ref_type> | |
, sequence_non_ref_type | |
, sequence_non_ref_type & | |
>::type sequence_type; | |
typedef | |
typename fusion::result_of::advance< | |
typename fusion::result_of::begin<sequence_non_ref_type>::type | |
, Index | |
>::type | |
iterator_type; | |
typedef typename traits::category_of<sequence_non_ref_type>::type category; | |
explicit segmented_range(Sequence &sequence_) | |
: sequence(sequence_type(sequence_)) | |
{} | |
segmented_range(sequence_type sequence_, int) | |
: sequence(sequence_) | |
{} | |
iterator_type where_() const | |
{ | |
return fusion::advance<Index>( | |
fusion::begin(const_cast<sequence_non_ref_type &>(this->sequence)) | |
); | |
} | |
sequence_type sequence; | |
private: | |
segmented_range &operator =(segmented_range const &); | |
}; | |
} | |
namespace extension | |
{ | |
template<> | |
struct is_segmented_impl<detail::segmented_range_tag> | |
{ | |
template<typename Sequence> | |
struct apply | |
: Sequence::is_segmented | |
{}; | |
}; | |
template<> | |
struct size_impl<detail::segmented_range_tag> | |
{ | |
template<typename Sequence> | |
struct apply | |
: mpl::int_< | |
result_of::distance< | |
typename Sequence::iterator_type | |
, typename result_of::end<typename Sequence::sequence_non_ref_type>::type | |
>::value | |
> | |
{}; | |
}; | |
template<> | |
struct segments_impl<detail::segmented_range_tag> | |
{ | |
template<typename Sequence> | |
struct apply | |
{ | |
typedef Sequence &type; | |
static type call(Sequence &seq) | |
{ | |
return seq; | |
} | |
}; | |
}; | |
template<> | |
struct begin_impl<detail::segmented_range_tag> | |
{ | |
template<typename Sequence> | |
struct apply | |
{ | |
typedef typename Sequence::iterator_type type; | |
static type call(Sequence &seq) | |
{ | |
return seq.where_(); | |
} | |
}; | |
}; | |
template<> | |
struct end_impl<detail::segmented_range_tag> | |
{ | |
template<typename Sequence> | |
struct apply | |
{ | |
typedef typename Sequence::sequence_non_ref_type sequence; | |
typedef typename result_of::end<sequence>::type type; | |
static type call(Sequence &seq) | |
{ | |
return fusion::end(seq.sequence); | |
} | |
}; | |
}; | |
} | |
namespace detail | |
{ | |
/////////////////////////////////////////////////////////////////////// | |
template<typename Range> | |
struct range_next; | |
template<typename Sequence, typename Index, bool IsSegmented> | |
struct range_next<segmented_range<Sequence, Index, IsSegmented> > | |
{ | |
typedef typename mpl::next<Index>::type index_type; | |
typedef segmented_range<Sequence, index_type, IsSegmented> type; | |
static type call(segmented_range<Sequence, Index, IsSegmented> const &rng) | |
{ | |
return type(rng.sequence, 0); | |
} | |
}; | |
/////////////////////////////////////////////////////////////////////// | |
template<typename Cons> | |
struct is_range_next_empty | |
: is_empty<typename range_next<typename Cons::car_type>::type> | |
{}; | |
template<> | |
struct is_range_next_empty<nil> | |
: mpl::true_ | |
{}; | |
/////////////////////////////////////////////////////////////////////// | |
template<typename Sequence, bool IsSegmented = traits::is_segmented<Sequence>::value> | |
struct as_segmented_range | |
{ | |
typedef typename result_of::segments<Sequence>::type segments; | |
typedef typename remove_reference<segments>::type sequence; | |
typedef segmented_range<sequence, mpl::int_<0>, true> type; | |
static type call(Sequence &seq) | |
{ | |
segments segs(fusion::segments(seq)); | |
return type(segs); | |
} | |
}; | |
template<typename Sequence> | |
struct as_segmented_range<Sequence, false> | |
{ | |
typedef typename remove_reference<Sequence>::type sequence; | |
typedef segmented_range<sequence, mpl::int_<0>, false> type; | |
static type call(Sequence &seq) | |
{ | |
return type(seq); | |
} | |
}; | |
template<typename Sequence, typename Index, bool IsSegmented> | |
struct as_segmented_range<segmented_range<Sequence, Index, IsSegmented>, IsSegmented> | |
{ | |
typedef segmented_range<Sequence, Index, IsSegmented> type; | |
static type &call(type &seq) | |
{ | |
return seq; | |
} | |
}; | |
/////////////////////////////////////////////////////////////////////// | |
template< | |
typename Sequence | |
, typename State = nil | |
, bool IsSegmented = traits::is_segmented<Sequence>::value | |
> | |
struct push_segments | |
{ | |
typedef typename as_segmented_range<Sequence>::type range; | |
typedef typename result_of::begin<range>::type begin; | |
typedef typename result_of::deref<begin>::type next_ref; | |
typedef typename remove_reference<next_ref>::type next; | |
typedef push_segments<next, cons<range, State> > push; | |
typedef typename push::type type; | |
static type call(Sequence &seq, State const &state) | |
{ | |
range rng(as_segmented_range<Sequence>::call(seq)); | |
next_ref nxt(*fusion::begin(rng)); | |
return push::call(nxt, fusion::make_cons(rng, state)); | |
} | |
}; | |
template<typename Sequence, typename State> | |
struct push_segments<Sequence, State, false> | |
{ | |
typedef typename as_segmented_range<Sequence>::type range; | |
typedef cons<range, State> type; | |
static type call(Sequence &seq, State const &state) | |
{ | |
range rng(as_segmented_range<Sequence>::call(seq)); | |
return fusion::make_cons(rng, state); | |
} | |
}; | |
/////////////////////////////////////////////////////////////////////// | |
template<typename State, bool IsEmpty = is_range_next_empty<State>::value> | |
struct pop_segments | |
{ | |
typedef range_next<typename State::car_type> next; | |
typedef push_segments<typename next::type, typename State::cdr_type> push; | |
typedef typename push::type type; | |
static type call(State const &state) | |
{ | |
typename next::type rng(next::call(state.car)); | |
return push::call(rng, state.cdr); | |
} | |
}; | |
template<typename State> | |
struct pop_segments<State, true> | |
{ | |
typedef pop_segments<typename State::cdr_type> pop; | |
typedef typename pop::type type; | |
static type call(State const &state) | |
{ | |
return pop::call(state.cdr); | |
} | |
}; | |
template<> | |
struct pop_segments<nil, true> | |
{ | |
typedef nil type; | |
static type call(nil const &) | |
{ | |
return nil(); | |
} | |
}; | |
} // namespace detail | |
struct segmented_iterator_tag; | |
//////////////////////////////////////////////////////////////////////////// | |
template<typename Cons> | |
struct segmented_iterator | |
: fusion::iterator_base<segmented_iterator<Cons> > | |
{ | |
typedef segmented_iterator_tag fusion_tag; | |
typedef fusion::forward_traversal_tag category; | |
typedef Cons cons_type; | |
typedef typename Cons::car_type car_type; | |
typedef typename Cons::cdr_type cdr_type; | |
explicit segmented_iterator(Cons const &c) | |
: cons_(c) | |
{} | |
cons_type const &cons() const { return this->cons_; }; | |
car_type const &car() const { return this->cons_.car; }; | |
cdr_type const &cdr() const { return this->cons_.cdr; }; | |
private: | |
Cons cons_; | |
}; | |
/////////////////////////////////////////////////////////////////////////// | |
template<typename Sequence> | |
struct segmented_begin | |
{ | |
typedef typename detail::push_segments<Sequence> push; | |
typedef segmented_iterator<typename push::type> type; | |
static type call(Sequence &seq) | |
{ | |
return type(push::call(seq, nil())); | |
} | |
}; | |
/////////////////////////////////////////////////////////////////////////// | |
template<typename Sequence> | |
struct segmented_end | |
{ | |
typedef segmented_iterator<nil> type; | |
static type call(Sequence &) | |
{ | |
return type(nil()); | |
} | |
}; | |
namespace extension | |
{ | |
template<> | |
struct value_of_impl<segmented_iterator_tag> | |
{ | |
template<typename Iterator> | |
struct apply | |
{ | |
typedef typename result_of::begin<typename Iterator::car_type>::type begin; | |
typedef typename result_of::value_of<begin>::type type; | |
}; | |
}; | |
template<> | |
struct deref_impl<segmented_iterator_tag> | |
{ | |
template<typename Iterator> | |
struct apply | |
{ | |
typedef typename result_of::begin<typename Iterator::car_type>::type begin; | |
typedef typename result_of::deref<begin>::type type; | |
static type call(Iterator const &it) | |
{ | |
return *fusion::begin(it.car()); | |
} | |
}; | |
}; | |
// discards the old head, expands the right child of the new head | |
// and pushes the result to the head of the list. | |
template<> | |
struct next_impl<segmented_iterator_tag> | |
{ | |
template< | |
typename Iterator | |
, bool IsSegmentDone = detail::is_range_next_empty<Iterator>::value | |
> | |
struct apply | |
{ | |
typedef typename Iterator::cdr_type cdr_type; | |
typedef detail::range_next<typename Iterator::car_type> next; | |
typedef segmented_iterator<cons<typename next::type, cdr_type> > type; | |
static type call(Iterator const &it) | |
{ | |
return type(fusion::make_cons(next::call(it.car()), it.cdr())); | |
} | |
}; | |
template<typename Iterator> | |
struct apply<Iterator, true> // segment done, move to next segment | |
{ | |
typedef typename Iterator::cdr_type cdr_type; | |
typedef typename detail::pop_segments<cdr_type> pop; | |
typedef segmented_iterator<typename pop::type> type; | |
static type call(Iterator const &it) | |
{ | |
return type(pop::call(it.cdr())); | |
} | |
}; | |
}; | |
} | |
}} // namespace boost::fusion | |
#endif |