Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/idna/intranges.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """
2 Given a list of integers, made up of (hopefully) a small number of long runs
3 of consecutive integers, compute a representation of the form
4 ((start1, end1), (start2, end2) ...). Then answer the question "was x present
5 in the original list?" in time O(log(# runs)).
6 """
7
8 import bisect
9
10 def intranges_from_list(list_):
11 """Represent a list of integers as a sequence of ranges:
12 ((start_0, end_0), (start_1, end_1), ...), such that the original
13 integers are exactly those x such that start_i <= x < end_i for some i.
14
15 Ranges are encoded as single integers (start << 32 | end), not as tuples.
16 """
17
18 sorted_list = sorted(list_)
19 ranges = []
20 last_write = -1
21 for i in range(len(sorted_list)):
22 if i+1 < len(sorted_list):
23 if sorted_list[i] == sorted_list[i+1]-1:
24 continue
25 current_range = sorted_list[last_write+1:i+1]
26 ranges.append(_encode_range(current_range[0], current_range[-1] + 1))
27 last_write = i
28
29 return tuple(ranges)
30
31 def _encode_range(start, end):
32 return (start << 32) | end
33
34 def _decode_range(r):
35 return (r >> 32), (r & ((1 << 32) - 1))
36
37
38 def intranges_contain(int_, ranges):
39 """Determine if `int_` falls into one of the ranges in `ranges`."""
40 tuple_ = _encode_range(int_, 0)
41 pos = bisect.bisect_left(ranges, tuple_)
42 # we could be immediately ahead of a tuple (start, end)
43 # with start < int_ <= end
44 if pos > 0:
45 left, right = _decode_range(ranges[pos-1])
46 if left <= int_ < right:
47 return True
48 # or we could be immediately behind a tuple (int_, end)
49 if pos < len(ranges):
50 left, _ = _decode_range(ranges[pos])
51 if left == int_:
52 return True
53 return False