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

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

Parameterize on quad size

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