MPQC  3.0.0-alpha
iterators.h
1 //
2 // iterators.h
3 //
4 // Contains generalized iterators, ranges, and other utilities for iteration
5 //
6 // Copyright (C) 2014 David Hollman
7 //
8 // Author: David Hollman
9 // Maintainer: DSH
10 // Created: Feb 5, 2014
11 //
12 // This file is part of the SC Toolkit.
13 //
14 // The SC Toolkit is free software; you can redistribute it and/or modify
15 // it under the terms of the GNU Library General Public License as published by
16 // the Free Software Foundation; either version 2, or (at your option)
17 // any later version.
18 //
19 // The SC Toolkit is distributed in the hope that it will be useful,
20 // but WITHOUT ANY WARRANTY; without even the implied warranty of
21 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 // GNU Library General Public License for more details.
23 //
24 // You should have received a copy of the GNU Library General Public License
25 // along with the SC Toolkit; see the file COPYING.LIB. If not, write to
26 // the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
27 //
28 // The U.S. Government is granted a limited license as per AL 91-7.
29 //
30 
31 #ifndef _util_misc_iterators_h
32 #define _util_misc_iterators_h
33 
34 // Standard library includes
35 #include <type_traits>
36 
37 // Boost includes
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>
47 
48 
49 namespace sc {
50 
51 namespace {
52  template <typename T>
53  struct iterable_iterator {
54  typedef decltype(typename std::remove_reference<T>::type().begin()) type;
55  };
56 
57  template <typename T>
58  struct iterator_dereference {
59  typedef typename std::remove_reference<T>::type::reference type;
60  };
61 
62  template <typename T>
63  struct iterable_iterator_dereference {
64  typedef typename iterator_dereference<
65  typename iterable_iterator<T>::type
66  >::type type;
67  };
68 
69  template<>
70  struct iterator_dereference<boost::tuples::null_type> {
71  typedef boost::tuples::null_type type;
72  };
73 
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
79  > type;
80  };
81 
82  template <typename H, typename T>
83  typename boost::enable_if<
84  boost::is_same<T, boost::tuples::null_type>,
85  boost::tuples::cons<
86  typename iterator_dereference<H>::type,
87  typename iterator_dereference<T>::type
88  >
89  >::type dereferencer(const boost::tuples::cons<H, T>& cons_iters);
90 
91  template <typename H, typename T>
92  typename boost::disable_if<
93  boost::is_same<T, boost::tuples::null_type>,
94  boost::tuples::cons<
95  typename iterator_dereference<H>::type,
96  typename iterator_dereference<T>::type
97  >
98  >::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
103  >(
104  *cons_iters.head,
105  dereferencer(cons_iters.tail)
106  );
107  }
108 
109  template <typename H, typename T>
110  typename boost::enable_if<
111  boost::is_same<T, boost::tuples::null_type>,
112  boost::tuples::cons<
113  typename iterator_dereference<H>::type,
114  typename iterator_dereference<T>::type
115  >
116  >::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());
122  }
123 
124  template <typename Iterable>
125  typename iterable_iterator<Iterable>::type
126  get_begin(Iterable& container)
127  {
128  return container.begin();
129  }
130 }
131 
132 namespace mpl = boost::mpl;
133 
134 template<typename... Iterables>
136  : public boost::iterator_facade<
137  product_iterator<Iterables...>,
138  typename boost::tuple<typename iterable_iterator<Iterables>::type...>, // Value type
139  boost::forward_traversal_tag, // CategoryOrTraversal
140  typename boost::tuple<typename iterable_iterator_dereference<Iterables>::type...> // Reference
141  >
142 
143 {
144  public:
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;
148  typedef product_iterator<Iterables...> self_type;
149 
150  private:
151 
152  iterators_type spots_;
153  iterables_type iterables_;
154 
155 
156  friend class boost::iterator_core_access;
157 
158  reference dereference() const {
159  return static_cast<reference>(
160  dereferencer(spots_)
161  );
162  }
163 
164 
165  template<typename... OtherIterTypes>
166  bool equal(product_iterator<OtherIterTypes...> const& other) const
167  {
168  return spots_ == other.spots_;
169  }
170 
171 
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,
175  bool
176  >::type
177  increment_impl(
178  boost::tuples::cons<H, T>& cons_iters,
179  boost::tuples::cons<H2, T2>& cons_containers
180  )
181  {
182  if(increment_impl(cons_iters.tail, cons_containers.tail)) {
183  ++(cons_iters.head);
184  if(cons_iters.head == cons_containers.head.end()) {
185  cons_iters.head = cons_containers.head.begin();
186  return true;
187  }
188  }
189  return false;
190  }
191 
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,
195  bool
196  >::type
197  increment_impl(
198  boost::tuples::cons<H, T>& cons_iters,
199  boost::tuples::cons<H2, T2>& cons_containers
200  )
201  {
202  ++(cons_iters.head);
203  if(cons_iters.head == cons_containers.head.end()) {
204  cons_iters.head = cons_containers.head.begin();
205  return true;
206  }
207  return false;
208  }
209 
210  // Outermost iterator needs to be treated specially
211  void increment_impl(
212  iterators_type& cons_iters,
213  iterables_type& cons_containers
214  )
215  {
216  if(increment_impl(cons_iters.tail, cons_containers.tail)) {
217  ++(cons_iters.head);
218  }
219  }
220 
221  void increment()
222  {
223  increment_impl(spots_, iterables_);
224  }
225 
226  public:
227 
228  explicit product_iterator(Iterables&&... iters)
229  : iterables_(iters...),
230  spots_(get_begin(iters)...)
231  { }
232 
233  static self_type end_iterator(Iterables&&... iters)
234  {
235  auto rv = self_type(std::forward<Iterables>(iters)...);
236  boost::tuples::get<0>(rv.spots_) = boost::tuples::get<0>(rv.iterables_).end();
237  return rv;
238  }
239 
240 };
241 
242 template<typename... Iterables>
243 boost::iterator_range<product_iterator<Iterables...>>
244 product_range(Iterables&&... iterables)
245 {
246  return boost::make_iterator_range(
248  std::forward<Iterables>(iterables)...
249  ),
251  std::forward<Iterables>(iterables)...
252  )
253  );
254 }
255 
257 
258 /*
259 Messy and doesn't work!
260 
261 template<typename Iterable1, typename Iterable2,
262  typename function_argument = typename iterable_iterator_dereference<Iterable1>::type
263 >
264 class dependent_pair_product_iterator
265  : public boost::iterator_facade<
266  dependent_pair_product_iterator<Iterable1, Iterable2>,
267  typename boost::tuple<
268  typename iterable_iterator<Iterable1>::type,
269  typename iterable_iterator<Iterable2>::type
270  >, // Value type
271  boost::forward_traversal_tag, // CategoryOrTraversal
272  boost::tuple<
273  typename iterable_iterator_dereference<Iterable1>::type,
274  typename iterable_iterator_dereference<Iterable2>::type
275  > // Reference
276  >
277 {
278 
279  public:
280 
281  typedef typename iterable_iterator_dereference<Iterable1>::type reference1;
282  typedef typename iterable_iterator_dereference<Iterable2>::type reference2;
283  typedef boost::tuple<reference1, reference2> reference;
284  typedef typename iterable_iterator<Iterable1>::type Iterator1;
285  typedef typename iterable_iterator<Iterable2>::type Iterator2;
286  typedef dependent_pair_product_iterator<Iterable1, Iterable2> self_type;
287  typedef std::function<Iterable2(function_argument)> iterable2_getter_type;
288 
289  protected:
290 
291  Iterable1 iterable1_;
292  Iterable2 curr_iterable2_;
293  Iterator1 spot1_;
294  Iterator2 spot2_;
295  const iterable2_getter_type& iterable2_getter_;
296 
297  friend class boost::iterator_core_access;
298 
299  reference dereference() const {
300  return boost::make_tuple(*spot1_, *spot2_);
301  }
302 
303  void increment() {
304  ++spot2_;
305  if(spot2_ == curr_iterable2_.end()) {
306  ++spot1_;
307  if(spot1_ != iterable1_.end()) {
308  curr_iterable2_ = iterable2_getter_(*spot1_);
309  spot2_ = curr_iterable2_.begin();
310  }
311  }
312  }
313 
314  template<typename Iter1, typename Iter2>
315  bool equal(dependent_pair_product_iterator<Iter1, Iter2> const& other) const
316  {
317  return spot1_ == other.spot1_ and spot2_ == other.spot2_;
318  }
319 
320  public:
321 
322  dependent_pair_product_iterator(
323  Iterable1&& iterable1,
324  iterable2_getter_type&& iterable2_getter
325  ) : iterable1_(iterable1),
326  iterable2_getter_(iterable2_getter),
327  spot1_(iterable1_.begin()),
328  curr_iterable2_(iterable2_getter_(*spot1_)),
329  spot2_(curr_iterable2_.begin())
330  { }
331 
332  static self_type end_iterator(
333  Iterable1&& iterable1,
334  iterable2_getter_type&& iterable2_getter
335  )
336  {
337  self_type rv(iterable1, iterable2_getter);
338  rv.spot1_ = rv.iterable1_.end();
339  rv.spot1_--;
340  rv.curr_iterable2_ = rv.iterable2_getter_(*rv.spot1_);
341  rv.spot2_ = rv.curr_iterable2_.end();
342  rv.spot1_++;
343  return rv;
344  }
345 
346 };
347 
348 template<typename Iterable1, typename Iterable2Getter>
349 boost::iterator_range<
350  dependent_pair_product_iterator<
351  Iterable1,
352  typename Iterable2Getter::result_type,
353  typename Iterable2Getter::argument_type
354  >
355 >
356 dependent_product_range(
357  Iterable1&& i1,
358  Iterable2Getter&& i2_getter
359 )
360 {
361  typedef typename Iterable2Getter::result_type Iterable2;
362  typedef typename Iterable2Getter::argument_type function_argument_type;
363  return boost::make_iterator_range(
364  dependent_pair_product_iterator<
365  Iterable1, Iterable2, function_argument_type
366  >(
367  std::forward<Iterable1>(i1),
368  std::forward<Iterable2Getter>(i2_getter)
369  ),
370  dependent_pair_product_iterator<
371  Iterable1, Iterable2, function_argument_type
372  >::end_iterator(
373  std::forward<Iterable1>(i1),
374  std::forward<Iterable2Getter>(i2_getter)
375  )
376  );
377 }
378 
379 */
380 
382 
383 namespace {
384 
385  // can_advance = true case
386  template<bool can_advance, typename Iterator, typename difference_type>
387  struct advance_iterator {
388  void operator()(
389  Iterator& it,
390  const difference_type& n_adv,
391  const Iterator& end_iter
392  ) const
393  {
394  it += std::min(
395  end_iter - it,
396  (typename std::iterator_traits<Iterator>::difference_type) n_adv
397  );
398  }
399  };
400 
401  template<typename Iterator, typename difference_type>
402  struct advance_iterator<false, Iterator, difference_type> {
403  void operator()(
404  Iterator& it,
405  const difference_type& n_adv,
406  const Iterator& end_iter
407  ) const
408  {
409  // assume only that Iterator is incrementable
410  for(int i = 0; i < n_adv; ++i, ++it) {
411  if(it == end_iter) {
412  break;
413  }
414  }
415  }
416  };
417 
418 } // end of anonymous namespace
419 
420 template<typename Iterator, bool base_can_be_advanced=false>
422  : public boost::iterator_adaptor<
423  threaded_iterator<Iterator>,
424  Iterator,
425  boost::use_default,
426  boost::forward_traversal_tag
427  >
428 {
429  public:
430 
431  typedef typename threaded_iterator::iterator_adaptor_ super_t;
432 
433  private:
434 
435  friend class boost::iterator_core_access;
436 
437  Iterator end_iter_;
438  int ithr_;
439  int nthr_;
440 
441  void increment() {
442  advance_iterator<
443  base_can_be_advanced,
444  Iterator,
445  decltype(nthr_)
446  >()(
447  super_t::base_reference(), nthr_, end_iter_
448  );
449  }
450 
451  public:
452 
453  threaded_iterator(Iterator&& iter, Iterator&& end_iter, int ithr, int nthr)
454  : super_t(iter), end_iter_(end_iter), ithr_(ithr), nthr_(nthr)
455  {
456  advance_iterator<
457  base_can_be_advanced,
458  Iterator,
459  decltype(ithr_)
460  >()(
461  super_t::base_reference(), ithr_, end_iter_
462  );
463  }
464 
465 };
466 
467 
468 
469 template<typename Iterator>
471 
472 template <
473  typename Range,
474  bool base_can_be_advanced=false
475 >
476 boost::iterator_range<threaded_iterator<typename iterable_iterator<Range>::type>>
477 thread_over_range(Range&& range, int ithr, int nthr)
478 {
479  return boost::make_iterator_range(
481  decltype(range.begin()), base_can_be_advanced
482  >(range.begin(), range.end(), ithr, nthr),
484  decltype(range.begin()), base_can_be_advanced
485  >(range.end(), range.end(), ithr, nthr)
486  );
487 }
488 
489 template <
490  typename Range,
491  bool base_can_be_advanced=false
492 >
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)
495 {
496  const int thr_offset = me*nthread + ithr;
497  const int increment = n_node*nthread;
498  return boost::make_iterator_range(
499  threaded_iterator<
500  decltype(range.begin()), base_can_be_advanced
501  >(range.begin(), range.end(), thr_offset, increment),
502  threaded_iterator<
503  decltype(range.begin()), base_can_be_advanced
504  >(range.end(), range.end(), thr_offset, increment)
505  );
506 }
507 
509 
510 // From http://stackoverflow.com/questions/8511035/sequence-zip-function-for-c11
511 // Make sure the containers are the same length. Behaviour is undefined otherwise
512 // TODO Length checking, if possible
513 template <typename... T>
514 auto zip(const T&... containers)
515  -> boost::iterator_range<boost::zip_iterator<decltype(boost::make_tuple(std::begin(containers)...))>>
516 {
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);
520 }
521 
522 
523 
524 } // end namespace sc
525 
526 #endif /* _util_misc_iterators_h */
mpqc::range
Definition: range.hpp:23
sc::threaded_iterator
Definition: iterators.h:421
sc::product_iterator
Definition: iterators.h:135
sc::other
SpinCase1 other(SpinCase1 S)
given 1-spin return the other 1-spin
sc
Contains all MPQC code up to version 3.
Definition: mpqcin.h:14

Generated at Sun Jan 26 2020 23:24:01 for MPQC 3.0.0-alpha using the documentation package Doxygen 1.8.16.