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

Last change on this file since 4372 was 4372, checked in by cameron, 4 years ago

UCD set to run list function

File size: 13.0 KB
RevLine 
[4135]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.
[4183]9import re, cformat
[4135]10#
11# Unicode Sparse Bitset Representation
12#
13# The Unicode Sparse Bitset representation is based on
[4177]14# (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
[4135]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
[4178]25default_log2_quad_bits = 5
[4135]26
[4178]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
[4135]35class UCset:
[4178]36   def __init__(self):
[4135]37      self.runs = []
38      self.quads = []
39      self.quad_count = 0
[4176]40     
[4135]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)
[4178]56      elif q & FullQuadMask == FullQuadMask:
[4135]57        self.append_run(Full, 1)
58      else:
59        self.append_run(Mixed, 1)
60        self.quads.append(q)
61
[4142]62   # printing
[4186]63   def showC(self, indent = 4):
[4178]64      hex_specifier =  "%%#0%ix" % (quad_bits/4 + 2)
[4142]65      runtype = {-1:"Full", 0:"Empty", 1: "Mixed"}
[4183]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]
[4186]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
[4176]75      return setrep
[4135]76
[4176]77   def bytes(self):
[4178]78       return (len(self.runs) * run_bytes) + (len(self.quads) * quad_bits/8)
[4142]79
[4176]80
[4135]81#
82# Set Operations
83#
[4178]84def empty_uset():
85   e = UCset()
86   e.runs = [(Empty, UnicodeQuadCount)]
[4135]87   e.quads = []
[4178]88   e.quad_count = UnicodeQuadCount
[4142]89   return e
[4135]90
[4178]91def singleton_uset(codepoint):
92   e = UCset()
[4176]93   quad_no = codepoint >> log2_quad_bits
[4178]94   quad_val = 1 << (codepoint & mod_quad_bit_mask)
[4135]95   if quad_no > 0: e.append_run(Empty, quad_no)
96   e.append_run(Mixed, 1)
97   e.quads = [quad_val]
[4178]98   if quad_no < UnicodeQuadCount - 1: e.append_run(Empty, UnicodeQuadCount - (quad_no + 1))
99   e.quad_count = UnicodeQuadCount
[4135]100   return e
101
[4178]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
[4135]108   if lo_quad_no > 0:  e.append_run(Empty, lo_quad_no)
109   if lo_quad_no == hi_quad_no:
[4178]110      quad = (FullQuadMask << lo_offset) & (FullQuadMask >> (quad_bits - 1 - hi_offset))
[4135]111      e.append_quad(quad)
112   else:
[4178]113      e.append_quad((FullQuadMask << lo_offset) & FullQuadMask)
[4135]114      e.append_run(Full, hi_quad_no - (lo_quad_no + 1))
[4178]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))
[4135]117   return e
118
119
[4177]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
[4191]134        elif this_run_type == Full: return FullQuadMask
[4177]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
[4178]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
[4365]162
163def uset_popcount(s):
164    popcount = 0
165    it = Uset_Iterator(s)
166    while not it.at_end():
167        (runtype, n) = it.current_run()
168        if runtype == Empty:
169            it.advance(n)
170        elif runtype == Full:
171            popcount += n * quad_bits
172            it.advance(n)
173        else:
174            popcount += popcount_quad(it.get_quad)
175            it.advance(1)
176    return popcount
177
178def popcount_quad(q):
179    c = 0
180    while q != 0:
181        q = q & (q - 1) # clear low bit
182        c += 1
183    return c
184
[4178]185def uset_complement (s):
186   assert s.quad_count == UnicodeQuadCount
187   iset = UCset()
[4177]188   it = Uset_Iterator(s)
189   while not it.at_end():
190      (runtype, n) = it.current_run()
[4135]191      if runtype == Empty:
192         iset.append_run(Full, n)
[4177]193         it.advance(n)
[4135]194      elif runtype == Full:
195         iset.append_run(Empty, n)
[4177]196         it.advance(n)
[4135]197      else: 
[4177]198         for i in range(n):
[4191]199            iset.append_quad(FullQuadMask ^ it.get_quad())
[4177]200            it.advance(1)
[4135]201   return iset
202
[4178]203def uset_intersection (s1, s2):
204   assert s1.quad_count == UnicodeQuadCount
205   assert s2.quad_count == UnicodeQuadCount
[4135]206   iset = UCset()
[4177]207   i1 = Uset_Iterator(s1)
208   i2 = Uset_Iterator(s2)
209   while not i1.at_end():
210      (s1_type, s1_length) = i1.current_run()
211      (s2_type, s2_length) = i2.current_run()
[4135]212      n = min(s1_length, s2_length)
213      if s1_type == Empty or s2_type == Empty:
214         iset.append_run(Empty, n)
[4177]215         i1.advance(n)
216         i2.advance(n)
[4135]217      elif s1_type == Full and s2_type == Full:
218         iset.append_run(Full, n)
[4177]219         i1.advance(n)
220         i2.advance(n)
[4135]221      elif s1_type == Full:
[4177]222         for i in range(n):
223            iset.append_quad(i2.get_quad())
224            i2.advance(1)
225         i1.advance(n)
[4135]226      elif s2_type == Full:
[4177]227         for i in range(n):
228            iset.append_quad(i1.get_quad())
229            i1.advance(1)
230         i2.advance(n)
[4135]231      else: # both s1 and s2 have mixed blocks; form block-by-block intersection
232         for i in range(n):
[4177]233            iset.append_quad(i1.get_quad() & i2.get_quad())
234            i1.advance(1)
235            i2.advance(1)
[4135]236   return iset
237
[4178]238def uset_union (s1, s2):
239   assert s1.quad_count == UnicodeQuadCount
240   assert s2.quad_count == UnicodeQuadCount
[4135]241   iset = UCset()
[4177]242   i1 = Uset_Iterator(s1)
243   i2 = Uset_Iterator(s2)
244   while not i1.at_end():
245      (s1_type, s1_length) = i1.current_run()
246      (s2_type, s2_length) = i2.current_run()
[4135]247      n = min(s1_length, s2_length)
248      if s1_type == Empty and s2_type == Empty:
249         iset.append_run(Empty, n)
[4177]250         i1.advance(n)
251         i2.advance(n)
[4135]252      elif s1_type == Full or s2_type == Full:
253         iset.append_run(Full, n)
[4177]254         i1.advance(n)
255         i2.advance(n)
[4135]256      elif s1_type == Empty:
[4177]257         for i in range(n):
258            iset.append_quad(i2.get_quad())
259            i2.advance(1)
260         i1.advance(n)
[4135]261      elif s2_type == Empty:
[4177]262         for i in range(n):
263            iset.append_quad(i1.get_quad())
264            i1.advance(1)
265         i2.advance(n)
[4135]266      else: # both s1 and s2 have mixed blocks; form block-by-block union
267         for i in range(n):
[4177]268            iset.append_quad(i1.get_quad() | i2.get_quad())
269            i1.advance(1)
270            i2.advance(1)
[4135]271   return iset
272
[4178]273def uset_difference (s1, s2):
274   assert s1.quad_count == UnicodeQuadCount
275   assert s2.quad_count == UnicodeQuadCount
[4135]276   iset = UCset()
[4177]277   i1 = Uset_Iterator(s1)
278   i2 = Uset_Iterator(s2)
279   while not i1.at_end():
280      (s1_type, s1_length) = i1.current_run()
281      (s2_type, s2_length) = i2.current_run()
[4135]282      n = min(s1_length, s2_length)
283      if s1_type == Empty or s2_type == Full:
284         iset.append_run(Empty, n)
[4177]285         i1.advance(n)
286         i2.advance(n)
[4135]287      elif s1_type == Full and s2_type == Empty:
288         iset.append_run(Full, n)
[4177]289         i1.advance(n)
290         i2.advance(n)
[4135]291      elif s1_type == Full:
292         for i in range(n):
[4191]293            iset.append_quad(FullQuadMask ^ i2.get_quad())
[4177]294            i2.advance(1)
295         i1.advance(n)
296      elif s2_type == Empty:
297         for i in range(n):
298            iset.append_quad(i1.get_quad())
299            i1.advance(1)
300         i2.advance(n)
301      else: # both s1 and s2 have mixed blocks; form block-by-block union
302         for i in range(n):
303            iset.append_quad(i1.get_quad() &~ i2.get_quad())
304            i1.advance(1)
305            i2.advance(1)
[4135]306   return iset
307
[4178]308def uset_symmetric_difference (s1, s2):
309   assert s1.quad_count == UnicodeQuadCount
310   assert s2.quad_count == UnicodeQuadCount
[4135]311   iset = UCset()
[4177]312   i1 = Uset_Iterator(s1)
313   i2 = Uset_Iterator(s2)
314   while not i1.at_end():
315      (s1_type, s1_length) = i1.current_run()
316      (s2_type, s2_length) = i2.current_run()
[4135]317      n = min(s1_length, s2_length)
318      if s1_type == Empty and s2_type == Full or s1_type == Full and s2_type == Empty:
319         iset.append_run(Full, n)
[4178]320         i1.advance(n)
321         i2.advance(n)
[4135]322      elif s1_type == Full and s2_type == Full or s1_type == Empty and s2_type == Empty:
323         iset.append_run(Empty, n)
[4178]324         i1.advance(n)
325         i2.advance(n)
[4135]326      elif s1_type == Empty:
[4177]327         for i in range(n):
328            iset.append_quad(i2.get_quad())
329            i2.advance(1)
330         i1.advance(n)
[4135]331      elif s2_type == Empty:
[4177]332         for i in range(n):
333            iset.append_quad(i1.get_quad())
334            i1.advance(1)
335         i2.advance(n)
[4135]336      elif s1_type == Full:
[4177]337         for i in range(n):
[4191]338            iset.append_quad(FullQuadMask ^ i2.get_quad())
[4177]339            i2.advance(1)
340         i1.advance(n)
[4135]341      elif s2_type == Full:
342         for i in range(n):
[4191]343            iset.append_quad(FullQuadMask ^ i1.get_quad())
[4177]344            i1.advance(1)
345         i2.advance(n)
346      else: # both s1 and s2 have mixed blocks; form block-by-block union
347         for i in range(n):
348            iset.append_quad(i1.get_quad() ^ i2.get_quad())
349            i1.advance(1)
350            i2.advance(1)
[4135]351   return iset
352
[4372]353def uset_to_range_list(s):
354    i = Uset_Iterator(s)
355    rl = []
356    open_range = False
357    range_first = 0
358    pos = 0
359    while not i.at_end():
360        (q_type, q_length) = i.current_run()
361        if q_type == Empty:
362            if open_range: 
363                rl.append((range_first, pos - 1))
364                open_range = False
365            pos += q_length * quad_bits
366            i.advance(q_length)
367        elif q_type == Full:
368            if not open_range:
369                range_first = pos
370                open_range = True
371            pos += q_length * quad_bits
372            i.advance(q_length)
373        else:  # mixed quad
374            q = i.get_quad()
375            qpos = pos
376            while q:
377                if q & 1 == 0:
378                    if open_range:
379                        rl.append((range_first, qpos - 1))
380                        open_range = False
381                else:
382                    if not open_range:
383                        range_first = qpos
384                        open_range = True
385                q >>= 1
386                qpos += 1
387            pos += quad_bits
388            i.advance(1)
389    if open_range:
390        rl.append((range_first, 0x10FFFF))
391    return rl
392
[4142]393UCD_point_regexp = re.compile("^([0-9A-F]{4,6})\s+;")
394UCD_range_regexp = re.compile("^([0-9A-F]{4,6})[.][.]([0-9A-F]{4,6})\s+;")
[4135]395
[4142]396def parse_UCD_set(lines):
397    pset = empty_set()
398    for t in lines:
399        m = UCD_point_regexp.match(t)
400        if m:
401            point = m.group(1)
402            pval = int(point, 16)
403            pset = union(pset, singleton_set(pval))
404        m = UCD_range_regexp.match(t)
405        if m:
406            point1 = m.group(1)
407            point2 = m.group(2)
408            pval1 = int(point1, 16)
409            pval2 = int(point2, 16)
410            pset = union(pset, make_range_set(pval1, pval2))
411    return pset
412
413def parse_UCD_file(fname, vname):
414    f = open(fname)
415    lines = f.readlines()
416    f.close()
417    s = parse_UCD_set(lines)
418    print s.showC(vname)
419
420
Note: See TracBrowser for help on using the repository browser.