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

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

Embedded UnicodeSet? into CC objects (will currently cause memory leak)

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