source: icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp @ 4611

Last change on this file since 4611 was 4611, checked in by nmedfort, 4 years ago

Temporary check-in

File size: 12.0 KB
Line 
1//
2// unicode_set.cpp - representing and manipulating sets of Unicode
3// characters, based on data from UCD - the Unicode Character Database
4//
5// Robert D. Cameron
6// September 18, 2014
7//
8// Licensed under Open Software License 3.0.
9//
10// Unicode Sparse Bitset Representation
11//
12// The Unicode Sparse Bitset representation is based on
13// (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
14// (b) Specifying the quads using a run-length encoding, in which each run
15//     is Empty (quads contain no members), Mixed (quads contain some members and
16//     some nonmembers) or Full (all codepoints in each quad are members of the set).
17// (c) Explicitly listing all the quads of Mixed type.
18//
19
20#include "unicode_set.h"
21#include "assert.h"
22#include <string>
23#include <iostream>
24
25bool Uset_Iterator::at_end() {
26    return run_no == uSet.runs.size();
27}
28
29RunStructure Uset_Iterator::current_run() {
30    RunStructure this_run = uSet.runs[run_no];
31    return RunStructure(this_run.run_type, this_run.run_length - offset);
32}
33
34bitquad_t Uset_Iterator::get_quad() {
35    RunStructure this_run = uSet.runs[run_no];
36    if (this_run.run_type == Empty) return 0;
37    else if (this_run.run_type == Full) return FullQuadMask;
38    else return uSet.quads[quad_no];
39}
40
41void Uset_Iterator::advance(int n) {
42    while (n > 0) {
43        RunStructure this_run = uSet.runs[run_no];
44        int remain = this_run.run_length - offset;
45        if (remain > n) {
46            offset += n;
47            if (this_run.run_type == Mixed) quad_no += n;
48            n = 0;
49        }
50        else if (remain == n) {
51            run_no += 1;
52            offset = 0;
53            if (this_run.run_type == Mixed) quad_no += n;
54            n = 0;
55        }
56        else {
57            run_no += 1;
58            offset = 0;
59            if (this_run.run_type == Mixed) quad_no += remain;
60            n -= remain;
61        }
62    }
63}
64
65void UnicodeSet::append_run(run_type_t run_type, int run_length) {
66    if (run_length == 0) {
67        return;
68    }
69    else if (runs.size() == 0) {
70        runs.emplace_back(run_type, run_length);
71    }
72    else {
73        RunStructure last_run = runs[runs.size()-1];
74        if (last_run.run_type == run_type) {
75            runs[runs.size()-1].run_length += run_length;
76        }
77        else {
78            runs.emplace_back(run_type, run_length);
79        }
80    }
81    quad_count += run_length;
82}
83
84void UnicodeSet::append_quad(bitquad_t q) {
85    if (q == 0) {
86        append_run(Empty, 1);
87    }
88    else if (q == FullQuadMask) {
89        append_run(Full, 1);
90    }
91    else {
92        quads.push_back(q);
93        append_run(Mixed, 1);
94    }
95}
96
97void Dump_uset(const UnicodeSet & s) {
98    Uset_Iterator it(s);
99    while (!it.at_end()) {
100        RunStructure this_run = it.current_run();
101        if (this_run.run_type == Empty) {
102            std::cout << "Empty(" << this_run.run_length << ")\n";
103            it.advance(this_run.run_length);
104        }
105        else if (this_run.run_type == Full) {
106            std::cout << "Full(" << this_run.run_length << ")\n";
107            it.advance(this_run.run_length);
108        }
109        else {
110            for (int i = 0; i < this_run.run_length; i++) {
111                std::cout << "Mixed(" << std::hex << it.get_quad() << std::dec << ")\n";
112                it.advance(1);
113            }
114        }
115    }
116}
117
118UnicodeSet empty_uset() {
119    UnicodeSet iset;
120    iset.runs.emplace_back(Empty, UnicodeQuadCount);
121    iset.quad_count = UnicodeQuadCount;
122    return iset;
123}
124
125// singleton set constructor
126UnicodeSet singleton_uset(int codepoint) {
127    UnicodeSet iset;
128    int quad_no = codepoint / quad_bits;
129    bitquad_t quad_val = 1 << (codepoint & mod_quad_bit_mask);
130    if (quad_no > 0) iset.append_run(Empty, quad_no);
131    iset.append_run(Mixed, 1);
132    iset.quads.push_back(quad_val);
133    if (quad_no < UnicodeQuadCount - 1) iset.append_run(Empty, UnicodeQuadCount - (quad_no + 1));
134    iset.quad_count =  UnicodeQuadCount;
135    return iset;
136}
137
138// range set constructor
139UnicodeSet range_uset(int lo_codepoint, int hi_codepoint) {
140    UnicodeSet iset;
141    int lo_quad_no = lo_codepoint / quad_bits;
142    int hi_quad_no = hi_codepoint / quad_bits;
143    int lo_offset = lo_codepoint & mod_quad_bit_mask;
144    int hi_offset = hi_codepoint & mod_quad_bit_mask;
145    if (lo_quad_no > 0) iset.append_run(Empty, lo_quad_no);
146    if (lo_quad_no == hi_quad_no) {
147        bitquad_t quad = (FullQuadMask << lo_offset) & (FullQuadMask >> (quad_bits - 1 - hi_offset));
148        iset.append_quad(quad);
149    }
150    else {
151        iset.append_quad((FullQuadMask << lo_offset) & FullQuadMask);
152        iset.append_run(Full, hi_quad_no - (lo_quad_no + 1));
153        iset.append_quad((FullQuadMask >> (quad_bits - 1 - hi_offset)) & FullQuadMask);
154    }
155    if (hi_quad_no < UnicodeQuadCount - 1) iset.append_run(Empty, UnicodeQuadCount - (hi_quad_no + 1));
156    return iset;
157}
158
159UnicodeSet uset_complement (const UnicodeSet & s) {
160    assert(s.quad_count == UnicodeQuadCount);
161    UnicodeSet iset;
162    Uset_Iterator it(s);
163    while (!it.at_end()) {
164        RunStructure this_run = it.current_run();
165        if (this_run.run_type == Empty) {
166            iset.append_run(Full, this_run.run_length);
167            it.advance(this_run.run_length);
168        }
169        else if (this_run.run_type == Full) {
170            iset.append_run(Empty, this_run.run_length);
171            it.advance(this_run.run_length);
172        }
173        else {
174            for (int i = 0; i < this_run.run_length; i++) {
175                iset.append_quad(FullQuadMask ^ it.get_quad());
176                it.advance(1);
177            }
178        }
179    }
180    return iset;
181}
182
183UnicodeSet uset_intersection (const UnicodeSet & s1, const UnicodeSet & s2) {
184    assert(s1.quad_count == UnicodeQuadCount);
185    assert(s2.quad_count == UnicodeQuadCount);
186    UnicodeSet iset;
187    Uset_Iterator i1(s1);
188    Uset_Iterator i2(s2);
189    while (!i1.at_end()) {
190        RunStructure run1 = i1.current_run();
191        RunStructure run2 = i2.current_run();
192        int n = std::min(run1.run_length, run2.run_length);
193        if ((run1.run_type == Empty) || (run2.run_type == Empty)) {
194            iset.append_run(Empty, n);
195            i1.advance(n);
196            i2.advance(n);
197        }
198        else if ((run1.run_type == Full) && (run2.run_type == Full)) {
199            iset.append_run(Full, n);
200            i1.advance(n);
201            i2.advance(n);
202        }
203        else if (run1.run_type == Full) {
204            for (int i = 0; i < n; i++) {
205                iset.append_quad(i2.get_quad());
206                i2.advance(1);
207            }
208            i1.advance(n);
209        }
210        else if (run2.run_type == Full) {
211            for (int i = 0; i < n; i++) {
212                iset.append_quad(i1.get_quad());
213                i1.advance(1);
214            }
215            i2.advance(n);
216        }
217        else {
218            for (int i = 0; i < n; i++) {
219                iset.append_quad(i1.get_quad() & i2.get_quad());
220                i1.advance(1);
221                i2.advance(1);
222            }
223        }
224    }
225    return iset;
226}
227
228UnicodeSet uset_union (const UnicodeSet & s1, const UnicodeSet & s2) {
229    assert(s1.quad_count == UnicodeQuadCount);
230    assert(s2.quad_count == UnicodeQuadCount);
231    UnicodeSet iset;
232    Uset_Iterator i1(s1);
233    Uset_Iterator i2(s2);
234    while (!i1.at_end()) {
235        RunStructure run1 = i1.current_run();
236        RunStructure run2 = i2.current_run();
237        int n = std::min(run1.run_length, run2.run_length);
238        if ((run1.run_type == Empty) && (run2.run_type == Empty)) {
239            iset.append_run(Empty, n);
240            i1.advance(n);
241            i2.advance(n);
242        }
243        else if ((run1.run_type == Full) || (run2.run_type == Full)) {
244            iset.append_run(Full, n);
245            i1.advance(n);
246            i2.advance(n);
247        }
248        else if (run1.run_type == Empty) {
249            for (int i = 0; i < n; i++) {
250                iset.append_quad(i2.get_quad());
251                i2.advance(1);
252            }
253            i1.advance(n);
254        }
255        else if (run2.run_type == Empty) {
256            for (int i = 0; i < n; i++) {
257                iset.append_quad(i1.get_quad());
258                i1.advance(1);
259            }
260            i2.advance(n);
261        }
262        else {
263            for (int i = 0; i < n; i++) {
264                iset.append_quad(i1.get_quad() | i2.get_quad());
265                i1.advance(1);
266                i2.advance(1);
267            }
268        }
269    }
270    return iset;
271}
272
273UnicodeSet uset_difference (const UnicodeSet & s1, const UnicodeSet & s2) {
274    assert(s1.quad_count == UnicodeQuadCount);
275    assert(s2.quad_count == UnicodeQuadCount);
276    UnicodeSet iset;
277    Uset_Iterator i1(s1);
278    Uset_Iterator i2(s2);
279    while (!i1.at_end()) {
280        RunStructure run1 = i1.current_run();
281        RunStructure run2 = i2.current_run();
282        int n = std::min(run1.run_length, run2.run_length);
283        if ((run1.run_type == Empty) || (run2.run_type == Full)) {
284            iset.append_run(Empty, n);
285            i1.advance(n);
286            i2.advance(n);
287        }
288        else if ((run1.run_type == Full) && (run2.run_type == Empty)) {
289            iset.append_run(Full, n);
290            i1.advance(n);
291            i2.advance(n);
292        }
293        else if (run1.run_type == Full) {
294            for (int i = 0; i < n; i++) {
295                iset.append_quad(FullQuadMask ^ i2.get_quad());
296                i2.advance(1);
297            }
298            i1.advance(n);
299        }
300        else if (run2.run_type == Empty) {
301            for (int i = 0; i < n; i++) {
302                iset.append_quad(i1.get_quad());
303                i1.advance(1);
304            }
305            i2.advance(n);
306        }
307        else {
308            for (int i = 0; i < n; i++) {
309                iset.append_quad(i1.get_quad() & ~i2.get_quad());
310                i1.advance(1);
311                i2.advance(1);
312            }
313        }
314    }
315    return iset;
316}
317
318UnicodeSet uset_symmetric_difference (const UnicodeSet & s1, const UnicodeSet & s2) {
319    assert(s1.quad_count == UnicodeQuadCount);
320    assert(s2.quad_count == UnicodeQuadCount);
321    UnicodeSet iset;
322    Uset_Iterator i1(s1);
323    Uset_Iterator i2(s2);
324    while (!i1.at_end()) {
325        RunStructure run1 = i1.current_run();
326        RunStructure run2 = i2.current_run();
327        int n = std::min(run1.run_length, run2.run_length);
328        if (((run1.run_type == Empty) && (run2.run_type == Full)) || ((run1.run_type == Full) && (run2.run_type == Empty))) {
329            iset.append_run(Full, n);
330            i1.advance(n);
331            i2.advance(n);
332        }
333        else if (((run1.run_type == Full) && (run2.run_type == Full)) || ((run1.run_type == Empty) && (run2.run_type == Empty))) {
334            iset.append_run(Empty, n);
335            i1.advance(n);
336            i2.advance(n);
337        }
338        else if (run1.run_type == Empty) {
339            for (int i = 0; i < n; i++) {
340                iset.append_quad(i2.get_quad());
341                i2.advance(1);
342            }
343            i1.advance(n);
344        }
345        else if (run2.run_type == Empty) {
346            for (int i = 0; i < n; i++) {
347                iset.append_quad(i1.get_quad());
348                i1.advance(1);
349            }
350            i2.advance(n);
351        }
352        else if (run1.run_type == Full) {
353            for (int i = 0; i < n; i++) {
354                iset.append_quad(FullQuadMask ^ i2.get_quad());
355                i2.advance(1);
356            }
357            i1.advance(n);
358        }
359        else if (run2.run_type == Empty) {
360            for (int i = 0; i < n; i++) {
361                iset.append_quad(FullQuadMask ^ i1.get_quad());
362                i1.advance(1);
363            }
364            i2.advance(n);
365        }
366        else {
367            for (int i = 0; i < n; i++) {
368                iset.append_quad(i1.get_quad() ^ i2.get_quad());
369                i1.advance(1);
370                i2.advance(1);
371            }
372        }
373    }
374    return iset;
375}
376
377bool uset_member(const UnicodeSet & s, int codepoint){
378    int quad_no = codepoint / quad_bits;
379    bitquad_t quad_val = 1 << (codepoint & mod_quad_bit_mask);
380    Uset_Iterator it(s);
381    it.advance(quad_no);
382    return (it.get_quad() & quad_val) != 0;
383}
Note: See TracBrowser for help on using the repository browser.