source: icGREP/icgrep-devel/UCD-scripts/unicode_set.py @ 5735

Last change on this file since 5735 was 5653, checked in by cameron, 20 months ago

Updates for Python 3; some refactoring

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
[5653]30UnicodeQuadCount = int(0x110000 / quad_bits) #  2**log2_quad_bits codepoints per quad
[4178]31FullQuadMask = (1<<(quad_bits)) - 1
[5153]32run_bytes = 4
[4178]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):
[5653]64      hex_specifier =  "%%#0%ix" % (int(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)
[4632]73      setrep += '}}'
[4176]74      return setrep
[4135]75
[4176]76   def bytes(self):
[5653]77       return (len(self.runs) * run_bytes) + (len(self.quads) * int(quad_bits/8))
[4142]78
[4176]79
[4135]80#
81# Set Operations
82#
[4178]83def empty_uset():
84   e = UCset()
85   e.runs = [(Empty, UnicodeQuadCount)]
[4135]86   e.quads = []
[4178]87   e.quad_count = UnicodeQuadCount
[4142]88   return e
[4135]89
[4178]90def singleton_uset(codepoint):
91   e = UCset()
[4176]92   quad_no = codepoint >> log2_quad_bits
[4178]93   quad_val = 1 << (codepoint & mod_quad_bit_mask)
[4135]94   if quad_no > 0: e.append_run(Empty, quad_no)
95   e.append_run(Mixed, 1)
96   e.quads = [quad_val]
[4178]97   if quad_no < UnicodeQuadCount - 1: e.append_run(Empty, UnicodeQuadCount - (quad_no + 1))
98   e.quad_count = UnicodeQuadCount
[4135]99   return e
100
[4178]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
[4135]107   if lo_quad_no > 0:  e.append_run(Empty, lo_quad_no)
108   if lo_quad_no == hi_quad_no:
[4178]109      quad = (FullQuadMask << lo_offset) & (FullQuadMask >> (quad_bits - 1 - hi_offset))
[4135]110      e.append_quad(quad)
111   else:
[4178]112      e.append_quad((FullQuadMask << lo_offset) & FullQuadMask)
[4135]113      e.append_run(Full, hi_quad_no - (lo_quad_no + 1))
[4178]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))
[4135]116   return e
117
118
[4177]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
[4191]133        elif this_run_type == Full: return FullQuadMask
[4177]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
[4178]153
154
155def uset_member(s, codepoint):
[5653]156   quad_no = int(codepoint / quad_bits)
[4178]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
[4365]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:
[4457]173            popcount += popcount_quad(it.get_quad())
[4365]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
[4178]184def uset_complement (s):
185   assert s.quad_count == UnicodeQuadCount
186   iset = UCset()
[4177]187   it = Uset_Iterator(s)
188   while not it.at_end():
189      (runtype, n) = it.current_run()
[4135]190      if runtype == Empty:
191         iset.append_run(Full, n)
[4177]192         it.advance(n)
[4135]193      elif runtype == Full:
194         iset.append_run(Empty, n)
[4177]195         it.advance(n)
[4135]196      else: 
[4177]197         for i in range(n):
[4191]198            iset.append_quad(FullQuadMask ^ it.get_quad())
[4177]199            it.advance(1)
[4135]200   return iset
201
[4178]202def uset_intersection (s1, s2):
203   assert s1.quad_count == UnicodeQuadCount
204   assert s2.quad_count == UnicodeQuadCount
[4135]205   iset = UCset()
[4177]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()
[4135]211      n = min(s1_length, s2_length)
212      if s1_type == Empty or s2_type == Empty:
213         iset.append_run(Empty, n)
[4177]214         i1.advance(n)
215         i2.advance(n)
[4135]216      elif s1_type == Full and s2_type == Full:
217         iset.append_run(Full, n)
[4177]218         i1.advance(n)
219         i2.advance(n)
[4135]220      elif s1_type == Full:
[4177]221         for i in range(n):
222            iset.append_quad(i2.get_quad())
223            i2.advance(1)
224         i1.advance(n)
[4135]225      elif s2_type == Full:
[4177]226         for i in range(n):
227            iset.append_quad(i1.get_quad())
228            i1.advance(1)
229         i2.advance(n)
[4135]230      else: # both s1 and s2 have mixed blocks; form block-by-block intersection
231         for i in range(n):
[4177]232            iset.append_quad(i1.get_quad() & i2.get_quad())
233            i1.advance(1)
234            i2.advance(1)
[4135]235   return iset
236
[4178]237def uset_union (s1, s2):
238   assert s1.quad_count == UnicodeQuadCount
239   assert s2.quad_count == UnicodeQuadCount
[4135]240   iset = UCset()
[4177]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()
[4135]246      n = min(s1_length, s2_length)
247      if s1_type == Empty and s2_type == Empty:
248         iset.append_run(Empty, n)
[4177]249         i1.advance(n)
250         i2.advance(n)
[4135]251      elif s1_type == Full or s2_type == Full:
252         iset.append_run(Full, n)
[4177]253         i1.advance(n)
254         i2.advance(n)
[4135]255      elif s1_type == Empty:
[4177]256         for i in range(n):
257            iset.append_quad(i2.get_quad())
258            i2.advance(1)
259         i1.advance(n)
[4135]260      elif s2_type == Empty:
[4177]261         for i in range(n):
262            iset.append_quad(i1.get_quad())
263            i1.advance(1)
264         i2.advance(n)
[4135]265      else: # both s1 and s2 have mixed blocks; form block-by-block union
266         for i in range(n):
[4177]267            iset.append_quad(i1.get_quad() | i2.get_quad())
268            i1.advance(1)
269            i2.advance(1)
[4135]270   return iset
271
[4178]272def uset_difference (s1, s2):
273   assert s1.quad_count == UnicodeQuadCount
274   assert s2.quad_count == UnicodeQuadCount
[4135]275   iset = UCset()
[4177]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()
[4135]281      n = min(s1_length, s2_length)
282      if s1_type == Empty or s2_type == Full:
283         iset.append_run(Empty, n)
[4177]284         i1.advance(n)
285         i2.advance(n)
[4135]286      elif s1_type == Full and s2_type == Empty:
287         iset.append_run(Full, n)
[4177]288         i1.advance(n)
289         i2.advance(n)
[4135]290      elif s1_type == Full:
291         for i in range(n):
[4191]292            iset.append_quad(FullQuadMask ^ i2.get_quad())
[4177]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)
[4135]305   return iset
306
[4178]307def uset_symmetric_difference (s1, s2):
308   assert s1.quad_count == UnicodeQuadCount
309   assert s2.quad_count == UnicodeQuadCount
[4135]310   iset = UCset()
[4177]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()
[4135]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)
[4178]319         i1.advance(n)
320         i2.advance(n)
[4135]321      elif s1_type == Full and s2_type == Full or s1_type == Empty and s2_type == Empty:
322         iset.append_run(Empty, n)
[4178]323         i1.advance(n)
324         i2.advance(n)
[4135]325      elif s1_type == Empty:
[4177]326         for i in range(n):
327            iset.append_quad(i2.get_quad())
328            i2.advance(1)
329         i1.advance(n)
[4135]330      elif s2_type == Empty:
[4177]331         for i in range(n):
332            iset.append_quad(i1.get_quad())
333            i1.advance(1)
334         i2.advance(n)
[4135]335      elif s1_type == Full:
[4177]336         for i in range(n):
[4191]337            iset.append_quad(FullQuadMask ^ i2.get_quad())
[4177]338            i2.advance(1)
339         i1.advance(n)
[4135]340      elif s2_type == Full:
341         for i in range(n):
[4191]342            iset.append_quad(FullQuadMask ^ i1.get_quad())
[4177]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)
[4135]350   return iset
351
[4372]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
[4373]375            for qpos in range(pos, pos+quad_bits):
[4372]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
[4142]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+;")
[4135]394
[4142]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)
[5653]417    print(s.showC(vname))
[4142]418
419
Note: See TracBrowser for help on using the repository browser.