def get_cat_ids(self, idx):
        """Get category ids of concatenated dataset by index.

        Args:
            idx (int): Index of data.

        Returns:
            list[int]: All categories in the image of specified index.
        """

        if idx < 0:
            if -idx > len(self):
                raise ValueError(
                    'absolute value of index should not exceed dataset length')
            idx = len(self) + idx
        dataset_idx = bisect.bisect_right(self.cumulative_sizes, idx)
        if dataset_idx == 0:
            sample_idx = idx
        else:
            sample_idx = idx - self.cumulative_sizes[dataset_idx - 1]
        return self.datasets[dataset_idx].get_cat_ids(sample_idx) 

def iterate_from(self, start_tok):
        piecenum = bisect.bisect_right(self._offsets, start_tok)-1

        while piecenum < len(self._pieces):
            offset = self._offsets[piecenum]
            piece = self._pieces[piecenum]

            # If we've got another piece open, close it first.
            if self._open_piece is not piece:
                if self._open_piece is not None:
                    self._open_piece.close()
                self._open_piece = piece

            # Get everything we can from this piece.
            for tok in piece.iterate_from(max(0, start_tok-offset)):
                yield tok

            # Update the offset table.
            if piecenum+1 == len(self._offsets):
                self._offsets.append(self._offsets[-1] + len(piece))

            # Move on to the next piece.
            piecenum += 1 

def bisect_right(self, value):
        """Return an index to insert `value` in the sorted-key list.

        Similar to `bisect_left`, but if `value` is already present, the
        insertion point with be after (to the right of) any existing values.

        Similar to the `bisect` module in the standard library.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> from operator import neg
        >>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
        >>> skl.bisect_right(1)
        5

        :param value: insertion index of value in sorted-key list
        :return: index

        """
        return self._bisect_key_right(self._key(value)) 

def bisect_right(self, value):
        """Return an index to insert `value` in the sorted-key list.

        Similar to `bisect_left`, but if `value` is already present, the
        insertion point with be after (to the right of) any existing values.

        Similar to the `bisect` module in the standard library.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> from operator import neg
        >>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
        >>> skl.bisect_right(1)
        5

        :param value: insertion index of value in sorted-key list
        :return: index

        """
        return self._bisect_key_right(self._key(value)) 

def bisect_right(self, value):
        """Return an index to insert `value` in the sorted-key list.

        Similar to `bisect_left`, but if `value` is already present, the
        insertion point with be after (to the right of) any existing values.

        Similar to the `bisect` module in the standard library.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> from operator import neg
        >>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
        >>> skl.bisect_right(1)
        5

        :param value: insertion index of value in sorted-key list
        :return: index

        """
        return self._bisect_key_right(self._key(value)) 

def bisect_right(self, value):
        """Return an index to insert `value` in the sorted-key list.

        Similar to `bisect_left`, but if `value` is already present, the
        insertion point with be after (to the right of) any existing values.

        Similar to the `bisect` module in the standard library.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> from operator import neg
        >>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
        >>> skl.bisect_right(1)
        5

        :param value: insertion index of value in sorted-key list
        :return: index

        """
        return self._bisect_key_right(self._key(value)) 

def get_statement_startend2(lineno, node):
    import ast
    # flatten all statements and except handlers into one lineno-list
    # AST's line numbers start indexing at 1
    l = []
    for x in ast.walk(node):
        if isinstance(x, _ast.stmt) or isinstance(x, _ast.ExceptHandler):
            l.append(x.lineno - 1)
            for name in "finalbody", "orelse":
                val = getattr(x, name, None)
                if val:
                    # treat the finally/orelse part as its own statement
                    l.append(val[0].lineno - 1 - 1)
    l.sort()
    insert_index = bisect_right(l, lineno)
    start = l[insert_index - 1]
    if insert_index >= len(l):
        end = None
    else:
        end = l[insert_index]
    return start, end 

def get_last_full_moon(d):
    """
    Returns the last full moon for d

    Raises ValueError if the d value is not between 2000 - 2099
    """

    now = d.timestamp
    idx = bisect.bisect_right(fullmoons, now)
    if idx in [0, len(fullmoons)]:
        raise ValueError(
            u'watson has only full moon dates from year 2000 to 2099, not {}'
            .format(d.year))

    last = fullmoons[idx - 1]
    return arrow.get(last) 

def Add(self, score):
    """Add a score into the last N scores.

    If needed, drops the score that is furthest away from the given score.
    """
    num_sampled_scores = len(self.scores)
    if num_sampled_scores < self.MAX_NUM_SAMPLED_SCORES:
      bisect.insort(self.scores, score)
    else:
      index_left = bisect.bisect_left(self.scores, score)
      index_right = bisect.bisect_right(self.scores, score)
      index_center = index_left + (index_right - index_left) / 2
      self.scores.insert(index_left, score)
      if index_center < num_sampled_scores / 2:
        self.scores.pop()
      else:
        self.scores.pop(0)
    self.num_scores += 1 

