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 { resethb_bimap_t36 void reset () 37 { 38 forw_map.reset (); 39 back_map.reset (); 40 } 41 resizehb_bimap_t42 void resize (unsigned pop) 43 { 44 forw_map.resize (pop); 45 back_map.resize (pop); 46 } 47 in_errorhb_bimap_t48 bool in_error () const { return forw_map.in_error () || back_map.in_error (); } 49 sethb_bimap_t50 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 gethb_bimap_t63 hb_codepoint_t get (hb_codepoint_t lhs) const { return forw_map.get (lhs); } backwardhb_bimap_t64 hb_codepoint_t backward (hb_codepoint_t rhs) const { return back_map.get (rhs); } 65 operator []hb_bimap_t66 hb_codepoint_t operator [] (hb_codepoint_t lhs) const { return get (lhs); } hashb_bimap_t67 bool has (hb_codepoint_t lhs) const { return forw_map.has (lhs); } 68 69 delhb_bimap_t70 void del (hb_codepoint_t lhs) 71 { 72 back_map.del (get (lhs)); 73 forw_map.del (lhs); 74 } 75 clearhb_bimap_t76 void clear () 77 { 78 forw_map.clear (); 79 back_map.clear (); 80 } 81 is_emptyhb_bimap_t82 bool is_empty () const { return forw_map.is_empty (); } 83 get_populationhb_bimap_t84 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 91 /* Inremental bimap: only lhs is given, rhs is incrementally assigned */ 92 struct hb_inc_bimap_t : hb_bimap_t 93 { 94 /* Add a mapping from lhs to rhs with a unique value if lhs is unknown. 95 * Return the rhs value as the result. 96 */ addhb_inc_bimap_t97 hb_codepoint_t add (hb_codepoint_t lhs) 98 { 99 hb_codepoint_t rhs = forw_map[lhs]; 100 if (rhs == HB_MAP_VALUE_INVALID) 101 { 102 rhs = next_value++; 103 set (lhs, rhs); 104 } 105 return rhs; 106 } 107 skiphb_inc_bimap_t108 hb_codepoint_t skip () 109 { return next_value++; } 110 get_next_valuehb_inc_bimap_t111 hb_codepoint_t get_next_value () const 112 { return next_value; } 113 add_sethb_inc_bimap_t114 void add_set (const hb_set_t *set) 115 { 116 hb_codepoint_t i = HB_SET_VALUE_INVALID; 117 while (hb_set_next (set, &i)) add (i); 118 } 119 120 /* Create an identity map. */ identityhb_inc_bimap_t121 bool identity (unsigned int size) 122 { 123 clear (); 124 for (hb_codepoint_t i = 0; i < size; i++) set (i, i); 125 return !in_error (); 126 } 127 128 protected: cmp_idhb_inc_bimap_t129 static int cmp_id (const void* a, const void* b) 130 { return (int)*(const hb_codepoint_t *)a - (int)*(const hb_codepoint_t *)b; } 131 132 public: 133 /* Optional: after finished adding all mappings in a random order, 134 * reassign rhs to lhs so that they are in the same order. */ sorthb_inc_bimap_t135 void sort () 136 { 137 hb_codepoint_t count = get_population (); 138 hb_vector_t <hb_codepoint_t> work; 139 work.resize (count); 140 141 for (hb_codepoint_t rhs = 0; rhs < count; rhs++) 142 work[rhs] = back_map[rhs]; 143 144 work.qsort (cmp_id); 145 146 clear (); 147 for (hb_codepoint_t rhs = 0; rhs < count; rhs++) 148 set (work[rhs], rhs); 149 } 150 151 protected: 152 unsigned int next_value = 0; 153 }; 154 155 #endif /* HB_BIMAP_HH */ 156