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

Last change on this file since 5232 was 5037, checked in by nmedfort, 3 years ago

UnicodeSet? bug fix and compile warning clean-up.

File size: 6.7 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#include <util/slab_allocator.h>
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
36namespace UCD {
37
38enum run_type_t : uint16_t {Empty, Mixed, Full};
39
40class UnicodeSet {
41public:
42
43    using bitquad_t = uint32_t;
44    using length_t = uint16_t;
45    using run_t = std::pair<run_type_t, length_t>;
46    using quad_iterator_return_t = std::pair<run_t, bitquad_t>;
47
48    using codepoint_t = unsigned;
49    using interval_t = std::pair<codepoint_t, codepoint_t>;
50
51    using RunAllocator = SlabAllocator<run_t>;
52    using QuadAllocator = SlabAllocator<bitquad_t>;
53
54    using RunVector = std::vector<run_t, RunAllocator>;
55    using QuadVector = std::vector<bitquad_t, QuadAllocator>;
56    using RunIterator = RunVector::const_iterator;
57    using QuadIterator = QuadVector::const_iterator;
58
59    using size_type = RunVector::size_type;
60
61    class iterator : public boost::iterator_facade<iterator, interval_t, boost::forward_traversal_tag, interval_t> {
62        friend class UnicodeSet;
63        friend class boost::iterator_core_access;
64    protected:
65
66        iterator(const RunVector::const_iterator runIterator, const QuadVector::const_iterator quadIterator, const codepoint_t baseCodePoint)
67        : mRunIterator(runIterator), mQuadIterator(quadIterator)
68        , mMixedRunIndex(0), mQuadOffset(0), mBaseCodePoint(baseCodePoint), mMinCodePoint(baseCodePoint), mMaxCodePoint(baseCodePoint) {
69
70        }
71
72        void advance(const unsigned n);
73
74        inline interval_t dereference() const {
75            return std::make_pair(mMinCodePoint, mMaxCodePoint);
76        }
77
78        inline void increment() {
79            advance(1);
80        }
81
82        inline bool equal(const iterator & other) const {
83            return (mMinCodePoint == other.mMinCodePoint);
84        }
85    private:
86        RunIterator         mRunIterator;
87        QuadIterator        mQuadIterator;
88        unsigned            mMixedRunIndex;
89        bitquad_t           mQuadOffset;
90        codepoint_t         mBaseCodePoint;
91        codepoint_t         mMinCodePoint;
92        codepoint_t         mMaxCodePoint;
93    };
94
95    inline iterator begin() const {
96        // note: preincrement forces the iterator to advance onto and capture the first interval.
97        return ++iterator(mRuns.cbegin(), mQuads.cbegin(), 0);
98    }
99
100    inline iterator end() const {
101        return iterator(mRuns.cend(), mQuads.cend(), 0x110000);
102    }
103
104    bool contains(const codepoint_t codepoint) const;
105
106    bool intersects(const codepoint_t lo, const codepoint_t hi) const;
107
108    void insert(const codepoint_t cp);
109
110    void insert_range(const codepoint_t lo, const codepoint_t hi);
111
112    bool empty() const;
113
114    size_type size() const;
115
116    interval_t front() const;
117
118    interval_t back() const;
119
120    void dump(llvm::raw_ostream & out) const;
121
122    UnicodeSet operator~() const;
123    UnicodeSet operator&(const UnicodeSet & other) const;
124    UnicodeSet operator+(const UnicodeSet & other) const;
125    UnicodeSet operator-(const UnicodeSet & other) const;
126    UnicodeSet operator^(const UnicodeSet & other) const;
127
128    inline UnicodeSet & operator=(const UnicodeSet & other) = default;
129    inline UnicodeSet & operator=(UnicodeSet && other) = default;
130    bool operator==(const UnicodeSet & other) const;
131    bool operator<(const UnicodeSet & other) const;
132
133    UnicodeSet();
134    UnicodeSet(const codepoint_t codepoint);
135    UnicodeSet(const codepoint_t lo, const codepoint_t hi);
136    UnicodeSet(const UnicodeSet & other);
137    UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q);
138    UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end);
139    UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end);
140
141    inline void swap(UnicodeSet & other);
142    inline void swap(UnicodeSet && other);
143
144protected:
145
146    UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q);
147
148    class quad_iterator : public boost::iterator_facade<quad_iterator, quad_iterator_return_t, boost::random_access_traversal_tag, quad_iterator_return_t> {
149        friend class UnicodeSet;
150        friend class boost::iterator_core_access;
151    public:
152        quad_iterator(RunIterator runIterator, QuadIterator quadIterator)
153            : mRunIterator(runIterator), mQuadIterator(quadIterator), mOffset(0) {}
154
155        void advance(unsigned n);
156
157        inline quad_iterator_return_t dereference() const {
158            return std::make_pair(std::make_pair(type(), length()), quad());
159        }
160
161        inline void increment() {
162            advance(1);
163        }
164
165        inline run_type_t type() const {
166            return mRunIterator->first;
167        }
168
169        inline length_t length() const {
170            return mRunIterator->second - mOffset;
171        }
172
173        inline bitquad_t quad() const {
174            return *mQuadIterator;
175        }
176
177        inline bool equal(const quad_iterator & other) const {
178            return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator);
179        }
180
181    private:
182        RunIterator     mRunIterator;
183        QuadIterator    mQuadIterator;
184        unsigned        mOffset;
185    };
186
187    inline quad_iterator quad_begin() const {
188        return quad_iterator(mRuns.cbegin(), mQuads.cbegin());
189    }
190
191    inline quad_iterator quad_end() const {
192        return quad_iterator(mRuns.cend(), mQuads.cend());
193    }
194
195private:
196
197    RunVector               mRuns;
198    QuadVector              mQuads;
199    static RunAllocator     mRunAllocator;
200    static QuadAllocator    mQuadAllocator;
201};
202
203enum : UnicodeSet::codepoint_t { UNICODE_MAX = 0x10FFFF };
204
205inline void UnicodeSet::swap(UnicodeSet & other) {
206    mRuns.swap(other.mRuns); mQuads.swap(other.mQuads);
207}
208
209inline void UnicodeSet::swap(UnicodeSet && other) {
210    mRuns.swap(other.mRuns); mQuads.swap(other.mQuads);
211}
212
213}
214
215#endif
216
Note: See TracBrowser for help on using the repository browser.