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

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

Parse various UCD files and generate header files

File size: 9.3 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      if len(self.runs) >= entries_per_line: setrep += "\n" + (" " * (indent+1))
60      setrep += '{%s, %i}' % (runtype[self.runs[0][0]], self.runs[0][1])
61      for i in range(1, len(self.runs)):
62         setrep += ', '
63         if i % entries_per_line == 0: setrep += "\n" + (" " * (indent+1))
64         setrep += '{%s, %i}' % (runtype[self.runs[i][0]], self.runs[i][1])
65      setrep += '};\n'
66      setrep += (" " * indent) + ("%s.quads = {" % name)
67      if len(self.quads) >= entries_per_line: setrep += "\n" + (" " * (indent+1))
68      if self.quads != []:
69         setrep += "%#018x" % self.quads[0]
70         for i in range(1, len(self.quads)):
71            setrep += ', '
72            if i % entries_per_line == 0: setrep += "\n" + (" " * (indent+1))
73            setrep += "%#018x" % (self.quads[i])
74      setrep += '};\n'
75      return setrep   
76
77
78# helper
79def advance_run_list(r, n):
80   (runtype, runlength) = r[0]
81   if runlength > n: return  [(runtype, runlength - n)] + r[1:]
82   elif runlength == n: return r[1:]
83   else: return advance_run_list(r[1:], n - runlength)
84   
85
86#
87# Set Operations
88#
89def empty_set():
90   e = UCset()
91   e.runs = [(Empty, UnicodeQuadCount)]
92   e.quads = []
93   e.quad_count = UnicodeQuadCount
94   return e
95
96def singleton_set(codepoint):
97   e = UCset()
98   quad_no = codepoint >> 6
99   quad_val = 1 << (codepoint & 0x3F)
100   if quad_no > 0: e.append_run(Empty, quad_no)
101   e.append_run(Mixed, 1)
102   e.quads = [quad_val]
103   if quad_no < UnicodeQuadCount - 1: e.append_run(Empty, UnicodeQuadCount - (quad_no + 1))
104   e.quad_count = UnicodeQuadCount
105   return e
106
107def make_range_set(lo_codepoint, hi_codepoint):
108   e = UCset()
109   lo_quad_no = lo_codepoint >> 6   
110   hi_quad_no = hi_codepoint >> 6
111   lo_offset = lo_codepoint & 0x3F
112   hi_offset = hi_codepoint & 0x3F
113   if lo_quad_no > 0:  e.append_run(Empty, lo_quad_no)
114   if lo_quad_no == hi_quad_no:
115      quad = (FullQuad << lo_offset) & (FullQuad >> (63 - hi_offset))
116      e.append_quad(quad)
117   else:
118      e.append_quad((FullQuad << lo_offset) & FullQuad)
119      e.append_run(Full, hi_quad_no - (lo_quad_no + 1))
120      e.append_quad((FullQuad >> (63 - hi_offset)) & FullQuad)
121   if hi_quad_no < UnicodeQuadCount - 1: e.append_run(Empty, UnicodeQuadCount - (hi_quad_no + 1))
122   return e
123
124
125def complement (s):
126   assert s.quad_count == UnicodeQuadCount
127   iset = UCset()
128   R = s.runs
129   Q = s.quads
130   while R != []:
131      (runtype, n) = R[0]
132      if runtype == Empty:
133         iset.append_run(Full, n)
134      elif runtype == Full:
135         iset.append_run(Empty, n)
136      else: 
137         iset.append_mixed_run(n, [FullQuad ^ q for q in Q[0:n]])
138         Q = Q[n:]
139      R = advance_run_list(R, n)
140   return iset
141
142def intersect (s1, s2):
143   assert s1.quad_count == UnicodeQuadCount
144   assert s2.quad_count == UnicodeQuadCount
145   iset = UCset()
146   r1 = s1.runs
147   q1 = s1.quads
148   r2 = s2.runs
149   q2 = s2.quads
150   while r1 != []:
151      (s1_type, s1_length) = r1[0]
152      (s2_type, s2_length) = r2[0]
153      n = min(s1_length, s2_length)
154      if s1_type == Empty or s2_type == Empty:
155         iset.append_run(Empty, n)
156      elif s1_type == Full and s2_type == Full:
157         iset.append_run(Full, n)
158      elif s1_type == Full:
159         iset.append_mixed_run(n, q2[0:n])
160         q2 = q2[n:]
161      elif s2_type == Full:
162         iset.append_mixed_run(n, q1[0:n])
163         q1 = q1[n:]
164      else: # both s1 and s2 have mixed blocks; form block-by-block intersection
165         for i in range(n):
166           iset.append_quad(q1[i] & q2[i])
167         q1 = q1[n:]
168         q2 = q2[n:]
169      r1 = advance_run_list(r1, n)
170      r2 = advance_run_list(r2, n)
171   return iset
172
173def union (s1, s2):
174   assert s1.quad_count == UnicodeQuadCount
175   assert s2.quad_count == UnicodeQuadCount
176   iset = UCset()
177   r1 = s1.runs
178   q1 = s1.quads
179   r2 = s2.runs
180   q2 = s2.quads
181   while r1 != []:
182      (s1_type, s1_length) = r1[0]
183      (s2_type, s2_length) = r2[0]
184      n = min(s1_length, s2_length)
185      if s1_type == Empty and s2_type == Empty:
186         iset.append_run(Empty, n)
187      elif s1_type == Full or s2_type == Full:
188         iset.append_run(Full, n)
189      elif s1_type == Empty:
190         iset.append_mixed_run(n, q2[0:n])
191         q2 = q2[n:]
192      elif s2_type == Empty:
193         iset.append_mixed_run(n, q1[0:n])
194         q1 = q1[n:]
195      else: # both s1 and s2 have mixed blocks; form block-by-block union
196         for i in range(n):
197           iset.append_quad(q1[i] | q2[i])
198         q1 = q1[n:]
199         q2 = q2[n:]
200      r1 = advance_run_list(r1, n)
201      r2 = advance_run_list(r2, n)
202   return iset
203
204def difference (s1, s2):
205   assert s1.quad_count == UnicodeQuadCount
206   assert s2.quad_count == UnicodeQuadCount
207   iset = UCset()
208   r1 = s1.runs
209   q1 = s1.quads
210   r2 = s2.runs
211   q2 = s2.quads
212   while r1 != []:
213      (s1_type, s1_length) = r1[0]
214      (s2_type, s2_length) = r2[0]
215      n = min(s1_length, s2_length)
216      if s1_type == Empty or s2_type == Full:
217         iset.append_run(Empty, n)
218      elif s1_type == Full and s2_type == Empty:
219         iset.append_run(Full, n)
220      elif s2_type == Empty:
221         iset.append_mixed_run(n, q1[0:n])
222         q1 = q1[n:]
223      elif s1_type == Full:
224         iset.append_mixed_run(n, [FullQuad ^ q for q in q2[0:n]])
225         q2 = q2[n:]
226      else: # both s1 and s2 have mixed blocks; form block-by-block difference
227         for i in range(n):
228           iset.append_quad(q1[i] &~ q2[i])
229         q1 = q1[n:]
230         q2 = q2[n:]
231      r1 = advance_run_list(r1, n)
232      r2 = advance_run_list(r2, n)
233   return iset
234
235
236def symmetric_difference (s1, s2):
237   assert s1.quad_count == UnicodeQuadCount
238   assert s2.quad_count == UnicodeQuadCount
239   iset = UCset()
240   r1 = s1.runs
241   q1 = s1.quads
242   r2 = s2.runs
243   q2 = s2.quads
244   while r1 != []:
245      (s1_type, s1_length) = r1[0]
246      (s2_type, s2_length) = r2[0]
247      n = min(s1_length, s2_length)
248      if s1_type == Empty and s2_type == Full or s1_type == Full and s2_type == Empty:
249         iset.append_run(Full, n)
250      elif s1_type == Full and s2_type == Full or s1_type == Empty and s2_type == Empty:
251         iset.append_run(Empty, n)
252      elif s1_type == Empty:
253         iset.append_mixed_run(n, q2[0:n])
254         q2 = q2[n:]
255      elif s2_type == Empty:
256         iset.append_mixed_run(n, q1[0:n])
257         q1 = q1[n:]
258      elif s1_type == Full:
259         iset.append_mixed_run(n, [FullQuad ^ q for q in q2[0:n]])
260         q2 = q2[n:]
261      elif s2_type == Full:
262         iset.append_mixed_run(n, [FullQuad ^ q for q in q1[0:n]])
263         q1 = q1[n:]
264      else: # both s1 and s2 have mixed blocks; form block-by-block symmetric difference
265         for i in range(n):
266           iset.append_quad(q1[i] ^ q2[i])
267         q1 = q1[n:]
268         q2 = q2[n:]
269      r1 = advance_run_list(r1, n)
270      r2 = advance_run_list(r2, n)
271   return iset
272
273UCD_point_regexp = re.compile("^([0-9A-F]{4,6})\s+;")
274UCD_range_regexp = re.compile("^([0-9A-F]{4,6})[.][.]([0-9A-F]{4,6})\s+;")
275
276def parse_UCD_set(lines):
277    pset = empty_set()
278    for t in lines:
279        m = UCD_point_regexp.match(t)
280        if m:
281            point = m.group(1)
282            pval = int(point, 16)
283            pset = union(pset, singleton_set(pval))
284        m = UCD_range_regexp.match(t)
285        if m:
286            point1 = m.group(1)
287            point2 = m.group(2)
288            pval1 = int(point1, 16)
289            pval2 = int(point2, 16)
290            pset = union(pset, make_range_set(pval1, pval2))
291    return pset
292
293def parse_UCD_file(fname, vname):
294    f = open(fname)
295    lines = f.readlines()
296    f.close()
297    s = parse_UCD_set(lines)
298    print s.showC(vname)
299
300
301
302
Note: See TracBrowser for help on using the repository browser.