1 /*
2 * Copyright © 2018 Google, Inc.
3 * Copyright © 2019 Facebook, Inc.
4 *
5 * This is part of HarfBuzz, a text shaping library.
6 *
7 * Permission is hereby granted, without written agreement and without
8 * license or royalty fees, to use, copy, modify, and distribute this
9 * software and its documentation for any purpose, provided that the
10 * above copyright notice and the following two paragraphs appear in
11 * all copies of this software.
12 *
13 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
14 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
15 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
16 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
17 * DAMAGE.
18 *
19 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
20 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
21 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
22 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
23 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
24 *
25 * Google Author(s): Behdad Esfahbod
26 * Facebook Author(s): Behdad Esfahbod
27 */
28
29 #ifndef HB_ITER_HH
30 #define HB_ITER_HH
31
32 #include "hb.hh"
33 #include "hb-algs.hh"
34 #include "hb-meta.hh"
35
36
37 /* Unified iterator object.
38 *
39 * The goal of this template is to make the same iterator interface
40 * available to all types, and make it very easy and compact to use.
41 * hb_iter_tator objects are small, light-weight, objects that can be
42 * copied by value. If the collection / object being iterated on
43 * is writable, then the iterator returns lvalues, otherwise it
44 * returns rvalues.
45 *
46 * TODO Document more.
47 *
48 * If iterator implementation implements operator!=, then can be
49 * used in range-based for loop. That already happens if the iterator
50 * is random-access. Otherwise, the range-based for loop incurs
51 * one traversal to find end(), which can be avoided if written
52 * as a while-style for loop, or if iterator implements a faster
53 * __end__() method.
54 * TODO When opting in for C++17, address this by changing return
55 * type of .end()?
56 */
57
58 /*
59 * Base classes for iterators.
60 */
61
62 /* Base class for all iterators. */
63 template <typename iter_t, typename Item = typename iter_t::__item_t__>
64 struct hb_iter_t
65 {
66 typedef Item item_t;
get_item_sizehb_iter_t67 constexpr unsigned get_item_size () const { return hb_static_size (Item); }
68 static constexpr bool is_iterator = true;
69 static constexpr bool is_random_access_iterator = false;
70 static constexpr bool is_sorted_iterator = false;
71
72 private:
73 /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
thizhb_iter_t74 const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
thizhb_iter_t75 iter_t* thiz () { return static_cast< iter_t *> (this); }
76 public:
77
78 /* TODO:
79 * Port operators below to use hb_enable_if to sniff which method implements
80 * an operator and use it, and remove hb_iter_fallback_mixin_t completely. */
81
82 /* Operators. */
iterhb_iter_t83 iter_t iter () const { return *thiz(); }
operator +hb_iter_t84 iter_t operator + () const { return *thiz(); }
beginhb_iter_t85 iter_t begin () const { return *thiz(); }
endhb_iter_t86 iter_t end () const { return thiz()->__end__ (); }
operator boolhb_iter_t87 explicit operator bool () const { return thiz()->__more__ (); }
lenhb_iter_t88 unsigned len () const { return thiz()->__len__ (); }
89 /* The following can only be enabled if item_t is reference type. Otherwise
90 * it will be returning pointer to temporary rvalue.
91 * TODO Use a wrapper return type to fix for non-reference type. */
92 template <typename T = item_t,
93 hb_enable_if (std::is_reference<T>::value)>
operator ->hb_iter_t94 hb_remove_reference<item_t>* operator -> () const { return std::addressof (**thiz()); }
operator *hb_iter_t95 item_t operator * () const { return thiz()->__item__ (); }
operator *hb_iter_t96 item_t operator * () { return thiz()->__item__ (); }
operator []hb_iter_t97 item_t operator [] (unsigned i) const { return thiz()->__item_at__ (i); }
operator []hb_iter_t98 item_t operator [] (unsigned i) { return thiz()->__item_at__ (i); }
operator +=hb_iter_t99 iter_t& operator += (unsigned count) & { thiz()->__forward__ (count); return *thiz(); }
operator +=hb_iter_t100 iter_t operator += (unsigned count) && { thiz()->__forward__ (count); return *thiz(); }
operator ++hb_iter_t101 iter_t& operator ++ () & { thiz()->__next__ (); return *thiz(); }
operator ++hb_iter_t102 iter_t operator ++ () && { thiz()->__next__ (); return *thiz(); }
operator -=hb_iter_t103 iter_t& operator -= (unsigned count) & { thiz()->__rewind__ (count); return *thiz(); }
operator -=hb_iter_t104 iter_t operator -= (unsigned count) && { thiz()->__rewind__ (count); return *thiz(); }
operator --hb_iter_t105 iter_t& operator -- () & { thiz()->__prev__ (); return *thiz(); }
operator --hb_iter_t106 iter_t operator -- () && { thiz()->__prev__ (); return *thiz(); }
operator +hb_iter_t107 iter_t operator + (unsigned count) const { auto c = thiz()->iter (); c += count; return c; }
operator +(unsigned count,const iter_t & it)108 friend iter_t operator + (unsigned count, const iter_t &it) { return it + count; }
operator ++hb_iter_t109 iter_t operator ++ (int) { iter_t c (*thiz()); ++*thiz(); return c; }
operator -hb_iter_t110 iter_t operator - (unsigned count) const { auto c = thiz()->iter (); c -= count; return c; }
operator --hb_iter_t111 iter_t operator -- (int) { iter_t c (*thiz()); --*thiz(); return c; }
112 template <typename T>
operator >>hb_iter_t113 iter_t& operator >> (T &v) & { v = **thiz(); ++*thiz(); return *thiz(); }
114 template <typename T>
operator >>hb_iter_t115 iter_t operator >> (T &v) && { v = **thiz(); ++*thiz(); return *thiz(); }
116 template <typename T>
operator <<hb_iter_t117 iter_t& operator << (const T v) & { **thiz() = v; ++*thiz(); return *thiz(); }
118 template <typename T>
operator <<hb_iter_t119 iter_t operator << (const T v) && { **thiz() = v; ++*thiz(); return *thiz(); }
120
121 protected:
122 hb_iter_t () = default;
123 hb_iter_t (const hb_iter_t &o HB_UNUSED) = default;
124 hb_iter_t (hb_iter_t &&o HB_UNUSED) = default;
125 hb_iter_t& operator = (const hb_iter_t &o HB_UNUSED) = default;
126 hb_iter_t& operator = (hb_iter_t &&o HB_UNUSED) = default;
127 };
128
129 #define HB_ITER_USING(Name) \
130 using item_t = typename Name::item_t; \
131 using Name::begin; \
132 using Name::end; \
133 using Name::get_item_size; \
134 using Name::is_iterator; \
135 using Name::iter; \
136 using Name::operator bool; \
137 using Name::len; \
138 using Name::operator ->; \
139 using Name::operator *; \
140 using Name::operator []; \
141 using Name::operator +=; \
142 using Name::operator ++; \
143 using Name::operator -=; \
144 using Name::operator --; \
145 using Name::operator +; \
146 using Name::operator -; \
147 using Name::operator >>; \
148 using Name::operator <<; \
149 static_assert (true, "")
150
151 /* Returns iterator / item type of a type. */
152 template <typename Iterable>
153 using hb_iter_type = decltype (hb_deref (hb_declval (Iterable)).iter ());
154 template <typename Iterable>
155 using hb_item_type = decltype (*hb_deref (hb_declval (Iterable)).iter ());
156
157
158 template <typename> struct hb_array_t;
159 template <typename> struct hb_sorted_array_t;
160
161 struct
162 {
163 template <typename T> hb_iter_type<T>
operator ()__anon0be8885c0108164 operator () (T&& c) const
165 { return hb_deref (std::forward<T> (c)).iter (); }
166
167 /* Specialization for C arrays. */
168
169 template <typename Type> inline hb_array_t<Type>
operator ()__anon0be8885c0108170 operator () (Type *array, unsigned int length) const
171 { return hb_array_t<Type> (array, length); }
172
173 template <typename Type, unsigned int length> hb_array_t<Type>
operator ()__anon0be8885c0108174 operator () (Type (&array)[length]) const
175 { return hb_array_t<Type> (array, length); }
176
177 }
178 HB_FUNCOBJ (hb_iter);
179 struct
180 {
181 template <typename T> unsigned
operator ()__anon0be8885c0208182 operator () (T&& c) const
183 { return c.len (); }
184
185 }
186 HB_FUNCOBJ (hb_len);
187
188 /* Mixin to fill in what the subclass doesn't provide. */
189 template <typename iter_t, typename item_t = typename iter_t::__item_t__>
190 struct hb_iter_fallback_mixin_t
191 {
192 private:
193 /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
thizhb_iter_fallback_mixin_t194 const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
thizhb_iter_fallback_mixin_t195 iter_t* thiz () { return static_cast< iter_t *> (this); }
196 public:
197
198 /* Access: Implement __item__(), or __item_at__() if random-access. */
__item__hb_iter_fallback_mixin_t199 item_t __item__ () const { return (*thiz())[0]; }
__item_at__hb_iter_fallback_mixin_t200 item_t __item_at__ (unsigned i) const { return *(*thiz() + i); }
201
202 /* Termination: Implement __more__(), or __len__() if random-access. */
__more__hb_iter_fallback_mixin_t203 bool __more__ () const { return bool (thiz()->len ()); }
__len__hb_iter_fallback_mixin_t204 unsigned __len__ () const
205 { iter_t c (*thiz()); unsigned l = 0; while (c) { c++; l++; } return l; }
206
207 /* Advancing: Implement __next__(), or __forward__() if random-access. */
__next__hb_iter_fallback_mixin_t208 void __next__ () { *thiz() += 1; }
__forward__hb_iter_fallback_mixin_t209 void __forward__ (unsigned n) { while (*thiz() && n--) ++*thiz(); }
210
211 /* Rewinding: Implement __prev__() or __rewind__() if bidirectional. */
__prev__hb_iter_fallback_mixin_t212 void __prev__ () { *thiz() -= 1; }
__rewind__hb_iter_fallback_mixin_t213 void __rewind__ (unsigned n) { while (*thiz() && n--) --*thiz(); }
214
215 /* Range-based for: Implement __end__() if can be done faster,
216 * and operator!=. */
__end__hb_iter_fallback_mixin_t217 iter_t __end__ () const
218 {
219 if (thiz()->is_random_access_iterator)
220 return *thiz() + thiz()->len ();
221 /* Above expression loops twice. Following loops once. */
222 auto it = *thiz();
223 while (it) ++it;
224 return it;
225 }
226
227 protected:
228 hb_iter_fallback_mixin_t () = default;
229 hb_iter_fallback_mixin_t (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default;
230 hb_iter_fallback_mixin_t (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default;
231 hb_iter_fallback_mixin_t& operator = (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default;
232 hb_iter_fallback_mixin_t& operator = (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default;
233 };
234
235 template <typename iter_t, typename item_t = typename iter_t::__item_t__>
236 struct hb_iter_with_fallback_t :
237 hb_iter_t<iter_t, item_t>,
238 hb_iter_fallback_mixin_t<iter_t, item_t>
239 {
240 protected:
241 hb_iter_with_fallback_t () = default;
242 hb_iter_with_fallback_t (const hb_iter_with_fallback_t &o HB_UNUSED) = default;
243 hb_iter_with_fallback_t (hb_iter_with_fallback_t &&o HB_UNUSED) = default;
244 hb_iter_with_fallback_t& operator = (const hb_iter_with_fallback_t &o HB_UNUSED) = default;
245 hb_iter_with_fallback_t& operator = (hb_iter_with_fallback_t &&o HB_UNUSED) = default;
246 };
247
248 /*
249 * Meta-programming predicates.
250 */
251
252 /* hb_is_iterator() / hb_is_iterator_of() */
253
254 template<typename Iter, typename Item>
255 struct hb_is_iterator_of
256 {
257 template <typename Item2 = Item>
258 static hb_true_type impl (hb_priority<2>, hb_iter_t<Iter, hb_type_identity<Item2>> *);
259 static hb_false_type impl (hb_priority<0>, const void *);
260
261 public:
262 static constexpr bool value = decltype (impl (hb_prioritize, hb_declval (Iter*)))::value;
263 };
264 #define hb_is_iterator_of(Iter, Item) hb_is_iterator_of<Iter, Item>::value
265 #define hb_is_iterator(Iter) hb_is_iterator_of (Iter, typename Iter::item_t)
266
267 /* hb_is_iterable() */
268
269 template <typename T>
270 struct hb_is_iterable
271 {
272 private:
273
274 template <typename U>
275 static auto impl (hb_priority<1>) -> decltype (hb_declval (U).iter (), hb_true_type ());
276
277 template <typename>
278 static hb_false_type impl (hb_priority<0>);
279
280 public:
281 static constexpr bool value = decltype (impl<T> (hb_prioritize))::value;
282 };
283 #define hb_is_iterable(Iterable) hb_is_iterable<Iterable>::value
284
285 /* hb_is_source_of() / hb_is_sink_of() */
286
287 template<typename Iter, typename Item>
288 struct hb_is_source_of
289 {
290 private:
291 template <typename Iter2 = Iter,
292 hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<const Item>))>
293 static hb_true_type impl (hb_priority<2>);
294 template <typename Iter2 = Iter>
295 static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) >> hb_declval (Item &), hb_true_type ());
296 static hb_false_type impl (hb_priority<0>);
297
298 public:
299 static constexpr bool value = decltype (impl (hb_prioritize))::value;
300 };
301 #define hb_is_source_of(Iter, Item) hb_is_source_of<Iter, Item>::value
302
303 template<typename Iter, typename Item>
304 struct hb_is_sink_of
305 {
306 private:
307 template <typename Iter2 = Iter,
308 hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<Item>))>
309 static hb_true_type impl (hb_priority<2>);
310 template <typename Iter2 = Iter>
311 static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) << hb_declval (Item), hb_true_type ());
312 static hb_false_type impl (hb_priority<0>);
313
314 public:
315 static constexpr bool value = decltype (impl (hb_prioritize))::value;
316 };
317 #define hb_is_sink_of(Iter, Item) hb_is_sink_of<Iter, Item>::value
318
319 /* This is commonly used, so define: */
320 #define hb_is_sorted_source_of(Iter, Item) \
321 (hb_is_source_of(Iter, Item) && Iter::is_sorted_iterator)
322
323
324 /* Range-based 'for' for iterables. */
325
326 template <typename Iterable,
327 hb_requires (hb_is_iterable (Iterable))>
328 static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ())
329
330 template <typename Iterable,
331 hb_requires (hb_is_iterable (Iterable))>
332 static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ())
333
334 /* begin()/end() are NOT looked up non-ADL. So each namespace must declare them.
335 * Do it for namespace OT. */
336 namespace OT {
337
338 template <typename Iterable,
339 hb_requires (hb_is_iterable (Iterable))>
340 static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ())
341
342 template <typename Iterable,
343 hb_requires (hb_is_iterable (Iterable))>
344 static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ())
345
346 }
347
348
349 /*
350 * Adaptors, combiners, etc.
351 */
352
353 template <typename Lhs, typename Rhs,
354 hb_requires (hb_is_iterator (Lhs))>
355 static inline auto
356 operator | (Lhs&& lhs, Rhs&& rhs) HB_AUTO_RETURN (std::forward<Rhs> (rhs) (std::forward<Lhs> (lhs)))
357
358 /* hb_map(), hb_filter(), hb_reduce() */
359
360 enum class hb_function_sortedness_t {
361 NOT_SORTED,
362 RETAINS_SORTING,
363 SORTED,
364 };
365
366 template <typename Iter, typename Proj, hb_function_sortedness_t Sorted,
367 hb_requires (hb_is_iterator (Iter))>
368 struct hb_map_iter_t :
369 hb_iter_t<hb_map_iter_t<Iter, Proj, Sorted>,
370 decltype (hb_get (hb_declval (Proj), *hb_declval (Iter)))>
371 {
hb_map_iter_thb_map_iter_t372 hb_map_iter_t (const Iter& it, Proj f_) : it (it), f (f_) {}
373
374 typedef decltype (hb_get (hb_declval (Proj), *hb_declval (Iter))) __item_t__;
375 static constexpr bool is_random_access_iterator = Iter::is_random_access_iterator;
376 static constexpr bool is_sorted_iterator =
377 Sorted == hb_function_sortedness_t::SORTED ? true :
378 Sorted == hb_function_sortedness_t::RETAINS_SORTING ? Iter::is_sorted_iterator :
379 false;
__item__hb_map_iter_t380 __item_t__ __item__ () const { return hb_get (f.get (), *it); }
__item_at__hb_map_iter_t381 __item_t__ __item_at__ (unsigned i) const { return hb_get (f.get (), it[i]); }
__more__hb_map_iter_t382 bool __more__ () const { return bool (it); }
__len__hb_map_iter_t383 unsigned __len__ () const { return it.len (); }
__next__hb_map_iter_t384 void __next__ () { ++it; }
__forward__hb_map_iter_t385 void __forward__ (unsigned n) { it += n; }
__prev__hb_map_iter_t386 void __prev__ () { --it; }
__rewind__hb_map_iter_t387 void __rewind__ (unsigned n) { it -= n; }
__end__hb_map_iter_t388 hb_map_iter_t __end__ () const { return hb_map_iter_t (it.end (), f); }
operator !=hb_map_iter_t389 bool operator != (const hb_map_iter_t& o) const
390 { return it != o.it; }
391
392 private:
393 Iter it;
394 hb_reference_wrapper<Proj> f;
395 };
396
397 template <typename Proj, hb_function_sortedness_t Sorted>
398 struct hb_map_iter_factory_t
399 {
hb_map_iter_factory_thb_map_iter_factory_t400 hb_map_iter_factory_t (Proj f) : f (f) {}
401
402 template <typename Iter,
403 hb_requires (hb_is_iterator (Iter))>
404 hb_map_iter_t<Iter, Proj, Sorted>
operator ()hb_map_iter_factory_t405 operator () (Iter it)
406 { return hb_map_iter_t<Iter, Proj, Sorted> (it, f); }
407
408 private:
409 Proj f;
410 };
411 struct
412 {
413 template <typename Proj>
414 hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED>
operator ()__anon0be8885c0308415 operator () (Proj&& f) const
416 { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED> (f); }
417 }
418 HB_FUNCOBJ (hb_map);
419 struct
420 {
421 template <typename Proj>
422 hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING>
operator ()__anon0be8885c0408423 operator () (Proj&& f) const
424 { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING> (f); }
425 }
426 HB_FUNCOBJ (hb_map_retains_sorting);
427 struct
428 {
429 template <typename Proj>
430 hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED>
operator ()__anon0be8885c0508431 operator () (Proj&& f) const
432 { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED> (f); }
433 }
434 HB_FUNCOBJ (hb_map_sorted);
435
436 template <typename Iter, typename Pred, typename Proj,
437 hb_requires (hb_is_iterator (Iter))>
438 struct hb_filter_iter_t :
439 hb_iter_with_fallback_t<hb_filter_iter_t<Iter, Pred, Proj>,
440 typename Iter::item_t>
441 {
hb_filter_iter_thb_filter_iter_t442 hb_filter_iter_t (const Iter& it_, Pred p_, Proj f_) : it (it_), p (p_), f (f_)
443 { while (it && !hb_has (p.get (), hb_get (f.get (), *it))) ++it; }
444
445 typedef typename Iter::item_t __item_t__;
446 static constexpr bool is_sorted_iterator = Iter::is_sorted_iterator;
__item__hb_filter_iter_t447 __item_t__ __item__ () const { return *it; }
__more__hb_filter_iter_t448 bool __more__ () const { return bool (it); }
__next__hb_filter_iter_t449 void __next__ () { do ++it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); }
__prev__hb_filter_iter_t450 void __prev__ () { do --it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); }
__end__hb_filter_iter_t451 hb_filter_iter_t __end__ () const { return hb_filter_iter_t (it.end (), p, f); }
operator !=hb_filter_iter_t452 bool operator != (const hb_filter_iter_t& o) const
453 { return it != o.it; }
454
455 private:
456 Iter it;
457 hb_reference_wrapper<Pred> p;
458 hb_reference_wrapper<Proj> f;
459 };
460 template <typename Pred, typename Proj>
461 struct hb_filter_iter_factory_t
462 {
hb_filter_iter_factory_thb_filter_iter_factory_t463 hb_filter_iter_factory_t (Pred p, Proj f) : p (p), f (f) {}
464
465 template <typename Iter,
466 hb_requires (hb_is_iterator (Iter))>
467 hb_filter_iter_t<Iter, Pred, Proj>
operator ()hb_filter_iter_factory_t468 operator () (Iter it)
469 { return hb_filter_iter_t<Iter, Pred, Proj> (it, p, f); }
470
471 private:
472 Pred p;
473 Proj f;
474 };
475 struct
476 {
477 template <typename Pred = decltype ((hb_identity)),
478 typename Proj = decltype ((hb_identity))>
479 hb_filter_iter_factory_t<Pred, Proj>
operator ()__anon0be8885c0608480 operator () (Pred&& p = hb_identity, Proj&& f = hb_identity) const
481 { return hb_filter_iter_factory_t<Pred, Proj> (p, f); }
482 }
483 HB_FUNCOBJ (hb_filter);
484
485 template <typename Redu, typename InitT>
486 struct hb_reduce_t
487 {
hb_reduce_thb_reduce_t488 hb_reduce_t (Redu r, InitT init_value) : r (r), init_value (init_value) {}
489
490 template <typename Iter,
491 hb_requires (hb_is_iterator (Iter)),
492 typename AccuT = hb_decay<decltype (hb_declval (Redu) (hb_declval (InitT), hb_declval (typename Iter::item_t)))>>
493 AccuT
operator ()hb_reduce_t494 operator () (Iter it)
495 {
496 AccuT value = init_value;
497 for (; it; ++it)
498 value = r (value, *it);
499 return value;
500 }
501
502 private:
503 Redu r;
504 InitT init_value;
505 };
506 struct
507 {
508 template <typename Redu, typename InitT>
509 hb_reduce_t<Redu, InitT>
operator ()__anon0be8885c0708510 operator () (Redu&& r, InitT init_value) const
511 { return hb_reduce_t<Redu, InitT> (r, init_value); }
512 }
513 HB_FUNCOBJ (hb_reduce);
514
515
516 /* hb_zip() */
517
518 template <typename A, typename B>
519 struct hb_zip_iter_t :
520 hb_iter_t<hb_zip_iter_t<A, B>,
521 hb_pair_t<typename A::item_t, typename B::item_t>>
522 {
hb_zip_iter_thb_zip_iter_t523 hb_zip_iter_t () {}
hb_zip_iter_thb_zip_iter_t524 hb_zip_iter_t (const A& a, const B& b) : a (a), b (b) {}
525
526 typedef hb_pair_t<typename A::item_t, typename B::item_t> __item_t__;
527 static constexpr bool is_random_access_iterator =
528 A::is_random_access_iterator &&
529 B::is_random_access_iterator;
530 /* Note. The following categorization is only valid if A is strictly sorted,
531 * ie. does NOT have duplicates. Previously I tried to categorize sortedness
532 * more granularly, see commits:
533 *
534 * 513762849a683914fc266a17ddf38f133cccf072
535 * 4d3cf2adb669c345cc43832d11689271995e160a
536 *
537 * However, that was not enough, since hb_sorted_array_t, hb_sorted_vector_t,
538 * SortedArrayOf, etc all needed to be updated to add more variants. At that
539 * point I saw it not worth the effort, and instead we now deem all sorted
540 * collections as essentially strictly-sorted for the purposes of zip.
541 *
542 * The above assumption is not as bad as it sounds. Our "sorted" comes with
543 * no guarantees. It's just a contract, put in place to help you remember,
544 * and think about, whether an iterator you receive is expected to be
545 * sorted or not. As such, it's not perfect by definition, and should not
546 * be treated so. The inaccuracy here just errs in the direction of being
547 * more permissive, so your code compiles instead of erring on the side of
548 * marking your zipped iterator unsorted in which case your code won't
549 * compile.
550 *
551 * This semantical limitation does NOT affect logic in any other place I
552 * know of as of this writing.
553 */
554 static constexpr bool is_sorted_iterator = A::is_sorted_iterator;
555
__item__hb_zip_iter_t556 __item_t__ __item__ () const { return __item_t__ (*a, *b); }
__item_at__hb_zip_iter_t557 __item_t__ __item_at__ (unsigned i) const { return __item_t__ (a[i], b[i]); }
__more__hb_zip_iter_t558 bool __more__ () const { return bool (a) && bool (b); }
__len__hb_zip_iter_t559 unsigned __len__ () const { return hb_min (a.len (), b.len ()); }
__next__hb_zip_iter_t560 void __next__ () { ++a; ++b; }
__forward__hb_zip_iter_t561 void __forward__ (unsigned n) { a += n; b += n; }
__prev__hb_zip_iter_t562 void __prev__ () { --a; --b; }
__rewind__hb_zip_iter_t563 void __rewind__ (unsigned n) { a -= n; b -= n; }
__end__hb_zip_iter_t564 hb_zip_iter_t __end__ () const { return hb_zip_iter_t (a.end (), b.end ()); }
565 /* Note, we should stop if ANY of the iters reaches end. As such two compare
566 * unequal if both items are unequal, NOT if either is unequal. */
operator !=hb_zip_iter_t567 bool operator != (const hb_zip_iter_t& o) const
568 { return a != o.a && b != o.b; }
569
570 private:
571 A a;
572 B b;
573 };
574 struct
575 { HB_PARTIALIZE(2);
576 template <typename A, typename B,
577 hb_requires (hb_is_iterable (A) && hb_is_iterable (B))>
578 hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>>
operator ()__anon0be8885c0808579 operator () (A&& a, B&& b) const
580 { return hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>> (hb_iter (a), hb_iter (b)); }
581 }
582 HB_FUNCOBJ (hb_zip);
583
584 /* hb_concat() */
585
586 template <typename A, typename B>
587 struct hb_concat_iter_t :
588 hb_iter_t<hb_concat_iter_t<A, B>, typename A::item_t>
589 {
hb_concat_iter_thb_concat_iter_t590 hb_concat_iter_t () {}
hb_concat_iter_thb_concat_iter_t591 hb_concat_iter_t (A& a, B& b) : a (a), b (b) {}
hb_concat_iter_thb_concat_iter_t592 hb_concat_iter_t (const A& a, const B& b) : a (a), b (b) {}
593
594
595 typedef typename A::item_t __item_t__;
596 static constexpr bool is_random_access_iterator =
597 A::is_random_access_iterator &&
598 B::is_random_access_iterator;
599 static constexpr bool is_sorted_iterator = false;
600
__item__hb_concat_iter_t601 __item_t__ __item__ () const
602 {
603 if (!a)
604 return *b;
605 return *a;
606 }
607
__item_at__hb_concat_iter_t608 __item_t__ __item_at__ (unsigned i) const
609 {
610 unsigned a_len = a.len ();
611 if (i < a_len)
612 return a[i];
613 return b[i - a_len];
614 }
615
__more__hb_concat_iter_t616 bool __more__ () const { return bool (a) || bool (b); }
617
__len__hb_concat_iter_t618 unsigned __len__ () const { return a.len () + b.len (); }
619
__next__hb_concat_iter_t620 void __next__ ()
621 {
622 if (a)
623 ++a;
624 else
625 ++b;
626 }
627
__forward__hb_concat_iter_t628 void __forward__ (unsigned n)
629 {
630 if (!n) return;
631 if (!is_random_access_iterator) {
632 while (n-- && *this) {
633 (*this)++;
634 }
635 return;
636 }
637
638 unsigned a_len = a.len ();
639 if (n > a_len) {
640 n -= a_len;
641 a.__forward__ (a_len);
642 b.__forward__ (n);
643 } else {
644 a.__forward__ (n);
645 }
646 }
647
__end__hb_concat_iter_t648 hb_concat_iter_t __end__ () const { return hb_concat_iter_t (a.end (), b.end ()); }
operator !=hb_concat_iter_t649 bool operator != (const hb_concat_iter_t& o) const
650 {
651 return a != o.a
652 || b != o.b;
653 }
654
655 private:
656 A a;
657 B b;
658 };
659 struct
660 { HB_PARTIALIZE(2);
661 template <typename A, typename B,
662 hb_requires (hb_is_iterable (A) && hb_is_iterable (B))>
663 hb_concat_iter_t<hb_iter_type<A>, hb_iter_type<B>>
operator ()__anon0be8885c0908664 operator () (A&& a, B&& b) const
665 { return hb_concat_iter_t<hb_iter_type<A>, hb_iter_type<B>> (hb_iter (a), hb_iter (b)); }
666 }
667 HB_FUNCOBJ (hb_concat);
668
669 /* hb_apply() */
670
671 template <typename Appl>
672 struct hb_apply_t
673 {
hb_apply_thb_apply_t674 hb_apply_t (Appl a) : a (a) {}
675
676 template <typename Iter,
677 hb_requires (hb_is_iterator (Iter))>
operator ()hb_apply_t678 void operator () (Iter it)
679 {
680 for (; it; ++it)
681 (void) hb_invoke (a, *it);
682 }
683
684 private:
685 Appl a;
686 };
687 struct
688 {
689 template <typename Appl> hb_apply_t<Appl>
operator ()__anon0be8885c0a08690 operator () (Appl&& a) const
691 { return hb_apply_t<Appl> (a); }
692
693 template <typename Appl> hb_apply_t<Appl&>
operator ()__anon0be8885c0a08694 operator () (Appl *a) const
695 { return hb_apply_t<Appl&> (*a); }
696 }
697 HB_FUNCOBJ (hb_apply);
698
699 /* hb_range()/hb_iota()/hb_repeat() */
700
701 template <typename T, typename S>
702 struct hb_range_iter_t :
703 hb_iter_t<hb_range_iter_t<T, S>, T>
704 {
hb_range_iter_thb_range_iter_t705 hb_range_iter_t (T start, T end_, S step) : v (start), end_ (end_for (start, end_, step)), step (step) {}
706
707 typedef T __item_t__;
708 static constexpr bool is_random_access_iterator = true;
709 static constexpr bool is_sorted_iterator = true;
__item__hb_range_iter_t710 __item_t__ __item__ () const { return hb_ridentity (v); }
__item_at__hb_range_iter_t711 __item_t__ __item_at__ (unsigned j) const { return v + j * step; }
__more__hb_range_iter_t712 bool __more__ () const { return v != end_; }
__len__hb_range_iter_t713 unsigned __len__ () const { return !step ? UINT_MAX : (end_ - v) / step; }
__next__hb_range_iter_t714 void __next__ () { v += step; }
__forward__hb_range_iter_t715 void __forward__ (unsigned n) { v += n * step; }
__prev__hb_range_iter_t716 void __prev__ () { v -= step; }
__rewind__hb_range_iter_t717 void __rewind__ (unsigned n) { v -= n * step; }
__end__hb_range_iter_t718 hb_range_iter_t __end__ () const { return hb_range_iter_t (end_, end_, step); }
operator !=hb_range_iter_t719 bool operator != (const hb_range_iter_t& o) const
720 { return v != o.v; }
721
722 private:
end_forhb_range_iter_t723 static inline T end_for (T start, T end_, S step)
724 {
725 if (!step)
726 return end_;
727 auto res = (end_ - start) % step;
728 if (!res)
729 return end_;
730 end_ += step - res;
731 return end_;
732 }
733
734 private:
735 T v;
736 T end_;
737 S step;
738 };
739 struct
740 {
741 template <typename T = unsigned> hb_range_iter_t<T, unsigned>
operator ()__anon0be8885c0b08742 operator () (T end = (unsigned) -1) const
743 { return hb_range_iter_t<T, unsigned> (0, end, 1u); }
744
745 template <typename T, typename S = unsigned> hb_range_iter_t<T, S>
operator ()__anon0be8885c0b08746 operator () (T start, T end, S step = 1u) const
747 { return hb_range_iter_t<T, S> (start, end, step); }
748 }
749 HB_FUNCOBJ (hb_range);
750
751 template <typename T, typename S>
752 struct hb_iota_iter_t :
753 hb_iter_with_fallback_t<hb_iota_iter_t<T, S>, T>
754 {
hb_iota_iter_thb_iota_iter_t755 hb_iota_iter_t (T start, S step) : v (start), step (step) {}
756
757 private:
758
759 template <typename S2 = S>
760 auto
inchb_iota_iter_t761 inc (hb_type_identity<S2> s, hb_priority<1>)
762 -> hb_void_t<decltype (hb_invoke (std::forward<S2> (s), hb_declval<T&> ()))>
763 { v = hb_invoke (std::forward<S2> (s), v); }
764
765 void
inchb_iota_iter_t766 inc (S s, hb_priority<0>)
767 { v += s; }
768
769 public:
770
771 typedef T __item_t__;
772 static constexpr bool is_random_access_iterator = true;
773 static constexpr bool is_sorted_iterator = true;
__item__hb_iota_iter_t774 __item_t__ __item__ () const { return hb_ridentity (v); }
__more__hb_iota_iter_t775 bool __more__ () const { return true; }
__len__hb_iota_iter_t776 unsigned __len__ () const { return UINT_MAX; }
__next__hb_iota_iter_t777 void __next__ () { inc (step, hb_prioritize); }
__prev__hb_iota_iter_t778 void __prev__ () { v -= step; }
__end__hb_iota_iter_t779 hb_iota_iter_t __end__ () const { return *this; }
operator !=hb_iota_iter_t780 bool operator != (const hb_iota_iter_t& o) const { return true; }
781
782 private:
783 T v;
784 S step;
785 };
786 struct
787 {
788 template <typename T = unsigned, typename S = unsigned> hb_iota_iter_t<T, S>
operator ()__anon0be8885c0c08789 operator () (T start = 0u, S step = 1u) const
790 { return hb_iota_iter_t<T, S> (start, step); }
791 }
792 HB_FUNCOBJ (hb_iota);
793
794 template <typename T>
795 struct hb_repeat_iter_t :
796 hb_iter_t<hb_repeat_iter_t<T>, T>
797 {
hb_repeat_iter_thb_repeat_iter_t798 hb_repeat_iter_t (T value) : v (value) {}
799
800 typedef T __item_t__;
801 static constexpr bool is_random_access_iterator = true;
802 static constexpr bool is_sorted_iterator = true;
__item__hb_repeat_iter_t803 __item_t__ __item__ () const { return v; }
__item_at__hb_repeat_iter_t804 __item_t__ __item_at__ (unsigned j) const { return v; }
__more__hb_repeat_iter_t805 bool __more__ () const { return true; }
__len__hb_repeat_iter_t806 unsigned __len__ () const { return UINT_MAX; }
__next__hb_repeat_iter_t807 void __next__ () {}
__forward__hb_repeat_iter_t808 void __forward__ (unsigned) {}
__prev__hb_repeat_iter_t809 void __prev__ () {}
__rewind__hb_repeat_iter_t810 void __rewind__ (unsigned) {}
__end__hb_repeat_iter_t811 hb_repeat_iter_t __end__ () const { return *this; }
operator !=hb_repeat_iter_t812 bool operator != (const hb_repeat_iter_t& o) const { return true; }
813
814 private:
815 T v;
816 };
817 struct
818 {
819 template <typename T> hb_repeat_iter_t<T>
operator ()__anon0be8885c0d08820 operator () (T value) const
821 { return hb_repeat_iter_t<T> (value); }
822 }
823 HB_FUNCOBJ (hb_repeat);
824
825 /* hb_enumerate()/hb_take() */
826
827 struct
828 {
829 template <typename Iterable,
830 typename Index = unsigned,
831 hb_requires (hb_is_iterable (Iterable))>
832 auto operator () (Iterable&& it, Index start = 0u) const HB_AUTO_RETURN
833 ( hb_zip (hb_iota (start), it) )
834 }
835 HB_FUNCOBJ (hb_enumerate);
836
837 struct
838 { HB_PARTIALIZE(2);
839 template <typename Iterable,
840 hb_requires (hb_is_iterable (Iterable))>
operator ()__anon0be8885c0f08841 auto operator () (Iterable&& it, unsigned count) const HB_AUTO_RETURN
842 ( hb_zip (hb_range (count), it) | hb_map (hb_second) )
843
844 /* Specialization arrays. */
845
846 template <typename Type> inline hb_array_t<Type>
847 operator () (hb_array_t<Type> array, unsigned count) const
848 { return array.sub_array (0, count); }
849
850 template <typename Type> inline hb_sorted_array_t<Type>
operator ()__anon0be8885c0f08851 operator () (hb_sorted_array_t<Type> array, unsigned count) const
852 { return array.sub_array (0, count); }
853 }
854 HB_FUNCOBJ (hb_take);
855
856 struct
857 { HB_PARTIALIZE(2);
858 template <typename Iter,
859 hb_requires (hb_is_iterator (Iter))>
860 auto operator () (Iter it, unsigned count) const HB_AUTO_RETURN
861 (
862 + hb_iota (it, hb_add (count))
863 | hb_map (hb_take (count))
864 | hb_take ((hb_len (it) + count - 1) / count)
865 )
866 }
867 HB_FUNCOBJ (hb_chop);
868
869 /* hb_sink() */
870
871 template <typename Sink>
872 struct hb_sink_t
873 {
hb_sink_thb_sink_t874 hb_sink_t (Sink s) : s (s) {}
875
876 template <typename Iter,
877 hb_requires (hb_is_iterator (Iter))>
operator ()hb_sink_t878 void operator () (Iter it)
879 {
880 for (; it; ++it)
881 s << *it;
882 }
883
884 private:
885 Sink s;
886 };
887 struct
888 {
889 template <typename Sink> hb_sink_t<Sink>
operator ()__anon0be8885c1108890 operator () (Sink&& s) const
891 { return hb_sink_t<Sink> (s); }
892
893 template <typename Sink> hb_sink_t<Sink&>
operator ()__anon0be8885c1108894 operator () (Sink *s) const
895 { return hb_sink_t<Sink&> (*s); }
896 }
897 HB_FUNCOBJ (hb_sink);
898
899 /* hb-drain: hb_sink to void / blackhole / /dev/null. */
900
901 struct
902 {
903 template <typename Iter,
904 hb_requires (hb_is_iterator (Iter))>
operator ()__anon0be8885c1208905 void operator () (Iter it) const
906 {
907 for (; it; ++it)
908 (void) *it;
909 }
910 }
911 HB_FUNCOBJ (hb_drain);
912
913 /* hb_unzip(): unzip and sink to two sinks. */
914
915 template <typename Sink1, typename Sink2>
916 struct hb_unzip_t
917 {
hb_unzip_thb_unzip_t918 hb_unzip_t (Sink1 s1, Sink2 s2) : s1 (s1), s2 (s2) {}
919
920 template <typename Iter,
921 hb_requires (hb_is_iterator (Iter))>
operator ()hb_unzip_t922 void operator () (Iter it)
923 {
924 for (; it; ++it)
925 {
926 const auto &v = *it;
927 s1 << v.first;
928 s2 << v.second;
929 }
930 }
931
932 private:
933 Sink1 s1;
934 Sink2 s2;
935 };
936 struct
937 {
938 template <typename Sink1, typename Sink2> hb_unzip_t<Sink1, Sink2>
operator ()__anon0be8885c1308939 operator () (Sink1&& s1, Sink2&& s2) const
940 { return hb_unzip_t<Sink1, Sink2> (s1, s2); }
941
942 template <typename Sink1, typename Sink2> hb_unzip_t<Sink1&, Sink2&>
operator ()__anon0be8885c1308943 operator () (Sink1 *s1, Sink2 *s2) const
944 { return hb_unzip_t<Sink1&, Sink2&> (*s1, *s2); }
945 }
946 HB_FUNCOBJ (hb_unzip);
947
948
949 /* hb-all, hb-any, hb-none. */
950
951 struct
952 {
953 template <typename Iterable,
954 typename Pred = decltype ((hb_identity)),
955 typename Proj = decltype ((hb_identity)),
956 hb_requires (hb_is_iterable (Iterable))>
operator ()__anon0be8885c1408957 bool operator () (Iterable&& c,
958 Pred&& p = hb_identity,
959 Proj&& f = hb_identity) const
960 {
961 for (auto it = hb_iter (c); it; ++it)
962 if (!hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
963 return false;
964 return true;
965 }
966 }
967 HB_FUNCOBJ (hb_all);
968 struct
969 {
970 template <typename Iterable,
971 typename Pred = decltype ((hb_identity)),
972 typename Proj = decltype ((hb_identity)),
973 hb_requires (hb_is_iterable (Iterable))>
operator ()__anon0be8885c1508974 bool operator () (Iterable&& c,
975 Pred&& p = hb_identity,
976 Proj&& f = hb_identity) const
977 {
978 for (auto it = hb_iter (c); it; ++it)
979 if (hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
980 return true;
981 return false;
982 }
983 }
984 HB_FUNCOBJ (hb_any);
985 struct
986 {
987 template <typename Iterable,
988 typename Pred = decltype ((hb_identity)),
989 typename Proj = decltype ((hb_identity)),
990 hb_requires (hb_is_iterable (Iterable))>
operator ()__anon0be8885c1608991 bool operator () (Iterable&& c,
992 Pred&& p = hb_identity,
993 Proj&& f = hb_identity) const
994 {
995 for (auto it = hb_iter (c); it; ++it)
996 if (hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
997 return false;
998 return true;
999 }
1000 }
1001 HB_FUNCOBJ (hb_none);
1002
1003 /*
1004 * Algorithms operating on iterators.
1005 */
1006
1007 template <typename C, typename V,
1008 hb_requires (hb_is_iterable (C))>
1009 inline void
hb_fill(C && c,const V & v)1010 hb_fill (C&& c, const V &v)
1011 {
1012 for (auto i = hb_iter (c); i; i++)
1013 *i = v;
1014 }
1015
1016 template <typename S, typename D>
1017 inline void
hb_copy(S && is,D && id)1018 hb_copy (S&& is, D&& id)
1019 {
1020 hb_iter (is) | hb_sink (id);
1021 }
1022
1023
1024 #endif /* HB_ITER_HH */
1025