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 { hb_bimap_thb_bimap_t36 hb_bimap_t () { init (); } ~hb_bimap_thb_bimap_t37 ~hb_bimap_t () { fini (); } 38 inithb_bimap_t39 void init () 40 { 41 forw_map.init (); 42 back_map.init (); 43 } 44 finihb_bimap_t45 void fini () 46 { 47 forw_map.fini (); 48 back_map.fini (); 49 } 50 resethb_bimap_t51 void reset () 52 { 53 forw_map.reset (); 54 back_map.reset (); 55 } 56 in_errorhb_bimap_t57 bool in_error () const { return forw_map.in_error () || back_map.in_error (); } 58 sethb_bimap_t59 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 gethb_bimap_t67 hb_codepoint_t get (hb_codepoint_t lhs) const { return forw_map.get (lhs); } backwardhb_bimap_t68 hb_codepoint_t backward (hb_codepoint_t rhs) const { return back_map.get (rhs); } 69 operator []hb_bimap_t70 hb_codepoint_t operator [] (hb_codepoint_t lhs) const { return get (lhs); } hashb_bimap_t71 bool has (hb_codepoint_t lhs, hb_codepoint_t *vp = nullptr) const { return forw_map.has (lhs, vp); } 72 delhb_bimap_t73 void del (hb_codepoint_t lhs) 74 { 75 back_map.del (get (lhs)); 76 forw_map.del (lhs); 77 } 78 clearhb_bimap_t79 void clear () 80 { 81 forw_map.clear (); 82 back_map.clear (); 83 } 84 is_emptyhb_bimap_t85 bool is_empty () const { return get_population () == 0; } 86 get_populationhb_bimap_t87 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 { hb_inc_bimap_thb_inc_bimap_t97 hb_inc_bimap_t () { init (); } 98 inithb_inc_bimap_t99 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 */ addhb_inc_bimap_t108 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 skiphb_inc_bimap_t119 hb_codepoint_t skip () 120 { return next_value++; } 121 get_next_valuehb_inc_bimap_t122 hb_codepoint_t get_next_value () const 123 { return next_value; } 124 add_sethb_inc_bimap_t125 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. */ identityhb_inc_bimap_t132 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: cmp_idhb_inc_bimap_t140 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. */ sorthb_inc_bimap_t146 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 */ 167