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 | void alloc (unsigned pop) |
43 | { |
44 | forw_map.alloc (pop); |
45 | back_map.alloc (pop); |
46 | } |
47 | |
48 | bool in_error () const { return forw_map.in_error () || back_map.in_error (); } |
49 | |
50 | 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 | |
63 | hb_codepoint_t get (hb_codepoint_t lhs) const { return forw_map.get (lhs); } |
64 | hb_codepoint_t backward (hb_codepoint_t rhs) const { return back_map.get (rhs); } |
65 | |
66 | hb_codepoint_t operator [] (hb_codepoint_t lhs) const { return get (lhs); } |
67 | bool has (hb_codepoint_t lhs) const { return forw_map.has (lhs); } |
68 | |
69 | |
70 | void del (hb_codepoint_t lhs) |
71 | { |
72 | back_map.del (get (lhs)); |
73 | forw_map.del (lhs); |
74 | } |
75 | |
76 | void clear () |
77 | { |
78 | forw_map.clear (); |
79 | back_map.clear (); |
80 | } |
81 | |
82 | bool is_empty () const { return forw_map.is_empty (); } |
83 | |
84 | 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 | public: |
91 | auto keys () const HB_AUTO_RETURN (+ forw_map.keys()) |
92 | auto values () const HB_AUTO_RETURN (+ forw_map.values()) |
93 | auto iter () const HB_AUTO_RETURN (+ forw_map.iter()) |
94 | }; |
95 | |
96 | /* Inremental bimap: only lhs is given, rhs is incrementally assigned */ |
97 | struct hb_inc_bimap_t |
98 | { |
99 | bool in_error () const { return forw_map.in_error () || back_map.in_error (); } |
100 | |
101 | unsigned int get_population () const { return forw_map.get_population (); } |
102 | |
103 | void reset () |
104 | { |
105 | forw_map.reset (); |
106 | back_map.reset (); |
107 | } |
108 | |
109 | void alloc (unsigned pop) |
110 | { |
111 | forw_map.alloc (pop); |
112 | back_map.alloc (pop); |
113 | } |
114 | |
115 | void clear () |
116 | { |
117 | forw_map.clear (); |
118 | back_map.resize (0); |
119 | } |
120 | |
121 | /* Add a mapping from lhs to rhs with a unique value if lhs is unknown. |
122 | * Return the rhs value as the result. |
123 | */ |
124 | hb_codepoint_t add (hb_codepoint_t lhs) |
125 | { |
126 | hb_codepoint_t rhs = forw_map[lhs]; |
127 | if (rhs == HB_MAP_VALUE_INVALID) |
128 | { |
129 | rhs = back_map.length; |
130 | forw_map.set (lhs, rhs); |
131 | back_map.push (lhs); |
132 | } |
133 | return rhs; |
134 | } |
135 | |
136 | hb_codepoint_t skip () |
137 | { |
138 | hb_codepoint_t start = back_map.length; |
139 | back_map.push (HB_MAP_VALUE_INVALID); |
140 | return start; |
141 | } |
142 | |
143 | hb_codepoint_t skip (unsigned count) |
144 | { |
145 | hb_codepoint_t start = back_map.length; |
146 | back_map.alloc (back_map.length + count); |
147 | for (unsigned i = 0; i < count; i++) |
148 | back_map.push (HB_MAP_VALUE_INVALID); |
149 | return start; |
150 | } |
151 | |
152 | hb_codepoint_t get_next_value () const |
153 | { return back_map.length; } |
154 | |
155 | void add_set (const hb_set_t *set) |
156 | { |
157 | for (auto i : *set) add (i); |
158 | } |
159 | |
160 | /* Create an identity map. */ |
161 | bool identity (unsigned int size) |
162 | { |
163 | clear (); |
164 | for (hb_codepoint_t i = 0; i < size; i++) add (i); |
165 | return !in_error (); |
166 | } |
167 | |
168 | protected: |
169 | static int cmp_id (const void* a, const void* b) |
170 | { return (int)*(const hb_codepoint_t *)a - (int)*(const hb_codepoint_t *)b; } |
171 | |
172 | public: |
173 | /* Optional: after finished adding all mappings in a random order, |
174 | * reassign rhs to lhs so that they are in the same order. */ |
175 | void sort () |
176 | { |
177 | hb_codepoint_t count = get_population (); |
178 | hb_vector_t <hb_codepoint_t> work; |
179 | if (unlikely (!work.resize (count, false))) return; |
180 | |
181 | for (hb_codepoint_t rhs = 0; rhs < count; rhs++) |
182 | work.arrayZ[rhs] = back_map[rhs]; |
183 | |
184 | work.qsort (cmp_id); |
185 | |
186 | clear (); |
187 | for (hb_codepoint_t rhs = 0; rhs < count; rhs++) |
188 | add (work.arrayZ[rhs]); |
189 | } |
190 | |
191 | hb_codepoint_t get (hb_codepoint_t lhs) const { return forw_map.get (lhs); } |
192 | hb_codepoint_t backward (hb_codepoint_t rhs) const { return back_map[rhs]; } |
193 | |
194 | hb_codepoint_t operator [] (hb_codepoint_t lhs) const { return get (lhs); } |
195 | bool has (hb_codepoint_t lhs) const { return forw_map.has (lhs); } |
196 | |
197 | protected: |
198 | hb_map_t forw_map; |
199 | hb_vector_t<hb_codepoint_t> back_map; |
200 | |
201 | public: |
202 | auto keys () const HB_AUTO_RETURN (+ back_map.iter()) |
203 | }; |
204 | |
205 | #endif /* HB_BIMAP_HH */ |
206 | |