source: proto/charsetcompiler/UCD/unicode_set.py @ 4142

Last change on this file since 4142 was 4142, checked in by cameron, 5 years ago

parse UCsets from UCD format; print UCsets in C format

File size: 9.1 KB
Line 
1#
2# unicode_set.py - representing and manipulating sets of Unicode
3# characters, based on data from UCD - the Unicode Character Database
4#
5# Robert D. Cameron
6# September 8, 2014
7#
8# Licensed under Open Software License 3.0.
9import re
10
11#
12# Unicode Sparse Bitset Representation
13#
14# The Unicode Sparse Bitset representation is based on
15# (a) Dividing the Unicode codepoint space into groups of 64 codepoints called quads.
16# (b) Specifying the quads using a run-length encoding, in which each run
17#     is Empty (quads contain no members), Mixed (quads contain some members and
18#     some nonmembers) or Full (all codepoints in each quad are members of the set).
19# (c) Explicitly listing all the quads of Mixed type.
20#
21UnicodeQuadCount = 0x110000 >> 6 #  2**6 codepoints per quad
22
23Empty = 0
24Full = -1
25Mixed = 1
26
27FullQuad = (1<<64) - 1
28
29class UCset:
30   def __init__(self):
31      self.runs = []
32      self.quads = []
33      self.quad_count = 0
34   # internal methods
35   def append_run(self, runtype, runlength):
36      if runlength == 0: return
37      if self.runs == []:  self.runs = [(runtype, runlength)]
38      else:
39         (lastruntype, lastrunlength) = self.runs[-1]
40         if lastruntype == runtype:  self.runs[-1] = (runtype, lastrunlength + runlength)
41         else: self.runs.append((runtype, runlength))
42      self.quad_count += runlength
43   def append_mixed_run(self, n, quadlist):
44      self.append_run(Mixed, n)
45      self.quads += quadlist
46   def append_quad(self, q):
47      if q == 0:
48        self.append_run(Empty, 1)
49      elif q & FullQuad == FullQuad:
50        self.append_run(Full, 1)
51      else:
52        self.append_run(Mixed, 1)
53        self.quads.append(q)
54
55   # printing
56   def showC(self, name, indent = 8, entries_per_line = 4):
57      runtype = {-1:"Full", 0:"Empty", 1: "Mixed"}
58      setrep = (" " * indent) + ("%s.runs = {" % name)
59      setrep += '{%s, %i}' % (runtype[self.runs[0][0]], self.runs[0][1])
60      for i in range(1, len(self.runs)):
61         setrep += ', '
62         if i % entries_per_line == 0: setrep += "\n" + (" " * (indent+1))
63         setrep += '{%s, %i}' % (runtype[self.runs[i][0]], self.runs[i][1])
64      setrep += '};\n'
65      setrep += (" " * indent) + ("%s.quads = {" % name)
66      if self.quads != []:
67         setrep += "%#018x" % self.quads[0]
68         for i in range(1, len(self.quads)):
69            setrep += ', '
70            if i % entries_per_line == 0: setrep += "\n" + (" " * (indent+1))
71            setrep += "%#018x" % (self.quads[i])
72      setrep += '};\n'
73      return setrep   
74
75
76# helper
77def advance_run_list(r, n):
78   (runtype, runlength) = r[0]
79   if runlength > n: return  [(runtype, runlength - n)] + r[1:]
80   elif runlength == n: return r[1:]
81   else: return advance_run_list(r[1:], n - runlength)
82   
83
84#
85# Set Operations
86#
87def empty_set():
88   e = UCset()
89   e.runs = [(Empty, UnicodeQuadCount)]
90   e.quads = []
91   e.quad_count = UnicodeQuadCount
92   return e
93
94def singleton_set(codepoint):
95   e = UCset()
96   quad_no = codepoint >> 6
97   quad_val = 1 << (codepoint & 0x3F)
98   if quad_no > 0: e.append_run(Empty, quad_no)
99   e.append_run(Mixed, 1)
100   e.quads = [quad_val]
101   if quad_no < UnicodeQuadCount - 1: e.append_run(Empty, UnicodeQuadCount - (quad_no + 1))
102   e.quad_count = UnicodeQuadCount
103   return e
104
105def make_range_set(lo_codepoint, hi_codepoint):
106   e = UCset()
107   lo_quad_no = lo_codepoint >> 6   
108   hi_quad_no = hi_codepoint >> 6
109   lo_offset = lo_codepoint & 0x3F
110   hi_offset = hi_codepoint & 0x3F
111   if lo_quad_no > 0:  e.append_run(Empty, lo_quad_no)
112   if lo_quad_no == hi_quad_no:
113      quad = (FullQuad << lo_offset) & (FullQuad >> (63 - hi_offset))
114      e.append_quad(quad)
115   else:
116      e.append_quad((FullQuad << lo_offset) & FullQuad)
117      e.append_run(Full, hi_quad_no - (lo_quad_no + 1))
118      e.append_quad((FullQuad >> (63 - hi_offset)) & FullQuad)
119   if hi_quad_no < UnicodeQuadCount - 1: e.append_run(Empty, UnicodeQuadCount - (hi_quad_no + 1))
120   return e
121
122
123def complement (s):
124   assert s.quad_count == UnicodeQuadCount
125   iset = UCset()
126   R = s.runs
127   Q = s.quads
128   while R != []:
129      (runtype, n) = R[0]
130      if runtype == Empty:
131         iset.append_run(Full, n)
132      elif runtype == Full:
133         iset.append_run(Empty, n)
134      else: 
135         iset.append_mixed_run(n, [FullQuad ^ q for q in Q[0:n]])
136         Q = Q[n:]
137      R = advance_run_list(R, n)
138   return iset
139
140def intersect (s1, s2):
141   assert s1.quad_count == UnicodeQuadCount
142   assert s2.quad_count == UnicodeQuadCount
143   iset = UCset()
144   r1 = s1.runs
145   q1 = s1.quads
146   r2 = s2.runs
147   q2 = s2.quads
148   while r1 != []:
149      (s1_type, s1_length) = r1[0]
150      (s2_type, s2_length) = r2[0]
151      n = min(s1_length, s2_length)
152      if s1_type == Empty or s2_type == Empty:
153         iset.append_run(Empty, n)
154      elif s1_type == Full and s2_type == Full:
155         iset.append_run(Full, n)
156      elif s1_type == Full:
157         iset.append_mixed_run(n, q2[0:n])
158         q2 = q2[n:]
159      elif s2_type == Full:
160         iset.append_mixed_run(n, q1[0:n])
161         q1 = q1[n:]
162      else: # both s1 and s2 have mixed blocks; form block-by-block intersection
163         for i in range(n):
164           iset.append_quad(q1[i] & q2[i])
165         q1 = q1[n:]
166         q2 = q2[n:]
167      r1 = advance_run_list(r1, n)
168      r2 = advance_run_list(r2, n)
169   return iset
170
171def union (s1, s2):
172   assert s1.quad_count == UnicodeQuadCount
173   assert s2.quad_count == UnicodeQuadCount
174   iset = UCset()
175   r1 = s1.runs
176   q1 = s1.quads
177   r2 = s2.runs
178   q2 = s2.quads
179   while r1 != []:
180      (s1_type, s1_length) = r1[0]
181      (s2_type, s2_length) = r2[0]
182      n = min(s1_length, s2_length)
183      if s1_type == Empty and s2_type == Empty:
184         iset.append_run(Empty, n)
185      elif s1_type == Full or s2_type == Full:
186         iset.append_run(Full, n)
187      elif s1_type == Empty:
188         iset.append_mixed_run(n, q2[0:n])
189         q2 = q2[n:]
190      elif s2_type == Empty:
191         iset.append_mixed_run(n, q1[0:n])
192         q1 = q1[n:]
193      else: # both s1 and s2 have mixed blocks; form block-by-block union
194         for i in range(n):
195           iset.append_quad(q1[i] | q2[i])
196         q1 = q1[n:]
197         q2 = q2[n:]
198      r1 = advance_run_list(r1, n)
199      r2 = advance_run_list(r2, n)
200   return iset
201
202def difference (s1, s2):
203   assert s1.quad_count == UnicodeQuadCount
204   assert s2.quad_count == UnicodeQuadCount
205   iset = UCset()
206   r1 = s1.runs
207   q1 = s1.quads
208   r2 = s2.runs
209   q2 = s2.quads
210   while r1 != []:
211      (s1_type, s1_length) = r1[0]
212      (s2_type, s2_length) = r2[0]
213      n = min(s1_length, s2_length)
214      if s1_type == Empty or s2_type == Full:
215         iset.append_run(Empty, n)
216      elif s1_type == Full and s2_type == Empty:
217         iset.append_run(Full, n)
218      elif s2_type == Empty:
219         iset.append_mixed_run(n, q1[0:n])
220         q1 = q1[n:]
221      elif s1_type == Full:
222         iset.append_mixed_run(n, [FullQuad ^ q for q in q2[0:n]])
223         q2 = q2[n:]
224      else: # both s1 and s2 have mixed blocks; form block-by-block difference
225         for i in range(n):
226           iset.append_quad(q1[i] &~ q2[i])
227         q1 = q1[n:]
228         q2 = q2[n:]
229      r1 = advance_run_list(r1, n)
230      r2 = advance_run_list(r2, n)
231   return iset
232
233
234def symmetric_difference (s1, s2):
235   assert s1.quad_count == UnicodeQuadCount
236   assert s2.quad_count == UnicodeQuadCount
237   iset = UCset()
238   r1 = s1.runs
239   q1 = s1.quads
240   r2 = s2.runs
241   q2 = s2.quads
242   while r1 != []:
243      (s1_type, s1_length) = r1[0]
244      (s2_type, s2_length) = r2[0]
245      n = min(s1_length, s2_length)
246      if s1_type == Empty and s2_type == Full or s1_type == Full and s2_type == Empty:
247         iset.append_run(Full, n)
248      elif s1_type == Full and s2_type == Full or s1_type == Empty and s2_type == Empty:
249         iset.append_run(Empty, n)
250      elif s1_type == Empty:
251         iset.append_mixed_run(n, q2[0:n])
252         q2 = q2[n:]
253      elif s2_type == Empty:
254         iset.append_mixed_run(n, q1[0:n])
255         q1 = q1[n:]
256      elif s1_type == Full:
257         iset.append_mixed_run(n, [FullQuad ^ q for q in q2[0:n]])
258         q2 = q2[n:]
259      elif s2_type == Full:
260         iset.append_mixed_run(n, [FullQuad ^ q for q in q1[0:n]])
261         q1 = q1[n:]
262      else: # both s1 and s2 have mixed blocks; form block-by-block symmetric difference
263         for i in range(n):
264           iset.append_quad(q1[i] ^ q2[i])
265         q1 = q1[n:]
266         q2 = q2[n:]
267      r1 = advance_run_list(r1, n)
268      r2 = advance_run_list(r2, n)
269   return iset
270
271UCD_point_regexp = re.compile("^([0-9A-F]{4,6})\s+;")
272UCD_range_regexp = re.compile("^([0-9A-F]{4,6})[.][.]([0-9A-F]{4,6})\s+;")
273
274def parse_UCD_set(lines):
275    pset = empty_set()
276    for t in lines:
277        m = UCD_point_regexp.match(t)
278        if m:
279            point = m.group(1)
280            pval = int(point, 16)
281            pset = union(pset, singleton_set(pval))
282        m = UCD_range_regexp.match(t)
283        if m:
284            point1 = m.group(1)
285            point2 = m.group(2)
286            pval1 = int(point1, 16)
287            pval2 = int(point2, 16)
288            pset = union(pset, make_range_set(pval1, pval2))
289    return pset
290
291def parse_UCD_file(fname, vname):
292    f = open(fname)
293    lines = f.readlines()
294    f.close()
295    s = parse_UCD_set(lines)
296    print s.showC(vname)
297
298
299
300
Note: See TracBrowser for help on using the repository browser.