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

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

Upload of an untested (inactive) UCD compiler.

File size: 5.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
32typedef uint32_t bitquad_t;
33
34// The representation for runs
35enum run_type_t : uint16_t {Empty, Mixed, Full};
36
37struct RunStructure {
38  RunStructure(run_type_t r, uint16_t lgth) : mType(r), mRunLength(lgth) {}
39  run_type_t mType;
40  uint16_t mRunLength;
41};
42
43class UnicodeSet;
44
45class UnicodeSet {
46public:
47
48    class quad_iterator : public boost::iterator_facade<quad_iterator, const std::pair<RunStructure, bitquad_t>, boost::forward_traversal_tag> {
49        friend class UnicodeSet;
50        friend class boost::iterator_core_access;
51    protected:
52        quad_iterator(const UnicodeSet & set, unsigned runIndex) : mUnicodeSet(set), mRunIndex(runIndex), mOffset(0), mQuadIndex(0) {}
53
54        void advance(unsigned n);
55
56        const std::pair<RunStructure, bitquad_t> dereference() const;
57
58        inline void increment() {
59            advance(1);
60        }
61
62        inline bool equal(quad_iterator const& other) const {
63            assert (&(mUnicodeSet) == &(other.mUnicodeSet));
64            return (mRunIndex == other.mRunIndex) && (mQuadIndex == other.mQuadIndex) && (mOffset == other.mOffset);
65        }
66    private:
67        const UnicodeSet &          mUnicodeSet;
68        unsigned                    mRunIndex;
69        unsigned                    mOffset;
70        unsigned                    mQuadIndex;
71    };
72
73    class iterator : public boost::iterator_facade<iterator, re::interval_t, boost::forward_traversal_tag, re::interval_t> {
74        friend class UnicodeSet;
75        friend class boost::iterator_core_access;
76    protected:
77        iterator(const UnicodeSet & set, unsigned runIndex, unsigned quadIndex)
78        : mUnicodeSet(set), mRunIndex(runIndex), mQuadIndex(quadIndex), mQuadOffset(0)
79        , mQuadRunIndex(0), mBaseCodePoint(0), mLeft(0), mRight(0)
80        {
81
82        }
83
84        void advance(unsigned n);
85
86        re::interval_t dereference() const {
87            return std::make_pair(mLeft, mRight);
88        }
89
90        inline void increment() {
91            advance(1);
92        }
93
94        inline bool equal(iterator const & other) const {
95            assert (&(mUnicodeSet) == &(other.mUnicodeSet));
96            return (mRunIndex == other.mRunIndex) && (mQuadIndex == other.mQuadIndex) &&
97                   (mQuadOffset == other.mQuadOffset) && (mQuadRunIndex == other.mQuadRunIndex);
98        }
99    private:
100        const UnicodeSet &      mUnicodeSet;
101        unsigned                mRunIndex;
102        unsigned                mQuadIndex;
103        bitquad_t               mQuadOffset;
104        unsigned                mQuadRunIndex;
105        unsigned                mBaseCodePoint;
106        re::codepoint_t         mLeft;
107        re::codepoint_t         mRight;
108    };
109
110    inline quad_iterator quad_begin() const {
111        return quad_iterator(*this, 0);
112    }
113
114    inline quad_iterator quad_end() const {
115        return quad_iterator(*this, runs.size());
116    }
117
118    inline iterator begin() const {
119        return iterator(*this, 0,0);
120    }
121
122    inline iterator end() const {
123        return iterator(*this, runs.size(), quads.size());
124    }
125
126//
127//  The internal fields for a UnicodeSet.
128    std::vector<RunStructure>   runs;
129    std::vector<bitquad_t>      quads;
130    unsigned quad_count;
131   
132// 
133//  Internal helper functions
134    void append_run(run_type_t run_type, int run_length);
135    void append_quad(bitquad_t q);
136//
137//  Nullary constructor for incremental building.
138    UnicodeSet() : quad_count(0) {}
139//
140//  Ternary constructor for constant construction using precomputed data.
141    UnicodeSet(std::initializer_list<RunStructure> r, std::initializer_list<bitquad_t> q, unsigned c) : runs(r), quads(q), quad_count(c) {}
142};
143
144void Dump_uset(UnicodeSet s);
145UnicodeSet empty_uset();
146UnicodeSet singleton_uset(int codepoint);
147UnicodeSet range_uset(int lo_codepoint, int hi_codepoint);
148UnicodeSet uset_complement (const UnicodeSet &s);
149UnicodeSet uset_union(const UnicodeSet & s1, const UnicodeSet & s2);
150UnicodeSet uset_intersection(const UnicodeSet &s1, const UnicodeSet &s2);
151UnicodeSet uset_difference(const UnicodeSet &s1, const UnicodeSet &s2);
152UnicodeSet uset_symmetric_difference(const UnicodeSet & s1, const UnicodeSet & s2);
153bool uset_member(const UnicodeSet & s, int codepoint);
154
155#endif
156
Note: See TracBrowser for help on using the repository browser.