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

Last change on this file since 4850 was 4850, checked in by cameron, 4 years ago

Fixes for set intersection

File size: 26.4 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#include <include/simd-lib/builtins.hpp>
26#include <iostream>
27
28namespace UCD {
29
30using bitquad_t = UnicodeSet::bitquad_t;
31using run_t = UnicodeSet::run_t;
32using RunVector = UnicodeSet::RunVector;
33using QuadVector = UnicodeSet::QuadVector;
34
35const size_t QUAD_BITS = (8 * sizeof(bitquad_t));
36const size_t MOD_QUAD_BIT_MASK = QUAD_BITS - 1;
37const size_t UNICODE_QUAD_COUNT = (UNICODE_MAX + 1) / QUAD_BITS;
38const bitquad_t FULL_QUAD_MASK = -1;
39
40inline run_type_t typeOf(const run_t & run) {
41    return run.first;
42}
43
44inline UnicodeSet::length_t lengthOf(const run_t & run) {
45    return run.second;
46}
47
48/** ------------------------------------------------------------------------------------------------------------- *
49 * @brief append_run
50 ** ------------------------------------------------------------------------------------------------------------- */
51inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) {
52    if (LLVM_UNLIKELY(length == 0)) {
53        return;
54    }
55    else if (!runs.empty() && typeOf(runs.back()) == type) {
56        std::get<1>(runs.back()) += length;
57        return;
58    }
59    runs.emplace_back(type, length);
60}
61
62/** ------------------------------------------------------------------------------------------------------------- *
63 * @brief append_quad
64 ** ------------------------------------------------------------------------------------------------------------- */
65inline void append_quad(const bitquad_t quad, QuadVector & quads, RunVector & runs) {
66    run_type_t type = Empty;
67    if (LLVM_UNLIKELY(quad == 0)) {
68        type = Empty;
69    }
70    else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
71        type = Full;
72    }
73    else {
74        quads.emplace_back(quad);
75        type = Mixed;
76    }
77    append_run(type, 1, runs);
78}
79
80#ifndef NDEBUG
81/** ------------------------------------------------------------------------------------------------------------- *
82 * @brief runLengthSumsUpToUnicodeQuadCount
83 *
84 * Sanity check for each function that constructs a new UnicodeSet
85 ** ------------------------------------------------------------------------------------------------------------- */
86inline bool runLengthSumsUpToUnicodeQuadCount(const RunVector & runs) {
87    unsigned sum = 0;
88    for (auto & run : runs) {
89        sum += lengthOf(run);
90    }
91    return sum == UNICODE_QUAD_COUNT;
92}
93#endif
94
95/** ------------------------------------------------------------------------------------------------------------- *
96 * @brief empty
97 ** ------------------------------------------------------------------------------------------------------------- */
98bool UnicodeSet::empty() const {
99    return (mRuns.size() == 1) && typeOf(mRuns.front()) == Empty;
100}
101
102/** ------------------------------------------------------------------------------------------------------------- *
103 * @brief size
104 ** ------------------------------------------------------------------------------------------------------------- */
105UnicodeSet::size_type UnicodeSet::size() const {
106    return std::distance(begin(), end());
107}
108
109/** ------------------------------------------------------------------------------------------------------------- *
110 * @brief front
111 ** ------------------------------------------------------------------------------------------------------------- */
112UnicodeSet::interval_t UnicodeSet::front() const {
113    return *begin();
114}
115
116/** ------------------------------------------------------------------------------------------------------------- *
117 * @brief back
118 ** ------------------------------------------------------------------------------------------------------------- */
119UnicodeSet::interval_t UnicodeSet::back() const {
120    auto back = begin();
121    for (auto i = back; i != end(); back = i++);
122    return *back;
123}
124
125/** ------------------------------------------------------------------------------------------------------------- *
126 * @brief dump
127 ** ------------------------------------------------------------------------------------------------------------- */
128void UnicodeSet::dump(llvm::raw_ostream & out) const {
129    auto qi = mQuads.cbegin();
130    for (const run_t & run : mRuns) {
131        if (typeOf(run) == Empty) {
132            out << "Empty(" << lengthOf(run) << ")\n";
133        }
134        else if (typeOf(run) == Full) {
135            out << "Full(" << lengthOf(run) << ")\n";
136        }
137        else {
138            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
139                assert (qi != mQuads.cend());
140                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
141            }
142        }
143    }
144}
145
146/** ------------------------------------------------------------------------------------------------------------- *
147 * @brief complement
148 ** ------------------------------------------------------------------------------------------------------------- */
149UnicodeSet UnicodeSet::operator~() const {
150    RunVector runs;
151    QuadVector quads;
152    runs.reserve(mRuns.size());
153    quads.reserve(mQuads.size());
154    auto qi = quads.cbegin();
155    for (const run_t & run : mRuns) {
156        if (typeOf(run) == Empty) {
157            append_run(Full, lengthOf(run), runs);
158        }
159        else if (typeOf(run) == Full) {
160            append_run(Empty, lengthOf(run), runs);
161        }
162        else {
163            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
164                assert (qi != quads.cend());
165                append_quad(FULL_QUAD_MASK ^ *qi, quads, runs);
166            }
167        }
168    }
169    assert (runLengthSumsUpToUnicodeQuadCount(runs));
170    return UnicodeSet(std::move(runs), std::move(quads));
171}
172
173/** ------------------------------------------------------------------------------------------------------------- *
174 * @brief intersection
175 ** ------------------------------------------------------------------------------------------------------------- */
176UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
177    RunVector runs;
178    QuadVector quads;
179    const auto e1 = quad_end();
180    const auto e2 = other.quad_end();
181    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
182        const auto n = std::min(i1.length(), i2.length());
183        if ((i1.type() == Full) && (i2.type() == Full)) {
184            append_run(Full, n, runs);
185            i1 += n;
186            i2 += n;
187        }
188        else if ((i1.type() == Empty) || (i2.type() == Empty)) {
189            append_run(Empty, n, runs);
190            i1 += n;
191            i2 += n;
192        }
193        else if (i1.type() == Full) {
194            for (unsigned i = 0; i != n; ++i, ++i2) {
195                append_quad(i2.quad(), quads, runs);
196            }
197            i1 += n;
198        }
199        else if (i2.type() == Full) {
200            for (unsigned i = 0; i != n; ++i, ++i1) {
201                append_quad(i1.quad(), quads, runs);
202            }
203            i2 += n;
204        }
205        else { //both Mixed
206            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
207                append_quad(i1.quad() & i2.quad(), quads, runs);
208            }
209        }
210    }
211    assert (runLengthSumsUpToUnicodeQuadCount(runs));
212    return UnicodeSet(std::move(runs), std::move(quads));
213}
214
215/** ------------------------------------------------------------------------------------------------------------- *
216 * @brief union
217 ** ------------------------------------------------------------------------------------------------------------- */
218UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
219    RunVector runs;
220    QuadVector quads;
221    const auto e1 = quad_end();
222    const auto e2 = other.quad_end();
223    auto i1 = quad_begin(), i2 = other.quad_begin();
224    for (; i1 != e1 && i2 != e2; ) {
225        const auto n = std::min(i1.length(), i2.length());
226        if ((i1.type() == Empty) && (i2.type() == Empty)) {
227            append_run(Empty, n, runs);
228            i1 += n;
229            i2 += n;
230        }
231        else if ((i1.type() == Full) || (i2.type() == Full)) {
232            append_run(Full, n, runs);
233            i1 += n;
234            i2 += n;
235        }
236        else if (i1.type() == Empty) {
237            for (unsigned i = 0; i != n; ++i, ++i2) {
238                append_quad(i2.quad(), quads, runs);
239            }
240            i1 += n;
241        }
242        else if (i2.type() == Empty) {
243            for (unsigned i = 0; i != n; ++i, ++i1) {
244                append_quad(i1.quad(), quads, runs);
245            }
246            i2 += n;
247        }
248        else {
249            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
250                append_quad(i1.quad() | i2.quad(), quads, runs);
251            }
252        }
253    }
254    assert (runLengthSumsUpToUnicodeQuadCount(runs));
255    return UnicodeSet(std::move(runs), std::move(quads));
256}
257
258/** ------------------------------------------------------------------------------------------------------------- *
259 * @brief difference
260 ** ------------------------------------------------------------------------------------------------------------- */
261UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
262    RunVector runs;
263    QuadVector quads;
264    const auto e1 = quad_end();
265    const auto e2 = other.quad_end();
266    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
267        unsigned n = std::min(i1.length(), i2.length());
268        if ((i1.type() == Empty) || (i2.type() == Full) || (i1.type() == Full && i2.type() == Empty)) {
269            append_run(i1.type(), n, runs);
270            i1 += n;
271            i2 += n;
272        }
273        else if (i1.type() == Full) {
274            for (unsigned i = 0; i != n; ++i, ++i2) {
275                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
276            }
277            i1 += n;
278        }
279        else if (i2.type() == Empty) {
280            for (unsigned i = 0; i != n; ++i, ++i1) {
281                append_quad(i1.quad(), quads, runs);
282            }
283            i2 += n;
284        }
285        else {
286            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
287                append_quad(i1.quad() &~ i2.quad(), quads, runs);
288            }
289        }
290    }
291    assert (runLengthSumsUpToUnicodeQuadCount(runs));
292    return UnicodeSet(std::move(runs), std::move(quads));
293}
294
295/** ------------------------------------------------------------------------------------------------------------- *
296 * @brief symmetric difference
297 ** ------------------------------------------------------------------------------------------------------------- */
298UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
299    RunVector runs;
300    QuadVector quads;
301    const auto e1 = quad_end();
302    const auto e2 = other.quad_end();
303    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
304        unsigned n = std::min(i1.length(), i2.length());
305        if (i1.type() != Mixed && i2.type() != Mixed) {
306            append_run(i1.type() == i2.type() ? Empty : Full, n, runs);
307            i1 += n;
308            i2 += n;
309        }
310        else if (i1.type() == Empty) {
311            for (unsigned i = 0; i < n; ++i, ++i2) {
312                append_quad(i2.quad(), quads, runs);
313            }
314            i1 += n;
315        }
316        else if (i2.type() == Empty) {
317            for (unsigned i = 0; i < n; ++i, ++i1) {
318                append_quad(i1.quad(), quads, runs);
319            }
320            i2 += n;
321        }
322        else if (i1.type() == Full) {
323            for (unsigned i = 0; i < n; ++i, ++i2) {
324                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
325            }
326            i1 += n;
327        }
328        else if (i2.type() == Empty) {
329            for (unsigned i = 0; i < n; ++i, ++i1) {
330                append_quad(FULL_QUAD_MASK ^ i1.quad(), quads, runs);
331            }
332            i2 += n;
333        }
334        else {
335            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
336                append_quad(i1.quad() ^ i2.quad(), quads, runs);
337            }
338        }
339    }
340    assert (runLengthSumsUpToUnicodeQuadCount(runs));
341    return UnicodeSet(std::move(runs), std::move(quads));
342}
343
344/** ------------------------------------------------------------------------------------------------------------- *
345 * @brief equality
346 ** ------------------------------------------------------------------------------------------------------------- */
347bool UnicodeSet::operator==(const UnicodeSet & other) const {
348    if (mRuns.size() != other.mRuns.size() || mQuads.size() != other.mQuads.size()) {
349        return false;
350    }
351    for (auto i = mQuads.begin(), j = other.mQuads.begin(); i != mQuads.end(); ++i, ++j) {
352        if (*i != *j) return false;
353    }
354    for (auto i = mRuns.begin(), j = other.mRuns.begin(); i != mRuns.end(); ++i, ++j) {
355        if (*i != *j) return false;
356    }
357    return true;
358}
359
360/** ------------------------------------------------------------------------------------------------------------- *
361 * @brief less operator
362 ** ------------------------------------------------------------------------------------------------------------- */
363bool UnicodeSet::operator<(const UnicodeSet & other) const {
364    if (LLVM_LIKELY(mRuns.size() != other.mRuns.size())) {
365        return mRuns.size() < other.mRuns.size();
366    } else if (LLVM_LIKELY(mQuads.size() != other.mQuads.size())) {
367        return (mQuads.size() < other.mQuads.size());
368    } else { // equal run and quad lengths; test their individual values
369        for (auto ri = mRuns.cbegin(), end = mRuns.cend(), rj = other.mRuns.cbegin(); ri != end; ++ri, ++rj) {
370            if (*ri < *rj) {
371                return true;
372            } else if (*ri > *rj) {
373                return false;
374            }
375        }
376        for (auto qi = mQuads.cbegin(), end = mQuads.cend(), qj = other.mQuads.cbegin(); qi != end; ++qi, ++qj) {
377            if (*qi < *qj) {
378                return true;
379            } else if (*qi > *qj) {
380                return false;
381            }
382        }
383        return false;
384    }
385}
386
387///** ------------------------------------------------------------------------------------------------------------- *
388// * @brief insert_range
389// ** ------------------------------------------------------------------------------------------------------------- */
390//void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi)  {
391
392//    if (LLVM_UNLIKELY(lo > hi)) {
393//        throw std::runtime_error('[' + std::to_string(lo) + ',' + std::to_string(hi) + "] is an illegal codepoint range!");
394//    } else if (LLVM_UNLIKELY(hi >= 0x110000)) {
395//        throw std::runtime_error(std::to_string(hi) + " exceeds maximum code point.");
396//    }
397
398//    auto r = mRuns.begin();
399//    auto q = mQuads.begin();
400//    unsigned offset = 0;
401
402//    auto lo_quad_no = lo / QUAD_BITS;
403//    auto lo_offset = lo & MOD_QUAD_BIT_MASK;
404
405//    auto hi_quad_no = hi / QUAD_BITS;
406//    auto hi_offset = hi & MOD_QUAD_BIT_MASK;
407
408//    // Scan up to the lo codepoint
409//    for (;;) {
410//        assert (r != mRuns.end());
411//        const auto l = lengthOf(*r);
412//        if ((offset + l) > lo_quad_no) {
413//            break;
414//        }
415//        if (typeOf(*r) == Mixed) {
416//            q += lengthOf(*r);
417//        }
418//        offset += l;
419//        ++r;
420//    }
421
422//    // Test whether the range is already 'full' and skip ahead to the first empty or mixed quad.
423//    // If the entire [lo,hi] range is already covered by a Full run, abort.
424//    while (typeOf(*r) == Full) {
425//        const auto l = lengthOf(*r);
426//        lo_quad_no += l;
427//        offset = lo_quad_no;
428//        lo_offset = 0;
429//        if (lo_quad_no > hi_quad_no) {
430//            return;
431//        }
432//        ++r;
433//    }
434
435//    // Otherwise, some portion of this range has to be inserted into the current sparse set.
436//    // Begin by inserting the initial (potentially) partial lo quad.
437//    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
438//    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
439//    bitquad_t quad = (lo_quad_no == hi_quad_no) ? (lo_quad & hi_quad) : lo_quad;
440//    run_type_t newType = (quad == FULL_QUAD_MASK) ? Full : ((quad == 0) ? Empty : Mixed);
441//    run_type_t runType = typeOf(*r);
442//    // If the original run is Mixed, we may be able to simply update the quad accordingly.
443//    if (runType == Mixed) {
444//        q += (lo_quad_no - offset);
445//        quad |= *q;
446//        if (LLVM_LIKELY(quad != FULL_QUAD_MASK)) {
447//            *q = quad;
448//            if (lo_quad_no == hi_quad_no) {
449//                return;
450//            }
451//        } else { // we filled a Mixed quad
452//            mQuads.erase(q);
453//        }
454//        newType = Full;
455//    }
456//    auto length = lengthOf(*r);
457//    auto splitAt = length - (lo_quad_no - offset) - 1;
458//    if (splitAt) {
459//        // reduce the original run length
460//        lengthOf(*r) = splitAt;
461//        // and add in a new quad
462//        r = mRuns.emplace(r, newType, 1);
463//    } else { // we're inserting this quad at the beginning of the run
464//        typeOf(*r) = newType;
465//        lengthOf(*r) = 1;
466//    }
467//    if (newType == Mixed) {
468//        q = mQuads.emplace(q, quad);
469//    }
470//    length -= splitAt + 1;
471//    auto remaining = (hi_quad_no - lo_quad_no);
472//    // We're inserting a Full run so if the original run type was Full and exceeds the
473//    // length of what we're inserting, we can abort without considering the hi_quad
474//    if (runType == Full && length > remaining) {
475//        return;
476//    }
477//    if (remaining) {
478//        r = mRuns.emplace(r, Full, remaining);
479
480
481
482//    }
483
484//}
485
486
487
488/** ------------------------------------------------------------------------------------------------------------- *
489 * @brief contains
490 * @param codepoint
491 *
492 * Return whether this UnicodeSet contains the specified code point
493 ** ------------------------------------------------------------------------------------------------------------- */
494bool UnicodeSet::contains(const codepoint_t codepoint) const {
495    auto n = codepoint / QUAD_BITS;
496    auto qi = mQuads.cbegin();
497    for (const auto & r : mRuns) {
498        if (lengthOf(r) >= n) {
499            if (typeOf(r) == Mixed) {
500                qi += n - 1;
501                return (*qi & (static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK))) != 0;
502            }
503            return (typeOf(r) == Full);
504        }
505        if (typeOf(r) == Mixed) {
506            qi += lengthOf(r);
507        }       
508        n -= lengthOf(r);
509    }
510    return false;
511}
512
513/** ------------------------------------------------------------------------------------------------------------- *
514 * @brief intersects
515 * @param lo_codepoint
516 * @param hi_codepoint
517 *
518 * Return true if this UnicodeSet contains any code point(s) between lo and hi (inclusive)
519 ** ------------------------------------------------------------------------------------------------------------- */
520bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const {
521    for (auto range : *this) {
522        if (range.second < lo) {
523            continue;
524        }
525        if (range.first > hi) {
526            break;
527        }
528        return true;
529    }
530    return false;
531}
532
533/** ------------------------------------------------------------------------------------------------------------- *
534 * @brief UnicodeSet::quad_iterator::advance
535 ** ------------------------------------------------------------------------------------------------------------- */
536void UnicodeSet::quad_iterator::advance(unsigned n) {
537    while (n > 0) {
538        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
539        if (remain > n) {
540            if (typeOf(*mRunIterator) == Mixed) {
541                mQuadIterator += n;
542            }
543            mOffset += n;
544            break;
545        }
546        if (typeOf(*mRunIterator) == Mixed) {
547            mQuadIterator += remain;
548        }
549        ++mRunIterator;
550        mOffset = 0;
551        n -= remain;
552    }
553}
554
555/** ------------------------------------------------------------------------------------------------------------- *
556 * @brief UnicodeSet::iterator::advance
557 ** ------------------------------------------------------------------------------------------------------------- */
558void UnicodeSet::iterator::advance(const unsigned n) {
559
560    assert (n == 1);
561
562    if (LLVM_UNLIKELY(mMinCodePoint >= 0x110000)) {
563        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
564    }
565
566    bool found = false;
567    // Find the start of our interval
568    while ( mBaseCodePoint < 0x110000 ) {
569        // Find the first non-empty block
570        if (typeOf(*mRunIterator) != Mixed) {           
571            // If we found a full run, this must be the start of our interval.
572            const auto baseCodePoint = mBaseCodePoint;
573            const auto type = typeOf(*mRunIterator);
574            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
575            if (type == Full) {
576                mMinCodePoint = baseCodePoint;
577                found = true;
578                break;
579            }
580        } else { // if (typeOf(t) == Mixed)
581            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
582                const bitquad_t m = (*mQuadIterator) & (FULL_QUAD_MASK << mQuadOffset);
583                // If we found a marker in m, it marks the beginning of our current interval.
584                // Find it and break out of the loop.
585                if (m) {
586                    mQuadOffset = scan_forward_zeroes(m);
587                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
588                    found = true;
589                    break;
590                }
591                mBaseCodePoint += QUAD_BITS;
592                ++mQuadIterator;
593                ++mMixedRunIndex;
594                mQuadOffset = 0;
595            }
596            if (found) break;
597            ++mRunIterator;
598            mQuadOffset = 0;
599            mMixedRunIndex = 0;
600        }
601    }
602
603    if (!found) {
604        assert (mBaseCodePoint == 0x110000);
605        mMinCodePoint = 0x110000;
606        return;
607    }
608
609    // at this stage, the max code point is the previous max code point (initially 0)
610    assert (mMaxCodePoint <= mMinCodePoint);
611    found = false;
612    // Find the end of our interval
613    while ( mBaseCodePoint < 0x110000 ) {
614
615        // Find the first non-Full block
616        if (typeOf(*mRunIterator) != Mixed) {
617            // If this run is Empty, the max code point is the last computed base code point - 1.
618            const auto baseCodePoint = mBaseCodePoint;
619            const auto type = typeOf(*mRunIterator);
620            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
621            if (type == Empty) {
622                mMaxCodePoint = baseCodePoint - 1;
623                found = true;
624                break;
625            }
626        } else { // if (typeOf(t) == Mixed)
627            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
628                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
629
630                // If we found a marker in m, it marks the end of our current interval.
631                // Find it and break out of the loop.
632                if (m) {
633                    mQuadOffset = scan_forward_zeroes(m);
634                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
635                    found = true;
636                    break;
637                }
638                mBaseCodePoint += QUAD_BITS;
639                ++mQuadIterator;
640                ++mMixedRunIndex;
641                mQuadOffset = 0;
642            }
643            if (found) break;
644            ++mRunIterator;
645            mQuadOffset = 0;
646            mMixedRunIndex = 0;
647        }
648    }
649    // if the very last block is a mixed block and we go past it, the last code point of the range is 0x10FFFF
650    if (!found) {
651        assert (mBaseCodePoint == 0x110000);
652        mMaxCodePoint = 0x10FFFF;
653    }
654
655    assert (mMinCodePoint <= mMaxCodePoint);
656}
657
658/** ------------------------------------------------------------------------------------------------------------- *
659 * @brief Empty Set Constructor
660 ** ------------------------------------------------------------------------------------------------------------- */
661UnicodeSet::UnicodeSet() : mRuns({{{Empty, UNICODE_QUAD_COUNT}}}) { }
662
663/** ------------------------------------------------------------------------------------------------------------- *
664 * @brief Singleton Set Constructor
665 ** ------------------------------------------------------------------------------------------------------------- */
666UnicodeSet::UnicodeSet(const codepoint_t codepoint) {
667    const codepoint_t quad_no = codepoint / QUAD_BITS;
668    if (quad_no > 0) {
669        append_run(Empty, quad_no, mRuns);
670    }
671    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
672    if (quad_no < UNICODE_QUAD_COUNT - 1) {
673        append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
674    }
675    assert (runLengthSumsUpToUnicodeQuadCount(mRuns));
676}
677
678/** ------------------------------------------------------------------------------------------------------------- *
679 * @brief Range Set Constructor
680 ** ------------------------------------------------------------------------------------------------------------- */
681UnicodeSet::UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) {
682    const codepoint_t lo_quad_no = lo_codepoint / QUAD_BITS;
683    const codepoint_t hi_quad_no = hi_codepoint / QUAD_BITS;
684    const codepoint_t lo_offset = lo_codepoint & MOD_QUAD_BIT_MASK;
685    const codepoint_t hi_offset = hi_codepoint & MOD_QUAD_BIT_MASK;
686    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
687    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
688    append_run(Empty, lo_quad_no, mRuns);
689    if (lo_quad_no == hi_quad_no) {       
690        append_quad(lo_quad & hi_quad, mQuads, mRuns);
691    }
692    else {
693        append_quad(lo_quad, mQuads, mRuns);
694        append_run(Full, hi_quad_no - (lo_quad_no + 1), mRuns);
695        append_quad(hi_quad, mQuads, mRuns);
696    }
697    if (hi_quad_no < UNICODE_QUAD_COUNT - 1) {
698        append_run(Empty, UNICODE_QUAD_COUNT - (hi_quad_no + 1), mRuns);
699    }
700    assert (runLengthSumsUpToUnicodeQuadCount(mRuns));
701}
702
703}
Note: See TracBrowser for help on using the repository browser.