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

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

Bug fix for Grep Engine + better bug fix for UnicodeSet?

File size: 7.6 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
38typedef unsigned codepoint_t;
39enum : codepoint_t { UNICODE_MAX = 0x10FFFF };
40
41enum run_type_t : uint16_t {Empty, Mixed, Full};
42
43class UnicodeSet {
44public:
45
46    using bitquad_t = uint32_t;
47    using length_t = uint16_t;
48    using run_t = std::pair<run_type_t, length_t>;
49    using quad_iterator_return_t = std::pair<run_t, bitquad_t>;
50
51    using interval_t = std::pair<codepoint_t, codepoint_t>;
52
53    using RunVector = std::vector<run_t, ProxyAllocator<run_t>>;
54    using QuadVector = std::vector<bitquad_t, ProxyAllocator<bitquad_t>>;
55    using RunIterator = RunVector::const_iterator;
56    using QuadIterator = QuadVector::const_iterator;
57
58    using size_type = RunVector::size_type;
59
60    class iterator : public boost::iterator_facade<iterator, interval_t, boost::forward_traversal_tag, interval_t> {
61        friend class UnicodeSet;
62        friend class boost::iterator_core_access;
63    protected:
64
65        iterator(const RunVector::const_iterator runIterator, const QuadVector::const_iterator quadIterator, const codepoint_t baseCodePoint)
66        : mRunIterator(runIterator), mQuadIterator(quadIterator)
67        , mMixedRunIndex(0), mQuadOffset(0), mBaseCodePoint(baseCodePoint), mMinCodePoint(baseCodePoint), mMaxCodePoint(baseCodePoint) {
68
69        }
70
71        void advance(const unsigned n);
72
73        inline interval_t dereference() const {
74            return std::make_pair(mMinCodePoint, mMaxCodePoint);
75        }
76
77        inline void increment() {
78            advance(1);
79        }
80
81        inline bool equal(const iterator & other) const {
82            return (mMinCodePoint == other.mMinCodePoint);
83        }
84    private:
85        RunIterator         mRunIterator;
86        QuadIterator        mQuadIterator;
87        unsigned            mMixedRunIndex;
88        bitquad_t           mQuadOffset;
89        codepoint_t         mBaseCodePoint;
90        codepoint_t         mMinCodePoint;
91        codepoint_t         mMaxCodePoint;
92    };
93
94    inline iterator begin() const {
95        // note: preincrement forces the iterator to advance onto and capture the first interval.
96        return ++iterator(mRuns.cbegin(), mQuads.cbegin(), 0);
97    }
98
99    inline iterator end() const {
100        return iterator(mRuns.cend(), mQuads.cend(), UNICODE_MAX+1);
101    }
102
103    bool empty() const; // The set has no members
104   
105    bool full() const;  // The set has the full set of possible Unicode codepoints.
106   
107    codepoint_t at(const size_type k) const; // return the k-th codepoint (or throw an error if it doesn't exist)
108
109    bool contains(const codepoint_t codepoint) const;
110
111    bool intersects(const codepoint_t lo, const codepoint_t hi) const;
112   
113    bool intersects(const UnicodeSet & other) const;
114   
115    void insert(const codepoint_t cp);
116
117    void insert_range(const codepoint_t lo, const codepoint_t hi);
118
119    size_type size() const; // number of intervals in this set
120
121    size_type count() const; // number of codepoints in this set
122
123    interval_t front() const;
124
125    interval_t back() const;
126
127    void print(llvm::raw_ostream & out) const;
128
129    void dump(llvm::raw_ostream & out) const;
130
131    UnicodeSet operator~() const;
132    UnicodeSet operator&(const UnicodeSet & other) const;
133    UnicodeSet operator+(const UnicodeSet & other) const;
134    UnicodeSet operator-(const UnicodeSet & other) const;
135    UnicodeSet operator^(const UnicodeSet & other) const;
136
137    inline UnicodeSet & operator=(const UnicodeSet & other) = default;
138    inline UnicodeSet & operator=(UnicodeSet && other) = default;
139    bool operator==(const UnicodeSet & other) const;
140    bool operator<(const UnicodeSet & other) const;
141
142    UnicodeSet(run_type_t emptyOrFull = Empty);
143    UnicodeSet(const codepoint_t codepoint);
144    UnicodeSet(const codepoint_t lo, const codepoint_t hi);
145    UnicodeSet(const UnicodeSet & other);
146    UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q);
147    UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end);
148    UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end);
149   
150    inline void swap(UnicodeSet & other);
151    inline void swap(UnicodeSet && other);
152
153protected:
154
155    UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q);
156
157    class quad_iterator : public boost::iterator_facade<quad_iterator, quad_iterator_return_t, boost::random_access_traversal_tag, quad_iterator_return_t> {
158        friend class UnicodeSet;
159        friend class boost::iterator_core_access;
160    public:
161        quad_iterator(RunIterator runIterator, RunIterator runEnd, QuadIterator quadIterator, QuadIterator quadEnd, const run_type_t type, const length_t remaining)
162        : mRunIterator(runIterator)
163        , mRunEnd(runEnd)
164        , mQuadIterator(quadIterator)
165        #ifndef NDEBUG
166        , mQuadEnd(quadEnd)
167        #endif
168        , mType(type)
169        , mRemaining(remaining) {}
170
171        void advance(unsigned n);
172
173        inline quad_iterator_return_t dereference() const {
174            return std::make_pair(std::make_pair(type(), length()), quad());
175        }
176
177        inline void increment() {
178            advance(1);
179        }
180
181        inline run_type_t type() const {
182            return mType;
183        }
184
185        inline length_t length() const {
186            return mRemaining;
187        }
188
189        inline bitquad_t quad() const {
190            assert (mQuadIterator != mQuadEnd);
191            return *mQuadIterator;
192        }
193
194        inline bool equal(const quad_iterator & other) const {
195            const auto r = (mRunIterator == other.mRunIterator) && (mRemaining == other.mRemaining);
196            assert (!r || (mQuadIterator == other.mQuadIterator));
197            return r;
198        }
199
200    private:
201        RunIterator         mRunIterator;   
202        const RunIterator   mRunEnd;
203        QuadIterator        mQuadIterator;       
204        #ifndef NDEBUG
205        const QuadIterator  mQuadEnd;
206        #endif
207        run_type_t          mType;
208        length_t            mRemaining;
209    };
210
211    inline quad_iterator quad_begin() const {
212        return quad_iterator(mRuns.cbegin(), mRuns.cend(), mQuads.cbegin(), mQuads.cend(), std::get<0>(*mRuns.cbegin()), std::get<1>(*mRuns.cbegin()));
213    }
214
215    inline quad_iterator quad_end() const {
216        return quad_iterator(mRuns.cend(), mRuns.cend(), mQuads.cend(), mQuads.cend(), Empty, 0);
217    }
218
219private:
220
221    RunVector               mRuns;
222    QuadVector              mQuads;
223    static SlabAllocator<>  mAllocator;
224};
225
226
227inline void UnicodeSet::swap(UnicodeSet & other) {
228    mRuns.swap(other.mRuns); mQuads.swap(other.mQuads);
229}
230
231inline void UnicodeSet::swap(UnicodeSet && other) {
232    mRuns.swap(other.mRuns); mQuads.swap(other.mQuads);
233}
234
235}
236
237#endif
238
Note: See TracBrowser for help on using the repository browser.