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