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

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

Bug fix for CC insert_range and UnicodeSet? iterator.

File size: 4.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
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 overlapp
63            lo_codepoint(i) = std::min(lo_codepoint(i), lo);
64            hi_codepoint(i) = std::max(hi_codepoint(i), hi);
65            // Test whether the new hi code point of this range touches the subsequent
66            // interval. If so extend it over that one and remove it from the list.
67            for (auto j = i + 1; j != mSparseCharSet.end(); ) {
68                if (LLVM_LIKELY(hi_codepoint(i) + 1 < lo_codepoint(j))) {
69                    break;
70                }
71                hi_codepoint(i) = std::max(hi_codepoint(i), hi_codepoint(j));
72                j = mSparseCharSet.erase(j);
73            }
74            return;
75        }
76    }
77    mSparseCharSet.emplace_back(lo, hi);
78}
79
80void CC::remove_range(const codepoint_t lo, const codepoint_t hi) {
81    for (auto i = mSparseCharSet.begin(); i != mSparseCharSet.end(); ) {
82        if (lo > hi_codepoint(i) + 1) {
83            ++i;
84        }
85        else if (hi < lo_codepoint(i) - 1) {
86            break;
87        }
88        else if (lo <= lo_codepoint(i) && hi >= hi_codepoint(i)) {
89            i = mSparseCharSet.erase(i);
90        }
91        else if (lo <= lo_codepoint(i)) {
92            lo_codepoint(i) = hi + 1;
93            break;
94        }
95        else if (hi >= hi_codepoint(i)) {
96            hi_codepoint(i) = lo - 1;
97            ++i;
98        }
99        else {         
100            mSparseCharSet.emplace(++i, hi + 1, hi_codepoint(i));
101            hi_codepoint(i) = lo - 1;
102            break;
103        }
104    }
105}
106
107CC * subtractCC(const CC * a, const CC * b) {
108    CC * diff = makeCC();
109    auto i = a->cbegin();
110    const auto i_end = a->cend();
111    auto j = b->cbegin();
112    const auto j_end = b->cend();
113    while (i != i_end && j != j_end) {
114        if (hi_codepoint(j) < lo_codepoint(i)) {
115            ++j;
116        }
117        else { // test whether the intervals overlap
118            if (lo_codepoint(i) < lo_codepoint(j)) {
119                diff->insert_range(lo_codepoint(i), std::min(lo_codepoint(j) - 1, hi_codepoint(i)));
120            }
121            if (hi_codepoint(i) > hi_codepoint(j)) {
122                diff->insert_range(std::max(hi_codepoint(j) + 1, lo_codepoint(i)), hi_codepoint(i));
123            }
124            ++i;
125        }
126    }
127    for (; i != i_end; ++i) {
128        diff->insert_range(lo_codepoint(i), hi_codepoint(i));
129    }
130    return diff;
131}
132   
133CC * intersectCC(const CC * a, const CC * b) {
134    CC * isect = makeCC();
135    auto ai = a->cbegin();
136    const auto ai_end = a->cend();
137    auto bi = b->cbegin();
138    const auto bi_end = b->cend();
139    while (ai != ai_end && bi != bi_end) {
140        if (hi_codepoint(ai) < lo_codepoint(bi)) {
141            ++ai;
142        }
143        else if (hi_codepoint(bi) < lo_codepoint(ai)) {
144            ++bi;
145        }
146        else {
147            isect->insert_range(std::max(lo_codepoint(ai), lo_codepoint(bi)), std::min(hi_codepoint(ai), hi_codepoint(bi)));
148            if (hi_codepoint(ai) < hi_codepoint(bi)) {
149                ++ai;
150            }
151            else {
152                ++bi;
153            }
154        }
155    }
156    return isect;
157}
158   
159CC * caseInsensitize(const CC * cc) {
160    CC * cci = makeCC();
161    for (const interval_t & i : *cc) {
162        caseInsensitiveInsertRange(cci, lo_codepoint(i), hi_codepoint(i));
163    }
164    return cci;
165}
166   
167}
Note: See TracBrowser for help on using the repository browser.