src/hb-bit-set-invertible.hh

   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
  35 struct 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 */