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   bool in_error () const { return forw_map.in_error () || back_map.in_error (); }
  43
  44   void set (hb_codepoint_t lhs, hb_codepoint_t rhs)
  45   {
  46     if (in_error ()) return;
  47     if (unlikely (lhs == HB_MAP_VALUE_INVALID)) return;
  48     if (unlikely (rhs == HB_MAP_VALUE_INVALID)) { del (lhs); return; }
  49
  50     forw_map.set (lhs, rhs);
  51     if (in_error ()) return;
  52
  53     back_map.set (rhs, lhs);
  54     if (in_error ()) forw_map.del (lhs);
  55   }
  56
  57   hb_codepoint_t get (hb_codepoint_t lhs) const { return forw_map.get (lhs); }
  58   hb_codepoint_t backward (hb_codepoint_t rhs) const { return back_map.get (rhs); }
  59
  60   hb_codepoint_t operator [] (hb_codepoint_t lhs) const { return get (lhs); }
  61   bool has (hb_codepoint_t lhs, hb_codepoint_t *vp = nullptr) const { return forw_map.has (lhs, vp); }
  62
  63   void del (hb_codepoint_t lhs)
  64   {
  65     back_map.del (get (lhs));
  66     forw_map.del (lhs);
  67   }
  68
  69   void clear ()
  70   {
  71     forw_map.clear ();
  72     back_map.clear ();
  73   }
  74
  75   bool is_empty () const { return get_population () == 0; }
  76
  77   unsigned int get_population () const { return forw_map.get_population (); }
  78
  79   protected:
  80   hb_map_t  forw_map;
  81   hb_map_t  back_map;
  82 };
  83
  84 /* Inremental bimap: only lhs is given, rhs is incrementally assigned */
  85 struct hb_inc_bimap_t : hb_bimap_t
  86 {
  87   /* Add a mapping from lhs to rhs with a unique value if lhs is unknown.
  88    * Return the rhs value as the result.
  89    */
  90   hb_codepoint_t add (hb_codepoint_t lhs)
  91   {
  92     hb_codepoint_t  rhs = forw_map[lhs];
  93     if (rhs == HB_MAP_VALUE_INVALID)
  94     {
  95       rhs = next_value++;
  96       set (lhs, rhs);
  97     }
  98     return rhs;
  99   }
 100
 101   hb_codepoint_t skip ()
 102   { return next_value++; }
 103
 104   hb_codepoint_t get_next_value () const
 105   { return next_value; }
 106
 107   void add_set (const hb_set_t *set)
 108   {
 109     hb_codepoint_t i = HB_SET_VALUE_INVALID;
 110     while (hb_set_next (set, &i)) add (i);
 111   }
 112
 113   /* Create an identity map. */
 114   bool identity (unsigned int size)
 115   {
 116     clear ();
 117     for (hb_codepoint_t i = 0; i < size; i++) set (i, i);
 118     return !in_error ();
 119   }
 120
 121   protected:
 122   static int cmp_id (const void* a, const void* b)
 123   { return (int)*(const hb_codepoint_t *)a - (int)*(const hb_codepoint_t *)b; }
 124
 125   public:
 126   /* Optional: after finished adding all mappings in a random order,
 127    * reassign rhs to lhs so that they are in the same order. */
 128   void sort ()
 129   {
 130     hb_codepoint_t  count = get_population ();
 131     hb_vector_t <hb_codepoint_t> work;
 132     work.resize (count);
 133
 134     for (hb_codepoint_t rhs = 0; rhs < count; rhs++)
 135       work[rhs] = back_map[rhs];
 136
 137     work.qsort (cmp_id);
 138
 139     clear ();
 140     for (hb_codepoint_t rhs = 0; rhs < count; rhs++)
 141       set (work[rhs], rhs);
 142   }
 143
 144   protected:
 145   unsigned int next_value = 0;
 146 };
 147
 148 #endif /* HB_BIMAP_HH */