Vcsn  2.4
Be Rational
zip-maps.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <cassert>
4 #include <type_traits>
5 
6 #include <vcsn/misc/raise.hh> // pass
7 #include <vcsn/misc/tuple.hh> // tuple_element_t
9 
10 namespace vcsn
11 {
12 
13  struct as_tuple {};
14  struct as_pair {};
15 
16  template <typename Dereference = as_tuple, typename... Maps>
17  struct zipped_maps
18  {
20  using maps_t = std::tuple<Maps...>;
21 
23  template <std::size_t... I>
25 
27  using indices_t = vcsn::detail::make_index_sequence<sizeof...(Maps)>;
28 
29  zipped_maps(Maps... maps)
30  : maps_(maps...)
31  {}
32 
33  zipped_maps(const maps_t& maps)
34  : maps_(maps)
35  {}
36 
38  struct iterator
39  {
40  template <typename T>
41  using iterator_t = typename std::remove_reference_t<T>::const_iterator;
42  using iterators_t = std::tuple<iterator_t<Maps>...>;
43 
44  template <typename T>
45  using value_t = typename std::remove_reference_t<T>::value_type;
46  using values_t = std::tuple<value_t<Maps>...>;
47 
48  // FIXME: we should be using ::reference, but I can't get it to
49  // work with const.
50  using references_t = std::tuple<const value_t<Maps>&...>;
51 
52  template <typename T>
53  using range_t = std::pair<iterator_t<T>, iterator_t<T>>;
54  using ranges_t = std::tuple<range_t<Maps>...>;
55 
57  using key_t
58  = std::remove_const_t<typename tuple_element_t<0, values_t>::first_type>;
60  using mapped_t
61  = std::tuple<const typename std::remove_reference_t<Maps>::mapped_type&...>;
62 
64  iterator_t<Maps>... is, iterator_t<Maps>... ends)
65  : zip_(zip)
66  , is_(is...)
67  , ends_(ends...)
68  , is_done_(false)
69  {
70  align_();
71  }
72 
75 
81  bool is_done_;
82 
85  {
86  if (!is_done_)
87  {
88  ++std::get<0>(is_);
89  align_();
90  }
91  return *this;
92  }
93 
94  bool operator!=(const iterator& that) const
95  {
96  return not_equal_(that, indices_t{});
97  }
98 
100  auto dereference_(as_pair) -> std::pair<key_t, mapped_t>
101  {
103  }
104 
107  {
108  return dereference_(indices_t{});
109  }
110 
111  auto operator*() -> decltype(this->dereference_(Dereference()))
112  {
113  return dereference_(Dereference());
114  }
115 
116  private:
118  void done_()
119  {
120  is_done_ = true;
121  is_ = ends_;
122  }
123 
128  void align_()
129  {
130  if (std::get<0>(is_) == std::get<0>(ends_))
131  done_();
132  if (!is_done_)
133  {
134  key_t k = std::get<0>(is_)->first;
135  while (!is_done_)
136  {
137  auto k2 = align_(k, indices_t{});
138  if (is_done_ || k == k2)
139  break;
140  else
141  k = k2;
142  }
143  }
144  }
145 
148  template <std::size_t... I>
150  {
151  using swallow = int[];
152  (void) swallow{ (!is_done_ && (k = align_<I>(k), false))... };
153  return k;
154  }
155 
158  template <std::size_t I>
160  {
161  assert(!is_done_);
162  auto& first = std::get<I>(is_);
163 
164  // Look for the beginning of the range for key k.
165  // first = second;
166  while (first != std::get<I>(ends_)
167  && std::get<I>(zip_.maps_).key_comp()(first->first, k))
168  ++first;
169  if (first == std::get<I>(ends_))
170  // Nothing left.
171  done_();
172  else
173  // Found something, return its key.
174  k = first->first;
175  return k;
176  }
177 
178  template <std::size_t... I>
179  bool not_equal_(const iterator& that, seq<I...>) const
180  {
181  for (auto n: {(std::get<I>(is_) != std::get<I>(that.is_))...})
182  if (n)
183  return true;
184  return false;
185  }
186 
189  {
190  return std::get<0>(is_)->first;
191  }
192 
194  template <std::size_t... I>
196  {
197  // clang 3.4 on top of libstdc++ wants this ctor to be
198  // explicitly called.
199  return mapped_t{(std::get<I>(is_)->second)...};
200  }
201 
203  template <std::size_t... I>
205  {
206  // clang 3.4 on top of libstdc++ wants this ctor to be
207  // explicitly called:
208 
209  // vcsn/misc/zip-maps.hh:275:16: error: chosen constructor is
210  // explicit in copy-initialization
211  // return {(*std::get<I>(is_))...};
212  // ^~~~~~~~~~~~~~~~~~~~~~~~
213  return references_t{(*std::get<I>(is_))...};
214  }
215  };
216 
218  {
219  auto res = begin_(indices_t{});
220  return res;
221  }
222 
224  {
225  return end_(indices_t{});
226  }
227 
228  private:
229  template <std::size_t... I>
231  {
232  return iterator(*this,
233  std::get<I>(maps_).begin()...,
234  std::get<I>(maps_).end()...);
235  }
236 
237  template <std::size_t... I>
239  {
240  return iterator(*this,
241  std::get<I>(maps_).end()...,
242  std::get<I>(maps_).end()...);
243  }
244 
246  };
247 
248  template <typename Dereference = as_pair, typename... Maps>
249  zipped_maps<Dereference, Maps...>
250  zip_maps(Maps&&... maps)
251  {
252  return {std::forward<Maps>(maps)...};
253  }
254 
255  template <typename Dereference = as_pair, typename... Maps>
256  zipped_maps<Dereference, Maps...>
257  zip_map_tuple(const std::tuple<Maps...>& maps)
258  {
259  return {maps};
260  }
261 }
typename std::remove_reference_t< T >::const_iterator iterator_t
Definition: zip-maps.hh:41
typename std::remove_reference_t< T >::value_type value_t
Definition: zip-maps.hh:45
return res
Definition: multiply.hh:398
references_t dereference_(seq< I... >) const
Tuple of pairs.
Definition: zip-maps.hh:204
std::tuple< const typename std::remove_reference_t< Maps >::mapped_type &... > mapped_t
Tuple of mapped types.
Definition: zip-maps.hh:61
bool not_equal_(const iterator &that, seq< I... >) const
Definition: zip-maps.hh:179
void done_()
We have reached the end, move all the cursors to this end.
Definition: zip-maps.hh:118
auto dereference_(as_tuple) -> references_t
Return as <, , ...>.
Definition: zip-maps.hh:106
std::tuple< Maps... > maps_t
Type of the tuple of all the maps.
Definition: zip-maps.hh:20
zipped_maps(const maps_t &maps)
Definition: zip-maps.hh:33
auto operator*() -> decltype(this->dereference_(Dereference()))
Definition: zip-maps.hh:111
Composite iterator.
Definition: zip-maps.hh:38
std::remove_const_t< typename tuple_element_t< 0, values_t >::first_type > key_t
Common key type.
Definition: zip-maps.hh:58
iterator begin()
Definition: zip-maps.hh:217
Definition: a-star.hh:8
zip_sequences< Sequences... > zip(Sequences &&...seqs)
Definition: zip.hh:439
zipped_maps< Dereference, Maps... > zip_maps(Maps &&...maps)
Definition: zip-maps.hh:250
std::tuple< value_t< Maps >... > values_t
Definition: zip-maps.hh:46
key_t align_(key_t k, seq< I... >)
Try to align all the ranges to support key k.
Definition: zip-maps.hh:149
key_t align_(key_t k)
Given the current candidate key, try to find the proper range for I.
Definition: zip-maps.hh:159
zipped_maps< Dereference, Maps... > zip_map_tuple(const std::tuple< Maps... > &maps)
Definition: zip-maps.hh:257
iterators_t is_
The current position.
Definition: zip-maps.hh:77
mapped_t dereference_second_(seq< I... >) const
The associated tuple of values.
Definition: zip-maps.hh:195
zipped_maps(Maps...maps)
Definition: zip-maps.hh:29
std::tuple< iterator_t< Maps >... > iterators_t
Definition: zip-maps.hh:42
bool operator!=(const iterator &that) const
Definition: zip-maps.hh:94
auto tuple(const Auts &...as)
Build the (accessible part of the) tuple.
std::pair< iterator_t< T >, iterator_t< T >> range_t
Definition: zip-maps.hh:53
iterator & operator++()
Advance to next position.
Definition: zip-maps.hh:84
iterator end()
Definition: zip-maps.hh:223
std::tuple< const value_t< Maps > &... > references_t
Definition: zip-maps.hh:50
iterator begin_(seq< I... >)
Definition: zip-maps.hh:230
void align_()
Align all iterators on the first common key.
Definition: zip-maps.hh:128
iterator end_(seq< I... >)
Definition: zip-maps.hh:238
bool is_done_
Whether we reached the end.
Definition: zip-maps.hh:81
key_t dereference_first_() const
The common key.
Definition: zip-maps.hh:188
std::tuple< range_t< Maps >... > ranges_t
Definition: zip-maps.hh:54
iterator(zipped_maps &zip, iterator_t< Maps >...is, iterator_t< Maps >...ends)
Definition: zip-maps.hh:63
iterators_t ends_
The genuine ends.
Definition: zip-maps.hh:79
auto dereference_(as_pair) -> std::pair< key_t, mapped_t >
Return as >.
Definition: zip-maps.hh:100
zipped_maps & zip_
The maps etc.
Definition: zip-maps.hh:74