source: icGREP/icgrep-devel/icgrep/UCD/unicode_set.h @ 4622

Last change on this file since 4622 was 4622, checked in by nmedfort, 4 years ago

Preliminary changes to inclusion of UCD Compiler into the RE Compiler.

File size: 6.3 KB
RevLine 
[4189]1#ifndef UNICODE_SET_H
2#define UNICODE_SET_H
3#include <stdint.h>
4#include <vector>
[4617]5#include <re/re_cc.h>
[4616]6#include <boost/iterator/iterator_facade.hpp>
[4611]7
[4189]8//
9// unicode_set.h - representing and manipulating sets of Unicode
10// characters, based on data from UCD - the Unicode Character Database
11//
12// Robert D. Cameron
13// September 18, 2014
14//
15// Licensed under Open Software License 3.0.
16//
17// Unicode Sparse Bitset Representation
18//
19// The Unicode Sparse Bitset representation is based on
20// (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
21// (b) Specifying the quads using a run-length encoding, in which each run
22//     is Empty (quads contain no members), Mixed (quads contain some members and
23//     some nonmembers) or Full (all codepoints in each quad are members of the set).
24// (c) Explicitly listing all the quads of Mixed type.
25//
26
27//
28// The internal datatype for quads - bitsets of 2^k codepoints.
29// Default: 64 codepoints (k=6).
30//
[4616]31
[4618]32namespace llvm {
33class raw_ostream;
34}
35
[4621]36namespace UCD {
[4189]37
38enum run_type_t : uint16_t {Empty, Mixed, Full};
39
[4620]40class UnicodeSet {
41public:
42
[4621]43    using bitquad_t = uint32_t;
44    using length_t = uint16_t;
45    using run_t = std::pair<run_type_t, length_t>;
[4622]46    using quad_iterator_return_t = std::pair<run_t, bitquad_t>;
[4621]47
[4618]48    using codepoint_t = re::codepoint_t;
49    using interval_t = re::interval_t;
[4621]50    using RunVector = std::vector<run_t>;
[4618]51    using QuadVector = std::vector<bitquad_t>;
[4616]52
[4620]53    class iterator : public boost::iterator_facade<iterator, interval_t, boost::forward_traversal_tag, interval_t> {
[4616]54        friend class UnicodeSet;
[4617]55        friend class boost::iterator_core_access;
[4616]56    protected:
[4618]57        iterator(RunVector::const_iterator runIterator, QuadVector::const_iterator quadIterator)
[4620]58        : mRunIterator(runIterator), mQuadIterator(quadIterator)
[4621]59        , mMixedRunIndex(0), mQuadOffset(0), mBaseCodePoint(0), mMinCodePoint(0), mMaxCodePoint(0)
[4618]60        {
[4617]61
[4618]62        }
63
[4620]64        void advance(const unsigned n);
[4617]65
[4622]66        inline interval_t dereference() const {
[4618]67            return std::make_pair(mMinCodePoint, mMaxCodePoint);
68        }
[4617]69
[4616]70        inline void increment() {
71            advance(1);
72        }
[4617]73
[4622]74        inline bool equal(const iterator & other) const {
[4621]75            return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator) &&
76                   (mMixedRunIndex == other.mMixedRunIndex) && (mQuadOffset == other.mQuadOffset);
[4616]77        }
78    private:
[4621]79        RunVector::const_iterator   mRunIterator;
80        QuadVector::const_iterator  mQuadIterator;
81        unsigned                    mMixedRunIndex;
82        bitquad_t                   mQuadOffset;       
83        codepoint_t                 mBaseCodePoint;
84        codepoint_t                 mMinCodePoint;
85        codepoint_t                 mMaxCodePoint;
[4616]86    };
87
[4618]88    inline iterator begin() const {
[4620]89        // note: pre-increment is intentional to move the iterator onto the first non-Empty interval.
90        return ++iterator(mRuns.cbegin(), mQuads.cbegin());
[4618]91    }
92
93    inline iterator end() const {
[4620]94        return iterator(mRuns.cend(), mQuads.cend());
[4618]95    }
96
[4622]97    class quad_iterator : public boost::iterator_facade<quad_iterator, quad_iterator_return_t, boost::random_access_traversal_tag, quad_iterator_return_t> {
[4617]98        friend class UnicodeSet;
99        friend class boost::iterator_core_access;
[4618]100    public:
[4620]101        quad_iterator(RunVector::const_iterator runIterator, QuadVector::const_iterator quadIterator)
102            : mRunIterator(runIterator), mQuadIterator(quadIterator), mOffset(0) {}
[4617]103
104        void advance(unsigned n);
105
[4622]106        inline quad_iterator_return_t dereference() const {
107            return std::make_pair(run(), quad());
[4617]108        }
109
110        inline void increment() {
111            advance(1);
112        }
113
[4622]114        inline run_t run() const {
[4620]115            const auto & t = *mRunIterator;
[4621]116            return std::make_pair(std::get<0>(t), std::get<1>(t) - mOffset);
[4618]117        }
118
[4622]119        inline bitquad_t quad() const {
[4620]120            return *mQuadIterator;
[4618]121        }
122
123        inline bool equal(const quad_iterator & other) const {
[4620]124            return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator);
[4617]125        }
[4618]126
[4617]127    private:
[4620]128        RunVector::const_iterator   mRunIterator;
129        QuadVector::const_iterator  mQuadIterator;
[4618]130        unsigned                    mOffset;
[4617]131    };
132
133    inline quad_iterator quad_begin() const {
[4620]134        return quad_iterator(mRuns.cbegin(), mQuads.cbegin());
[4617]135    }
136
137    inline quad_iterator quad_end() const {
[4620]138        return quad_iterator(mRuns.cend(), mQuads.cend());
[4617]139    }
140
[4620]141    bool contains(const codepoint_t codepoint) const;
[4616]142
[4620]143    void dump(llvm::raw_ostream & out) const;
[4616]144
[4621]145    UnicodeSet operator~() const;
146    UnicodeSet operator&(const UnicodeSet & other) const;
147    UnicodeSet operator+(const UnicodeSet & other) const;
148    UnicodeSet operator-(const UnicodeSet & other) const;
149    UnicodeSet operator^(const UnicodeSet & other) const;
[4622]150    inline UnicodeSet & operator=(const UnicodeSet & other) = default;
151    inline UnicodeSet & operator=(UnicodeSet && other) = default;
[4621]152    UnicodeSet operator==(const UnicodeSet & other) const;
[4620]153
154    UnicodeSet();
155    UnicodeSet(const codepoint_t codepoint);
156    UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint);
[4622]157    inline UnicodeSet(const UnicodeSet & other) = default;
[4621]158    UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q) : mRuns(r), mQuads(q) {}
159    UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q) : mRuns(r), mQuads(q) {}
[4620]160
[4621]161    inline void swap(UnicodeSet & other);
162    inline void swap(UnicodeSet && other);
163
[4618]164private:
165
[4622]166    RunVector       mRuns;
167    QuadVector      mQuads;
[4189]168};
169
[4621]170inline void UnicodeSet::swap(UnicodeSet & other) {
[4622]171    mRuns.swap(other.mRuns); mQuads.swap(other.mQuads);
[4621]172}
173
174inline void UnicodeSet::swap(UnicodeSet && other) {
[4622]175    mRuns.swap(other.mRuns); mQuads.swap(other.mQuads);
[4621]176}
177
[4618]178inline UnicodeSet uset_complement(const UnicodeSet & s) {
[4621]179    return ~s;
[4618]180}
[4189]181
[4618]182inline UnicodeSet uset_intersection(const UnicodeSet & s1, const UnicodeSet & s2) {
183    return s1 & s2;
184}
185
186inline UnicodeSet uset_union(const UnicodeSet & s1, const UnicodeSet & s2) {
187    return s1 + s2;
188}
189
190inline UnicodeSet uset_difference(const UnicodeSet & s1, const UnicodeSet & s2) {
191    return s1 - s2;
192}
193
194inline UnicodeSet uset_symmetric_difference(const UnicodeSet & s1, const UnicodeSet & s2) {
195    return s1 ^ s2;
196}
197
[4621]198}
199
[4189]200#endif
201
Note: See TracBrowser for help on using the repository browser.