diff options
Diffstat (limited to 'thirdparty/harfbuzz/src/hb-iter.hh')
| -rw-r--r-- | thirdparty/harfbuzz/src/hb-iter.hh | 1016 |
1 files changed, 1016 insertions, 0 deletions
diff --git a/thirdparty/harfbuzz/src/hb-iter.hh b/thirdparty/harfbuzz/src/hb-iter.hh new file mode 100644 index 0000000000..1a3ab43de0 --- /dev/null +++ b/thirdparty/harfbuzz/src/hb-iter.hh @@ -0,0 +1,1016 @@ +/* + * Copyright © 2018 Google, Inc. + * Copyright © 2019 Facebook, Inc. + * + * This is part of HarfBuzz, a text shaping library. + * + * Permission is hereby granted, without written agreement and without + * license or royalty fees, to use, copy, modify, and distribute this + * software and its documentation for any purpose, provided that the + * above copyright notice and the following two paragraphs appear in + * all copies of this software. + * + * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR + * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES + * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN + * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + * + * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, + * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND + * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS + * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO + * 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-algs.hh" +#include "hb-meta.hh" + + +/* Unified iterator object. + * + * The goal of this template is to make the same iterator interface + * available to all types, and make it very easy and compact to use. + * hb_iter_tator objects are small, light-weight, objects that can be + * copied by value. If the collection / object being iterated on + * is writable, then the iterator returns lvalues, otherwise it + * returns rvalues. + * + * If iterator implementation implements operator!=, then it can be + * used in range-based for loop. That already happens 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. */ + +/* + * Base classes for iterators. + */ + +/* Base class for all iterators. */ +template <typename iter_t, typename Item = typename iter_t::__item_t__> +struct hb_iter_t +{ + typedef Item item_t; + constexpr unsigned get_item_size () const { return 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 */ + const iter_t* thiz () const { return static_cast<const iter_t *> (this); } + iter_t* thiz () { return static_cast< iter_t *> (this); } + public: + + /* Operators. */ + iter_t iter () const { return *thiz(); } + 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__ (); } + /* The following can only be enabled if item_t is reference type. Otherwise + * it will be returning pointer to temporary rvalue. */ + template <typename T = item_t, + hb_enable_if (std::is_reference<T>::value)> + hb_remove_reference<item_t>* operator -> () const { return std::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 () = 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; +}; + +#define HB_ITER_USING(Name) \ + using item_t = typename Name::item_t; \ + using Name::begin; \ + using Name::end; \ + using Name::get_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; +template <typename> struct hb_sorted_array_t; + +struct +{ + template <typename T> hb_iter_type<T> + operator () (T&& c) const + { return hb_deref (std::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); +struct +{ + template <typename T> unsigned + operator () (T&& c) const + { return c.len (); } + +} +HB_FUNCOBJ (hb_len); + +/* Mixin to fill in what the subclass doesn't provide. */ +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 */ + const iter_t* thiz () const { return static_cast<const iter_t *> (this); } + iter_t* thiz () { return static_cast< iter_t *> (this); } + public: + + /* Access: Implement __item__(), or __item_at__() if random-access. */ + 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 bool (thiz()->len ()); } + unsigned __len__ () const + { iter_t c (*thiz()); unsigned l = 0; while (c) { c++; l++; } return l; } + + /* Advancing: Implement __next__(), or __forward__() if random-access. */ + void __next__ () { *thiz() += 1; } + void __forward__ (unsigned n) { while (*thiz() && n--) ++*thiz(); } + + /* Rewinding: Implement __prev__() or __rewind__() if bidirectional. */ + 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) +#define hb_is_sorted_iterator_of(Iter, Item) (hb_is_iterator_of<Iter, Item>::value && Iter::is_sorted_iterator) +#define hb_is_sorted_iterator(Iter) hb_is_sorted_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<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 (std::forward<Rhs> (rhs) (std::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 = hb_decay<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); + + +/* 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 +{ HB_PARTIALIZE(2); + 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_concat() */ + +template <typename A, typename B> +struct hb_concat_iter_t : + hb_iter_t<hb_concat_iter_t<A, B>, typename A::item_t> +{ + hb_concat_iter_t () {} + hb_concat_iter_t (A& a, B& b) : a (a), b (b) {} + hb_concat_iter_t (const A& a, const B& b) : a (a), b (b) {} + + + typedef typename A::item_t __item_t__; + static constexpr bool is_random_access_iterator = + A::is_random_access_iterator && + B::is_random_access_iterator; + static constexpr bool is_sorted_iterator = false; + + __item_t__ __item__ () const + { + if (!a) + return *b; + return *a; + } + + __item_t__ __item_at__ (unsigned i) const + { + unsigned a_len = a.len (); + if (i < a_len) + return a[i]; + return b[i - a_len]; + } + + bool __more__ () const { return bool (a) || bool (b); } + + unsigned __len__ () const { return a.len () + b.len (); } + + void __next__ () + { + if (a) + ++a; + else + ++b; + } + + void __forward__ (unsigned n) + { + if (!n) return; + if (!is_random_access_iterator) { + while (n-- && *this) { + (*this)++; + } + return; + } + + unsigned a_len = a.len (); + if (n > a_len) { + n -= a_len; + a.__forward__ (a_len); + b.__forward__ (n); + } else { + a.__forward__ (n); + } + } + + hb_concat_iter_t __end__ () const { return hb_concat_iter_t (a.end (), b.end ()); } + bool operator != (const hb_concat_iter_t& o) const + { + return a != o.a + || b != o.b; + } + + private: + A a; + B b; +}; +struct +{ HB_PARTIALIZE(2); + template <typename A, typename B, + hb_requires (hb_is_iterable (A) && hb_is_iterable (B))> + hb_concat_iter_t<hb_iter_type<A>, hb_iter_type<B>> + operator () (A&& a, B&& b) const + { return hb_concat_iter_t<hb_iter_type<A>, hb_iter_type<B>> (hb_iter (a), hb_iter (b)); } +} +HB_FUNCOBJ (hb_concat); + +/* 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_range()/hb_iota()/hb_repeat() */ + +template <typename T, typename S> +struct hb_range_iter_t : + hb_iter_t<hb_range_iter_t<T, S>, T> +{ + hb_range_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 hb_ridentity (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_range_iter_t __end__ () const { return hb_range_iter_t (end_, end_, step); } + bool operator != (const hb_range_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> hb_range_iter_t<T, unsigned> + operator () (T end = (unsigned) -1) const + { return hb_range_iter_t<T, unsigned> (0, end, 1u); } + + template <typename T, typename S = unsigned> hb_range_iter_t<T, S> + operator () (T start, T end, S step = 1u) const + { return hb_range_iter_t<T, S> (start, end, step); } +} +HB_FUNCOBJ (hb_range); + +template <typename T, typename S> +struct hb_iota_iter_t : + hb_iter_with_fallback_t<hb_iota_iter_t<T, S>, T> +{ + hb_iota_iter_t (T start, S step) : v (start), step (step) {} + + private: + + template <typename S2 = S> + auto + inc (hb_type_identity<S2> s, hb_priority<1>) + -> hb_void_t<decltype (hb_invoke (std::forward<S2> (s), hb_declval<T&> ()))> + { v = hb_invoke (std::forward<S2> (s), v); } + + void + inc (S s, hb_priority<0>) + { v += s; } + + public: + + typedef T __item_t__; + static constexpr bool is_random_access_iterator = true; + static constexpr bool is_sorted_iterator = true; + __item_t__ __item__ () const { return hb_ridentity (v); } + bool __more__ () const { return true; } + unsigned __len__ () const { return UINT_MAX; } + void __next__ () { inc (step, hb_prioritize); } + void __prev__ () { v -= step; } + hb_iota_iter_t __end__ () const { return *this; } + bool operator != (const hb_iota_iter_t& o) const { return true; } + + private: + T v; + S step; +}; +struct +{ + template <typename T = unsigned, typename S = unsigned> hb_iota_iter_t<T, S> + operator () (T start = 0u, S step = 1u) const + { return hb_iota_iter_t<T, S> (start, step); } +} +HB_FUNCOBJ (hb_iota); + +template <typename T> +struct hb_repeat_iter_t : + hb_iter_t<hb_repeat_iter_t<T>, T> +{ + hb_repeat_iter_t (T value) : v (value) {} + + 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; } + bool __more__ () const { return true; } + unsigned __len__ () const { return UINT_MAX; } + void __next__ () {} + void __forward__ (unsigned) {} + void __prev__ () {} + void __rewind__ (unsigned) {} + hb_repeat_iter_t __end__ () const { return *this; } + bool operator != (const hb_repeat_iter_t& o) const { return true; } + + private: + T v; +}; +struct +{ + template <typename T> hb_repeat_iter_t<T> + operator () (T value) const + { return hb_repeat_iter_t<T> (value); } +} +HB_FUNCOBJ (hb_repeat); + +/* hb_enumerate()/hb_take() */ + +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); + +struct +{ HB_PARTIALIZE(2); + template <typename Iterable, + hb_requires (hb_is_iterable (Iterable))> + auto operator () (Iterable&& it, unsigned count) const HB_AUTO_RETURN + ( hb_zip (hb_range (count), it) | hb_map (hb_second) ) + + /* Specialization arrays. */ + + template <typename Type> inline hb_array_t<Type> + operator () (hb_array_t<Type> array, unsigned count) const + { return array.sub_array (0, count); } + + template <typename Type> inline hb_sorted_array_t<Type> + operator () (hb_sorted_array_t<Type> array, unsigned count) const + { return array.sub_array (0, count); } +} +HB_FUNCOBJ (hb_take); + +struct +{ HB_PARTIALIZE(2); + template <typename Iter, + hb_requires (hb_is_iterator (Iter))> + auto operator () (Iter it, unsigned count) const HB_AUTO_RETURN + ( + + hb_iota (it, hb_add (count)) + | hb_map (hb_take (count)) + | hb_take ((hb_len (it) + count - 1) / count) + ) +} +HB_FUNCOBJ (hb_chop); + +/* 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 (std::forward<Pred> (p), hb_get (std::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 (std::forward<Pred> (p), hb_get (std::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 (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it))) + return false; + return true; + } +} +HB_FUNCOBJ (hb_none); + +/* + * Algorithms operating on iterators. + */ + +template <typename C, typename V, + hb_requires (hb_is_iterable (C))> +inline void +hb_fill (C&& c, const V &v) +{ + for (auto i = hb_iter (c); i; i++) + *i = v; +} + +template <typename S, typename D> +inline void +hb_copy (S&& is, D&& id) +{ + hb_iter (is) | hb_sink (id); +} + + +#endif /* HB_ITER_HH */ |