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

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

Introduce Uset_Iterator objects

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