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

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

Replaced CharSetItem? with a std::pair.

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