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

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

More modifications to UnicodeSet? class.

File size: 5.9 KB
Line 
1#ifndef UNICODE_SET_H
2#define UNICODE_SET_H
3#include <stdint.h>
4#include <vector>
5#include <re/re_cc.h>
6#include <boost/iterator/iterator_facade.hpp>
7
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//
31
32namespace llvm {
33class raw_ostream;
34}
35
36typedef uint32_t bitquad_t;
37
38// The representation for runs
39enum run_type_t : uint16_t {Empty, Mixed, Full};
40
41struct RunStructure {
42  RunStructure(run_type_t r, uint16_t lgth) : mType(r), mRunLength(lgth) {}
43  run_type_t mType;
44  uint16_t mRunLength;
45};
46
47class UnicodeSet;
48    using codepoint_t = re::codepoint_t;
49    using interval_t = re::interval_t;
50    using RunVector = std::vector<RunStructure>;
51    using QuadVector = std::vector<bitquad_t>;
52class UnicodeSet {
53public:
54
55    class iterator : public boost::iterator_facade<iterator, re::interval_t, boost::forward_traversal_tag, re::interval_t> {
56        friend class UnicodeSet;
57        friend class boost::iterator_core_access;
58    protected:
59        iterator(RunVector::const_iterator runIterator, QuadVector::const_iterator quadIterator)
60        : mRunIterator(runIterator), mQuadIterator(quadIterator), mQuadOffset(0)
61        , mQuadPosition(0), mBaseCodePoint(0), mMinCodePoint(0), mMaxCodePoint(0)
62        {
63
64        }
65
66        void advance(unsigned n);
67
68        re::interval_t dereference() const {
69            return std::make_pair(mMinCodePoint, mMaxCodePoint);
70        }
71
72        inline void increment() {
73            advance(1);
74        }
75
76        inline bool equal(iterator const & other) const {
77            assert (&(mUnicodeSet) == &(other.mUnicodeSet));
78            return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator);
79        }
80    private:
81        RunVector::const_iterator   mRunIterator;
82        QuadVector::const_iterator  mQuadIterator;
83        bitquad_t                   mQuadOffset;
84        unsigned                    mQuadPosition;
85        unsigned                    mBaseCodePoint;
86        re::codepoint_t             mMinCodePoint;
87        re::codepoint_t             mMaxCodePoint;
88    };
89
90    inline iterator begin() const {
91        return iterator(runs.cbegin(), quads.cbegin());
92    }
93
94    inline iterator end() const {
95        return iterator(runs.cend(), quads.cend());
96    }
97
98    bool contains(const codepoint_t codepoint) const;
99
100    void dump(llvm::raw_ostream & out) const;
101
102    UnicodeSet complement() const;
103    UnicodeSet operator & (const UnicodeSet & other) const;
104    UnicodeSet operator + (const UnicodeSet & other) const;
105    UnicodeSet operator - (const UnicodeSet & other) const;
106    UnicodeSet operator ^ (const UnicodeSet & other) const;
107
108    UnicodeSet();
109    UnicodeSet(const codepoint_t codepoint);
110    UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint);
111    UnicodeSet(std::initializer_list<RunStructure> r, std::initializer_list<bitquad_t> q) : runs(r), quads(q) {}
112
113protected:
114
115    class quad_iterator : public boost::iterator_facade<quad_iterator, std::pair<RunStructure, bitquad_t>, boost::random_access_traversal_tag> {
116        friend class UnicodeSet;
117        friend class boost::iterator_core_access;
118    public:
119        quad_iterator(const UnicodeSet & set, unsigned runIndex) : mUnicodeSet(set), mRunIndex(runIndex), mOffset(0), mQuadIndex(0) {}
120
121        void advance(unsigned n);
122
123        inline const std::pair<RunStructure, bitquad_t> dereference() const {
124            return std::make_pair(getRun(), getQuad());
125        }
126
127        inline void increment() {
128            advance(1);
129        }
130
131        inline RunStructure getRun() const {
132            const auto & t = mUnicodeSet.runs[mRunIndex];
133            return RunStructure(t.mType, t.mRunLength - mOffset);
134        }
135
136        inline bitquad_t getQuad() const {
137            return mUnicodeSet.quads[mQuadIndex];
138        }
139
140        inline bool equal(const quad_iterator & other) const {
141            assert (&(mUnicodeSet) == &(other.mUnicodeSet));
142            return (mRunIndex == other.mRunIndex);
143        }
144
145    private:
146        const UnicodeSet &          mUnicodeSet;
147        unsigned                    mRunIndex;
148        unsigned                    mOffset;
149        unsigned                    mQuadIndex;
150    };
151
152    inline quad_iterator quad_begin() const {
153        return quad_iterator(*this, 0);
154    }
155
156    inline quad_iterator quad_end() const {
157        return quad_iterator(*this, runs.size());
158    }
159
160    friend class UnicodeSet::quad_iterator;
161
162    // Internal helper functions
163    void append_run(const run_type_t type, const unsigned length);
164    void append_quad(const bitquad_t quad);
165
166private:
167
168    // The internal fields for a UnicodeSet.
169    std::vector<RunStructure>   runs;
170    std::vector<bitquad_t>      quads;
171   
172
173};
174
175inline UnicodeSet uset_complement(const UnicodeSet & s) {
176    return s.complement();
177}
178
179inline UnicodeSet uset_intersection(const UnicodeSet & s1, const UnicodeSet & s2) {
180    return s1 & s2;
181}
182
183inline UnicodeSet uset_union(const UnicodeSet & s1, const UnicodeSet & s2) {
184    return s1 + s2;
185}
186
187inline UnicodeSet uset_difference(const UnicodeSet & s1, const UnicodeSet & s2) {
188    return s1 - s2;
189}
190
191inline UnicodeSet uset_symmetric_difference(const UnicodeSet & s1, const UnicodeSet & s2) {
192    return s1 ^ s2;
193}
194
195#endif
196
Note: See TracBrowser for help on using the repository browser.