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 * If iterator implementation implements operator!=, then it can be
47 * used in range-based for loop. That already happens if the iterator
48 * is random-access. Otherwise, the range-based for loop incurs
49 * one traversal to find end(), which can be avoided if written
50 * as a while-style for loop, or if iterator implements a faster
51 * __end__() method. */
52
53/*
54 * Base classes for iterators.
55 */
56
57/* Base class for all iterators. */
58template <typename iter_t, typename Item = typename iter_t::__item_t__>
59struct hb_iter_t
60{
61 typedef Item item_t;
62 constexpr unsigned get_item_size () const { return hb_static_size (Item); }
63 static constexpr bool is_iterator = true;
64 static constexpr bool is_random_access_iterator = false;
65 static constexpr bool is_sorted_iterator = false;
66 static constexpr bool has_fast_len = false; // Should be checked in combination with is_random_access_iterator.
67
68 private:
69 /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
70 const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
71 iter_t* thiz () { return static_cast< iter_t *> (this); }
72 public:
73
74 /* Operators. */
75 iter_t iter () const { return *thiz(); }
76 iter_t operator + () const { return *thiz(); }
77 iter_t _begin () const { return *thiz(); }
78 iter_t begin () const { return _begin (); }
79 iter_t _end () const { return thiz()->__end__ (); }
80 iter_t end () const { return _end (); }
81 explicit operator bool () const { return thiz()->__more__ (); }
82 unsigned len () const { return thiz()->__len__ (); }
83 /* The following can only be enabled if item_t is reference type. Otherwise
84 * it will be returning pointer to temporary rvalue. */
85 template <typename T = item_t,
86 hb_enable_if (std::is_reference<T>::value)>
87 hb_remove_reference<item_t>* operator -> () const { return std::addressof (**thiz()); }
88 item_t operator * () const { return thiz()->__item__ (); }
89 item_t operator * () { return thiz()->__item__ (); }
90 item_t operator [] (unsigned i) const { return thiz()->__item_at__ (i); }
91 item_t operator [] (unsigned i) { return thiz()->__item_at__ (i); }
92 iter_t& operator += (unsigned count) & { thiz()->__forward__ (count); return *thiz(); }
93 iter_t operator += (unsigned count) && { thiz()->__forward__ (count); return *thiz(); }
94 iter_t& operator ++ () & { thiz()->__next__ (); return *thiz(); }
95 iter_t operator ++ () && { thiz()->__next__ (); return *thiz(); }
96 iter_t& operator -= (unsigned count) & { thiz()->__rewind__ (count); return *thiz(); }
97 iter_t operator -= (unsigned count) && { thiz()->__rewind__ (count); return *thiz(); }
98 iter_t& operator -- () & { thiz()->__prev__ (); return *thiz(); }
99 iter_t operator -- () && { thiz()->__prev__ (); return *thiz(); }
100 iter_t operator + (unsigned count) const { auto c = thiz()->iter (); c += count; return c; }
101 friend iter_t operator + (unsigned count, const iter_t &it) { return it + count; }
102 iter_t operator ++ (int) { iter_t c (*thiz()); ++*thiz(); return c; }
103 iter_t operator - (unsigned count) const { auto c = thiz()->iter (); c -= count; return c; }
104 iter_t operator -- (int) { iter_t c (*thiz()); --*thiz(); return c; }
105 template <typename T>
106 iter_t& operator >> (T &v) & { v = **thiz(); ++*thiz(); return *thiz(); }
107 template <typename T>
108 iter_t operator >> (T &v) && { v = **thiz(); ++*thiz(); return *thiz(); }
109 template <typename T>
110 iter_t& operator << (const T v) & { **thiz() = v; ++*thiz(); return *thiz(); }
111 template <typename T>
112 iter_t operator << (const T v) && { **thiz() = v; ++*thiz(); return *thiz(); }
113
114 protected:
115 hb_iter_t () = default;
116 hb_iter_t (const hb_iter_t &o HB_UNUSED) = default;
117 hb_iter_t (hb_iter_t &&o HB_UNUSED) = default;
118 hb_iter_t& operator = (const hb_iter_t &o HB_UNUSED) = default;
119 hb_iter_t& operator = (hb_iter_t &&o HB_UNUSED) = default;
120};
121
122#define HB_ITER_USING(Name) \
123 using item_t = typename Name::item_t; \
124 using Name::_begin; \
125 using Name::begin; \
126 using Name::_end; \
127 using Name::end; \
128 using Name::get_item_size; \
129 using Name::is_iterator; \
130 using Name::iter; \
131 using Name::operator bool; \
132 using Name::len; \
133 using Name::operator ->; \
134 using Name::operator *; \
135 using Name::operator []; \
136 using Name::operator +=; \
137 using Name::operator ++; \
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 static_assert (true, "")
145
146/* Returns iterator / item type of a type. */
147template <typename Iterable>
148using hb_iter_type = decltype (hb_deref (hb_declval (Iterable)).iter ());
149template <typename Iterable>
150using hb_item_type = decltype (*hb_deref (hb_declval (Iterable)).iter ());
151
152
153template <typename> struct hb_array_t;
154template <typename> struct hb_sorted_array_t;
155
156struct
157{
158 template <typename T> hb_iter_type<T>
159 operator () (T&& c) const
160 { return hb_deref (std::forward<T> (c)).iter (); }
161
162 /* Specialization for C arrays. */
163
164 template <typename Type> inline hb_array_t<Type>
165 operator () (Type *array, unsigned int length) const
166 { return hb_array_t<Type> (array, length); }
167
168 template <typename Type, unsigned int length> hb_array_t<Type>
169 operator () (Type (&array)[length]) const
170 { return hb_array_t<Type> (array, length); }
171
172}
173HB_FUNCOBJ (hb_iter);
174struct
175{
176 template <typename T> auto
177 impl (T&& c, hb_priority<1>) const HB_RETURN (unsigned, c.len ())
178
179 template <typename T> auto
180 impl (T&& c, hb_priority<0>) const HB_RETURN (unsigned, c.len)
181
182 public:
183
184 template <typename T> auto
185 operator () (T&& c) const HB_RETURN (unsigned, impl (std::forward<T> (c), hb_prioritize))
186}
187HB_FUNCOBJ (hb_len);
188
189/* Mixin to fill in what the subclass doesn't provide. */
190template <typename iter_t, typename item_t = typename iter_t::__item_t__>
191struct hb_iter_fallback_mixin_t
192{
193 private:
194 /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
195 const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
196 iter_t* thiz () { return static_cast< iter_t *> (this); }
197 public:
198
199 /* Access: Implement __item__(), or __item_at__() if random-access. */
200 item_t __item__ () const { return (*thiz())[0]; }
201 item_t __item_at__ (unsigned i) const { return *(*thiz() + i); }
202
203 /* Termination: Implement __more__(), or __len__() if random-access. */
204 bool __more__ () const { return bool (thiz()->len ()); }
205 unsigned __len__ () const
206 { iter_t c (*thiz()); unsigned l = 0; while (c) { c++; l++; } return l; }
207
208 /* Advancing: Implement __next__(), or __forward__() if random-access. */
209 void __next__ () { *thiz() += 1; }
210 void __forward__ (unsigned n) { while (*thiz() && n--) ++*thiz(); }
211
212 /* Rewinding: Implement __prev__() or __rewind__() if bidirectional. */
213 void __prev__ () { *thiz() -= 1; }
214 void __rewind__ (unsigned n) { while (*thiz() && n--) --*thiz(); }
215
216 /* Range-based for: Implement __end__() if can be done faster,
217 * and operator!=. */
218 iter_t __end__ () const
219 {
220 if (thiz()->is_random_access_iterator)
221 return *thiz() + thiz()->len ();
222 /* Above expression loops twice. Following loops once. */
223 auto it = *thiz();
224 while (it) ++it;
225 return it;
226 }
227
228 protected:
229 hb_iter_fallback_mixin_t () = default;
230 hb_iter_fallback_mixin_t (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default;
231 hb_iter_fallback_mixin_t (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default;
232 hb_iter_fallback_mixin_t& operator = (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default;
233 hb_iter_fallback_mixin_t& operator = (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default;
234};
235
236template <typename iter_t, typename item_t = typename iter_t::__item_t__>
237struct hb_iter_with_fallback_t :
238 hb_iter_t<iter_t, item_t>,
239 hb_iter_fallback_mixin_t<iter_t, item_t>
240{
241 protected:
242 hb_iter_with_fallback_t () = default;
243 hb_iter_with_fallback_t (const hb_iter_with_fallback_t &o HB_UNUSED) = default;
244 hb_iter_with_fallback_t (hb_iter_with_fallback_t &&o HB_UNUSED) = default;
245 hb_iter_with_fallback_t& operator = (const hb_iter_with_fallback_t &o HB_UNUSED) = default;
246 hb_iter_with_fallback_t& operator = (hb_iter_with_fallback_t &&o HB_UNUSED) = default;
247};
248
249/*
250 * Meta-programming predicates.
251 */
252
253/* hb_is_iterator() / hb_is_iterator_of() */
254
255template<typename Iter, typename Item>
256struct hb_is_iterator_of
257{
258 template <typename Item2 = Item>
259 static hb_true_type impl (hb_priority<2>, hb_iter_t<Iter, hb_type_identity<Item2>> *);
260 static hb_false_type impl (hb_priority<0>, const void *);
261
262 public:
263 static constexpr bool value = decltype (impl (hb_prioritize, hb_declval (Iter*)))::value;
264};
265#define hb_is_iterator_of(Iter, Item) hb_is_iterator_of<Iter, Item>::value
266#define hb_is_iterator(Iter) hb_is_iterator_of (Iter, typename Iter::item_t)
267#define hb_is_sorted_iterator_of(Iter, Item) (hb_is_iterator_of<Iter, Item>::value && Iter::is_sorted_iterator)
268#define hb_is_sorted_iterator(Iter) hb_is_sorted_iterator_of (Iter, typename Iter::item_t)
269
270/* hb_is_iterable() */
271
272template <typename T>
273struct hb_is_iterable
274{
275 private:
276
277 template <typename U>
278 static auto impl (hb_priority<1>) -> decltype (hb_declval (U).iter (), hb_true_type ());
279
280 template <typename>
281 static hb_false_type impl (hb_priority<0>);
282
283 public:
284 static constexpr bool value = decltype (impl<T> (hb_prioritize))::value;
285};
286#define hb_is_iterable(Iterable) hb_is_iterable<Iterable>::value
287
288/* hb_is_source_of() / hb_is_sink_of() */
289
290template<typename Iter, typename Item>
291struct hb_is_source_of
292{
293 private:
294 template <typename Iter2 = Iter,
295 hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<const Item>))>
296 static hb_true_type impl (hb_priority<2>);
297 template <typename Iter2 = Iter>
298 static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) >> hb_declval (Item &), hb_true_type ());
299 static hb_false_type impl (hb_priority<0>);
300
301 public:
302 static constexpr bool value = decltype (impl (hb_prioritize))::value;
303};
304#define hb_is_source_of(Iter, Item) hb_is_source_of<Iter, Item>::value
305
306template<typename Iter, typename Item>
307struct hb_is_sink_of
308{
309 private:
310 template <typename Iter2 = Iter,
311 hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<Item>))>
312 static hb_true_type impl (hb_priority<2>);
313 template <typename Iter2 = Iter>
314 static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) << hb_declval (Item), hb_true_type ());
315 static hb_false_type impl (hb_priority<0>);
316
317 public:
318 static constexpr bool value = decltype (impl (hb_prioritize))::value;
319};
320#define hb_is_sink_of(Iter, Item) hb_is_sink_of<Iter, Item>::value
321
322/* This is commonly used, so define: */
323#define hb_is_sorted_source_of(Iter, Item) \
324 (hb_is_source_of(Iter, Item) && Iter::is_sorted_iterator)
325
326
327/* Range-based 'for' for iterables. */
328
329template <typename Iterable,
330 hb_requires (hb_is_iterable (Iterable))>
331static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ())
332
333template <typename Iterable,
334 hb_requires (hb_is_iterable (Iterable))>
335static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ())
336
337/* begin()/end() are NOT looked up non-ADL. So each namespace must declare them.
338 * Do it for namespace OT. */
339namespace OT {
340
341template <typename Iterable,
342 hb_requires (hb_is_iterable (Iterable))>
343static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ())
344
345template <typename Iterable,
346 hb_requires (hb_is_iterable (Iterable))>
347static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ())
348
349}
350
351
352/*
353 * Adaptors, combiners, etc.
354 */
355
356template <typename Lhs, typename Rhs,
357 hb_requires (hb_is_iterator (Lhs))>
358static inline auto
359operator | (Lhs&& lhs, Rhs&& rhs) HB_AUTO_RETURN (std::forward<Rhs> (rhs) (std::forward<Lhs> (lhs)))
360
361/* hb_map(), hb_filter(), hb_reduce() */
362
363enum class hb_function_sortedness_t {
364 NOT_SORTED,
365 RETAINS_SORTING,
366 SORTED,
367};
368
369template <typename Iter, typename Proj, hb_function_sortedness_t Sorted,
370 hb_requires (hb_is_iterator (Iter))>
371struct hb_map_iter_t :
372 hb_iter_t<hb_map_iter_t<Iter, Proj, Sorted>,
373 decltype (hb_get (hb_declval (Proj), *hb_declval (Iter)))>
374{
375 hb_map_iter_t (const Iter& it, Proj f_) : it (it), f (f_) {}
376
377 typedef decltype (hb_get (hb_declval (Proj), *hb_declval (Iter))) __item_t__;
378 static constexpr bool is_random_access_iterator = Iter::is_random_access_iterator;
379 static constexpr bool is_sorted_iterator =
380 Sorted == hb_function_sortedness_t::SORTED ? true :
381 Sorted == hb_function_sortedness_t::RETAINS_SORTING ? Iter::is_sorted_iterator :
382 false;
383 __item_t__ __item__ () const { return hb_get (f.get (), *it); }
384 __item_t__ __item_at__ (unsigned i) const { return hb_get (f.get (), it[i]); }
385 bool __more__ () const { return bool (it); }
386 unsigned __len__ () const { return it.len (); }
387 void __next__ () { ++it; }
388 void __forward__ (unsigned n) { it += n; }
389 void __prev__ () { --it; }
390 void __rewind__ (unsigned n) { it -= n; }
391 hb_map_iter_t __end__ () const { return hb_map_iter_t (it._end (), f); }
392 bool operator != (const hb_map_iter_t& o) const
393 { return it != o.it; }
394
395 private:
396 Iter it;
397 mutable hb_reference_wrapper<Proj> f;
398};
399
400template <typename Proj, hb_function_sortedness_t Sorted>
401struct hb_map_iter_factory_t
402{
403 hb_map_iter_factory_t (Proj f) : f (f) {}
404
405 template <typename Iter,
406 hb_requires (hb_is_iterator (Iter))>
407 hb_map_iter_t<Iter, Proj, Sorted>
408 operator () (Iter it)
409 { return hb_map_iter_t<Iter, Proj, Sorted> (it, f); }
410
411 private:
412 Proj f;
413};
414struct
415{
416 template <typename Proj>
417 hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED>
418 operator () (Proj&& f) const
419 { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED> (f); }
420}
421HB_FUNCOBJ (hb_map);
422struct
423{
424 template <typename Proj>
425 hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING>
426 operator () (Proj&& f) const
427 { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING> (f); }
428}
429HB_FUNCOBJ (hb_map_retains_sorting);
430struct
431{
432 template <typename Proj>
433 hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED>
434 operator () (Proj&& f) const
435 { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED> (f); }
436}
437HB_FUNCOBJ (hb_map_sorted);
438
439template <typename Iter, typename Pred, typename Proj,
440 hb_requires (hb_is_iterator (Iter))>
441struct hb_filter_iter_t :
442 hb_iter_with_fallback_t<hb_filter_iter_t<Iter, Pred, Proj>,
443 typename Iter::item_t>
444{
445 hb_filter_iter_t (const Iter& it_, Pred p_, Proj f_) : it (it_), p (p_), f (f_)
446 { while (it && !hb_has (p.get (), hb_get (f.get (), *it))) ++it; }
447
448 typedef typename Iter::item_t __item_t__;
449 static constexpr bool is_sorted_iterator = Iter::is_sorted_iterator;
450 __item_t__ __item__ () const { return *it; }
451 bool __more__ () const { return bool (it); }
452 void __next__ () { do ++it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); }
453 void __prev__ () { do --it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); }
454 hb_filter_iter_t __end__ () const { return hb_filter_iter_t (it._end (), p, f); }
455 bool operator != (const hb_filter_iter_t& o) const
456 { return it != o.it; }
457
458 private:
459 Iter it;
460 mutable hb_reference_wrapper<Pred> p;
461 mutable hb_reference_wrapper<Proj> f;
462};
463template <typename Pred, typename Proj>
464struct hb_filter_iter_factory_t
465{
466 hb_filter_iter_factory_t (Pred p, Proj f) : p (p), f (f) {}
467
468 template <typename Iter,
469 hb_requires (hb_is_iterator (Iter))>
470 hb_filter_iter_t<Iter, Pred, Proj>
471 operator () (Iter it)
472 { return hb_filter_iter_t<Iter, Pred, Proj> (it, p, f); }
473
474 private:
475 Pred p;
476 Proj f;
477};
478struct
479{
480 template <typename Pred = decltype ((hb_identity)),
481 typename Proj = decltype ((hb_identity))>
482 hb_filter_iter_factory_t<Pred, Proj>
483 operator () (Pred&& p = hb_identity, Proj&& f = hb_identity) const
484 { return hb_filter_iter_factory_t<Pred, Proj> (p, f); }
485}
486HB_FUNCOBJ (hb_filter);
487
488template <typename Redu, typename InitT>
489struct hb_reduce_t
490{
491 hb_reduce_t (Redu r, InitT init_value) : r (r), init_value (init_value) {}
492
493 template <typename Iter,
494 hb_requires (hb_is_iterator (Iter)),
495 typename AccuT = hb_decay<decltype (hb_declval (Redu) (hb_declval (InitT), hb_declval (typename Iter::item_t)))>>
496 AccuT
497 operator () (Iter it)
498 {
499 AccuT value = init_value;
500 for (; it; ++it)
501 value = r (value, *it);
502 return value;
503 }
504
505 private:
506 Redu r;
507 InitT init_value;
508};
509struct
510{
511 template <typename Redu, typename InitT>
512 hb_reduce_t<Redu, InitT>
513 operator () (Redu&& r, InitT init_value) const
514 { return hb_reduce_t<Redu, InitT> (r, init_value); }
515}
516HB_FUNCOBJ (hb_reduce);
517
518
519/* hb_zip() */
520
521template <typename A, typename B>
522struct hb_zip_iter_t :
523 hb_iter_t<hb_zip_iter_t<A, B>,
524 hb_pair_t<typename A::item_t, typename B::item_t>>
525{
526 hb_zip_iter_t () {}
527 hb_zip_iter_t (const A& a, const B& b) : a (a), b (b) {}
528
529 typedef hb_pair_t<typename A::item_t, typename B::item_t> __item_t__;
530 static constexpr bool is_random_access_iterator =
531 A::is_random_access_iterator &&
532 B::is_random_access_iterator;
533 /* Note. The following categorization is only valid if A is strictly sorted,
534 * ie. does NOT have duplicates. Previously I tried to categorize sortedness
535 * more granularly, see commits:
536 *
537 * 513762849a683914fc266a17ddf38f133cccf072
538 * 4d3cf2adb669c345cc43832d11689271995e160a
539 *
540 * However, that was not enough, since hb_sorted_array_t, hb_sorted_vector_t,
541 * SortedArrayOf, etc all needed to be updated to add more variants. At that
542 * point I saw it not worth the effort, and instead we now deem all sorted
543 * collections as essentially strictly-sorted for the purposes of zip.
544 *
545 * The above assumption is not as bad as it sounds. Our "sorted" comes with
546 * no guarantees. It's just a contract, put in place to help you remember,
547 * and think about, whether an iterator you receive is expected to be
548 * sorted or not. As such, it's not perfect by definition, and should not
549 * be treated so. The inaccuracy here just errs in the direction of being
550 * more permissive, so your code compiles instead of erring on the side of
551 * marking your zipped iterator unsorted in which case your code won't
552 * compile.
553 *
554 * This semantical limitation does NOT affect logic in any other place I
555 * know of as of this writing.
556 */
557 static constexpr bool is_sorted_iterator = A::is_sorted_iterator;
558
559 __item_t__ __item__ () const { return __item_t__ (*a, *b); }
560 __item_t__ __item_at__ (unsigned i) const { return __item_t__ (a[i], b[i]); }
561 bool __more__ () const { return bool (a) && bool (b); }
562 unsigned __len__ () const { return hb_min (a.len (), b.len ()); }
563 void __next__ () { ++a; ++b; }
564 void __forward__ (unsigned n) { a += n; b += n; }
565 void __prev__ () { --a; --b; }
566 void __rewind__ (unsigned n) { a -= n; b -= n; }
567 hb_zip_iter_t __end__ () const { return hb_zip_iter_t (a._end (), b._end ()); }
568 /* Note, we should stop if ANY of the iters reaches end. As such two compare
569 * unequal if both items are unequal, NOT if either is unequal. */
570 bool operator != (const hb_zip_iter_t& o) const
571 { return a != o.a && b != o.b; }
572
573 private:
574 A a;
575 B b;
576};
577struct
578{ HB_PARTIALIZE(2);
579 template <typename A, typename B,
580 hb_requires (hb_is_iterable (A) && hb_is_iterable (B))>
581 hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>>
582 operator () (A&& a, B&& b) const
583 { return hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>> (hb_iter (a), hb_iter (b)); }
584}
585HB_FUNCOBJ (hb_zip);
586
587/* hb_concat() */
588
589template <typename A, typename B>
590struct hb_concat_iter_t :
591 hb_iter_t<hb_concat_iter_t<A, B>, typename A::item_t>
592{
593 hb_concat_iter_t () {}
594 hb_concat_iter_t (A& a, B& b) : a (a), b (b) {}
595 hb_concat_iter_t (const A& a, const B& b) : a (a), b (b) {}
596
597
598 typedef typename A::item_t __item_t__;
599 static constexpr bool is_random_access_iterator =
600 A::is_random_access_iterator &&
601 B::is_random_access_iterator;
602 static constexpr bool is_sorted_iterator = false;
603
604 __item_t__ __item__ () const
605 {
606 if (!a)
607 return *b;
608 return *a;
609 }
610
611 __item_t__ __item_at__ (unsigned i) const
612 {
613 unsigned a_len = a.len ();
614 if (i < a_len)
615 return a[i];
616 return b[i - a_len];
617 }
618
619 bool __more__ () const { return bool (a) || bool (b); }
620
621 unsigned __len__ () const { return a.len () + b.len (); }
622
623 void __next__ ()
624 {
625 if (a)
626 ++a;
627 else
628 ++b;
629 }
630
631 void __forward__ (unsigned n)
632 {
633 if (!n) return;
634 if (!is_random_access_iterator) {
635 while (n-- && *this) {
636 (*this)++;
637 }
638 return;
639 }
640
641 unsigned a_len = a.len ();
642 if (n > a_len) {
643 n -= a_len;
644 a.__forward__ (a_len);
645 b.__forward__ (n);
646 } else {
647 a.__forward__ (n);
648 }
649 }
650
651 hb_concat_iter_t __end__ () const { return hb_concat_iter_t (a._end (), b._end ()); }
652 bool operator != (const hb_concat_iter_t& o) const
653 {
654 return a != o.a
655 || b != o.b;
656 }
657
658 private:
659 A a;
660 B b;
661};
662struct
663{ HB_PARTIALIZE(2);
664 template <typename A, typename B,
665 hb_requires (hb_is_iterable (A) && hb_is_iterable (B))>
666 hb_concat_iter_t<hb_iter_type<A>, hb_iter_type<B>>
667 operator () (A&& a, B&& b) const
668 { return hb_concat_iter_t<hb_iter_type<A>, hb_iter_type<B>> (hb_iter (a), hb_iter (b)); }
669}
670HB_FUNCOBJ (hb_concat);
671
672/* hb_apply() */
673
674template <typename Appl>
675struct hb_apply_t
676{
677 hb_apply_t (Appl a) : a (a) {}
678
679 template <typename Iter,
680 hb_requires (hb_is_iterator (Iter))>
681 void operator () (Iter it)
682 {
683 for (; it; ++it)
684 (void) hb_invoke (a, *it);
685 }
686
687 private:
688 Appl a;
689};
690struct
691{
692 template <typename Appl> hb_apply_t<Appl>
693 operator () (Appl&& a) const
694 { return hb_apply_t<Appl> (a); }
695
696 template <typename Appl> hb_apply_t<Appl&>
697 operator () (Appl *a) const
698 { return hb_apply_t<Appl&> (*a); }
699}
700HB_FUNCOBJ (hb_apply);
701
702/* hb_range()/hb_iota()/hb_repeat() */
703
704template <typename T, typename S>
705struct hb_range_iter_t :
706 hb_iter_t<hb_range_iter_t<T, S>, T>
707{
708 hb_range_iter_t (T start, T end_, S step) : v (start), end_ (end_for (start, end_, step)), step (step) {}
709
710 typedef T __item_t__;
711 static constexpr bool is_random_access_iterator = true;
712 static constexpr bool is_sorted_iterator = true;
713 __item_t__ __item__ () const { return hb_ridentity (v); }
714 __item_t__ __item_at__ (unsigned j) const { return v + j * step; }
715 bool __more__ () const { return v != end_; }
716 unsigned __len__ () const { return !step ? UINT_MAX : (end_ - v) / step; }
717 void __next__ () { v += step; }
718 void __forward__ (unsigned n) { v += n * step; }
719 void __prev__ () { v -= step; }
720 void __rewind__ (unsigned n) { v -= n * step; }
721 hb_range_iter_t __end__ () const { return hb_range_iter_t (end_, end_, step); }
722 bool operator != (const hb_range_iter_t& o) const
723 { return v != o.v; }
724
725 private:
726 static inline T end_for (T start, T end_, S step)
727 {
728 if (!step)
729 return end_;
730 auto res = (end_ - start) % step;
731 if (!res)
732 return end_;
733 end_ += step - res;
734 return end_;
735 }
736
737 private:
738 T v;
739 T end_;
740 S step;
741};
742struct
743{
744 template <typename T = unsigned> hb_range_iter_t<T, unsigned>
745 operator () (T end = (unsigned) -1) const
746 { return hb_range_iter_t<T, unsigned> (0, end, 1u); }
747
748 template <typename T, typename S = unsigned> hb_range_iter_t<T, S>
749 operator () (T start, T end, S step = 1u) const
750 { return hb_range_iter_t<T, S> (start, end, step); }
751}
752HB_FUNCOBJ (hb_range);
753
754template <typename T, typename S>
755struct hb_iota_iter_t :
756 hb_iter_with_fallback_t<hb_iota_iter_t<T, S>, T>
757{
758 hb_iota_iter_t (T start, S step) : v (start), step (step) {}
759
760 private:
761
762 template <typename S2 = S>
763 auto
764 inc (hb_type_identity<S2> s, hb_priority<1>)
765 -> hb_void_t<decltype (hb_invoke (std::forward<S2> (s), hb_declval<T&> ()))>
766 { v = hb_invoke (std::forward<S2> (s), v); }
767
768 void
769 inc (S s, hb_priority<0>)
770 { v += s; }
771
772 public:
773
774 typedef T __item_t__;
775 static constexpr bool is_random_access_iterator = true;
776 static constexpr bool is_sorted_iterator = true;
777 __item_t__ __item__ () const { return hb_ridentity (v); }
778 bool __more__ () const { return true; }
779 unsigned __len__ () const { return UINT_MAX; }
780 void __next__ () { inc (step, hb_prioritize); }
781 void __prev__ () { v -= step; }
782 hb_iota_iter_t __end__ () const { return *this; }
783 bool operator != (const hb_iota_iter_t& o) const { return true; }
784
785 private:
786 T v;
787 S step;
788};
789struct
790{
791 template <typename T = unsigned, typename S = unsigned> hb_iota_iter_t<T, S>
792 operator () (T start = 0u, S step = 1u) const
793 { return hb_iota_iter_t<T, S> (start, step); }
794}
795HB_FUNCOBJ (hb_iota);
796
797template <typename T>
798struct hb_repeat_iter_t :
799 hb_iter_t<hb_repeat_iter_t<T>, T>
800{
801 hb_repeat_iter_t (T value) : v (value) {}
802
803 typedef T __item_t__;
804 static constexpr bool is_random_access_iterator = true;
805 static constexpr bool is_sorted_iterator = true;
806 __item_t__ __item__ () const { return v; }
807 __item_t__ __item_at__ (unsigned j) const { return v; }
808 bool __more__ () const { return true; }
809 unsigned __len__ () const { return UINT_MAX; }
810 void __next__ () {}
811 void __forward__ (unsigned) {}
812 void __prev__ () {}
813 void __rewind__ (unsigned) {}
814 hb_repeat_iter_t __end__ () const { return *this; }
815 bool operator != (const hb_repeat_iter_t& o) const { return true; }
816
817 private:
818 T v;
819};
820struct
821{
822 template <typename T> hb_repeat_iter_t<T>
823 operator () (T value) const
824 { return hb_repeat_iter_t<T> (value); }
825}
826HB_FUNCOBJ (hb_repeat);
827
828/* hb_enumerate()/hb_take() */
829
830struct
831{
832 template <typename Iterable,
833 typename Index = unsigned,
834 hb_requires (hb_is_iterable (Iterable))>
835 auto operator () (Iterable&& it, Index start = 0u) const HB_AUTO_RETURN
836 ( hb_zip (hb_iota (start), it) )
837}
838HB_FUNCOBJ (hb_enumerate);
839
840struct
841{ HB_PARTIALIZE(2);
842 template <typename Iterable,
843 hb_requires (hb_is_iterable (Iterable))>
844 auto operator () (Iterable&& it, unsigned count) const HB_AUTO_RETURN
845 ( hb_zip (hb_range (count), it) | hb_map_retains_sorting (hb_second) )
846
847 /* Specialization arrays. */
848
849 template <typename Type> inline hb_array_t<Type>
850 operator () (hb_array_t<Type> array, unsigned count) const
851 { return array.sub_array (0, count); }
852
853 template <typename Type> inline hb_sorted_array_t<Type>
854 operator () (hb_sorted_array_t<Type> array, unsigned count) const
855 { return array.sub_array (0, count); }
856}
857HB_FUNCOBJ (hb_take);
858
859struct
860{ HB_PARTIALIZE(2);
861 template <typename Iter,
862 hb_requires (hb_is_iterator (Iter))>
863 auto operator () (Iter it, unsigned count) const HB_AUTO_RETURN
864 (
865 + hb_iota (it, hb_add (count))
866 | hb_map (hb_take (count))
867 | hb_take ((hb_len (it) + count - 1) / count)
868 )
869}
870HB_FUNCOBJ (hb_chop);
871
872/* hb_sink() */
873
874template <typename Sink>
875struct hb_sink_t
876{
877 hb_sink_t (Sink s) : s (s) {}
878
879 template <typename Iter,
880 hb_requires (hb_is_iterator (Iter))>
881 void operator () (Iter it)
882 {
883 for (; it; ++it)
884 s << *it;
885 }
886
887 private:
888 Sink s;
889};
890struct
891{
892 template <typename Sink> hb_sink_t<Sink>
893 operator () (Sink&& s) const
894 { return hb_sink_t<Sink> (s); }
895
896 template <typename Sink> hb_sink_t<Sink&>
897 operator () (Sink *s) const
898 { return hb_sink_t<Sink&> (*s); }
899}
900HB_FUNCOBJ (hb_sink);
901
902/* hb-drain: hb_sink to void / blackhole / /dev/null. */
903
904struct
905{
906 template <typename Iter,
907 hb_requires (hb_is_iterator (Iter))>
908 void operator () (Iter it) const
909 {
910 for (; it; ++it)
911 (void) *it;
912 }
913}
914HB_FUNCOBJ (hb_drain);
915
916/* hb_unzip(): unzip and sink to two sinks. */
917
918template <typename Sink1, typename Sink2>
919struct hb_unzip_t
920{
921 hb_unzip_t (Sink1 s1, Sink2 s2) : s1 (s1), s2 (s2) {}
922
923 template <typename Iter,
924 hb_requires (hb_is_iterator (Iter))>
925 void operator () (Iter it)
926 {
927 for (; it; ++it)
928 {
929 const auto &v = *it;
930 s1 << v.first;
931 s2 << v.second;
932 }
933 }
934
935 private:
936 Sink1 s1;
937 Sink2 s2;
938};
939struct
940{
941 template <typename Sink1, typename Sink2> hb_unzip_t<Sink1, Sink2>
942 operator () (Sink1&& s1, Sink2&& s2) const
943 { return hb_unzip_t<Sink1, Sink2> (s1, s2); }
944
945 template <typename Sink1, typename Sink2> hb_unzip_t<Sink1&, Sink2&>
946 operator () (Sink1 *s1, Sink2 *s2) const
947 { return hb_unzip_t<Sink1&, Sink2&> (*s1, *s2); }
948}
949HB_FUNCOBJ (hb_unzip);
950
951
952/* hb-all, hb-any, hb-none. */
953
954struct
955{
956 template <typename Iterable,
957 typename Pred = decltype ((hb_identity)),
958 typename Proj = decltype ((hb_identity)),
959 hb_requires (hb_is_iterable (Iterable))>
960 bool operator () (Iterable&& c,
961 Pred&& p = hb_identity,
962 Proj&& f = hb_identity) const
963 {
964 for (auto it = hb_iter (c); it; ++it)
965 if (!hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
966 return false;
967 return true;
968 }
969}
970HB_FUNCOBJ (hb_all);
971struct
972{
973 template <typename Iterable,
974 typename Pred = decltype ((hb_identity)),
975 typename Proj = decltype ((hb_identity)),
976 hb_requires (hb_is_iterable (Iterable))>
977 bool operator () (Iterable&& c,
978 Pred&& p = hb_identity,
979 Proj&& f = hb_identity) const
980 {
981 for (auto it = hb_iter (c); it; ++it)
982 if (hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
983 return true;
984 return false;
985 }
986}
987HB_FUNCOBJ (hb_any);
988struct
989{
990 template <typename Iterable,
991 typename Pred = decltype ((hb_identity)),
992 typename Proj = decltype ((hb_identity)),
993 hb_requires (hb_is_iterable (Iterable))>
994 bool operator () (Iterable&& c,
995 Pred&& p = hb_identity,
996 Proj&& f = hb_identity) const
997 {
998 for (auto it = hb_iter (c); it; ++it)
999 if (hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
1000 return false;
1001 return true;
1002 }
1003}
1004HB_FUNCOBJ (hb_none);
1005
1006/*
1007 * Algorithms operating on iterators.
1008 */
1009
1010template <typename C, typename V,
1011 hb_requires (hb_is_iterable (C))>
1012inline void
1013hb_fill (C&& c, const V &v)
1014{
1015 for (auto i = hb_iter (c); i; i++)
1016 *i = v;
1017}
1018
1019template <typename S, typename D>
1020inline void
1021hb_copy (S&& is, D&& id)
1022{
1023 hb_iter (is) | hb_sink (id);
1024}
1025
1026
1027#endif /* HB_ITER_HH */
1028