1""" 2Given a list of integers, made up of (hopefully) a small number of long runs 3of consecutive integers, compute a representation of the form 4((start1, end1), (start2, end2) ...). Then answer the question "was x present 5in the original list?" in time O(log(# runs)). 6""" 7 8import bisect 9 10def 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 31def _encode_range(start, end): 32 return (start << 32) | end 33 34def _decode_range(r): 35 return (r >> 32), (r & ((1 << 32) - 1)) 36 37 38def 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 54