1 /*
2 * Copyright © 2018 Google, Inc.
3 *
4 * This is part of HarfBuzz, a text shaping library.
5 *
6 * Permission is hereby granted, without written agreement and without
7 * license or royalty fees, to use, copy, modify, and distribute this
8 * software and its documentation for any purpose, provided that the
9 * above copyright notice and the following two paragraphs appear in
10 * all copies of this software.
11 *
12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
16 * DAMAGE.
17 *
18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
23 *
24 * Google Author(s): Behdad Esfahbod
25 */
26
27 #include "hb.hh"
28 #include "hb-iter.hh"
29
30 #include "hb-array.hh"
31 #include "hb-set.hh"
32 #include "hb-ot-layout-common.hh"
33
34 template <typename T>
35 struct array_iter_t : hb_iter_with_fallback_t<array_iter_t<T>, T&>
36 {
array_iter_tarray_iter_t37 array_iter_t (hb_array_t<T> arr_) : arr (arr_) {}
38
39 typedef T& __item_t__;
40 static constexpr bool is_random_access_iterator = true;
__item_at__array_iter_t41 T& __item_at__ (unsigned i) const { return arr[i]; }
__forward__array_iter_t42 void __forward__ (unsigned n) { arr += n; }
__rewind__array_iter_t43 void __rewind__ (unsigned n) { arr -= n; }
__len__array_iter_t44 unsigned __len__ () const { return arr.length; }
operator !=array_iter_t45 bool operator != (const array_iter_t& o) { return arr != o.arr; }
46
47 private:
48 hb_array_t<T> arr;
49 };
50
51 template <typename T>
52 struct some_array_t
53 {
some_array_tsome_array_t54 some_array_t (hb_array_t<T> arr_) : arr (arr_) {}
55
56 typedef array_iter_t<T> iter_t;
itersome_array_t57 array_iter_t<T> iter () { return array_iter_t<T> (arr); }
operator array_iter_t<T>some_array_t58 operator array_iter_t<T> () { return iter (); }
operator hb_iter_t<array_iter_t<T>>some_array_t59 operator hb_iter_t<array_iter_t<T>> () { return iter (); }
60
61 private:
62 hb_array_t<T> arr;
63 };
64
65
66 template <typename Iter,
67 hb_requires (hb_is_iterator (Iter))>
68 static void
test_iterator_non_default_constructable(Iter it)69 test_iterator_non_default_constructable (Iter it)
70 {
71 /* Iterate over a copy of it. */
72 for (auto c = it.iter (); c; c++)
73 *c;
74
75 /* Same. */
76 for (auto c = +it; c; c++)
77 *c;
78
79 /* Range-based for over a copy. */
80 for (auto _ : +it)
81 (void) _;
82
83 it += it.len ();
84 it = it + 10;
85 it = 10 + it;
86
87 assert (*it == it[0]);
88
89 static_assert (true || it.is_random_access_iterator, "");
90 static_assert (true || it.is_sorted_iterator, "");
91 }
92
93 template <typename Iter,
94 hb_requires (hb_is_iterator (Iter))>
95 static void
test_iterator(Iter it)96 test_iterator (Iter it)
97 {
98 Iter default_constructed;
99 assert (!default_constructed);
100
101 test_iterator_non_default_constructable (it);
102 }
103
104 template <typename Iterable,
105 hb_requires (hb_is_iterable (Iterable))>
106 static void
test_iterable(const Iterable & lst=Null (Iterable))107 test_iterable (const Iterable &lst = Null (Iterable))
108 {
109 for (auto _ : lst)
110 (void) _;
111
112 // Test that can take iterator from.
113 test_iterator (lst.iter ());
114 }
115
116 template <typename It>
check_sequential(It it)117 static void check_sequential (It it)
118 {
119 int i = 1;
120 for (int v : +it) {
121 assert (v == i++);
122 }
123 }
124
test_concat()125 static void test_concat ()
126 {
127 hb_vector_t<int> a = {1, 2, 3};
128 hb_vector_t<int> b = {4, 5};
129
130 hb_vector_t<int> c = {};
131 hb_vector_t<int> d = {1, 2, 3, 4, 5};
132
133 auto it1 = hb_concat (a, b);
134 assert (it1.len () == 5);
135 assert (it1.is_random_access_iterator);
136 auto it2 = hb_concat (c, d);
137 assert (it2.len () == 5);
138 auto it3 = hb_concat (d, c);
139 assert (it3.len () == 5);
140 for (int i = 0; i < 5; i++) {
141 assert(it1[i] == i + 1);
142 assert(it2[i] == i + 1);
143 assert(it3[i] == i + 1);
144 }
145
146 check_sequential (it1);
147 check_sequential (it2);
148 check_sequential (it3);
149
150 auto it4 = +it1;
151 it4 += 0;
152 assert (*it4 == 1);
153
154 it4 += 2;
155 assert (*it4 == 3);
156 assert (it4);
157 assert (it4.len () == 3);
158
159 it4 += 2;
160 assert (*it4 == 5);
161 assert (it4);
162 assert (it4.len () == 1);
163
164 it4++;
165 assert (!it4);
166 assert (it4.len () == 0);
167
168 auto it5 = +it1;
169 it5 += 3;
170 assert (*it5 == 4);
171
172 hb_set_t s_a = {1, 2, 3};
173 hb_set_t s_b = {4, 5};
174 auto it6 = hb_concat (s_a, s_b);
175 assert (!it6.is_random_access_iterator);
176 check_sequential (it6);
177 assert (it6.len () == 5);
178
179 it6 += 0;
180 assert (*it6 == 1);
181
182 it6 += 3;
183 assert (*it6 == 4);
184 assert (it6);
185 assert (it6.len () == 2);
186 }
187
188 int
main(int argc,char ** argv)189 main (int argc, char **argv)
190 {
191 const int src[10] = {};
192 int dst[20];
193 hb_vector_t<int> v;
194
195 array_iter_t<const int> s (src); /* Implicit conversion from static array. */
196 array_iter_t<const int> s2 (v); /* Implicit conversion from vector. */
197 array_iter_t<int> t (dst);
198
199 static_assert (array_iter_t<int>::is_random_access_iterator, "");
200
201 some_array_t<const int> a (src);
202
203 s2 = s;
204
205 hb_iter (src);
206 hb_iter (src, 2);
207
208 hb_fill (t, 42);
209 hb_copy (s, t);
210 hb_copy (a.iter (), t);
211
212 test_iterable (v);
213 hb_set_t st;
214 st << 1 << 15 << 43;
215 test_iterable (st);
216 hb_sorted_array_t<int> sa;
217 (void) static_cast<hb_iter_t<hb_sorted_array_t<int>, hb_sorted_array_t<int>::item_t>&> (sa);
218 (void) static_cast<hb_iter_t<hb_sorted_array_t<int>, hb_sorted_array_t<int>::__item_t__>&> (sa);
219 (void) static_cast<hb_iter_t<hb_sorted_array_t<int>, int&>&>(sa);
220 (void) static_cast<hb_iter_t<hb_sorted_array_t<int>>&>(sa);
221 (void) static_cast<hb_iter_t<hb_array_t<int>, int&>&> (sa);
222 test_iterable (sa);
223
224 test_iterable<hb_array_t<int>> ();
225 test_iterable<hb_sorted_array_t<const int>> ();
226 test_iterable<hb_vector_t<float>> ();
227 test_iterable<hb_set_t> ();
228 test_iterable<OT::Array16Of<OT::HBUINT16>> ();
229
230 test_iterator (hb_zip (st, v));
231 test_iterator_non_default_constructable (hb_enumerate (st));
232 test_iterator_non_default_constructable (hb_enumerate (st, -5));
233 test_iterator_non_default_constructable (hb_enumerate (hb_iter (st)));
234 test_iterator_non_default_constructable (hb_enumerate (hb_iter (st) + 1));
235 test_iterator_non_default_constructable (hb_iter (st) | hb_filter ());
236 test_iterator_non_default_constructable (hb_iter (st) | hb_map (hb_lidentity));
237
238 assert (true == hb_all (st));
239 assert (false == hb_all (st, 42u));
240 assert (true == hb_any (st));
241 assert (false == hb_any (st, 14u));
242 assert (true == hb_any (st, 14u, [] (unsigned _) { return _ - 1u; }));
243 assert (true == hb_any (st, [] (unsigned _) { return _ == 15u; }));
244 assert (true == hb_any (st, 15u));
245 assert (false == hb_none (st));
246 assert (false == hb_none (st, 15u));
247 assert (true == hb_none (st, 17u));
248
249 hb_array_t<hb_vector_t<int>> pa;
250 pa->as_array ();
251
252 hb_map_t m;
253
254 hb_iter (st);
255 hb_iter (&st);
256
257 + hb_iter (src)
258 | hb_map (m)
259 | hb_map (&m)
260 | hb_filter ()
261 | hb_filter (st)
262 | hb_filter (&st)
263 | hb_filter (hb_bool)
264 | hb_filter (hb_bool, hb_identity)
265 | hb_sink (st)
266 ;
267
268 + hb_iter (src)
269 | hb_sink (hb_array (dst))
270 ;
271
272 + hb_iter (src)
273 | hb_apply (&st)
274 ;
275
276 + hb_iter (src)
277 | hb_map ([] (int i) { return 1; })
278 | hb_reduce ([=] (int acc, int value) { return acc; }, 2)
279 ;
280
281 using map_pair_t = hb_item_type<hb_map_t>;
282 + hb_iter (m)
283 | hb_map ([] (map_pair_t p) { return p.first * p.second; })
284 ;
285
286 m.keys ();
287 using map_key_t = decltype (*m.keys());
288 + hb_iter (m.keys ())
289 | hb_filter ([] (map_key_t k) { return k < 42; })
290 | hb_drain
291 ;
292
293 m.values ();
294 using map_value_t = decltype (*m.values());
295 + hb_iter (m.values ())
296 | hb_filter ([] (map_value_t k) { return k < 42; })
297 | hb_drain
298 ;
299
300 unsigned int temp1 = 10;
301 unsigned int temp2 = 0;
302 hb_map_t *result =
303 + hb_iter (src)
304 | hb_map ([&] (int i) -> hb_set_t *
305 {
306 hb_set_t *set = hb_set_create ();
307 for (unsigned int i = 0; i < temp1; ++i)
308 hb_set_add (set, i);
309 temp1++;
310 return set;
311 })
312 | hb_reduce ([&] (hb_map_t *acc, hb_set_t *value) -> hb_map_t *
313 {
314 hb_map_set (acc, temp2++, hb_set_get_population (value));
315 /* This is not a memory managed language, take care! */
316 hb_set_destroy (value);
317 return acc;
318 }, hb_map_create ())
319 ;
320 /* The result should be something like 0->10, 1->11, ..., 9->19 */
321 assert (hb_map_get (result, 9) == 19);
322 hb_map_destroy (result);
323
324 /* Like above, but passing hb_set_t instead of hb_set_t * */
325 temp1 = 10;
326 temp2 = 0;
327 result =
328 + hb_iter (src)
329 | hb_map ([&] (int i) -> hb_set_t
330 {
331 hb_set_t set;
332 for (unsigned int i = 0; i < temp1; ++i)
333 hb_set_add (&set, i);
334 temp1++;
335 return set;
336 })
337 | hb_reduce ([&] (hb_map_t *acc, hb_set_t value) -> hb_map_t *
338 {
339 hb_map_set (acc, temp2++, hb_set_get_population (&value));
340 return acc;
341 }, hb_map_create ())
342 ;
343 /* The result should be something like 0->10, 1->11, ..., 9->19 */
344 assert (hb_map_get (result, 9) == 19);
345 hb_map_destroy (result);
346
347 unsigned int temp3 = 0;
348 + hb_iter(src)
349 | hb_map([&] (int i) { return ++temp3; })
350 | hb_reduce([&] (float acc, int value) { return acc + value; }, 0)
351 ;
352
353 + hb_iter (src)
354 | hb_drain
355 ;
356
357 t << 1;
358 long vl;
359 s >> vl;
360
361 hb_iota ();
362 hb_iota (3);
363 hb_iota (3, 2);
364 assert ((&vl) + 1 == *++hb_iota (&vl, hb_inc));
365 hb_range ();
366 hb_repeat (7u);
367 hb_repeat (nullptr);
368 hb_repeat (vl) | hb_chop (3);
369 assert (hb_len (hb_range (10) | hb_take (3)) == 3);
370 assert (hb_range (9).len () == 9);
371 assert (hb_range (2, 9).len () == 7);
372 assert (hb_range (2, 9, 3).len () == 3);
373 assert (hb_range (2, 8, 3).len () == 2);
374 assert (hb_range (2, 7, 3).len () == 2);
375 assert (hb_range (-2, -9, -3).len () == 3);
376 assert (hb_range (-2, -8, -3).len () == 2);
377 assert (hb_range (-2, -7, -3).len () == 2);
378
379 test_concat ();
380
381 return 0;
382 }
383