source: icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp @ 5727

Last change on this file since 5727 was 5727, checked in by cameron, 18 months ago

Small fixes, constructing/testing full UnicodeSets?.

File size: 36.5 KB
RevLine 
[4189]1//
2// unicode_set.cpp - representing and manipulating sets of Unicode
3// characters, based on data from UCD - the Unicode Character Database
4//
5// Robert D. Cameron
6// September 18, 2014
7//
8// Licensed under Open Software License 3.0.
9//
10// Unicode Sparse Bitset Representation
11//
12// The Unicode Sparse Bitset representation is based on
13// (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
14// (b) Specifying the quads using a run-length encoding, in which each run
15//     is Empty (quads contain no members), Mixed (quads contain some members and
16//     some nonmembers) or Full (all codepoints in each quad are members of the set).
17// (c) Explicitly listing all the quads of Mixed type.
18//
19
20#include "unicode_set.h"
21#include "assert.h"
22#include <string>
[4618]23#include <llvm/Support/raw_ostream.h>
[4620]24#include <llvm/Support/Format.h>
[4189]25
[4621]26namespace UCD {
27
28using bitquad_t = UnicodeSet::bitquad_t;
29using run_t = UnicodeSet::run_t;
[4860]30using interval_t = UnicodeSet::interval_t;
[4621]31
[4982]32//
33// Select the correct built-in scan function, dependent on whatever
[5727]34// bitquad_t resolves to, when scan_forward_zeroes<bitquad_t> is called.
[4982]35template <typename T> int scan_forward_zeroes(T x);
36template <> inline int scan_forward_zeroes<unsigned int>(unsigned int x){return __builtin_ctz(x);}
37template <> inline int scan_forward_zeroes<unsigned long>(unsigned long x){return __builtin_ctzl(x);}
38template <> inline int scan_forward_zeroes<unsigned long long>(unsigned long long x){return __builtin_ctzll(x);}
39
[5240]40SlabAllocator<> UnicodeSet::mAllocator;
[4982]41
[5227]42const uint64_t QUAD_BITS = (8 * sizeof(bitquad_t));
43const uint64_t MOD_QUAD_BIT_MASK = QUAD_BITS - 1;
44const uint64_t UNICODE_QUAD_COUNT = (UNICODE_MAX + 1) / QUAD_BITS;
[4616]45const bitquad_t FULL_QUAD_MASK = -1;
46
[4621]47inline run_type_t typeOf(const run_t & run) {
[4812]48    return run.first;
[4620]49}
50
[4621]51inline UnicodeSet::length_t lengthOf(const run_t & run) {
[4812]52    return run.second;
[4621]53}
[4620]54
[4618]55/** ------------------------------------------------------------------------------------------------------------- *
56 * @brief append_run
57 ** ------------------------------------------------------------------------------------------------------------- */
[4860]58template <class RunVector>
[4620]59inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) {
60    if (LLVM_UNLIKELY(length == 0)) {
[4611]61        return;
[4860]62    } else if (!runs.empty() && typeOf(runs.back()) == type) {
[4621]63        std::get<1>(runs.back()) += length;
[4620]64        return;
[4611]65    }
[4620]66    runs.emplace_back(type, length);
[4189]67}
68
[4618]69/** ------------------------------------------------------------------------------------------------------------- *
70 * @brief append_quad
71 ** ------------------------------------------------------------------------------------------------------------- */
[4860]72template <class QuadVector, class RunVector>
[4620]73inline void append_quad(const bitquad_t quad, QuadVector & quads, RunVector & runs) {
74    run_type_t type = Empty;
75    if (LLVM_UNLIKELY(quad == 0)) {
76        type = Empty;
[4860]77    } else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
[4620]78        type = Full;
[4860]79    } else {
[4620]80        quads.emplace_back(quad);
81        type = Mixed;
[4189]82    }
[4620]83    append_run(type, 1, runs);
[4189]84}
85
[4812]86#ifndef NDEBUG
[4618]87/** ------------------------------------------------------------------------------------------------------------- *
[4860]88 * @brief verify
[4621]89 *
[4860]90 * Sanity check for each function that constructs or modifies a UnicodeSet
[4621]91 ** ------------------------------------------------------------------------------------------------------------- */
[4860]92template <class RunVector, class QuadVector>
93inline bool verify(const RunVector & runs, const QuadVector & quads) {
[4621]94    unsigned sum = 0;
[4860]95    unsigned mixedQuads = 0;
96    for (auto run : runs) {
97        const auto l = lengthOf(run);
98        if (l == 0) {
99            throw std::runtime_error("Zero-length quad found!");
100        }
101        if (typeOf(run) == Mixed) {
102            mixedQuads += l;
103        }
104        sum += l;
[4621]105    }
[4860]106    if (sum != UNICODE_QUAD_COUNT) {
107        throw std::runtime_error("Invalid quad count: found " + std::to_string(sum) + " but expected " + std::to_string(UNICODE_QUAD_COUNT));
108    }
109    if (mixedQuads != quads.size()) {
110        throw std::runtime_error("Invalid mixed quad count: found " + std::to_string(quads.size()) + " but expected " + std::to_string(mixedQuads));
111    }
112    for (auto quad : quads) {
113        if (quad == 0) {
114            throw std::runtime_error("Empty quad found in Mixed quad array!");
115        } else if (quad == FULL_QUAD_MASK) {
116            throw std::runtime_error("Full quad found in Mixed quad array!");
117        }
118    }
119    return true;
[4621]120}
[4812]121#endif
[4621]122
123/** ------------------------------------------------------------------------------------------------------------- *
[4812]124 * @brief empty
125 ** ------------------------------------------------------------------------------------------------------------- */
126bool UnicodeSet::empty() const {
127    return (mRuns.size() == 1) && typeOf(mRuns.front()) == Empty;
128}
129
130/** ------------------------------------------------------------------------------------------------------------- *
[5727]131 * @brief full
132 ** ------------------------------------------------------------------------------------------------------------- */
133bool UnicodeSet::full() const {
134    return (mRuns.size() == 1) && typeOf(mRuns.front()) == Full;
135}
136
137/** ------------------------------------------------------------------------------------------------------------- *
[4812]138 * @brief size
139 ** ------------------------------------------------------------------------------------------------------------- */
140UnicodeSet::size_type UnicodeSet::size() const {
141    return std::distance(begin(), end());
142}
143
144/** ------------------------------------------------------------------------------------------------------------- *
145 * @brief front
146 ** ------------------------------------------------------------------------------------------------------------- */
147UnicodeSet::interval_t UnicodeSet::front() const {
148    return *begin();
149}
150
151/** ------------------------------------------------------------------------------------------------------------- *
152 * @brief back
153 ** ------------------------------------------------------------------------------------------------------------- */
154UnicodeSet::interval_t UnicodeSet::back() const {
155    auto back = begin();
156    for (auto i = back; i != end(); back = i++);
157    return *back;
158}
159
160/** ------------------------------------------------------------------------------------------------------------- *
[5620]161 * @brief print
162 ** ------------------------------------------------------------------------------------------------------------- */
163void UnicodeSet::print(llvm::raw_ostream & out) const {
164    if (LLVM_UNLIKELY(empty())) {
165        out << "()";
166    } else {
167        char joiner = '(';
168        for (auto r : *this) {
169            out << joiner << std::get<0>(r);
170            if (std::get<0>(r) != std::get<1>(r)) {
171                out << '-' << std::get<1>(r);
172            }
173            joiner = ',';
174        }
175        out << ')';
176
177    }
178}
179
180/** ------------------------------------------------------------------------------------------------------------- *
[4618]181 * @brief dump
182 ** ------------------------------------------------------------------------------------------------------------- */
183void UnicodeSet::dump(llvm::raw_ostream & out) const {
[4620]184    auto qi = mQuads.cbegin();
[4621]185    for (const run_t & run : mRuns) {
186        if (typeOf(run) == Empty) {
187            out << "Empty(" << lengthOf(run) << ")\n";
[4611]188        }
[4621]189        else if (typeOf(run) == Full) {
190            out << "Full(" << lengthOf(run) << ")\n";
[4611]191        }
192        else {
[4621]193            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
[4620]194                assert (qi != mQuads.cend());
195                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
[4611]196            }
197        }
[4189]198    }
199}
200
[4618]201/** ------------------------------------------------------------------------------------------------------------- *
202 * @brief complement
203 ** ------------------------------------------------------------------------------------------------------------- */
[4621]204UnicodeSet UnicodeSet::operator~() const {
[4860]205    std::vector<run_t> runs;
206    std::vector<bitquad_t> quads;
[4620]207    runs.reserve(mRuns.size());
208    quads.reserve(mQuads.size());
209    auto qi = quads.cbegin();
[4621]210    for (const run_t & run : mRuns) {
211        if (typeOf(run) == Empty) {
212            append_run(Full, lengthOf(run), runs);
[4611]213        }
[4621]214        else if (typeOf(run) == Full) {
215            append_run(Empty, lengthOf(run), runs);
[4611]216        }
217        else {
[4621]218            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
[4620]219                assert (qi != quads.cend());
220                append_quad(FULL_QUAD_MASK ^ *qi, quads, runs);
[4611]221            }
222        }
[4189]223    }
[4620]224    return UnicodeSet(std::move(runs), std::move(quads));
[4189]225}
226
[4618]227/** ------------------------------------------------------------------------------------------------------------- *
228 * @brief intersection
229 ** ------------------------------------------------------------------------------------------------------------- */
230UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
[4860]231    std::vector<run_t> runs;
232    std::vector<bitquad_t> quads;
[4618]233    const auto e1 = quad_end();
234    const auto e2 = other.quad_end();
235    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
[4629]236        const auto n = std::min(i1.length(), i2.length());
[4850]237        if ((i1.type() == Full) && (i2.type() == Full)) {
238            append_run(Full, n, runs);
[4616]239            i1 += n;
240            i2 += n;
[4611]241        }
[4850]242        else if ((i1.type() == Empty) || (i2.type() == Empty)) {
243            append_run(Empty, n, runs);
244            i1 += n;
245            i2 += n;
246        }
[4629]247        else if (i1.type() == Full) {
[4616]248            for (unsigned i = 0; i != n; ++i, ++i2) {
[4622]249                append_quad(i2.quad(), quads, runs);
[4611]250            }
[4616]251            i1 += n;
[4611]252        }
[4629]253        else if (i2.type() == Full) {
[4616]254            for (unsigned i = 0; i != n; ++i, ++i1) {
[4622]255                append_quad(i1.quad(), quads, runs);
[4611]256            }
[4616]257            i2 += n;
[4611]258        }
[4850]259        else { //both Mixed
[4620]260            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
[4622]261                append_quad(i1.quad() & i2.quad(), quads, runs);
[4611]262            }
263        }
[4189]264    }
[4620]265    return UnicodeSet(std::move(runs), std::move(quads));
[4189]266}
267
[4618]268/** ------------------------------------------------------------------------------------------------------------- *
269 * @brief union
270 ** ------------------------------------------------------------------------------------------------------------- */
271UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
[4860]272    std::vector<run_t> runs;
273    std::vector<bitquad_t> quads;
[4618]274    const auto e1 = quad_end();
275    const auto e2 = other.quad_end();
[4621]276    auto i1 = quad_begin(), i2 = other.quad_begin();
277    for (; i1 != e1 && i2 != e2; ) {
[4629]278        const auto n = std::min(i1.length(), i2.length());
279        if ((i1.type() == Empty) && (i2.type() == Empty)) {
[4620]280            append_run(Empty, n, runs);
[4616]281            i1 += n;
282            i2 += n;
[4860]283        } else if ((i1.type() == Full) || (i2.type() == Full)) {
[4620]284            append_run(Full, n, runs);
285            i1 += n;
286            i2 += n;
[4860]287        } else if (i1.type() == Empty) {
[4618]288            for (unsigned i = 0; i != n; ++i, ++i2) {
[4622]289                append_quad(i2.quad(), quads, runs);
[4611]290            }
[4616]291            i1 += n;
[4860]292        } else if (i2.type() == Empty) {
[4618]293            for (unsigned i = 0; i != n; ++i, ++i1) {
[4622]294                append_quad(i1.quad(), quads, runs);
[4611]295            }
[4616]296            i2 += n;
[4860]297        } else {
[4618]298            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
[4622]299                append_quad(i1.quad() | i2.quad(), quads, runs);
[4611]300            }
301        }
[4189]302    }
[4620]303    return UnicodeSet(std::move(runs), std::move(quads));
[4189]304}
305
[4618]306/** ------------------------------------------------------------------------------------------------------------- *
307 * @brief difference
308 ** ------------------------------------------------------------------------------------------------------------- */
309UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
[4860]310    std::vector<run_t> runs;
311    std::vector<bitquad_t> quads;
[4618]312    const auto e1 = quad_end();
313    const auto e2 = other.quad_end();
314    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
[4629]315        unsigned n = std::min(i1.length(), i2.length());
316        if ((i1.type() == Empty) || (i2.type() == Full) || (i1.type() == Full && i2.type() == Empty)) {
317            append_run(i1.type(), n, runs);
[4616]318            i1 += n;
319            i2 += n;
[4611]320        }
[4629]321        else if (i1.type() == Full) {
[4616]322            for (unsigned i = 0; i != n; ++i, ++i2) {
[4622]323                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
[4611]324            }
[4616]325            i1 += n;
[4611]326        }
[4629]327        else if (i2.type() == Empty) {
[4616]328            for (unsigned i = 0; i != n; ++i, ++i1) {
[4622]329                append_quad(i1.quad(), quads, runs);
[4611]330            }
[4616]331            i2 += n;
[4611]332        }
333        else {
[4616]334            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
[4622]335                append_quad(i1.quad() &~ i2.quad(), quads, runs);
[4611]336            }
337        }
[4189]338    }
[4620]339    return UnicodeSet(std::move(runs), std::move(quads));
[4189]340}
341
[4618]342/** ------------------------------------------------------------------------------------------------------------- *
343 * @brief symmetric difference
344 ** ------------------------------------------------------------------------------------------------------------- */
345UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
[4860]346    std::vector<run_t> runs;
347    std::vector<bitquad_t> quads;
[4618]348    const auto e1 = quad_end();
349    const auto e2 = other.quad_end();
350    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
[4629]351        unsigned n = std::min(i1.length(), i2.length());
352        if (i1.type() != Mixed && i2.type() != Mixed) {
353            append_run(i1.type() == i2.type() ? Empty : Full, n, runs);
[4616]354            i1 += n;
355            i2 += n;
[5620]356        } else if (i1.type() == Empty) {
[4620]357            for (unsigned i = 0; i < n; ++i, ++i2) {
[4622]358                append_quad(i2.quad(), quads, runs);
[4611]359            }
[4616]360            i1 += n;
[5620]361        } else if (i2.type() == Empty) {
[4620]362            for (unsigned i = 0; i < n; ++i, ++i1) {
[4622]363                append_quad(i1.quad(), quads, runs);
[4611]364            }
[4616]365            i2 += n;
[5620]366        } else if (i1.type() == Full) {
[4620]367            for (unsigned i = 0; i < n; ++i, ++i2) {
[4622]368                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
[4611]369            }
[4616]370            i1 += n;
[5620]371        } else if (i2.type() == Full) {
[4616]372            for (unsigned i = 0; i < n; ++i, ++i1) {
[4622]373                append_quad(FULL_QUAD_MASK ^ i1.quad(), quads, runs);
[4611]374            }
[4616]375            i2 += n;
[5620]376        } else {
[4616]377            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
[4622]378                append_quad(i1.quad() ^ i2.quad(), quads, runs);
[4611]379            }
380        }
[4189]381    }
[4620]382    return UnicodeSet(std::move(runs), std::move(quads));
[4189]383}
384
[4618]385/** ------------------------------------------------------------------------------------------------------------- *
[4621]386 * @brief equality
387 ** ------------------------------------------------------------------------------------------------------------- */
[4818]388bool UnicodeSet::operator==(const UnicodeSet & other) const {
[4621]389    if (mRuns.size() != other.mRuns.size() || mQuads.size() != other.mQuads.size()) {
390        return false;
391    }
392    for (auto i = mQuads.begin(), j = other.mQuads.begin(); i != mQuads.end(); ++i, ++j) {
393        if (*i != *j) return false;
394    }
395    for (auto i = mRuns.begin(), j = other.mRuns.begin(); i != mRuns.end(); ++i, ++j) {
396        if (*i != *j) return false;
397    }
398    return true;
399}
400
[4818]401/** ------------------------------------------------------------------------------------------------------------- *
402 * @brief less operator
403 ** ------------------------------------------------------------------------------------------------------------- */
404bool UnicodeSet::operator<(const UnicodeSet & other) const {
405    if (LLVM_LIKELY(mRuns.size() != other.mRuns.size())) {
406        return mRuns.size() < other.mRuns.size();
407    } else if (LLVM_LIKELY(mQuads.size() != other.mQuads.size())) {
408        return (mQuads.size() < other.mQuads.size());
409    } else { // equal run and quad lengths; test their individual values
410        for (auto ri = mRuns.cbegin(), end = mRuns.cend(), rj = other.mRuns.cbegin(); ri != end; ++ri, ++rj) {
411            if (*ri < *rj) {
412                return true;
413            } else if (*ri > *rj) {
414                return false;
415            }
416        }
417        for (auto qi = mQuads.cbegin(), end = mQuads.cend(), qj = other.mQuads.cbegin(); qi != end; ++qi, ++qj) {
418            if (*qi < *qj) {
419                return true;
420            } else if (*qi > *qj) {
421                return false;
422            }
423        }
424        return false;
425    }
426}
427
[4860]428/** ------------------------------------------------------------------------------------------------------------- *
429 * @brief insert
430 ** ------------------------------------------------------------------------------------------------------------- */
431void UnicodeSet::insert(const codepoint_t cp) {
[4812]432
[5727]433    if (LLVM_UNLIKELY(cp > UNICODE_MAX)) {
[4860]434        throw std::runtime_error(std::to_string(cp) + " exceeds maximum code point.");
435    }
[4812]436
[4860]437    codepoint_t offset = cp / QUAD_BITS;
438    const bitquad_t value = static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK);
439    auto run = mRuns.begin();
440    auto quad = mQuads.begin();
441    length_t l = 0;
442    run_type_t t = Empty;
443    for (;;) {
444        std::tie(t, l) = *run;
445        if (offset < l) {
446            break;
447        }
448        if (t == Mixed) {
449            quad += l;
450        }
451        offset -= l;
452        ++run;
453    }
454    if (LLVM_LIKELY(t == Mixed)) {
455        quad += offset;
456        *quad |= value;
457        if (LLVM_LIKELY(*quad != FULL_QUAD_MASK)) {
458            assert (contains(cp));
459            return;
460        }
461        mQuads.erase(quad);
462    } else if (t == Empty) {
463        mQuads.insert(quad, value);
464    } else { // if (t == Full) {
465        assert (contains(cp));
466        return;
467    }
468    const unsigned remaining = l - (offset + 1);
469    if (offset == 0) {
470        *run = std::make_pair(t == Empty ? Mixed : Full, 1);
471        if (remaining != 0) {
472            mRuns.insert(++run, std::make_pair(t, remaining));
473        }
474    } else {
475        run->second = offset;
476        if (remaining == 0) {
477            mRuns.insert(++run, std::make_pair(t == Empty ? Mixed : Full, 1));
478        } else {
479            mRuns.insert(++run, {std::make_pair(t == Empty ? Mixed : Full, 1), std::make_pair(t, remaining)});
480        }
481    }
[4812]482
[4860]483    assert (verify(mRuns, mQuads));
484    assert (contains(cp));
485}
[4812]486
[4860]487/** ------------------------------------------------------------------------------------------------------------- *
488 * @brief insert_range
489 ** ------------------------------------------------------------------------------------------------------------- */
490void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi)  {
[4812]491
[4860]492    if (LLVM_UNLIKELY(lo > hi)) {
493        throw std::runtime_error('[' + std::to_string(lo) + ',' + std::to_string(hi) + "] is an illegal codepoint range!");
494    } else if (LLVM_UNLIKELY(hi > UNICODE_MAX)) {
495        throw std::runtime_error(std::to_string(hi) + " exceeds maximum code point.");
496    }
[4812]497
[4860]498    // Create a temporary run and quad set for the given range
499    std::vector<run_t> runs;
500    std::vector<bitquad_t> quads;
[4812]501
[4860]502    codepoint_t lo_index = lo / QUAD_BITS;
503    codepoint_t hi_index = hi / QUAD_BITS;
[4812]504
[4860]505    auto ri = mRuns.cbegin();
506    auto qi = mQuads.cbegin();
[4812]507
[5634]508    codepoint_t length = 0;
[4860]509    run_type_t type = Empty;
[5037]510
[5634]511    // Advance past any runs prior to the lo_index
[4860]512    for (;;) {
[5037]513        assert (ri != mRuns.cend());
[5634]514        std::tie(type, length) = *ri;       
[4860]515        if (lo_index < length) {
516            break;
517        }
518        if (type == Mixed) {
[5037]519            assert (std::distance(qi, mQuads.cend()) >= length);
[4860]520            qi += length;
521        }
522        lo_index -= length;
523        hi_index -= length;
524        ++ri;
525    }
[4812]526
[4860]527    // Now record the runs and any quads prior to lo_index
[5037]528    runs.assign(mRuns.cbegin(), ri++);
[4860]529    if (lo_index) {
[5634]530        runs.emplace_back(type, lo_index);
[4860]531        if (type == Mixed) {
[5386]532            assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) >= lo_index);
[4860]533            qi += lo_index;
534        }
535        hi_index -= lo_index;
536        length -= lo_index;
537    }
[4812]538
[4860]539    quads.assign(mQuads.cbegin(), qi);
540    // We now have everything up to the first quad added to our temporary buffers; merge in the first new quad.
541    bitquad_t lo_quad = (FULL_QUAD_MASK << (lo & MOD_QUAD_BIT_MASK));
542    bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - (hi & MOD_QUAD_BIT_MASK)));
[4812]543
[4860]544    // If our original quad is full, just append a Full run
545    if (LLVM_UNLIKELY(type == Full)) {
546        append_run(Full, 1, runs);
547    } else { // Otherwise merge the new quad value with the original one
548        if (hi_index == 0) {
549            lo_quad &= hi_quad;
550        }
551        if (type == Mixed) {
[5037]552            assert (std::distance(qi, mQuads.cend()) > 0);
[4860]553            lo_quad |= *qi++;
554        }
555        append_quad(lo_quad, quads, runs);
556    }
557    --length;
[4812]558
[4860]559    // Now check if we need to write out any Full blocks between the lo and hi code points; adjust our position
560    // in the original quad to suit.
561    if (hi_index) {
562        // Add in any full runs between the lo and hi quads
563        append_run(Full, hi_index - 1, runs);
564        // Advance past original quads that were filled in
[5037]565        while (ri != mRuns.cend()) {
[4860]566            if (type == Mixed) {
[5037]567                assert (std::distance(qi, mQuads.cend()) >= length);
[4860]568                qi += length;
569            }
[5037]570            std::tie(type, length) = *ri++;
[4860]571            if (hi_index < length) {
572                break;
573            }
574            hi_index -= length;
[5634]575            length = 0;
576        }       
[4860]577        // Write out the hi_quad value
578        if (LLVM_UNLIKELY(type == Full)) {
579            append_run(Full, 1, runs);
580        } else {
581            if (type == Mixed) {
[5386]582                assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) > hi_index);
[4860]583                qi += hi_index;
584                hi_quad |= *qi++;
585            }
586            append_quad(hi_quad, quads, runs);
587        }
588    }
589
590    // And append any remaining values from the original data
[5634]591    assert (length >= hi_index);
[4860]592    append_run(type, length - hi_index, runs);
[5037]593    assert ("We wrote all the runs but still have remaining quads?" && (ri != mRuns.cend() || qi == mQuads.cend()));
594    runs.insert(runs.end(), ri, mRuns.cend());
[4860]595    quads.insert(quads.end(), qi, mQuads.cend());
596    assert (verify(runs, quads));
597    mRuns.assign(runs.cbegin(), runs.cend());
[5634]598    mQuads.assign(quads.cbegin(), quads.cend());   
[4860]599}
600
[4621]601/** ------------------------------------------------------------------------------------------------------------- *
[4618]602 * @brief contains
603 * @param codepoint
604 *
605 * Return whether this UnicodeSet contains the specified code point
606 ** ------------------------------------------------------------------------------------------------------------- */
[4860]607bool UnicodeSet::contains(const codepoint_t cp) const {
608    codepoint_t offset = cp / QUAD_BITS;
609    auto quad = mQuads.cbegin();
610    for (const auto r : mRuns) {
611        length_t l = 0;
612        run_type_t t = Empty;
613        std::tie(t, l) = r;
614        if (offset < l) {
615            if (t == Mixed) {
616                quad += offset;
617                return (*quad & static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK)) != 0;
[4618]618            }
[4860]619            return (t == Full);
[4618]620        }
[4860]621        if (t == Mixed) {
622            quad += l;
[4621]623        }       
[4860]624        offset -= l;
[4618]625    }
[4621]626    return false;
[4611]627}
[4617]628
[4618]629/** ------------------------------------------------------------------------------------------------------------- *
[4629]630 * @brief intersects
631 * @param lo_codepoint
632 * @param hi_codepoint
633 *
[4631]634 * Return true if this UnicodeSet contains any code point(s) between lo and hi (inclusive)
[4629]635 ** ------------------------------------------------------------------------------------------------------------- */
[4631]636bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const {
637    for (auto range : *this) {
[4812]638        if (range.second < lo) {
[4631]639            continue;
[4629]640        }
[4812]641        if (range.first > hi) {
[4631]642            break;
643        }
[4629]644        return true;
645    }
[4631]646    return false;
[4629]647}
[5632]648   
649   
650/** ------------------------------------------------------------------------------------------------------------- *
651 * @brief intersects
652 * @param other_set
653 *
654 * Return true if this UnicodeSet has a non-empty intersection with other_set
655 ** ------------------------------------------------------------------------------------------------------------- */
656bool UnicodeSet::intersects(const UnicodeSet & other) const {
657    const auto e1 = quad_end();
658    const auto e2 = other.quad_end();
659    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
[5706]660        auto n = std::min(i1.length(), i2.length());
661        if (i1.type() == Empty || i2.type() == Empty) {
662            i1 += n;
663            i2 += n;
664        } else if (i1.type() == Full || i2.type() == Full) {
665            return true;
666        } else { //both Mixed
667            for (; n; --n, ++i1, ++i2) {
668                if ((i1.quad() & i2.quad()) != 0) return true;
[5632]669            }
670        }
671    }
[5706]672    return false;
[5632]673}
[4629]674
[5632]675
[4629]676/** ------------------------------------------------------------------------------------------------------------- *
[4618]677 * @brief UnicodeSet::quad_iterator::advance
678 ** ------------------------------------------------------------------------------------------------------------- */
679void UnicodeSet::quad_iterator::advance(unsigned n) {
680    while (n > 0) {
[4621]681        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
[4618]682        if (remain > n) {
[4621]683            if (typeOf(*mRunIterator) == Mixed) {
[4620]684                mQuadIterator += n;
685            }
[4618]686            mOffset += n;
687            break;
688        }
[4621]689        if (typeOf(*mRunIterator) == Mixed) {
[4620]690            mQuadIterator += remain;
[4618]691        }
[4620]692        ++mRunIterator;
693        mOffset = 0;
694        n -= remain;
[4618]695    }
696}
697
698/** ------------------------------------------------------------------------------------------------------------- *
699 * @brief UnicodeSet::iterator::advance
700 ** ------------------------------------------------------------------------------------------------------------- */
[4620]701void UnicodeSet::iterator::advance(const unsigned n) {
[4617]702
[4812]703    assert (n == 1);
[4617]704
[5727]705    if (LLVM_UNLIKELY(mMinCodePoint > UNICODE_MAX)) {
[4627]706        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
[4626]707    }
708
[4627]709    bool found = false;
[4620]710    // Find the start of our interval
[5727]711    while ( mBaseCodePoint <= UNICODE_MAX ) {
[4620]712        // Find the first non-empty block
[4627]713        if (typeOf(*mRunIterator) != Mixed) {           
[4621]714            // If we found a full run, this must be the start of our interval.
[4627]715            const auto baseCodePoint = mBaseCodePoint;
716            const auto type = typeOf(*mRunIterator);
717            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
718            if (type == Full) {
719                mMinCodePoint = baseCodePoint;
720                found = true;
[4620]721                break;
[4618]722            }
[4812]723        } else { // if (typeOf(t) == Mixed)
[4621]724            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
725                const bitquad_t m = (*mQuadIterator) & (FULL_QUAD_MASK << mQuadOffset);
726                // If we found a marker in m, it marks the beginning of our current interval.
727                // Find it and break out of the loop.
728                if (m) {
[4982]729                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
[4621]730                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
731                    found = true;
732                    break;
[4620]733                }
[4621]734                mBaseCodePoint += QUAD_BITS;
[4627]735                ++mQuadIterator;
[4621]736                ++mMixedRunIndex;
737                mQuadOffset = 0;
[4617]738            }
[4627]739            if (found) break;
740            ++mRunIterator;
741            mQuadOffset = 0;
742            mMixedRunIndex = 0;
[4620]743        }
744    }
[4617]745
[4627]746    if (!found) {
[5727]747        assert (mBaseCodePoint == (UNICODE_MAX+1));
748        mMinCodePoint = (UNICODE_MAX+1);
[4627]749        return;
750    }
751
752    // at this stage, the max code point is the previous max code point (initially 0)
753    assert (mMaxCodePoint <= mMinCodePoint);
754    found = false;
[4620]755    // Find the end of our interval
[5727]756    while ( mBaseCodePoint <= UNICODE_MAX ) {
[4627]757
758        // Find the first non-Full block
759        if (typeOf(*mRunIterator) != Mixed) {
760            // If this run is Empty, the max code point is the last computed base code point - 1.
761            const auto baseCodePoint = mBaseCodePoint;
762            const auto type = typeOf(*mRunIterator);
763            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
764            if (type == Empty) {
765                mMaxCodePoint = baseCodePoint - 1;
766                found = true;
767                break;
768            }
[4812]769        } else { // if (typeOf(t) == Mixed)
[4621]770            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
[4627]771                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
772
[4621]773                // If we found a marker in m, it marks the end of our current interval.
774                // Find it and break out of the loop.
775                if (m) {
[4982]776                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
[4621]777                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
778                    found = true;
779                    break;
[4620]780                }
[4621]781                mBaseCodePoint += QUAD_BITS;
[4627]782                ++mQuadIterator;
[4621]783                ++mMixedRunIndex;
784                mQuadOffset = 0;
[4617]785            }
[4627]786            if (found) break;
787            ++mRunIterator;
788            mQuadOffset = 0;
789            mMixedRunIndex = 0;
[4617]790        }
791    }
[5727]792    // if the very last block is a mixed block and we go past it, the last code point of the range is UNICODE_MAX
[4627]793    if (!found) {
[5727]794        assert (mBaseCodePoint == (UNICODE_MAX+1));
795        mMaxCodePoint = UNICODE_MAX;
[4627]796    }
[4617]797
[4627]798    assert (mMinCodePoint <= mMaxCodePoint);
[4618]799}
[5727]800   
[4620]801/** ------------------------------------------------------------------------------------------------------------- *
[5727]802 * @brief Empty/Full Set Constructor
[4620]803 ** ------------------------------------------------------------------------------------------------------------- */
[5727]804UnicodeSet::UnicodeSet(run_type_t emptyOrFull)
[5240]805: mRuns(mAllocator)
806, mQuads(mAllocator)
[4860]807{
[5727]808    assert((emptyOrFull == Empty) || (emptyOrFull == Full));
809    append_run(emptyOrFull, UNICODE_QUAD_COUNT, mRuns);
[4860]810    assert (verify(mRuns, mQuads));
811}
[5727]812           
[4620]813/** ------------------------------------------------------------------------------------------------------------- *
814 * @brief Singleton Set Constructor
815 ** ------------------------------------------------------------------------------------------------------------- */
[4860]816UnicodeSet::UnicodeSet(const codepoint_t codepoint)
[5240]817: mRuns(mAllocator)
818, mQuads(mAllocator)
[4860]819{
[4620]820    const codepoint_t quad_no = codepoint / QUAD_BITS;
[4860]821    append_run(Empty, quad_no, mRuns);
[4620]822    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
[4860]823    append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
824    assert (verify(mRuns, mQuads));
[4618]825}
826
[4620]827/** ------------------------------------------------------------------------------------------------------------- *
828 * @brief Range Set Constructor
829 ** ------------------------------------------------------------------------------------------------------------- */
[4860]830UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi)
[5240]831: mRuns(mAllocator)
832, mQuads(mAllocator)
[4860]833{
834    const codepoint_t lo_index = lo / QUAD_BITS;
835    const codepoint_t hi_index = hi / QUAD_BITS;
836    const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
837    const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
[4620]838    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
839    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
[4860]840    append_run(Empty, lo_index, mRuns);
841    bitquad_t mask = hi_quad;
842    if (lo_index == hi_index) {
843        mask &= lo_quad;
844    } else {
[4620]845        append_quad(lo_quad, mQuads, mRuns);
[4860]846        append_run(Full, hi_index - (lo_index + 1), mRuns);
[4618]847    }
[4860]848    append_quad(mask, mQuads, mRuns);
849    append_run(Empty, UNICODE_QUAD_COUNT - (hi_index + 1), mRuns);
850    assert (verify(mRuns, mQuads));
851}
852
853/** ------------------------------------------------------------------------------------------------------------- *
854 * @brief Range List Set Constructor
855 ** ------------------------------------------------------------------------------------------------------------- */
856template <typename itr>
857void convertIntervalRangesToSparseSet(const itr begin, const itr end, UnicodeSet::RunVector & mRuns, UnicodeSet::QuadVector & mQuads) {
858    assert (std::is_sorted(begin, end, [](const interval_t l, const interval_t r) {
859        assert (l.first <= l.second);
[5727]860        assert (l.second <= UNICODE_MAX);
[4860]861        assert (r.first <= r.second);
[5727]862        assert (r.second <= UNICODE_MAX);
[4860]863        return l.second < r.first;
864    }));
865
866    std::vector<run_t> runs;
867    std::vector<bitquad_t> quads;
868
869    codepoint_t prior_index = 0;
870    bitquad_t mask = 0;
871    for (auto interval = begin; interval != end; ) {
872        codepoint_t lo, hi;
873        std::tie(lo, hi) = *interval;
874        const codepoint_t lo_index = (lo / QUAD_BITS);
875        const codepoint_t hi_index = (hi / QUAD_BITS);
876        const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
877        const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
878        const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
879        const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
880        append_run(Empty, lo_index - prior_index, runs);
881        if (lo_index == hi_index) {
882            mask |= (lo_quad & hi_quad);
883        } else {
884            append_quad(mask | lo_quad, quads, runs);
885            append_run(Full, hi_index - (lo_index + 1), runs);
886            mask = hi_quad;
887        }
888        // if the next interval is in our current quad, continue to the next range
889        prior_index = hi_index;
890        if (LLVM_LIKELY(++interval != end)) {
891            if (hi_index == (interval->first / QUAD_BITS)) {
892                continue;
893            }
894        }
895        append_quad(mask, quads, runs);
896        mask = 0;
897        ++prior_index;
[4621]898    }
[4860]899    assert (mask == 0);
900    if (prior_index < UNICODE_QUAD_COUNT) {
901        append_run(Empty, UNICODE_QUAD_COUNT - prior_index, runs);
902    }   
903    assert (verify(runs, quads));
904    mRuns.assign(runs.begin(), runs.end());
905    mQuads.assign(quads.begin(), quads.end());
[4618]906}
907
[4860]908/** ------------------------------------------------------------------------------------------------------------- *
909 * @brief Interval Range Constructor
910 ** ------------------------------------------------------------------------------------------------------------- */
911UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end)
[5240]912: mRuns(0, {Empty, 0}, mAllocator)
913, mQuads(0, 0, mAllocator) {
[4860]914    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
[4621]915}
[4860]916
917/** ------------------------------------------------------------------------------------------------------------- *
918 * @brief Interval Range Constructor
919 ** ------------------------------------------------------------------------------------------------------------- */
920UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end)
[5240]921: mRuns(0, {Empty, 0}, mAllocator)
922, mQuads(0, 0, mAllocator) {
[4860]923    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
924}
925
926/** ------------------------------------------------------------------------------------------------------------- *
927 * @brief Copy Constructor
928 ** ------------------------------------------------------------------------------------------------------------- */
929UnicodeSet::UnicodeSet(const UnicodeSet & other)
[5240]930: mRuns(other.mRuns, mAllocator)
931, mQuads(other.mQuads, mAllocator) {
[4860]932    assert (verify(mRuns, mQuads));
933}
934
935/** ------------------------------------------------------------------------------------------------------------- *
936 * @brief Initializer Constructor
937 ** ------------------------------------------------------------------------------------------------------------- */
938UnicodeSet::UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q)
[5240]939: mRuns(r.begin(), r.end(), mAllocator)
940, mQuads(q.begin(), q.end(), mAllocator) {
[4860]941    assert (verify(mRuns, mQuads));
942}
943
944/** ------------------------------------------------------------------------------------------------------------- *
945 * @brief Internal Vector Constructor
946 ** ------------------------------------------------------------------------------------------------------------- */
947inline UnicodeSet::UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q)
[5240]948: mRuns(r.begin(), r.end(), mAllocator)
949, mQuads(q.begin(), q.end(), mAllocator) {
[4860]950    assert (verify(mRuns, mQuads));
951}
952
953}
Note: See TracBrowser for help on using the repository browser.