Vcsn  2.4
Be Rational
cross.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <memory>
4 
5 #include <boost/iterator/iterator_facade.hpp>
6 
7 #include <vcsn/misc/tuple.hh>
8 
9 namespace vcsn
10 {
15  template <typename... Sequences>
17  {
19  using sequences_t = std::tuple<Sequences...>;
20 
22  template <std::size_t... I>
24 
26  static constexpr size_t size = sizeof...(Sequences);
27 
29  using indices_t = vcsn::detail::make_index_sequence<sizeof...(Sequences)>;
30 
32  template <typename Seq>
33  using seq_t = std::remove_reference_t<Seq>;
34 
36  using value_type
37  = std::tuple<typename seq_t<Sequences>::value_type...>;
38 
40  : sequences_(std::move(sequences))
41  {}
42 
43  cross_sequences(Sequences... sequences)
44  : sequences_(sequences...)
45  {}
46 
48  using const_iterators_t
49  = std::tuple<typename seq_t<Sequences>::const_iterator...>;
50 
52  using iterators_t
53  = std::tuple<typename seq_t<Sequences>::iterator...>;
54 
56  template <typename ValueType,
57  typename IteratorsType>
59  : public boost::iterator_facade<
60  cross_iterator<ValueType, IteratorsType>
61  , ValueType
62  , boost::forward_traversal_tag
63  , ValueType // Reference.
64  >
65  {
67  using iterators_type = IteratorsType;
68 
70  const iterators_type& begins, const iterators_type& ends)
71  : is_{is}
72  , begins_{begins}
73  , ends_{ends}
74  {
75  // If one of the ranges is empty, we are done already.
76  if (empty())
77  done_();
78  }
79 
81  : cross_iterator{is, is, ends}
82  {}
83 
84  template <typename OtherValue, typename OtherIterators>
86  : cross_iterator{that.is_, that.begins_, that.ends_}
87  {}
88 
95 
97  bool empty() const
98  {
99  return empty_(indices_t{});
100  }
101 
103  void increment()
104  {
105  if (increment_() == -1)
106  done_();
107  }
108 
109  bool equal(const cross_iterator& that) const
110  {
111  return equal_(that, indices_t{});
112  }
113 
115  {
116  return dereference_(indices_t{});
117  }
118 
119  private:
121 
122  template <std::size_t... I>
123  bool empty_(seq<I...>) const
124  {
125  for (auto n: {(std::get<I>(begins_) == std::get<I>(ends_))...})
126  if (n)
127  return true;
128  return false;
129  }
130 
132  void done_()
133  {
134  is_ = ends_;
135  }
136 
140  {
141  auto res = increment_(indices_t{});
142  // Reset all the iterators that are before the first one that could
143  // advance.
144  if (res != -1)
145  reset_up_to_(res);
146  return res;
147  }
148 
149  template <std::size_t... I>
151  {
152  int res = -1;
153  using swallow = int[];
154  (void) swallow
155  {
156  (res == -1
157  && std::get<size-1-I>(is_) != std::get<size-1-I>(ends_)
158  && ++std::get<size-1-I>(is_) != std::get<size-1-I>(ends_))
159  ? res = size-1-I
160  : 0
161  ...
162  };
163  return res;
164  }
165 
167  void reset_up_to_(int n)
168  {
169  reset_up_to_(n, indices_t{});
170  }
171 
172  template <std::size_t... I>
173  void reset_up_to_(size_t n, seq<I...>)
174  {
175  using swallow = int[];
176  (void) swallow
177  {
178  (n < I
179  && ((std::get<I>(is_) = std::get<I>(begins_)), true))...
180  };
181  }
182 
183  template <std::size_t... I>
184  bool equal_(const cross_iterator& that, seq<I...>) const
185  {
186  for (auto n: {(std::get<I>(is_) == std::get<I>(that.is_))...})
187  if (!n)
188  return false;
189  return true;
190  }
191 
193  template <std::size_t... I>
195  {
196  return value_type{(*std::get<I>(is_))...};
197  }
198  };
199 
202 
205 
207  {
208  auto res = cbegin_(indices_t{});
209  return res;
210  }
211 
213  {
214  return cend_(indices_t{});
215  }
216 
218  {
219  return cbegin();
220  }
221 
223  {
224  return cend();
225  }
226 
228  {
229  auto res = begin_(indices_t{});
230  return res;
231  }
232 
234  {
235  return end_(indices_t{});
236  }
237 
239  bool empty() const
240  {
241  return cbegin() == cend();
242  }
243 
244 
245  private:
246  template <std::size_t... I>
248  {
249  // FIXME: clang-3.5: std::cbegin/cend are not supported, yet.
250  using std::begin;
251  using std::end;
252  return {const_iterators_t{begin(std::get<I>(sequences_))...},
253  const_iterators_t{end(std::get<I>(sequences_))...}};
254  }
255 
256  template <std::size_t... I>
258  {
259  using std::end;
260  return {const_iterators_t{end(std::get<I>(sequences_))...},
261  const_iterators_t{end(std::get<I>(sequences_))...}};
262  }
263 
264  template <std::size_t... I>
266  {
267  using std::begin;
268  using std::end;
269  return {iterators_t{begin(std::get<I>(sequences_))...},
270  iterators_t{end(std::get<I>(sequences_))...}};
271  }
272 
273  template <std::size_t... I>
275  {
276  using std::end;
277  return {iterators_t{end(std::get<I>(sequences_))...},
278  iterators_t{end(std::get<I>(sequences_))...}};
279  }
280 
283  };
284 
285  template <typename... Sequences>
286  cross_sequences<Sequences...>
287  cross(Sequences&&... seqs)
288  {
289  return {std::forward<Sequences>(seqs)...};
290  }
291 
292  template <typename... Sequences>
293  cross_sequences<Sequences...>
294  cross_tuple(const std::tuple<Sequences...>& seqs)
295  {
296  return {seqs};
297  }
298 }
cross_iterator(const iterators_type &is, const iterators_type &ends)
Definition: cross.hh:80
STL namespace.
std::tuple< Sequences... > sequences_t
Type of the tuple of all the maps.
Definition: cross.hh:19
bool empty() const
Whether the sequence is empty.
Definition: cross.hh:239
iterators_type ends_
The ends.
Definition: cross.hh:94
Composite iterator.
Definition: cross.hh:58
return res
Definition: multiply.hh:398
iterator begin_(seq< I... >)
Definition: cross.hh:265
const_iterator cend_(seq< I... >) const
Definition: cross.hh:257
std::tuple< typename seq_t< Sequences >::const_iterator... > const_iterators_t
Tuple of const_iterators.
Definition: cross.hh:49
const_iterator cend() const
Definition: cross.hh:212
sequences_t sequences_
The sequences we iterate upon.
Definition: cross.hh:282
bool empty_(seq< I... >) const
Definition: cross.hh:123
cross_iterator(const iterators_type &is, const iterators_type &begins, const iterators_type &ends)
Definition: cross.hh:69
void reset_up_to_(size_t n, seq< I... >)
Definition: cross.hh:173
static constexpr size_t size
Number of sequences.
Definition: cross.hh:26
const_iterator cbegin() const
Definition: cross.hh:206
bool equal(const cross_iterator &that) const
Definition: cross.hh:109
iterators_type is_
The current position.
Definition: cross.hh:90
bool equal_(const cross_iterator &that, seq< I... >) const
Definition: cross.hh:184
void done_()
We have reached the end, move all the cursors to this end.
Definition: cross.hh:132
cross_iterator(cross_iterator< OtherValue, OtherIterators > const &that)
Definition: cross.hh:85
std::tuple< typename seq_t< Sequences >::iterator... > iterators_t
Tuple of iterators.
Definition: cross.hh:53
std::remove_reference_t< Seq > seq_t
The type of the underlying sequences, without reference.
Definition: cross.hh:33
Definition: a-star.hh:8
cross_sequences(sequences_t sequences)
Definition: cross.hh:39
iterators_type begins_
The begins.
Definition: cross.hh:92
friend class boost::iterator_core_access
Definition: cross.hh:120
iterator end_(seq< I... >)
Definition: cross.hh:274
iterator begin()
Definition: cross.hh:227
const_iterator cbegin_(seq< I... >) const
Definition: cross.hh:247
void increment()
Advance to next position.
Definition: cross.hh:103
iterator end()
Definition: cross.hh:233
auto tuple(const Auts &...as)
Build the (accessible part of the) tuple.
cross_sequences< Sequences... > cross_tuple(const std::tuple< Sequences... > &seqs)
Definition: cross.hh:294
Provide a range that allows to iterate over the cross product of the provided ranges.
Definition: cross.hh:16
const_iterator end() const
Definition: cross.hh:222
IteratorsType iterators_type
Underlying iterators.
Definition: cross.hh:67
cross_sequences< Sequences... > cross(Sequences &&...seqs)
Definition: cross.hh:287
std::tuple< typename seq_t< Sequences >::value_type... > value_type
The type of the members.
Definition: cross.hh:37
cross_sequences(Sequences...sequences)
Definition: cross.hh:43
bool empty() const
Whether some of the range is empty.
Definition: cross.hh:97
int increment_()
Move to the next position.
Definition: cross.hh:139
const_iterator begin() const
Definition: cross.hh:217
value_type dereference_(seq< I... >) const
Tuple of values.
Definition: cross.hh:194
void reset_up_to_(int n)
Move beginning of ranges to their end, and align.
Definition: cross.hh:167
value_type dereference() const
Definition: cross.hh:114