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 hb_bimap_t () { init (); }
37 ~hb_bimap_t () { fini (); }
38
39 void init ()
40 {
41 forw_map.init ();
42 back_map.init ();
43 }
44
45 void fini ()
46 {
47 forw_map.fini ();
48 back_map.fini ();
49 }
50
51 void reset ()
52 {
53 forw_map.reset ();
54 back_map.reset ();
55 }
56
57 bool in_error () const { return forw_map.in_error () || back_map.in_error (); }
58
59 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
67 hb_codepoint_t get (hb_codepoint_t lhs) const { return forw_map.get (lhs); }
68 hb_codepoint_t backward (hb_codepoint_t rhs) const { return back_map.get (rhs); }
69
70 hb_codepoint_t operator [] (hb_codepoint_t lhs) const { return get (lhs); }
71 bool has (hb_codepoint_t lhs, hb_codepoint_t *vp = nullptr) const { return forw_map.has (lhs, vp); }
72
73 void del (hb_codepoint_t lhs)
74 {
75 back_map.del (get (lhs));
76 forw_map.del (lhs);
77 }
78
79 void clear ()
80 {
81 forw_map.clear ();
82 back_map.clear ();
83 }
84
85 bool is_empty () const { return get_population () == 0; }
86
87 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 */
95struct hb_inc_bimap_t : hb_bimap_t
96{
97 hb_inc_bimap_t () { init (); }
98
99 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 */
108 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
119 hb_codepoint_t skip ()
120 { return next_value++; }
121
122 hb_codepoint_t get_next_value () const
123 { return next_value; }
124
125 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. */
132 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:
140 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. */
146 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