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 */
34struct 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 */
97struct 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