def Add(self, score):
    """Add a score into the last N scores.

    If needed, drops the score that is furthest away from the given score.
    """
    num_sampled_scores = len(self.scores)
    if num_sampled_scores < self.MAX_NUM_SAMPLED_SCORES:
      bisect.insort(self.scores, score)
    else:
      index_left = bisect.bisect_left(self.scores, score)
      index_right = bisect.bisect_right(self.scores, score)
      index_center = index_left + (index_right - index_left) / 2
      self.scores.insert(index_left, score)
      if index_center < num_sampled_scores / 2:
        self.scores.pop()
      else:
        self.scores.pop(0)
    self.num_scores += 1
    RankerCacher.CachePut(self) 

def get_ancestral_haplotypes(ts):
    """
    Returns a numpy array of the haplotypes of the ancestors in the
    specified tree sequence.
    """
    tables = ts.dump_tables()
    nodes = tables.nodes
    flags = nodes.flags[:]
    flags[:] = 1
    nodes.set_columns(time=nodes.time, flags=flags)

    sites = tables.sites.position
    tsp = tables.tree_sequence()
    B = tsp.genotype_matrix().T

    A = np.full((ts.num_nodes, ts.num_sites), tskit.MISSING_DATA, dtype=np.int8)
    for edge in ts.edges():
        start = bisect.bisect_left(sites, edge.left)
        end = bisect.bisect_right(sites, edge.right)
        if sites[end - 1] == edge.right:
            end -= 1
        A[edge.parent, start:end] = B[edge.parent, start:end]
    A[: ts.num_samples] = B[: ts.num_samples]
    return A 

def query_by_time(self, category, time_start=None, time_end=None):
        self._purge_old_events(category)

        class ItemWrapper(object):
            def __init__(self, tl):
                self._l = tl

            def __getitem__(self, item):
                return self._l[item][0]

            def __len__(self):
                return len(self._l)

        timeline = self._event_timelines[category]
        left_pos = 0 if time_start is None \
            else bisect.bisect_left(ItemWrapper(timeline), time_start)
        right_pos = len(timeline) if time_end is None \
            else bisect.bisect_right(ItemWrapper(timeline), time_end)
        return [it[1] for it in itertools.islice(timeline, left_pos, right_pos)] 

def _find_nearest_size(self, size_candidate):
        index = bisect.bisect_right(self._possible_sizes, size_candidate)

        if index == 0:
            return self._possible_sizes[0]

        if index >= len(self._possible_sizes):
            return self._possible_sizes[-1]

        right_size = self._possible_sizes[index]
        left_size = self._possible_sizes[index - 1]

        if abs(size_candidate - right_size) < abs(size_candidate - left_size):
            return right_size
        else:
            return left_size 

def get_statement_startend2(lineno, node):
    import ast

    # flatten all statements and except handlers into one lineno-list
    # AST's line numbers start indexing at 1
    values = []
    for x in ast.walk(node):
        if isinstance(x, (ast.stmt, ast.ExceptHandler)):
            values.append(x.lineno - 1)
            for name in ("finalbody", "orelse"):
                val = getattr(x, name, None)
                if val:
                    # treat the finally/orelse part as its own statement
                    values.append(val[0].lineno - 1 - 1)
    values.sort()
    insert_index = bisect_right(values, lineno)
    start = values[insert_index - 1]
    if insert_index >= len(values):
        end = None
    else:
        end = values[insert_index]
    return start, end 

def get_statement_startend2(lineno, node):
    import ast
    # flatten all statements and except handlers into one lineno-list
    # AST's line numbers start indexing at 1
    l = []
    for x in ast.walk(node):
        if isinstance(x, _ast.stmt) or isinstance(x, _ast.ExceptHandler):
            l.append(x.lineno - 1)
            for name in "finalbody", "orelse":
                val = getattr(x, name, None)
                if val:
                    # treat the finally/orelse part as its own statement
                    l.append(val[0].lineno - 1 - 1)
    l.sort()
    insert_index = bisect_right(l, lineno)
    start = l[insert_index - 1]
    if insert_index >= len(l):
        end = None
    else:
        end = l[insert_index]
    return start, end 

def get_statement_startend2(lineno, node):
    import ast

    # flatten all statements and except handlers into one lineno-list
    # AST's line numbers start indexing at 1
    values = []
    for x in ast.walk(node):
        if isinstance(x, (ast.stmt, ast.ExceptHandler)):
            values.append(x.lineno - 1)
            for name in ("finalbody", "orelse"):
                val = getattr(x, name, None)
                if val:
                    # treat the finally/orelse part as its own statement
                    values.append(val[0].lineno - 1 - 1)
    values.sort()
    insert_index = bisect_right(values, lineno)
    start = values[insert_index - 1]
    if insert_index >= len(values):
        end = None
    else:
        end = values[insert_index]
    return start, end 

