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

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

Back up check in. Memory leaks should be fixed.

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