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

Last change on this file since 4532 was 4189, checked in by cameron, 5 years ago

Unicode data files and sparse bitset representation

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