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

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

Restructing.

File size: 11.4 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, cformat
10#
11# Unicode Sparse Bitset Representation
12#
13# The Unicode Sparse Bitset representation is based on
14# (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
15# (b) Specifying the quads using a run-length encoding, in which each run
16#     is Empty (quads contain no members), Mixed (quads contain some members and
17#     some nonmembers) or Full (all codepoints in each quad are members of the set).
18# (c) Explicitly listing all the quads of Mixed type.
19#
20
21Empty = 0
22Full = -1
23Mixed = 1
24
25default_log2_quad_bits = 5
26
27log2_quad_bits = default_log2_quad_bits
28quad_bits = 1 << log2_quad_bits
29mod_quad_bit_mask = quad_bits - 1
30UnicodeQuadCount = 0x110000 / quad_bits #  2**log2_quad_bits codepoints per quad
31FullQuadMask = (1<<(quad_bits)) - 1
32run_bytes = 2
33
34
35class UCset:
36   def __init__(self):
37      self.runs = []
38      self.quads = []
39      self.quad_count = 0
40     
41   # internal methods
42   def append_run(self, runtype, runlength):
43      if runlength == 0: return
44      if self.runs == []:  self.runs = [(runtype, runlength)]
45      else:
46         (lastruntype, lastrunlength) = self.runs[-1]
47         if lastruntype == runtype:  self.runs[-1] = (runtype, lastrunlength + runlength)
48         else: self.runs.append((runtype, runlength))
49      self.quad_count += runlength
50   def append_mixed_run(self, n, quadlist):
51      self.append_run(Mixed, n)
52      self.quads += quadlist
53   def append_quad(self, q):
54      if q == 0:
55        self.append_run(Empty, 1)
56      elif q & FullQuadMask == FullQuadMask:
57        self.append_run(Full, 1)
58      else:
59        self.append_run(Mixed, 1)
60        self.quads.append(q)
61
62   # printing
63   def showC(self, indent = 4):
64      hex_specifier =  "%%#0%ix" % (quad_bits/4 + 2)
65      runtype = {-1:"Full", 0:"Empty", 1: "Mixed"}
66      formatted_runs = ['{%s, %i}' % (runtype[r[0]], r[1]) for r in self.runs]
67      formatted_quads = [hex_specifier % q for q in self.quads]
68      setrep = (" " * indent) + "{{"
69      setrep += cformat.multiline_fill(formatted_runs, ',', indent+2)
70      setrep += '},\n'
71      setrep += (" " * indent) + " {"
72      setrep += cformat.multiline_fill(formatted_quads, ',', indent+2)
73      setrep += '},\n'
74      setrep += (" " * indent) + " %i}" % self.quad_count
75      return setrep
76
77   def bytes(self):
78       return (len(self.runs) * run_bytes) + (len(self.quads) * quad_bits/8)
79
80
81#
82# Set Operations
83#
84def empty_uset():
85   e = UCset()
86   e.runs = [(Empty, UnicodeQuadCount)]
87   e.quads = []
88   e.quad_count = UnicodeQuadCount
89   return e
90
91def singleton_uset(codepoint):
92   e = UCset()
93   quad_no = codepoint >> log2_quad_bits
94   quad_val = 1 << (codepoint & mod_quad_bit_mask)
95   if quad_no > 0: e.append_run(Empty, quad_no)
96   e.append_run(Mixed, 1)
97   e.quads = [quad_val]
98   if quad_no < UnicodeQuadCount - 1: e.append_run(Empty, UnicodeQuadCount - (quad_no + 1))
99   e.quad_count = UnicodeQuadCount
100   return e
101
102def range_uset(lo_codepoint, hi_codepoint):
103   e = UCset()
104   lo_quad_no = lo_codepoint >> log2_quad_bits   
105   hi_quad_no = hi_codepoint >> log2_quad_bits
106   lo_offset = lo_codepoint & mod_quad_bit_mask
107   hi_offset = hi_codepoint & mod_quad_bit_mask
108   if lo_quad_no > 0:  e.append_run(Empty, lo_quad_no)
109   if lo_quad_no == hi_quad_no:
110      quad = (FullQuadMask << lo_offset) & (FullQuadMask >> (quad_bits - 1 - hi_offset))
111      e.append_quad(quad)
112   else:
113      e.append_quad((FullQuadMask << lo_offset) & FullQuadMask)
114      e.append_run(Full, hi_quad_no - (lo_quad_no + 1))
115      e.append_quad((FullQuadMask >> (quad_bits - 1 - hi_offset)) & FullQuadMask)
116   if hi_quad_no < UnicodeQuadCount - 1: e.append_run(Empty, UnicodeQuadCount - (hi_quad_no + 1))
117   return e
118
119
120class Uset_Iterator:
121    def __init__(self, uSet):
122        self.uSet = uSet
123        self.run_no = 0
124        self.offset = 0
125        self.quad_no = 0
126    def at_end(self):
127        return self.run_no == len(self.uSet.runs)
128    def current_run(self):
129        (this_run_type, this_run_length) = self.uSet.runs[self.run_no]
130        return (this_run_type, this_run_length - self.offset)
131    def get_quad(self):
132        (this_run_type, this_run_length) = self.uSet.runs[self.run_no]
133        if this_run_type == Empty: return 0
134        elif this_run_type == Full: return self.uSet.FullQuadMask
135        else: return self.uSet.quads[self.quad_no]
136    def advance(self, n):
137        while n > 0:
138           (this_run_type, this_run_length) = self.uSet.runs[self.run_no]
139           remain = this_run_length - self.offset
140           if remain > n:
141               self.offset += n
142               if this_run_type == Mixed: self.quad_no += n
143               n = 0
144           elif remain == n:
145               self.run_no += 1
146               self.offset = 0
147               if this_run_type == Mixed: self.quad_no += n
148               n = 0
149           else:
150               self.run_no += 1
151               self.offset = 0
152               if this_run_type == Mixed: self.quad_no += remain
153               n -= remain
154
155
156def uset_member(s, codepoint):
157   quad_no = codepoint / quad_bits
158   quad_val = 1 << (codepoint & mod_quad_bit_mask)
159   it = Uset_Iterator(s)   
160   it.advance(quad_no)
161   return (it.get_quad() & quad_val) != 0
162 
163def uset_complement (s):
164   assert s.quad_count == UnicodeQuadCount
165   iset = UCset()
166   it = Uset_Iterator(s)
167   while not it.at_end():
168      (runtype, n) = it.current_run()
169      if runtype == Empty:
170         iset.append_run(Full, n)
171         it.advance(n)
172      elif runtype == Full:
173         iset.append_run(Empty, n)
174         it.advance(n)
175      else: 
176         for i in range(n):
177            iset.append_quad(s.FullQuadMask ^ it.get_quad())
178            it.advance(1)
179   return iset
180
181
182def uset_intersection (s1, s2):
183   assert s1.quad_count == UnicodeQuadCount
184   assert s2.quad_count == UnicodeQuadCount
185   iset = UCset()
186   i1 = Uset_Iterator(s1)
187   i2 = Uset_Iterator(s2)
188   while not i1.at_end():
189      (s1_type, s1_length) = i1.current_run()
190      (s2_type, s2_length) = i2.current_run()
191      n = min(s1_length, s2_length)
192      if s1_type == Empty or s2_type == Empty:
193         iset.append_run(Empty, n)
194         i1.advance(n)
195         i2.advance(n)
196      elif s1_type == Full and s2_type == Full:
197         iset.append_run(Full, n)
198         i1.advance(n)
199         i2.advance(n)
200      elif s1_type == Full:
201         for i in range(n):
202            iset.append_quad(i2.get_quad())
203            i2.advance(1)
204         i1.advance(n)
205      elif s2_type == Full:
206         for i in range(n):
207            iset.append_quad(i1.get_quad())
208            i1.advance(1)
209         i2.advance(n)
210      else: # both s1 and s2 have mixed blocks; form block-by-block intersection
211         for i in range(n):
212            iset.append_quad(i1.get_quad() & i2.get_quad())
213            i1.advance(1)
214            i2.advance(1)
215   return iset
216
217def uset_union (s1, s2):
218   assert s1.quad_count == UnicodeQuadCount
219   assert s2.quad_count == UnicodeQuadCount
220   iset = UCset()
221   i1 = Uset_Iterator(s1)
222   i2 = Uset_Iterator(s2)
223   while not i1.at_end():
224      (s1_type, s1_length) = i1.current_run()
225      (s2_type, s2_length) = i2.current_run()
226      n = min(s1_length, s2_length)
227      if s1_type == Empty and s2_type == Empty:
228         iset.append_run(Empty, n)
229         i1.advance(n)
230         i2.advance(n)
231      elif s1_type == Full or s2_type == Full:
232         iset.append_run(Full, n)
233         i1.advance(n)
234         i2.advance(n)
235      elif s1_type == Empty:
236         for i in range(n):
237            iset.append_quad(i2.get_quad())
238            i2.advance(1)
239         i1.advance(n)
240      elif s2_type == Empty:
241         for i in range(n):
242            iset.append_quad(i1.get_quad())
243            i1.advance(1)
244         i2.advance(n)
245      else: # both s1 and s2 have mixed blocks; form block-by-block union
246         for i in range(n):
247            iset.append_quad(i1.get_quad() | i2.get_quad())
248            i1.advance(1)
249            i2.advance(1)
250   return iset
251
252def uset_difference (s1, s2):
253   assert s1.quad_count == UnicodeQuadCount
254   assert s2.quad_count == UnicodeQuadCount
255   iset = UCset()
256   i1 = Uset_Iterator(s1)
257   i2 = Uset_Iterator(s2)
258   while not i1.at_end():
259      (s1_type, s1_length) = i1.current_run()
260      (s2_type, s2_length) = i2.current_run()
261      n = min(s1_length, s2_length)
262      if s1_type == Empty or s2_type == Full:
263         iset.append_run(Empty, n)
264         i1.advance(n)
265         i2.advance(n)
266      elif s1_type == Full and s2_type == Empty:
267         iset.append_run(Full, n)
268         i1.advance(n)
269         i2.advance(n)
270      elif s1_type == Full:
271         for i in range(n):
272            iset.append_quad(iset.FullQuadMask ^ i2.get_quad())
273            i2.advance(1)
274         i1.advance(n)
275      elif s2_type == Empty:
276         for i in range(n):
277            iset.append_quad(i1.get_quad())
278            i1.advance(1)
279         i2.advance(n)
280      else: # both s1 and s2 have mixed blocks; form block-by-block union
281         for i in range(n):
282            iset.append_quad(i1.get_quad() &~ i2.get_quad())
283            i1.advance(1)
284            i2.advance(1)
285   return iset
286
287def uset_symmetric_difference (s1, s2):
288   assert s1.quad_count == UnicodeQuadCount
289   assert s2.quad_count == UnicodeQuadCount
290   iset = UCset()
291   i1 = Uset_Iterator(s1)
292   i2 = Uset_Iterator(s2)
293   while not i1.at_end():
294      (s1_type, s1_length) = i1.current_run()
295      (s2_type, s2_length) = i2.current_run()
296      n = min(s1_length, s2_length)
297      if s1_type == Empty and s2_type == Full or s1_type == Full and s2_type == Empty:
298         iset.append_run(Full, n)
299         i1.advance(n)
300         i2.advance(n)
301      elif s1_type == Full and s2_type == Full or s1_type == Empty and s2_type == Empty:
302         iset.append_run(Empty, n)
303         i1.advance(n)
304         i2.advance(n)
305      elif s1_type == Empty:
306         for i in range(n):
307            iset.append_quad(i2.get_quad())
308            i2.advance(1)
309         i1.advance(n)
310      elif s2_type == Empty:
311         for i in range(n):
312            iset.append_quad(i1.get_quad())
313            i1.advance(1)
314         i2.advance(n)
315      elif s1_type == Full:
316         for i in range(n):
317            iset.append_quad(iset.FullQuadMask ^ i2.get_quad())
318            i2.advance(1)
319         i1.advance(n)
320      elif s2_type == Full:
321         for i in range(n):
322            iset.append_quad(iset.FullQuadMask ^ i1.get_quad())
323            i1.advance(1)
324         i2.advance(n)
325      else: # both s1 and s2 have mixed blocks; form block-by-block union
326         for i in range(n):
327            iset.append_quad(i1.get_quad() ^ i2.get_quad())
328            i1.advance(1)
329            i2.advance(1)
330   return iset
331
332UCD_point_regexp = re.compile("^([0-9A-F]{4,6})\s+;")
333UCD_range_regexp = re.compile("^([0-9A-F]{4,6})[.][.]([0-9A-F]{4,6})\s+;")
334
335def parse_UCD_set(lines):
336    pset = empty_set()
337    for t in lines:
338        m = UCD_point_regexp.match(t)
339        if m:
340            point = m.group(1)
341            pval = int(point, 16)
342            pset = union(pset, singleton_set(pval))
343        m = UCD_range_regexp.match(t)
344        if m:
345            point1 = m.group(1)
346            point2 = m.group(2)
347            pval1 = int(point1, 16)
348            pval2 = int(point2, 16)
349            pset = union(pset, make_range_set(pval1, pval2))
350    return pset
351
352def parse_UCD_file(fname, vname):
353    f = open(fname)
354    lines = f.readlines()
355    f.close()
356    s = parse_UCD_set(lines)
357    print s.showC(vname)
358
359
Note: See TracBrowser for help on using the repository browser.