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