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

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

Multiplexing bug fix and some CC changes.

File size: 7.2 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 {
13CC::CharSetAllocator CC::mCharSetAllocator;
14
15CC::CC(const CC * cc1, const CC * cc2)
16: RE(ClassTypeId::CC)
17, mSparseCharSet(cc1->cbegin(), cc1->cend(), mCharSetAllocator) {
18    for (const CharSetItem & i : cc2->mSparseCharSet) {
19        insert_range(i.lo_codepoint, i.hi_codepoint);
20    }
21}
22
23CC::CC(const CC & cc)
24: RE(ClassTypeId::CC)
25, mSparseCharSet(cc.cbegin(), cc.cend(), mCharSetAllocator) {
26
27}
28
29std::string CC::canonicalName(const CC_type type) const {
30    std::stringstream name;
31    name << std::hex;
32    if ((type == ByteClass) && (mSparseCharSet.back().hi_codepoint >= 0x80)) {
33      name << "BC";
34    }
35    else {
36        name << "CC";
37    }
38    char separator = '_';
39    for (const CharSetItem & i : mSparseCharSet) {
40        name << separator;
41        if (i.lo_codepoint == i.hi_codepoint) {
42            name << i.lo_codepoint;
43        }
44        else {
45            name << i.lo_codepoint << '_' << i.hi_codepoint;
46        }
47        separator = ',';
48    }
49    return name.str();
50}
51
52void CC::insert_range(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) {
53    CharSetItem item(lo_codepoint, hi_codepoint);
54    for (auto i = mSparseCharSet.begin(); i != mSparseCharSet.end(); ) {
55        CharSetItem & range = *i;
56        if (item.hi_codepoint < range.lo_codepoint - 1) {
57            mSparseCharSet.insert(i, item);
58            return;
59        }
60        else if (item.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, item.lo_codepoint);
67            range.hi_codepoint = std::max(range.hi_codepoint, item.hi_codepoint);
68            return;
69        }
70    }
71    mSparseCharSet.push_back(item);
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    for (const CharSetItem & i : cc1->mSparseCharSet) {
106        diff->insert_range(i.lo_codepoint, i.hi_codepoint);
107    }
108    for (const CharSetItem & i : cc2->mSparseCharSet) {
109        diff->remove_range(i.lo_codepoint, i.hi_codepoint);
110    }
111    return diff;
112}
113   
114CC * intersectCC(const CC * a, const CC * b) {
115    CC * isect = makeCC();
116    auto ai = a->cbegin();
117    const auto ai_end = a->cend();
118    auto bi = b->cbegin();
119    const auto bi_end = b->cend();
120    while (ai != ai_end && bi != bi_end) {
121        const CharSetItem & ra = *ai;
122        const CharSetItem & rb = *bi;
123        if (ra.hi_codepoint < rb.lo_codepoint) {
124            ++ai;
125            continue;
126        }
127        else if (rb.hi_codepoint < ra.lo_codepoint) {
128            ++bi;
129            continue;
130        }
131        isect->insert_range(std::max(ra.lo_codepoint, rb.lo_codepoint), std::min(ra.hi_codepoint, rb.hi_codepoint));
132        if (ra.hi_codepoint < rb.hi_codepoint) ++ai;
133        else ++bi;
134    }
135    return isect;
136}
137   
138CC * caseInsensitize(const CC * cc) {
139    CC * cci = makeCC();
140    for (const CharSetItem & i : *cc) {
141        caseInsensitiveInsertRange(cci, i.lo_codepoint, i.hi_codepoint);
142    }
143    return cci;
144}
145
146/** ------------------------------------------------------------------------------------------------------------- *
147 * @brief rangeIntersect
148 * @param cc
149 * @param lo
150 * @param hi
151 ** ------------------------------------------------------------------------------------------------------------- */
152CC * rangeIntersect(const CC * cc, const codepoint_t lo, const codepoint_t hi) {
153    assert ("cc cannot be null" && cc);
154    CC * intersect = makeCC();
155    for (const auto & p : *cc) {
156        if ((p.lo_codepoint <= hi) && (p.hi_codepoint >= lo)) {
157            intersect->insert_range(std::max(lo, p.lo_codepoint), std::min(hi, p.hi_codepoint));
158        }
159    }
160    return intersect;
161}
162
163/** ------------------------------------------------------------------------------------------------------------- *
164 * @brief rangeGaps
165 * @param cc
166 * @param lo
167 * @param hi
168 ** ------------------------------------------------------------------------------------------------------------- */
169CC * rangeGaps(const CC * cc, const codepoint_t lo, const codepoint_t hi) {
170    assert ("cc cannot be null" && cc);
171    CC * gaps = makeCC();
172    codepoint_t cp = lo;
173    if (cp < hi) {
174        auto i = cc->cbegin(), end = cc->cend();
175        for (; i != end && cp < hi; ++i) {
176            if (i->hi_codepoint < cp) {
177                continue;
178            }
179            else if (i->lo_codepoint > cp) {
180                gaps->insert_range(cp, i->lo_codepoint - 1);
181            }
182            cp = i->hi_codepoint + 1;
183        }
184        if (cp < hi) {
185            gaps->insert_range(cp, hi);
186        }
187    }
188    return gaps;
189}
190
191/** ------------------------------------------------------------------------------------------------------------- *
192 * @brief outerRanges
193 * @param cc
194 ** ------------------------------------------------------------------------------------------------------------- */
195CC * outerRanges(const CC * cc) {
196    assert ("cc cannot be null" && cc);
197    CC * ranges = makeCC();
198    auto i = cc->cbegin();
199    const auto end = cc->cend();
200    for (auto j = i; ++j != end; ) {
201        if (j->hi_codepoint > i->hi_codepoint) {
202            ranges->insert_range(i->lo_codepoint, i->hi_codepoint);
203            i = j;
204        }
205    }
206    return ranges;
207}
208
209/** ------------------------------------------------------------------------------------------------------------- *
210 * @brief innerRanges
211 * @param cc
212 ** ------------------------------------------------------------------------------------------------------------- */
213CC * innerRanges(const CC * cc) {
214    assert ("cc cannot be null" && cc);
215    CC * ranges = makeCC();
216    auto i = cc->cbegin();
217    const auto end = cc->cend();
218    for (auto j = i; ++j != end; ) {
219        if (j->hi_codepoint <= i->hi_codepoint) {
220            ranges->insert_range(j->lo_codepoint, j->hi_codepoint);
221        }
222        else {
223            i = j;
224        }
225    }
226    return ranges;
227}
228   
229}
Note: See TracBrowser for help on using the repository browser.