31 #ifndef _util_misc_iterators_h
32 #define _util_misc_iterators_h
35 #include <type_traits>
38 #include <boost/iterator/iterator_facade.hpp>
39 #include <boost/iterator/iterator_adaptor.hpp>
40 #include <boost/tuple/tuple.hpp>
41 #include <boost/tuple/tuple_comparison.hpp>
42 #include <boost/type_traits.hpp>
43 #include <boost/mpl/and.hpp>
44 #include <boost/utility/enable_if.hpp>
45 #include <boost/range.hpp>
46 #include <boost/iterator/zip_iterator.hpp>
53 struct iterable_iterator {
54 typedef decltype(
typename std::remove_reference<T>::type().begin()) type;
58 struct iterator_dereference {
59 typedef typename std::remove_reference<T>::type::reference type;
63 struct iterable_iterator_dereference {
64 typedef typename iterator_dereference<
65 typename iterable_iterator<T>::type
70 struct iterator_dereference<boost::tuples::null_type> {
71 typedef boost::tuples::null_type type;
74 template <
typename H,
typename T>
75 struct iterator_dereference<boost::tuples::cons<H,T>> {
76 typedef boost::tuples::cons<
77 typename iterator_dereference<H>::type,
78 typename iterator_dereference<T>::type
82 template <
typename H,
typename T>
83 typename boost::enable_if<
84 boost::is_same<T, boost::tuples::null_type>,
86 typename iterator_dereference<H>::type,
87 typename iterator_dereference<T>::type
89 >::type dereferencer(
const boost::tuples::cons<H, T>& cons_iters);
91 template <
typename H,
typename T>
92 typename boost::disable_if<
93 boost::is_same<T, boost::tuples::null_type>,
95 typename iterator_dereference<H>::type,
96 typename iterator_dereference<T>::type
99 dereferencer(
const boost::tuples::cons<H, T>& cons_iters) {
100 return boost::tuples::cons<
101 typename iterator_dereference<H>::type,
102 typename iterator_dereference<T>::type
105 dereferencer(cons_iters.tail)
109 template <
typename H,
typename T>
110 typename boost::enable_if<
111 boost::is_same<T, boost::tuples::null_type>,
113 typename iterator_dereference<H>::type,
114 typename iterator_dereference<T>::type
117 dereferencer(
const boost::tuples::cons<H, T>& cons_iters) {
118 return boost::tuples::cons<
119 typename iterator_dereference<H>::type,
120 typename iterator_dereference<T>::type
121 >(*cons_iters.head, cons_iters.get_tail());
124 template <
typename Iterable>
125 typename iterable_iterator<Iterable>::type
126 get_begin(Iterable& container)
128 return container.begin();
132 namespace mpl = boost::mpl;
134 template<
typename... Iterables>
136 :
public boost::iterator_facade<
137 product_iterator<Iterables...>,
138 typename boost::tuple<typename iterable_iterator<Iterables>::type...>,
139 boost::forward_traversal_tag,
140 typename boost::tuple<typename iterable_iterator_dereference<Iterables>::type...>
145 typedef boost::tuple<typename iterable_iterator_dereference<Iterables>::type...> reference;
146 typedef boost::tuple<typename iterable_iterator<Iterables>::type...> iterators_type;
147 typedef boost::tuple<Iterables...> iterables_type;
152 iterators_type spots_;
153 iterables_type iterables_;
156 friend class boost::iterator_core_access;
158 reference dereference()
const {
159 return static_cast<reference>(
165 template<
typename... OtherIterTypes>
168 return spots_ ==
other.spots_;
172 template<
typename H,
typename T,
typename H2,
typename T2>
173 typename boost::disable_if_c<
174 boost::is_same<T, boost::tuples::null_type>::value,
178 boost::tuples::cons<H, T>& cons_iters,
179 boost::tuples::cons<H2, T2>& cons_containers
182 if(increment_impl(cons_iters.tail, cons_containers.tail)) {
184 if(cons_iters.head == cons_containers.head.end()) {
185 cons_iters.head = cons_containers.head.begin();
192 template<
typename H,
typename T,
typename H2,
typename T2>
193 typename boost::enable_if_c<
194 boost::is_same<T, boost::tuples::null_type>::value,
198 boost::tuples::cons<H, T>& cons_iters,
199 boost::tuples::cons<H2, T2>& cons_containers
203 if(cons_iters.head == cons_containers.head.end()) {
204 cons_iters.head = cons_containers.head.begin();
212 iterators_type& cons_iters,
213 iterables_type& cons_containers
216 if(increment_impl(cons_iters.tail, cons_containers.tail)) {
223 increment_impl(spots_, iterables_);
229 : iterables_(iters...),
230 spots_(get_begin(iters)...)
233 static self_type end_iterator(Iterables&&... iters)
235 auto rv =
self_type(std::forward<Iterables>(iters)...);
236 boost::tuples::get<0>(rv.spots_) = boost::tuples::get<0>(rv.iterables_).end();
242 template<
typename... Iterables>
244 product_range(Iterables&&... iterables)
246 return boost::make_iterator_range(
248 std::forward<Iterables>(iterables)...
251 std::forward<Iterables>(iterables)...
386 template<
bool can_advance,
typename Iterator,
typename difference_type>
387 struct advance_iterator {
390 const difference_type& n_adv,
391 const Iterator& end_iter
396 (
typename std::iterator_traits<Iterator>::difference_type) n_adv
401 template<
typename Iterator,
typename difference_type>
402 struct advance_iterator<false, Iterator, difference_type> {
405 const difference_type& n_adv,
406 const Iterator& end_iter
410 for(
int i = 0; i < n_adv; ++i, ++it) {
420 template<
typename Iterator,
bool base_can_be_advanced=false>
422 :
public boost::iterator_adaptor<
423 threaded_iterator<Iterator>,
426 boost::forward_traversal_tag
431 typedef typename threaded_iterator::iterator_adaptor_ super_t;
435 friend class boost::iterator_core_access;
443 base_can_be_advanced,
447 super_t::base_reference(), nthr_, end_iter_
454 : super_t(iter), end_iter_(end_iter), ithr_(ithr), nthr_(nthr)
457 base_can_be_advanced,
461 super_t::base_reference(), ithr_, end_iter_
469 template<
typename Iterator>
474 bool base_can_be_advanced=
false
476 boost::iterator_range<threaded_iterator<typename iterable_iterator<Range>::type>>
477 thread_over_range(Range&&
range,
int ithr,
int nthr)
479 return boost::make_iterator_range(
481 decltype(
range.begin()), base_can_be_advanced
484 decltype(
range.begin()), base_can_be_advanced
491 bool base_can_be_advanced=
false
493 boost::iterator_range<threaded_iterator<typename iterable_iterator<Range>::type>>
494 thread_node_parallel_range(Range&& range,
int n_node,
int me,
int nthread,
int ithr)
496 const int thr_offset = me*nthread + ithr;
497 const int increment = n_node*nthread;
498 return boost::make_iterator_range(
500 decltype(range.begin()), base_can_be_advanced
501 >(range.begin(), range.end(), thr_offset, increment),
503 decltype(range.begin()), base_can_be_advanced
504 >(range.end(), range.end(), thr_offset, increment)
513 template <
typename... T>
514 auto zip(
const T&... containers)
515 -> boost::iterator_range<boost::zip_iterator<decltype(boost::make_tuple(std::begin(containers)...))>>
517 auto zip_begin = boost::make_zip_iterator(boost::make_tuple(std::begin(containers)...));
518 auto zip_end = boost::make_zip_iterator(boost::make_tuple(std::end(containers)...));
519 return boost::make_iterator_range(zip_begin, zip_end);