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
RevLine 
[3850]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"
[4286]8#include <llvm/Support/Compiler.h>
[4320]9#include <UCD/CaseFolding_txt.h>
[4339]10#include <sstream>
[3850]11
[4194]12namespace re {
[4614]13CC::IntervalAllocator CC::mCharSetAllocator;
[3850]14
[4194]15CC::CC(const CC * cc1, const CC * cc2)
16: RE(ClassTypeId::CC)
[4510]17, mSparseCharSet(cc1->cbegin(), cc1->cend(), mCharSetAllocator) {
[4614]18    for (const interval_t & i : cc2->mSparseCharSet) {
19        insert_range(lo_codepoint(i), hi_codepoint(i));
[4194]20    }
[3850]21}
22
[4194]23CC::CC(const CC & cc)
24: RE(ClassTypeId::CC)
[4510]25, mSparseCharSet(cc.cbegin(), cc.cend(), mCharSetAllocator) {
[3850]26
27}
28
[4510]29std::string CC::canonicalName(const CC_type type) const {
[4339]30    std::stringstream name;
[4614]31    name << std::hex;
[4613]32    if ((type == ByteClass) && (max_codepoint() >= 0x80)) {
33        name << "BC";
[4337]34    }
[4510]35    else {
[4612]36        name << "CC";
[4510]37    }
[4519]38    char separator = '_';
[4614]39    for (const interval_t & i : mSparseCharSet) {
[4339]40        name << separator;
[4614]41        if (lo_codepoint(i) == hi_codepoint(i)) {
42            name << lo_codepoint(i);
[4287]43        }
44        else {
[4614]45            name << lo_codepoint(i) << '_' << hi_codepoint(i);
[4287]46        }
[4612]47        separator = ',';
[3914]48    }
[4339]49    return name.str();
[3850]50}
51
[4614]52void CC::insert_range(const codepoint_t lo, const codepoint_t hi) {
[4187]53    for (auto i = mSparseCharSet.begin(); i != mSparseCharSet.end(); ) {
[4614]54        if (hi < lo_codepoint(i) - 1) {
55            mSparseCharSet.emplace(i, lo, hi);
[4187]56            return;
[3850]57        }
[4614]58        else if (lo > hi_codepoint(i) + 1) {
[4187]59            ++i;
[3850]60        }
[4187]61        else {
[4621]62            // ranges overlap; expand the range to include the overlapp
[4614]63            lo_codepoint(i) = std::min(lo_codepoint(i), lo);
64            hi_codepoint(i) = std::max(hi_codepoint(i), hi);
[4621]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            }
[4287]74            return;
[3850]75        }
76    }
[4614]77    mSparseCharSet.emplace_back(lo, hi);
[3850]78}
79
[4614]80void CC::remove_range(const codepoint_t lo, const codepoint_t hi) {
[4187]81    for (auto i = mSparseCharSet.begin(); i != mSparseCharSet.end(); ) {
[4614]82        if (lo > hi_codepoint(i) + 1) {
[4187]83            ++i;
[3850]84        }
[4614]85        else if (hi < lo_codepoint(i) - 1) {
[4187]86            break;
[3850]87        }
[4614]88        else if (lo <= lo_codepoint(i) && hi >= hi_codepoint(i)) {
[4187]89            i = mSparseCharSet.erase(i);
[3850]90        }
[4614]91        else if (lo <= lo_codepoint(i)) {
92            lo_codepoint(i) = hi + 1;
[4187]93            break;
[3850]94        }
[4614]95        else if (hi >= hi_codepoint(i)) {
96            hi_codepoint(i) = lo - 1;
[4187]97            ++i;
[3850]98        }
[4614]99        else {         
100            mSparseCharSet.emplace(++i, hi + 1, hi_codepoint(i));
101            hi_codepoint(i) = lo - 1;
[4187]102            break;
[3850]103        }
104    }
105}
[4194]106
[4614]107CC * subtractCC(const CC * a, const CC * b) {
[4319]108    CC * diff = makeCC();
[4614]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;
[4613]116        }
117        else { // test whether the intervals overlap
[4614]118            if (lo_codepoint(i) < lo_codepoint(j)) {
119                diff->insert_range(lo_codepoint(i), std::min(lo_codepoint(j) - 1, hi_codepoint(i)));
[4613]120            }
[4614]121            if (hi_codepoint(i) > hi_codepoint(j)) {
122                diff->insert_range(std::max(hi_codepoint(j) + 1, lo_codepoint(i)), hi_codepoint(i));
[4613]123            }
[4614]124            ++i;
[4613]125        }
[4319]126    }
[4614]127    for (; i != i_end; ++i) {
128        diff->insert_range(lo_codepoint(i), hi_codepoint(i));
[4319]129    }
130    return diff;
[4285]131}
[4319]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) {
[4614]140        if (hi_codepoint(ai) < lo_codepoint(bi)) {
[4319]141            ++ai;
142        }
[4614]143        else if (hi_codepoint(bi) < lo_codepoint(ai)) {
[4319]144            ++bi;
145        }
[4613]146        else {
[4614]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)) {
[4613]149                ++ai;
150            }
151            else {
152                ++bi;
153            }
154        }
[4319]155    }
156    return isect;
157}
158   
[4320]159CC * caseInsensitize(const CC * cc) {
160    CC * cci = makeCC();
[4614]161    for (const interval_t & i : *cc) {
162        caseInsensitiveInsertRange(cci, lo_codepoint(i), hi_codepoint(i));
[4320]163    }
164    return cci;
[4319]165}
[4320]166   
167}
Note: See TracBrowser for help on using the repository browser.