Ignore:
Timestamp:
Jun 28, 2015, 12:18:14 AM (4 years ago)
Author:
nmedfort
Message:

More modifications to the UnicodeSet? class. Default iterator computes code point range intervals as expected by the UCD compiler.

Location:
icGREP/icgrep-devel/icgrep/UCD
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp

    r4618 r4620  
    2222#include <string>
    2323#include <llvm/Support/raw_ostream.h>
     24#include <llvm/Support/Format.h>
    2425#include <include/simd-lib/builtins.hpp>
    2526#include <iostream>
     27#include <iomanip>
    2628
    2729const size_t QUAD_BITS = (8 * sizeof(bitquad_t));
     
    3032const bitquad_t FULL_QUAD_MASK = -1;
    3133
     34std::string run_type_name(const run_type_t type) {
     35    if (type == Empty) {
     36        return "Empty";
     37    }
     38    if (type == Full) {
     39        return "Full";
     40    }
     41    if (type == Mixed) {
     42        return "Mixed";
     43    }
     44    return "???";
     45}
     46
     47using RunVector = UnicodeSet::RunVector;
     48using QuadVector = UnicodeSet::QuadVector;
     49
    3250/** ------------------------------------------------------------------------------------------------------------- *
    3351 * @brief append_run
    3452 ** ------------------------------------------------------------------------------------------------------------- */
    35 inline void UnicodeSet::append_run(const run_type_t type, const unsigned length) {
    36     if (length == 0) {
     53inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) {
     54    if (LLVM_UNLIKELY(length == 0)) {
    3755        return;
    3856    }
    39     else if (runs.size() == 0) {
    40         runs.emplace_back(type, length);
     57    else if (!runs.empty() && runs.back().mType == type) {
     58        runs.back().mRunLength += length;
     59        return;
     60    }
     61    runs.emplace_back(type, length);
     62}
     63
     64/** ------------------------------------------------------------------------------------------------------------- *
     65 * @brief append_quad
     66 ** ------------------------------------------------------------------------------------------------------------- */
     67inline void append_quad(const bitquad_t quad, QuadVector & quads, RunVector & runs) {
     68    run_type_t type = Empty;
     69    if (LLVM_UNLIKELY(quad == 0)) {
     70        type = Empty;
     71    }
     72    else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
     73        type = Full;
    4174    }
    4275    else {
    43         RunStructure last_run = runs[runs.size()-1];
    44         if (last_run.mType == type) {
    45             runs.back().mRunLength += length;
    46         }
    47         else {
    48             runs.emplace_back(type, length);
    49         }
    50     }
    51 }
    52 
    53 /** ------------------------------------------------------------------------------------------------------------- *
    54  * @brief append_quad
    55  ** ------------------------------------------------------------------------------------------------------------- */
    56 inline void UnicodeSet::append_quad(const bitquad_t quad) {
    57     if (quad == 0) {
    58         append_run(Empty, 1);
    59     }
    60     else if (quad == FULL_QUAD_MASK) {
    61         append_run(Full, 1);
    62     }
    63     else {
    64         quads.push_back(quad);
    65         append_run(Mixed, 1);
    66     }
     76        quads.emplace_back(quad);
     77        type = Mixed;
     78    }
     79    append_run(type, 1, runs);
    6780}
    6881
     
    7184 ** ------------------------------------------------------------------------------------------------------------- */
    7285void UnicodeSet::dump(llvm::raw_ostream & out) const {
    73     auto quad_itr = quads.cbegin();
    74     for (const RunStructure & run : runs) {
     86    auto qi = mQuads.cbegin();
     87    for (const RunStructure & run : mRuns) {
    7588        if (run.mType == Empty) {
    7689            out << "Empty(" << run.mRunLength << ")\n";
    7790        }
    78         else if (run.mType == Empty) {
     91        else if (run.mType == Full) {
    7992            out << "Full(" << run.mRunLength << ")\n";
    8093        }
    8194        else {
    82             for (unsigned i = 0; i != run.mRunLength; ++i, ++quad_itr) {
    83                 assert (quad_itr != quads.cend());
    84                 out << "Mixed("; out.write_hex(*quad_itr) << ")\n";
    85             }
    86         }
    87     }
     95            for (const auto qi_end = qi + run.mRunLength; qi != qi_end; ++qi) {
     96                assert (qi != mQuads.cend());
     97                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
     98            }
     99        }
     100    }
     101    out.flush();
    88102}
    89103
     
    92106 ** ------------------------------------------------------------------------------------------------------------- */
    93107UnicodeSet UnicodeSet::complement() const {
    94     UnicodeSet set;
    95     auto quad_itr = quads.cbegin();
    96     for (const RunStructure & run : runs) {
     108    RunVector runs;
     109    QuadVector quads;
     110    runs.reserve(mRuns.size());
     111    quads.reserve(mQuads.size());
     112    auto qi = quads.cbegin();
     113    for (const RunStructure & run : mRuns) {
    97114        if (run.mType == Empty) {
    98             set.append_run(Full, run.mRunLength);
    99         }
    100         else if (run.mType == Empty) {
    101             set.append_run(Empty, run.mRunLength);
    102         }
    103         else {
    104             for (unsigned i = 0; i != run.mRunLength; ++i, ++quad_itr) {
    105                 assert (quad_itr != quads.cend());
    106                 set.append_quad(FULL_QUAD_MASK ^ *quad_itr);
    107             }
    108         }
    109     }
    110     return set;
     115            append_run(Full, run.mRunLength, runs);
     116        }
     117        else if (run.mType == Full) {
     118            append_run(Empty, run.mRunLength, runs);
     119        }
     120        else {
     121            for (const auto qi_end = qi + run.mRunLength; qi != qi_end; ++qi) {
     122                assert (qi != quads.cend());
     123                append_quad(FULL_QUAD_MASK ^ *qi, quads, runs);
     124            }
     125        }
     126    }
     127    return UnicodeSet(std::move(runs), std::move(quads));
    111128}
    112129
     
    115132 ** ------------------------------------------------------------------------------------------------------------- */
    116133UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
    117     UnicodeSet iset;
     134    RunVector runs;
     135    QuadVector quads;
    118136    const auto e1 = quad_end();
    119137    const auto e2 = other.quad_end();
     
    123141        const auto n = std::min(run1.mRunLength, run2.mRunLength);
    124142        if (run1.mType == run2.mType && run1.mType != Mixed) {
    125             iset.append_run(run1.mType, n);
     143            append_run(run1.mType, n, runs);
    126144            i1 += n;
    127145            i2 += n;
     
    129147        else if (run1.mType == Full) {
    130148            for (unsigned i = 0; i != n; ++i, ++i2) {
    131                 iset.append_quad(i2.getQuad());
     149                append_quad(i2.getQuad(), quads, runs);
    132150            }
    133151            i1 += n;
     
    135153        else if (run2.mType == Full) {
    136154            for (unsigned i = 0; i != n; ++i, ++i1) {
    137                 iset.append_quad(i1.getQuad());
    138             }
    139             i2 += n;
    140         }
    141         else {
    142             for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
    143                 iset.append_quad(i1.getQuad() & i2.getQuad());
    144             }
    145         }
    146     }
    147     return iset;
     155                append_quad(i1.getQuad(), quads, runs);
     156            }
     157            i2 += n;
     158        }
     159        else {
     160            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
     161                append_quad(i1.getQuad() & i2.getQuad(), quads, runs);
     162            }
     163        }
     164    }
     165    return UnicodeSet(std::move(runs), std::move(quads));
    148166}
    149167
     
    152170 ** ------------------------------------------------------------------------------------------------------------- */
    153171UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
    154     UnicodeSet iset;
     172    RunVector runs;
     173    QuadVector quads;
    155174    const auto e1 = quad_end();
    156175    const auto e2 = other.quad_end();
     
    158177        const auto run1 = i1.getRun();
    159178        const auto run2 = i2.getRun();
     179
    160180        const auto n = std::min(run1.mRunLength, run2.mRunLength);
    161         if (run1.mType == run2.mType && run1.mType != Mixed) {
    162             iset.append_run(run1.mType, n);
     181        if ((run1.mType == Empty) && (run2.mType == Empty)) {
     182            append_run(Empty, n, runs);
     183            i1 += n;
     184            i2 += n;
     185        }
     186        else if ((run1.mType == Full) || (run2.mType == Full)) {
     187            append_run(Full, n, runs);
    163188            i1 += n;
    164189            i2 += n;
     
    166191        else if (run1.mType == Empty) {
    167192            for (unsigned i = 0; i != n; ++i, ++i2) {
    168                 iset.append_quad(i2.getQuad());
     193                append_quad(i2.getQuad(), quads, runs);
    169194            }
    170195            i1 += n;
     
    172197        else if (run2.mType == Empty) {
    173198            for (unsigned i = 0; i != n; ++i, ++i1) {
    174                 iset.append_quad(i1.getQuad());
     199                append_quad(i1.getQuad(), quads, runs);
    175200            }
    176201            i2 += n;
     
    178203        else {
    179204            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
    180                 iset.append_quad(i1.getQuad() | i2.getQuad());
    181             }
    182         }
    183     }
    184     return iset;
     205                append_quad(i1.getQuad() | i2.getQuad(), quads, runs);
     206            }
     207        }
     208    }
     209    return UnicodeSet(std::move(runs), std::move(quads));
    185210}
    186211
     
    189214 ** ------------------------------------------------------------------------------------------------------------- */
    190215UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
    191     UnicodeSet iset;
     216    RunVector runs;
     217    QuadVector quads;
    192218    const auto e1 = quad_end();
    193219    const auto e2 = other.quad_end();
     
    197223        unsigned n = std::min(run1.mRunLength, run2.mRunLength);
    198224        if ((run1.mType == Empty) || (run2.mType == Full) || (run1.mType == Full && run2.mType == Empty)) {
    199             iset.append_run(run1.mType, n);
     225            append_run(run1.mType, n, runs);
    200226            i1 += n;
    201227            i2 += n;
     
    203229        else if (run1.mType == Full) {
    204230            for (unsigned i = 0; i != n; ++i, ++i2) {
    205                 iset.append_quad(FULL_QUAD_MASK ^ i2.getQuad());
     231                append_quad(FULL_QUAD_MASK ^ i2.getQuad(), quads, runs);
    206232            }
    207233            i1 += n;
     
    209235        else if (run2.mType == Empty) {
    210236            for (unsigned i = 0; i != n; ++i, ++i1) {
    211                 iset.append_quad(i1.getQuad());
     237                append_quad(i1.getQuad(), quads, runs);
    212238            }
    213239            i2 += n;
     
    215241        else {
    216242            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
    217                 iset.append_quad(i1.getQuad() &~ i2.getQuad());
    218             }
    219         }
    220     }
    221     return iset;
     243                append_quad(i1.getQuad() &~ i2.getQuad(), quads, runs);
     244            }
     245        }
     246    }
     247    return UnicodeSet(std::move(runs), std::move(quads));
    222248}
    223249
     
    226252 ** ------------------------------------------------------------------------------------------------------------- */
    227253UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
    228     UnicodeSet iset;
     254    RunVector runs;
     255    QuadVector quads;
    229256    const auto e1 = quad_end();
    230257    const auto e2 = other.quad_end();
     
    234261        unsigned n = std::min(run1.mRunLength, run2.mRunLength);
    235262        if (run1.mType != Mixed && run2.mType != Mixed) {
    236             iset.append_run(run1.mType == run2.mType ? Empty : Full, n);
     263            append_run(run1.mType == run2.mType ? Empty : Full, n, runs);
    237264            i1 += n;
    238265            i2 += n;
    239266        }
    240267        else if (run1.mType == Empty) {
    241             for (int i = 0; i < n; ++i, ++i2) {
    242                 iset.append_quad(i2.getQuad());
    243             }
    244             i1 += n;
    245         }
    246         else if (run2.mType == Empty) {
    247             for (int i = 0; i < n; ++i, ++i1) {
    248                 iset.append_quad(i1.getQuad());
    249             }
    250             i2 += n;
    251         }
    252         else if (run1.mType == Full) {
    253             for (int i = 0; i < n; ++i, ++i2) {
    254                 iset.append_quad(FULL_QUAD_MASK ^ i2.getQuad());
     268            for (unsigned i = 0; i < n; ++i, ++i2) {
     269                append_quad(i2.getQuad(), quads, runs);
    255270            }
    256271            i1 += n;
     
    258273        else if (run2.mType == Empty) {
    259274            for (unsigned i = 0; i < n; ++i, ++i1) {
    260                 iset.append_quad(FULL_QUAD_MASK ^ i1.getQuad());
     275                append_quad(i1.getQuad(), quads, runs);
     276            }
     277            i2 += n;
     278        }
     279        else if (run1.mType == Full) {
     280            for (unsigned i = 0; i < n; ++i, ++i2) {
     281                append_quad(FULL_QUAD_MASK ^ i2.getQuad(), quads, runs);
     282            }
     283            i1 += n;
     284        }
     285        else if (run2.mType == Empty) {
     286            for (unsigned i = 0; i < n; ++i, ++i1) {
     287                append_quad(FULL_QUAD_MASK ^ i1.getQuad(), quads, runs);
    261288            }
    262289            i2 += n;
     
    264291        else {
    265292            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
    266                 iset.append_quad(i1.getQuad() ^ i2.getQuad());
    267             }
    268         }
    269     }
    270     return iset;
     293                append_quad(i1.getQuad() ^ i2.getQuad(), quads, runs);
     294            }
     295        }
     296    }
     297    return UnicodeSet(std::move(runs), std::move(quads));
    271298}
    272299
     
    284311
    285312    for (;;) {
    286         const RunStructure & t = runs[runIndex];
     313        const RunStructure & t = mRuns[runIndex];
    287314        if (t.mRunLength >= n) {
    288315            if (t.mType == Mixed) {
    289                 return (quads[quadIndex + n - 1] & (static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK))) != 0;
     316                return (mQuads[quadIndex + n - 1] & (static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK))) != 0;
    290317            }
    291318            return (t.mType == Full);
     
    305332void UnicodeSet::quad_iterator::advance(unsigned n) {
    306333    while (n > 0) {
    307         const RunStructure & t = mUnicodeSet.runs[mRunIndex];
    308         const unsigned remain = t.mRunLength - mOffset;
     334        const unsigned remain = mRunIterator->mRunLength - mOffset;
    309335        if (remain > n) {
     336            if (mRunIterator->mType == Mixed) {
     337                mQuadIterator += n;
     338            }
    310339            mOffset += n;
    311             if (t.mType == Mixed) {
    312                 mQuadIndex += n;
    313             }
    314340            break;
    315341        }
    316         else if (remain == n) {
    317             ++mRunIndex;
    318             mOffset = 0;
    319             if (t.mType == Mixed) {
    320                 mQuadIndex += n;
    321             }
    322             break;
    323         }
    324         else {
    325             ++mRunIndex;
    326             mOffset = 0;
    327             if (t.mType == Mixed) {
    328                 mQuadIndex += remain;
    329             }
    330             n -= remain;
    331         }
     342        if (mRunIterator->mType == Mixed) {
     343            mQuadIterator += remain;
     344        }
     345        ++mRunIterator;
     346        mOffset = 0;
     347        n -= remain;
    332348    }
    333349}
     
    336352 * @brief UnicodeSet::iterator::advance
    337353 ** ------------------------------------------------------------------------------------------------------------- */
    338 void UnicodeSet::iterator::advance(unsigned n) {
    339 
    340     std::cerr << "advance(" << n << ")\n";
    341 
    342     mMinCodePoint = mBaseCodePoint;
    343 
    344     for  ( ;n; ++mRunIterator) {
    345 
    346         const RunStructure & t = *mRunIterator;
    347 
    348         std::cerr << "Type:";
    349         switch (t.mType) {
    350             case Empty: std::cerr << "Empty"; break;
    351             case Full: std::cerr << "Full"; break;
    352             case Mixed: std::cerr << "Mixed"; break;
    353         }
    354         std::cerr << " Length:" << t.mRunLength;
    355         std::cerr << " BaseCodePoint:" << mBaseCodePoint;
    356 
    357 
    358         std::cerr << std::endl;
    359 
    360         if (t.mType != Mixed) {
    361             mMaxCodePoint = mBaseCodePoint + t.mRunLength * QUAD_BITS;
    362             mBaseCodePoint = mMaxCodePoint;
     354void UnicodeSet::iterator::advance(const unsigned n) {
     355
     356    assert (n == 1);
     357
     358    // Find the start of our interval
     359    for ( ; mBaseCodePoint <= re::CC::UNICODE_MAX; ++mRunIterator) {
     360        // Find the first non-empty block
     361        const RunStructure & run = *mRunIterator;
     362        if (run.mType != Mixed) {
     363            mMinCodePoint = mBaseCodePoint;
     364            mBaseCodePoint += run.mRunLength * QUAD_BITS;
    363365            mQuadOffset = 0;
    364366            mQuadPosition = 0;
    365             if (t.mType == Full) {
    366                 --n;
    367             }
     367            if (run.mType == Full) {
     368                break;
     369            }
     370        }
     371        else { // if (left.mType == Mixed)
     372            while (mQuadPosition != run.mRunLength) {
     373                const bitquad_t q = *mQuadIterator;
     374                const bitquad_t M = (FULL_QUAD_MASK << mQuadOffset);
     375                const bitquad_t m = q & M;
     376                // Nothing left in this quad to add; skip to the next one.
     377                if (m == 0) {
     378                    mBaseCodePoint += QUAD_BITS;
     379                    ++mQuadPosition;
     380                    ++mQuadIterator;
     381                    continue;
     382                }
     383                mQuadOffset = scan_forward_zeroes(m);
     384                mMinCodePoint = mBaseCodePoint + mQuadOffset;
     385                break;
     386            }
     387            // If we found nothing in the quad, restart the loop.
     388            if (mQuadPosition != run.mRunLength) {
     389                break;
     390            }
     391        }
     392    }
     393
     394    // Find the end of our interval
     395    for ( ; mBaseCodePoint <= re::CC::UNICODE_MAX; ++mRunIterator) {
     396        const RunStructure & run = *mRunIterator;
     397        // If the next run is empty, we already know the max code point.
     398        if (run.mType == Empty) {
     399            mMaxCodePoint = mBaseCodePoint;
     400            break;
     401        }
     402        // If the next run is Full, increment the base code point.
     403        else if (run.mType == Full) {
     404            mBaseCodePoint += run.mRunLength * QUAD_BITS;
     405            mMaxCodePoint = mBaseCodePoint;
     406            mQuadOffset = 0;
     407            mQuadPosition = 0;
    368408            continue;
    369409        }
    370 
    371         while (mQuadPosition != t.mRunLength) {
    372 
    373             const bitquad_t q = *mQuadIterator;
    374 
    375             const bitquad_t m = q & ((-1) >> mQuadOffset);
    376 
    377             std::cerr << "  q:" << std::hex << q << std::endl;
    378             std::cerr << " +m:" << std::hex << m << std::dec << "   (" << mQuadOffset << ")" << std::endl;
    379 
    380             // Nothing left in this quad to add; skip to the next one.
    381             if (m == 0) {
    382                 mBaseCodePoint += QUAD_BITS;
    383                 mMinCodePoint = mBaseCodePoint;
    384                 ++mQuadIterator;
    385                 continue;
    386             }
    387 
    388             mQuadOffset = scan_forward_zeroes(m);
    389             mMinCodePoint = mBaseCodePoint + mQuadOffset;
    390 
    391 
    392 
    393             break;
    394         }
    395 
    396         while (mQuadPosition != t.mRunLength) {
    397 
    398             // Although the initial position was in this quad, the final position isn't
    399             // unless this is the last quad of this mixed run and the subsequent quad is
    400             // Empty.
    401 
    402             const bitquad_t q = *mQuadIterator;
    403             const bitquad_t m = ~q & ((-1) >> mQuadOffset);
    404 
    405             std::cerr << "  q:" << std::hex << q << std::endl;
    406             std::cerr << " -m:" << std::hex << m << std::dec << "   (" << mQuadOffset << ")" << std::endl;
    407 
    408             // Nothing left in this quad to add; skip to the next one.
    409             if (m == 0) {
    410                 mBaseCodePoint += QUAD_BITS;
    411                 mMaxCodePoint = mBaseCodePoint;
    412                 ++mQuadIterator;
    413                 continue;
    414             }
    415 
    416             mQuadOffset = scan_forward_zeroes(m);
    417             mMaxCodePoint = mBaseCodePoint + mQuadOffset;
    418             --n;
    419             break;
    420         }
    421     }
    422 }
    423 
    424 UnicodeSet::UnicodeSet()
    425 : runs({{{Empty, UNICODE_QUAD_COUNT}}})
    426 {
    427 
    428 }
    429 
    430 // singleton set constructor
     410        else { // if (left.mType == Mixed)
     411            while (mQuadPosition != run.mRunLength) {
     412
     413                const bitquad_t q = *mQuadIterator;
     414                const bitquad_t M = (FULL_QUAD_MASK << mQuadOffset);
     415                const bitquad_t m = ~q & M;
     416
     417                // Nothing left in this quad to add; skip to the next one.
     418                if (m == 0) {
     419                    mBaseCodePoint += QUAD_BITS;
     420                    mMaxCodePoint = mBaseCodePoint;
     421                    ++mQuadPosition;
     422                    ++mQuadIterator;
     423                    continue;
     424                }
     425
     426                mQuadOffset = scan_forward_zeroes(m);
     427                mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
     428                break;
     429            }
     430            // If we found nothing in the quad, restart the loop.
     431            if (mQuadPosition != run.mRunLength) {
     432                break;
     433            }
     434        }
     435    }
     436
     437
     438}
     439
     440/** ------------------------------------------------------------------------------------------------------------- *
     441 * @brief Empty Set Constructor
     442 ** ------------------------------------------------------------------------------------------------------------- */
     443UnicodeSet::UnicodeSet() : mRuns({{{Empty, UNICODE_QUAD_COUNT}}}) { }
     444
     445/** ------------------------------------------------------------------------------------------------------------- *
     446 * @brief Singleton Set Constructor
     447 ** ------------------------------------------------------------------------------------------------------------- */
    431448UnicodeSet::UnicodeSet(const codepoint_t codepoint) {
    432     codepoint_t quad_no = codepoint / QUAD_BITS;
    433     if (quad_no > 0) {
    434         append_run(Empty, quad_no);
    435     }
    436     append_run(Mixed, 1);
    437     quads.push_back(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK));
    438     if (quad_no < UNICODE_QUAD_COUNT - 1) {
    439         append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1));
    440     }
    441 }
    442 
    443 // range set constructor
     449    const codepoint_t quad_no = codepoint / QUAD_BITS;
     450    append_run(Empty, quad_no, mRuns);
     451    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
     452    append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
     453}
     454
     455/** ------------------------------------------------------------------------------------------------------------- *
     456 * @brief Range Set Constructor
     457 ** ------------------------------------------------------------------------------------------------------------- */
    444458UnicodeSet::UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) {
    445     codepoint_t lo_quad_no = lo_codepoint / QUAD_BITS;
    446     codepoint_t hi_quad_no = hi_codepoint / QUAD_BITS;
    447     codepoint_t lo_offset = lo_codepoint & MOD_QUAD_BIT_MASK;
    448     codepoint_t hi_offset = hi_codepoint & MOD_QUAD_BIT_MASK;
    449     if (lo_quad_no > 0) {
    450         append_run(Empty, lo_quad_no);
    451     }
    452     if (lo_quad_no == hi_quad_no) {
    453         bitquad_t quad = (FULL_QUAD_MASK << lo_offset) & (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
    454         append_quad(quad);
     459    const codepoint_t lo_quad_no = lo_codepoint / QUAD_BITS;
     460    const codepoint_t hi_quad_no = hi_codepoint / QUAD_BITS;
     461    const codepoint_t lo_offset = lo_codepoint & MOD_QUAD_BIT_MASK;
     462    const codepoint_t hi_offset = hi_codepoint & MOD_QUAD_BIT_MASK;
     463    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
     464    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
     465    append_run(Empty, lo_quad_no, mRuns);
     466    if (lo_quad_no == hi_quad_no) {       
     467        append_quad(lo_quad & hi_quad, mQuads, mRuns);
    455468    }
    456469    else {
    457         append_quad((FULL_QUAD_MASK << lo_offset) & FULL_QUAD_MASK);
    458         append_run(Full, hi_quad_no - (lo_quad_no + 1));
    459         append_quad((FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset)) & FULL_QUAD_MASK);
    460     }
    461     if (hi_quad_no < UNICODE_QUAD_COUNT - 1) {
    462         append_run(Empty, UNICODE_QUAD_COUNT - (hi_quad_no + 1));
    463     }
    464 }
    465 
     470        append_quad(lo_quad, mQuads, mRuns);
     471        append_run(Full, hi_quad_no - (lo_quad_no + 1), mRuns);
     472        append_quad(hi_quad, mQuads, mRuns);
     473    }
     474    append_run(Empty, UNICODE_QUAD_COUNT - (hi_quad_no + 1), mRuns);
     475}
     476
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.h

    r4618 r4620  
    4545};
    4646
    47 class UnicodeSet;
     47class UnicodeSet {
     48public:
     49
    4850    using codepoint_t = re::codepoint_t;
    4951    using interval_t = re::interval_t;
    5052    using RunVector = std::vector<RunStructure>;
    5153    using QuadVector = std::vector<bitquad_t>;
    52 class UnicodeSet {
    53 public:
    5454
    55     class iterator : public boost::iterator_facade<iterator, re::interval_t, boost::forward_traversal_tag, re::interval_t> {
     55    class iterator : public boost::iterator_facade<iterator, interval_t, boost::forward_traversal_tag, interval_t> {
    5656        friend class UnicodeSet;
    5757        friend class boost::iterator_core_access;
    5858    protected:
    5959        iterator(RunVector::const_iterator runIterator, QuadVector::const_iterator quadIterator)
    60         : mRunIterator(runIterator), mQuadIterator(quadIterator), mQuadOffset(0)
    61         , mQuadPosition(0), mBaseCodePoint(0), mMinCodePoint(0), mMaxCodePoint(0)
     60        : mRunIterator(runIterator), mQuadIterator(quadIterator)
     61        , mQuadOffset(0), mQuadPosition(0), mBaseCodePoint(0), mMinCodePoint(0), mMaxCodePoint(0)
    6262        {
    6363
    6464        }
    6565
    66         void advance(unsigned n);
     66        void advance(const unsigned n);
    6767
    6868        re::interval_t dereference() const {
     
    7575
    7676        inline bool equal(iterator const & other) const {
    77             assert (&(mUnicodeSet) == &(other.mUnicodeSet));
    7877            return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator);
    7978        }
    8079    private:
    81         RunVector::const_iterator   mRunIterator;
    82         QuadVector::const_iterator  mQuadIterator;
     80        RunVector::const_iterator           mRunIterator;
     81        const RunVector::const_iterator     mRunEnd;
     82        QuadVector::const_iterator          mQuadIterator;
     83
     84
    8385        bitquad_t                   mQuadOffset;
    8486        unsigned                    mQuadPosition;
     
    8991
    9092    inline iterator begin() const {
    91         return iterator(runs.cbegin(), quads.cbegin());
     93        // note: pre-increment is intentional to move the iterator onto the first non-Empty interval.
     94        return ++iterator(mRuns.cbegin(), mQuads.cbegin());
    9295    }
    9396
    9497    inline iterator end() const {
    95         return iterator(runs.cend(), quads.cend());
     98        return iterator(mRuns.cend(), mQuads.cend());
     99    }
     100
     101    class quad_iterator : public boost::iterator_facade<quad_iterator, std::pair<RunStructure, bitquad_t>, boost::random_access_traversal_tag> {
     102        friend class UnicodeSet;
     103        friend class boost::iterator_core_access;
     104    public:
     105        quad_iterator(RunVector::const_iterator runIterator, QuadVector::const_iterator quadIterator)
     106            : mRunIterator(runIterator), mQuadIterator(quadIterator), mOffset(0) {}
     107
     108        void advance(unsigned n);
     109
     110        inline const std::pair<RunStructure, bitquad_t> dereference() const {
     111            return std::make_pair(getRun(), getQuad());
     112        }
     113
     114        inline void increment() {
     115            advance(1);
     116        }
     117
     118        inline RunStructure getRun() const {
     119            const auto & t = *mRunIterator;
     120            return RunStructure(t.mType, t.mRunLength - mOffset);
     121        }
     122
     123        inline bitquad_t getQuad() const {
     124            return *mQuadIterator;
     125        }
     126
     127        inline bool equal(const quad_iterator & other) const {
     128            return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator);
     129        }
     130
     131    private:
     132        RunVector::const_iterator   mRunIterator;
     133        QuadVector::const_iterator  mQuadIterator;
     134        unsigned                    mOffset;
     135    };
     136
     137    inline quad_iterator quad_begin() const {
     138        return quad_iterator(mRuns.cbegin(), mQuads.cbegin());
     139    }
     140
     141    inline quad_iterator quad_end() const {
     142        return quad_iterator(mRuns.cend(), mQuads.cend());
    96143    }
    97144
     
    109156    UnicodeSet(const codepoint_t codepoint);
    110157    UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint);
    111     UnicodeSet(std::initializer_list<RunStructure> r, std::initializer_list<bitquad_t> q) : runs(r), quads(q) {}
    112 
    113 protected:
    114 
    115     class quad_iterator : public boost::iterator_facade<quad_iterator, std::pair<RunStructure, bitquad_t>, boost::random_access_traversal_tag> {
    116         friend class UnicodeSet;
    117         friend class boost::iterator_core_access;
    118     public:
    119         quad_iterator(const UnicodeSet & set, unsigned runIndex) : mUnicodeSet(set), mRunIndex(runIndex), mOffset(0), mQuadIndex(0) {}
    120 
    121         void advance(unsigned n);
    122 
    123         inline const std::pair<RunStructure, bitquad_t> dereference() const {
    124             return std::make_pair(getRun(), getQuad());
    125         }
    126 
    127         inline void increment() {
    128             advance(1);
    129         }
    130 
    131         inline RunStructure getRun() const {
    132             const auto & t = mUnicodeSet.runs[mRunIndex];
    133             return RunStructure(t.mType, t.mRunLength - mOffset);
    134         }
    135 
    136         inline bitquad_t getQuad() const {
    137             return mUnicodeSet.quads[mQuadIndex];
    138         }
    139 
    140         inline bool equal(const quad_iterator & other) const {
    141             assert (&(mUnicodeSet) == &(other.mUnicodeSet));
    142             return (mRunIndex == other.mRunIndex);
    143         }
    144 
    145     private:
    146         const UnicodeSet &          mUnicodeSet;
    147         unsigned                    mRunIndex;
    148         unsigned                    mOffset;
    149         unsigned                    mQuadIndex;
    150     };
    151 
    152     inline quad_iterator quad_begin() const {
    153         return quad_iterator(*this, 0);
    154     }
    155 
    156     inline quad_iterator quad_end() const {
    157         return quad_iterator(*this, runs.size());
    158     }
    159 
    160     friend class UnicodeSet::quad_iterator;
    161 
    162     // Internal helper functions
    163     void append_run(const run_type_t type, const unsigned length);
    164     void append_quad(const bitquad_t quad);
     158    UnicodeSet(std::initializer_list<RunStructure> r, std::initializer_list<bitquad_t> q) : mRuns(r), mQuads(q) {}
     159    UnicodeSet(std::vector<RunStructure> && r, std::vector<bitquad_t> && q) : mRuns(r), mQuads(q) {}
    165160
    166161private:
    167162
    168     // The internal fields for a UnicodeSet.
    169     std::vector<RunStructure>   runs;
    170     std::vector<bitquad_t>      quads;
    171    
    172 
     163    std::vector<RunStructure>   mRuns;
     164    std::vector<bitquad_t>      mQuads;
    173165};
    174166
Note: See TracChangeset for help on using the changeset viewer.