diff options
Diffstat (limited to 'Build/source/libs/harfbuzz/harfbuzz-src/src/hb-iter.hh')
| -rw-r--r-- | Build/source/libs/harfbuzz/harfbuzz-src/src/hb-iter.hh | 801 |
1 files changed, 740 insertions, 61 deletions
diff --git a/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-iter.hh b/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-iter.hh index c4ab26dc063..5df433375c8 100644 --- a/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-iter.hh +++ b/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-iter.hh @@ -1,5 +1,6 @@ /* * Copyright © 2018 Google, Inc. + * Copyright © 2019 Facebook, Inc. * * This is part of HarfBuzz, a text shaping library. * @@ -22,13 +23,15 @@ * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. * * Google Author(s): Behdad Esfahbod + * Facebook Author(s): Behdad Esfahbod */ #ifndef HB_ITER_HH #define HB_ITER_HH #include "hb.hh" -#include "hb-null.hh" +#include "hb-algs.hh" +#include "hb-meta.hh" /* Unified iterator object. @@ -39,16 +42,32 @@ * copied by value. If the collection / object being iterated on * is writable, then the iterator returns lvalues, otherwise it * returns rvalues. + * + * TODO Document more. + * + * If iterator implementation implements operator!=, then can be + * used in range-based for loop. That comes free if the iterator + * is random-access. Otherwise, the range-based for loop incurs + * one traversal to find end(), which can be avoided if written + * as a while-style for loop, or if iterator implements a faster + * __end__() method. + * TODO When opting in for C++17, address this by changing return + * type of .end()? + */ + +/* + * Base classes for iterators. */ /* Base class for all iterators. */ -template <typename Iter, typename Item = typename Iter::__item_type__> +template <typename iter_t, typename Item = typename iter_t::__item_t__> struct hb_iter_t { - typedef Iter iter_t; - typedef iter_t const_iter_t; typedef Item item_t; static constexpr unsigned item_size = hb_static_size (Item); + static constexpr bool is_iterator = true; + static constexpr bool is_random_access_iterator = false; + static constexpr bool is_sorted_iterator = false; private: /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */ @@ -56,53 +75,110 @@ struct hb_iter_t iter_t* thiz () { return static_cast< iter_t *> (this); } public: - /* Operators. */ - operator iter_t () { return iter(); } - explicit_operator bool () const { return more (); } - item_t& operator * () const { return item (); } - item_t& operator [] (signed i) const { return item_at ((unsigned) i); } - iter_t& operator += (unsigned count) { forward (count); return *thiz(); } - iter_t& operator ++ () { next (); return *thiz(); } - iter_t& operator -= (unsigned count) { rewind (count); return *thiz(); } - iter_t& operator -- () { prev (); return *thiz(); } - iter_t operator + (unsigned count) { iter_t c (*thiz()); c += count; return c; } - iter_t operator ++ (int) { iter_t c (*thiz()); ++*thiz(); return c; } - iter_t operator - (unsigned count) { iter_t c (*thiz()); c -= count; return c; } - iter_t operator -- (int) { iter_t c (*thiz()); --*thiz(); return c; } + /* TODO: + * Port operators below to use hb_enable_if to sniff which method implements + * an operator and use it, and remove hb_iter_fallback_mixin_t completely. */ - /* Methods. */ + /* Operators. */ iter_t iter () const { return *thiz(); } - const_iter_t const_iter () const { return iter (); } - item_t& item () const { return thiz()->__item__ (); } - item_t& item_at (unsigned i) const { return thiz()->__item_at__ (i); } - bool more () const { return thiz()->__more__ (); } + iter_t operator + () const { return *thiz(); } + iter_t begin () const { return *thiz(); } + iter_t end () const { return thiz()->__end__ (); } + explicit operator bool () const { return thiz()->__more__ (); } unsigned len () const { return thiz()->__len__ (); } - void next () { thiz()->__next__ (); } - void forward (unsigned n) { thiz()->__forward__ (n); } - void prev () { thiz()->__prev__ (); } - void rewind (unsigned n) { thiz()->__rewind__ (n); } - bool random_access () const { return thiz()->__random_access__ (); } + /* The following can only be enabled if item_t is reference type. Otherwise + * it will be returning pointer to temporary rvalue. + * TODO Use a wrapper return type to fix for non-reference type. */ + template <typename T = item_t, + hb_enable_if (hb_is_reference (T))> + hb_remove_reference<item_t>* operator -> () const { return hb_addressof (**thiz()); } + item_t operator * () const { return thiz()->__item__ (); } + item_t operator * () { return thiz()->__item__ (); } + item_t operator [] (unsigned i) const { return thiz()->__item_at__ (i); } + item_t operator [] (unsigned i) { return thiz()->__item_at__ (i); } + iter_t& operator += (unsigned count) & { thiz()->__forward__ (count); return *thiz(); } + iter_t operator += (unsigned count) && { thiz()->__forward__ (count); return *thiz(); } + iter_t& operator ++ () & { thiz()->__next__ (); return *thiz(); } + iter_t operator ++ () && { thiz()->__next__ (); return *thiz(); } + iter_t& operator -= (unsigned count) & { thiz()->__rewind__ (count); return *thiz(); } + iter_t operator -= (unsigned count) && { thiz()->__rewind__ (count); return *thiz(); } + iter_t& operator -- () & { thiz()->__prev__ (); return *thiz(); } + iter_t operator -- () && { thiz()->__prev__ (); return *thiz(); } + iter_t operator + (unsigned count) const { auto c = thiz()->iter (); c += count; return c; } + friend iter_t operator + (unsigned count, const iter_t &it) { return it + count; } + iter_t operator ++ (int) { iter_t c (*thiz()); ++*thiz(); return c; } + iter_t operator - (unsigned count) const { auto c = thiz()->iter (); c -= count; return c; } + iter_t operator -- (int) { iter_t c (*thiz()); --*thiz(); return c; } + template <typename T> + iter_t& operator >> (T &v) & { v = **thiz(); ++*thiz(); return *thiz(); } + template <typename T> + iter_t operator >> (T &v) && { v = **thiz(); ++*thiz(); return *thiz(); } + template <typename T> + iter_t& operator << (const T v) & { **thiz() = v; ++*thiz(); return *thiz(); } + template <typename T> + iter_t operator << (const T v) && { **thiz() = v; ++*thiz(); return *thiz(); } protected: - hb_iter_t () {} - hb_iter_t (const hb_iter_t &o HB_UNUSED) {} - void operator = (const hb_iter_t &o HB_UNUSED) {} + hb_iter_t () = default; + hb_iter_t (const hb_iter_t &o HB_UNUSED) = default; + hb_iter_t (hb_iter_t &&o HB_UNUSED) = default; + hb_iter_t& operator = (const hb_iter_t &o HB_UNUSED) = default; + hb_iter_t& operator = (hb_iter_t &&o HB_UNUSED) = default; }; -/* Base class for sorted iterators. Does not enforce anything. - * Just for class taxonomy and requirements. */ -template <typename Iter, typename Item = typename Iter::__item_type__> -struct hb_sorted_iter_t : hb_iter_t<Iter, Item> +#define HB_ITER_USING(Name) \ + using item_t = typename Name::item_t; \ + using Name::begin; \ + using Name::end; \ + using Name::item_size; \ + using Name::is_iterator; \ + using Name::iter; \ + using Name::operator bool; \ + using Name::len; \ + using Name::operator ->; \ + using Name::operator *; \ + using Name::operator []; \ + using Name::operator +=; \ + using Name::operator ++; \ + using Name::operator -=; \ + using Name::operator --; \ + using Name::operator +; \ + using Name::operator -; \ + using Name::operator >>; \ + using Name::operator <<; \ + static_assert (true, "") + +/* Returns iterator / item type of a type. */ +template <typename Iterable> +using hb_iter_type = decltype (hb_deref (hb_declval (Iterable)).iter ()); +template <typename Iterable> +using hb_item_type = decltype (*hb_deref (hb_declval (Iterable)).iter ()); + + +template <typename> struct hb_array_t; + +struct { - protected: - hb_sorted_iter_t () {} - hb_sorted_iter_t (const hb_sorted_iter_t &o) : hb_iter_t<Iter, Item> (o) {} - void operator = (const hb_sorted_iter_t &o HB_UNUSED) {} -}; + template <typename T> hb_iter_type<T> + operator () (T&& c) const + { return hb_deref (hb_forward<T> (c)).iter (); } + + /* Specialization for C arrays. */ + + template <typename Type> inline hb_array_t<Type> + operator () (Type *array, unsigned int length) const + { return hb_array_t<Type> (array, length); } + + template <typename Type, unsigned int length> hb_array_t<Type> + operator () (Type (&array)[length]) const + { return hb_array_t<Type> (array, length); } + +} +HB_FUNCOBJ (hb_iter); /* Mixin to fill in what the subclass doesn't provide. */ -template <typename iter_t, typename item_t = typename iter_t::__item_type__> -struct hb_iter_mixin_t +template <typename iter_t, typename item_t = typename iter_t::__item_t__> +struct hb_iter_fallback_mixin_t { private: /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */ @@ -111,42 +187,645 @@ struct hb_iter_mixin_t public: /* Access: Implement __item__(), or __item_at__() if random-access. */ - item_t& __item__ () const { return thiz()->item_at (0); } - item_t& __item_at__ (unsigned i) const { return *(thiz() + i); } + item_t __item__ () const { return (*thiz())[0]; } + item_t __item_at__ (unsigned i) const { return *(*thiz() + i); } /* Termination: Implement __more__(), or __len__() if random-access. */ - bool __more__ () const { return thiz()->__len__ (); } + bool __more__ () const { return bool (thiz()->len ()); } unsigned __len__ () const - { iter_t c (*thiz()); unsigned l = 0; while (c) { c++; l++; }; return l; } + { iter_t c (*thiz()); unsigned l = 0; while (c) { c++; l++; } return l; } /* Advancing: Implement __next__(), or __forward__() if random-access. */ - void __next__ () { thiz()->forward (1); } - void __forward__ (unsigned n) { while (n--) thiz()->next (); } + void __next__ () { *thiz() += 1; } + void __forward__ (unsigned n) { while (*thiz() && n--) ++*thiz(); } /* Rewinding: Implement __prev__() or __rewind__() if bidirectional. */ - void __prev__ () { thiz()->rewind (1); } - void __rewind__ (unsigned n) { while (n--) thiz()->prev (); } + void __prev__ () { *thiz() -= 1; } + void __rewind__ (unsigned n) { while (*thiz() && n--) --*thiz(); } + + /* Range-based for: Implement __end__() if can be done faster, + * and operator!=. */ + iter_t __end__ () const + { + if (thiz()->is_random_access_iterator) + return *thiz() + thiz()->len (); + /* Above expression loops twice. Following loops once. */ + auto it = *thiz(); + while (it) ++it; + return it; + } + + protected: + hb_iter_fallback_mixin_t () = default; + hb_iter_fallback_mixin_t (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default; + hb_iter_fallback_mixin_t (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default; + hb_iter_fallback_mixin_t& operator = (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default; + hb_iter_fallback_mixin_t& operator = (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default; +}; + +template <typename iter_t, typename item_t = typename iter_t::__item_t__> +struct hb_iter_with_fallback_t : + hb_iter_t<iter_t, item_t>, + hb_iter_fallback_mixin_t<iter_t, item_t> +{ + protected: + hb_iter_with_fallback_t () = default; + hb_iter_with_fallback_t (const hb_iter_with_fallback_t &o HB_UNUSED) = default; + hb_iter_with_fallback_t (hb_iter_with_fallback_t &&o HB_UNUSED) = default; + hb_iter_with_fallback_t& operator = (const hb_iter_with_fallback_t &o HB_UNUSED) = default; + hb_iter_with_fallback_t& operator = (hb_iter_with_fallback_t &&o HB_UNUSED) = default; +}; + +/* + * Meta-programming predicates. + */ + +/* hb_is_iterator() / hb_is_iterator_of() */ + +template<typename Iter, typename Item> +struct hb_is_iterator_of +{ + template <typename Item2 = Item> + static hb_true_type impl (hb_priority<2>, hb_iter_t<Iter, hb_type_identity<Item2>> *); + static hb_false_type impl (hb_priority<0>, const void *); + + public: + static constexpr bool value = decltype (impl (hb_prioritize, hb_declval (Iter*)))::value; +}; +#define hb_is_iterator_of(Iter, Item) hb_is_iterator_of<Iter, Item>::value +#define hb_is_iterator(Iter) hb_is_iterator_of (Iter, typename Iter::item_t) + +/* hb_is_iterable() */ + +template <typename T> +struct hb_is_iterable +{ + private: + + template <typename U> + static auto impl (hb_priority<1>) -> decltype (hb_declval (U).iter (), hb_true_type ()); + + template <typename> + static hb_false_type impl (hb_priority<0>); + + public: + static constexpr bool value = decltype (impl<T> (hb_prioritize))::value; +}; +#define hb_is_iterable(Iterable) hb_is_iterable<Iterable>::value + +/* hb_is_source_of() / hb_is_sink_of() */ + +template<typename Iter, typename Item> +struct hb_is_source_of +{ + private: + template <typename Iter2 = Iter, + hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<hb_add_const<Item>>))> + static hb_true_type impl (hb_priority<2>); + template <typename Iter2 = Iter> + static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) >> hb_declval (Item &), hb_true_type ()); + static hb_false_type impl (hb_priority<0>); + + public: + static constexpr bool value = decltype (impl (hb_prioritize))::value; +}; +#define hb_is_source_of(Iter, Item) hb_is_source_of<Iter, Item>::value + +template<typename Iter, typename Item> +struct hb_is_sink_of +{ + private: + template <typename Iter2 = Iter, + hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<Item>))> + static hb_true_type impl (hb_priority<2>); + template <typename Iter2 = Iter> + static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) << hb_declval (Item), hb_true_type ()); + static hb_false_type impl (hb_priority<0>); + + public: + static constexpr bool value = decltype (impl (hb_prioritize))::value; +}; +#define hb_is_sink_of(Iter, Item) hb_is_sink_of<Iter, Item>::value + +/* This is commonly used, so define: */ +#define hb_is_sorted_source_of(Iter, Item) \ + (hb_is_source_of(Iter, Item) && Iter::is_sorted_iterator) + + +/* Range-based 'for' for iterables. */ + +template <typename Iterable, + hb_requires (hb_is_iterable (Iterable))> +static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ()) + +template <typename Iterable, + hb_requires (hb_is_iterable (Iterable))> +static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ()) + +/* begin()/end() are NOT looked up non-ADL. So each namespace must declare them. + * Do it for namespace OT. */ +namespace OT { + +template <typename Iterable, + hb_requires (hb_is_iterable (Iterable))> +static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ()) + +template <typename Iterable, + hb_requires (hb_is_iterable (Iterable))> +static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ()) + +} + + +/* + * Adaptors, combiners, etc. + */ + +template <typename Lhs, typename Rhs, + hb_requires (hb_is_iterator (Lhs))> +static inline auto +operator | (Lhs&& lhs, Rhs&& rhs) HB_AUTO_RETURN (hb_forward<Rhs> (rhs) (hb_forward<Lhs> (lhs))) + +/* hb_map(), hb_filter(), hb_reduce() */ + +enum class hb_function_sortedness_t { + NOT_SORTED, + RETAINS_SORTING, + SORTED, +}; + +template <typename Iter, typename Proj, hb_function_sortedness_t Sorted, + hb_requires (hb_is_iterator (Iter))> +struct hb_map_iter_t : + hb_iter_t<hb_map_iter_t<Iter, Proj, Sorted>, + decltype (hb_get (hb_declval (Proj), *hb_declval (Iter)))> +{ + hb_map_iter_t (const Iter& it, Proj f_) : it (it), f (f_) {} + + typedef decltype (hb_get (hb_declval (Proj), *hb_declval (Iter))) __item_t__; + static constexpr bool is_random_access_iterator = Iter::is_random_access_iterator; + static constexpr bool is_sorted_iterator = + Sorted == hb_function_sortedness_t::SORTED ? true : + Sorted == hb_function_sortedness_t::RETAINS_SORTING ? Iter::is_sorted_iterator : + false; + __item_t__ __item__ () const { return hb_get (f.get (), *it); } + __item_t__ __item_at__ (unsigned i) const { return hb_get (f.get (), it[i]); } + bool __more__ () const { return bool (it); } + unsigned __len__ () const { return it.len (); } + void __next__ () { ++it; } + void __forward__ (unsigned n) { it += n; } + void __prev__ () { --it; } + void __rewind__ (unsigned n) { it -= n; } + hb_map_iter_t __end__ () const { return hb_map_iter_t (it.end (), f); } + bool operator != (const hb_map_iter_t& o) const + { return it != o.it; } + + private: + Iter it; + hb_reference_wrapper<Proj> f; +}; + +template <typename Proj, hb_function_sortedness_t Sorted> +struct hb_map_iter_factory_t +{ + hb_map_iter_factory_t (Proj f) : f (f) {} + + template <typename Iter, + hb_requires (hb_is_iterator (Iter))> + hb_map_iter_t<Iter, Proj, Sorted> + operator () (Iter it) + { return hb_map_iter_t<Iter, Proj, Sorted> (it, f); } + + private: + Proj f; +}; +struct +{ + template <typename Proj> + hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED> + operator () (Proj&& f) const + { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED> (f); } +} +HB_FUNCOBJ (hb_map); +struct +{ + template <typename Proj> + hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING> + operator () (Proj&& f) const + { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING> (f); } +} +HB_FUNCOBJ (hb_map_retains_sorting); +struct +{ + template <typename Proj> + hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED> + operator () (Proj&& f) const + { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED> (f); } +} +HB_FUNCOBJ (hb_map_sorted); + +template <typename Iter, typename Pred, typename Proj, + hb_requires (hb_is_iterator (Iter))> +struct hb_filter_iter_t : + hb_iter_with_fallback_t<hb_filter_iter_t<Iter, Pred, Proj>, + typename Iter::item_t> +{ + hb_filter_iter_t (const Iter& it_, Pred p_, Proj f_) : it (it_), p (p_), f (f_) + { while (it && !hb_has (p.get (), hb_get (f.get (), *it))) ++it; } + + typedef typename Iter::item_t __item_t__; + static constexpr bool is_sorted_iterator = Iter::is_sorted_iterator; + __item_t__ __item__ () const { return *it; } + bool __more__ () const { return bool (it); } + void __next__ () { do ++it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); } + void __prev__ () { do --it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); } + hb_filter_iter_t __end__ () const { return hb_filter_iter_t (it.end (), p, f); } + bool operator != (const hb_filter_iter_t& o) const + { return it != o.it; } + + private: + Iter it; + hb_reference_wrapper<Pred> p; + hb_reference_wrapper<Proj> f; +}; +template <typename Pred, typename Proj> +struct hb_filter_iter_factory_t +{ + hb_filter_iter_factory_t (Pred p, Proj f) : p (p), f (f) {} + + template <typename Iter, + hb_requires (hb_is_iterator (Iter))> + hb_filter_iter_t<Iter, Pred, Proj> + operator () (Iter it) + { return hb_filter_iter_t<Iter, Pred, Proj> (it, p, f); } + + private: + Pred p; + Proj f; +}; +struct +{ + template <typename Pred = decltype ((hb_identity)), + typename Proj = decltype ((hb_identity))> + hb_filter_iter_factory_t<Pred, Proj> + operator () (Pred&& p = hb_identity, Proj&& f = hb_identity) const + { return hb_filter_iter_factory_t<Pred, Proj> (p, f); } +} +HB_FUNCOBJ (hb_filter); + +template <typename Redu, typename InitT> +struct hb_reduce_t +{ + hb_reduce_t (Redu r, InitT init_value) : r (r), init_value (init_value) {} + + template <typename Iter, + hb_requires (hb_is_iterator (Iter)), + typename AccuT = decltype (hb_declval (Redu) (hb_declval (InitT), hb_declval (typename Iter::item_t)))> + AccuT + operator () (Iter it) + { + AccuT value = init_value; + for (; it; ++it) + value = r (value, *it); + return value; + } + + private: + Redu r; + InitT init_value; +}; +struct +{ + template <typename Redu, typename InitT> + hb_reduce_t<Redu, InitT> + operator () (Redu&& r, InitT init_value) const + { return hb_reduce_t<Redu, InitT> (r, init_value); } +} +HB_FUNCOBJ (hb_reduce); + - /* Random access: Return true if item_at(), len(), forward() are fast. */ - bool __random_access__ () const { return false; } +/* hb_zip() */ + +template <typename A, typename B> +struct hb_zip_iter_t : + hb_iter_t<hb_zip_iter_t<A, B>, + hb_pair_t<typename A::item_t, typename B::item_t>> +{ + hb_zip_iter_t () {} + hb_zip_iter_t (const A& a, const B& b) : a (a), b (b) {} + + typedef hb_pair_t<typename A::item_t, typename B::item_t> __item_t__; + static constexpr bool is_random_access_iterator = + A::is_random_access_iterator && + B::is_random_access_iterator; + /* Note. The following categorization is only valid if A is strictly sorted, + * ie. does NOT have duplicates. Previously I tried to categorize sortedness + * more granularly, see commits: + * + * 513762849a683914fc266a17ddf38f133cccf072 + * 4d3cf2adb669c345cc43832d11689271995e160a + * + * However, that was not enough, since hb_sorted_array_t, hb_sorted_vector_t, + * SortedArrayOf, etc all needed to be updated to add more variants. At that + * point I saw it not worth the effort, and instead we now deem all sorted + * collections as essentially strictly-sorted for the purposes of zip. + * + * The above assumption is not as bad as it sounds. Our "sorted" comes with + * no guarantees. It's just a contract, put in place to help you remember, + * and think about, whether an iterator you receive is expected to be + * sorted or not. As such, it's not perfect by definition, and should not + * be treated so. The inaccuracy here just errs in the direction of being + * more permissive, so your code compiles instead of erring on the side of + * marking your zipped iterator unsorted in which case your code won't + * compile. + * + * This semantical limitation does NOT affect logic in any other place I + * know of as of this writing. + */ + static constexpr bool is_sorted_iterator = A::is_sorted_iterator; + + __item_t__ __item__ () const { return __item_t__ (*a, *b); } + __item_t__ __item_at__ (unsigned i) const { return __item_t__ (a[i], b[i]); } + bool __more__ () const { return bool (a) && bool (b); } + unsigned __len__ () const { return hb_min (a.len (), b.len ()); } + void __next__ () { ++a; ++b; } + void __forward__ (unsigned n) { a += n; b += n; } + void __prev__ () { --a; --b; } + void __rewind__ (unsigned n) { a -= n; b -= n; } + hb_zip_iter_t __end__ () const { return hb_zip_iter_t (a.end (), b.end ()); } + /* Note, we should stop if ANY of the iters reaches end. As such two compare + * unequal if both items are unequal, NOT if either is unequal. */ + bool operator != (const hb_zip_iter_t& o) const + { return a != o.a && b != o.b; } + + private: + A a; + B b; +}; +struct +{ + template <typename A, typename B, + hb_requires (hb_is_iterable (A) && hb_is_iterable (B))> + hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>> + operator () (A&& a, B&& b) const + { return hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>> (hb_iter (a), hb_iter (b)); } +} +HB_FUNCOBJ (hb_zip); + +/* hb_apply() */ + +template <typename Appl> +struct hb_apply_t +{ + hb_apply_t (Appl a) : a (a) {} + + template <typename Iter, + hb_requires (hb_is_iterator (Iter))> + void operator () (Iter it) + { + for (; it; ++it) + (void) hb_invoke (a, *it); + } + + private: + Appl a; }; +struct +{ + template <typename Appl> hb_apply_t<Appl> + operator () (Appl&& a) const + { return hb_apply_t<Appl> (a); } + + template <typename Appl> hb_apply_t<Appl&> + operator () (Appl *a) const + { return hb_apply_t<Appl&> (*a); } +} +HB_FUNCOBJ (hb_apply); +/* hb_iota()/hb_range() */ -/* Functions operating on iterators or iteratables. */ +template <typename T, typename S> +struct hb_counter_iter_t : + hb_iter_t<hb_counter_iter_t<T, S>, T> +{ + hb_counter_iter_t (T start, T end_, S step) : v (start), end_ (end_for (start, end_, step)), step (step) {} + + typedef T __item_t__; + static constexpr bool is_random_access_iterator = true; + static constexpr bool is_sorted_iterator = true; + __item_t__ __item__ () const { return +v; } + __item_t__ __item_at__ (unsigned j) const { return v + j * step; } + bool __more__ () const { return v != end_; } + unsigned __len__ () const { return !step ? UINT_MAX : (end_ - v) / step; } + void __next__ () { v += step; } + void __forward__ (unsigned n) { v += n * step; } + void __prev__ () { v -= step; } + void __rewind__ (unsigned n) { v -= n * step; } + hb_counter_iter_t __end__ () const { return hb_counter_iter_t (end_, end_, step); } + bool operator != (const hb_counter_iter_t& o) const + { return v != o.v; } + + private: + static inline T end_for (T start, T end_, S step) + { + if (!step) + return end_; + auto res = (end_ - start) % step; + if (!res) + return end_; + end_ += step - res; + return end_; + } + + private: + T v; + T end_; + S step; +}; +struct +{ + template <typename T = unsigned, typename S = unsigned> hb_counter_iter_t<T, S> + operator () (T start = 0u, S&& step = 1u) const + { return hb_counter_iter_t<T, S> (start, step >= 0 ? hb_int_max (T) : hb_int_min (T), step); } +} +HB_FUNCOBJ (hb_iota); +struct +{ + template <typename T = unsigned> hb_counter_iter_t<T, unsigned> + operator () (T end = (unsigned) -1) const + { return hb_counter_iter_t<T, unsigned> (0, end, 1u); } + + template <typename T, typename S = unsigned> hb_counter_iter_t<T, S> + operator () (T start, T end, S&& step = 1u) const + { return hb_counter_iter_t<T, S> (start, end, step); } +} +HB_FUNCOBJ (hb_range); + +/* hb_enumerate */ + +struct +{ + template <typename Iterable, + typename Index = unsigned, + hb_requires (hb_is_iterable (Iterable))> + auto operator () (Iterable&& it, Index start = 0u) const HB_AUTO_RETURN + ( hb_zip (hb_iota (start), it) ) +} +HB_FUNCOBJ (hb_enumerate); + + +/* hb_sink() */ + +template <typename Sink> +struct hb_sink_t +{ + hb_sink_t (Sink s) : s (s) {} + + template <typename Iter, + hb_requires (hb_is_iterator (Iter))> + void operator () (Iter it) + { + for (; it; ++it) + s << *it; + } + + private: + Sink s; +}; +struct +{ + template <typename Sink> hb_sink_t<Sink> + operator () (Sink&& s) const + { return hb_sink_t<Sink> (s); } + + template <typename Sink> hb_sink_t<Sink&> + operator () (Sink *s) const + { return hb_sink_t<Sink&> (*s); } +} +HB_FUNCOBJ (hb_sink); + +/* hb-drain: hb_sink to void / blackhole / /dev/null. */ + +struct +{ + template <typename Iter, + hb_requires (hb_is_iterator (Iter))> + void operator () (Iter it) const + { + for (; it; ++it) + (void) *it; + } +} +HB_FUNCOBJ (hb_drain); + +/* hb_unzip(): unzip and sink to two sinks. */ + +template <typename Sink1, typename Sink2> +struct hb_unzip_t +{ + hb_unzip_t (Sink1 s1, Sink2 s2) : s1 (s1), s2 (s2) {} + + template <typename Iter, + hb_requires (hb_is_iterator (Iter))> + void operator () (Iter it) + { + for (; it; ++it) + { + const auto &v = *it; + s1 << v.first; + s2 << v.second; + } + } + + private: + Sink1 s1; + Sink2 s2; +}; +struct +{ + template <typename Sink1, typename Sink2> hb_unzip_t<Sink1, Sink2> + operator () (Sink1&& s1, Sink2&& s2) const + { return hb_unzip_t<Sink1, Sink2> (s1, s2); } + + template <typename Sink1, typename Sink2> hb_unzip_t<Sink1&, Sink2&> + operator () (Sink1 *s1, Sink2 *s2) const + { return hb_unzip_t<Sink1&, Sink2&> (*s1, *s2); } +} +HB_FUNCOBJ (hb_unzip); + + +/* hb-all, hb-any, hb-none. */ + +struct +{ + template <typename Iterable, + typename Pred = decltype ((hb_identity)), + typename Proj = decltype ((hb_identity)), + hb_requires (hb_is_iterable (Iterable))> + bool operator () (Iterable&& c, + Pred&& p = hb_identity, + Proj&& f = hb_identity) const + { + for (auto it = hb_iter (c); it; ++it) + if (!hb_match (hb_forward<Pred> (p), hb_get (hb_forward<Proj> (f), *it))) + return false; + return true; + } +} +HB_FUNCOBJ (hb_all); +struct +{ + template <typename Iterable, + typename Pred = decltype ((hb_identity)), + typename Proj = decltype ((hb_identity)), + hb_requires (hb_is_iterable (Iterable))> + bool operator () (Iterable&& c, + Pred&& p = hb_identity, + Proj&& f = hb_identity) const + { + for (auto it = hb_iter (c); it; ++it) + if (hb_match (hb_forward<Pred> (p), hb_get (hb_forward<Proj> (f), *it))) + return true; + return false; + } +} +HB_FUNCOBJ (hb_any); +struct +{ + template <typename Iterable, + typename Pred = decltype ((hb_identity)), + typename Proj = decltype ((hb_identity)), + hb_requires (hb_is_iterable (Iterable))> + bool operator () (Iterable&& c, + Pred&& p = hb_identity, + Proj&& f = hb_identity) const + { + for (auto it = hb_iter (c); it; ++it) + if (hb_match (hb_forward<Pred> (p), hb_get (hb_forward<Proj> (f), *it))) + return false; + return true; + } +} +HB_FUNCOBJ (hb_none); + +/* + * Algorithms operating on iterators. + */ -template <typename C, typename V> inline void -hb_fill (const C& c, const V &v) +template <typename C, typename V, + hb_requires (hb_is_iterable (C))> +inline void +hb_fill (C& c, const V &v) { - for (typename C::iter_t i (c); i; i++) - hb_assign (*i, v); + for (auto i = hb_iter (c); i; i++) + *i = v; } -template <typename S, typename D> inline bool -hb_copy (hb_iter_t<D> &id, hb_iter_t<S> &is) +template <typename S, typename D> +inline void +hb_copy (S&& is, D&& id) { - for (; id && is; ++id, ++is) - *id = *is; - return !is; + hb_iter (is) | hb_sink (id); } |