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
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 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_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
185def uset_complement (s):
186   assert s.quad_count == UnicodeQuadCount
187   iset = UCset()
188   it = Uset_Iterator(s)
189   while not it.at_end():
190      (runtype, n) = it.current_run()
191      if runtype == Empty:
192         iset.append_run(Full, n)
193         it.advance(n)
194      elif runtype == Full:
195         iset.append_run(Empty, n)
196         it.advance(n)
197      else: 
198         for i in range(n):
199            iset.append_quad(FullQuadMask ^ it.get_quad())
200            it.advance(1)
201   return iset
202
203def uset_intersection (s1, s2):
204   assert s1.quad_count == UnicodeQuadCount
205   assert s2.quad_count == UnicodeQuadCount
206   iset = UCset()
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()
212      n = min(s1_length, s2_length)
213      if s1_type == Empty or s2_type == Empty:
214         iset.append_run(Empty, n)
215         i1.advance(n)
216         i2.advance(n)
217      elif s1_type == Full and s2_type == Full:
218         iset.append_run(Full, n)
219         i1.advance(n)
220         i2.advance(n)
221      elif s1_type == Full:
222         for i in range(n):
223            iset.append_quad(i2.get_quad())
224            i2.advance(1)
225         i1.advance(n)
226      elif s2_type == Full:
227         for i in range(n):
228            iset.append_quad(i1.get_quad())
229            i1.advance(1)
230         i2.advance(n)
231      else: # both s1 and s2 have mixed blocks; form block-by-block intersection
232         for i in range(n):
233            iset.append_quad(i1.get_quad() & i2.get_quad())
234            i1.advance(1)
235            i2.advance(1)
236   return iset
237
238def uset_union (s1, s2):
239   assert s1.quad_count == UnicodeQuadCount
240   assert s2.quad_count == UnicodeQuadCount
241   iset = UCset()
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()
247      n = min(s1_length, s2_length)
248      if s1_type == Empty and s2_type == Empty:
249         iset.append_run(Empty, n)
250         i1.advance(n)
251         i2.advance(n)
252      elif s1_type == Full or s2_type == Full:
253         iset.append_run(Full, n)
254         i1.advance(n)
255         i2.advance(n)
256      elif s1_type == Empty:
257         for i in range(n):
258            iset.append_quad(i2.get_quad())
259            i2.advance(1)
260         i1.advance(n)
261      elif s2_type == Empty:
262         for i in range(n):
263            iset.append_quad(i1.get_quad())
264            i1.advance(1)
265         i2.advance(n)
266      else: # both s1 and s2 have mixed blocks; form block-by-block union
267         for i in range(n):
268            iset.append_quad(i1.get_quad() | i2.get_quad())
269            i1.advance(1)
270            i2.advance(1)
271   return iset
272
273def uset_difference (s1, s2):
274   assert s1.quad_count == UnicodeQuadCount
275   assert s2.quad_count == UnicodeQuadCount
276   iset = UCset()
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()
282      n = min(s1_length, s2_length)
283      if s1_type == Empty or s2_type == Full:
284         iset.append_run(Empty, n)
285         i1.advance(n)
286         i2.advance(n)
287      elif s1_type == Full and s2_type == Empty:
288         iset.append_run(Full, n)
289         i1.advance(n)
290         i2.advance(n)
291      elif s1_type == Full:
292         for i in range(n):
293            iset.append_quad(FullQuadMask ^ i2.get_quad())
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)
306   return iset
307
308def uset_symmetric_difference (s1, s2):
309   assert s1.quad_count == UnicodeQuadCount
310   assert s2.quad_count == UnicodeQuadCount
311   iset = UCset()
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()
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)
320         i1.advance(n)
321         i2.advance(n)
322      elif s1_type == Full and s2_type == Full or s1_type == Empty and s2_type == Empty:
323         iset.append_run(Empty, n)
324         i1.advance(n)
325         i2.advance(n)
326      elif s1_type == Empty:
327         for i in range(n):
328            iset.append_quad(i2.get_quad())
329            i2.advance(1)
330         i1.advance(n)
331      elif s2_type == Empty:
332         for i in range(n):
333            iset.append_quad(i1.get_quad())
334            i1.advance(1)
335         i2.advance(n)
336      elif s1_type == Full:
337         for i in range(n):
338            iset.append_quad(FullQuadMask ^ i2.get_quad())
339            i2.advance(1)
340         i1.advance(n)
341      elif s2_type == Full:
342         for i in range(n):
343            iset.append_quad(FullQuadMask ^ i1.get_quad())
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)
351   return iset
352
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
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+;")
395
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.