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