我们从Python开源项目中，提取了以下50个代码示例，用于说明如何使用bisect.bisect_left()。
def _del_timeout(self, fd): if fd._timeout_id: self._lock.acquire() i = bisect_left(self._timeouts, (fd._timeout_id, fd)) while i < len(self._timeouts): if self._timeouts[i] == (fd._timeout_id, fd): del self._timeouts[i] fd._timeout_id = None break if fd._timeout_id != self._timeouts[i][0]: logger.warning('fd %s with %s is not found', fd._fileno, fd._timeout_id) break i += 1 if self._polling: self.interrupt() self._lock.release()
def keys(self, prefix=None): if prefix is None or prefix == "" or not self._keys: return set(self._keys) if prefix.startswith(self._cachestr): lo, hi = self._cachepoints start = i = bisect_left(self._keys, prefix, lo, hi) else: start = i = bisect_left(self._keys, prefix) keys = set() if start == len(self._keys): return keys while self._keys[i].startswith(prefix): keys.add(self._keys[i]) i += 1 self._cachestr = prefix self._cachepoints = (start, i) return keys
def intranges_contain(int_, ranges): """Determine if `int_` falls into one of the ranges in `ranges`.""" tuple_ = _encode_range(int_, 0) pos = bisect.bisect_left(ranges, tuple_) # we could be immediately ahead of a tuple (start, end) # with start < int_ <= end if pos > 0: left, right = _decode_range(ranges[pos-1]) if left <= int_ < right: return True # or we could be immediately behind a tuple (int_, end) if pos < len(ranges): left, _ = _decode_range(ranges[pos]) if left == int_: return True return False
def add_region(self, reg): """ Adds single region to set while removing overlap """ # in case not given as named tuple region = Region(reg[0], reg[1]) # find where this region should go start_index = bisect.bisect_left(self.starts, region.start) end_index = bisect.bisect_left(self.ends, region.end) # merge if required if start_index > 0 and self.ends[start_index-1] > region.start: region = Region(self.starts[start_index-1], region.end) start_index -= 1 if end_index < len(self.starts) and self.starts[end_index] < region.end: region = Region(region.start, self.ends[end_index]) end_index += 1 # if no merge, insert this region in the lists if start_index == end_index: self.starts = self.starts[:start_index] + [region.start] + self.starts[start_index:] self.ends = self.ends[:start_index] + [region.end] + self.ends[start_index:] else: self.starts = self.starts[:start_index] + [region.start] + self.starts[end_index:] self.ends = self.ends[:start_index] + [region.end] + self.ends[end_index:]
def _malloc(self, size): # returns a large enough block -- it might be much larger i = bisect.bisect_left(self._lengths, size) if i == len(self._lengths): length = self._roundup(max(self._size, size), mmap.PAGESIZE) self._size *= 2 info('allocating a new mmap of length %d', length) arena = Arena(length) self._arenas.append(arena) return (arena, 0, length) else: length = self._lengths[i] seq = self._len_to_seq[length] block = seq.pop() if not seq: del self._len_to_seq[length], self._lengths[i] (arena, start, stop) = block del self._start_to_block[(arena, start)] del self._stop_to_block[(arena, stop)] return block
def binary_search(haystack, needle, returnIndex=False, onlyURI=False): lBound = 0 uBound = None surtURIsAndDatetimes = [] cdxjObj = objectifyCDXJData(haystack, onlyURI) surtURIsAndDatetimes = cdxjObj['data'] metaLineCount = len(cdxjObj['metadata']) if uBound is not None: uBound = uBound else: uBound = len(surtURIsAndDatetimes) pos = bisect_left(surtURIsAndDatetimes, needle, lBound, uBound) if pos != uBound and surtURIsAndDatetimes[pos] == needle: if returnIndex: # Index useful for adjacent line searching return pos + metaLineCount return haystack[pos + metaLineCount] else: return None
def union(self, *others): union = sortedset() union._items = list(self._items) for other in others: if isinstance(other, self.__class__): i = 0 for item in other._items: i = bisect_left(union._items, item, i) if i < len(union._items): if item != union._items[i]: union._items.insert(i, item) else: union._items.append(item) else: for item in other: union.add(item) return union
def _diff(self, other): diff = sortedset() if isinstance(other, self.__class__): i = 0 for item in self._items: i = bisect_left(other._items, item, i) if i < len(other._items): if item != other._items[i]: diff._items.append(item) else: diff._items.append(item) else: for item in self._items: if item not in other: diff.add(item) return diff
def union(self, other, find=bisect_left): i = j = 0 x = self.data y = Set._getotherdata(other) result = Set([]) append = result.data.append extend = result.data.extend try: while 1: if x[i] == y[j]: append(x[i]) i += 1 j += 1 elif x[i] > y[j]: cut = find(y, x[i], j) extend(y[j:cut]) j = cut else: cut = find(x, y[j], i) extend(x[i:cut]) i = cut except IndexError: extend(x[i:]) extend(y[j:]) return result
def intersection(self, other, find=bisect_left): i = j = 0 x = self.data y = Set._getotherdata(other) result = Set([]) append = result.data.append try: while 1: if x[i] == y[j]: append(x[i]) i += 1 j += 1 elif x[i] > y[j]: j = find(y, x[i], j) else: i = find(x, y[j], i) except IndexError: pass return result
def difference(self, other, find=bisect_left): i = j = 0 x = self.data y = Set._getotherdata(other) result = Set([]) extend = result.data.extend try: while 1: if x[i] == y[j]: i += 1 j += 1 elif x[i] > y[j]: j = find(y, x[i], j) else: cut = find(x, y[j], i) extend(x[i:cut]) i = cut except IndexError: extend(x[i:]) return result
def __getitem__(self, key): bounds, values = self._bounds, self._values if hasattr(key, 'start') and hasattr(key, 'stop'): # we are indexing with an interval. we only return the value # if that interval is contained within one of our intervals. start, stop = key.start, key.stop lindex = bisect_right(bounds, start) if start is not None else 0 rindex = (bisect_left(bounds, stop) if stop is not None else len(bounds)) if lindex != rindex: raise KeyError(key) return values[lindex] else: # We are indexing with a single element. result = values[bisect_right(bounds, key)] if result is self.nothing: raise KeyError(key) return result
def submapping(self, start, stop): bounds, values, nothing = self._bounds, self._values, self.nothing lindex = bisect_right(bounds, start) if start is not None else 0 rindex = (bisect_left(bounds, stop) if stop is not None else len(bounds)) res = type(self)() res._bounds = blist(bounds[lindex:rindex]) res._values = blist(values[lindex:rindex + 1]) if start is not None: res[:start] = nothing if stop is not None: res[stop:] = nothing return res
def contains(self, *args): if len(args) == 1 and isinstance(args[0], Cell): return self.contains(args[0].id()) elif len(args) == 1 and isinstance(args[0], CellId): cell_id = args[0] index = bisect.bisect_left(self.__cell_ids, cell_id) if index < len(self.__cell_ids) \ and self.__cell_ids[index].range_min() <= cell_id: return True return (index != 0 and self.__cell_ids[index - 1].range_max() >= cell_id) elif len(args) == 1 and isinstance(args[0], Point): return self.contains(CellId.from_point(args[0])) elif len(args) == 1 and isinstance(args[0], self.__class__): cell_union = args[0] for i in range(cell_union.num_cells()): if not self.contains(cell_union.cell_id(i)): return False return True else: raise NotImplementedError()
def intersects(self, *args): if len(args) == 1 and isinstance(args[0], CellId): cell_id = args[0] index = bisect.bisect_left(self.__cell_ids, cell_id) if index != len(self.__cell_ids) and \ self.__cell_ids[index].range_min() <= cell_id.range_max(): return True return ( index != 0 and self.__cell_ids[index - 1].range_max() >= cell_id.range_min() ) elif len(args) == 1 and isinstance(args[0], CellUnion): cell_union = args[0] for cell_id in cell_union.__cell_ids: if self.intersects(cell_id): return True return False else: raise NotImplementedError()
def intranges_contain(int_, ranges): """Determine if `int_` falls into one of the ranges in `ranges`.""" tuple_ = (int_, int_) pos = bisect.bisect_left(ranges, tuple_) # we could be immediately ahead of a tuple (start, end) # with start < int_ <= end if pos > 0: left, right = ranges[pos-1] if left <= int_ < right: return True # or we could be immediately behind a tuple (int_, end) if pos < len(ranges): left, _ = ranges[pos] if left == int_: return True return False
def add(self, i): data = self.data if not data or i > data[-1]: data.append(i) else: mn = data[0] mx = data[-1] if i == mn or i == mx: return elif i > mx: data.append(i) elif i < mn: data.insert(0, i) else: pos = bisect_left(data, i) if data[pos] != i: data.insert(pos, i)
def find_next_edge(self, s, label, asbytes): if label is None: label = b"\x00" if asbytes else u'\0' else: label = (label + 1) if asbytes else unichr(ord(label) + 1) trans = self.transitions.get(s, {}) if label in trans or s in self.defaults: return label try: labels = self.outlabels[s] except KeyError: self.outlabels[s] = labels = sorted(trans) pos = bisect_left(labels, label) if pos < len(labels): return labels[pos] return None
def get(cls, uni_char): """Return the Unicode block of the given Unicode character""" uni_char = unicod(uni_char) # Force to Unicode code_point = ord(uni_char) if Block._RANGE_KEYS is None: Block._RANGE_KEYS = sorted(Block._RANGES.keys()) idx = bisect.bisect_left(Block._RANGE_KEYS, code_point) if (idx > 0 and code_point >= Block._RANGES[Block._RANGE_KEYS[idx - 1]].start and code_point <= Block._RANGES[Block._RANGE_KEYS[idx - 1]].end): return Block._RANGES[Block._RANGE_KEYS[idx - 1]] elif (idx < len(Block._RANGES) and code_point >= Block._RANGES[Block._RANGE_KEYS[idx]].start and code_point <= Block._RANGES[Block._RANGE_KEYS[idx]].end): return Block._RANGES[Block._RANGE_KEYS[idx]] else: return Block.UNKNOWN
def predict(self, t_new): """ Use the segments in this model to predict the v value for new t values. Params: t_new (np.array): t values for which predictions should be made Returns: np.array of predictions """ v_hats = np.empty_like(t_new, dtype=float) for idx, t in enumerate(t_new): # Find the applicable segment. seg_index = bisect.bisect_left(self._starts, t) - 1 seg = self.segments[max(0, seg_index)] # Use it for prediction v_hats[idx] = seg.predict(t) return v_hats ## Data structures used during the fitting of the regression in `piecewise()`. # Segment represents a time range and a linear regression fit through it.
def _decorated_list_slice(dec_list, starttime=None, endtime=None, ffill=False): """Get slice for sorted list of tuples with (time, ...).""" ks = 0 ke = len(dec_list) if starttime is not None: # (because of tuple comparison, all bisects are left) # dec_list[:ks][0] < starttime <= dec_list[ks:][0] ks = bisect.bisect_left(dec_list, (starttime,)) # forward fill, first index where dec_list[ks][0] <= starttime if ffill and (ks == len(dec_list) or dec_list[ks][0] > starttime): ks = max(ks - 1, 0) if endtime is not None: # (because of tuple comparison, all bisects are left) # dec_list[:ke][0] < endtime <= dec_list[ke:][0] ke = bisect.bisect_left(dec_list, (endtime,), lo=ks) # make ke first index to exclude if ke < len(dec_list) and dec_list[ke][0] == endtime: ke = ke + 1 return slice(ks, ke)
def maxSumSubmatrix(self, matrix, k): """ :type matrix: List[List[int]] :type k: int :rtype: int """ ans = float("-inf") dp = [[0] * len(matrix[0]) for _ in range(len(matrix))] for i in range(0, len(matrix)): for j in range(0, len(matrix[0])): dp[i][j] = dp[i][j - 1] + matrix[i][j] for start in range(0, len(matrix[0])): for end in range(start, len(matrix[0])): sums = [0] subsum = 0 for i in range(0, len(matrix)): if start > 0: subsum += dp[i][end] - dp[i][start - 1] else: subsum += dp[i][end] idx = bisect.bisect_left(sums, subsum - k) if idx < len(sums): ans = max(ans, subsum - sums[idx]) bisect.insort(sums, subsum) return ans
def findClosestElements(self, arr, k, x): """ :type arr: List[int] :type k: int :type x: int :rtype: List[int] """ left = right = bisect.bisect_left(arr, x) while right - left < k: if left == 0: return arr[:k] if right == len(arr): return arr[-k:] if x - arr[left - 1] <= arr[right] - x: left -= 1 else: right += 1 return arr[left:right]
