blob: 87b8ed880d2d9e94ca343c0d733e3edd96caddc8 [file] [log] [blame]
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -05001/*
2 * Copyright © 2018 Google, Inc.
Behdad Esfahbod89fea212019-04-15 17:36:09 -04003 * Copyright © 2019 Facebook, Inc.
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -05004 *
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 Esfahbod02d864a2019-04-15 15:39:03 -040026 * Facebook Author(s): Behdad Esfahbod
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -050027 */
28
29#ifndef HB_ITER_HH
30#define HB_ITER_HH
31
32#include "hb.hh"
Behdad Esfahboda3fcb9a2019-04-16 10:45:20 -040033#include "hb-algs.hh"
Behdad Esfahbode76a3ca2018-12-27 17:23:12 -050034#include "hb-meta.hh"
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -050035
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 Esfahbod314d8692018-12-21 00:54:55 -050041 * hb_iter_tator objects are small, light-weight, objects that can be
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -050042 * copied by value. If the collection / object being iterated on
Behdad Esfahbod314d8692018-12-21 00:54:55 -050043 * is writable, then the iterator returns lvalues, otherwise it
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -050044 * returns rvalues.
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -070045 *
46 * TODO Document more.
47 *
48 * If iterator implementation implements operator!=, then can be
Behdad Esfahbodbb48bf52021-07-08 10:53:45 -060049 * used in range-based for loop. That already happens if the iterator
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -070050 * 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 Esfahbodb80b97b2018-12-21 00:08:05 -050056 */
57
Behdad Esfahbod8c6cbbd2018-12-28 14:29:09 -050058/*
59 * Base classes for iterators.
60 */
61
Behdad Esfahbod314d8692018-12-21 00:54:55 -050062/* Base class for all iterators. */
Behdad Esfahbod6b6783e2019-01-26 22:44:09 +010063template <typename iter_t, typename Item = typename iter_t::__item_t__>
Behdad Esfahbodcb5011d2019-01-04 11:22:32 -050064struct hb_iter_t
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -050065{
Behdad Esfahbodaeb696a2018-12-21 01:57:02 -050066 typedef Item item_t;
Behdad Esfahbodc72589f2019-08-29 15:45:21 -070067 constexpr unsigned get_item_size () const { return hb_static_size (Item); }
Behdad Esfahbod090fe562019-01-25 15:34:03 +010068 static constexpr bool is_iterator = true;
69 static constexpr bool is_random_access_iterator = false;
Behdad Esfahbod889dc1e2019-05-14 22:28:07 -070070 static constexpr bool is_sorted_iterator = false;
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -050071
Behdad Esfahbod2fc18602018-12-21 18:09:45 -050072 private:
73 /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
Behdad Esfahboda98e4062019-04-12 22:42:44 -040074 const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
Ebrahim Byagowia0b4ac42019-08-24 17:57:14 +043075 iter_t* thiz () { return static_cast< iter_t *> (this); }
Behdad Esfahbod2fc18602018-12-21 18:09:45 -050076 public:
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -050077
Behdad Esfahbod6c548b62019-01-08 13:43:49 -080078 /* TODO:
79 * Port operators below to use hb_enable_if to sniff which method implements
Behdad Esfahbod84a25d72019-01-29 13:39:19 -080080 * an operator and use it, and remove hb_iter_fallback_mixin_t completely. */
Behdad Esfahbod6c548b62019-01-08 13:43:49 -080081
Behdad Esfahbod314d8692018-12-21 00:54:55 -050082 /* Operators. */
Behdad Esfahboda98e4062019-04-12 22:42:44 -040083 iter_t iter () const { return *thiz(); }
84 iter_t operator + () const { return *thiz(); }
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -070085 iter_t begin () const { return *thiz(); }
86 iter_t end () const { return thiz()->__end__ (); }
Behdad Esfahboda98e4062019-04-12 22:42:44 -040087 explicit operator bool () const { return thiz()->__more__ (); }
88 unsigned len () const { return thiz()->__len__ (); }
Behdad Esfahbod2d940942019-01-30 16:03:16 -080089 /* The following can only be enabled if item_t is reference type. Otherwise
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -070090 * it will be returning pointer to temporary rvalue.
91 * TODO Use a wrapper return type to fix for non-reference type. */
Behdad Esfahbod2d940942019-01-30 16:03:16 -080092 template <typename T = item_t,
93 hb_enable_if (hb_is_reference (T))>
Behdad Esfahbod54ece292019-04-16 16:45:53 -040094 hb_remove_reference<item_t>* operator -> () const { return hb_addressof (**thiz()); }
Behdad Esfahboda98e4062019-04-12 22:42:44 -040095 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 Esfahboda66598e2019-05-08 09:56:29 -070099 iter_t& operator += (unsigned count) & { thiz()->__forward__ (count); return *thiz(); }
100 iter_t operator += (unsigned count) && { thiz()->__forward__ (count); return *thiz(); }
Behdad Esfahbodc09d6c52019-05-07 14:09:00 -0700101 iter_t& operator ++ () & { thiz()->__next__ (); return *thiz(); }
102 iter_t operator ++ () && { thiz()->__next__ (); return *thiz(); }
Behdad Esfahboda66598e2019-05-08 09:56:29 -0700103 iter_t& operator -= (unsigned count) & { thiz()->__rewind__ (count); return *thiz(); }
104 iter_t operator -= (unsigned count) && { thiz()->__rewind__ (count); return *thiz(); }
Behdad Esfahbodc09d6c52019-05-07 14:09:00 -0700105 iter_t& operator -- () & { thiz()->__prev__ (); return *thiz(); }
106 iter_t operator -- () && { thiz()->__prev__ (); return *thiz(); }
Behdad Esfahboda98e4062019-04-12 22:42:44 -0400107 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 Esfahbod57795bc2019-01-28 16:23:12 -0500112 template <typename T>
Behdad Esfahboda66598e2019-05-08 09:56:29 -0700113 iter_t& operator >> (T &v) & { v = **thiz(); ++*thiz(); return *thiz(); }
Behdad Esfahbod57795bc2019-01-28 16:23:12 -0500114 template <typename T>
Behdad Esfahboda66598e2019-05-08 09:56:29 -0700115 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 Esfahbodb80b97b2018-12-21 00:08:05 -0500120
Behdad Esfahbod2fc18602018-12-21 18:09:45 -0500121 protected:
Behdad Esfahbodf2442242019-05-15 14:19:20 -0700122 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 Esfahbod2fc18602018-12-21 18:09:45 -0500127};
128
Behdad Esfahbod570473a2018-12-27 13:29:51 -0500129#define HB_ITER_USING(Name) \
Behdad Esfahbodf78f8372019-01-08 16:38:08 -0800130 using item_t = typename Name::item_t; \
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -0700131 using Name::begin; \
132 using Name::end; \
Behdad Esfahbodc72589f2019-08-29 15:45:21 -0700133 using Name::get_item_size; \
Behdad Esfahbod6cd96ba2018-12-30 20:51:31 -0500134 using Name::is_iterator; \
Behdad Esfahbod570473a2018-12-27 13:29:51 -0500135 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 Esfahbod859a8802018-12-30 02:11:03 -0500145 using Name::operator +; \
Behdad Esfahbod570473a2018-12-27 13:29:51 -0500146 using Name::operator -; \
Behdad Esfahbod6521d5b2019-01-29 13:44:39 -0800147 using Name::operator >>; \
148 using Name::operator <<; \
Behdad Esfahbod570473a2018-12-27 13:29:51 -0500149 static_assert (true, "")
150
Behdad Esfahbod5875d772019-05-08 12:25:34 -0700151/* Returns iterator / item type of a type. */
152template <typename Iterable>
153using hb_iter_type = decltype (hb_deref (hb_declval (Iterable)).iter ());
154template <typename Iterable>
155using hb_item_type = decltype (*hb_deref (hb_declval (Iterable)).iter ());
Behdad Esfahbod778c96b2019-01-27 00:50:54 +0100156
Behdad Esfahbod0363ce62019-01-27 01:03:56 +0100157
Behdad Esfahbod0363ce62019-01-27 01:03:56 +0100158template <typename> struct hb_array_t;
Behdad Esfahbod5828d8e2019-08-31 14:36:44 -0500159template <typename> struct hb_sorted_array_t;
Behdad Esfahbod72dd5e32019-02-15 16:11:32 -0800160
Behdad Esfahbod02d864a2019-04-15 15:39:03 -0400161struct
Behdad Esfahbod72dd5e32019-02-15 16:11:32 -0800162{
Behdad Esfahbod5875d772019-05-08 12:25:34 -0700163 template <typename T> hb_iter_type<T>
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800164 operator () (T&& c) const
Behdad Esfahbod6d555ce2021-11-02 00:18:22 -0600165 { return hb_deref (std::forward<T> (c)).iter (); }
Behdad Esfahbod72dd5e32019-02-15 16:11:32 -0800166
167 /* Specialization for C arrays. */
168
169 template <typename Type> inline hb_array_t<Type>
Behdad Esfahboda98e4062019-04-12 22:42:44 -0400170 operator () (Type *array, unsigned int length) const
Behdad Esfahbod72dd5e32019-02-15 16:11:32 -0800171 { return hb_array_t<Type> (array, length); }
172
173 template <typename Type, unsigned int length> hb_array_t<Type>
Behdad Esfahboda98e4062019-04-12 22:42:44 -0400174 operator () (Type (&array)[length]) const
Behdad Esfahbod72dd5e32019-02-15 16:11:32 -0800175 { return hb_array_t<Type> (array, length); }
176
Behdad Esfahbod7654ebe2019-05-07 16:53:03 -0700177}
178HB_FUNCOBJ (hb_iter);
Behdad Esfahbod398b2962019-08-31 12:44:24 -0500179struct
180{
181 template <typename T> unsigned
182 operator () (T&& c) const
183 { return c.len (); }
184
185}
186HB_FUNCOBJ (hb_len);
Behdad Esfahbod0363ce62019-01-27 01:03:56 +0100187
Behdad Esfahbod2fc18602018-12-21 18:09:45 -0500188/* Mixin to fill in what the subclass doesn't provide. */
Behdad Esfahbod636786e2019-01-08 23:48:35 -0800189template <typename iter_t, typename item_t = typename iter_t::__item_t__>
Behdad Esfahbod84a25d72019-01-29 13:39:19 -0800190struct hb_iter_fallback_mixin_t
Behdad Esfahbod2fc18602018-12-21 18:09:45 -0500191{
192 private:
193 /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
Behdad Esfahboda98e4062019-04-12 22:42:44 -0400194 const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
Ebrahim Byagowia0b4ac42019-08-24 17:57:14 +0430195 iter_t* thiz () { return static_cast< iter_t *> (this); }
Behdad Esfahbod2fc18602018-12-21 18:09:45 -0500196 public:
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -0500197
Behdad Esfahbod8001e002018-12-21 01:53:27 -0500198 /* Access: Implement __item__(), or __item_at__() if random-access. */
Behdad Esfahboda98e4062019-04-12 22:42:44 -0400199 item_t __item__ () const { return (*thiz())[0]; }
200 item_t __item_at__ (unsigned i) const { return *(*thiz() + i); }
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -0500201
Behdad Esfahbod2a33ab02018-12-21 18:49:27 -0500202 /* Termination: Implement __more__(), or __len__() if random-access. */
Behdad Esfahbod57a52562019-05-09 11:30:27 -0700203 bool __more__ () const { return bool (thiz()->len ()); }
Behdad Esfahboda98e4062019-04-12 22:42:44 -0400204 unsigned __len__ () const
Behdad Esfahbode98f0dd2019-05-13 13:53:06 -0700205 { iter_t c (*thiz()); unsigned l = 0; while (c) { c++; l++; } return l; }
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -0500206
Behdad Esfahbod314d8692018-12-21 00:54:55 -0500207 /* Advancing: Implement __next__(), or __forward__() if random-access. */
Behdad Esfahboda98e4062019-04-12 22:42:44 -0400208 void __next__ () { *thiz() += 1; }
Behdad Esfahbod606841b2019-05-11 11:54:30 -0700209 void __forward__ (unsigned n) { while (*thiz() && n--) ++*thiz(); }
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -0500210
Behdad Esfahbod19d2b502018-12-21 01:17:35 -0500211 /* Rewinding: Implement __prev__() or __rewind__() if bidirectional. */
Behdad Esfahboda98e4062019-04-12 22:42:44 -0400212 void __prev__ () { *thiz() -= 1; }
Behdad Esfahbod606841b2019-05-11 11:54:30 -0700213 void __rewind__ (unsigned n) { while (*thiz() && n--) --*thiz(); }
Behdad Esfahbod19d2b502018-12-21 01:17:35 -0500214
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -0700215 /* 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 Esfahbodd3976b72018-12-26 18:54:27 -0500227 protected:
Behdad Esfahbodf2442242019-05-15 14:19:20 -0700228 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 Esfahbodb80b97b2018-12-21 00:08:05 -0500233};
234
Behdad Esfahbod849a0f12019-01-29 17:10:19 -0800235template <typename iter_t, typename item_t = typename iter_t::__item_t__>
236struct 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 Esfahbodf2442242019-05-15 14:19:20 -0700241 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 Esfahbod849a0f12019-01-29 17:10:19 -0800246};
247
Behdad Esfahbod8c6cbbd2018-12-28 14:29:09 -0500248/*
249 * Meta-programming predicates.
250 */
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -0500251
Behdad Esfahboded972d52019-05-09 16:58:28 -0700252/* hb_is_iterator() / hb_is_iterator_of() */
253
254template<typename Iter, typename Item>
255struct hb_is_iterator_of
256{
257 template <typename Item2 = Item>
Behdad Esfahbod61d150c2019-05-10 20:06:31 -0700258 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 Esfahboded972d52019-05-09 16:58:28 -0700260
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 Esfahboddf138da2018-12-28 16:29:48 -0500267/* hb_is_iterable() */
268
Behdad Esfahbodd419a9a2019-04-03 14:18:19 -0700269template <typename T>
270struct hb_is_iterable
271{
272 private:
Behdad Esfahbodae8da4b2019-04-22 15:25:11 -0400273
Behdad Esfahbodd419a9a2019-04-03 14:18:19 -0700274 template <typename U>
Behdad Esfahbod61d150c2019-05-10 20:06:31 -0700275 static auto impl (hb_priority<1>) -> decltype (hb_declval (U).iter (), hb_true_type ());
Behdad Esfahbodae8da4b2019-04-22 15:25:11 -0400276
Behdad Esfahbodd419a9a2019-04-03 14:18:19 -0700277 template <typename>
Behdad Esfahbod61d150c2019-05-10 20:06:31 -0700278 static hb_false_type impl (hb_priority<0>);
Behdad Esfahbod8570da12018-12-28 14:40:30 -0500279
Behdad Esfahbodd419a9a2019-04-03 14:18:19 -0700280 public:
Behdad Esfahboded972d52019-05-09 16:58:28 -0700281 static constexpr bool value = decltype (impl<T> (hb_prioritize))::value;
Behdad Esfahbodd419a9a2019-04-03 14:18:19 -0700282};
Behdad Esfahbod8c6cbbd2018-12-28 14:29:09 -0500283#define hb_is_iterable(Iterable) hb_is_iterable<Iterable>::value
284
Behdad Esfahboded972d52019-05-09 16:58:28 -0700285/* hb_is_source_of() / hb_is_sink_of() */
Behdad Esfahbod73c82f22019-04-26 13:16:48 -0700286
Behdad Esfahbod06a44e22018-12-30 18:42:14 -0500287template<typename Iter, typename Item>
Behdad Esfahboded972d52019-05-09 16:58:28 -0700288struct hb_is_source_of
289{
290 private:
291 template <typename Iter2 = Iter,
Behdad Esfahbod19e08a12019-05-10 21:25:07 -0700292 hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<hb_add_const<Item>>))>
Behdad Esfahbod61d150c2019-05-10 20:06:31 -0700293 static hb_true_type impl (hb_priority<2>);
Behdad Esfahbod98974ac2019-05-10 11:18:52 -0700294 template <typename Iter2 = Iter>
Behdad Esfahbod61d150c2019-05-10 20:06:31 -0700295 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 Esfahboddf138da2018-12-28 16:29:48 -0500297
Behdad Esfahboded972d52019-05-09 16:58:28 -0700298 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 Esfahbod2658e402019-01-08 12:53:02 -0800302
Behdad Esfahboded972d52019-05-09 16:58:28 -0700303template<typename Iter, typename Item>
304struct hb_is_sink_of
305{
306 private:
Behdad Esfahbod98974ac2019-05-10 11:18:52 -0700307 template <typename Iter2 = Iter,
Behdad Esfahbod19e08a12019-05-10 21:25:07 -0700308 hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<Item>))>
Behdad Esfahbod61d150c2019-05-10 20:06:31 -0700309 static hb_true_type impl (hb_priority<2>);
Behdad Esfahbod98974ac2019-05-10 11:18:52 -0700310 template <typename Iter2 = Iter>
Behdad Esfahbod61d150c2019-05-10 20:06:31 -0700311 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 Esfahboded972d52019-05-09 16:58:28 -0700313
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 Esfahboddf138da2018-12-28 16:29:48 -0500322
Behdad Esfahbod014c5022019-01-09 09:07:01 -0800323
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -0700324/* Range-based 'for' for iterables. */
325
326template <typename Iterable,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700327 hb_requires (hb_is_iterable (Iterable))>
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -0700328static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ())
329
330template <typename Iterable,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700331 hb_requires (hb_is_iterable (Iterable))>
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -0700332static 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. */
336namespace OT {
337
338template <typename Iterable,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700339 hb_requires (hb_is_iterable (Iterable))>
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -0700340static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ())
341
342template <typename Iterable,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700343 hb_requires (hb_is_iterable (Iterable))>
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -0700344static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ())
345
346}
347
348
Behdad Esfahbod8c6cbbd2018-12-28 14:29:09 -0500349/*
Behdad Esfahbod014c5022019-01-09 09:07:01 -0800350 * Adaptors, combiners, etc.
Behdad Esfahbod8c6cbbd2018-12-28 14:29:09 -0500351 */
Behdad Esfahbod7557e342018-12-21 17:21:19 -0500352
Behdad Esfahbod343f5a42019-01-09 12:35:45 -0800353template <typename Lhs, typename Rhs,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700354 hb_requires (hb_is_iterator (Lhs))>
Behdad Esfahbod6916b772019-04-16 18:33:51 -0400355static inline auto
Behdad Esfahbod6d555ce2021-11-02 00:18:22 -0600356operator | (Lhs&& lhs, Rhs&& rhs) HB_AUTO_RETURN (std::forward<Rhs> (rhs) (std::forward<Lhs> (lhs)))
Behdad Esfahbod343f5a42019-01-09 12:35:45 -0800357
Behdad Esfahbod1733e472019-01-09 11:15:49 -0800358/* hb_map(), hb_filter(), hb_reduce() */
359
Behdad Esfahbod7e020632019-05-13 15:26:00 -0700360enum class hb_function_sortedness_t {
Behdad Esfahbod79126df2019-05-11 11:23:31 -0700361 NOT_SORTED,
362 RETAINS_SORTING,
363 SORTED,
364};
365
Behdad Esfahbod7e020632019-05-13 15:26:00 -0700366template <typename Iter, typename Proj, hb_function_sortedness_t Sorted,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700367 hb_requires (hb_is_iterator (Iter))>
Behdad Esfahbod1733e472019-01-09 11:15:49 -0800368struct hb_map_iter_t :
Behdad Esfahbod79126df2019-05-11 11:23:31 -0700369 hb_iter_t<hb_map_iter_t<Iter, Proj, Sorted>,
Behdad Esfahbodc93eeba2019-05-08 10:56:09 -0700370 decltype (hb_get (hb_declval (Proj), *hb_declval (Iter)))>
Behdad Esfahbod1733e472019-01-09 11:15:49 -0800371{
Behdad Esfahbod025eaa32019-05-07 00:05:37 -0700372 hb_map_iter_t (const Iter& it, Proj f_) : it (it), f (f_) {}
Behdad Esfahbod1733e472019-01-09 11:15:49 -0800373
Behdad Esfahbodc93eeba2019-05-08 10:56:09 -0700374 typedef decltype (hb_get (hb_declval (Proj), *hb_declval (Iter))) __item_t__;
Behdad Esfahbod090fe562019-01-25 15:34:03 +0100375 static constexpr bool is_random_access_iterator = Iter::is_random_access_iterator;
Behdad Esfahbod889dc1e2019-05-14 22:28:07 -0700376 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 Esfahbod025eaa32019-05-07 00:05:37 -0700380 __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 Esfahbod343f5a42019-01-09 12:35:45 -0800382 bool __more__ () const { return bool (it); }
Behdad Esfahbod1733e472019-01-09 11:15:49 -0800383 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 Esfahbod89030402019-05-07 00:13:11 -0700388 hb_map_iter_t __end__ () const { return hb_map_iter_t (it.end (), f); }
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -0700389 bool operator != (const hb_map_iter_t& o) const
Behdad Esfahbodebf47a92019-05-15 15:14:26 -0700390 { return it != o.it; }
Behdad Esfahbod1733e472019-01-09 11:15:49 -0800391
392 private:
393 Iter it;
Behdad Esfahbod025eaa32019-05-07 00:05:37 -0700394 hb_reference_wrapper<Proj> f;
Behdad Esfahbod1733e472019-01-09 11:15:49 -0800395};
Behdad Esfahbod6b6783e2019-01-26 22:44:09 +0100396
Behdad Esfahbod7e020632019-05-13 15:26:00 -0700397template <typename Proj, hb_function_sortedness_t Sorted>
Behdad Esfahbod1733e472019-01-09 11:15:49 -0800398struct hb_map_iter_factory_t
399{
Behdad Esfahbod0670e1a2019-02-14 11:53:40 -0800400 hb_map_iter_factory_t (Proj f) : f (f) {}
Behdad Esfahbod1733e472019-01-09 11:15:49 -0800401
Behdad Esfahbod345bfbb2019-02-14 10:48:20 -0800402 template <typename Iter,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700403 hb_requires (hb_is_iterator (Iter))>
Behdad Esfahbod79126df2019-05-11 11:23:31 -0700404 hb_map_iter_t<Iter, Proj, Sorted>
Behdad Esfahbodaa4ac132019-05-08 10:02:30 -0700405 operator () (Iter it)
Behdad Esfahbod79126df2019-05-11 11:23:31 -0700406 { return hb_map_iter_t<Iter, Proj, Sorted> (it, f); }
Behdad Esfahbod1733e472019-01-09 11:15:49 -0800407
408 private:
409 Proj f;
410};
Behdad Esfahbod02d864a2019-04-15 15:39:03 -0400411struct
Behdad Esfahbod98be7bd2019-02-15 16:09:29 -0800412{
413 template <typename Proj>
Behdad Esfahbod7e020632019-05-13 15:26:00 -0700414 hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED>
Behdad Esfahbod98be7bd2019-02-15 16:09:29 -0800415 operator () (Proj&& f) const
Behdad Esfahbod7e020632019-05-13 15:26:00 -0700416 { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED> (f); }
Behdad Esfahbod7654ebe2019-05-07 16:53:03 -0700417}
418HB_FUNCOBJ (hb_map);
Behdad Esfahbod79126df2019-05-11 11:23:31 -0700419struct
420{
421 template <typename Proj>
Behdad Esfahbod7e020632019-05-13 15:26:00 -0700422 hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING>
Behdad Esfahbod79126df2019-05-11 11:23:31 -0700423 operator () (Proj&& f) const
Behdad Esfahbod7e020632019-05-13 15:26:00 -0700424 { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING> (f); }
Behdad Esfahbod79126df2019-05-11 11:23:31 -0700425}
426HB_FUNCOBJ (hb_map_retains_sorting);
427struct
428{
429 template <typename Proj>
Behdad Esfahbod7e020632019-05-13 15:26:00 -0700430 hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED>
Behdad Esfahbod79126df2019-05-11 11:23:31 -0700431 operator () (Proj&& f) const
Behdad Esfahbod7e020632019-05-13 15:26:00 -0700432 { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED> (f); }
Behdad Esfahbod79126df2019-05-11 11:23:31 -0700433}
434HB_FUNCOBJ (hb_map_sorted);
Behdad Esfahbod1733e472019-01-09 11:15:49 -0800435
Behdad Esfahbodf35568d2019-01-09 11:32:33 -0800436template <typename Iter, typename Pred, typename Proj,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700437 hb_requires (hb_is_iterator (Iter))>
Behdad Esfahbodf35568d2019-01-09 11:32:33 -0800438struct hb_filter_iter_t :
Behdad Esfahbod849a0f12019-01-29 17:10:19 -0800439 hb_iter_with_fallback_t<hb_filter_iter_t<Iter, Pred, Proj>,
440 typename Iter::item_t>
Behdad Esfahbodf35568d2019-01-09 11:32:33 -0800441{
Behdad Esfahbod025eaa32019-05-07 00:05:37 -0700442 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 Esfahbodf35568d2019-01-09 11:32:33 -0800444
445 typedef typename Iter::item_t __item_t__;
Behdad Esfahbod889dc1e2019-05-14 22:28:07 -0700446 static constexpr bool is_sorted_iterator = Iter::is_sorted_iterator;
Behdad Esfahbodf35568d2019-01-09 11:32:33 -0800447 __item_t__ __item__ () const { return *it; }
Behdad Esfahbod343f5a42019-01-09 12:35:45 -0800448 bool __more__ () const { return bool (it); }
Behdad Esfahbod025eaa32019-05-07 00:05:37 -0700449 void __next__ () { do ++it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); }
David Corbettc1c122e2019-05-11 11:38:06 -0400450 void __prev__ () { do --it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); }
Behdad Esfahbod89030402019-05-07 00:13:11 -0700451 hb_filter_iter_t __end__ () const { return hb_filter_iter_t (it.end (), p, f); }
Behdad Esfahbod4c2fd052019-05-06 19:57:15 -0700452 bool operator != (const hb_filter_iter_t& o) const
Behdad Esfahbodebf47a92019-05-15 15:14:26 -0700453 { return it != o.it; }
Behdad Esfahbodf35568d2019-01-09 11:32:33 -0800454
455 private:
456 Iter it;
Behdad Esfahbod025eaa32019-05-07 00:05:37 -0700457 hb_reference_wrapper<Pred> p;
458 hb_reference_wrapper<Proj> f;
Behdad Esfahbodf35568d2019-01-09 11:32:33 -0800459};
460template <typename Pred, typename Proj>
461struct hb_filter_iter_factory_t
462{
Behdad Esfahbod0670e1a2019-02-14 11:53:40 -0800463 hb_filter_iter_factory_t (Pred p, Proj f) : p (p), f (f) {}
Behdad Esfahbodf35568d2019-01-09 11:32:33 -0800464
Behdad Esfahbod0f292ea2019-02-14 10:49:31 -0800465 template <typename Iter,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700466 hb_requires (hb_is_iterator (Iter))>
Behdad Esfahbod0f292ea2019-02-14 10:49:31 -0800467 hb_filter_iter_t<Iter, Pred, Proj>
Behdad Esfahbodaa4ac132019-05-08 10:02:30 -0700468 operator () (Iter it)
Behdad Esfahbod0f292ea2019-02-14 10:49:31 -0800469 { return hb_filter_iter_t<Iter, Pred, Proj> (it, p, f); }
Behdad Esfahbodf35568d2019-01-09 11:32:33 -0800470
471 private:
472 Pred p;
473 Proj f;
474};
Behdad Esfahbod02d864a2019-04-15 15:39:03 -0400475struct
Behdad Esfahbod00db9402019-02-14 11:10:13 -0800476{
Behdad Esfahbod710d4592019-05-08 09:33:09 -0700477 template <typename Pred = decltype ((hb_identity)),
Behdad Esfahbod00db9402019-02-14 11:10:13 -0800478 typename Proj = decltype ((hb_identity))>
479 hb_filter_iter_factory_t<Pred, Proj>
Behdad Esfahbod710d4592019-05-08 09:33:09 -0700480 operator () (Pred&& p = hb_identity, Proj&& f = hb_identity) const
Behdad Esfahbod00db9402019-02-14 11:10:13 -0800481 { return hb_filter_iter_factory_t<Pred, Proj> (p, f); }
Behdad Esfahbod7654ebe2019-05-07 16:53:03 -0700482}
483HB_FUNCOBJ (hb_filter);
Behdad Esfahbod7557e342018-12-21 17:21:19 -0500484
Ebrahim Byagowib8642082019-04-02 00:30:06 +0430485template <typename Redu, typename InitT>
Ebrahim Byagowie5264142019-03-31 12:41:58 +0430486struct hb_reduce_t
487{
Ebrahim Byagowib8642082019-04-02 00:30:06 +0430488 hb_reduce_t (Redu r, InitT init_value) : r (r), init_value (init_value) {}
Ebrahim Byagowie5264142019-03-31 12:41:58 +0430489
490 template <typename Iter,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700491 hb_requires (hb_is_iterator (Iter)),
Behdad Esfahbod7bcc5df2019-07-28 20:55:50 -0700492 typename AccuT = hb_decay<decltype (hb_declval (Redu) (hb_declval (InitT), hb_declval (typename Iter::item_t)))>>
Ebrahim Byagowib8642082019-04-02 00:30:06 +0430493 AccuT
Behdad Esfahbodaa4ac132019-05-08 10:02:30 -0700494 operator () (Iter it)
Ebrahim Byagowie5264142019-03-31 12:41:58 +0430495 {
Ebrahim Byagowib8642082019-04-02 00:30:06 +0430496 AccuT value = init_value;
Ebrahim Byagowie5264142019-03-31 12:41:58 +0430497 for (; it; ++it)
Ebrahim Byagowib8642082019-04-02 00:30:06 +0430498 value = r (value, *it);
Ebrahim Byagowie5264142019-03-31 12:41:58 +0430499 return value;
500 }
501
502 private:
503 Redu r;
Ebrahim Byagowib8642082019-04-02 00:30:06 +0430504 InitT init_value;
Ebrahim Byagowie5264142019-03-31 12:41:58 +0430505};
Behdad Esfahbod02d864a2019-04-15 15:39:03 -0400506struct
Ebrahim Byagowie5264142019-03-31 12:41:58 +0430507{
Ebrahim Byagowib8642082019-04-02 00:30:06 +0430508 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 Esfahbod7654ebe2019-05-07 16:53:03 -0700512}
513HB_FUNCOBJ (hb_reduce);
Ebrahim Byagowie5264142019-03-31 12:41:58 +0430514
515
Behdad Esfahbod014c5022019-01-09 09:07:01 -0800516/* hb_zip() */
Behdad Esfahbod7557e342018-12-21 17:21:19 -0500517
Behdad Esfahbod84e5d002019-01-08 23:57:16 -0800518template <typename A, typename B>
Behdad Esfahbod200cdb72019-01-09 09:49:12 -0800519struct hb_zip_iter_t :
Behdad Esfahbode7990042019-01-29 17:15:12 -0800520 hb_iter_t<hb_zip_iter_t<A, B>,
Ebrahim Byagowi92588782019-04-30 13:05:10 -0700521 hb_pair_t<typename A::item_t, typename B::item_t>>
Behdad Esfahbod84e5d002019-01-08 23:57:16 -0800522{
Behdad Esfahbod200cdb72019-01-09 09:49:12 -0800523 hb_zip_iter_t () {}
Behdad Esfahbodb8b3b3e2019-02-15 16:05:36 -0800524 hb_zip_iter_t (const A& a, const B& b) : a (a), b (b) {}
Behdad Esfahbod84e5d002019-01-08 23:57:16 -0800525
526 typedef hb_pair_t<typename A::item_t, typename B::item_t> __item_t__;
Behdad Esfahbod090fe562019-01-25 15:34:03 +0100527 static constexpr bool is_random_access_iterator =
Behdad Esfahbode7990042019-01-29 17:15:12 -0800528 A::is_random_access_iterator &&
529 B::is_random_access_iterator;
Behdad Esfahbod889dc1e2019-05-14 22:28:07 -0700530 /* 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 Esfahbod51376282019-05-13 15:36:14 -0700555
Behdad Esfahbod84e5d002019-01-08 23:57:16 -0800556 __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 Esfahbod57a52562019-05-09 11:30:27 -0700558 bool __more__ () const { return bool (a) && bool (b); }
Behdad Esfahbod41248cc2019-05-07 20:54:31 -0700559 unsigned __len__ () const { return hb_min (a.len (), b.len ()); }
Behdad Esfahbod84e5d002019-01-08 23:57:16 -0800560 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 Esfahbod4c2fd052019-05-06 19:57:15 -0700564 hb_zip_iter_t __end__ () const { return hb_zip_iter_t (a.end (), b.end ()); }
Behdad Esfahbodebf47a92019-05-15 15:14:26 -0700565 /* 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 Esfahbod4c2fd052019-05-06 19:57:15 -0700567 bool operator != (const hb_zip_iter_t& o) const
Behdad Esfahbod5da3c9c2019-05-09 11:30:31 -0700568 { return a != o.a && b != o.b; }
Behdad Esfahbod84e5d002019-01-08 23:57:16 -0800569
570 private:
571 A a;
572 B b;
573};
Behdad Esfahbod02d864a2019-04-15 15:39:03 -0400574struct
Behdad Esfahbod9510e912019-09-01 16:25:33 -0500575{ HB_PARTIALIZE(2);
Behdad Esfahbodaa4c3212019-02-14 11:07:12 -0800576 template <typename A, typename B,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700577 hb_requires (hb_is_iterable (A) && hb_is_iterable (B))>
Behdad Esfahbod5875d772019-05-08 12:25:34 -0700578 hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>>
Behdad Esfahbod2c24ea32019-05-09 11:07:38 -0700579 operator () (A&& a, B&& b) const
Behdad Esfahbod5875d772019-05-08 12:25:34 -0700580 { return hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>> (hb_iter (a), hb_iter (b)); }
Behdad Esfahbod7654ebe2019-05-07 16:53:03 -0700581}
582HB_FUNCOBJ (hb_zip);
Behdad Esfahbod84e5d002019-01-08 23:57:16 -0800583
Behdad Esfahbod773d7562019-02-14 11:40:22 -0800584/* hb_apply() */
585
586template <typename Appl>
587struct hb_apply_t
588{
Behdad Esfahbod0670e1a2019-02-14 11:53:40 -0800589 hb_apply_t (Appl a) : a (a) {}
Behdad Esfahbod773d7562019-02-14 11:40:22 -0800590
591 template <typename Iter,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700592 hb_requires (hb_is_iterator (Iter))>
Behdad Esfahbodaa4ac132019-05-08 10:02:30 -0700593 void operator () (Iter it)
Behdad Esfahbod773d7562019-02-14 11:40:22 -0800594 {
595 for (; it; ++it)
Behdad Esfahbodb8e763f2019-04-16 10:50:22 -0400596 (void) hb_invoke (a, *it);
Behdad Esfahbod773d7562019-02-14 11:40:22 -0800597 }
598
599 private:
600 Appl a;
601};
Behdad Esfahbod02d864a2019-04-15 15:39:03 -0400602struct
Behdad Esfahbod773d7562019-02-14 11:40:22 -0800603{
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 Esfahbod7654ebe2019-05-07 16:53:03 -0700611}
612HB_FUNCOBJ (hb_apply);
Behdad Esfahbod773d7562019-02-14 11:40:22 -0800613
Behdad Esfahbodb1378d82019-08-30 12:10:45 -0500614/* hb_range()/hb_iota()/hb_repeat() */
Behdad Esfahbod50dc3e72019-05-08 10:35:02 -0700615
616template <typename T, typename S>
Behdad Esfahbod814dc3c2019-08-30 10:20:30 -0500617struct hb_range_iter_t :
618 hb_iter_t<hb_range_iter_t<T, S>, T>
Behdad Esfahbod50dc3e72019-05-08 10:35:02 -0700619{
Behdad Esfahbod814dc3c2019-08-30 10:20:30 -0500620 hb_range_iter_t (T start, T end_, S step) : v (start), end_ (end_for (start, end_, step)), step (step) {}
Behdad Esfahbod50dc3e72019-05-08 10:35:02 -0700621
622 typedef T __item_t__;
623 static constexpr bool is_random_access_iterator = true;
Behdad Esfahbod889dc1e2019-05-14 22:28:07 -0700624 static constexpr bool is_sorted_iterator = true;
Behdad Esfahbodde457752019-08-30 12:02:46 -0500625 __item_t__ __item__ () const { return hb_ridentity (v); }
Behdad Esfahbod50dc3e72019-05-08 10:35:02 -0700626 __item_t__ __item_at__ (unsigned j) const { return v + j * step; }
Behdad Esfahbod71537f92019-05-09 10:46:49 -0700627 bool __more__ () const { return v != end_; }
Behdad Esfahbod4f2ad752019-05-09 12:07:45 -0700628 unsigned __len__ () const { return !step ? UINT_MAX : (end_ - v) / step; }
Behdad Esfahbod50dc3e72019-05-08 10:35:02 -0700629 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 Esfahbod814dc3c2019-08-30 10:20:30 -0500633 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 Esfahbodebf47a92019-05-15 15:14:26 -0700635 { return v != o.v; }
Behdad Esfahbod50dc3e72019-05-08 10:35:02 -0700636
637 private:
Behdad Esfahbod12dd56f2019-05-09 11:25:02 -0700638 static inline T end_for (T start, T end_, S step)
Behdad Esfahbod50dc3e72019-05-08 10:35:02 -0700639 {
Behdad Esfahbod12dd56f2019-05-09 11:25:02 -0700640 if (!step)
641 return end_;
Behdad Esfahbod71537f92019-05-09 10:46:49 -0700642 auto res = (end_ - start) % step;
Behdad Esfahbod50dc3e72019-05-08 10:35:02 -0700643 if (!res)
Behdad Esfahbod71537f92019-05-09 10:46:49 -0700644 return end_;
645 end_ += step - res;
646 return end_;
Behdad Esfahbod50dc3e72019-05-08 10:35:02 -0700647 }
648
649 private:
650 T v;
Behdad Esfahbod71537f92019-05-09 10:46:49 -0700651 T end_;
Behdad Esfahbod50dc3e72019-05-08 10:35:02 -0700652 S step;
653};
654struct
655{
Behdad Esfahbod814dc3c2019-08-30 10:20:30 -0500656 template <typename T = unsigned> hb_range_iter_t<T, unsigned>
Behdad Esfahbod7675d0d2019-05-09 11:02:56 -0700657 operator () (T end = (unsigned) -1) const
Behdad Esfahbod814dc3c2019-08-30 10:20:30 -0500658 { return hb_range_iter_t<T, unsigned> (0, end, 1u); }
Behdad Esfahbod7675d0d2019-05-09 11:02:56 -0700659
Behdad Esfahbod814dc3c2019-08-30 10:20:30 -0500660 template <typename T, typename S = unsigned> hb_range_iter_t<T, S>
Behdad Esfahbod966a18b2019-08-30 12:07:17 -0500661 operator () (T start, T end, S step = 1u) const
Behdad Esfahbod814dc3c2019-08-30 10:20:30 -0500662 { return hb_range_iter_t<T, S> (start, end, step); }
Behdad Esfahbod7675d0d2019-05-09 11:02:56 -0700663}
664HB_FUNCOBJ (hb_range);
Behdad Esfahbod50dc3e72019-05-08 10:35:02 -0700665
Behdad Esfahbodce4d63b2019-08-30 11:59:50 -0500666template <typename T, typename S>
667struct hb_iota_iter_t :
Behdad Esfahbod1f88dae2019-08-31 12:24:42 -0500668 hb_iter_with_fallback_t<hb_iota_iter_t<T, S>, T>
Behdad Esfahbodce4d63b2019-08-30 11:59:50 -0500669{
670 hb_iota_iter_t (T start, S step) : v (start), step (step) {}
671
Behdad Esfahbod1f88dae2019-08-31 12:24:42 -0500672 private:
673
674 template <typename S2 = S>
675 auto
Behdad Esfahbod875131d2019-08-31 12:42:52 -0500676 inc (hb_type_identity<S2> s, hb_priority<1>)
Behdad Esfahbod6d555ce2021-11-02 00:18:22 -0600677 -> hb_void_t<decltype (hb_invoke (std::forward<S2> (s), hb_declval<T&> ()))>
678 { v = hb_invoke (std::forward<S2> (s), v); }
Behdad Esfahbod1f88dae2019-08-31 12:24:42 -0500679
680 void
681 inc (S s, hb_priority<0>)
682 { v += s; }
683
684 public:
685
Behdad Esfahbodce4d63b2019-08-30 11:59:50 -0500686 typedef T __item_t__;
687 static constexpr bool is_random_access_iterator = true;
688 static constexpr bool is_sorted_iterator = true;
Behdad Esfahbodde457752019-08-30 12:02:46 -0500689 __item_t__ __item__ () const { return hb_ridentity (v); }
Behdad Esfahbodce4d63b2019-08-30 11:59:50 -0500690 bool __more__ () const { return true; }
691 unsigned __len__ () const { return UINT_MAX; }
Behdad Esfahbod1f88dae2019-08-31 12:24:42 -0500692 void __next__ () { inc (step, hb_prioritize); }
Behdad Esfahbodce4d63b2019-08-30 11:59:50 -0500693 void __prev__ () { v -= step; }
Behdad Esfahbodb1378d82019-08-30 12:10:45 -0500694 hb_iota_iter_t __end__ () const { return *this; }
Behdad Esfahbodce4d63b2019-08-30 11:59:50 -0500695 bool operator != (const hb_iota_iter_t& o) const { return true; }
696
697 private:
698 T v;
699 S step;
700};
Behdad Esfahbod814dc3c2019-08-30 10:20:30 -0500701struct
702{
Behdad Esfahbodce4d63b2019-08-30 11:59:50 -0500703 template <typename T = unsigned, typename S = unsigned> hb_iota_iter_t<T, S>
Behdad Esfahbod966a18b2019-08-30 12:07:17 -0500704 operator () (T start = 0u, S step = 1u) const
Behdad Esfahbodce4d63b2019-08-30 11:59:50 -0500705 { return hb_iota_iter_t<T, S> (start, step); }
Behdad Esfahbod814dc3c2019-08-30 10:20:30 -0500706}
707HB_FUNCOBJ (hb_iota);
708
Behdad Esfahbodb1378d82019-08-30 12:10:45 -0500709template <typename T>
710struct 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};
732struct
733{
734 template <typename T> hb_repeat_iter_t<T>
735 operator () (T value) const
736 { return hb_repeat_iter_t<T> (value); }
737}
738HB_FUNCOBJ (hb_repeat);
739
Behdad Esfahbod875131d2019-08-31 12:42:52 -0500740/* hb_enumerate()/hb_take() */
Behdad Esfahbod2c24ea32019-05-09 11:07:38 -0700741
742struct
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}
750HB_FUNCOBJ (hb_enumerate);
Behdad Esfahbod67ec9fa2019-08-31 14:51:49 -0500751
Behdad Esfahbod875131d2019-08-31 12:42:52 -0500752struct
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 Esfahbod5828d8e2019-08-31 14:36:44 -0500758
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 Esfahbod875131d2019-08-31 12:42:52 -0500768}
769HB_FUNCOBJ (hb_take);
Behdad Esfahbod2c24ea32019-05-09 11:07:38 -0700770
Behdad Esfahbod67ec9fa2019-08-31 14:51:49 -0500771struct
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 Esfahbodc9eb9132019-08-31 15:21:02 -0500777 + hb_iota (it, hb_add (count))
778 | hb_map (hb_take (count))
Behdad Esfahbod67ec9fa2019-08-31 14:51:49 -0500779 | hb_take ((hb_len (it) + count - 1) / count)
780 )
781}
782HB_FUNCOBJ (hb_chop);
783
Behdad Esfahbodb702a0c2019-02-14 10:39:58 -0800784/* hb_sink() */
785
786template <typename Sink>
787struct hb_sink_t
788{
Behdad Esfahbod8479eb52019-05-08 09:48:55 -0700789 hb_sink_t (Sink s) : s (s) {}
Behdad Esfahbodb702a0c2019-02-14 10:39:58 -0800790
Behdad Esfahbod5fa52e62019-02-14 10:51:02 -0800791 template <typename Iter,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700792 hb_requires (hb_is_iterator (Iter))>
Behdad Esfahbodaa4ac132019-05-08 10:02:30 -0700793 void operator () (Iter it)
Behdad Esfahbodb702a0c2019-02-14 10:39:58 -0800794 {
Behdad Esfahbod5fa52e62019-02-14 10:51:02 -0800795 for (; it; ++it)
Behdad Esfahbodb702a0c2019-02-14 10:39:58 -0800796 s << *it;
797 }
798
799 private:
800 Sink s;
801};
Behdad Esfahbod02d864a2019-04-15 15:39:03 -0400802struct
Behdad Esfahbodb5305732019-02-14 11:00:10 -0800803{
804 template <typename Sink> hb_sink_t<Sink>
805 operator () (Sink&& s) const
806 { return hb_sink_t<Sink> (s); }
Behdad Esfahbodf8fcfb22019-02-14 11:03:29 -0800807
808 template <typename Sink> hb_sink_t<Sink&>
809 operator () (Sink *s) const
810 { return hb_sink_t<Sink&> (*s); }
Behdad Esfahbod7654ebe2019-05-07 16:53:03 -0700811}
812HB_FUNCOBJ (hb_sink);
Behdad Esfahbodb702a0c2019-02-14 10:39:58 -0800813
Behdad Esfahbod6237b472019-03-29 21:36:49 -0700814/* hb-drain: hb_sink to void / blackhole / /dev/null. */
815
Behdad Esfahbod02d864a2019-04-15 15:39:03 -0400816struct
Behdad Esfahbodfa35d3f2019-02-14 14:04:05 -0800817{
818 template <typename Iter,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700819 hb_requires (hb_is_iterator (Iter))>
820 void operator () (Iter it) const
Behdad Esfahbodfa35d3f2019-02-14 14:04:05 -0800821 {
822 for (; it; ++it)
823 (void) *it;
824 }
Behdad Esfahbod7654ebe2019-05-07 16:53:03 -0700825}
826HB_FUNCOBJ (hb_drain);
Behdad Esfahbod014c5022019-01-09 09:07:01 -0800827
Behdad Esfahbod6237b472019-03-29 21:36:49 -0700828/* hb_unzip(): unzip and sink to two sinks. */
829
830template <typename Sink1, typename Sink2>
831struct hb_unzip_t
832{
Behdad Esfahbodaa4ac132019-05-08 10:02:30 -0700833 hb_unzip_t (Sink1 s1, Sink2 s2) : s1 (s1), s2 (s2) {}
Behdad Esfahbod6237b472019-03-29 21:36:49 -0700834
835 template <typename Iter,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700836 hb_requires (hb_is_iterator (Iter))>
Behdad Esfahbodaa4ac132019-05-08 10:02:30 -0700837 void operator () (Iter it)
Behdad Esfahbod6237b472019-03-29 21:36:49 -0700838 {
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 Esfahbod02d864a2019-04-15 15:39:03 -0400851struct
Behdad Esfahbod6237b472019-03-29 21:36:49 -0700852{
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 Esfahbod7654ebe2019-05-07 16:53:03 -0700860}
861HB_FUNCOBJ (hb_unzip);
Behdad Esfahbod6237b472019-03-29 21:36:49 -0700862
863
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800864/* hb-all, hb-any, hb-none. */
865
Behdad Esfahbod02d864a2019-04-15 15:39:03 -0400866struct
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800867{
868 template <typename Iterable,
Behdad Esfahbod710d4592019-05-08 09:33:09 -0700869 typename Pred = decltype ((hb_identity)),
Behdad Esfahbodbdbfdc92019-05-07 22:52:43 -0700870 typename Proj = decltype ((hb_identity)),
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700871 hb_requires (hb_is_iterable (Iterable))>
Behdad Esfahbodbdbfdc92019-05-07 22:52:43 -0700872 bool operator () (Iterable&& c,
Behdad Esfahbod710d4592019-05-08 09:33:09 -0700873 Pred&& p = hb_identity,
Behdad Esfahbodbdbfdc92019-05-07 22:52:43 -0700874 Proj&& f = hb_identity) const
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800875 {
876 for (auto it = hb_iter (c); it; ++it)
Behdad Esfahbod6d555ce2021-11-02 00:18:22 -0600877 if (!hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800878 return false;
879 return true;
880 }
Behdad Esfahbod7654ebe2019-05-07 16:53:03 -0700881}
882HB_FUNCOBJ (hb_all);
Behdad Esfahbod02d864a2019-04-15 15:39:03 -0400883struct
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800884{
885 template <typename Iterable,
Behdad Esfahbod710d4592019-05-08 09:33:09 -0700886 typename Pred = decltype ((hb_identity)),
Behdad Esfahbodbdbfdc92019-05-07 22:52:43 -0700887 typename Proj = decltype ((hb_identity)),
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700888 hb_requires (hb_is_iterable (Iterable))>
Behdad Esfahbodbdbfdc92019-05-07 22:52:43 -0700889 bool operator () (Iterable&& c,
Behdad Esfahbod710d4592019-05-08 09:33:09 -0700890 Pred&& p = hb_identity,
Behdad Esfahbodbdbfdc92019-05-07 22:52:43 -0700891 Proj&& f = hb_identity) const
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800892 {
893 for (auto it = hb_iter (c); it; ++it)
Behdad Esfahbod6d555ce2021-11-02 00:18:22 -0600894 if (hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800895 return true;
896 return false;
897 }
Behdad Esfahbod7654ebe2019-05-07 16:53:03 -0700898}
899HB_FUNCOBJ (hb_any);
Behdad Esfahbod02d864a2019-04-15 15:39:03 -0400900struct
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800901{
902 template <typename Iterable,
Behdad Esfahbod710d4592019-05-08 09:33:09 -0700903 typename Pred = decltype ((hb_identity)),
Behdad Esfahbodbdbfdc92019-05-07 22:52:43 -0700904 typename Proj = decltype ((hb_identity)),
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700905 hb_requires (hb_is_iterable (Iterable))>
Behdad Esfahbodbdbfdc92019-05-07 22:52:43 -0700906 bool operator () (Iterable&& c,
Behdad Esfahbod710d4592019-05-08 09:33:09 -0700907 Pred&& p = hb_identity,
Behdad Esfahbodbdbfdc92019-05-07 22:52:43 -0700908 Proj&& f = hb_identity) const
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800909 {
910 for (auto it = hb_iter (c); it; ++it)
Behdad Esfahbod6d555ce2021-11-02 00:18:22 -0600911 if (hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800912 return false;
913 return true;
914 }
Behdad Esfahbod7654ebe2019-05-07 16:53:03 -0700915}
916HB_FUNCOBJ (hb_none);
Behdad Esfahbod77060bc2019-02-15 16:55:08 -0800917
Behdad Esfahbod014c5022019-01-09 09:07:01 -0800918/*
919 * Algorithms operating on iterators.
920 */
921
922template <typename C, typename V,
Behdad Esfahbodaf571db2019-05-07 21:39:20 -0700923 hb_requires (hb_is_iterable (C))>
Behdad Esfahbod014c5022019-01-09 09:07:01 -0800924inline void
Behdad Esfahbod5fce8892021-01-21 12:14:20 -0700925hb_fill (C&& c, const V &v)
Behdad Esfahbod014c5022019-01-09 09:07:01 -0800926{
Behdad Esfahbod5b99c922019-02-14 17:10:04 -0800927 for (auto i = hb_iter (c); i; i++)
Behdad Esfahbod4c38a9f2019-03-29 20:23:07 -0700928 *i = v;
Behdad Esfahbod014c5022019-01-09 09:07:01 -0800929}
930
Behdad Esfahbod8a8d45b2019-03-31 19:00:09 -0700931template <typename S, typename D>
932inline void
Behdad Esfahbod78fc43f2019-03-31 19:17:07 -0700933hb_copy (S&& is, D&& id)
Behdad Esfahbod014c5022019-01-09 09:07:01 -0800934{
Behdad Esfahbod78fc43f2019-03-31 19:17:07 -0700935 hb_iter (is) | hb_sink (id);
Behdad Esfahbod014c5022019-01-09 09:07:01 -0800936}
937
938
Behdad Esfahbodb80b97b2018-12-21 00:08:05 -0500939#endif /* HB_ITER_HH */