codekingpro/portable-devtools
115k
1"""Sorted List2==============3 4:doc:`Sorted Containers<index>` is an Apache2 licensed Python sorted5collections library, written in pure-Python, and fast as C-extensions. The6:doc:`introduction<introduction>` is the best way to get started.7 8Sorted list implementations:9 10.. currentmodule:: sortedcontainers11 12* :class:`SortedList`13* :class:`SortedKeyList`14 15"""16# pylint: disable=too-many-lines17from __future__ import print_function18 19import sys20import traceback21 22from bisect import bisect_left, bisect_right, insort23from itertools import chain, repeat, starmap24from math import log25from operator import add, eq, ne, gt, ge, lt, le, iadd26from textwrap import dedent27 28###############################################################################29# BEGIN Python 2/3 Shims30###############################################################################31 32try:33 from collections.abc import Sequence, MutableSequence34except ImportError:35 from collections import Sequence, MutableSequence36 37from functools import wraps38from sys import hexversion39 40if hexversion < 0x03000000:41 from itertools import imap as map # pylint: disable=redefined-builtin42 from itertools import izip as zip # pylint: disable=redefined-builtin43 try:44 from thread import get_ident45 except ImportError:46 from dummy_thread import get_ident47else:48 from functools import reduce49 try:50 from _thread import get_ident51 except ImportError:52 from _dummy_thread import get_ident53 54 55def recursive_repr(fillvalue='...'):56 "Decorator to make a repr function return fillvalue for a recursive call."57 # pylint: disable=missing-docstring58 # Copied from reprlib in Python 359 # https://hg.python.org/cpython/file/3.6/Lib/reprlib.py60 61 def decorating_function(user_function):62 repr_running = set()63 64 @wraps(user_function)65 def wrapper(self):66 key = id(self), get_ident()67 if key in repr_running:68 return fillvalue69 repr_running.add(key)70 try:71 result = user_function(self)72 finally:73 repr_running.discard(key)74 return result75 76 return wrapper77 78 return decorating_function79 80###############################################################################81# END Python 2/3 Shims82###############################################################################83 84 85class SortedList(MutableSequence):86 """Sorted list is a sorted mutable sequence.87 88 Sorted list values are maintained in sorted order.89 90 Sorted list values must be comparable. The total ordering of values must91 not change while they are stored in the sorted list.92 93 Methods for adding values:94 95 * :func:`SortedList.add`96 * :func:`SortedList.update`97 * :func:`SortedList.__add__`98 * :func:`SortedList.__iadd__`99 * :func:`SortedList.__mul__`100 * :func:`SortedList.__imul__`101 102 Methods for removing values:103 104 * :func:`SortedList.clear`105 * :func:`SortedList.discard`106 * :func:`SortedList.remove`107 * :func:`SortedList.pop`108 * :func:`SortedList.__delitem__`109 110 Methods for looking up values:111 112 * :func:`SortedList.bisect_left`113 * :func:`SortedList.bisect_right`114 * :func:`SortedList.count`115 * :func:`SortedList.index`116 * :func:`SortedList.__contains__`117 * :func:`SortedList.__getitem__`118 119 Methods for iterating values:120 121 * :func:`SortedList.irange`122 * :func:`SortedList.islice`123 * :func:`SortedList.__iter__`124 * :func:`SortedList.__reversed__`125 126 Methods for miscellany:127 128 * :func:`SortedList.copy`129 * :func:`SortedList.__len__`130 * :func:`SortedList.__repr__`131 * :func:`SortedList._check`132 * :func:`SortedList._reset`133 134 Sorted lists use lexicographical ordering semantics when compared to other135 sequences.136 137 Some methods of mutable sequences are not supported and will raise138 not-implemented error.139 140 """141 DEFAULT_LOAD_FACTOR = 1000142 143 144 def __init__(self, iterable=None, key=None):145 """Initialize sorted list instance.146 147 Optional `iterable` argument provides an initial iterable of values to148 initialize the sorted list.149 150 Runtime complexity: `O(n*log(n))`151 152 >>> sl = SortedList()153 >>> sl154 SortedList([])155 >>> sl = SortedList([3, 1, 2, 5, 4])156 >>> sl157 SortedList([1, 2, 3, 4, 5])158 159 :param iterable: initial values (optional)160 161 """162 assert key is None163 self._len = 0164 self._load = self.DEFAULT_LOAD_FACTOR165 self._lists = []166 self._maxes = []167 self._index = []168 self._offset = 0169 170 if iterable is not None:171 self._update(iterable)172 173 174 def __new__(cls, iterable=None, key=None):175 """Create new sorted list or sorted-key list instance.176 177 Optional `key`-function argument will return an instance of subtype178 :class:`SortedKeyList`.179 180 >>> sl = SortedList()181 >>> isinstance(sl, SortedList)182 True183 >>> sl = SortedList(key=lambda x: -x)184 >>> isinstance(sl, SortedList)185 True186 >>> isinstance(sl, SortedKeyList)187 True188 189 :param iterable: initial values (optional)190 :param key: function used to extract comparison key (optional)191 :return: sorted list or sorted-key list instance192 193 """194 # pylint: disable=unused-argument195 if key is None:196 return object.__new__(cls)197 else:198 if cls is SortedList:199 return object.__new__(SortedKeyList)200 else:201 raise TypeError('inherit SortedKeyList for key argument')202 203 204 @property205 def key(self): # pylint: disable=useless-return206 """Function used to extract comparison key from values.207 208 Sorted list compares values directly so the key function is none.209 210 """211 return None212 213 214 def _reset(self, load):215 """Reset sorted list load factor.216 217 The `load` specifies the load-factor of the list. The default load218 factor of 1000 works well for lists from tens to tens-of-millions of219 values. Good practice is to use a value that is the cube root of the220 list size. With billions of elements, the best load factor depends on221 your usage. It's best to leave the load factor at the default until you222 start benchmarking.223 224 See :doc:`implementation` and :doc:`performance-scale` for more225 information.226 227 Runtime complexity: `O(n)`228 229 :param int load: load-factor for sorted list sublists230 231 """232 values = reduce(iadd, self._lists, [])233 self._clear()234 self._load = load235 self._update(values)236 237 238 def clear(self):239 """Remove all values from sorted list.240 241 Runtime complexity: `O(n)`242 243 """244 self._len = 0245 del self._lists[:]246 del self._maxes[:]247 del self._index[:]248 self._offset = 0249 250 _clear = clear251 252 253 def add(self, value):254 """Add `value` to sorted list.255 256 Runtime complexity: `O(log(n))` -- approximate.257 258 >>> sl = SortedList()259 >>> sl.add(3)260 >>> sl.add(1)261 >>> sl.add(2)262 >>> sl263 SortedList([1, 2, 3])264 265 :param value: value to add to sorted list266 267 """268 _lists = self._lists269 _maxes = self._maxes270 271 if _maxes:272 pos = bisect_right(_maxes, value)273 274 if pos == len(_maxes):275 pos -= 1276 _lists[pos].append(value)277 _maxes[pos] = value278 else:279 insort(_lists[pos], value)280 281 self._expand(pos)282 else:283 _lists.append([value])284 _maxes.append(value)285 286 self._len += 1287 288 289 def _expand(self, pos):290 """Split sublists with length greater than double the load-factor.291 292 Updates the index when the sublist length is less than double the load293 level. This requires incrementing the nodes in a traversal from the294 leaf node to the root. For an example traversal see295 ``SortedList._loc``.296 297 """298 _load = self._load299 _lists = self._lists300 _index = self._index301 302 if len(_lists[pos]) > (_load << 1):303 _maxes = self._maxes304 305 _lists_pos = _lists[pos]306 half = _lists_pos[_load:]307 del _lists_pos[_load:]308 _maxes[pos] = _lists_pos[-1]309 310 _lists.insert(pos + 1, half)311 _maxes.insert(pos + 1, half[-1])312 313 del _index[:]314 else:315 if _index:316 child = self._offset + pos317 while child:318 _index[child] += 1319 child = (child - 1) >> 1320 _index[0] += 1321 322 323 def update(self, iterable):324 """Update sorted list by adding all values from `iterable`.325 326 Runtime complexity: `O(k*log(n))` -- approximate.327 328 >>> sl = SortedList()329 >>> sl.update([3, 1, 2])330 >>> sl331 SortedList([1, 2, 3])332 333 :param iterable: iterable of values to add334 335 """336 _lists = self._lists337 _maxes = self._maxes338 values = sorted(iterable)339 340 if _maxes:341 if len(values) * 4 >= self._len:342 _lists.append(values)343 values = reduce(iadd, _lists, [])344 values.sort()345 self._clear()346 else:347 _add = self.add348 for val in values:349 _add(val)350 return351 352 _load = self._load353 _lists.extend(values[pos:(pos + _load)]354 for pos in range(0, len(values), _load))355 _maxes.extend(sublist[-1] for sublist in _lists)356 self._len = len(values)357 del self._index[:]358 359 _update = update360 361 362 def __contains__(self, value):363 """Return true if `value` is an element of the sorted list.364 365 ``sl.__contains__(value)`` <==> ``value in sl``366 367 Runtime complexity: `O(log(n))`368 369 >>> sl = SortedList([1, 2, 3, 4, 5])370 >>> 3 in sl371 True372 373 :param value: search for value in sorted list374 :return: true if `value` in sorted list375 376 """377 _maxes = self._maxes378 379 if not _maxes:380 return False381 382 pos = bisect_left(_maxes, value)383 384 if pos == len(_maxes):385 return False386 387 _lists = self._lists388 idx = bisect_left(_lists[pos], value)389 390 return _lists[pos][idx] == value391 392 393 def discard(self, value):394 """Remove `value` from sorted list if it is a member.395 396 If `value` is not a member, do nothing.397 398 Runtime complexity: `O(log(n))` -- approximate.399 400 >>> sl = SortedList([1, 2, 3, 4, 5])401 >>> sl.discard(5)402 >>> sl.discard(0)403 >>> sl == [1, 2, 3, 4]404 True405 406 :param value: `value` to discard from sorted list407 408 """409 _maxes = self._maxes410 411 if not _maxes:412 return413 414 pos = bisect_left(_maxes, value)415 416 if pos == len(_maxes):417 return418 419 _lists = self._lists420 idx = bisect_left(_lists[pos], value)421 422 if _lists[pos][idx] == value:423 self._delete(pos, idx)424 425 426 def remove(self, value):427 """Remove `value` from sorted list; `value` must be a member.428 429 If `value` is not a member, raise ValueError.430 431 Runtime complexity: `O(log(n))` -- approximate.432 433 >>> sl = SortedList([1, 2, 3, 4, 5])434 >>> sl.remove(5)435 >>> sl == [1, 2, 3, 4]436 True437 >>> sl.remove(0)438 Traceback (most recent call last):439 ...440 ValueError: 0 not in list441 442 :param value: `value` to remove from sorted list443 :raises ValueError: if `value` is not in sorted list444 445 """446 _maxes = self._maxes447 448 if not _maxes:449 raise ValueError('{0!r} not in list'.format(value))450 451 pos = bisect_left(_maxes, value)452 453 if pos == len(_maxes):454 raise ValueError('{0!r} not in list'.format(value))455 456 _lists = self._lists457 idx = bisect_left(_lists[pos], value)458 459 if _lists[pos][idx] == value:460 self._delete(pos, idx)461 else:462 raise ValueError('{0!r} not in list'.format(value))463 464 465 def _delete(self, pos, idx):466 """Delete value at the given `(pos, idx)`.467 468 Combines lists that are less than half the load level.469 470 Updates the index when the sublist length is more than half the load471 level. This requires decrementing the nodes in a traversal from the472 leaf node to the root. For an example traversal see473 ``SortedList._loc``.474 475 :param int pos: lists index476 :param int idx: sublist index477 478 """479 _lists = self._lists480 _maxes = self._maxes481 _index = self._index482 483 _lists_pos = _lists[pos]484 485 del _lists_pos[idx]486 self._len -= 1487 488 len_lists_pos = len(_lists_pos)489 490 if len_lists_pos > (self._load >> 1):491 _maxes[pos] = _lists_pos[-1]492 493 if _index:494 child = self._offset + pos495 while child > 0:496 _index[child] -= 1497 child = (child - 1) >> 1498 _index[0] -= 1499 elif len(_lists) > 1:500 if not pos:501 pos += 1502 503 prev = pos - 1504 _lists[prev].extend(_lists[pos])505 _maxes[prev] = _lists[prev][-1]506 507 del _lists[pos]508 del _maxes[pos]509 del _index[:]510 511 self._expand(prev)512 elif len_lists_pos:513 _maxes[pos] = _lists_pos[-1]514 else:515 del _lists[pos]516 del _maxes[pos]517 del _index[:]518 519 520 def _loc(self, pos, idx):521 """Convert an index pair (lists index, sublist index) into a single522 index number that corresponds to the position of the value in the523 sorted list.524 525 Many queries require the index be built. Details of the index are526 described in ``SortedList._build_index``.527 528 Indexing requires traversing the tree from a leaf node to the root. The529 parent of each node is easily computable at ``(pos - 1) // 2``.530 531 Left-child nodes are always at odd indices and right-child nodes are532 always at even indices.533 534 When traversing up from a right-child node, increment the total by the535 left-child node.536 537 The final index is the sum from traversal and the index in the sublist.538 539 For example, using the index from ``SortedList._build_index``::540 541 _index = 14 5 9 3 2 4 5542 _offset = 3543 544 Tree::545 546 14547 5 9548 3 2 4 5549 550 Converting an index pair (2, 3) into a single index involves iterating551 like so:552 553 1. Starting at the leaf node: offset + alpha = 3 + 2 = 5. We identify554 the node as a left-child node. At such nodes, we simply traverse to555 the parent.556 557 2. At node 9, position 2, we recognize the node as a right-child node558 and accumulate the left-child in our total. Total is now 5 and we559 traverse to the parent at position 0.560 561 3. Iteration ends at the root.562 563 The index is then the sum of the total and sublist index: 5 + 3 = 8.564 565 :param int pos: lists index566 :param int idx: sublist index567 :return: index in sorted list568 569 """570 if not pos:571 return idx572 573 _index = self._index574 575 if not _index:576 self._build_index()577 578 total = 0579 580 # Increment pos to point in the index to len(self._lists[pos]).581 582 pos += self._offset583 584 # Iterate until reaching the root of the index tree at pos = 0.585 586 while pos:587 588 # Right-child nodes are at odd indices. At such indices589 # account the total below the left child node.590 591 if not pos & 1:592 total += _index[pos - 1]593 594 # Advance pos to the parent node.595 596 pos = (pos - 1) >> 1597 598 return total + idx599 600 601 def _pos(self, idx):602 """Convert an index into an index pair (lists index, sublist index)603 that can be used to access the corresponding lists position.604 605 Many queries require the index be built. Details of the index are606 described in ``SortedList._build_index``.607 608 Indexing requires traversing the tree to a leaf node. Each node has two609 children which are easily computable. Given an index, pos, the610 left-child is at ``pos * 2 + 1`` and the right-child is at ``pos * 2 +611 2``.612 613 When the index is less than the left-child, traversal moves to the614 left sub-tree. Otherwise, the index is decremented by the left-child615 and traversal moves to the right sub-tree.616 617 At a child node, the indexing pair is computed from the relative618 position of the child node as compared with the offset and the remaining619 index.620 621 For example, using the index from ``SortedList._build_index``::622 623 _index = 14 5 9 3 2 4 5624 _offset = 3625 626 Tree::627 628 14629 5 9630 3 2 4 5631 632 Indexing position 8 involves iterating like so:633 634 1. Starting at the root, position 0, 8 is compared with the left-child635 node (5) which it is greater than. When greater the index is636 decremented and the position is updated to the right child node.637 638 2. At node 9 with index 3, we again compare the index to the left-child639 node with value 4. Because the index is the less than the left-child640 node, we simply traverse to the left.641 642 3. At node 4 with index 3, we recognize that we are at a leaf node and643 stop iterating.644 645 4. To compute the sublist index, we subtract the offset from the index646 of the leaf node: 5 - 3 = 2. To compute the index in the sublist, we647 simply use the index remaining from iteration. In this case, 3.648 649 The final index pair from our example is (2, 3) which corresponds to650 index 8 in the sorted list.651 652 :param int idx: index in sorted list653 :return: (lists index, sublist index) pair654 655 """656 if idx < 0:657 last_len = len(self._lists[-1])658 659 if (-idx) <= last_len:660 return len(self._lists) - 1, last_len + idx661 662 idx += self._len663 664 if idx < 0:665 raise IndexError('list index out of range')666 elif idx >= self._len:667 raise IndexError('list index out of range')668 669 if idx < len(self._lists[0]):670 return 0, idx671 672 _index = self._index673 674 if not _index:675 self._build_index()676 677 pos = 0678 child = 1679 len_index = len(_index)680 681 while child < len_index:682 index_child = _index[child]683 684 if idx < index_child:685 pos = child686 else:687 idx -= index_child688 pos = child + 1689 690 child = (pos << 1) + 1691 692 return (pos - self._offset, idx)693 694 695 def _build_index(self):696 """Build a positional index for indexing the sorted list.697 698 Indexes are represented as binary trees in a dense array notation699 similar to a binary heap.700 701 For example, given a lists representation storing integers::702 703 0: [1, 2, 3]704 1: [4, 5]705 2: [6, 7, 8, 9]706 3: [10, 11, 12, 13, 14]707 708 The first transformation maps the sub-lists by their length. The709 first row of the index is the length of the sub-lists::710 711 0: [3, 2, 4, 5]712 713 Each row after that is the sum of consecutive pairs of the previous714 row::715 716 1: [5, 9]717 2: [14]718 719 Finally, the index is built by concatenating these lists together::720 721 _index = [14, 5, 9, 3, 2, 4, 5]722 723 An offset storing the start of the first row is also stored::724 725 _offset = 3726 727 When built, the index can be used for efficient indexing into the list.728 See the comment and notes on ``SortedList._pos`` for details.729 730 """731 row0 = list(map(len, self._lists))732 733 if len(row0) == 1:734 self._index[:] = row0735 self._offset = 0736 return737 738 head = iter(row0)739 tail = iter(head)740 row1 = list(starmap(add, zip(head, tail)))741 742 if len(row0) & 1:743 row1.append(row0[-1])744 745 if len(row1) == 1:746 self._index[:] = row1 + row0747 self._offset = 1748 return749 750 size = 2 ** (int(log(len(row1) - 1, 2)) + 1)751 row1.extend(repeat(0, size - len(row1)))752 tree = [row0, row1]753 754 while len(tree[-1]) > 1:755 head = iter(tree[-1])756 tail = iter(head)757 row = list(starmap(add, zip(head, tail)))758 tree.append(row)759 760 reduce(iadd, reversed(tree), self._index)761 self._offset = size * 2 - 1762 763 764 def __delitem__(self, index):765 """Remove value at `index` from sorted list.766 767 ``sl.__delitem__(index)`` <==> ``del sl[index]``768 769 Supports slicing.770 771 Runtime complexity: `O(log(n))` -- approximate.772 773 >>> sl = SortedList('abcde')774 >>> del sl[2]775 >>> sl776 SortedList(['a', 'b', 'd', 'e'])777 >>> del sl[:2]778 >>> sl779 SortedList(['d', 'e'])780 781 :param index: integer or slice for indexing782 :raises IndexError: if index out of range783 784 """785 if isinstance(index, slice):786 start, stop, step = index.indices(self._len)787 788 if step == 1 and start < stop:789 if start == 0 and stop == self._len:790 return self._clear()791 elif self._len <= 8 * (stop - start):792 values = self._getitem(slice(None, start))793 if stop < self._len:794 values += self._getitem(slice(stop, None))795 self._clear()796 return self._update(values)797 798 indices = range(start, stop, step)799 800 # Delete items from greatest index to least so801 # that the indices remain valid throughout iteration.802 803 if step > 0:804 indices = reversed(indices)805 806 _pos, _delete = self._pos, self._delete807 808 for index in indices:809 pos, idx = _pos(index)810 _delete(pos, idx)811 else:812 pos, idx = self._pos(index)813 self._delete(pos, idx)814 815 816 def __getitem__(self, index):817 """Lookup value at `index` in sorted list.818 819 ``sl.__getitem__(index)`` <==> ``sl[index]``820 821 Supports slicing.822 823 Runtime complexity: `O(log(n))` -- approximate.824 825 >>> sl = SortedList('abcde')826 >>> sl[1]827 'b'828 >>> sl[-1]829 'e'830 >>> sl[2:5]831 ['c', 'd', 'e']832 833 :param index: integer or slice for indexing834 :return: value or list of values835 :raises IndexError: if index out of range836 837 """838 _lists = self._lists839 840 if isinstance(index, slice):841 start, stop, step = index.indices(self._len)842 843 if step == 1 and start < stop:844 # Whole slice optimization: start to stop slices the whole845 # sorted list.846 847 if start == 0 and stop == self._len:848 return reduce(iadd, self._lists, [])849 850 start_pos, start_idx = self._pos(start)851 start_list = _lists[start_pos]852 stop_idx = start_idx + stop - start853 854 # Small slice optimization: start index and stop index are855 # within the start list.856 857 if len(start_list) >= stop_idx:858 return start_list[start_idx:stop_idx]859 860 if stop == self._len:861 stop_pos = len(_lists) - 1862 stop_idx = len(_lists[stop_pos])863 else:864 stop_pos, stop_idx = self._pos(stop)865 866 prefix = _lists[start_pos][start_idx:]867 middle = _lists[(start_pos + 1):stop_pos]868 result = reduce(iadd, middle, prefix)869 result += _lists[stop_pos][:stop_idx]870 871 return result872 873 if step == -1 and start > stop:874 result = self._getitem(slice(stop + 1, start + 1))875 result.reverse()876 return result877 878 # Return a list because a negative step could879 # reverse the order of the items and this could880 # be the desired behavior.881 882 indices = range(start, stop, step)883 return list(self._getitem(index) for index in indices)884 else:885 if self._len:886 if index == 0:887 return _lists[0][0]888 elif index == -1:889 return _lists[-1][-1]890 else:891 raise IndexError('list index out of range')892 893 if 0 <= index < len(_lists[0]):894 return _lists[0][index]895 896 len_last = len(_lists[-1])897 898 if -len_last < index < 0:899 return _lists[-1][len_last + index]900 901 pos, idx = self._pos(index)902 return _lists[pos][idx]903 904 _getitem = __getitem__905 906 907 def __setitem__(self, index, value):908 """Raise not-implemented error.909 910 ``sl.__setitem__(index, value)`` <==> ``sl[index] = value``911 912 :raises NotImplementedError: use ``del sl[index]`` and913 ``sl.add(value)`` instead914 915 """916 message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'917 raise NotImplementedError(message)918 919 920 def __iter__(self):921 """Return an iterator over the sorted list.922 923 ``sl.__iter__()`` <==> ``iter(sl)``924 925 Iterating the sorted list while adding or deleting values may raise a926 :exc:`RuntimeError` or fail to iterate over all values.927 928 """929 return chain.from_iterable(self._lists)930 931 932 def __reversed__(self):933 """Return a reverse iterator over the sorted list.934 935 ``sl.__reversed__()`` <==> ``reversed(sl)``936 937 Iterating the sorted list while adding or deleting values may raise a938 :exc:`RuntimeError` or fail to iterate over all values.939 940 """941 return chain.from_iterable(map(reversed, reversed(self._lists)))942 943 944 def reverse(self):945 """Raise not-implemented error.946 947 Sorted list maintains values in ascending sort order. Values may not be948 reversed in-place.949 950 Use ``reversed(sl)`` for an iterator over values in descending sort951 order.952 953 Implemented to override `MutableSequence.reverse` which provides an954 erroneous default implementation.955 956 :raises NotImplementedError: use ``reversed(sl)`` instead957 958 """959 raise NotImplementedError('use ``reversed(sl)`` instead')960 961 962 def islice(self, start=None, stop=None, reverse=False):963 """Return an iterator that slices sorted list from `start` to `stop`.964 965 The `start` and `stop` index are treated inclusive and exclusive,966 respectively.967 968 Both `start` and `stop` default to `None` which is automatically969 inclusive of the beginning and end of the sorted list.970 971 When `reverse` is `True` the values are yielded from the iterator in972 reverse order; `reverse` defaults to `False`.973 974 >>> sl = SortedList('abcdefghij')975 >>> it = sl.islice(2, 6)976 >>> list(it)977 ['c', 'd', 'e', 'f']978 979 :param int start: start index (inclusive)980 :param int stop: stop index (exclusive)981 :param bool reverse: yield values in reverse order982 :return: iterator983 984 """985 _len = self._len986 987 if not _len:988 return iter(())989 990 start, stop, _ = slice(start, stop).indices(self._len)991 992 if start >= stop:993 return iter(())994 995 _pos = self._pos996 997 min_pos, min_idx = _pos(start)998 999 if stop == _len:1000 max_pos = len(self._lists) - 11001 max_idx = len(self._lists[-1])1002 else:1003 max_pos, max_idx = _pos(stop)1004 1005 return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)1006 1007 1008 def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):1009 """Return an iterator that slices sorted list using two index pairs.1010 1011 The index pairs are (min_pos, min_idx) and (max_pos, max_idx), the1012 first inclusive and the latter exclusive. See `_pos` for details on how1013 an index is converted to an index pair.1014 1015 When `reverse` is `True`, values are yielded from the iterator in1016 reverse order.1017 1018 """1019 _lists = self._lists1020 1021 if min_pos > max_pos:1022 return iter(())1023 1024 if min_pos == max_pos:1025 if reverse:1026 indices = reversed(range(min_idx, max_idx))1027 return map(_lists[min_pos].__getitem__, indices)1028 1029 indices = range(min_idx, max_idx)1030 return map(_lists[min_pos].__getitem__, indices)1031 1032 next_pos = min_pos + 11033 1034 if next_pos == max_pos:1035 if reverse:1036 min_indices = range(min_idx, len(_lists[min_pos]))1037 max_indices = range(max_idx)1038 return chain(1039 map(_lists[max_pos].__getitem__, reversed(max_indices)),1040 map(_lists[min_pos].__getitem__, reversed(min_indices)),1041 )1042 1043 min_indices = range(min_idx, len(_lists[min_pos]))1044 max_indices = range(max_idx)1045 return chain(1046 map(_lists[min_pos].__getitem__, min_indices),1047 map(_lists[max_pos].__getitem__, max_indices),1048 )1049 1050 if reverse:1051 min_indices = range(min_idx, len(_lists[min_pos]))1052 sublist_indices = range(next_pos, max_pos)1053 sublists = map(_lists.__getitem__, reversed(sublist_indices))1054 max_indices = range(max_idx)1055 return chain(1056 map(_lists[max_pos].__getitem__, reversed(max_indices)),1057 chain.from_iterable(map(reversed, sublists)),1058 map(_lists[min_pos].__getitem__, reversed(min_indices)),1059 )1060 1061 min_indices = range(min_idx, len(_lists[min_pos]))1062 sublist_indices = range(next_pos, max_pos)1063 sublists = map(_lists.__getitem__, sublist_indices)1064 max_indices = range(max_idx)1065 return chain(1066 map(_lists[min_pos].__getitem__, min_indices),1067 chain.from_iterable(sublists),1068 map(_lists[max_pos].__getitem__, max_indices),1069 )1070 1071 1072 def irange(self, minimum=None, maximum=None, inclusive=(True, True),1073 reverse=False):1074 """Create an iterator of values between `minimum` and `maximum`.1075 1076 Both `minimum` and `maximum` default to `None` which is automatically1077 inclusive of the beginning and end of the sorted list.1078 1079 The argument `inclusive` is a pair of booleans that indicates whether1080 the minimum and maximum ought to be included in the range,1081 respectively. The default is ``(True, True)`` such that the range is1082 inclusive of both minimum and maximum.1083 1084 When `reverse` is `True` the values are yielded from the iterator in1085 reverse order; `reverse` defaults to `False`.1086 1087 >>> sl = SortedList('abcdefghij')1088 >>> it = sl.irange('c', 'f')1089 >>> list(it)1090 ['c', 'd', 'e', 'f']1091 1092 :param minimum: minimum value to start iterating1093 :param maximum: maximum value to stop iterating1094 :param inclusive: pair of booleans1095 :param bool reverse: yield values in reverse order1096 :return: iterator1097 1098 """1099 _maxes = self._maxes1100 1101 if not _maxes:1102 return iter(())1103 1104 _lists = self._lists1105 1106 # Calculate the minimum (pos, idx) pair. By default this location1107 # will be inclusive in our calculation.1108 1109 if minimum is None:1110 min_pos = 01111 min_idx = 01112 else:1113 if inclusive[0]:1114 min_pos = bisect_left(_maxes, minimum)1115 1116 if min_pos == len(_maxes):1117 return iter(())1118 1119 min_idx = bisect_left(_lists[min_pos], minimum)1120 else:1121 min_pos = bisect_right(_maxes, minimum)1122 1123 if min_pos == len(_maxes):1124 return iter(())1125 1126 min_idx = bisect_right(_lists[min_pos], minimum)1127 1128 # Calculate the maximum (pos, idx) pair. By default this location1129 # will be exclusive in our calculation.1130 1131 if maximum is None:1132 max_pos = len(_maxes) - 11133 max_idx = len(_lists[max_pos])1134 else:1135 if inclusive[1]:1136 max_pos = bisect_right(_maxes, maximum)1137 1138 if max_pos == len(_maxes):1139 max_pos -= 11140 max_idx = len(_lists[max_pos])1141 else:1142 max_idx = bisect_right(_lists[max_pos], maximum)1143 else:1144 max_pos = bisect_left(_maxes, maximum)1145 1146 if max_pos == len(_maxes):1147 max_pos -= 11148 max_idx = len(_lists[max_pos])1149 else:1150 max_idx = bisect_left(_lists[max_pos], maximum)1151 1152 return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)1153 1154 1155 def __len__(self):1156 """Return the size of the sorted list.1157 1158 ``sl.__len__()`` <==> ``len(sl)``1159 1160 :return: size of sorted list1161 1162 """1163 return self._len1164 1165 1166 def bisect_left(self, value):1167 """Return an index to insert `value` in the sorted list.1168 1169 If the `value` is already present, the insertion point will be before1170 (to the left of) any existing values.1171 1172 Similar to the `bisect` module in the standard library.1173 1174 Runtime complexity: `O(log(n))` -- approximate.1175 1176 >>> sl = SortedList([10, 11, 12, 13, 14])1177 >>> sl.bisect_left(12)1178 21179 1180 :param value: insertion index of value in sorted list1181 :return: index1182 1183 """1184 _maxes = self._maxes1185 1186 if not _maxes:1187 return 01188 1189 pos = bisect_left(_maxes, value)1190 1191 if pos == len(_maxes):1192 return self._len1193 1194 idx = bisect_left(self._lists[pos], value)1195 return self._loc(pos, idx)1196 1197 1198 def bisect_right(self, value):1199 """Return an index to insert `value` in the sorted list.1200