Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/harfbuzz/src/hb-iter.hh @ 2:b50eed0cc0ef upstream

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