| /*============================================================================= |
| 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_RANGE_EAN_05032006_1027 |
| #define FUSION_SEGMENTED_ITERATOR_RANGE_EAN_05032006_1027 |
| |
| #include <boost/mpl/bool.hpp> |
| #include <boost/mpl/minus.hpp> |
| #include <boost/mpl/next_prior.hpp> |
| #include <boost/mpl/and.hpp> |
| #include <boost/type_traits/remove_cv.hpp> |
| #include <boost/type_traits/remove_reference.hpp> |
| #include <boost/fusion/iterator/mpl/convert_iterator.hpp> |
| #include <boost/fusion/container/list/cons.hpp> |
| #include <boost/fusion/view/joint_view.hpp> |
| #include <boost/fusion/view/single_view.hpp> |
| #include <boost/fusion/view/transform_view.hpp> |
| #include <boost/fusion/view/iterator_range.hpp> |
| #include <boost/fusion/view/ext_/multiple_view.hpp> |
| #include <boost/fusion/view/ext_/segmented_iterator.hpp> |
| #include <boost/fusion/adapted/mpl/mpl_iterator.hpp> |
| |
| namespace boost { namespace fusion |
| { |
| namespace detail |
| { |
| //////////////////////////////////////////////////////////////////////////// |
| template<typename Cons, typename State = nil> |
| struct reverse_cons; |
| |
| template<typename Car, typename Cdr, typename State> |
| struct reverse_cons<cons<Car, Cdr>, State> |
| { |
| typedef reverse_cons<Cdr, cons<Car, State> > reverse; |
| typedef typename reverse::type type; |
| |
| static type call(cons<Car, Cdr> const &cons, State const &state = State()) |
| { |
| return reverse::call(cons.cdr, fusion::make_cons(cons.car, state)); |
| } |
| }; |
| |
| template<typename State> |
| struct reverse_cons<nil, State> |
| { |
| typedef State type; |
| |
| static State const &call(nil const &, State const &state = State()) |
| { |
| return state; |
| } |
| }; |
| |
| //////////////////////////////////////////////////////////////////////////// |
| // tags |
| struct full_view {}; |
| struct left_view {}; |
| struct right_view {}; |
| struct center_view {}; |
| |
| template<typename Tag> |
| struct segmented_view_tag; |
| |
| //////////////////////////////////////////////////////////////////////////// |
| // a segmented view of that includes all elements either to the |
| // right or the left of a segmented iterator. |
| template<typename Tag, typename Cons1, typename Cons2 = void_> |
| struct segmented_view |
| : sequence_base<segmented_view<Tag, Cons1, Cons2> > |
| { |
| typedef segmented_view_tag<Tag> fusion_tag; |
| typedef fusion_sequence_tag tag; // this gets picked up by MPL |
| typedef mpl::true_ is_view; |
| typedef forward_traversal_tag category; |
| |
| explicit segmented_view(Cons1 const &cons) |
| : cons(cons) |
| {} |
| |
| typedef Cons1 cons_type; |
| cons_type const &cons; |
| }; |
| |
| // a segmented view that contains all the elements in between |
| // two segmented iterators |
| template<typename Cons1, typename Cons2> |
| struct segmented_view<center_view, Cons1, Cons2> |
| : sequence_base<segmented_view<center_view, Cons1, Cons2> > |
| { |
| typedef segmented_view_tag<center_view> fusion_tag; |
| typedef fusion_sequence_tag tag; // this gets picked up by MPL |
| typedef mpl::true_ is_view; |
| typedef forward_traversal_tag category; |
| |
| segmented_view(Cons1 const &lcons, Cons2 const &rcons) |
| : left_cons(lcons) |
| , right_cons(rcons) |
| {} |
| |
| typedef Cons1 left_cons_type; |
| typedef Cons2 right_cons_type; |
| |
| left_cons_type const &left_cons; |
| right_cons_type const &right_cons; |
| }; |
| |
| //////////////////////////////////////////////////////////////////////////// |
| // Used to transform a sequence of segments. The first segment is |
| // bounded by RightCons, and the last segment is bounded by LeftCons |
| // and all the others are passed through unchanged. |
| template<typename RightCons, typename LeftCons = RightCons> |
| struct segments_transform |
| { |
| explicit segments_transform(RightCons const &cons_) |
| : right_cons(cons_) |
| , left_cons(cons_) |
| {} |
| |
| segments_transform(RightCons const &right_cons_, LeftCons const &left_cons_) |
| : right_cons(right_cons_) |
| , left_cons(left_cons_) |
| {} |
| |
| template<typename First, typename Second> |
| struct result_; |
| |
| template<typename Second> |
| struct result_<right_view, Second> |
| { |
| typedef segmented_view<right_view, RightCons> type; |
| }; |
| |
| template<typename Second> |
| struct result_<left_view, Second> |
| { |
| typedef segmented_view<left_view, LeftCons> type; |
| }; |
| |
| template<typename Second> |
| struct result_<full_view, Second> |
| { |
| typedef Second type; |
| }; |
| |
| template<typename Sig> |
| struct result; |
| |
| template<typename This, typename First, typename Second> |
| struct result<This(First, Second)> |
| : result_< |
| typename remove_cv<typename remove_reference<First>::type>::type |
| , typename remove_cv<typename remove_reference<Second>::type>::type |
| > |
| {}; |
| |
| template<typename Second> |
| segmented_view<right_view, RightCons> operator ()(right_view, Second &second) const |
| { |
| return segmented_view<right_view, RightCons>(this->right_cons); |
| } |
| |
| template<typename Second> |
| segmented_view<left_view, LeftCons> operator ()(left_view, Second &second) const |
| { |
| return segmented_view<left_view, LeftCons>(this->left_cons); |
| } |
| |
| template<typename Second> |
| Second &operator ()(full_view, Second &second) const |
| { |
| return second; |
| } |
| |
| private: |
| RightCons const &right_cons; |
| LeftCons const &left_cons; |
| }; |
| |
| } // namespace detail |
| |
| namespace extension |
| { |
| //////////////////////////////////////////////////////////////////////////// |
| template<typename Tag> |
| struct is_segmented_impl<detail::segmented_view_tag<Tag> > |
| { |
| template<typename Sequence> |
| struct apply |
| : mpl::true_ |
| {}; |
| }; |
| |
| //////////////////////////////////////////////////////////////////////////// |
| template<> |
| struct segments_impl<detail::segmented_view_tag<detail::right_view> > |
| { |
| template< |
| typename Sequence |
| , typename Cdr = typename Sequence::cons_type::cdr_type |
| > |
| struct apply |
| { |
| typedef typename Sequence::cons_type::car_type segmented_range; |
| typedef typename result_of::size<segmented_range>::type size; |
| typedef typename mpl::prior<size>::type size_minus_1; |
| typedef detail::segments_transform<Cdr> tfx; |
| typedef joint_view< |
| single_view<detail::right_view> const |
| , multiple_view<size_minus_1, detail::full_view> const |
| > mask; |
| typedef transform_view<mask const, segmented_range const, tfx> type; |
| |
| static type call(Sequence &seq) |
| { |
| return type( |
| mask( |
| make_single_view(detail::right_view()) |
| , make_multiple_view<size_minus_1>(detail::full_view()) |
| ) |
| , seq.cons.car |
| , tfx(seq.cons.cdr) |
| ); |
| } |
| }; |
| |
| template<typename Sequence> |
| struct apply<Sequence, nil> |
| { |
| typedef typename Sequence::cons_type::car_type segmented_range; |
| typedef typename segmented_range::iterator_type begin; |
| typedef typename segmented_range::sequence_non_ref_type sequence_type; |
| typedef typename result_of::end<sequence_type>::type end; |
| typedef iterator_range<begin, end> range; |
| typedef single_view<range> type; |
| |
| static type call(Sequence &seq) |
| { |
| return type(range(seq.cons.car.where_, fusion::end(seq.cons.car.sequence))); |
| } |
| }; |
| }; |
| |
| //////////////////////////////////////////////////////////////////////////// |
| template<> |
| struct segments_impl<detail::segmented_view_tag<detail::left_view> > |
| { |
| template< |
| typename Sequence |
| , typename Cdr = typename Sequence::cons_type::cdr_type |
| > |
| struct apply |
| { |
| typedef typename Sequence::cons_type::car_type right_segmented_range; |
| typedef typename right_segmented_range::sequence_type sequence_type; |
| typedef typename right_segmented_range::iterator_type iterator_type; |
| |
| typedef iterator_range< |
| typename result_of::begin<sequence_type>::type |
| , typename result_of::next<iterator_type>::type |
| > segmented_range; |
| |
| typedef detail::segments_transform<Cdr> tfx; |
| typedef typename result_of::size<segmented_range>::type size; |
| typedef typename mpl::prior<size>::type size_minus_1; |
| typedef joint_view< |
| multiple_view<size_minus_1, detail::full_view> const |
| , single_view<detail::left_view> const |
| > mask; |
| typedef transform_view<mask const, segmented_range const, tfx> type; |
| |
| static type call(Sequence &seq) |
| { |
| return type( |
| mask( |
| make_multiple_view<size_minus_1>(detail::full_view()) |
| , make_single_view(detail::left_view()) |
| ) |
| , segmented_range(fusion::begin(seq.cons.car.sequence), fusion::next(seq.cons.car.where_)) |
| , tfx(seq.cons.cdr) |
| ); |
| } |
| }; |
| |
| template<typename Sequence> |
| struct apply<Sequence, nil> |
| { |
| typedef typename Sequence::cons_type::car_type segmented_range; |
| typedef typename segmented_range::sequence_non_ref_type sequence_type; |
| typedef typename result_of::begin<sequence_type>::type begin; |
| typedef typename segmented_range::iterator_type end; |
| typedef iterator_range<begin, end> range; |
| typedef single_view<range> type; |
| |
| static type call(Sequence &seq) |
| { |
| return type(range(fusion::begin(seq.cons.car.sequence), seq.cons.car.where_)); |
| } |
| }; |
| }; |
| |
| //////////////////////////////////////////////////////////////////////////// |
| template<> |
| struct segments_impl<detail::segmented_view_tag<detail::center_view> > |
| { |
| template<typename Sequence> |
| struct apply |
| { |
| typedef typename Sequence::right_cons_type right_cons_type; |
| typedef typename Sequence::left_cons_type left_cons_type; |
| typedef typename right_cons_type::car_type right_segmented_range; |
| typedef typename left_cons_type::car_type left_segmented_range; |
| |
| typedef iterator_range< |
| typename result_of::begin<left_segmented_range>::type |
| , typename result_of::next<typename result_of::begin<right_segmented_range>::type>::type |
| > segmented_range; |
| |
| typedef typename mpl::minus< |
| typename result_of::size<segmented_range>::type |
| , mpl::int_<2> |
| >::type size_minus_2; |
| |
| BOOST_MPL_ASSERT_RELATION(0, <=, size_minus_2::value); |
| |
| typedef detail::segments_transform< |
| typename left_cons_type::cdr_type |
| , typename right_cons_type::cdr_type |
| > tfx; |
| |
| typedef joint_view< |
| multiple_view<size_minus_2, detail::full_view> const |
| , single_view<detail::left_view> const |
| > left_mask; |
| |
| typedef joint_view< |
| single_view<detail::right_view> const |
| , left_mask const |
| > mask; |
| |
| typedef transform_view<mask const, segmented_range const, tfx> type; |
| |
| static type call(Sequence &seq) |
| { |
| left_mask lmask( |
| make_multiple_view<size_minus_2>(detail::full_view()) |
| , make_single_view(detail::left_view()) |
| ); |
| return type( |
| mask(make_single_view(detail::right_view()), lmask) |
| , segmented_range(fusion::begin(seq.left_cons.car), fusion::next(fusion::begin(seq.right_cons.car))) |
| , tfx(seq.left_cons.cdr, seq.right_cons.cdr) |
| ); |
| } |
| }; |
| }; |
| } |
| |
| // specialize iterator_range for use with segmented iterators, so that |
| // it presents a segmented view of the range. |
| template<typename First, typename Last> |
| struct iterator_range; |
| |
| template<typename First, typename Last> |
| struct iterator_range<segmented_iterator<First>, segmented_iterator<Last> > |
| : sequence_base<iterator_range<segmented_iterator<First>, segmented_iterator<Last> > > |
| { |
| typedef typename convert_iterator<segmented_iterator<First> >::type begin_type; |
| typedef typename convert_iterator<segmented_iterator<Last> >::type end_type; |
| typedef typename detail::reverse_cons<First>::type begin_cons_type; |
| typedef typename detail::reverse_cons<Last>::type end_cons_type; |
| typedef iterator_range_tag fusion_tag; |
| typedef fusion_sequence_tag tag; // this gets picked up by MPL |
| typedef typename traits::category_of<begin_type>::type category; |
| typedef typename result_of::distance<begin_type, end_type>::type size; |
| typedef mpl::true_ is_view; |
| |
| iterator_range(segmented_iterator<First> const& first_, segmented_iterator<Last> const& last_) |
| : first(convert_iterator<segmented_iterator<First> >::call(first_)) |
| , last(convert_iterator<segmented_iterator<Last> >::call(last_)) |
| , first_cons(detail::reverse_cons<First>::call(first_.cons())) |
| , last_cons(detail::reverse_cons<Last>::call(last_.cons())) |
| {} |
| |
| begin_type first; |
| end_type last; |
| |
| begin_cons_type first_cons; |
| end_cons_type last_cons; |
| }; |
| |
| namespace detail |
| { |
| |
| template<typename Cons1, typename Cons2> |
| struct same_segment |
| : mpl::false_ |
| {}; |
| |
| template<typename Car1, typename Cdr1, typename Car2, typename Cdr2> |
| struct same_segment<cons<Car1, Cdr1>, cons<Car2, Cdr2> > |
| : mpl::and_< |
| traits::is_segmented<Car1> |
| , is_same<Car1, Car2> |
| > |
| {}; |
| |
| //////////////////////////////////////////////////////////////////////////// |
| template<typename Cons1, typename Cons2> |
| struct segments_gen; |
| |
| //////////////////////////////////////////////////////////////////////////// |
| template<typename Cons1, typename Cons2, bool SameSegment> |
| struct segments_gen2 |
| { |
| typedef segments_gen<typename Cons1::cdr_type, typename Cons2::cdr_type> gen; |
| typedef typename gen::type type; |
| |
| static type call(Cons1 const &cons1, Cons2 const &cons2) |
| { |
| return gen::call(cons1.cdr, cons2.cdr); |
| } |
| }; |
| |
| template<typename Cons1, typename Cons2> |
| struct segments_gen2<Cons1, Cons2, false> |
| { |
| typedef segmented_view<center_view, Cons1, Cons2> view; |
| typedef typename result_of::segments<view>::type type; |
| |
| static type call(Cons1 const &cons1, Cons2 const &cons2) |
| { |
| view v(cons1, cons2); |
| return fusion::segments(v); |
| } |
| }; |
| |
| template<typename Car1, typename Car2> |
| struct segments_gen2<cons<Car1>, cons<Car2>, false> |
| { |
| typedef iterator_range< |
| typename Car1::iterator_type |
| , typename Car2::iterator_type |
| > range; |
| |
| typedef single_view<range> type; |
| |
| static type call(cons<Car1> const &cons1, cons<Car2> const &cons2) |
| { |
| return type(range(cons1.car.where_, cons2.car.where_)); |
| } |
| }; |
| |
| //////////////////////////////////////////////////////////////////////////// |
| template<typename Cons1, typename Cons2> |
| struct segments_gen |
| : segments_gen2<Cons1, Cons2, same_segment<Cons1, Cons2>::value> |
| {}; |
| |
| template<typename Car, typename Cdr> |
| struct segments_gen<cons<Car, Cdr>, nil> |
| { |
| typedef segmented_view<right_view, cons<Car, Cdr> > view; |
| typedef typename result_of::segments<view>::type type; |
| |
| static type call(cons<Car, Cdr> const &cons, nil const &) |
| { |
| view v(cons); |
| return fusion::segments(v); |
| } |
| }; |
| |
| template<> |
| struct segments_gen<nil, nil> |
| { |
| typedef nil type; |
| |
| static type call(nil const &, nil const &) |
| { |
| return nil(); |
| } |
| }; |
| } // namespace detail |
| |
| namespace extension |
| { |
| template<typename Tag> |
| struct is_segmented_impl; |
| |
| // An iterator_range of segmented_iterators is segmented |
| template<> |
| struct is_segmented_impl<iterator_range_tag> |
| { |
| template<typename Iterator> |
| struct is_segmented_iterator : mpl::false_ {}; |
| |
| template<typename Cons> |
| struct is_segmented_iterator<segmented_iterator<Cons> > : mpl::true_ {}; |
| |
| template<typename Sequence> |
| struct apply |
| : mpl::and_< |
| is_segmented_iterator<typename Sequence::begin_type> |
| , is_segmented_iterator<typename Sequence::end_type> |
| > |
| {}; |
| }; |
| |
| template<typename Sequence> |
| struct segments_impl; |
| |
| template<> |
| struct segments_impl<iterator_range_tag> |
| { |
| template<typename Sequence> |
| struct apply |
| { |
| typedef typename Sequence::begin_cons_type begin_cons; |
| typedef typename Sequence::end_cons_type end_cons; |
| |
| typedef detail::segments_gen<begin_cons, end_cons> gen; |
| typedef typename gen::type type; |
| |
| static type call(Sequence &sequence) |
| { |
| return gen::call(sequence.first_cons, sequence.last_cons); |
| } |
| }; |
| }; |
| } |
| |
| }} |
| |
| #endif |