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

Last change on this file since 5739 was 5739, checked in by nmedfort, 22 months ago

Bug fixes for UnicodeSet?. Added count and at functions to count the number of codepoints in the set or return the k-th codepoint.

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