Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 1 | /* |
| 2 | * Copyright © 2018 Google, Inc. |
Behdad Esfahbod | 89fea21 | 2019-04-15 17:36:09 -0400 | [diff] [blame] | 3 | * Copyright © 2019 Facebook, Inc. |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 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 |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 26 | * Facebook Author(s): Behdad Esfahbod |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 27 | */ |
| 28 | |
| 29 | #ifndef HB_ITER_HH |
| 30 | #define HB_ITER_HH |
| 31 | |
| 32 | #include "hb.hh" |
Behdad Esfahbod | a3fcb9a | 2019-04-16 10:45:20 -0400 | [diff] [blame] | 33 | #include "hb-algs.hh" |
Behdad Esfahbod | e76a3ca | 2018-12-27 17:23:12 -0500 | [diff] [blame] | 34 | #include "hb-meta.hh" |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 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. |
Behdad Esfahbod | 314d869 | 2018-12-21 00:54:55 -0500 | [diff] [blame] | 41 | * hb_iter_tator objects are small, light-weight, objects that can be |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 42 | * copied by value. If the collection / object being iterated on |
Behdad Esfahbod | 314d869 | 2018-12-21 00:54:55 -0500 | [diff] [blame] | 43 | * is writable, then the iterator returns lvalues, otherwise it |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 44 | * returns rvalues. |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 45 | * |
| 46 | * TODO Document more. |
| 47 | * |
| 48 | * If iterator implementation implements operator!=, then can be |
Behdad Esfahbod | bb48bf5 | 2021-07-08 10:53:45 -0600 | [diff] [blame] | 49 | * used in range-based for loop. That already happens if the iterator |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 50 | * is random-access. Otherwise, the range-based for loop incurs |
| 51 | * one traversal to find end(), which can be avoided if written |
| 52 | * as a while-style for loop, or if iterator implements a faster |
| 53 | * __end__() method. |
| 54 | * TODO When opting in for C++17, address this by changing return |
| 55 | * type of .end()? |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 56 | */ |
| 57 | |
Behdad Esfahbod | 8c6cbbd | 2018-12-28 14:29:09 -0500 | [diff] [blame] | 58 | /* |
| 59 | * Base classes for iterators. |
| 60 | */ |
| 61 | |
Behdad Esfahbod | 314d869 | 2018-12-21 00:54:55 -0500 | [diff] [blame] | 62 | /* Base class for all iterators. */ |
Behdad Esfahbod | 6b6783e | 2019-01-26 22:44:09 +0100 | [diff] [blame] | 63 | template <typename iter_t, typename Item = typename iter_t::__item_t__> |
Behdad Esfahbod | cb5011d | 2019-01-04 11:22:32 -0500 | [diff] [blame] | 64 | struct hb_iter_t |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 65 | { |
Behdad Esfahbod | aeb696a | 2018-12-21 01:57:02 -0500 | [diff] [blame] | 66 | typedef Item item_t; |
Behdad Esfahbod | c72589f | 2019-08-29 15:45:21 -0700 | [diff] [blame] | 67 | constexpr unsigned get_item_size () const { return hb_static_size (Item); } |
Behdad Esfahbod | 090fe56 | 2019-01-25 15:34:03 +0100 | [diff] [blame] | 68 | static constexpr bool is_iterator = true; |
| 69 | static constexpr bool is_random_access_iterator = false; |
Behdad Esfahbod | 889dc1e | 2019-05-14 22:28:07 -0700 | [diff] [blame] | 70 | static constexpr bool is_sorted_iterator = false; |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 71 | |
Behdad Esfahbod | 2fc1860 | 2018-12-21 18:09:45 -0500 | [diff] [blame] | 72 | private: |
| 73 | /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */ |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 74 | const iter_t* thiz () const { return static_cast<const iter_t *> (this); } |
Ebrahim Byagowi | a0b4ac4 | 2019-08-24 17:57:14 +0430 | [diff] [blame] | 75 | iter_t* thiz () { return static_cast< iter_t *> (this); } |
Behdad Esfahbod | 2fc1860 | 2018-12-21 18:09:45 -0500 | [diff] [blame] | 76 | public: |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 77 | |
Behdad Esfahbod | 6c548b6 | 2019-01-08 13:43:49 -0800 | [diff] [blame] | 78 | /* TODO: |
| 79 | * Port operators below to use hb_enable_if to sniff which method implements |
Behdad Esfahbod | 84a25d7 | 2019-01-29 13:39:19 -0800 | [diff] [blame] | 80 | * an operator and use it, and remove hb_iter_fallback_mixin_t completely. */ |
Behdad Esfahbod | 6c548b6 | 2019-01-08 13:43:49 -0800 | [diff] [blame] | 81 | |
Behdad Esfahbod | 314d869 | 2018-12-21 00:54:55 -0500 | [diff] [blame] | 82 | /* Operators. */ |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 83 | iter_t iter () const { return *thiz(); } |
| 84 | iter_t operator + () const { return *thiz(); } |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 85 | iter_t begin () const { return *thiz(); } |
| 86 | iter_t end () const { return thiz()->__end__ (); } |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 87 | explicit operator bool () const { return thiz()->__more__ (); } |
| 88 | unsigned len () const { return thiz()->__len__ (); } |
Behdad Esfahbod | 2d94094 | 2019-01-30 16:03:16 -0800 | [diff] [blame] | 89 | /* The following can only be enabled if item_t is reference type. Otherwise |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 90 | * it will be returning pointer to temporary rvalue. |
| 91 | * TODO Use a wrapper return type to fix for non-reference type. */ |
Behdad Esfahbod | 2d94094 | 2019-01-30 16:03:16 -0800 | [diff] [blame] | 92 | template <typename T = item_t, |
| 93 | hb_enable_if (hb_is_reference (T))> |
Behdad Esfahbod | 54ece29 | 2019-04-16 16:45:53 -0400 | [diff] [blame] | 94 | hb_remove_reference<item_t>* operator -> () const { return hb_addressof (**thiz()); } |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 95 | item_t operator * () const { return thiz()->__item__ (); } |
| 96 | item_t operator * () { return thiz()->__item__ (); } |
| 97 | item_t operator [] (unsigned i) const { return thiz()->__item_at__ (i); } |
| 98 | item_t operator [] (unsigned i) { return thiz()->__item_at__ (i); } |
Behdad Esfahbod | a66598e | 2019-05-08 09:56:29 -0700 | [diff] [blame] | 99 | iter_t& operator += (unsigned count) & { thiz()->__forward__ (count); return *thiz(); } |
| 100 | iter_t operator += (unsigned count) && { thiz()->__forward__ (count); return *thiz(); } |
Behdad Esfahbod | c09d6c5 | 2019-05-07 14:09:00 -0700 | [diff] [blame] | 101 | iter_t& operator ++ () & { thiz()->__next__ (); return *thiz(); } |
| 102 | iter_t operator ++ () && { thiz()->__next__ (); return *thiz(); } |
Behdad Esfahbod | a66598e | 2019-05-08 09:56:29 -0700 | [diff] [blame] | 103 | iter_t& operator -= (unsigned count) & { thiz()->__rewind__ (count); return *thiz(); } |
| 104 | iter_t operator -= (unsigned count) && { thiz()->__rewind__ (count); return *thiz(); } |
Behdad Esfahbod | c09d6c5 | 2019-05-07 14:09:00 -0700 | [diff] [blame] | 105 | iter_t& operator -- () & { thiz()->__prev__ (); return *thiz(); } |
| 106 | iter_t operator -- () && { thiz()->__prev__ (); return *thiz(); } |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 107 | iter_t operator + (unsigned count) const { auto c = thiz()->iter (); c += count; return c; } |
| 108 | friend iter_t operator + (unsigned count, const iter_t &it) { return it + count; } |
| 109 | iter_t operator ++ (int) { iter_t c (*thiz()); ++*thiz(); return c; } |
| 110 | iter_t operator - (unsigned count) const { auto c = thiz()->iter (); c -= count; return c; } |
| 111 | iter_t operator -- (int) { iter_t c (*thiz()); --*thiz(); return c; } |
Behdad Esfahbod | 57795bc | 2019-01-28 16:23:12 -0500 | [diff] [blame] | 112 | template <typename T> |
Behdad Esfahbod | a66598e | 2019-05-08 09:56:29 -0700 | [diff] [blame] | 113 | iter_t& operator >> (T &v) & { v = **thiz(); ++*thiz(); return *thiz(); } |
Behdad Esfahbod | 57795bc | 2019-01-28 16:23:12 -0500 | [diff] [blame] | 114 | template <typename T> |
Behdad Esfahbod | a66598e | 2019-05-08 09:56:29 -0700 | [diff] [blame] | 115 | iter_t operator >> (T &v) && { v = **thiz(); ++*thiz(); return *thiz(); } |
| 116 | template <typename T> |
| 117 | iter_t& operator << (const T v) & { **thiz() = v; ++*thiz(); return *thiz(); } |
| 118 | template <typename T> |
| 119 | iter_t operator << (const T v) && { **thiz() = v; ++*thiz(); return *thiz(); } |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 120 | |
Behdad Esfahbod | 2fc1860 | 2018-12-21 18:09:45 -0500 | [diff] [blame] | 121 | protected: |
Behdad Esfahbod | f244224 | 2019-05-15 14:19:20 -0700 | [diff] [blame] | 122 | hb_iter_t () = default; |
| 123 | hb_iter_t (const hb_iter_t &o HB_UNUSED) = default; |
| 124 | hb_iter_t (hb_iter_t &&o HB_UNUSED) = default; |
| 125 | hb_iter_t& operator = (const hb_iter_t &o HB_UNUSED) = default; |
| 126 | hb_iter_t& operator = (hb_iter_t &&o HB_UNUSED) = default; |
Behdad Esfahbod | 2fc1860 | 2018-12-21 18:09:45 -0500 | [diff] [blame] | 127 | }; |
| 128 | |
Behdad Esfahbod | 570473a | 2018-12-27 13:29:51 -0500 | [diff] [blame] | 129 | #define HB_ITER_USING(Name) \ |
Behdad Esfahbod | f78f837 | 2019-01-08 16:38:08 -0800 | [diff] [blame] | 130 | using item_t = typename Name::item_t; \ |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 131 | using Name::begin; \ |
| 132 | using Name::end; \ |
Behdad Esfahbod | c72589f | 2019-08-29 15:45:21 -0700 | [diff] [blame] | 133 | using Name::get_item_size; \ |
Behdad Esfahbod | 6cd96ba | 2018-12-30 20:51:31 -0500 | [diff] [blame] | 134 | using Name::is_iterator; \ |
Behdad Esfahbod | 570473a | 2018-12-27 13:29:51 -0500 | [diff] [blame] | 135 | using Name::iter; \ |
| 136 | using Name::operator bool; \ |
| 137 | using Name::len; \ |
| 138 | using Name::operator ->; \ |
| 139 | using Name::operator *; \ |
| 140 | using Name::operator []; \ |
| 141 | using Name::operator +=; \ |
| 142 | using Name::operator ++; \ |
| 143 | using Name::operator -=; \ |
| 144 | using Name::operator --; \ |
Behdad Esfahbod | 859a880 | 2018-12-30 02:11:03 -0500 | [diff] [blame] | 145 | using Name::operator +; \ |
Behdad Esfahbod | 570473a | 2018-12-27 13:29:51 -0500 | [diff] [blame] | 146 | using Name::operator -; \ |
Behdad Esfahbod | 6521d5b | 2019-01-29 13:44:39 -0800 | [diff] [blame] | 147 | using Name::operator >>; \ |
| 148 | using Name::operator <<; \ |
Behdad Esfahbod | 570473a | 2018-12-27 13:29:51 -0500 | [diff] [blame] | 149 | static_assert (true, "") |
| 150 | |
Behdad Esfahbod | 5875d77 | 2019-05-08 12:25:34 -0700 | [diff] [blame] | 151 | /* Returns iterator / item type of a type. */ |
| 152 | template <typename Iterable> |
| 153 | using hb_iter_type = decltype (hb_deref (hb_declval (Iterable)).iter ()); |
| 154 | template <typename Iterable> |
| 155 | using hb_item_type = decltype (*hb_deref (hb_declval (Iterable)).iter ()); |
Behdad Esfahbod | 778c96b | 2019-01-27 00:50:54 +0100 | [diff] [blame] | 156 | |
Behdad Esfahbod | 0363ce6 | 2019-01-27 01:03:56 +0100 | [diff] [blame] | 157 | |
Behdad Esfahbod | 0363ce6 | 2019-01-27 01:03:56 +0100 | [diff] [blame] | 158 | template <typename> struct hb_array_t; |
Behdad Esfahbod | 5828d8e | 2019-08-31 14:36:44 -0500 | [diff] [blame] | 159 | template <typename> struct hb_sorted_array_t; |
Behdad Esfahbod | 72dd5e3 | 2019-02-15 16:11:32 -0800 | [diff] [blame] | 160 | |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 161 | struct |
Behdad Esfahbod | 72dd5e3 | 2019-02-15 16:11:32 -0800 | [diff] [blame] | 162 | { |
Behdad Esfahbod | 5875d77 | 2019-05-08 12:25:34 -0700 | [diff] [blame] | 163 | template <typename T> hb_iter_type<T> |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 164 | operator () (T&& c) const |
Behdad Esfahbod | 6d555ce | 2021-11-02 00:18:22 -0600 | [diff] [blame^] | 165 | { return hb_deref (std::forward<T> (c)).iter (); } |
Behdad Esfahbod | 72dd5e3 | 2019-02-15 16:11:32 -0800 | [diff] [blame] | 166 | |
| 167 | /* Specialization for C arrays. */ |
| 168 | |
| 169 | template <typename Type> inline hb_array_t<Type> |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 170 | operator () (Type *array, unsigned int length) const |
Behdad Esfahbod | 72dd5e3 | 2019-02-15 16:11:32 -0800 | [diff] [blame] | 171 | { return hb_array_t<Type> (array, length); } |
| 172 | |
| 173 | template <typename Type, unsigned int length> hb_array_t<Type> |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 174 | operator () (Type (&array)[length]) const |
Behdad Esfahbod | 72dd5e3 | 2019-02-15 16:11:32 -0800 | [diff] [blame] | 175 | { return hb_array_t<Type> (array, length); } |
| 176 | |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 177 | } |
| 178 | HB_FUNCOBJ (hb_iter); |
Behdad Esfahbod | 398b296 | 2019-08-31 12:44:24 -0500 | [diff] [blame] | 179 | struct |
| 180 | { |
| 181 | template <typename T> unsigned |
| 182 | operator () (T&& c) const |
| 183 | { return c.len (); } |
| 184 | |
| 185 | } |
| 186 | HB_FUNCOBJ (hb_len); |
Behdad Esfahbod | 0363ce6 | 2019-01-27 01:03:56 +0100 | [diff] [blame] | 187 | |
Behdad Esfahbod | 2fc1860 | 2018-12-21 18:09:45 -0500 | [diff] [blame] | 188 | /* Mixin to fill in what the subclass doesn't provide. */ |
Behdad Esfahbod | 636786e | 2019-01-08 23:48:35 -0800 | [diff] [blame] | 189 | template <typename iter_t, typename item_t = typename iter_t::__item_t__> |
Behdad Esfahbod | 84a25d7 | 2019-01-29 13:39:19 -0800 | [diff] [blame] | 190 | struct hb_iter_fallback_mixin_t |
Behdad Esfahbod | 2fc1860 | 2018-12-21 18:09:45 -0500 | [diff] [blame] | 191 | { |
| 192 | private: |
| 193 | /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */ |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 194 | const iter_t* thiz () const { return static_cast<const iter_t *> (this); } |
Ebrahim Byagowi | a0b4ac4 | 2019-08-24 17:57:14 +0430 | [diff] [blame] | 195 | iter_t* thiz () { return static_cast< iter_t *> (this); } |
Behdad Esfahbod | 2fc1860 | 2018-12-21 18:09:45 -0500 | [diff] [blame] | 196 | public: |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 197 | |
Behdad Esfahbod | 8001e00 | 2018-12-21 01:53:27 -0500 | [diff] [blame] | 198 | /* Access: Implement __item__(), or __item_at__() if random-access. */ |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 199 | item_t __item__ () const { return (*thiz())[0]; } |
| 200 | item_t __item_at__ (unsigned i) const { return *(*thiz() + i); } |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 201 | |
Behdad Esfahbod | 2a33ab0 | 2018-12-21 18:49:27 -0500 | [diff] [blame] | 202 | /* Termination: Implement __more__(), or __len__() if random-access. */ |
Behdad Esfahbod | 57a5256 | 2019-05-09 11:30:27 -0700 | [diff] [blame] | 203 | bool __more__ () const { return bool (thiz()->len ()); } |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 204 | unsigned __len__ () const |
Behdad Esfahbod | e98f0dd | 2019-05-13 13:53:06 -0700 | [diff] [blame] | 205 | { iter_t c (*thiz()); unsigned l = 0; while (c) { c++; l++; } return l; } |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 206 | |
Behdad Esfahbod | 314d869 | 2018-12-21 00:54:55 -0500 | [diff] [blame] | 207 | /* Advancing: Implement __next__(), or __forward__() if random-access. */ |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 208 | void __next__ () { *thiz() += 1; } |
Behdad Esfahbod | 606841b | 2019-05-11 11:54:30 -0700 | [diff] [blame] | 209 | void __forward__ (unsigned n) { while (*thiz() && n--) ++*thiz(); } |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 210 | |
Behdad Esfahbod | 19d2b50 | 2018-12-21 01:17:35 -0500 | [diff] [blame] | 211 | /* Rewinding: Implement __prev__() or __rewind__() if bidirectional. */ |
Behdad Esfahbod | a98e406 | 2019-04-12 22:42:44 -0400 | [diff] [blame] | 212 | void __prev__ () { *thiz() -= 1; } |
Behdad Esfahbod | 606841b | 2019-05-11 11:54:30 -0700 | [diff] [blame] | 213 | void __rewind__ (unsigned n) { while (*thiz() && n--) --*thiz(); } |
Behdad Esfahbod | 19d2b50 | 2018-12-21 01:17:35 -0500 | [diff] [blame] | 214 | |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 215 | /* Range-based for: Implement __end__() if can be done faster, |
| 216 | * and operator!=. */ |
| 217 | iter_t __end__ () const |
| 218 | { |
| 219 | if (thiz()->is_random_access_iterator) |
| 220 | return *thiz() + thiz()->len (); |
| 221 | /* Above expression loops twice. Following loops once. */ |
| 222 | auto it = *thiz(); |
| 223 | while (it) ++it; |
| 224 | return it; |
| 225 | } |
| 226 | |
Behdad Esfahbod | d3976b7 | 2018-12-26 18:54:27 -0500 | [diff] [blame] | 227 | protected: |
Behdad Esfahbod | f244224 | 2019-05-15 14:19:20 -0700 | [diff] [blame] | 228 | hb_iter_fallback_mixin_t () = default; |
| 229 | hb_iter_fallback_mixin_t (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default; |
| 230 | hb_iter_fallback_mixin_t (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default; |
| 231 | hb_iter_fallback_mixin_t& operator = (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default; |
| 232 | hb_iter_fallback_mixin_t& operator = (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default; |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 233 | }; |
| 234 | |
Behdad Esfahbod | 849a0f1 | 2019-01-29 17:10:19 -0800 | [diff] [blame] | 235 | template <typename iter_t, typename item_t = typename iter_t::__item_t__> |
| 236 | struct hb_iter_with_fallback_t : |
| 237 | hb_iter_t<iter_t, item_t>, |
| 238 | hb_iter_fallback_mixin_t<iter_t, item_t> |
| 239 | { |
| 240 | protected: |
Behdad Esfahbod | f244224 | 2019-05-15 14:19:20 -0700 | [diff] [blame] | 241 | hb_iter_with_fallback_t () = default; |
| 242 | hb_iter_with_fallback_t (const hb_iter_with_fallback_t &o HB_UNUSED) = default; |
| 243 | hb_iter_with_fallback_t (hb_iter_with_fallback_t &&o HB_UNUSED) = default; |
| 244 | hb_iter_with_fallback_t& operator = (const hb_iter_with_fallback_t &o HB_UNUSED) = default; |
| 245 | hb_iter_with_fallback_t& operator = (hb_iter_with_fallback_t &&o HB_UNUSED) = default; |
Behdad Esfahbod | 849a0f1 | 2019-01-29 17:10:19 -0800 | [diff] [blame] | 246 | }; |
| 247 | |
Behdad Esfahbod | 8c6cbbd | 2018-12-28 14:29:09 -0500 | [diff] [blame] | 248 | /* |
| 249 | * Meta-programming predicates. |
| 250 | */ |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 251 | |
Behdad Esfahbod | ed972d5 | 2019-05-09 16:58:28 -0700 | [diff] [blame] | 252 | /* hb_is_iterator() / hb_is_iterator_of() */ |
| 253 | |
| 254 | template<typename Iter, typename Item> |
| 255 | struct hb_is_iterator_of |
| 256 | { |
| 257 | template <typename Item2 = Item> |
Behdad Esfahbod | 61d150c | 2019-05-10 20:06:31 -0700 | [diff] [blame] | 258 | static hb_true_type impl (hb_priority<2>, hb_iter_t<Iter, hb_type_identity<Item2>> *); |
| 259 | static hb_false_type impl (hb_priority<0>, const void *); |
Behdad Esfahbod | ed972d5 | 2019-05-09 16:58:28 -0700 | [diff] [blame] | 260 | |
| 261 | public: |
| 262 | static constexpr bool value = decltype (impl (hb_prioritize, hb_declval (Iter*)))::value; |
| 263 | }; |
| 264 | #define hb_is_iterator_of(Iter, Item) hb_is_iterator_of<Iter, Item>::value |
| 265 | #define hb_is_iterator(Iter) hb_is_iterator_of (Iter, typename Iter::item_t) |
| 266 | |
Behdad Esfahbod | df138da | 2018-12-28 16:29:48 -0500 | [diff] [blame] | 267 | /* hb_is_iterable() */ |
| 268 | |
Behdad Esfahbod | d419a9a | 2019-04-03 14:18:19 -0700 | [diff] [blame] | 269 | template <typename T> |
| 270 | struct hb_is_iterable |
| 271 | { |
| 272 | private: |
Behdad Esfahbod | ae8da4b | 2019-04-22 15:25:11 -0400 | [diff] [blame] | 273 | |
Behdad Esfahbod | d419a9a | 2019-04-03 14:18:19 -0700 | [diff] [blame] | 274 | template <typename U> |
Behdad Esfahbod | 61d150c | 2019-05-10 20:06:31 -0700 | [diff] [blame] | 275 | static auto impl (hb_priority<1>) -> decltype (hb_declval (U).iter (), hb_true_type ()); |
Behdad Esfahbod | ae8da4b | 2019-04-22 15:25:11 -0400 | [diff] [blame] | 276 | |
Behdad Esfahbod | d419a9a | 2019-04-03 14:18:19 -0700 | [diff] [blame] | 277 | template <typename> |
Behdad Esfahbod | 61d150c | 2019-05-10 20:06:31 -0700 | [diff] [blame] | 278 | static hb_false_type impl (hb_priority<0>); |
Behdad Esfahbod | 8570da1 | 2018-12-28 14:40:30 -0500 | [diff] [blame] | 279 | |
Behdad Esfahbod | d419a9a | 2019-04-03 14:18:19 -0700 | [diff] [blame] | 280 | public: |
Behdad Esfahbod | ed972d5 | 2019-05-09 16:58:28 -0700 | [diff] [blame] | 281 | static constexpr bool value = decltype (impl<T> (hb_prioritize))::value; |
Behdad Esfahbod | d419a9a | 2019-04-03 14:18:19 -0700 | [diff] [blame] | 282 | }; |
Behdad Esfahbod | 8c6cbbd | 2018-12-28 14:29:09 -0500 | [diff] [blame] | 283 | #define hb_is_iterable(Iterable) hb_is_iterable<Iterable>::value |
| 284 | |
Behdad Esfahbod | ed972d5 | 2019-05-09 16:58:28 -0700 | [diff] [blame] | 285 | /* hb_is_source_of() / hb_is_sink_of() */ |
Behdad Esfahbod | 73c82f2 | 2019-04-26 13:16:48 -0700 | [diff] [blame] | 286 | |
Behdad Esfahbod | 06a44e2 | 2018-12-30 18:42:14 -0500 | [diff] [blame] | 287 | template<typename Iter, typename Item> |
Behdad Esfahbod | ed972d5 | 2019-05-09 16:58:28 -0700 | [diff] [blame] | 288 | struct hb_is_source_of |
| 289 | { |
| 290 | private: |
| 291 | template <typename Iter2 = Iter, |
Behdad Esfahbod | 19e08a1 | 2019-05-10 21:25:07 -0700 | [diff] [blame] | 292 | hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<hb_add_const<Item>>))> |
Behdad Esfahbod | 61d150c | 2019-05-10 20:06:31 -0700 | [diff] [blame] | 293 | static hb_true_type impl (hb_priority<2>); |
Behdad Esfahbod | 98974ac | 2019-05-10 11:18:52 -0700 | [diff] [blame] | 294 | template <typename Iter2 = Iter> |
Behdad Esfahbod | 61d150c | 2019-05-10 20:06:31 -0700 | [diff] [blame] | 295 | static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) >> hb_declval (Item &), hb_true_type ()); |
| 296 | static hb_false_type impl (hb_priority<0>); |
Behdad Esfahbod | df138da | 2018-12-28 16:29:48 -0500 | [diff] [blame] | 297 | |
Behdad Esfahbod | ed972d5 | 2019-05-09 16:58:28 -0700 | [diff] [blame] | 298 | public: |
| 299 | static constexpr bool value = decltype (impl (hb_prioritize))::value; |
| 300 | }; |
| 301 | #define hb_is_source_of(Iter, Item) hb_is_source_of<Iter, Item>::value |
Behdad Esfahbod | 2658e40 | 2019-01-08 12:53:02 -0800 | [diff] [blame] | 302 | |
Behdad Esfahbod | ed972d5 | 2019-05-09 16:58:28 -0700 | [diff] [blame] | 303 | template<typename Iter, typename Item> |
| 304 | struct hb_is_sink_of |
| 305 | { |
| 306 | private: |
Behdad Esfahbod | 98974ac | 2019-05-10 11:18:52 -0700 | [diff] [blame] | 307 | template <typename Iter2 = Iter, |
Behdad Esfahbod | 19e08a1 | 2019-05-10 21:25:07 -0700 | [diff] [blame] | 308 | hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<Item>))> |
Behdad Esfahbod | 61d150c | 2019-05-10 20:06:31 -0700 | [diff] [blame] | 309 | static hb_true_type impl (hb_priority<2>); |
Behdad Esfahbod | 98974ac | 2019-05-10 11:18:52 -0700 | [diff] [blame] | 310 | template <typename Iter2 = Iter> |
Behdad Esfahbod | 61d150c | 2019-05-10 20:06:31 -0700 | [diff] [blame] | 311 | static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) << hb_declval (Item), hb_true_type ()); |
| 312 | static hb_false_type impl (hb_priority<0>); |
Behdad Esfahbod | ed972d5 | 2019-05-09 16:58:28 -0700 | [diff] [blame] | 313 | |
| 314 | public: |
| 315 | static constexpr bool value = decltype (impl (hb_prioritize))::value; |
| 316 | }; |
| 317 | #define hb_is_sink_of(Iter, Item) hb_is_sink_of<Iter, Item>::value |
| 318 | |
| 319 | /* This is commonly used, so define: */ |
| 320 | #define hb_is_sorted_source_of(Iter, Item) \ |
| 321 | (hb_is_source_of(Iter, Item) && Iter::is_sorted_iterator) |
Behdad Esfahbod | df138da | 2018-12-28 16:29:48 -0500 | [diff] [blame] | 322 | |
Behdad Esfahbod | 014c502 | 2019-01-09 09:07:01 -0800 | [diff] [blame] | 323 | |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 324 | /* Range-based 'for' for iterables. */ |
| 325 | |
| 326 | template <typename Iterable, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 327 | hb_requires (hb_is_iterable (Iterable))> |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 328 | static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ()) |
| 329 | |
| 330 | template <typename Iterable, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 331 | hb_requires (hb_is_iterable (Iterable))> |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 332 | static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ()) |
| 333 | |
| 334 | /* begin()/end() are NOT looked up non-ADL. So each namespace must declare them. |
| 335 | * Do it for namespace OT. */ |
| 336 | namespace OT { |
| 337 | |
| 338 | template <typename Iterable, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 339 | hb_requires (hb_is_iterable (Iterable))> |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 340 | static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ()) |
| 341 | |
| 342 | template <typename Iterable, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 343 | hb_requires (hb_is_iterable (Iterable))> |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 344 | static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ()) |
| 345 | |
| 346 | } |
| 347 | |
| 348 | |
Behdad Esfahbod | 8c6cbbd | 2018-12-28 14:29:09 -0500 | [diff] [blame] | 349 | /* |
Behdad Esfahbod | 014c502 | 2019-01-09 09:07:01 -0800 | [diff] [blame] | 350 | * Adaptors, combiners, etc. |
Behdad Esfahbod | 8c6cbbd | 2018-12-28 14:29:09 -0500 | [diff] [blame] | 351 | */ |
Behdad Esfahbod | 7557e34 | 2018-12-21 17:21:19 -0500 | [diff] [blame] | 352 | |
Behdad Esfahbod | 343f5a4 | 2019-01-09 12:35:45 -0800 | [diff] [blame] | 353 | template <typename Lhs, typename Rhs, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 354 | hb_requires (hb_is_iterator (Lhs))> |
Behdad Esfahbod | 6916b77 | 2019-04-16 18:33:51 -0400 | [diff] [blame] | 355 | static inline auto |
Behdad Esfahbod | 6d555ce | 2021-11-02 00:18:22 -0600 | [diff] [blame^] | 356 | operator | (Lhs&& lhs, Rhs&& rhs) HB_AUTO_RETURN (std::forward<Rhs> (rhs) (std::forward<Lhs> (lhs))) |
Behdad Esfahbod | 343f5a4 | 2019-01-09 12:35:45 -0800 | [diff] [blame] | 357 | |
Behdad Esfahbod | 1733e47 | 2019-01-09 11:15:49 -0800 | [diff] [blame] | 358 | /* hb_map(), hb_filter(), hb_reduce() */ |
| 359 | |
Behdad Esfahbod | 7e02063 | 2019-05-13 15:26:00 -0700 | [diff] [blame] | 360 | enum class hb_function_sortedness_t { |
Behdad Esfahbod | 79126df | 2019-05-11 11:23:31 -0700 | [diff] [blame] | 361 | NOT_SORTED, |
| 362 | RETAINS_SORTING, |
| 363 | SORTED, |
| 364 | }; |
| 365 | |
Behdad Esfahbod | 7e02063 | 2019-05-13 15:26:00 -0700 | [diff] [blame] | 366 | template <typename Iter, typename Proj, hb_function_sortedness_t Sorted, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 367 | hb_requires (hb_is_iterator (Iter))> |
Behdad Esfahbod | 1733e47 | 2019-01-09 11:15:49 -0800 | [diff] [blame] | 368 | struct hb_map_iter_t : |
Behdad Esfahbod | 79126df | 2019-05-11 11:23:31 -0700 | [diff] [blame] | 369 | hb_iter_t<hb_map_iter_t<Iter, Proj, Sorted>, |
Behdad Esfahbod | c93eeba | 2019-05-08 10:56:09 -0700 | [diff] [blame] | 370 | decltype (hb_get (hb_declval (Proj), *hb_declval (Iter)))> |
Behdad Esfahbod | 1733e47 | 2019-01-09 11:15:49 -0800 | [diff] [blame] | 371 | { |
Behdad Esfahbod | 025eaa3 | 2019-05-07 00:05:37 -0700 | [diff] [blame] | 372 | hb_map_iter_t (const Iter& it, Proj f_) : it (it), f (f_) {} |
Behdad Esfahbod | 1733e47 | 2019-01-09 11:15:49 -0800 | [diff] [blame] | 373 | |
Behdad Esfahbod | c93eeba | 2019-05-08 10:56:09 -0700 | [diff] [blame] | 374 | typedef decltype (hb_get (hb_declval (Proj), *hb_declval (Iter))) __item_t__; |
Behdad Esfahbod | 090fe56 | 2019-01-25 15:34:03 +0100 | [diff] [blame] | 375 | static constexpr bool is_random_access_iterator = Iter::is_random_access_iterator; |
Behdad Esfahbod | 889dc1e | 2019-05-14 22:28:07 -0700 | [diff] [blame] | 376 | static constexpr bool is_sorted_iterator = |
| 377 | Sorted == hb_function_sortedness_t::SORTED ? true : |
| 378 | Sorted == hb_function_sortedness_t::RETAINS_SORTING ? Iter::is_sorted_iterator : |
| 379 | false; |
Behdad Esfahbod | 025eaa3 | 2019-05-07 00:05:37 -0700 | [diff] [blame] | 380 | __item_t__ __item__ () const { return hb_get (f.get (), *it); } |
| 381 | __item_t__ __item_at__ (unsigned i) const { return hb_get (f.get (), it[i]); } |
Behdad Esfahbod | 343f5a4 | 2019-01-09 12:35:45 -0800 | [diff] [blame] | 382 | bool __more__ () const { return bool (it); } |
Behdad Esfahbod | 1733e47 | 2019-01-09 11:15:49 -0800 | [diff] [blame] | 383 | unsigned __len__ () const { return it.len (); } |
| 384 | void __next__ () { ++it; } |
| 385 | void __forward__ (unsigned n) { it += n; } |
| 386 | void __prev__ () { --it; } |
| 387 | void __rewind__ (unsigned n) { it -= n; } |
Behdad Esfahbod | 8903040 | 2019-05-07 00:13:11 -0700 | [diff] [blame] | 388 | hb_map_iter_t __end__ () const { return hb_map_iter_t (it.end (), f); } |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 389 | bool operator != (const hb_map_iter_t& o) const |
Behdad Esfahbod | ebf47a9 | 2019-05-15 15:14:26 -0700 | [diff] [blame] | 390 | { return it != o.it; } |
Behdad Esfahbod | 1733e47 | 2019-01-09 11:15:49 -0800 | [diff] [blame] | 391 | |
| 392 | private: |
| 393 | Iter it; |
Behdad Esfahbod | 025eaa3 | 2019-05-07 00:05:37 -0700 | [diff] [blame] | 394 | hb_reference_wrapper<Proj> f; |
Behdad Esfahbod | 1733e47 | 2019-01-09 11:15:49 -0800 | [diff] [blame] | 395 | }; |
Behdad Esfahbod | 6b6783e | 2019-01-26 22:44:09 +0100 | [diff] [blame] | 396 | |
Behdad Esfahbod | 7e02063 | 2019-05-13 15:26:00 -0700 | [diff] [blame] | 397 | template <typename Proj, hb_function_sortedness_t Sorted> |
Behdad Esfahbod | 1733e47 | 2019-01-09 11:15:49 -0800 | [diff] [blame] | 398 | struct hb_map_iter_factory_t |
| 399 | { |
Behdad Esfahbod | 0670e1a | 2019-02-14 11:53:40 -0800 | [diff] [blame] | 400 | hb_map_iter_factory_t (Proj f) : f (f) {} |
Behdad Esfahbod | 1733e47 | 2019-01-09 11:15:49 -0800 | [diff] [blame] | 401 | |
Behdad Esfahbod | 345bfbb | 2019-02-14 10:48:20 -0800 | [diff] [blame] | 402 | template <typename Iter, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 403 | hb_requires (hb_is_iterator (Iter))> |
Behdad Esfahbod | 79126df | 2019-05-11 11:23:31 -0700 | [diff] [blame] | 404 | hb_map_iter_t<Iter, Proj, Sorted> |
Behdad Esfahbod | aa4ac13 | 2019-05-08 10:02:30 -0700 | [diff] [blame] | 405 | operator () (Iter it) |
Behdad Esfahbod | 79126df | 2019-05-11 11:23:31 -0700 | [diff] [blame] | 406 | { return hb_map_iter_t<Iter, Proj, Sorted> (it, f); } |
Behdad Esfahbod | 1733e47 | 2019-01-09 11:15:49 -0800 | [diff] [blame] | 407 | |
| 408 | private: |
| 409 | Proj f; |
| 410 | }; |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 411 | struct |
Behdad Esfahbod | 98be7bd | 2019-02-15 16:09:29 -0800 | [diff] [blame] | 412 | { |
| 413 | template <typename Proj> |
Behdad Esfahbod | 7e02063 | 2019-05-13 15:26:00 -0700 | [diff] [blame] | 414 | hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED> |
Behdad Esfahbod | 98be7bd | 2019-02-15 16:09:29 -0800 | [diff] [blame] | 415 | operator () (Proj&& f) const |
Behdad Esfahbod | 7e02063 | 2019-05-13 15:26:00 -0700 | [diff] [blame] | 416 | { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED> (f); } |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 417 | } |
| 418 | HB_FUNCOBJ (hb_map); |
Behdad Esfahbod | 79126df | 2019-05-11 11:23:31 -0700 | [diff] [blame] | 419 | struct |
| 420 | { |
| 421 | template <typename Proj> |
Behdad Esfahbod | 7e02063 | 2019-05-13 15:26:00 -0700 | [diff] [blame] | 422 | hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING> |
Behdad Esfahbod | 79126df | 2019-05-11 11:23:31 -0700 | [diff] [blame] | 423 | operator () (Proj&& f) const |
Behdad Esfahbod | 7e02063 | 2019-05-13 15:26:00 -0700 | [diff] [blame] | 424 | { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING> (f); } |
Behdad Esfahbod | 79126df | 2019-05-11 11:23:31 -0700 | [diff] [blame] | 425 | } |
| 426 | HB_FUNCOBJ (hb_map_retains_sorting); |
| 427 | struct |
| 428 | { |
| 429 | template <typename Proj> |
Behdad Esfahbod | 7e02063 | 2019-05-13 15:26:00 -0700 | [diff] [blame] | 430 | hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED> |
Behdad Esfahbod | 79126df | 2019-05-11 11:23:31 -0700 | [diff] [blame] | 431 | operator () (Proj&& f) const |
Behdad Esfahbod | 7e02063 | 2019-05-13 15:26:00 -0700 | [diff] [blame] | 432 | { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED> (f); } |
Behdad Esfahbod | 79126df | 2019-05-11 11:23:31 -0700 | [diff] [blame] | 433 | } |
| 434 | HB_FUNCOBJ (hb_map_sorted); |
Behdad Esfahbod | 1733e47 | 2019-01-09 11:15:49 -0800 | [diff] [blame] | 435 | |
Behdad Esfahbod | f35568d | 2019-01-09 11:32:33 -0800 | [diff] [blame] | 436 | template <typename Iter, typename Pred, typename Proj, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 437 | hb_requires (hb_is_iterator (Iter))> |
Behdad Esfahbod | f35568d | 2019-01-09 11:32:33 -0800 | [diff] [blame] | 438 | struct hb_filter_iter_t : |
Behdad Esfahbod | 849a0f1 | 2019-01-29 17:10:19 -0800 | [diff] [blame] | 439 | hb_iter_with_fallback_t<hb_filter_iter_t<Iter, Pred, Proj>, |
| 440 | typename Iter::item_t> |
Behdad Esfahbod | f35568d | 2019-01-09 11:32:33 -0800 | [diff] [blame] | 441 | { |
Behdad Esfahbod | 025eaa3 | 2019-05-07 00:05:37 -0700 | [diff] [blame] | 442 | hb_filter_iter_t (const Iter& it_, Pred p_, Proj f_) : it (it_), p (p_), f (f_) |
| 443 | { while (it && !hb_has (p.get (), hb_get (f.get (), *it))) ++it; } |
Behdad Esfahbod | f35568d | 2019-01-09 11:32:33 -0800 | [diff] [blame] | 444 | |
| 445 | typedef typename Iter::item_t __item_t__; |
Behdad Esfahbod | 889dc1e | 2019-05-14 22:28:07 -0700 | [diff] [blame] | 446 | static constexpr bool is_sorted_iterator = Iter::is_sorted_iterator; |
Behdad Esfahbod | f35568d | 2019-01-09 11:32:33 -0800 | [diff] [blame] | 447 | __item_t__ __item__ () const { return *it; } |
Behdad Esfahbod | 343f5a4 | 2019-01-09 12:35:45 -0800 | [diff] [blame] | 448 | bool __more__ () const { return bool (it); } |
Behdad Esfahbod | 025eaa3 | 2019-05-07 00:05:37 -0700 | [diff] [blame] | 449 | void __next__ () { do ++it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); } |
David Corbett | c1c122e | 2019-05-11 11:38:06 -0400 | [diff] [blame] | 450 | void __prev__ () { do --it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); } |
Behdad Esfahbod | 8903040 | 2019-05-07 00:13:11 -0700 | [diff] [blame] | 451 | hb_filter_iter_t __end__ () const { return hb_filter_iter_t (it.end (), p, f); } |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 452 | bool operator != (const hb_filter_iter_t& o) const |
Behdad Esfahbod | ebf47a9 | 2019-05-15 15:14:26 -0700 | [diff] [blame] | 453 | { return it != o.it; } |
Behdad Esfahbod | f35568d | 2019-01-09 11:32:33 -0800 | [diff] [blame] | 454 | |
| 455 | private: |
| 456 | Iter it; |
Behdad Esfahbod | 025eaa3 | 2019-05-07 00:05:37 -0700 | [diff] [blame] | 457 | hb_reference_wrapper<Pred> p; |
| 458 | hb_reference_wrapper<Proj> f; |
Behdad Esfahbod | f35568d | 2019-01-09 11:32:33 -0800 | [diff] [blame] | 459 | }; |
| 460 | template <typename Pred, typename Proj> |
| 461 | struct hb_filter_iter_factory_t |
| 462 | { |
Behdad Esfahbod | 0670e1a | 2019-02-14 11:53:40 -0800 | [diff] [blame] | 463 | hb_filter_iter_factory_t (Pred p, Proj f) : p (p), f (f) {} |
Behdad Esfahbod | f35568d | 2019-01-09 11:32:33 -0800 | [diff] [blame] | 464 | |
Behdad Esfahbod | 0f292ea | 2019-02-14 10:49:31 -0800 | [diff] [blame] | 465 | template <typename Iter, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 466 | hb_requires (hb_is_iterator (Iter))> |
Behdad Esfahbod | 0f292ea | 2019-02-14 10:49:31 -0800 | [diff] [blame] | 467 | hb_filter_iter_t<Iter, Pred, Proj> |
Behdad Esfahbod | aa4ac13 | 2019-05-08 10:02:30 -0700 | [diff] [blame] | 468 | operator () (Iter it) |
Behdad Esfahbod | 0f292ea | 2019-02-14 10:49:31 -0800 | [diff] [blame] | 469 | { return hb_filter_iter_t<Iter, Pred, Proj> (it, p, f); } |
Behdad Esfahbod | f35568d | 2019-01-09 11:32:33 -0800 | [diff] [blame] | 470 | |
| 471 | private: |
| 472 | Pred p; |
| 473 | Proj f; |
| 474 | }; |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 475 | struct |
Behdad Esfahbod | 00db940 | 2019-02-14 11:10:13 -0800 | [diff] [blame] | 476 | { |
Behdad Esfahbod | 710d459 | 2019-05-08 09:33:09 -0700 | [diff] [blame] | 477 | template <typename Pred = decltype ((hb_identity)), |
Behdad Esfahbod | 00db940 | 2019-02-14 11:10:13 -0800 | [diff] [blame] | 478 | typename Proj = decltype ((hb_identity))> |
| 479 | hb_filter_iter_factory_t<Pred, Proj> |
Behdad Esfahbod | 710d459 | 2019-05-08 09:33:09 -0700 | [diff] [blame] | 480 | operator () (Pred&& p = hb_identity, Proj&& f = hb_identity) const |
Behdad Esfahbod | 00db940 | 2019-02-14 11:10:13 -0800 | [diff] [blame] | 481 | { return hb_filter_iter_factory_t<Pred, Proj> (p, f); } |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 482 | } |
| 483 | HB_FUNCOBJ (hb_filter); |
Behdad Esfahbod | 7557e34 | 2018-12-21 17:21:19 -0500 | [diff] [blame] | 484 | |
Ebrahim Byagowi | b864208 | 2019-04-02 00:30:06 +0430 | [diff] [blame] | 485 | template <typename Redu, typename InitT> |
Ebrahim Byagowi | e526414 | 2019-03-31 12:41:58 +0430 | [diff] [blame] | 486 | struct hb_reduce_t |
| 487 | { |
Ebrahim Byagowi | b864208 | 2019-04-02 00:30:06 +0430 | [diff] [blame] | 488 | hb_reduce_t (Redu r, InitT init_value) : r (r), init_value (init_value) {} |
Ebrahim Byagowi | e526414 | 2019-03-31 12:41:58 +0430 | [diff] [blame] | 489 | |
| 490 | template <typename Iter, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 491 | hb_requires (hb_is_iterator (Iter)), |
Behdad Esfahbod | 7bcc5df | 2019-07-28 20:55:50 -0700 | [diff] [blame] | 492 | typename AccuT = hb_decay<decltype (hb_declval (Redu) (hb_declval (InitT), hb_declval (typename Iter::item_t)))>> |
Ebrahim Byagowi | b864208 | 2019-04-02 00:30:06 +0430 | [diff] [blame] | 493 | AccuT |
Behdad Esfahbod | aa4ac13 | 2019-05-08 10:02:30 -0700 | [diff] [blame] | 494 | operator () (Iter it) |
Ebrahim Byagowi | e526414 | 2019-03-31 12:41:58 +0430 | [diff] [blame] | 495 | { |
Ebrahim Byagowi | b864208 | 2019-04-02 00:30:06 +0430 | [diff] [blame] | 496 | AccuT value = init_value; |
Ebrahim Byagowi | e526414 | 2019-03-31 12:41:58 +0430 | [diff] [blame] | 497 | for (; it; ++it) |
Ebrahim Byagowi | b864208 | 2019-04-02 00:30:06 +0430 | [diff] [blame] | 498 | value = r (value, *it); |
Ebrahim Byagowi | e526414 | 2019-03-31 12:41:58 +0430 | [diff] [blame] | 499 | return value; |
| 500 | } |
| 501 | |
| 502 | private: |
| 503 | Redu r; |
Ebrahim Byagowi | b864208 | 2019-04-02 00:30:06 +0430 | [diff] [blame] | 504 | InitT init_value; |
Ebrahim Byagowi | e526414 | 2019-03-31 12:41:58 +0430 | [diff] [blame] | 505 | }; |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 506 | struct |
Ebrahim Byagowi | e526414 | 2019-03-31 12:41:58 +0430 | [diff] [blame] | 507 | { |
Ebrahim Byagowi | b864208 | 2019-04-02 00:30:06 +0430 | [diff] [blame] | 508 | template <typename Redu, typename InitT> |
| 509 | hb_reduce_t<Redu, InitT> |
| 510 | operator () (Redu&& r, InitT init_value) const |
| 511 | { return hb_reduce_t<Redu, InitT> (r, init_value); } |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 512 | } |
| 513 | HB_FUNCOBJ (hb_reduce); |
Ebrahim Byagowi | e526414 | 2019-03-31 12:41:58 +0430 | [diff] [blame] | 514 | |
| 515 | |
Behdad Esfahbod | 014c502 | 2019-01-09 09:07:01 -0800 | [diff] [blame] | 516 | /* hb_zip() */ |
Behdad Esfahbod | 7557e34 | 2018-12-21 17:21:19 -0500 | [diff] [blame] | 517 | |
Behdad Esfahbod | 84e5d00 | 2019-01-08 23:57:16 -0800 | [diff] [blame] | 518 | template <typename A, typename B> |
Behdad Esfahbod | 200cdb7 | 2019-01-09 09:49:12 -0800 | [diff] [blame] | 519 | struct hb_zip_iter_t : |
Behdad Esfahbod | e799004 | 2019-01-29 17:15:12 -0800 | [diff] [blame] | 520 | hb_iter_t<hb_zip_iter_t<A, B>, |
Ebrahim Byagowi | 9258878 | 2019-04-30 13:05:10 -0700 | [diff] [blame] | 521 | hb_pair_t<typename A::item_t, typename B::item_t>> |
Behdad Esfahbod | 84e5d00 | 2019-01-08 23:57:16 -0800 | [diff] [blame] | 522 | { |
Behdad Esfahbod | 200cdb7 | 2019-01-09 09:49:12 -0800 | [diff] [blame] | 523 | hb_zip_iter_t () {} |
Behdad Esfahbod | b8b3b3e | 2019-02-15 16:05:36 -0800 | [diff] [blame] | 524 | hb_zip_iter_t (const A& a, const B& b) : a (a), b (b) {} |
Behdad Esfahbod | 84e5d00 | 2019-01-08 23:57:16 -0800 | [diff] [blame] | 525 | |
| 526 | typedef hb_pair_t<typename A::item_t, typename B::item_t> __item_t__; |
Behdad Esfahbod | 090fe56 | 2019-01-25 15:34:03 +0100 | [diff] [blame] | 527 | static constexpr bool is_random_access_iterator = |
Behdad Esfahbod | e799004 | 2019-01-29 17:15:12 -0800 | [diff] [blame] | 528 | A::is_random_access_iterator && |
| 529 | B::is_random_access_iterator; |
Behdad Esfahbod | 889dc1e | 2019-05-14 22:28:07 -0700 | [diff] [blame] | 530 | /* Note. The following categorization is only valid if A is strictly sorted, |
| 531 | * ie. does NOT have duplicates. Previously I tried to categorize sortedness |
| 532 | * more granularly, see commits: |
| 533 | * |
| 534 | * 513762849a683914fc266a17ddf38f133cccf072 |
| 535 | * 4d3cf2adb669c345cc43832d11689271995e160a |
| 536 | * |
| 537 | * However, that was not enough, since hb_sorted_array_t, hb_sorted_vector_t, |
| 538 | * SortedArrayOf, etc all needed to be updated to add more variants. At that |
| 539 | * point I saw it not worth the effort, and instead we now deem all sorted |
| 540 | * collections as essentially strictly-sorted for the purposes of zip. |
| 541 | * |
| 542 | * The above assumption is not as bad as it sounds. Our "sorted" comes with |
| 543 | * no guarantees. It's just a contract, put in place to help you remember, |
| 544 | * and think about, whether an iterator you receive is expected to be |
| 545 | * sorted or not. As such, it's not perfect by definition, and should not |
| 546 | * be treated so. The inaccuracy here just errs in the direction of being |
| 547 | * more permissive, so your code compiles instead of erring on the side of |
| 548 | * marking your zipped iterator unsorted in which case your code won't |
| 549 | * compile. |
| 550 | * |
| 551 | * This semantical limitation does NOT affect logic in any other place I |
| 552 | * know of as of this writing. |
| 553 | */ |
| 554 | static constexpr bool is_sorted_iterator = A::is_sorted_iterator; |
Behdad Esfahbod | 5137628 | 2019-05-13 15:36:14 -0700 | [diff] [blame] | 555 | |
Behdad Esfahbod | 84e5d00 | 2019-01-08 23:57:16 -0800 | [diff] [blame] | 556 | __item_t__ __item__ () const { return __item_t__ (*a, *b); } |
| 557 | __item_t__ __item_at__ (unsigned i) const { return __item_t__ (a[i], b[i]); } |
Behdad Esfahbod | 57a5256 | 2019-05-09 11:30:27 -0700 | [diff] [blame] | 558 | bool __more__ () const { return bool (a) && bool (b); } |
Behdad Esfahbod | 41248cc | 2019-05-07 20:54:31 -0700 | [diff] [blame] | 559 | unsigned __len__ () const { return hb_min (a.len (), b.len ()); } |
Behdad Esfahbod | 84e5d00 | 2019-01-08 23:57:16 -0800 | [diff] [blame] | 560 | void __next__ () { ++a; ++b; } |
| 561 | void __forward__ (unsigned n) { a += n; b += n; } |
| 562 | void __prev__ () { --a; --b; } |
| 563 | void __rewind__ (unsigned n) { a -= n; b -= n; } |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 564 | hb_zip_iter_t __end__ () const { return hb_zip_iter_t (a.end (), b.end ()); } |
Behdad Esfahbod | ebf47a9 | 2019-05-15 15:14:26 -0700 | [diff] [blame] | 565 | /* Note, we should stop if ANY of the iters reaches end. As such two compare |
| 566 | * unequal if both items are unequal, NOT if either is unequal. */ |
Behdad Esfahbod | 4c2fd05 | 2019-05-06 19:57:15 -0700 | [diff] [blame] | 567 | bool operator != (const hb_zip_iter_t& o) const |
Behdad Esfahbod | 5da3c9c | 2019-05-09 11:30:31 -0700 | [diff] [blame] | 568 | { return a != o.a && b != o.b; } |
Behdad Esfahbod | 84e5d00 | 2019-01-08 23:57:16 -0800 | [diff] [blame] | 569 | |
| 570 | private: |
| 571 | A a; |
| 572 | B b; |
| 573 | }; |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 574 | struct |
Behdad Esfahbod | 9510e91 | 2019-09-01 16:25:33 -0500 | [diff] [blame] | 575 | { HB_PARTIALIZE(2); |
Behdad Esfahbod | aa4c321 | 2019-02-14 11:07:12 -0800 | [diff] [blame] | 576 | template <typename A, typename B, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 577 | hb_requires (hb_is_iterable (A) && hb_is_iterable (B))> |
Behdad Esfahbod | 5875d77 | 2019-05-08 12:25:34 -0700 | [diff] [blame] | 578 | hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>> |
Behdad Esfahbod | 2c24ea3 | 2019-05-09 11:07:38 -0700 | [diff] [blame] | 579 | operator () (A&& a, B&& b) const |
Behdad Esfahbod | 5875d77 | 2019-05-08 12:25:34 -0700 | [diff] [blame] | 580 | { return hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>> (hb_iter (a), hb_iter (b)); } |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 581 | } |
| 582 | HB_FUNCOBJ (hb_zip); |
Behdad Esfahbod | 84e5d00 | 2019-01-08 23:57:16 -0800 | [diff] [blame] | 583 | |
Behdad Esfahbod | 773d756 | 2019-02-14 11:40:22 -0800 | [diff] [blame] | 584 | /* hb_apply() */ |
| 585 | |
| 586 | template <typename Appl> |
| 587 | struct hb_apply_t |
| 588 | { |
Behdad Esfahbod | 0670e1a | 2019-02-14 11:53:40 -0800 | [diff] [blame] | 589 | hb_apply_t (Appl a) : a (a) {} |
Behdad Esfahbod | 773d756 | 2019-02-14 11:40:22 -0800 | [diff] [blame] | 590 | |
| 591 | template <typename Iter, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 592 | hb_requires (hb_is_iterator (Iter))> |
Behdad Esfahbod | aa4ac13 | 2019-05-08 10:02:30 -0700 | [diff] [blame] | 593 | void operator () (Iter it) |
Behdad Esfahbod | 773d756 | 2019-02-14 11:40:22 -0800 | [diff] [blame] | 594 | { |
| 595 | for (; it; ++it) |
Behdad Esfahbod | b8e763f | 2019-04-16 10:50:22 -0400 | [diff] [blame] | 596 | (void) hb_invoke (a, *it); |
Behdad Esfahbod | 773d756 | 2019-02-14 11:40:22 -0800 | [diff] [blame] | 597 | } |
| 598 | |
| 599 | private: |
| 600 | Appl a; |
| 601 | }; |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 602 | struct |
Behdad Esfahbod | 773d756 | 2019-02-14 11:40:22 -0800 | [diff] [blame] | 603 | { |
| 604 | template <typename Appl> hb_apply_t<Appl> |
| 605 | operator () (Appl&& a) const |
| 606 | { return hb_apply_t<Appl> (a); } |
| 607 | |
| 608 | template <typename Appl> hb_apply_t<Appl&> |
| 609 | operator () (Appl *a) const |
| 610 | { return hb_apply_t<Appl&> (*a); } |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 611 | } |
| 612 | HB_FUNCOBJ (hb_apply); |
Behdad Esfahbod | 773d756 | 2019-02-14 11:40:22 -0800 | [diff] [blame] | 613 | |
Behdad Esfahbod | b1378d8 | 2019-08-30 12:10:45 -0500 | [diff] [blame] | 614 | /* hb_range()/hb_iota()/hb_repeat() */ |
Behdad Esfahbod | 50dc3e7 | 2019-05-08 10:35:02 -0700 | [diff] [blame] | 615 | |
| 616 | template <typename T, typename S> |
Behdad Esfahbod | 814dc3c | 2019-08-30 10:20:30 -0500 | [diff] [blame] | 617 | struct hb_range_iter_t : |
| 618 | hb_iter_t<hb_range_iter_t<T, S>, T> |
Behdad Esfahbod | 50dc3e7 | 2019-05-08 10:35:02 -0700 | [diff] [blame] | 619 | { |
Behdad Esfahbod | 814dc3c | 2019-08-30 10:20:30 -0500 | [diff] [blame] | 620 | hb_range_iter_t (T start, T end_, S step) : v (start), end_ (end_for (start, end_, step)), step (step) {} |
Behdad Esfahbod | 50dc3e7 | 2019-05-08 10:35:02 -0700 | [diff] [blame] | 621 | |
| 622 | typedef T __item_t__; |
| 623 | static constexpr bool is_random_access_iterator = true; |
Behdad Esfahbod | 889dc1e | 2019-05-14 22:28:07 -0700 | [diff] [blame] | 624 | static constexpr bool is_sorted_iterator = true; |
Behdad Esfahbod | de45775 | 2019-08-30 12:02:46 -0500 | [diff] [blame] | 625 | __item_t__ __item__ () const { return hb_ridentity (v); } |
Behdad Esfahbod | 50dc3e7 | 2019-05-08 10:35:02 -0700 | [diff] [blame] | 626 | __item_t__ __item_at__ (unsigned j) const { return v + j * step; } |
Behdad Esfahbod | 71537f9 | 2019-05-09 10:46:49 -0700 | [diff] [blame] | 627 | bool __more__ () const { return v != end_; } |
Behdad Esfahbod | 4f2ad75 | 2019-05-09 12:07:45 -0700 | [diff] [blame] | 628 | unsigned __len__ () const { return !step ? UINT_MAX : (end_ - v) / step; } |
Behdad Esfahbod | 50dc3e7 | 2019-05-08 10:35:02 -0700 | [diff] [blame] | 629 | void __next__ () { v += step; } |
| 630 | void __forward__ (unsigned n) { v += n * step; } |
| 631 | void __prev__ () { v -= step; } |
| 632 | void __rewind__ (unsigned n) { v -= n * step; } |
Behdad Esfahbod | 814dc3c | 2019-08-30 10:20:30 -0500 | [diff] [blame] | 633 | hb_range_iter_t __end__ () const { return hb_range_iter_t (end_, end_, step); } |
| 634 | bool operator != (const hb_range_iter_t& o) const |
Behdad Esfahbod | ebf47a9 | 2019-05-15 15:14:26 -0700 | [diff] [blame] | 635 | { return v != o.v; } |
Behdad Esfahbod | 50dc3e7 | 2019-05-08 10:35:02 -0700 | [diff] [blame] | 636 | |
| 637 | private: |
Behdad Esfahbod | 12dd56f | 2019-05-09 11:25:02 -0700 | [diff] [blame] | 638 | static inline T end_for (T start, T end_, S step) |
Behdad Esfahbod | 50dc3e7 | 2019-05-08 10:35:02 -0700 | [diff] [blame] | 639 | { |
Behdad Esfahbod | 12dd56f | 2019-05-09 11:25:02 -0700 | [diff] [blame] | 640 | if (!step) |
| 641 | return end_; |
Behdad Esfahbod | 71537f9 | 2019-05-09 10:46:49 -0700 | [diff] [blame] | 642 | auto res = (end_ - start) % step; |
Behdad Esfahbod | 50dc3e7 | 2019-05-08 10:35:02 -0700 | [diff] [blame] | 643 | if (!res) |
Behdad Esfahbod | 71537f9 | 2019-05-09 10:46:49 -0700 | [diff] [blame] | 644 | return end_; |
| 645 | end_ += step - res; |
| 646 | return end_; |
Behdad Esfahbod | 50dc3e7 | 2019-05-08 10:35:02 -0700 | [diff] [blame] | 647 | } |
| 648 | |
| 649 | private: |
| 650 | T v; |
Behdad Esfahbod | 71537f9 | 2019-05-09 10:46:49 -0700 | [diff] [blame] | 651 | T end_; |
Behdad Esfahbod | 50dc3e7 | 2019-05-08 10:35:02 -0700 | [diff] [blame] | 652 | S step; |
| 653 | }; |
| 654 | struct |
| 655 | { |
Behdad Esfahbod | 814dc3c | 2019-08-30 10:20:30 -0500 | [diff] [blame] | 656 | template <typename T = unsigned> hb_range_iter_t<T, unsigned> |
Behdad Esfahbod | 7675d0d | 2019-05-09 11:02:56 -0700 | [diff] [blame] | 657 | operator () (T end = (unsigned) -1) const |
Behdad Esfahbod | 814dc3c | 2019-08-30 10:20:30 -0500 | [diff] [blame] | 658 | { return hb_range_iter_t<T, unsigned> (0, end, 1u); } |
Behdad Esfahbod | 7675d0d | 2019-05-09 11:02:56 -0700 | [diff] [blame] | 659 | |
Behdad Esfahbod | 814dc3c | 2019-08-30 10:20:30 -0500 | [diff] [blame] | 660 | template <typename T, typename S = unsigned> hb_range_iter_t<T, S> |
Behdad Esfahbod | 966a18b | 2019-08-30 12:07:17 -0500 | [diff] [blame] | 661 | operator () (T start, T end, S step = 1u) const |
Behdad Esfahbod | 814dc3c | 2019-08-30 10:20:30 -0500 | [diff] [blame] | 662 | { return hb_range_iter_t<T, S> (start, end, step); } |
Behdad Esfahbod | 7675d0d | 2019-05-09 11:02:56 -0700 | [diff] [blame] | 663 | } |
| 664 | HB_FUNCOBJ (hb_range); |
Behdad Esfahbod | 50dc3e7 | 2019-05-08 10:35:02 -0700 | [diff] [blame] | 665 | |
Behdad Esfahbod | ce4d63b | 2019-08-30 11:59:50 -0500 | [diff] [blame] | 666 | template <typename T, typename S> |
| 667 | struct hb_iota_iter_t : |
Behdad Esfahbod | 1f88dae | 2019-08-31 12:24:42 -0500 | [diff] [blame] | 668 | hb_iter_with_fallback_t<hb_iota_iter_t<T, S>, T> |
Behdad Esfahbod | ce4d63b | 2019-08-30 11:59:50 -0500 | [diff] [blame] | 669 | { |
| 670 | hb_iota_iter_t (T start, S step) : v (start), step (step) {} |
| 671 | |
Behdad Esfahbod | 1f88dae | 2019-08-31 12:24:42 -0500 | [diff] [blame] | 672 | private: |
| 673 | |
| 674 | template <typename S2 = S> |
| 675 | auto |
Behdad Esfahbod | 875131d | 2019-08-31 12:42:52 -0500 | [diff] [blame] | 676 | inc (hb_type_identity<S2> s, hb_priority<1>) |
Behdad Esfahbod | 6d555ce | 2021-11-02 00:18:22 -0600 | [diff] [blame^] | 677 | -> hb_void_t<decltype (hb_invoke (std::forward<S2> (s), hb_declval<T&> ()))> |
| 678 | { v = hb_invoke (std::forward<S2> (s), v); } |
Behdad Esfahbod | 1f88dae | 2019-08-31 12:24:42 -0500 | [diff] [blame] | 679 | |
| 680 | void |
| 681 | inc (S s, hb_priority<0>) |
| 682 | { v += s; } |
| 683 | |
| 684 | public: |
| 685 | |
Behdad Esfahbod | ce4d63b | 2019-08-30 11:59:50 -0500 | [diff] [blame] | 686 | typedef T __item_t__; |
| 687 | static constexpr bool is_random_access_iterator = true; |
| 688 | static constexpr bool is_sorted_iterator = true; |
Behdad Esfahbod | de45775 | 2019-08-30 12:02:46 -0500 | [diff] [blame] | 689 | __item_t__ __item__ () const { return hb_ridentity (v); } |
Behdad Esfahbod | ce4d63b | 2019-08-30 11:59:50 -0500 | [diff] [blame] | 690 | bool __more__ () const { return true; } |
| 691 | unsigned __len__ () const { return UINT_MAX; } |
Behdad Esfahbod | 1f88dae | 2019-08-31 12:24:42 -0500 | [diff] [blame] | 692 | void __next__ () { inc (step, hb_prioritize); } |
Behdad Esfahbod | ce4d63b | 2019-08-30 11:59:50 -0500 | [diff] [blame] | 693 | void __prev__ () { v -= step; } |
Behdad Esfahbod | b1378d8 | 2019-08-30 12:10:45 -0500 | [diff] [blame] | 694 | hb_iota_iter_t __end__ () const { return *this; } |
Behdad Esfahbod | ce4d63b | 2019-08-30 11:59:50 -0500 | [diff] [blame] | 695 | bool operator != (const hb_iota_iter_t& o) const { return true; } |
| 696 | |
| 697 | private: |
| 698 | T v; |
| 699 | S step; |
| 700 | }; |
Behdad Esfahbod | 814dc3c | 2019-08-30 10:20:30 -0500 | [diff] [blame] | 701 | struct |
| 702 | { |
Behdad Esfahbod | ce4d63b | 2019-08-30 11:59:50 -0500 | [diff] [blame] | 703 | template <typename T = unsigned, typename S = unsigned> hb_iota_iter_t<T, S> |
Behdad Esfahbod | 966a18b | 2019-08-30 12:07:17 -0500 | [diff] [blame] | 704 | operator () (T start = 0u, S step = 1u) const |
Behdad Esfahbod | ce4d63b | 2019-08-30 11:59:50 -0500 | [diff] [blame] | 705 | { return hb_iota_iter_t<T, S> (start, step); } |
Behdad Esfahbod | 814dc3c | 2019-08-30 10:20:30 -0500 | [diff] [blame] | 706 | } |
| 707 | HB_FUNCOBJ (hb_iota); |
| 708 | |
Behdad Esfahbod | b1378d8 | 2019-08-30 12:10:45 -0500 | [diff] [blame] | 709 | template <typename T> |
| 710 | struct hb_repeat_iter_t : |
| 711 | hb_iter_t<hb_repeat_iter_t<T>, T> |
| 712 | { |
| 713 | hb_repeat_iter_t (T value) : v (value) {} |
| 714 | |
| 715 | typedef T __item_t__; |
| 716 | static constexpr bool is_random_access_iterator = true; |
| 717 | static constexpr bool is_sorted_iterator = true; |
| 718 | __item_t__ __item__ () const { return v; } |
| 719 | __item_t__ __item_at__ (unsigned j) const { return v; } |
| 720 | bool __more__ () const { return true; } |
| 721 | unsigned __len__ () const { return UINT_MAX; } |
| 722 | void __next__ () {} |
| 723 | void __forward__ (unsigned) {} |
| 724 | void __prev__ () {} |
| 725 | void __rewind__ (unsigned) {} |
| 726 | hb_repeat_iter_t __end__ () const { return *this; } |
| 727 | bool operator != (const hb_repeat_iter_t& o) const { return true; } |
| 728 | |
| 729 | private: |
| 730 | T v; |
| 731 | }; |
| 732 | struct |
| 733 | { |
| 734 | template <typename T> hb_repeat_iter_t<T> |
| 735 | operator () (T value) const |
| 736 | { return hb_repeat_iter_t<T> (value); } |
| 737 | } |
| 738 | HB_FUNCOBJ (hb_repeat); |
| 739 | |
Behdad Esfahbod | 875131d | 2019-08-31 12:42:52 -0500 | [diff] [blame] | 740 | /* hb_enumerate()/hb_take() */ |
Behdad Esfahbod | 2c24ea3 | 2019-05-09 11:07:38 -0700 | [diff] [blame] | 741 | |
| 742 | struct |
| 743 | { |
| 744 | template <typename Iterable, |
| 745 | typename Index = unsigned, |
| 746 | hb_requires (hb_is_iterable (Iterable))> |
| 747 | auto operator () (Iterable&& it, Index start = 0u) const HB_AUTO_RETURN |
| 748 | ( hb_zip (hb_iota (start), it) ) |
| 749 | } |
| 750 | HB_FUNCOBJ (hb_enumerate); |
Behdad Esfahbod | 67ec9fa | 2019-08-31 14:51:49 -0500 | [diff] [blame] | 751 | |
Behdad Esfahbod | 875131d | 2019-08-31 12:42:52 -0500 | [diff] [blame] | 752 | struct |
| 753 | { HB_PARTIALIZE(2); |
| 754 | template <typename Iterable, |
| 755 | hb_requires (hb_is_iterable (Iterable))> |
| 756 | auto operator () (Iterable&& it, unsigned count) const HB_AUTO_RETURN |
| 757 | ( hb_zip (hb_range (count), it) | hb_map (hb_second) ) |
Behdad Esfahbod | 5828d8e | 2019-08-31 14:36:44 -0500 | [diff] [blame] | 758 | |
| 759 | /* Specialization arrays. */ |
| 760 | |
| 761 | template <typename Type> inline hb_array_t<Type> |
| 762 | operator () (hb_array_t<Type> array, unsigned count) const |
| 763 | { return array.sub_array (0, count); } |
| 764 | |
| 765 | template <typename Type> inline hb_sorted_array_t<Type> |
| 766 | operator () (hb_sorted_array_t<Type> array, unsigned count) const |
| 767 | { return array.sub_array (0, count); } |
Behdad Esfahbod | 875131d | 2019-08-31 12:42:52 -0500 | [diff] [blame] | 768 | } |
| 769 | HB_FUNCOBJ (hb_take); |
Behdad Esfahbod | 2c24ea3 | 2019-05-09 11:07:38 -0700 | [diff] [blame] | 770 | |
Behdad Esfahbod | 67ec9fa | 2019-08-31 14:51:49 -0500 | [diff] [blame] | 771 | struct |
| 772 | { HB_PARTIALIZE(2); |
| 773 | template <typename Iter, |
| 774 | hb_requires (hb_is_iterator (Iter))> |
| 775 | auto operator () (Iter it, unsigned count) const HB_AUTO_RETURN |
| 776 | ( |
Behdad Esfahbod | c9eb913 | 2019-08-31 15:21:02 -0500 | [diff] [blame] | 777 | + hb_iota (it, hb_add (count)) |
| 778 | | hb_map (hb_take (count)) |
Behdad Esfahbod | 67ec9fa | 2019-08-31 14:51:49 -0500 | [diff] [blame] | 779 | | hb_take ((hb_len (it) + count - 1) / count) |
| 780 | ) |
| 781 | } |
| 782 | HB_FUNCOBJ (hb_chop); |
| 783 | |
Behdad Esfahbod | b702a0c | 2019-02-14 10:39:58 -0800 | [diff] [blame] | 784 | /* hb_sink() */ |
| 785 | |
| 786 | template <typename Sink> |
| 787 | struct hb_sink_t |
| 788 | { |
Behdad Esfahbod | 8479eb5 | 2019-05-08 09:48:55 -0700 | [diff] [blame] | 789 | hb_sink_t (Sink s) : s (s) {} |
Behdad Esfahbod | b702a0c | 2019-02-14 10:39:58 -0800 | [diff] [blame] | 790 | |
Behdad Esfahbod | 5fa52e6 | 2019-02-14 10:51:02 -0800 | [diff] [blame] | 791 | template <typename Iter, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 792 | hb_requires (hb_is_iterator (Iter))> |
Behdad Esfahbod | aa4ac13 | 2019-05-08 10:02:30 -0700 | [diff] [blame] | 793 | void operator () (Iter it) |
Behdad Esfahbod | b702a0c | 2019-02-14 10:39:58 -0800 | [diff] [blame] | 794 | { |
Behdad Esfahbod | 5fa52e6 | 2019-02-14 10:51:02 -0800 | [diff] [blame] | 795 | for (; it; ++it) |
Behdad Esfahbod | b702a0c | 2019-02-14 10:39:58 -0800 | [diff] [blame] | 796 | s << *it; |
| 797 | } |
| 798 | |
| 799 | private: |
| 800 | Sink s; |
| 801 | }; |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 802 | struct |
Behdad Esfahbod | b530573 | 2019-02-14 11:00:10 -0800 | [diff] [blame] | 803 | { |
| 804 | template <typename Sink> hb_sink_t<Sink> |
| 805 | operator () (Sink&& s) const |
| 806 | { return hb_sink_t<Sink> (s); } |
Behdad Esfahbod | f8fcfb2 | 2019-02-14 11:03:29 -0800 | [diff] [blame] | 807 | |
| 808 | template <typename Sink> hb_sink_t<Sink&> |
| 809 | operator () (Sink *s) const |
| 810 | { return hb_sink_t<Sink&> (*s); } |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 811 | } |
| 812 | HB_FUNCOBJ (hb_sink); |
Behdad Esfahbod | b702a0c | 2019-02-14 10:39:58 -0800 | [diff] [blame] | 813 | |
Behdad Esfahbod | 6237b47 | 2019-03-29 21:36:49 -0700 | [diff] [blame] | 814 | /* hb-drain: hb_sink to void / blackhole / /dev/null. */ |
| 815 | |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 816 | struct |
Behdad Esfahbod | fa35d3f | 2019-02-14 14:04:05 -0800 | [diff] [blame] | 817 | { |
| 818 | template <typename Iter, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 819 | hb_requires (hb_is_iterator (Iter))> |
| 820 | void operator () (Iter it) const |
Behdad Esfahbod | fa35d3f | 2019-02-14 14:04:05 -0800 | [diff] [blame] | 821 | { |
| 822 | for (; it; ++it) |
| 823 | (void) *it; |
| 824 | } |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 825 | } |
| 826 | HB_FUNCOBJ (hb_drain); |
Behdad Esfahbod | 014c502 | 2019-01-09 09:07:01 -0800 | [diff] [blame] | 827 | |
Behdad Esfahbod | 6237b47 | 2019-03-29 21:36:49 -0700 | [diff] [blame] | 828 | /* hb_unzip(): unzip and sink to two sinks. */ |
| 829 | |
| 830 | template <typename Sink1, typename Sink2> |
| 831 | struct hb_unzip_t |
| 832 | { |
Behdad Esfahbod | aa4ac13 | 2019-05-08 10:02:30 -0700 | [diff] [blame] | 833 | hb_unzip_t (Sink1 s1, Sink2 s2) : s1 (s1), s2 (s2) {} |
Behdad Esfahbod | 6237b47 | 2019-03-29 21:36:49 -0700 | [diff] [blame] | 834 | |
| 835 | template <typename Iter, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 836 | hb_requires (hb_is_iterator (Iter))> |
Behdad Esfahbod | aa4ac13 | 2019-05-08 10:02:30 -0700 | [diff] [blame] | 837 | void operator () (Iter it) |
Behdad Esfahbod | 6237b47 | 2019-03-29 21:36:49 -0700 | [diff] [blame] | 838 | { |
| 839 | for (; it; ++it) |
| 840 | { |
| 841 | const auto &v = *it; |
| 842 | s1 << v.first; |
| 843 | s2 << v.second; |
| 844 | } |
| 845 | } |
| 846 | |
| 847 | private: |
| 848 | Sink1 s1; |
| 849 | Sink2 s2; |
| 850 | }; |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 851 | struct |
Behdad Esfahbod | 6237b47 | 2019-03-29 21:36:49 -0700 | [diff] [blame] | 852 | { |
| 853 | template <typename Sink1, typename Sink2> hb_unzip_t<Sink1, Sink2> |
| 854 | operator () (Sink1&& s1, Sink2&& s2) const |
| 855 | { return hb_unzip_t<Sink1, Sink2> (s1, s2); } |
| 856 | |
| 857 | template <typename Sink1, typename Sink2> hb_unzip_t<Sink1&, Sink2&> |
| 858 | operator () (Sink1 *s1, Sink2 *s2) const |
| 859 | { return hb_unzip_t<Sink1&, Sink2&> (*s1, *s2); } |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 860 | } |
| 861 | HB_FUNCOBJ (hb_unzip); |
Behdad Esfahbod | 6237b47 | 2019-03-29 21:36:49 -0700 | [diff] [blame] | 862 | |
| 863 | |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 864 | /* hb-all, hb-any, hb-none. */ |
| 865 | |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 866 | struct |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 867 | { |
| 868 | template <typename Iterable, |
Behdad Esfahbod | 710d459 | 2019-05-08 09:33:09 -0700 | [diff] [blame] | 869 | typename Pred = decltype ((hb_identity)), |
Behdad Esfahbod | bdbfdc9 | 2019-05-07 22:52:43 -0700 | [diff] [blame] | 870 | typename Proj = decltype ((hb_identity)), |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 871 | hb_requires (hb_is_iterable (Iterable))> |
Behdad Esfahbod | bdbfdc9 | 2019-05-07 22:52:43 -0700 | [diff] [blame] | 872 | bool operator () (Iterable&& c, |
Behdad Esfahbod | 710d459 | 2019-05-08 09:33:09 -0700 | [diff] [blame] | 873 | Pred&& p = hb_identity, |
Behdad Esfahbod | bdbfdc9 | 2019-05-07 22:52:43 -0700 | [diff] [blame] | 874 | Proj&& f = hb_identity) const |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 875 | { |
| 876 | for (auto it = hb_iter (c); it; ++it) |
Behdad Esfahbod | 6d555ce | 2021-11-02 00:18:22 -0600 | [diff] [blame^] | 877 | if (!hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it))) |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 878 | return false; |
| 879 | return true; |
| 880 | } |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 881 | } |
| 882 | HB_FUNCOBJ (hb_all); |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 883 | struct |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 884 | { |
| 885 | template <typename Iterable, |
Behdad Esfahbod | 710d459 | 2019-05-08 09:33:09 -0700 | [diff] [blame] | 886 | typename Pred = decltype ((hb_identity)), |
Behdad Esfahbod | bdbfdc9 | 2019-05-07 22:52:43 -0700 | [diff] [blame] | 887 | typename Proj = decltype ((hb_identity)), |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 888 | hb_requires (hb_is_iterable (Iterable))> |
Behdad Esfahbod | bdbfdc9 | 2019-05-07 22:52:43 -0700 | [diff] [blame] | 889 | bool operator () (Iterable&& c, |
Behdad Esfahbod | 710d459 | 2019-05-08 09:33:09 -0700 | [diff] [blame] | 890 | Pred&& p = hb_identity, |
Behdad Esfahbod | bdbfdc9 | 2019-05-07 22:52:43 -0700 | [diff] [blame] | 891 | Proj&& f = hb_identity) const |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 892 | { |
| 893 | for (auto it = hb_iter (c); it; ++it) |
Behdad Esfahbod | 6d555ce | 2021-11-02 00:18:22 -0600 | [diff] [blame^] | 894 | if (hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it))) |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 895 | return true; |
| 896 | return false; |
| 897 | } |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 898 | } |
| 899 | HB_FUNCOBJ (hb_any); |
Behdad Esfahbod | 02d864a | 2019-04-15 15:39:03 -0400 | [diff] [blame] | 900 | struct |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 901 | { |
| 902 | template <typename Iterable, |
Behdad Esfahbod | 710d459 | 2019-05-08 09:33:09 -0700 | [diff] [blame] | 903 | typename Pred = decltype ((hb_identity)), |
Behdad Esfahbod | bdbfdc9 | 2019-05-07 22:52:43 -0700 | [diff] [blame] | 904 | typename Proj = decltype ((hb_identity)), |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 905 | hb_requires (hb_is_iterable (Iterable))> |
Behdad Esfahbod | bdbfdc9 | 2019-05-07 22:52:43 -0700 | [diff] [blame] | 906 | bool operator () (Iterable&& c, |
Behdad Esfahbod | 710d459 | 2019-05-08 09:33:09 -0700 | [diff] [blame] | 907 | Pred&& p = hb_identity, |
Behdad Esfahbod | bdbfdc9 | 2019-05-07 22:52:43 -0700 | [diff] [blame] | 908 | Proj&& f = hb_identity) const |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 909 | { |
| 910 | for (auto it = hb_iter (c); it; ++it) |
Behdad Esfahbod | 6d555ce | 2021-11-02 00:18:22 -0600 | [diff] [blame^] | 911 | if (hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it))) |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 912 | return false; |
| 913 | return true; |
| 914 | } |
Behdad Esfahbod | 7654ebe | 2019-05-07 16:53:03 -0700 | [diff] [blame] | 915 | } |
| 916 | HB_FUNCOBJ (hb_none); |
Behdad Esfahbod | 77060bc | 2019-02-15 16:55:08 -0800 | [diff] [blame] | 917 | |
Behdad Esfahbod | 014c502 | 2019-01-09 09:07:01 -0800 | [diff] [blame] | 918 | /* |
| 919 | * Algorithms operating on iterators. |
| 920 | */ |
| 921 | |
| 922 | template <typename C, typename V, |
Behdad Esfahbod | af571db | 2019-05-07 21:39:20 -0700 | [diff] [blame] | 923 | hb_requires (hb_is_iterable (C))> |
Behdad Esfahbod | 014c502 | 2019-01-09 09:07:01 -0800 | [diff] [blame] | 924 | inline void |
Behdad Esfahbod | 5fce889 | 2021-01-21 12:14:20 -0700 | [diff] [blame] | 925 | hb_fill (C&& c, const V &v) |
Behdad Esfahbod | 014c502 | 2019-01-09 09:07:01 -0800 | [diff] [blame] | 926 | { |
Behdad Esfahbod | 5b99c92 | 2019-02-14 17:10:04 -0800 | [diff] [blame] | 927 | for (auto i = hb_iter (c); i; i++) |
Behdad Esfahbod | 4c38a9f | 2019-03-29 20:23:07 -0700 | [diff] [blame] | 928 | *i = v; |
Behdad Esfahbod | 014c502 | 2019-01-09 09:07:01 -0800 | [diff] [blame] | 929 | } |
| 930 | |
Behdad Esfahbod | 8a8d45b | 2019-03-31 19:00:09 -0700 | [diff] [blame] | 931 | template <typename S, typename D> |
| 932 | inline void |
Behdad Esfahbod | 78fc43f | 2019-03-31 19:17:07 -0700 | [diff] [blame] | 933 | hb_copy (S&& is, D&& id) |
Behdad Esfahbod | 014c502 | 2019-01-09 09:07:01 -0800 | [diff] [blame] | 934 | { |
Behdad Esfahbod | 78fc43f | 2019-03-31 19:17:07 -0700 | [diff] [blame] | 935 | hb_iter (is) | hb_sink (id); |
Behdad Esfahbod | 014c502 | 2019-01-09 09:07:01 -0800 | [diff] [blame] | 936 | } |
| 937 | |
| 938 | |
Behdad Esfahbod | b80b97b | 2018-12-21 00:08:05 -0500 | [diff] [blame] | 939 | #endif /* HB_ITER_HH */ |