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

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

Fix to compile under Mac OS

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