def get_statement_startend2(lineno, node):
    import ast
    # flatten all statements and except handlers into one lineno-list
    # AST's line numbers start indexing at 1
    l = []
    for x in ast.walk(node):
        if isinstance(x, _ast.stmt) or isinstance(x, _ast.ExceptHandler):
            l.append(x.lineno - 1)
            for name in "finalbody", "orelse":
                val = getattr(x, name, None)
                if val:
                    # treat the finally/orelse part as its own statement
                    l.append(val[0].lineno - 1 - 1)
    l.sort()
    insert_index = bisect_right(l, lineno)
    start = l[insert_index - 1]
    if insert_index >= len(l):
        end = None
    else:
        end = l[insert_index]
    return start, end 

def find_module(modlist, mod_addrs, addr):
    """Uses binary search to find what module a given address resides in.

    This is much faster than a series of linear checks if you have
    to do it many times. Note that modlist and mod_addrs must be sorted
    in order of the module base address.
    
    NOTE: the mod_addrs and addr parameters must already be masked for 
    the address space"""

    pos = bisect_right(mod_addrs, addr) - 1
    if pos == -1:
        return None
    mod = modlist[mod_addrs[pos]]

    if (mod.obj_vm.address_compare(addr, mod.DllBase) != -1 and
            mod.obj_vm.address_compare(addr, mod.DllBase + mod.SizeOfImage) == -1):
        return mod
    else:
        return None 

def find_module(cls, modlist, mod_addrs, addr_space, vpage):
        """Determine which module owns a virtual page. 

        :param      modlist     | <list>
                    mod_addrs   | <list>
                    addr_space  | <addrspace.AbstractVirtualAddressSpace>
                    vpage       | <int> 
        
        :returns    <module> || None
        """

        pos = bisect_right(mod_addrs, vpage) - 1
        if pos == -1:
            return None
        mod = modlist[mod_addrs[pos]]

        compare = mod.obj_vm.address_compare
        if (compare(vpage, mod.module_core) != -1 and
                compare(vpage, mod.module_core + mod.core_size) == -1):
            return mod
        else:
            return None 

def find_module(cls, modlist, mod_addrs, addr_space, vpage):
        """Determine which module owns a virtual page. 

        :param      modlist     | <list>
                    mod_addrs   | <list>
                    addr_space  | <addrspace.AbstractVirtualAddressSpace>
                    vpage       | <int> 
        
        :returns    <module> || None
        """

        pos = bisect_right(mod_addrs, vpage) - 1
        if pos == -1:
            return None
        mod = modlist[mod_addrs[pos]]

        compare = mod.obj_vm.address_compare
        if (compare(vpage, mod.address) != -1 and
                compare(vpage, mod.address + mod.m('size')) == -1):
            return mod
        else:
            return None 

def getMxCompatibility(version):
    """:rtype: MxCompatibility500"""
    if version < minVersion():  # ensures compat loaded
        return None
    keys = list(_versionsMap.keys())
    return _versionsMap[keys[bisect.bisect_right(keys, version)-1]] 

def iterate_from(self, start_index):
        if start_index < self._offsets[-1]:
            sublist_index = bisect.bisect_right(self._offsets, start_index)-1
        else:
            sublist_index = len(self._offsets)-1

        index = self._offsets[sublist_index]

        # Construct an iterator over the sublists.
        if isinstance(self._list, AbstractLazySequence):
            sublist_iter = self._list.iterate_from(sublist_index)
        else:
            sublist_iter = islice(self._list, sublist_index, None)

        for sublist in sublist_iter:
            if sublist_index == (len(self._offsets)-1):
                assert index+len(sublist) >= self._offsets[-1], (
                        'offests not monotonic increasing!')
                self._offsets.append(index+len(sublist))
            else:
                assert self._offsets[sublist_index+1] == index+len(sublist), (
                        'inconsistent list value (num elts)')

            for value in sublist[max(0, start_index-index):]:
                yield value

            index += len(sublist)
            sublist_index += 1 

def get_example(self, i: int) -> Any:
        j = bisect.bisect_right(self._lengths, i)
        return self._datasets[j][i - self._offsets[j]] 

def __getitem__(self, frame_nr):
        # Keep default case of no offsets as fast as possible.
        base = frame_nr * self.frame_nbytes
        if not self.frame_nr:
            return base
        # Find first index for which frame_nr < value-at-index,
        # hence the offset at the previous index is the one we need.
        index = bisect.bisect_right(self.frame_nr, frame_nr)
        return base if index == 0 else base + self.offset[index - 1] 

