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

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

Bug fix for CC insert_range and UnicodeSet? iterator.

File size: 6.1 KB
Line 
1#ifndef UNICODE_SET_H
2#define UNICODE_SET_H
3#include <stdint.h>
4#include <vector>
5#include <re/re_cc.h>
6#include <boost/iterator/iterator_facade.hpp>
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
47    using codepoint_t = re::codepoint_t;
48    using interval_t = re::interval_t;
49    using RunVector = std::vector<run_t>;
50    using QuadVector = std::vector<bitquad_t>;
51
52    class iterator : public boost::iterator_facade<iterator, interval_t, boost::forward_traversal_tag, interval_t> {
53        friend class UnicodeSet;
54        friend class boost::iterator_core_access;
55    protected:
56        iterator(RunVector::const_iterator runIterator, QuadVector::const_iterator quadIterator)
57        : mRunIterator(runIterator), mQuadIterator(quadIterator)
58        , mMixedRunIndex(0), mQuadOffset(0), mBaseCodePoint(0), mMinCodePoint(0), mMaxCodePoint(0)
59        {
60
61        }
62
63        void advance(const unsigned n);
64
65        re::interval_t dereference() const {
66            return std::make_pair(mMinCodePoint, mMaxCodePoint);
67        }
68
69        inline void increment() {
70            advance(1);
71        }
72
73        inline bool equal(iterator const & other) const {
74            return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator) &&
75                   (mMixedRunIndex == other.mMixedRunIndex) && (mQuadOffset == other.mQuadOffset);
76        }
77    private:
78        RunVector::const_iterator   mRunIterator;
79        QuadVector::const_iterator  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: pre-increment is intentional to move the iterator onto the first non-Empty interval.
89        return ++iterator(mRuns.cbegin(), mQuads.cbegin());
90    }
91
92    inline iterator end() const {
93        return iterator(mRuns.cend(), mQuads.cend());
94    }
95
96    class quad_iterator : public boost::iterator_facade<quad_iterator, std::pair<run_t, bitquad_t>, boost::random_access_traversal_tag> {
97        friend class UnicodeSet;
98        friend class boost::iterator_core_access;
99    public:
100        quad_iterator(RunVector::const_iterator runIterator, QuadVector::const_iterator quadIterator)
101            : mRunIterator(runIterator), mQuadIterator(quadIterator), mOffset(0) {}
102
103        void advance(unsigned n);
104
105        inline const std::pair<run_t, bitquad_t> dereference() const {
106            return std::make_pair(getRun(), getQuad());
107        }
108
109        inline void increment() {
110            advance(1);
111        }
112
113        inline run_t getRun() const {
114            const auto & t = *mRunIterator;
115            return std::make_pair(std::get<0>(t), std::get<1>(t) - mOffset);
116        }
117
118        inline bitquad_t getQuad() const {
119            return *mQuadIterator;
120        }
121
122        inline bool equal(const quad_iterator & other) const {
123            return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator);
124        }
125
126    private:
127        RunVector::const_iterator   mRunIterator;
128        QuadVector::const_iterator  mQuadIterator;
129        unsigned                    mOffset;
130    };
131
132    inline quad_iterator quad_begin() const {
133        return quad_iterator(mRuns.cbegin(), mQuads.cbegin());
134    }
135
136    inline quad_iterator quad_end() const {
137        return quad_iterator(mRuns.cend(), mQuads.cend());
138    }
139
140    bool contains(const codepoint_t codepoint) const;
141
142    void dump(llvm::raw_ostream & out) const;
143
144    UnicodeSet operator~() const;
145    UnicodeSet operator&(const UnicodeSet & other) const;
146    UnicodeSet operator+(const UnicodeSet & other) const;
147    UnicodeSet operator-(const UnicodeSet & other) const;
148    UnicodeSet operator^(const UnicodeSet & other) const;
149    UnicodeSet operator==(const UnicodeSet & other) const;
150
151    UnicodeSet();
152    UnicodeSet(const codepoint_t codepoint);
153    UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint);
154    UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q) : mRuns(r), mQuads(q) {}
155    UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q) : mRuns(r), mQuads(q) {}
156
157    inline void swap(UnicodeSet & other);
158    inline void swap(UnicodeSet && other);
159
160private:
161
162    std::vector<run_t>   mRuns;
163    std::vector<bitquad_t>      mQuads;
164};
165
166inline void UnicodeSet::swap(UnicodeSet & other) {
167    mRuns.swap(other.mRuns);
168    mQuads.swap(other.mQuads);
169}
170
171inline void UnicodeSet::swap(UnicodeSet && other) {
172    mRuns.swap(other.mRuns);
173    mQuads.swap(other.mQuads);
174}
175
176inline UnicodeSet uset_complement(const UnicodeSet & s) {
177    return ~s;
178}
179
180inline UnicodeSet uset_intersection(const UnicodeSet & s1, const UnicodeSet & s2) {
181    return s1 & s2;
182}
183
184inline UnicodeSet uset_union(const UnicodeSet & s1, const UnicodeSet & s2) {
185    return s1 + s2;
186}
187
188inline UnicodeSet uset_difference(const UnicodeSet & s1, const UnicodeSet & s2) {
189    return s1 - s2;
190}
191
192inline UnicodeSet uset_symmetric_difference(const UnicodeSet & s1, const UnicodeSet & s2) {
193    return s1 ^ s2;
194}
195
196}
197
198#endif
199
Note: See TracBrowser for help on using the repository browser.