gfx/harfbuzz/src/hb-bimap.hh

   1 /*
   2  * Copyright © 2019 Adobe 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  * Adobe Author(s): Michiharu Ariza
  25  */
  26
  27 #ifndef HB_BIMAP_HH
  28 #define HB_BIMAP_HH
  29
  30 #include "hb.hh"
  31 #include "hb-map.hh"
  32
  33 /* Bi-directional map */
  34 struct hb_bimap_t
  35 {
  36   void reset ()
  37   {
  38     forw_map.reset ();
  39     back_map.reset ();
  40   }
  41
  42   void alloc (unsigned pop)
  43   {
  44     forw_map.alloc (pop);
  45     back_map.alloc (pop);
  46   }
  47
  48   bool in_error () const { return forw_map.in_error () || back_map.in_error (); }
  49
  50   void set (hb_codepoint_t lhs, hb_codepoint_t rhs)
  51   {
  52     if (in_error ()) return;
  53     if (unlikely (lhs == HB_MAP_VALUE_INVALID)) return;
  54     if (unlikely (rhs == HB_MAP_VALUE_INVALID)) { del (lhs); return; }
  55
  56     forw_map.set (lhs, rhs);
  57     if (unlikely (in_error ())) return;
  58
  59     back_map.set (rhs, lhs);
  60     if (unlikely (in_error ())) forw_map.del (lhs);
  61   }
  62
  63   hb_codepoint_t get (hb_codepoint_t lhs) const { return forw_map.get (lhs); }
  64   hb_codepoint_t backward (hb_codepoint_t rhs) const { return back_map.get (rhs); }
  65
  66   hb_codepoint_t operator [] (hb_codepoint_t lhs) const { return get (lhs); }
  67   bool has (hb_codepoint_t lhs) const { return forw_map.has (lhs); }
  68
  69
  70   void del (hb_codepoint_t lhs)
  71   {
  72     back_map.del (get (lhs));
  73     forw_map.del (lhs);
  74   }
  75
  76   void clear ()
  77   {
  78     forw_map.clear ();
  79     back_map.clear ();
  80   }
  81
  82   bool is_empty () const { return forw_map.is_empty (); }
  83
  84   unsigned int get_population () const { return forw_map.get_population (); }
  85
  86   protected:
  87   hb_map_t  forw_map;
  88   hb_map_t  back_map;
  89
  90   public:
  91   auto keys () const HB_AUTO_RETURN (+ forw_map.keys())
  92   auto values () const HB_AUTO_RETURN (+ forw_map.values())
  93   auto iter () const HB_AUTO_RETURN (+ forw_map.iter())
  94 };
  95
  96 /* Incremental bimap: only lhs is given, rhs is incrementally assigned */
  97 struct hb_inc_bimap_t
  98 {
  99   bool in_error () const { return forw_map.in_error () || back_map.in_error (); }
 100
 101   unsigned int get_population () const { return forw_map.get_population (); }
 102
 103   void reset ()
 104   {
 105     forw_map.reset ();
 106     back_map.reset ();
 107   }
 108
 109   void alloc (unsigned pop)
 110   {
 111     forw_map.alloc (pop);
 112     back_map.alloc (pop);
 113   }
 114
 115   void clear ()
 116   {
 117     forw_map.clear ();
 118     back_map.resize (0);
 119   }
 120
 121   /* Add a mapping from lhs to rhs with a unique value if lhs is unknown.
 122    * Return the rhs value as the result.
 123    */
 124   hb_codepoint_t add (hb_codepoint_t lhs)
 125   {
 126     hb_codepoint_t  rhs = forw_map[lhs];
 127     if (rhs == HB_MAP_VALUE_INVALID)
 128     {
 129       rhs = back_map.length;
 130       forw_map.set (lhs, rhs);
 131       back_map.push (lhs);
 132     }
 133     return rhs;
 134   }
 135
 136   hb_codepoint_t skip ()
 137   {
 138     hb_codepoint_t start = back_map.length;
 139     back_map.push (HB_MAP_VALUE_INVALID);
 140     return start;
 141   }
 142
 143   hb_codepoint_t skip (unsigned count)
 144   {
 145     hb_codepoint_t start = back_map.length;
 146     back_map.alloc (back_map.length + count);
 147     for (unsigned i = 0; i < count; i++)
 148       back_map.push (HB_MAP_VALUE_INVALID);
 149     return start;
 150   }
 151
 152   hb_codepoint_t get_next_value () const
 153   { return back_map.length; }
 154
 155   void add_set (const hb_set_t *set)
 156   {
 157     for (auto i : *set) add (i);
 158   }
 159
 160   /* Create an identity map. */
 161   bool identity (unsigned int size)
 162   {
 163     clear ();
 164     for (hb_codepoint_t i = 0; i < size; i++) add (i);
 165     return !in_error ();
 166   }
 167
 168   protected:
 169   static int cmp_id (const void* a, const void* b)
 170   { return (int)*(const hb_codepoint_t *)a - (int)*(const hb_codepoint_t *)b; }
 171
 172   public:
 173   /* Optional: after finished adding all mappings in a random order,
 174    * reassign rhs to lhs so that they are in the same order. */
 175   void sort ()
 176   {
 177     hb_codepoint_t  count = get_population ();
 178     hb_vector_t <hb_codepoint_t> work;
 179     if (unlikely (!work.resize (count, false))) return;
 180
 181     for (hb_codepoint_t rhs = 0; rhs < count; rhs++)
 182       work.arrayZ[rhs] = back_map[rhs];
 183
 184     work.qsort (cmp_id);
 185
 186     clear ();
 187     for (hb_codepoint_t rhs = 0; rhs < count; rhs++)
 188       add (work.arrayZ[rhs]);
 189   }
 190
 191   hb_codepoint_t get (hb_codepoint_t lhs) const { return forw_map.get (lhs); }
 192   hb_codepoint_t backward (hb_codepoint_t rhs) const { return back_map[rhs]; }
 193
 194   hb_codepoint_t operator [] (hb_codepoint_t lhs) const { return get (lhs); }
 195   bool has (hb_codepoint_t lhs) const { return forw_map.has (lhs); }
 196
 197   protected:
 198   hb_map_t forw_map;
 199   hb_vector_t<hb_codepoint_t> back_map;
 200
 201   public:
 202   auto keys () const HB_AUTO_RETURN (+ back_map.iter())
 203 };
 204
 205 #endif /* HB_BIMAP_HH */