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

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

Replaced USet_Iterator with a standard C++ UnicodeSet? iterator.

File size: 11.4 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
25const size_t QUAD_BITS = (8 * sizeof(bitquad_t));
26const size_t MOD_QUAD_BIT_MASK = QUAD_BITS - 1;
27const size_t UNICODE_QUAD_COUNT = 0x110000 / QUAD_BITS;
28const bitquad_t FULL_QUAD_MASK = -1;
29
30
31inline const RunStructure & get_run(UnicodeSet::iterator i) {
32    return std::get<0>(*i);
33}
34
35inline bitquad_t get_quad(UnicodeSet::iterator i) {
36    return std::get<1>(*i);
37}
38
39const std::pair<RunStructure, bitquad_t> UnicodeSet::iterator::dereference() const {
40    const RunStructure & t = mUnicodeSet.runs[mRunIndex];
41    RunStructure s(t.mType, t.mRunLength - mOffset);
42    const bitquad_t q = ((t.mType == Empty) ? 0 : (t.mType == Full) ? FULL_QUAD_MASK : mUnicodeSet.quads[mQuadIndex]);
43    return std::make_pair(s, q);
44}
45
46void UnicodeSet::iterator::advance(unsigned n) {
47    while (n > 0) {
48        const RunStructure & t = mUnicodeSet.runs[mRunIndex];
49        int remain = t.mRunLength - mOffset;
50        if (remain > n) {
51            mOffset += n;
52            if (t.mType == Mixed) {
53                mQuadIndex += n;
54            }
55            break;
56        }
57        else if (remain == n) {
58            ++mRunIndex;
59            mOffset = 0;
60            if (t.mType == Mixed) {
61                mQuadIndex += n;
62            }
63            break;
64        }
65        else {
66            ++mRunIndex;
67            mOffset = 0;
68            if (t.mType == Mixed) {
69                mQuadIndex += remain;
70            }
71            n -= remain;
72        }
73    }
74}
75
76void UnicodeSet::append_run(run_type_t run_type, int run_length) {
77    if (run_length == 0) {
78        return;
79    }
80    else if (runs.size() == 0) {
81        runs.emplace_back(run_type, run_length);
82    }
83    else {
84        RunStructure last_run = runs[runs.size()-1];
85        if (last_run.mType == run_type) {
86            runs.back().mRunLength += run_length;
87        }
88        else {
89            runs.emplace_back(run_type, run_length);
90        }
91    }
92    quad_count += run_length;
93}
94
95void UnicodeSet::append_quad(bitquad_t q) {
96    if (q == 0) {
97        append_run(Empty, 1);
98    }
99    else if (q == FULL_QUAD_MASK) {
100        append_run(Full, 1);
101    }
102    else {
103        quads.push_back(q);
104        append_run(Mixed, 1);
105    }
106}
107
108void Dump_uset(const UnicodeSet & s) {
109    for (auto it = s.begin(); it != s.end(); ++it) {
110        RunStructure this_run = get_run(it);
111        if (this_run.mType == Empty) {
112            std::cout << "Empty(" << this_run.mRunLength << ")\n";
113            it += this_run.mRunLength;
114        }
115        else if (this_run.mType == Full) {
116            std::cout << "Full(" << this_run.mRunLength << ")\n";
117            it += this_run.mRunLength;
118        }
119        else {
120            for (int i = 0; i != this_run.mRunLength; i++) {
121                std::cout << "Mixed(" << std::hex << get_quad(it) << std::dec << ")\n";
122                ++it;
123            }
124        }
125    }
126}
127
128UnicodeSet empty_uset() {
129    UnicodeSet iset;
130    iset.runs.emplace_back(Empty, UNICODE_QUAD_COUNT);
131    iset.quad_count = UNICODE_QUAD_COUNT;
132    return iset;
133}
134
135// singleton set constructor
136UnicodeSet singleton_uset(int codepoint) {
137    UnicodeSet iset;
138    int quad_no = codepoint / QUAD_BITS;
139    bitquad_t quad_val = 1 << (codepoint & MOD_QUAD_BIT_MASK);
140    if (quad_no > 0) iset.append_run(Empty, quad_no);
141    iset.append_run(Mixed, 1);
142    iset.quads.push_back(quad_val);
143    if (quad_no < UNICODE_QUAD_COUNT - 1) iset.append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1));
144    iset.quad_count =  UNICODE_QUAD_COUNT;
145    return iset;
146}
147
148// range set constructor
149UnicodeSet range_uset(int lo_codepoint, int hi_codepoint) {
150    UnicodeSet iset;
151    int lo_quad_no = lo_codepoint / QUAD_BITS;
152    int hi_quad_no = hi_codepoint / QUAD_BITS;
153    int lo_offset = lo_codepoint & MOD_QUAD_BIT_MASK;
154    int hi_offset = hi_codepoint & MOD_QUAD_BIT_MASK;
155    if (lo_quad_no > 0) iset.append_run(Empty, lo_quad_no);
156    if (lo_quad_no == hi_quad_no) {
157        bitquad_t quad = (FULL_QUAD_MASK << lo_offset) & (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
158        iset.append_quad(quad);
159    }
160    else {
161        iset.append_quad((FULL_QUAD_MASK << lo_offset) & FULL_QUAD_MASK);
162        iset.append_run(Full, hi_quad_no - (lo_quad_no + 1));
163        iset.append_quad((FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset)) & FULL_QUAD_MASK);
164    }
165    if (hi_quad_no < UNICODE_QUAD_COUNT - 1) iset.append_run(Empty, UNICODE_QUAD_COUNT - (hi_quad_no + 1));
166    return iset;
167}
168
169UnicodeSet uset_complement (const UnicodeSet & s) {
170    assert(s.quad_count == UNICODE_QUAD_COUNT);
171    UnicodeSet iset;
172    for (auto itr = s.begin(); itr != s.end(); ) {
173        auto run = get_run(itr);
174        if (run.mType == Empty) {
175            iset.append_run(Full, run.mRunLength);
176            itr += run.mRunLength;
177        }
178        else if (run.mType == Full) {
179            iset.append_run(Empty, run.mRunLength);
180            itr += run.mRunLength;
181        }
182        else {
183            for (unsigned i = 0; i != run.mRunLength; i++) {
184                iset.append_quad(FULL_QUAD_MASK ^ get_quad(itr++));
185            }
186        }
187    }
188    return iset;
189}
190
191UnicodeSet uset_intersection (const UnicodeSet & s1, const UnicodeSet & s2) {
192    assert(s1.quad_count == UNICODE_QUAD_COUNT);
193    assert(s2.quad_count == UNICODE_QUAD_COUNT);
194    UnicodeSet iset;
195    for (auto i1 = s1.begin(), i2 = s2.begin(); i1 != s1.end(); ) {
196        auto run1 = get_run(i1);
197        auto run2 = get_run(i2);
198        unsigned n = std::min(run1.mRunLength, run2.mRunLength);
199        if ((run1.mType == Empty) || (run2.mType == Empty)) {
200            iset.append_run(Empty, n);
201            i1 += n;
202            i2 += n;
203        }
204        else if ((run1.mType == Full) && (run2.mType == Full)) {
205            iset.append_run(Full, n);
206            i1 += n;
207            i2 += n;
208        }
209        else if (run1.mType == Full) {
210            for (unsigned i = 0; i != n; ++i, ++i2) {
211                iset.append_quad(get_quad(i2));
212            }
213            i1 += n;
214        }
215        else if (run2.mType == Full) {
216            for (unsigned i = 0; i != n; ++i, ++i1) {
217                iset.append_quad(get_quad(i1));
218            }
219            i2 += n;
220        }
221        else {
222            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
223                iset.append_quad(get_quad(i1) & get_quad(i2));
224            }
225        }
226    }
227    return iset;
228}
229
230UnicodeSet uset_union (const UnicodeSet & s1, const UnicodeSet & s2) {
231    assert(s1.quad_count == UNICODE_QUAD_COUNT);
232    assert(s2.quad_count == UNICODE_QUAD_COUNT);
233    UnicodeSet iset;
234    for (auto i1 = s1.begin(), i2 = s2.begin(); i1 != s1.end(); ) {
235        auto run1 = get_run(i1);
236        auto run2 = get_run(i2);
237        unsigned n = std::min(run1.mRunLength, run2.mRunLength);
238        if ((run1.mType == Empty) && (run2.mType == Empty)) {
239            iset.append_run(Empty, n);
240            i1 += n;
241            i2 += n;
242        }
243        else if ((run1.mType == Full) || (run2.mType == Full)) {
244            iset.append_run(Full, n);
245            i1 += n;
246            i2 += n;
247        }
248        else if (run1.mType == Empty) {
249            for (unsigned i = 0; i < n; ++i, ++i2) {
250                iset.append_quad(get_quad(i2));
251            }
252            i1 += n;
253        }
254        else if (run2.mType == Empty) {
255            for (unsigned i = 0; i < n; ++i, ++i1) {
256                iset.append_quad(get_quad(i1));
257            }
258            i2 += n;
259        }
260        else {
261            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
262                iset.append_quad(get_quad(i1) | get_quad(i2));
263            }
264        }
265    }
266    return iset;
267}
268
269UnicodeSet uset_difference (const UnicodeSet & s1, const UnicodeSet & s2) {
270    assert(s1.quad_count == UNICODE_QUAD_COUNT);
271    assert(s2.quad_count == UNICODE_QUAD_COUNT);
272    UnicodeSet iset;
273    for (auto i1 = s1.begin(), i2 = s2.begin(); i1 != s1.end(); ) {
274        auto run1 = get_run(i1);
275        auto run2 = get_run(i2);
276        unsigned n = std::min(run1.mRunLength, run2.mRunLength);
277        if ((run1.mType == Empty) || (run2.mType == Full)) {
278            iset.append_run(Empty, n);
279            i1 += n;
280            i2 += n;
281        }
282        else if ((run1.mType == Full) && (run2.mType == Empty)) {
283            iset.append_run(Full, n);
284            i1 += n;
285            i2 += n;
286        }
287        else if (run1.mType == Full) {
288            for (unsigned i = 0; i != n; ++i, ++i2) {
289                iset.append_quad(FULL_QUAD_MASK ^ get_quad(i2));
290            }
291            i1 += n;
292        }
293        else if (run2.mType == Empty) {
294            for (unsigned i = 0; i != n; ++i, ++i1) {
295                iset.append_quad(get_quad(i1));
296            }
297            i2 += n;
298        }
299        else {
300            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
301                iset.append_quad(get_quad(i1) & ~get_quad(i2));
302            }
303        }
304    }
305    return iset;
306}
307
308UnicodeSet uset_symmetric_difference (const UnicodeSet & s1, const UnicodeSet & s2) {
309    assert(s1.quad_count == UNICODE_QUAD_COUNT);
310    assert(s2.quad_count == UNICODE_QUAD_COUNT);
311    UnicodeSet iset;
312    for (auto i1 = s1.begin(), i2 = s2.begin(); i1 != s1.end(); ) {
313        auto run1 = get_run(i1);
314        auto run2 = get_run(i2);
315        unsigned n = std::min(run1.mRunLength, run2.mRunLength);
316        if (((run1.mType == Empty) && (run2.mType == Full)) || ((run1.mType == Full) && (run2.mType == Empty))) {
317            iset.append_run(Full, n);
318            i1 += n;
319            i2 += n;
320        }
321        else if (((run1.mType == Full) && (run2.mType == Full)) || ((run1.mType == Empty) && (run2.mType == Empty))) {
322            iset.append_run(Empty, n);
323            i1 += n;
324            i2 += n;
325        }
326        else if (run1.mType == Empty) {
327            for (int i = 0; i < n; ++i, ++i2) {
328                iset.append_quad(get_quad(i2));
329            }
330            i1 += n;
331        }
332        else if (run2.mType == Empty) {
333            for (int i = 0; i < n; ++i, ++i1) {
334                iset.append_quad(get_quad(i1));
335            }
336            i2 += n;
337        }
338        else if (run1.mType == Full) {
339            for (int i = 0; i < n; ++i, ++i2) {
340                iset.append_quad(FULL_QUAD_MASK ^ get_quad(i2));
341            }
342            i1 += n;
343        }
344        else if (run2.mType == Empty) {
345            for (unsigned i = 0; i < n; ++i, ++i1) {
346                iset.append_quad(FULL_QUAD_MASK ^ get_quad(i1));
347            }
348            i2 += n;
349        }
350        else {
351            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
352                iset.append_quad(get_quad(i1) ^ get_quad(i2));
353            }
354        }
355    }
356    return iset;
357}
358
359bool uset_member(const UnicodeSet & s, int codepoint){
360    int quad_no = codepoint / QUAD_BITS;
361    bitquad_t quad_val = 1 << (codepoint & MOD_QUAD_BIT_MASK);
362    return (get_quad(s.begin() + quad_no) & quad_val) != 0;
363}
Note: See TracBrowser for help on using the repository browser.