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

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

Minor bug fix for CC canonicalName(...) and slightly more efficient subtractCC function.

File size: 7.9 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#include <iostream>
12
13namespace re {
14CC::CharSetAllocator CC::mCharSetAllocator;
15
16CC::CC(const CC * cc1, const CC * cc2)
17: RE(ClassTypeId::CC)
18, mSparseCharSet(cc1->cbegin(), cc1->cend(), mCharSetAllocator) {
19    for (const CharSetItem & i : cc2->mSparseCharSet) {
20        insert_range(i.lo_codepoint, i.hi_codepoint);
21    }
22}
23
24CC::CC(const CC & cc)
25: RE(ClassTypeId::CC)
26, mSparseCharSet(cc.cbegin(), cc.cend(), mCharSetAllocator) {
27
28}
29
30std::string CC::canonicalName(const CC_type type) const {
31    std::stringstream name;
32    // name << std::hex;
33    if ((type == ByteClass) && (max_codepoint() >= 0x80)) {
34        name << "BC";
35    }
36    else {
37        name << "CC";
38    }
39    char separator = '_';
40    for (const CharSetItem & i : mSparseCharSet) {
41        name << separator;
42        if (i.lo_codepoint == i.hi_codepoint) {
43            name << i.lo_codepoint;
44        }
45        else {
46            name << i.lo_codepoint << '_' << i.hi_codepoint;
47        }
48        separator = ',';
49    }
50    return name.str();
51}
52
53void CC::insert_range(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) {
54    for (auto i = mSparseCharSet.begin(); i != mSparseCharSet.end(); ) {
55        CharSetItem & range = *i;
56        if (hi_codepoint < range.lo_codepoint - 1) {
57            mSparseCharSet.emplace(i, lo_codepoint, hi_codepoint);
58            return;
59        }
60        else if (lo_codepoint > range.hi_codepoint + 1) {
61            ++i;
62        }
63        else {
64            // ranges overlap; expand the range to include the prior one and
65            // remove the old one from the list
66            range.lo_codepoint = std::min(range.lo_codepoint, lo_codepoint);
67            range.hi_codepoint = std::max(range.hi_codepoint, hi_codepoint);
68            return;
69        }
70    }
71    mSparseCharSet.emplace_back(lo_codepoint, hi_codepoint);
72}
73
74void CC::remove_range(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) {
75    for (auto i = mSparseCharSet.begin(); i != mSparseCharSet.end(); ) {
76        CharSetItem & range = *i;
77        if (lo_codepoint > range.hi_codepoint + 1) {
78            ++i;
79        }
80        else if (hi_codepoint < range.lo_codepoint - 1) {
81            break;
82        }
83        else if (lo_codepoint <= range.lo_codepoint && hi_codepoint >= range.hi_codepoint) {
84            i = mSparseCharSet.erase(i);
85        }
86        else if (lo_codepoint <= range.lo_codepoint) {
87            range.lo_codepoint = hi_codepoint + 1;
88            break;
89        }
90        else if (hi_codepoint >= range.hi_codepoint) {
91            range.hi_codepoint = lo_codepoint - 1;
92            ++i;
93        }
94        else {
95            CharSetItem item(hi_codepoint + 1, range.hi_codepoint);
96            range.hi_codepoint = lo_codepoint - 1;
97            mSparseCharSet.insert(++i, std::move(item));
98            break;
99        }
100    }
101}
102
103CC * subtractCC(const CC * cc1, const CC * cc2) {
104    CC * diff = makeCC();
105    auto ai = cc1->cbegin();
106    const auto ai_end = cc1->cend();
107    auto bi = cc2->cbegin();
108    const auto bi_end = cc2->cend();
109    while (ai != ai_end && bi != bi_end) {
110        const CharSetItem & ra = *ai;
111        const CharSetItem & rb = *bi;
112        if (rb.hi_codepoint < ra.lo_codepoint) {
113            ++bi;
114        }
115        else { // test whether the intervals overlap
116            if (ra.lo_codepoint < rb.lo_codepoint) {
117                diff->insert_range(ra.lo_codepoint, std::min(rb.lo_codepoint - 1, ra.hi_codepoint));
118            }
119            if (ra.hi_codepoint > rb.hi_codepoint) {
120                diff->insert_range(std::max(rb.hi_codepoint + 1, ra.lo_codepoint), ra.hi_codepoint);
121            }
122            ++ai;
123        }
124    }
125    for (; ai != ai_end; ++ai) {
126        const CharSetItem & ra = *ai;
127        diff->insert_range(ra.lo_codepoint, ra.hi_codepoint);
128    }
129    return diff;
130}
131   
132CC * intersectCC(const CC * a, const CC * b) {
133    CC * isect = makeCC();
134    auto ai = a->cbegin();
135    const auto ai_end = a->cend();
136    auto bi = b->cbegin();
137    const auto bi_end = b->cend();
138    while (ai != ai_end && bi != bi_end) {
139        const CharSetItem & ra = *ai;
140        const CharSetItem & rb = *bi;
141        if (ra.hi_codepoint < rb.lo_codepoint) {
142            ++ai;
143        }
144        else if (rb.hi_codepoint < ra.lo_codepoint) {
145            ++bi;
146        }
147        else {
148            isect->insert_range(std::max(ra.lo_codepoint, rb.lo_codepoint), std::min(ra.hi_codepoint, rb.hi_codepoint));
149            if (ra.hi_codepoint < rb.hi_codepoint) {
150                ++ai;
151            }
152            else {
153                ++bi;
154            }
155        }
156    }
157    return isect;
158}
159   
160CC * caseInsensitize(const CC * cc) {
161    CC * cci = makeCC();
162    for (const CharSetItem & i : *cc) {
163        caseInsensitiveInsertRange(cci, i.lo_codepoint, i.hi_codepoint);
164    }
165    return cci;
166}
167
168/** ------------------------------------------------------------------------------------------------------------- *
169 * @brief rangeIntersect
170 * @param cc
171 * @param lo
172 * @param hi
173 ** ------------------------------------------------------------------------------------------------------------- */
174CC * rangeIntersect(const CC * cc, const codepoint_t lo, const codepoint_t hi) {
175    assert ("cc cannot be null" && cc);
176    CC * intersect = makeCC();
177    for (const auto & p : *cc) {
178        if ((p.lo_codepoint <= hi) && (p.hi_codepoint >= lo)) {
179            intersect->insert_range(std::max(lo, p.lo_codepoint), std::min(hi, p.hi_codepoint));
180        }
181    }
182    return intersect;
183}
184
185/** ------------------------------------------------------------------------------------------------------------- *
186 * @brief rangeGaps
187 * @param cc
188 * @param lo
189 * @param hi
190 ** ------------------------------------------------------------------------------------------------------------- */
191CC * rangeGaps(const CC * cc, const codepoint_t lo, const codepoint_t hi) {
192    assert ("cc cannot be null" && cc);
193    CC * gaps = makeCC();
194    codepoint_t cp = lo;
195    if (cp < hi) {
196        auto i = cc->cbegin(), end = cc->cend();
197        for (; i != end && cp < hi; ++i) {
198            if (i->hi_codepoint < cp) {
199                continue;
200            }
201            else if (i->lo_codepoint > cp) {
202                gaps->insert_range(cp, i->lo_codepoint - 1);
203            }
204            cp = i->hi_codepoint + 1;
205        }
206        if (cp < hi) {
207            gaps->insert_range(cp, hi);
208        }
209    }
210    return gaps;
211}
212
213/** ------------------------------------------------------------------------------------------------------------- *
214 * @brief outerRanges
215 * @param cc
216 ** ------------------------------------------------------------------------------------------------------------- */
217CC * outerRanges(const CC * cc) {
218    assert ("cc cannot be null" && cc);
219    CC * ranges = makeCC();
220    auto i = cc->cbegin();
221    const auto end = cc->cend();
222    for (auto j = i; ++j != end; ) {
223        if (j->hi_codepoint > i->hi_codepoint) {
224            ranges->insert_range(i->lo_codepoint, i->hi_codepoint);
225            i = j;
226        }
227    }
228    return ranges;
229}
230
231/** ------------------------------------------------------------------------------------------------------------- *
232 * @brief innerRanges
233 * @param cc
234 ** ------------------------------------------------------------------------------------------------------------- */
235CC * innerRanges(const CC * cc) {
236    assert ("cc cannot be null" && cc);
237    CC * ranges = makeCC();
238    auto i = cc->cbegin();
239    const auto end = cc->cend();
240    for (auto j = i; ++j != end; ) {
241        if (j->hi_codepoint <= i->hi_codepoint) {
242            ranges->insert_range(j->lo_codepoint, j->hi_codepoint);
243        }
244        else {
245            i = j;
246        }
247    }
248    return ranges;
249}
250   
251}
Note: See TracBrowser for help on using the repository browser.