def __setitem__(self, frame_nr, offset):
        # Get the offset from expected.
        offset -= frame_nr * self.frame_nbytes
        # Find first index for which frame_nr < value-at-index.
        # Hence, this is where we should be if we do not yet exist.
        index = bisect.bisect_right(self.frame_nr, frame_nr)
        # If the entry already exists (should not really happen),
        # and the new value is different, replace it.
        if index > 0 and self.frame_nr[index-1] == frame_nr:
            if self.offset[index-1] == offset:
                return

            # Best to *remove* the entry, since the new value may
            # be consistent with one of the surrounding values,
            # in which case we can shorten our list.
            self.frame_nr.pop(index-1)
            self.offset.pop(index-1)
            index -= 1

        # If the offset at the next location is the same as ours,
        # then we can keep everything consistent by just moving the
        # frame number to our value.
        if index < len(self) and self.offset[index] == offset:
            self.frame_nr[index] = frame_nr
        elif index == 0 or self.offset[index-1] != offset:
            # Otherwise, if we add new information, insert ourserlves.
            self.frame_nr.insert(index, frame_nr)
            self.offset.insert(index, offset) 

def add(self, value):
        """Add `value` to sorted list.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList()
        >>> sl.add(3)
        >>> sl.add(1)
        >>> sl.add(2)
        >>> sl
        SortedList([1, 2, 3])

        :param value: value to add to sorted list

        """
        _lists = self._lists
        _maxes = self._maxes

        if _maxes:
            pos = bisect_right(_maxes, value)

            if pos == len(_maxes):
                pos -= 1
                _lists[pos].append(value)
                _maxes[pos] = value
            else:
                insort(_lists[pos], value)

            self._expand(pos)
        else:
            _lists.append([value])
            _maxes.append(value)

        self._len += 1 

def bisect_right(self, value):
        """Return an index to insert `value` in the sorted list.

        Similar to `bisect_left`, but if `value` is already present, the
        insertion point with be after (to the right of) any existing values.

        Similar to the `bisect` module in the standard library.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList([10, 11, 12, 13, 14])
        >>> sl.bisect_right(12)
        3

        :param value: insertion index of value in sorted list
        :return: index

        """
        _maxes = self._maxes

        if not _maxes:
            return 0

        pos = bisect_right(_maxes, value)

        if pos == len(_maxes):
            return self._len

        idx = bisect_right(self._lists[pos], value)
        return self._loc(pos, idx) 

def count(self, value):
        """Return number of occurrences of `value` in the sorted list.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList([1, 2, 2, 3, 3, 3, 4, 4, 4, 4])
        >>> sl.count(3)
        3

        :param value: value to count in sorted list
        :return: count

        """
        _maxes = self._maxes

        if not _maxes:
            return 0

        pos_left = bisect_left(_maxes, value)

        if pos_left == len(_maxes):
            return 0

        _lists = self._lists
        idx_left = bisect_left(_lists[pos_left], value)
        pos_right = bisect_right(_maxes, value)

        if pos_right == len(_maxes):
            return self._len - self._loc(pos_left, idx_left)

        idx_right = bisect_right(_lists[pos_right], value)

        if pos_left == pos_right:
            return idx_right - idx_left

        right = self._loc(pos_right, idx_right)
        left = self._loc(pos_left, idx_left)
        return right - left 

def add(self, value):
        """Add `value` to sorted list.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList()
        >>> sl.add(3)
        >>> sl.add(1)
        >>> sl.add(2)
        >>> sl
        SortedList([1, 2, 3])

        :param value: value to add to sorted list

        """
        _lists = self._lists
        _maxes = self._maxes

        if _maxes:
            pos = bisect_right(_maxes, value)

            if pos == len(_maxes):
                pos -= 1
                _lists[pos].append(value)
                _maxes[pos] = value
            else:
                insort(_lists[pos], value)

            self._expand(pos)
        else:
            _lists.append([value])
            _maxes.append(value)

        self._len += 1 

def bisect_right(self, value):
        """Return an index to insert `value` in the sorted list.

        Similar to `bisect_left`, but if `value` is already present, the
        insertion point with be after (to the right of) any existing values.

        Similar to the `bisect` module in the standard library.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sl = SortedList([10, 11, 12, 13, 14])
        >>> sl.bisect_right(12)
        3

        :param value: insertion index of value in sorted list
        :return: index

        """
        _maxes = self._maxes

        if not _maxes:
            return 0

        pos = bisect_right(_maxes, value)

        if pos == len(_maxes):
            return self._len

        idx = bisect_right(self._lists[pos], value)
        return self._loc(pos, idx)