1/*
2 * Copyright © 2012,2017 Google, Inc.
3 * Copyright © 2021 Behdad Esfahbod
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
26 */
27
28#ifndef HB_BIT_SET_INVERTIBLE_HH
29#define HB_BIT_SET_INVERTIBLE_HH
30
31#include "hb.hh"
32#include "hb-bit-set.hh"
33
34
35struct hb_bit_set_invertible_t
36{
37 hb_bit_set_t s;
38 bool inverted = false;
39
40 hb_bit_set_invertible_t () = default;
41 hb_bit_set_invertible_t (const hb_bit_set_invertible_t& o) = default;
42 hb_bit_set_invertible_t (hb_bit_set_invertible_t&& other) : hb_bit_set_invertible_t () { hb_swap (*this, other); }
43 hb_bit_set_invertible_t& operator= (const hb_bit_set_invertible_t& o) = default;
44 hb_bit_set_invertible_t& operator= (hb_bit_set_invertible_t&& other) { hb_swap (*this, other); return *this; }
45 friend void swap (hb_bit_set_invertible_t &a, hb_bit_set_invertible_t &b)
46 {
47 if (likely (!a.s.successful || !b.s.successful))
48 return;
49 hb_swap (a.inverted, b.inverted);
50 hb_swap (a.s, b.s);
51 }
52
53 void init () { s.init (); inverted = false; }
54 void fini () { s.fini (); }
55 void err () { s.err (); }
56 bool in_error () const { return s.in_error (); }
57 explicit operator bool () const { return !is_empty (); }
58
59 void alloc (unsigned sz) { s.alloc (sz); }
60 void reset ()
61 {
62 s.reset ();
63 inverted = false;
64 }
65 void clear ()
66 {
67 s.clear ();
68 if (likely (s.successful))
69 inverted = false;
70 }
71 void invert ()
72 {
73 if (likely (s.successful))
74 inverted = !inverted;
75 }
76
77 bool is_inverted () const
78 {
79 return inverted;
80 }
81
82 bool is_empty () const
83 {
84 hb_codepoint_t v = INVALID;
85 next (&v);
86 return v == INVALID;
87 }
88 uint32_t hash () const { return s.hash () ^ (uint32_t) inverted; }
89
90 hb_codepoint_t get_min () const
91 {
92 hb_codepoint_t v = INVALID;
93 next (&v);
94 return v;
95 }
96 hb_codepoint_t get_max () const
97 {
98 hb_codepoint_t v = INVALID;
99 previous (&v);
100 return v;
101 }
102 unsigned int get_population () const
103 { return inverted ? INVALID - s.get_population () : s.get_population (); }
104
105
106 void add (hb_codepoint_t g) { unlikely (inverted) ? s.del (g) : s.add (g); }
107 bool add_range (hb_codepoint_t a, hb_codepoint_t b)
108 { return unlikely (inverted) ? ((void) s.del_range (a, b), true) : s.add_range (a, b); }
109
110 template <typename T>
111 void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
112 { inverted ? s.del_array (array, count, stride) : s.add_array (array, count, stride); }
113 template <typename T>
114 void add_array (const hb_array_t<const T>& arr) { add_array (&arr, arr.len ()); }
115
116 /* Might return false if array looks unsorted.
117 * Used for faster rejection of corrupt data. */
118 template <typename T>
119 bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
120 { return inverted ? s.del_sorted_array (array, count, stride) : s.add_sorted_array (array, count, stride); }
121 template <typename T>
122 bool add_sorted_array (const hb_sorted_array_t<const T>& arr) { return add_sorted_array (&arr, arr.len ()); }
123
124 void del (hb_codepoint_t g) { unlikely (inverted) ? s.add (g) : s.del (g); }
125 void del_range (hb_codepoint_t a, hb_codepoint_t b)
126 { unlikely (inverted) ? (void) s.add_range (a, b) : s.del_range (a, b); }
127
128 bool get (hb_codepoint_t g) const { return s.get (g) ^ inverted; }
129
130 /* Has interface. */
131 bool operator [] (hb_codepoint_t k) const { return get (k); }
132 bool has (hb_codepoint_t k) const { return (*this)[k]; }
133 /* Predicate. */
134 bool operator () (hb_codepoint_t k) const { return has (k); }
135
136 /* Sink interface. */
137 hb_bit_set_invertible_t& operator << (hb_codepoint_t v)
138 { add (v); return *this; }
139 hb_bit_set_invertible_t& operator << (const hb_codepoint_pair_t& range)
140 { add_range (range.first, range.second); return *this; }
141
142 bool intersects (hb_codepoint_t first, hb_codepoint_t last) const
143 {
144 hb_codepoint_t c = first - 1;
145 return next (&c) && c <= last;
146 }
147
148 void set (const hb_bit_set_invertible_t &other)
149 {
150 s.set (other.s);
151 if (likely (s.successful))
152 inverted = other.inverted;
153 }
154
155 bool is_equal (const hb_bit_set_invertible_t &other) const
156 {
157 if (likely (inverted == other.inverted))
158 return s.is_equal (other.s);
159 else
160 {
161 /* TODO Add iter_ranges() and use here. */
162 auto it1 = iter ();
163 auto it2 = other.iter ();
164 return hb_all (+ hb_zip (it1, it2)
165 | hb_map ([](hb_codepoint_pair_t _) { return _.first == _.second; }));
166 }
167 }
168
169 bool is_subset (const hb_bit_set_invertible_t &larger_set) const
170 {
171 if (unlikely (inverted != larger_set.inverted))
172 return hb_all (hb_iter (s) | hb_map (larger_set.s));
173 else
174 return unlikely (inverted) ? larger_set.s.is_subset (s) : s.is_subset (larger_set.s);
175 }
176
177 protected:
178 template <typename Op>
179 void process (const Op& op, const hb_bit_set_invertible_t &other)
180 { s.process (op, other.s); }
181 public:
182 void union_ (const hb_bit_set_invertible_t &other)
183 {
184 if (likely (inverted == other.inverted))
185 {
186 if (unlikely (inverted))
187 process (hb_bitwise_and, other);
188 else
189 process (hb_bitwise_or, other); /* Main branch. */
190 }
191 else
192 {
193 if (unlikely (inverted))
194 process (hb_bitwise_gt, other);
195 else
196 process (hb_bitwise_lt, other);
197 }
198 if (likely (s.successful))
199 inverted = inverted || other.inverted;
200 }
201 void intersect (const hb_bit_set_invertible_t &other)
202 {
203 if (likely (inverted == other.inverted))
204 {
205 if (unlikely (inverted))
206 process (hb_bitwise_or, other);
207 else
208 process (hb_bitwise_and, other); /* Main branch. */
209 }
210 else
211 {
212 if (unlikely (inverted))
213 process (hb_bitwise_lt, other);
214 else
215 process (hb_bitwise_gt, other);
216 }
217 if (likely (s.successful))
218 inverted = inverted && other.inverted;
219 }
220 void subtract (const hb_bit_set_invertible_t &other)
221 {
222 if (likely (inverted == other.inverted))
223 {
224 if (unlikely (inverted))
225 process (hb_bitwise_lt, other);
226 else
227 process (hb_bitwise_gt, other); /* Main branch. */
228 }
229 else
230 {
231 if (unlikely (inverted))
232 process (hb_bitwise_or, other);
233 else
234 process (hb_bitwise_and, other);
235 }
236 if (likely (s.successful))
237 inverted = inverted && !other.inverted;
238 }
239 void symmetric_difference (const hb_bit_set_invertible_t &other)
240 {
241 process (hb_bitwise_xor, other);
242 if (likely (s.successful))
243 inverted = inverted ^ other.inverted;
244 }
245
246 bool next (hb_codepoint_t *codepoint) const
247 {
248 if (likely (!inverted))
249 return s.next (codepoint);
250
251 auto old = *codepoint;
252 if (unlikely (old + 1 == INVALID))
253 {
254 *codepoint = INVALID;
255 return false;
256 }
257
258 auto v = old;
259 s.next (&v);
260 if (old + 1 < v)
261 {
262 *codepoint = old + 1;
263 return true;
264 }
265
266 v = old;
267 s.next_range (&old, &v);
268
269 *codepoint = v + 1;
270 return *codepoint != INVALID;
271 }
272 bool previous (hb_codepoint_t *codepoint) const
273 {
274 if (likely (!inverted))
275 return s.previous (codepoint);
276
277 auto old = *codepoint;
278 if (unlikely (old - 1 == INVALID))
279 {
280 *codepoint = INVALID;
281 return false;
282 }
283
284 auto v = old;
285 s.previous (&v);
286
287 if (old - 1 > v || v == INVALID)
288 {
289 *codepoint = old - 1;
290 return true;
291 }
292
293 v = old;
294 s.previous_range (&v, &old);
295
296 *codepoint = v - 1;
297 return *codepoint != INVALID;
298 }
299 bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const
300 {
301 if (likely (!inverted))
302 return s.next_range (first, last);
303
304 if (!next (last))
305 {
306 *last = *first = INVALID;
307 return false;
308 }
309
310 *first = *last;
311 s.next (last);
312 --*last;
313 return true;
314 }
315 bool previous_range (hb_codepoint_t *first, hb_codepoint_t *last) const
316 {
317 if (likely (!inverted))
318 return s.previous_range (first, last);
319
320 if (!previous (first))
321 {
322 *last = *first = INVALID;
323 return false;
324 }
325
326 *last = *first;
327 s.previous (first);
328 ++*first;
329 return true;
330 }
331
332 unsigned int next_many (hb_codepoint_t codepoint,
333 hb_codepoint_t *out,
334 unsigned int size) const
335 {
336 return inverted ? s.next_many_inverted (codepoint, out, size)
337 : s.next_many (codepoint, out, size);
338 }
339
340 static constexpr hb_codepoint_t INVALID = hb_bit_set_t::INVALID;
341
342 /*
343 * Iterator implementation.
344 */
345 struct iter_t : hb_iter_with_fallback_t<iter_t, hb_codepoint_t>
346 {
347 static constexpr bool is_sorted_iterator = true;
348 static constexpr bool has_fast_len = true;
349 iter_t (const hb_bit_set_invertible_t &s_ = Null (hb_bit_set_invertible_t),
350 bool init = true) : s (&s_), v (INVALID), l(0)
351 {
352 if (init)
353 {
354 l = s->get_population () + 1;
355 __next__ ();
356 }
357 }
358
359 typedef hb_codepoint_t __item_t__;
360 hb_codepoint_t __item__ () const { return v; }
361 bool __more__ () const { return v != INVALID; }
362 void __next__ () { s->next (&v); if (l) l--; }
363 void __prev__ () { s->previous (&v); }
364 unsigned __len__ () const { return l; }
365 iter_t end () const { return iter_t (*s, false); }
366 bool operator != (const iter_t& o) const
367 { return v != o.v || s != o.s; }
368
369 protected:
370 const hb_bit_set_invertible_t *s;
371 hb_codepoint_t v;
372 unsigned l;
373 };
374 iter_t iter () const { return iter_t (*this); }
375 operator iter_t () const { return iter (); }
376};
377
378
379#endif /* HB_BIT_SET_INVERTIBLE_HH */
380