1 /* Copyright 2016-2017 Joaquin M Lopez Munoz.
2 * Distributed under the Boost Software License, Version 1.0.
3 * (See accompanying file LICENSE_1_0.txt or copy at
4 * http://www.boost.org/LICENSE_1_0.txt)
5 *
6 * See http://www.boost.org/libs/poly_collection for library home page.
7 */
8
9 #ifndef BOOST_POLY_COLLECTION_DETAIL_SEGMENT_SPLIT_HPP
10 #define BOOST_POLY_COLLECTION_DETAIL_SEGMENT_SPLIT_HPP
11
12 #if defined(_MSC_VER)
13 #pragma once
14 #endif
15
16 #include <boost/iterator/iterator_facade.hpp>
17 #include <boost/poly_collection/detail/iterator_traits.hpp>
18 #include <typeinfo>
19 #include <utility>
20
21 namespace boost{
22
23 namespace poly_collection{
24
25 namespace detail{
26
27 /* breakdown of an iterator range into local_base_iterator segments */
28
29 template<typename PolyCollectionIterator>
30 class segment_splitter
31 {
32 using traits=iterator_traits<PolyCollectionIterator>;
33 using local_base_iterator=typename traits::local_base_iterator;
34 using base_segment_info_iterator=typename traits::base_segment_info_iterator;
35
36 public:
37 struct info
38 {
type_infoboost::poly_collection::detail::segment_splitter::info39 const std::type_info& type_info()const noexcept{return *pinfo_;}
beginboost::poly_collection::detail::segment_splitter::info40 local_base_iterator begin()const noexcept{return begin_;}
endboost::poly_collection::detail::segment_splitter::info41 local_base_iterator end()const noexcept{return end_;}
42
43 const std::type_info* pinfo_;
44 local_base_iterator begin_,end_;
45 };
46
47 struct iterator:iterator_facade<iterator,info,std::input_iterator_tag,info>
48 {
49 iterator()=default;
50
51 private:
52 friend class segment_splitter;
53 friend class boost::iterator_core_access;
54
iteratorboost::poly_collection::detail::segment_splitter::iterator55 iterator(
56 base_segment_info_iterator it,
57 const PolyCollectionIterator& first,const PolyCollectionIterator& last):
58 it{it},pfirst{&first},plast{&last}{}
iteratorboost::poly_collection::detail::segment_splitter::iterator59 iterator(
60 const PolyCollectionIterator& first,const PolyCollectionIterator& last):
61 it{traits::base_segment_info_iterator_from(first)},
62 pfirst{&first},plast{&last}
63 {}
64
dereferenceboost::poly_collection::detail::segment_splitter::iterator65 info dereference()const noexcept
66 {
67 return {
68 &it->type_info(),
69 it==traits::base_segment_info_iterator_from(*pfirst)?
70 traits::local_base_iterator_from(*pfirst):it->begin(),
71 it==traits::base_segment_info_iterator_from(*plast)?
72 traits::local_base_iterator_from(*plast):it->end()
73 };
74 }
75
equalboost::poly_collection::detail::segment_splitter::iterator76 bool equal(const iterator& x)const noexcept{return it==x.it;}
incrementboost::poly_collection::detail::segment_splitter::iterator77 void increment()noexcept{++it;}
78
79 base_segment_info_iterator it;
80 const PolyCollectionIterator* pfirst;
81 const PolyCollectionIterator* plast;
82 };
83
segment_splitter(const PolyCollectionIterator & first,const PolyCollectionIterator & last)84 segment_splitter(
85 const PolyCollectionIterator& first,const PolyCollectionIterator& last):
86 pfirst{&first},plast{&last}{}
87
begin() const88 iterator begin()const noexcept{return {*pfirst,*plast};}
89
end() const90 iterator end()const noexcept
91 {
92 auto slast=traits::base_segment_info_iterator_from(*plast);
93 if(slast!=traits::end_base_segment_info_iterator_from(*plast))++slast;
94 return {slast,*plast,*plast};
95 }
96
97 private:
98 const PolyCollectionIterator* pfirst;
99 const PolyCollectionIterator* plast;
100 };
101
102 template<typename PolyCollectionIterator>
103 segment_splitter<PolyCollectionIterator>
segment_split(const PolyCollectionIterator & first,const PolyCollectionIterator & last)104 segment_split(
105 const PolyCollectionIterator& first,const PolyCollectionIterator& last)
106 {
107 return {first,last};
108 }
109
110 #if 1
111 /* equivalent to for(auto i:segment_split(first,last))f(i) */
112
113 template<typename PolyCollectionIterator,typename F>
for_each_segment(const PolyCollectionIterator & first,const PolyCollectionIterator & last,F && f)114 void for_each_segment(
115 const PolyCollectionIterator& first,const PolyCollectionIterator& last,F&& f)
116 {
117 using traits=iterator_traits<PolyCollectionIterator>;
118 using info=typename segment_splitter<PolyCollectionIterator>::info;
119
120 auto sfirst=traits::base_segment_info_iterator_from(first),
121 slast=traits::base_segment_info_iterator_from(last),
122 send=traits::end_base_segment_info_iterator_from(last);
123 auto lbfirst=traits::local_base_iterator_from(first),
124 lblast=traits::local_base_iterator_from(last);
125
126 if(sfirst!=slast){
127 for(;;){
128 f(info{&sfirst->type_info(),lbfirst,sfirst->end()});
129 ++sfirst;
130 if(sfirst==slast)break;
131 lbfirst=sfirst->begin();
132 }
133 if(sfirst!=send)f(info{&sfirst->type_info(),sfirst->begin(),lblast});
134 }
135 else if(sfirst!=send){
136 f(info{&sfirst->type_info(),lbfirst,lblast});
137 }
138 }
139 #else
140 template<typename PolyCollectionIterator,typename F>
for_each_segment(const PolyCollectionIterator & first,const PolyCollectionIterator & last,F && f)141 void for_each_segment(
142 const PolyCollectionIterator& first,const PolyCollectionIterator& last,F&& f)
143 {
144 for(auto i:segment_split(first,last))f(i);
145 }
146 #endif
147
148 } /* namespace poly_collection::detail */
149
150 } /* namespace poly_collection */
151
152 } /* namespace boost */
153
154 #endif
155