Mercurial > repos > rliterman > csp2

comparison CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/lib/python3.8/site-packages/idna/intranges.py @ 68:5028fdace37b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 16:23:26 -0400
parents
children
comparison
equal deleted inserted replaced
67:0e9998148a16 68:5028fdace37b
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 from typing import List, Tuple
10
11
12 def intranges_from_list(list_: List[int]) -> Tuple[int, ...]:
13 """Represent a list of integers as a sequence of ranges:
14 ((start_0, end_0), (start_1, end_1), ...), such that the original
15 integers are exactly those x such that start_i <= x < end_i for some i.
16
17 Ranges are encoded as single integers (start << 32 | end), not as tuples.
18 """
19
20 sorted_list = sorted(list_)
21 ranges = []
22 last_write = -1
23 for i in range(len(sorted_list)):
24 if i + 1 < len(sorted_list):
25 if sorted_list[i] == sorted_list[i + 1] - 1:
26 continue
27 current_range = sorted_list[last_write + 1 : i + 1]
28 ranges.append(_encode_range(current_range[0], current_range[-1] + 1))
29 last_write = i
30
31 return tuple(ranges)
32
33
34 def _encode_range(start: int, end: int) -> int:
35 return (start << 32) | end
36
37
38 def _decode_range(r: int) -> Tuple[int, int]:
39 return (r >> 32), (r & ((1 << 32) - 1))
40
41
42 def intranges_contain(int_: int, ranges: Tuple[int, ...]) -> bool:
43 """Determine if `int_` falls into one of the ranges in `ranges`."""
44 tuple_ = _encode_range(int_, 0)
45 pos = bisect.bisect_left(ranges, tuple_)
46 # we could be immediately ahead of a tuple (start, end)
47 # with start < int_ <= end
48 if pos > 0:
49 left, right = _decode_range(ranges[pos - 1])
50 if left <= int_ < right:
51 return True
52 # or we could be immediately behind a tuple (int_, end)
53 if pos < len(ranges):
54 left, _ = _decode_range(ranges[pos])
55 if left == int_:
56 return True
57 return False