source: icGREP/icgrep-devel/icgrep/re/re_cc.cpp @ 4415

Last change on this file since 4415 was 4339, checked in by cameron, 5 years ago

Use hex in canonical names

File size: 6.6 KB
Line 
1/*
2 *  Copyright (c) 2014 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include "re_cc.h"
8#include <llvm/Support/Compiler.h>
9#include <UCD/CaseFolding_txt.h>
10#include <sstream>
11
12namespace re {
13
14CC::CC(const CC * cc1, const CC * cc2)
15: RE(ClassTypeId::CC)
16, mSparseCharSet(cc1->cbegin(), cc1->cend()) {
17    for (const CharSetItem & i : cc2->mSparseCharSet) {
18        insert_range(i.lo_codepoint, i.hi_codepoint);
19    }
20}
21
22CC::CC(const CC & cc)
23: RE(ClassTypeId::CC)
24, mSparseCharSet(cc.cbegin(), cc.cend()) {
25
26}
27
28std::string CC::canonicalName(CC_type t) const {
29    std::stringstream name;
30    name << std::hex;
31    if ((t == ByteClass) && (mSparseCharSet.back().hi_codepoint >= 0x80)) {
32      name << "BC";
33    }
34    else name << "CC";
35    char separator = '_';
36    for (const CharSetItem & i : mSparseCharSet) {
37        name << separator;
38        if (i.lo_codepoint == i.hi_codepoint) {
39            name << i.lo_codepoint;
40        }
41        else {
42            name << i.lo_codepoint << "-" << i.hi_codepoint;
43        }
44        separator = ',';
45    }
46    return name.str();
47}
48
49CodePointType CC::max_codepoint() {
50    return mSparseCharSet.size() == 0 ? 0 : mSparseCharSet.back().hi_codepoint;
51}
52
53void CC::insert_range(const CodePointType lo_codepoint, const CodePointType hi_codepoint) {
54    CharSetItem item(lo_codepoint, hi_codepoint);
55    for (auto i = mSparseCharSet.begin(); i != mSparseCharSet.end(); ) {
56        CharSetItem & range = *i;
57        if (item.hi_codepoint < range.lo_codepoint - 1) {
58            mSparseCharSet.insert(i, item);
59            return;
60        }
61        else if (item.lo_codepoint > range.hi_codepoint + 1) {
62            ++i;
63        }
64        else {
65            // ranges overlap; expand the range to include the prior one and
66            // remove the old one from the list
67            range.lo_codepoint = std::min(range.lo_codepoint, item.lo_codepoint);
68            range.hi_codepoint = std::max(range.hi_codepoint, item.hi_codepoint);
69            return;
70        }
71    }
72    mSparseCharSet.push_back(item);
73}
74
75void CC::remove_range(const CodePointType lo_codepoint, const CodePointType hi_codepoint) {
76    for (auto i = mSparseCharSet.begin(); i != mSparseCharSet.end(); ) {
77        CharSetItem & range = *i;
78        if (lo_codepoint > range.hi_codepoint + 1) {
79            ++i;
80        }
81        else if (hi_codepoint < range.lo_codepoint - 1) {
82            break;
83        }
84        else if (lo_codepoint <= range.lo_codepoint && hi_codepoint >= range.hi_codepoint) {
85            i = mSparseCharSet.erase(i);
86        }
87        else if (lo_codepoint <= range.lo_codepoint) {
88            range.lo_codepoint = hi_codepoint + 1;
89            break;
90        }
91        else if (hi_codepoint >= range.hi_codepoint) {
92            range.hi_codepoint = lo_codepoint - 1;
93            ++i;
94        }
95        else {
96            CharSetItem item(hi_codepoint + 1, range.hi_codepoint);
97            range.hi_codepoint = lo_codepoint - 1;
98            mSparseCharSet.insert(++i, std::move(item));
99            break;
100        }
101    }
102}
103
104CC::SetRelationship CC::compare(const CC * other) const {
105
106    if (LLVM_UNLIKELY(other == this)) {
107        return SetRelationship::EQUIVALENT;
108    }
109
110    auto ai = cbegin();
111    const auto ai_end = cend();
112    auto bi = other->cbegin();
113    const auto bi_end = other->cend();
114
115    bool nonSubset = false;
116    bool nonSuperset = false;
117    bool disjoint = true;
118
119    while (ai != ai_end && bi != bi_end) {
120        const CharSetItem & ra = *ai;
121        const CharSetItem & rb = *bi;
122
123        // _A_| ...
124        //     |_B_
125
126        // A may be a superset of B but it cannot be a subset of B
127
128        if (ra.hi_codepoint < rb.lo_codepoint) {
129            ++ai;
130            nonSubset = true;
131            continue;
132        }
133
134        //     |_A_
135        // _B_| ...
136
137        // A may be a subset of B but it cannot be a superset of B
138
139
140        if (rb.hi_codepoint < ra.lo_codepoint) {
141            ++bi;
142            nonSuperset = true;
143            continue;
144        }
145
146        disjoint = false;
147
148        // |_A__
149        //   |_B__
150
151        // A may be a superset of B but it cannot be a subset of B nor can it be disjoint
152
153        if (ra.lo_codepoint < rb.lo_codepoint) {
154            nonSubset = true;
155        }
156
157        //   |_A__
158        // |_B__
159
160        // A may be a subset of B but it cannot be a superset of B nor can it be disjoint
161
162        if (rb.lo_codepoint < ra.lo_codepoint) {
163            nonSuperset = true;
164        }
165
166        // __A__| ...
167        // __B______|
168
169        // SUCC(A) may overlap B in some way; only increment A
170
171        if (ra.hi_codepoint <= rb.hi_codepoint) {
172            ++ai;
173        }
174
175        // __A______|
176        // __B__| ...
177
178        // SUCC(B) may overlap A in some way; only increment B
179
180        if (rb.hi_codepoint <= ra.hi_codepoint) {
181            ++bi;
182        }
183
184    }
185    if (disjoint) {
186        return SetRelationship::DISJOINT;
187    }
188
189    if (ai == ai_end && bi != bi_end) {
190        nonSuperset = true;
191    }
192    else if (bi == bi_end && ai != ai_end) {
193        nonSubset = true;
194    }
195
196    if (nonSubset && nonSuperset) {
197        return SetRelationship::OVERLAPPING;
198    }
199    else if (nonSubset) {
200        return SetRelationship::SUPERSET;
201    }
202    else if (nonSuperset) {
203        return SetRelationship::SUBSET;
204    }
205    return SetRelationship::EQUIVALENT;
206}
207
208CC * subtractCC(const CC * cc1, const CC * cc2) {
209    CC * diff = makeCC();
210    for (const CharSetItem & i : cc1->mSparseCharSet) {
211        diff->insert_range(i.lo_codepoint, i.hi_codepoint);
212    }
213    for (const CharSetItem & i : cc2->mSparseCharSet) {
214        diff->remove_range(i.lo_codepoint, i.hi_codepoint);
215    }
216    return diff;
217}
218   
219CC * intersectCC(const CC * a, const CC * b) {
220    CC * isect = makeCC();
221    auto ai = a->cbegin();
222    const auto ai_end = a->cend();
223    auto bi = b->cbegin();
224    const auto bi_end = b->cend();
225    while (ai != ai_end && bi != bi_end) {
226        const CharSetItem & ra = *ai;
227        const CharSetItem & rb = *bi;
228        if (ra.hi_codepoint < rb.lo_codepoint) {
229            ++ai;
230            continue;
231        }
232        else if (rb.hi_codepoint < ra.lo_codepoint) {
233            ++bi;
234            continue;
235        }
236        isect->insert_range(std::max(ra.lo_codepoint, rb.lo_codepoint), std::min(ra.hi_codepoint, rb.hi_codepoint));
237        if (ra.hi_codepoint < rb.hi_codepoint) ++ai; 
238        else ++bi;
239    }
240    return isect;
241}
242   
243CC * caseInsensitize(const CC * cc) {
244    CC * cci = makeCC();
245    for (auto i = cc->cbegin(); i != cc->cend(); i++) {
246        caseInsensitiveInsertRange(cci, i->lo_codepoint, i->hi_codepoint);
247    }
248    return cci;
249}
250   
251}
Note: See TracBrowser for help on using the repository browser.