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
Line 
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>
23#include <llvm/Support/raw_ostream.h>
24#include <llvm/Support/Format.h>
25
26namespace UCD {
27
28using bitquad_t = UnicodeSet::bitquad_t;
29using run_t = UnicodeSet::run_t;
30using interval_t = UnicodeSet::interval_t;
31
32//
33// Select the correct built-in scan function, dependent on whatever
34// bitquad_t resolves to, when scan_forward_zeroes<bitquad_t> is called.
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
40SlabAllocator<> UnicodeSet::mAllocator;
41
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;
45const bitquad_t FULL_QUAD_MASK = -1;
46
47inline run_type_t typeOf(const run_t & run) {
48    return run.first;
49}
50
51inline UnicodeSet::length_t lengthOf(const run_t & run) {
52    return run.second;
53}
54
55/** ------------------------------------------------------------------------------------------------------------- *
56 * @brief append_run
57 ** ------------------------------------------------------------------------------------------------------------- */
58template <class RunVector>
59inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) {
60    if (LLVM_UNLIKELY(length == 0)) {
61        return;
62    } else if (!runs.empty() && typeOf(runs.back()) == type) {
63        std::get<1>(runs.back()) += length;
64        return;
65    }
66    runs.emplace_back(type, length);
67}
68
69/** ------------------------------------------------------------------------------------------------------------- *
70 * @brief append_quad
71 ** ------------------------------------------------------------------------------------------------------------- */
72template <class QuadVector, class RunVector>
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;
77    } else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
78        type = Full;
79    } else {
80        quads.emplace_back(quad);
81        type = Mixed;
82    }
83    append_run(type, 1, runs);
84}
85
86#ifndef NDEBUG
87/** ------------------------------------------------------------------------------------------------------------- *
88 * @brief verify
89 *
90 * Sanity check for each function that constructs or modifies a UnicodeSet
91 ** ------------------------------------------------------------------------------------------------------------- */
92template <class RunVector, class QuadVector>
93inline bool verify(const RunVector & runs, const QuadVector & quads) {
94    unsigned sum = 0;
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;
105    }
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;
120}
121#endif
122
123/** ------------------------------------------------------------------------------------------------------------- *
124 * @brief empty
125 ** ------------------------------------------------------------------------------------------------------------- */
126bool UnicodeSet::empty() const {
127    return (mRuns.size() == 1) && typeOf(mRuns.front()) == Empty;
128}
129
130/** ------------------------------------------------------------------------------------------------------------- *
131 * @brief full
132 ** ------------------------------------------------------------------------------------------------------------- */
133bool UnicodeSet::full() const {
134    return (mRuns.size() == 1) && typeOf(mRuns.front()) == Full;
135}
136
137/** ------------------------------------------------------------------------------------------------------------- *
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/** ------------------------------------------------------------------------------------------------------------- *
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/** ------------------------------------------------------------------------------------------------------------- *
181 * @brief dump
182 ** ------------------------------------------------------------------------------------------------------------- */
183void UnicodeSet::dump(llvm::raw_ostream & out) const {
184    auto qi = mQuads.cbegin();
185    for (const run_t & run : mRuns) {
186        if (typeOf(run) == Empty) {
187            out << "Empty(" << lengthOf(run) << ")\n";
188        }
189        else if (typeOf(run) == Full) {
190            out << "Full(" << lengthOf(run) << ")\n";
191        }
192        else {
193            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
194                assert (qi != mQuads.cend());
195                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
196            }
197        }
198    }
199}
200
201/** ------------------------------------------------------------------------------------------------------------- *
202 * @brief complement
203 ** ------------------------------------------------------------------------------------------------------------- */
204UnicodeSet UnicodeSet::operator~() const {
205    std::vector<run_t> runs;
206    std::vector<bitquad_t> quads;
207    runs.reserve(mRuns.size());
208    quads.reserve(mQuads.size());
209    auto qi = quads.cbegin();
210    for (const run_t & run : mRuns) {
211        if (typeOf(run) == Empty) {
212            append_run(Full, lengthOf(run), runs);
213        }
214        else if (typeOf(run) == Full) {
215            append_run(Empty, lengthOf(run), runs);
216        }
217        else {
218            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
219                assert (qi != quads.cend());
220                append_quad(FULL_QUAD_MASK ^ *qi, quads, runs);
221            }
222        }
223    }
224    return UnicodeSet(std::move(runs), std::move(quads));
225}
226
227/** ------------------------------------------------------------------------------------------------------------- *
228 * @brief intersection
229 ** ------------------------------------------------------------------------------------------------------------- */
230UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
231    std::vector<run_t> runs;
232    std::vector<bitquad_t> quads;
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; ) {
236        const auto n = std::min(i1.length(), i2.length());
237        if ((i1.type() == Full) && (i2.type() == Full)) {
238            append_run(Full, n, runs);
239            i1 += n;
240            i2 += n;
241        }
242        else if ((i1.type() == Empty) || (i2.type() == Empty)) {
243            append_run(Empty, n, runs);
244            i1 += n;
245            i2 += n;
246        }
247        else if (i1.type() == Full) {
248            for (unsigned i = 0; i != n; ++i, ++i2) {
249                append_quad(i2.quad(), quads, runs);
250            }
251            i1 += n;
252        }
253        else if (i2.type() == Full) {
254            for (unsigned i = 0; i != n; ++i, ++i1) {
255                append_quad(i1.quad(), quads, runs);
256            }
257            i2 += n;
258        }
259        else { //both Mixed
260            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
261                append_quad(i1.quad() & i2.quad(), quads, runs);
262            }
263        }
264    }
265    return UnicodeSet(std::move(runs), std::move(quads));
266}
267
268/** ------------------------------------------------------------------------------------------------------------- *
269 * @brief union
270 ** ------------------------------------------------------------------------------------------------------------- */
271UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
272    std::vector<run_t> runs;
273    std::vector<bitquad_t> quads;
274    const auto e1 = quad_end();
275    const auto e2 = other.quad_end();
276    auto i1 = quad_begin(), i2 = other.quad_begin();
277    for (; i1 != e1 && i2 != e2; ) {
278        const auto n = std::min(i1.length(), i2.length());
279        if ((i1.type() == Empty) && (i2.type() == Empty)) {
280            append_run(Empty, n, runs);
281            i1 += n;
282            i2 += n;
283        } else if ((i1.type() == Full) || (i2.type() == Full)) {
284            append_run(Full, n, runs);
285            i1 += n;
286            i2 += n;
287        } else if (i1.type() == Empty) {
288            for (unsigned i = 0; i != n; ++i, ++i2) {
289                append_quad(i2.quad(), quads, runs);
290            }
291            i1 += n;
292        } else if (i2.type() == Empty) {
293            for (unsigned i = 0; i != n; ++i, ++i1) {
294                append_quad(i1.quad(), quads, runs);
295            }
296            i2 += n;
297        } else {
298            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
299                append_quad(i1.quad() | i2.quad(), quads, runs);
300            }
301        }
302    }
303    return UnicodeSet(std::move(runs), std::move(quads));
304}
305
306/** ------------------------------------------------------------------------------------------------------------- *
307 * @brief difference
308 ** ------------------------------------------------------------------------------------------------------------- */
309UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
310    std::vector<run_t> runs;
311    std::vector<bitquad_t> quads;
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; ) {
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);
318            i1 += n;
319            i2 += n;
320        }
321        else if (i1.type() == Full) {
322            for (unsigned i = 0; i != n; ++i, ++i2) {
323                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
324            }
325            i1 += n;
326        }
327        else if (i2.type() == Empty) {
328            for (unsigned i = 0; i != n; ++i, ++i1) {
329                append_quad(i1.quad(), quads, runs);
330            }
331            i2 += n;
332        }
333        else {
334            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
335                append_quad(i1.quad() &~ i2.quad(), quads, runs);
336            }
337        }
338    }
339    return UnicodeSet(std::move(runs), std::move(quads));
340}
341
342/** ------------------------------------------------------------------------------------------------------------- *
343 * @brief symmetric difference
344 ** ------------------------------------------------------------------------------------------------------------- */
345UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
346    std::vector<run_t> runs;
347    std::vector<bitquad_t> quads;
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; ) {
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);
354            i1 += n;
355            i2 += n;
356        } else if (i1.type() == Empty) {
357            for (unsigned i = 0; i < n; ++i, ++i2) {
358                append_quad(i2.quad(), quads, runs);
359            }
360            i1 += n;
361        } else if (i2.type() == Empty) {
362            for (unsigned i = 0; i < n; ++i, ++i1) {
363                append_quad(i1.quad(), quads, runs);
364            }
365            i2 += n;
366        } else if (i1.type() == Full) {
367            for (unsigned i = 0; i < n; ++i, ++i2) {
368                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
369            }
370            i1 += n;
371        } else if (i2.type() == Full) {
372            for (unsigned i = 0; i < n; ++i, ++i1) {
373                append_quad(FULL_QUAD_MASK ^ i1.quad(), quads, runs);
374            }
375            i2 += n;
376        } else {
377            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
378                append_quad(i1.quad() ^ i2.quad(), quads, runs);
379            }
380        }
381    }
382    return UnicodeSet(std::move(runs), std::move(quads));
383}
384
385/** ------------------------------------------------------------------------------------------------------------- *
386 * @brief equality
387 ** ------------------------------------------------------------------------------------------------------------- */
388bool UnicodeSet::operator==(const UnicodeSet & other) const {
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
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
428/** ------------------------------------------------------------------------------------------------------------- *
429 * @brief insert
430 ** ------------------------------------------------------------------------------------------------------------- */
431void UnicodeSet::insert(const codepoint_t cp) {
432
433    if (LLVM_UNLIKELY(cp > UNICODE_MAX)) {
434        throw std::runtime_error(std::to_string(cp) + " exceeds maximum code point.");
435    }
436
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    }
482
483    assert (verify(mRuns, mQuads));
484    assert (contains(cp));
485}
486
487/** ------------------------------------------------------------------------------------------------------------- *
488 * @brief insert_range
489 ** ------------------------------------------------------------------------------------------------------------- */
490void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi)  {
491
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    }
497
498    // Create a temporary run and quad set for the given range
499    std::vector<run_t> runs;
500    std::vector<bitquad_t> quads;
501
502    codepoint_t lo_index = lo / QUAD_BITS;
503    codepoint_t hi_index = hi / QUAD_BITS;
504
505    auto ri = mRuns.cbegin();
506    auto qi = mQuads.cbegin();
507
508    codepoint_t length = 0;
509    run_type_t type = Empty;
510
511    // Advance past any runs prior to the lo_index
512    for (;;) {
513        assert (ri != mRuns.cend());
514        std::tie(type, length) = *ri;       
515        if (lo_index < length) {
516            break;
517        }
518        if (type == Mixed) {
519            assert (std::distance(qi, mQuads.cend()) >= length);
520            qi += length;
521        }
522        lo_index -= length;
523        hi_index -= length;
524        ++ri;
525    }
526
527    // Now record the runs and any quads prior to lo_index
528    runs.assign(mRuns.cbegin(), ri++);
529    if (lo_index) {
530        runs.emplace_back(type, lo_index);
531        if (type == Mixed) {
532            assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) >= lo_index);
533            qi += lo_index;
534        }
535        hi_index -= lo_index;
536        length -= lo_index;
537    }
538
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)));
543
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) {
552            assert (std::distance(qi, mQuads.cend()) > 0);
553            lo_quad |= *qi++;
554        }
555        append_quad(lo_quad, quads, runs);
556    }
557    --length;
558
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
565        while (ri != mRuns.cend()) {
566            if (type == Mixed) {
567                assert (std::distance(qi, mQuads.cend()) >= length);
568                qi += length;
569            }
570            std::tie(type, length) = *ri++;
571            if (hi_index < length) {
572                break;
573            }
574            hi_index -= length;
575            length = 0;
576        }       
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) {
582                assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) > hi_index);
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
591    assert (length >= hi_index);
592    append_run(type, length - hi_index, runs);
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());
595    quads.insert(quads.end(), qi, mQuads.cend());
596    assert (verify(runs, quads));
597    mRuns.assign(runs.cbegin(), runs.cend());
598    mQuads.assign(quads.cbegin(), quads.cend());   
599}
600
601/** ------------------------------------------------------------------------------------------------------------- *
602 * @brief contains
603 * @param codepoint
604 *
605 * Return whether this UnicodeSet contains the specified code point
606 ** ------------------------------------------------------------------------------------------------------------- */
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;
618            }
619            return (t == Full);
620        }
621        if (t == Mixed) {
622            quad += l;
623        }       
624        offset -= l;
625    }
626    return false;
627}
628
629/** ------------------------------------------------------------------------------------------------------------- *
630 * @brief intersects
631 * @param lo_codepoint
632 * @param hi_codepoint
633 *
634 * Return true if this UnicodeSet contains any code point(s) between lo and hi (inclusive)
635 ** ------------------------------------------------------------------------------------------------------------- */
636bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const {
637    for (auto range : *this) {
638        if (range.second < lo) {
639            continue;
640        }
641        if (range.first > hi) {
642            break;
643        }
644        return true;
645    }
646    return false;
647}
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; ) {
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;
669            }
670        }
671    }
672    return false;
673}
674
675
676/** ------------------------------------------------------------------------------------------------------------- *
677 * @brief UnicodeSet::quad_iterator::advance
678 ** ------------------------------------------------------------------------------------------------------------- */
679void UnicodeSet::quad_iterator::advance(unsigned n) {
680    while (n > 0) {
681        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
682        if (remain > n) {
683            if (typeOf(*mRunIterator) == Mixed) {
684                mQuadIterator += n;
685            }
686            mOffset += n;
687            break;
688        }
689        if (typeOf(*mRunIterator) == Mixed) {
690            mQuadIterator += remain;
691        }
692        ++mRunIterator;
693        mOffset = 0;
694        n -= remain;
695    }
696}
697
698/** ------------------------------------------------------------------------------------------------------------- *
699 * @brief UnicodeSet::iterator::advance
700 ** ------------------------------------------------------------------------------------------------------------- */
701void UnicodeSet::iterator::advance(const unsigned n) {
702
703    assert (n == 1);
704
705    if (LLVM_UNLIKELY(mMinCodePoint > UNICODE_MAX)) {
706        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
707    }
708
709    bool found = false;
710    // Find the start of our interval
711    while ( mBaseCodePoint <= UNICODE_MAX ) {
712        // Find the first non-empty block
713        if (typeOf(*mRunIterator) != Mixed) {           
714            // If we found a full run, this must be the start of our interval.
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;
721                break;
722            }
723        } else { // if (typeOf(t) == Mixed)
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) {
729                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
730                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
731                    found = true;
732                    break;
733                }
734                mBaseCodePoint += QUAD_BITS;
735                ++mQuadIterator;
736                ++mMixedRunIndex;
737                mQuadOffset = 0;
738            }
739            if (found) break;
740            ++mRunIterator;
741            mQuadOffset = 0;
742            mMixedRunIndex = 0;
743        }
744    }
745
746    if (!found) {
747        assert (mBaseCodePoint == (UNICODE_MAX+1));
748        mMinCodePoint = (UNICODE_MAX+1);
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;
755    // Find the end of our interval
756    while ( mBaseCodePoint <= UNICODE_MAX ) {
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            }
769        } else { // if (typeOf(t) == Mixed)
770            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
771                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
772
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) {
776                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
777                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
778                    found = true;
779                    break;
780                }
781                mBaseCodePoint += QUAD_BITS;
782                ++mQuadIterator;
783                ++mMixedRunIndex;
784                mQuadOffset = 0;
785            }
786            if (found) break;
787            ++mRunIterator;
788            mQuadOffset = 0;
789            mMixedRunIndex = 0;
790        }
791    }
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
793    if (!found) {
794        assert (mBaseCodePoint == (UNICODE_MAX+1));
795        mMaxCodePoint = UNICODE_MAX;
796    }
797
798    assert (mMinCodePoint <= mMaxCodePoint);
799}
800   
801/** ------------------------------------------------------------------------------------------------------------- *
802 * @brief Empty/Full Set Constructor
803 ** ------------------------------------------------------------------------------------------------------------- */
804UnicodeSet::UnicodeSet(run_type_t emptyOrFull)
805: mRuns(mAllocator)
806, mQuads(mAllocator)
807{
808    assert((emptyOrFull == Empty) || (emptyOrFull == Full));
809    append_run(emptyOrFull, UNICODE_QUAD_COUNT, mRuns);
810    assert (verify(mRuns, mQuads));
811}
812           
813/** ------------------------------------------------------------------------------------------------------------- *
814 * @brief Singleton Set Constructor
815 ** ------------------------------------------------------------------------------------------------------------- */
816UnicodeSet::UnicodeSet(const codepoint_t codepoint)
817: mRuns(mAllocator)
818, mQuads(mAllocator)
819{
820    const codepoint_t quad_no = codepoint / QUAD_BITS;
821    append_run(Empty, quad_no, mRuns);
822    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
823    append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
824    assert (verify(mRuns, mQuads));
825}
826
827/** ------------------------------------------------------------------------------------------------------------- *
828 * @brief Range Set Constructor
829 ** ------------------------------------------------------------------------------------------------------------- */
830UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi)
831: mRuns(mAllocator)
832, mQuads(mAllocator)
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;
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));
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 {
845        append_quad(lo_quad, mQuads, mRuns);
846        append_run(Full, hi_index - (lo_index + 1), mRuns);
847    }
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);
860        assert (l.second <= UNICODE_MAX);
861        assert (r.first <= r.second);
862        assert (r.second <= UNICODE_MAX);
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;
898    }
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());
906}
907
908/** ------------------------------------------------------------------------------------------------------------- *
909 * @brief Interval Range Constructor
910 ** ------------------------------------------------------------------------------------------------------------- */
911UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end)
912: mRuns(0, {Empty, 0}, mAllocator)
913, mQuads(0, 0, mAllocator) {
914    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
915}
916
917/** ------------------------------------------------------------------------------------------------------------- *
918 * @brief Interval Range Constructor
919 ** ------------------------------------------------------------------------------------------------------------- */
920UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end)
921: mRuns(0, {Empty, 0}, mAllocator)
922, mQuads(0, 0, mAllocator) {
923    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
924}
925
926/** ------------------------------------------------------------------------------------------------------------- *
927 * @brief Copy Constructor
928 ** ------------------------------------------------------------------------------------------------------------- */
929UnicodeSet::UnicodeSet(const UnicodeSet & other)
930: mRuns(other.mRuns, mAllocator)
931, mQuads(other.mQuads, mAllocator) {
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)
939: mRuns(r.begin(), r.end(), mAllocator)
940, mQuads(q.begin(), q.end(), mAllocator) {
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)
948: mRuns(r.begin(), r.end(), mAllocator)
949, mQuads(q.begin(), q.end(), mAllocator) {
950    assert (verify(mRuns, mQuads));
951}
952
953}
Note: See TracBrowser for help on using the repository browser.