1 # Copyright 2013 The Chromium Authors. All rights reserved. 2 # Use of this source code is governed by a BSD-style license that can be 3 # found in the LICENSE file. 4 5 import os 6 import sys 7 8 _BASE_PATH = os.path.dirname(os.path.dirname(os.path.abspath(__file__))) 9 _BINTREES_PATH = os.path.join( 10 _BASE_PATH, os.pardir, os.pardir, 'third_party', 'bintrees') 11 sys.path.insert(0, _BINTREES_PATH) 12 13 from bintrees import FastRBTree # pylint: disable=F0401 14 15 16 class ExclusiveRangeDict(object): 17 """A class like dict whose key is a range [begin, end) of integers. 18 19 It has an attribute for each range of integers, for example: 20 [10, 20) => Attribute(0), 21 [20, 40) => Attribute(1), 22 [40, 50) => Attribute(2), 23 ... 24 25 An instance of this class is accessed only via iter_range(begin, end). 26 The instance is accessed as follows: 27 28 1) If the given range [begin, end) is not covered by the instance, 29 the range is newly created and iterated. 30 31 2) If the given range [begin, end) exactly covers ranges in the instance, 32 the ranges are iterated. 33 (See test_set() in tests/range_dict_tests.py.) 34 35 3) If the given range [begin, end) starts at and/or ends at a mid-point of 36 an existing range, the existing range is split by the given range, and 37 ranges in the given range are iterated. For example, consider a case that 38 [25, 45) is given to an instance of [20, 30), [30, 40), [40, 50). In this 39 case, [20, 30) is split into [20, 25) and [25, 30), and [40, 50) into 40 [40, 45) and [45, 50). Then, [25, 30), [30, 40), [40, 45) are iterated. 41 (See test_split() in tests/range_dict_tests.py.) 42 43 4) If the given range [begin, end) includes non-existing ranges in an 44 instance, the gaps are filled with new ranges, and all ranges are iterated. 45 For example, consider a case that [25, 50) is given to an instance of 46 [30, 35) and [40, 45). In this case, [25, 30), [35, 40) and [45, 50) are 47 created in the instance, and then [25, 30), [30, 35), [35, 40), [40, 45) 48 and [45, 50) are iterated. 49 (See test_fill() in tests/range_dict_tests.py.) 50 """ 51 class RangeAttribute(object): 52 def __init__(self): 53 pass 54 55 def __str__(self): 56 return '<RangeAttribute>' 57 58 def __repr__(self): 59 return '<RangeAttribute>' 60 61 def copy(self): # pylint: disable=R0201 62 return ExclusiveRangeDict.RangeAttribute() 63 64 def __init__(self, attr=RangeAttribute): 65 self._tree = FastRBTree() 66 self._attr = attr 67 68 def iter_range(self, begin=None, end=None): 69 if not begin: 70 begin = self._tree.min_key() 71 if not end: 72 end = self._tree.max_item()[1][0] 73 74 # Assume that self._tree has at least one element. 75 if self._tree.is_empty(): 76 self._tree[begin] = (end, self._attr()) 77 78 # Create a beginning range (border) 79 try: 80 bound_begin, bound_value = self._tree.floor_item(begin) 81 bound_end = bound_value[0] 82 if begin >= bound_end: 83 # Create a blank range. 84 try: 85 new_end, _ = self._tree.succ_item(bound_begin) 86 except KeyError: 87 new_end = end 88 self._tree[begin] = (min(end, new_end), self._attr()) 89 elif bound_begin < begin and begin < bound_end: 90 # Split the existing range. 91 new_end = bound_value[0] 92 new_value = bound_value[1] 93 self._tree[bound_begin] = (begin, new_value.copy()) 94 self._tree[begin] = (new_end, new_value.copy()) 95 else: # bound_begin == begin 96 # Do nothing (just saying it clearly since this part is confusing) 97 pass 98 except KeyError: # begin is less than the smallest element. 99 # Create a blank range. 100 # Note that we can assume self._tree has at least one element. 101 self._tree[begin] = (min(end, self._tree.min_key()), self._attr()) 102 103 # Create an ending range (border) 104 try: 105 bound_begin, bound_value = self._tree.floor_item(end) 106 bound_end = bound_value[0] 107 if end > bound_end: 108 # Create a blank range. 109 new_begin = bound_end 110 self._tree[new_begin] = (end, self._attr()) 111 elif bound_begin < end and end < bound_end: 112 # Split the existing range. 113 new_end = bound_value[0] 114 new_value = bound_value[1] 115 self._tree[bound_begin] = (end, new_value.copy()) 116 self._tree[end] = (new_end, new_value.copy()) 117 else: # bound_begin == begin 118 # Do nothing (just saying it clearly since this part is confusing) 119 pass 120 except KeyError: # end is less than the smallest element. 121 # It must not happen. A blank range [begin,end) has already been created 122 # even if [begin,end) is less than the smallest range. 123 # Do nothing (just saying it clearly since this part is confusing) 124 raise 125 126 missing_ranges = [] 127 128 prev_end = None 129 for range_begin, range_value in self._tree.itemslice(begin, end): 130 range_end = range_value[0] 131 # Note that we can assume that we have a range beginning with |begin| 132 # and a range ending with |end| (they may be the same range). 133 if prev_end and prev_end != range_begin: 134 missing_ranges.append((prev_end, range_begin)) 135 prev_end = range_end 136 137 for missing_begin, missing_end in missing_ranges: 138 self._tree[missing_begin] = (missing_end, self._attr()) 139 140 for range_begin, range_value in self._tree.itemslice(begin, end): 141 yield range_begin, range_value[0], range_value[1] 142 143 def __str__(self): 144 return str(self._tree) 145
