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

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

Modifications to UCD property object generator.

File size: 13.0 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 += '}}'
74      return setrep
75
76   def bytes(self):
77       return (len(self.runs) * run_bytes) + (len(self.quads) * quad_bits/8)
78
79
80#
81# Set Operations
82#
83def empty_uset():
84   e = UCset()
85   e.runs = [(Empty, UnicodeQuadCount)]
86   e.quads = []
87   e.quad_count = UnicodeQuadCount
88   return e
89
90def singleton_uset(codepoint):
91   e = UCset()
92   quad_no = codepoint >> log2_quad_bits
93   quad_val = 1 << (codepoint & mod_quad_bit_mask)
94   if quad_no > 0: e.append_run(Empty, quad_no)
95   e.append_run(Mixed, 1)
96   e.quads = [quad_val]
97   if quad_no < UnicodeQuadCount - 1: e.append_run(Empty, UnicodeQuadCount - (quad_no + 1))
98   e.quad_count = UnicodeQuadCount
99   return e
100
101def range_uset(lo_codepoint, hi_codepoint):
102   e = UCset()
103   lo_quad_no = lo_codepoint >> log2_quad_bits   
104   hi_quad_no = hi_codepoint >> log2_quad_bits
105   lo_offset = lo_codepoint & mod_quad_bit_mask
106   hi_offset = hi_codepoint & mod_quad_bit_mask
107   if lo_quad_no > 0:  e.append_run(Empty, lo_quad_no)
108   if lo_quad_no == hi_quad_no:
109      quad = (FullQuadMask << lo_offset) & (FullQuadMask >> (quad_bits - 1 - hi_offset))
110      e.append_quad(quad)
111   else:
112      e.append_quad((FullQuadMask << lo_offset) & FullQuadMask)
113      e.append_run(Full, hi_quad_no - (lo_quad_no + 1))
114      e.append_quad((FullQuadMask >> (quad_bits - 1 - hi_offset)) & FullQuadMask)
115   if hi_quad_no < UnicodeQuadCount - 1: e.append_run(Empty, UnicodeQuadCount - (hi_quad_no + 1))
116   return e
117
118
119class Uset_Iterator:
120    def __init__(self, uSet):
121        self.uSet = uSet
122        self.run_no = 0
123        self.offset = 0
124        self.quad_no = 0
125    def at_end(self):
126        return self.run_no == len(self.uSet.runs)
127    def current_run(self):
128        (this_run_type, this_run_length) = self.uSet.runs[self.run_no]
129        return (this_run_type, this_run_length - self.offset)
130    def get_quad(self):
131        (this_run_type, this_run_length) = self.uSet.runs[self.run_no]
132        if this_run_type == Empty: return 0
133        elif this_run_type == Full: return FullQuadMask
134        else: return self.uSet.quads[self.quad_no]
135    def advance(self, n):
136        while n > 0:
137           (this_run_type, this_run_length) = self.uSet.runs[self.run_no]
138           remain = this_run_length - self.offset
139           if remain > n:
140               self.offset += n
141               if this_run_type == Mixed: self.quad_no += n
142               n = 0
143           elif remain == n:
144               self.run_no += 1
145               self.offset = 0
146               if this_run_type == Mixed: self.quad_no += n
147               n = 0
148           else:
149               self.run_no += 1
150               self.offset = 0
151               if this_run_type == Mixed: self.quad_no += remain
152               n -= remain
153
154
155def uset_member(s, codepoint):
156   quad_no = codepoint / quad_bits
157   quad_val = 1 << (codepoint & mod_quad_bit_mask)
158   it = Uset_Iterator(s)   
159   it.advance(quad_no)
160   return (it.get_quad() & quad_val) != 0
161
162def uset_popcount(s):
163    popcount = 0
164    it = Uset_Iterator(s)
165    while not it.at_end():
166        (runtype, n) = it.current_run()
167        if runtype == Empty:
168            it.advance(n)
169        elif runtype == Full:
170            popcount += n * quad_bits
171            it.advance(n)
172        else:
173            popcount += popcount_quad(it.get_quad())
174            it.advance(1)
175    return popcount
176
177def popcount_quad(q):
178    c = 0
179    while q != 0:
180        q = q & (q - 1) # clear low bit
181        c += 1
182    return c
183
184def uset_complement (s):
185   assert s.quad_count == UnicodeQuadCount
186   iset = UCset()
187   it = Uset_Iterator(s)
188   while not it.at_end():
189      (runtype, n) = it.current_run()
190      if runtype == Empty:
191         iset.append_run(Full, n)
192         it.advance(n)
193      elif runtype == Full:
194         iset.append_run(Empty, n)
195         it.advance(n)
196      else: 
197         for i in range(n):
198            iset.append_quad(FullQuadMask ^ it.get_quad())
199            it.advance(1)
200   return iset
201
202def uset_intersection (s1, s2):
203   assert s1.quad_count == UnicodeQuadCount
204   assert s2.quad_count == UnicodeQuadCount
205   iset = UCset()
206   i1 = Uset_Iterator(s1)
207   i2 = Uset_Iterator(s2)
208   while not i1.at_end():
209      (s1_type, s1_length) = i1.current_run()
210      (s2_type, s2_length) = i2.current_run()
211      n = min(s1_length, s2_length)
212      if s1_type == Empty or s2_type == Empty:
213         iset.append_run(Empty, n)
214         i1.advance(n)
215         i2.advance(n)
216      elif s1_type == Full and s2_type == Full:
217         iset.append_run(Full, n)
218         i1.advance(n)
219         i2.advance(n)
220      elif s1_type == Full:
221         for i in range(n):
222            iset.append_quad(i2.get_quad())
223            i2.advance(1)
224         i1.advance(n)
225      elif s2_type == Full:
226         for i in range(n):
227            iset.append_quad(i1.get_quad())
228            i1.advance(1)
229         i2.advance(n)
230      else: # both s1 and s2 have mixed blocks; form block-by-block intersection
231         for i in range(n):
232            iset.append_quad(i1.get_quad() & i2.get_quad())
233            i1.advance(1)
234            i2.advance(1)
235   return iset
236
237def uset_union (s1, s2):
238   assert s1.quad_count == UnicodeQuadCount
239   assert s2.quad_count == UnicodeQuadCount
240   iset = UCset()
241   i1 = Uset_Iterator(s1)
242   i2 = Uset_Iterator(s2)
243   while not i1.at_end():
244      (s1_type, s1_length) = i1.current_run()
245      (s2_type, s2_length) = i2.current_run()
246      n = min(s1_length, s2_length)
247      if s1_type == Empty and s2_type == Empty:
248         iset.append_run(Empty, n)
249         i1.advance(n)
250         i2.advance(n)
251      elif s1_type == Full or s2_type == Full:
252         iset.append_run(Full, n)
253         i1.advance(n)
254         i2.advance(n)
255      elif s1_type == Empty:
256         for i in range(n):
257            iset.append_quad(i2.get_quad())
258            i2.advance(1)
259         i1.advance(n)
260      elif s2_type == Empty:
261         for i in range(n):
262            iset.append_quad(i1.get_quad())
263            i1.advance(1)
264         i2.advance(n)
265      else: # both s1 and s2 have mixed blocks; form block-by-block union
266         for i in range(n):
267            iset.append_quad(i1.get_quad() | i2.get_quad())
268            i1.advance(1)
269            i2.advance(1)
270   return iset
271
272def uset_difference (s1, s2):
273   assert s1.quad_count == UnicodeQuadCount
274   assert s2.quad_count == UnicodeQuadCount
275   iset = UCset()
276   i1 = Uset_Iterator(s1)
277   i2 = Uset_Iterator(s2)
278   while not i1.at_end():
279      (s1_type, s1_length) = i1.current_run()
280      (s2_type, s2_length) = i2.current_run()
281      n = min(s1_length, s2_length)
282      if s1_type == Empty or s2_type == Full:
283         iset.append_run(Empty, n)
284         i1.advance(n)
285         i2.advance(n)
286      elif s1_type == Full and s2_type == Empty:
287         iset.append_run(Full, n)
288         i1.advance(n)
289         i2.advance(n)
290      elif s1_type == Full:
291         for i in range(n):
292            iset.append_quad(FullQuadMask ^ i2.get_quad())
293            i2.advance(1)
294         i1.advance(n)
295      elif s2_type == Empty:
296         for i in range(n):
297            iset.append_quad(i1.get_quad())
298            i1.advance(1)
299         i2.advance(n)
300      else: # both s1 and s2 have mixed blocks; form block-by-block union
301         for i in range(n):
302            iset.append_quad(i1.get_quad() &~ i2.get_quad())
303            i1.advance(1)
304            i2.advance(1)
305   return iset
306
307def uset_symmetric_difference (s1, s2):
308   assert s1.quad_count == UnicodeQuadCount
309   assert s2.quad_count == UnicodeQuadCount
310   iset = UCset()
311   i1 = Uset_Iterator(s1)
312   i2 = Uset_Iterator(s2)
313   while not i1.at_end():
314      (s1_type, s1_length) = i1.current_run()
315      (s2_type, s2_length) = i2.current_run()
316      n = min(s1_length, s2_length)
317      if s1_type == Empty and s2_type == Full or s1_type == Full and s2_type == Empty:
318         iset.append_run(Full, n)
319         i1.advance(n)
320         i2.advance(n)
321      elif s1_type == Full and s2_type == Full or s1_type == Empty and s2_type == Empty:
322         iset.append_run(Empty, n)
323         i1.advance(n)
324         i2.advance(n)
325      elif s1_type == Empty:
326         for i in range(n):
327            iset.append_quad(i2.get_quad())
328            i2.advance(1)
329         i1.advance(n)
330      elif s2_type == Empty:
331         for i in range(n):
332            iset.append_quad(i1.get_quad())
333            i1.advance(1)
334         i2.advance(n)
335      elif s1_type == Full:
336         for i in range(n):
337            iset.append_quad(FullQuadMask ^ i2.get_quad())
338            i2.advance(1)
339         i1.advance(n)
340      elif s2_type == Full:
341         for i in range(n):
342            iset.append_quad(FullQuadMask ^ i1.get_quad())
343            i1.advance(1)
344         i2.advance(n)
345      else: # both s1 and s2 have mixed blocks; form block-by-block union
346         for i in range(n):
347            iset.append_quad(i1.get_quad() ^ i2.get_quad())
348            i1.advance(1)
349            i2.advance(1)
350   return iset
351
352def uset_to_range_list(s):
353    i = Uset_Iterator(s)
354    rl = []
355    open_range = False
356    range_first = 0
357    pos = 0
358    while not i.at_end():
359        (q_type, q_length) = i.current_run()
360        if q_type == Empty:
361            if open_range: 
362                rl.append((range_first, pos - 1))
363                open_range = False
364            pos += q_length * quad_bits
365            i.advance(q_length)
366        elif q_type == Full:
367            if not open_range:
368                range_first = pos
369                open_range = True
370            pos += q_length * quad_bits
371            i.advance(q_length)
372        else:  # mixed quad
373            q = i.get_quad()
374            qpos = pos
375            for qpos in range(pos, pos+quad_bits):
376                if q & 1 == 0:
377                    if open_range:
378                        rl.append((range_first, qpos - 1))
379                        open_range = False
380                else:
381                    if not open_range:
382                        range_first = qpos
383                        open_range = True
384                q >>= 1
385                qpos += 1
386            pos += quad_bits
387            i.advance(1)
388    if open_range:
389        rl.append((range_first, 0x10FFFF))
390    return rl
391
392UCD_point_regexp = re.compile("^([0-9A-F]{4,6})\s+;")
393UCD_range_regexp = re.compile("^([0-9A-F]{4,6})[.][.]([0-9A-F]{4,6})\s+;")
394
395def parse_UCD_set(lines):
396    pset = empty_set()
397    for t in lines:
398        m = UCD_point_regexp.match(t)
399        if m:
400            point = m.group(1)
401            pval = int(point, 16)
402            pset = union(pset, singleton_set(pval))
403        m = UCD_range_regexp.match(t)
404        if m:
405            point1 = m.group(1)
406            point2 = m.group(2)
407            pval1 = int(point1, 16)
408            pval2 = int(point2, 16)
409            pset = union(pset, make_range_set(pval1, pval2))
410    return pset
411
412def parse_UCD_file(fname, vname):
413    f = open(fname)
414    lines = f.readlines()
415    f.close()
416    s = parse_UCD_set(lines)
417    print s.showC(vname)
418
419
Note: See TracBrowser for help on using the repository browser.