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

Last change on this file since 5765 was 5759, checked in by cameron, 20 months ago

Small fixes

File size: 8.2 KB
Line 
1#ifndef UNICODE_SET_H
2#define UNICODE_SET_H
3
4#include "UCD_Config.h"
5#include <stdint.h>
6#include <vector>
7#include <boost/iterator/iterator_facade.hpp>
8#include <util/slab_allocator.h>
9
10//
11// unicode_set.h - representing and manipulating sets of Unicode
12// characters, based on data from UCD - the Unicode Character Database
13//
14// Robert D. Cameron
15// September 18, 2014
16//
17// Licensed under Open Software License 3.0.
18//
19// Unicode Sparse Bitset Representation
20//
21// The Unicode Sparse Bitset representation is based on
22// (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
23// (b) Specifying the quads using a run-length encoding, in which each run
24//     is Empty (quads contain no members), Mixed (quads contain some members and
25//     some nonmembers) or Full (all codepoints in each quad are members of the set).
26// (c) Explicitly listing all the quads of Mixed type.
27//
28
29//
30// The internal datatype for quads - bitsets of 2^k codepoints.
31// Default: 64 codepoints (k=6).
32//
33
34namespace llvm { class raw_ostream; }
35namespace re { class RE; }
36
37namespace UCD {
38
39enum run_type_t : uint16_t {Empty, Mixed, Full};
40
41class UnicodeSet {
42    friend class re::RE;
43    template<typename RunVector, typename QuadVector> friend void assign(UnicodeSet *, const RunVector &, const QuadVector &) noexcept;
44public:
45
46    using bitquad_t = uint32_t;
47    using length_t = uint16_t;
48    using size_type = size_t;
49
50    using run_t = std::pair<run_type_t, length_t>;
51    using quad_iterator_return_t = std::pair<run_t, bitquad_t>;
52
53    class iterator : public boost::iterator_facade<iterator, interval_t, boost::forward_traversal_tag, interval_t> {
54        friend class UnicodeSet;
55        friend class boost::iterator_core_access;
56    protected:
57
58        iterator(const run_t * const runIterator, const bitquad_t * const quadIterator, const codepoint_t baseCodePoint)
59        : mRunIterator(runIterator), mQuadIterator(quadIterator)
60        , mMixedRunIndex(0), mQuadOffset(0), mBaseCodePoint(baseCodePoint), mMinCodePoint(baseCodePoint), mMaxCodePoint(baseCodePoint) {
61
62        }
63
64        void advance(const unsigned n);
65
66        inline interval_t dereference() const {
67            return std::make_pair(mMinCodePoint, mMaxCodePoint);
68        }
69
70        inline void increment() {
71            advance(1);
72        }
73
74        inline bool equal(const iterator & other) const {
75            return (mMinCodePoint == other.mMinCodePoint);
76        }
77    private:
78        const run_t *       mRunIterator;
79        const bitquad_t *   mQuadIterator;
80        unsigned            mMixedRunIndex;
81        bitquad_t           mQuadOffset;
82        codepoint_t         mBaseCodePoint;
83        codepoint_t         mMinCodePoint;
84        codepoint_t         mMaxCodePoint;
85    };
86
87    inline iterator begin() const {
88        // note: preincrement forces the iterator to advance onto and capture the first interval.
89        return ++iterator(mRuns, mQuads, 0);
90    }
91
92    inline iterator end() const {
93        return iterator(mRuns, mQuads, UNICODE_MAX+1);
94    }
95
96    bool empty() const { // The set has no members
97        return (mRunLength == 1) && mRuns->first == Empty;
98    }
99
100    bool full() const {  // The set has the full set of possible Unicode codepoints.
101        return (mRunLength == 1) && mRuns->first == Full;
102    }
103   
104    codepoint_t at(const size_type k) const; // return the k-th codepoint (or throw an error if it doesn't exist)
105
106    bool contains(const codepoint_t codepoint) const noexcept;
107
108    bool intersects(const codepoint_t lo, const codepoint_t hi) const noexcept;
109   
110    bool intersects(const UnicodeSet & other) const noexcept;
111
112    bool subset(const UnicodeSet & other) const noexcept;
113   
114    void insert(const codepoint_t cp);
115
116    void insert(const UnicodeSet & other) noexcept;
117
118    void invert() noexcept;
119
120    void insert_range(const codepoint_t lo, const codepoint_t hi);
121
122    size_type size() const noexcept; // number of intervals in this set
123
124    size_type count() const noexcept; // number of codepoints in this set
125
126    interval_t front() const noexcept;
127
128    interval_t back() const noexcept;
129
130    void print(llvm::raw_ostream & out) const noexcept;
131
132    void dump(llvm::raw_ostream & out) const noexcept;
133
134    UnicodeSet operator~() const noexcept;
135    UnicodeSet operator&(const UnicodeSet & other) const noexcept;
136    UnicodeSet operator+(const UnicodeSet & other) const noexcept;
137    UnicodeSet operator-(const UnicodeSet & other) const noexcept;
138    UnicodeSet operator^(const UnicodeSet & other) const noexcept;
139
140    UnicodeSet & operator=(const UnicodeSet & other) noexcept;
141    UnicodeSet & operator=(const UnicodeSet && other) noexcept;
142    bool operator==(const UnicodeSet & other) const noexcept;
143    bool operator<(const UnicodeSet & other) const noexcept;
144
145    UnicodeSet() noexcept;
146    UnicodeSet(const codepoint_t codepoint) noexcept;
147    UnicodeSet(const codepoint_t lo, const codepoint_t hi) noexcept;
148    UnicodeSet(const UnicodeSet & other) noexcept;
149    UnicodeSet(const UnicodeSet && other) noexcept;
150
151    UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end) noexcept;
152    UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end) noexcept;
153    UnicodeSet(run_t * const runs, const uint32_t runLength, const uint32_t runCapacity, bitquad_t * const quads, const uint32_t quadLength, const uint32_t quadCapacity) noexcept;
154
155    UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q) noexcept;
156
157    inline static void Reset() {
158        GlobalAllocator.Reset();
159    }
160
161protected:
162
163    class quad_iterator : public boost::iterator_facade<quad_iterator, quad_iterator_return_t, boost::random_access_traversal_tag, quad_iterator_return_t> {
164        friend class UnicodeSet;
165        friend class boost::iterator_core_access;
166    public:
167        explicit quad_iterator(const run_t * const runIterator, const run_t * const runEnd, const bitquad_t * const quadIterator, const bitquad_t * const quadEnd, const run_type_t type, const length_t remaining)
168        : mRunIterator(runIterator)
169        , mRunEnd(runEnd)
170        , mQuadIterator(quadIterator)
171        #ifndef NDEBUG
172        , mQuadEnd(quadEnd)
173        #endif
174        , mType(type)
175        , mRemaining(remaining) {
176            assert (type == Empty || type == Mixed || type == Full);
177            assert (remaining > 0 || type == Empty);
178            assert (remaining <= ((UNICODE_MAX+1) / (sizeof(bitquad_t) * 8)));
179        }
180
181        void advance(unsigned n);
182
183        inline quad_iterator_return_t dereference() const {
184            return std::make_pair(std::make_pair(type(), length()), quad());
185        }
186
187        inline void increment() {
188            advance(1);
189        }
190
191        inline run_type_t type() const {
192            return mType;
193        }
194
195        inline length_t length() const {
196            return mRemaining;
197        }
198
199        inline bitquad_t quad() const {
200            assert (mQuadIterator != mQuadEnd);
201            return *mQuadIterator;
202        }
203
204        inline bool equal(const quad_iterator & other) const {
205            const auto r = (mRunIterator == other.mRunIterator) && (mRemaining == other.mRemaining);
206            assert (!r || (mQuadIterator == other.mQuadIterator));
207            return r;
208        }
209
210    private:
211        const run_t *           mRunIterator;
212        const run_t * const     mRunEnd;
213        const bitquad_t *       mQuadIterator;
214        #ifndef NDEBUG
215        const bitquad_t * const mQuadEnd;
216        #endif
217        run_type_t              mType;
218        length_t                mRemaining;
219    };
220
221    inline quad_iterator quad_begin() const {
222        return quad_iterator(mRuns, mRuns + mRunLength, mQuads, mQuads + mQuadLength, std::get<0>(*mRuns), std::get<1>(*mRuns));
223    }
224
225    inline quad_iterator quad_end() const {       
226        return quad_iterator(mRuns + mRunLength, mRuns + mRunLength, mQuads + mQuadLength, mQuads + mQuadLength, Empty, 0);
227    }
228
229private:
230
231    run_t *                 mRuns;
232    bitquad_t *             mQuads;
233
234    uint32_t                mRunLength;
235    uint32_t                mQuadLength;
236
237    uint32_t                mRunCapacity;
238    uint32_t                mQuadCapacity;
239
240    static SlabAllocator<>  GlobalAllocator;
241};
242
243}
244
245#endif
246
Note: See TracBrowser for help on using the repository browser.