Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Sorted List
2==============
4:doc:`Sorted Containers<index>` is an Apache2 licensed Python sorted
5collections library, written in pure-Python, and fast as C-extensions. The
6:doc:`introduction<introduction>` is the best way to get started.
8Sorted list implementations:
10.. currentmodule:: sortedcontainers
12* :class:`SortedList`
13* :class:`SortedKeyList`
15"""
16# pylint: disable=too-many-lines
17from __future__ import print_function
19import sys
20import traceback
22from bisect import bisect_left, bisect_right, insort
23from itertools import chain, repeat, starmap
24from math import log
25from operator import add, eq, ne, gt, ge, lt, le, iadd
26from textwrap import dedent
28###############################################################################
29# BEGIN Python 2/3 Shims
30###############################################################################
32try:
33 from collections.abc import Sequence, MutableSequence
34except ImportError:
35 from collections import Sequence, MutableSequence
37from functools import wraps
38from sys import hexversion
40if hexversion < 0x03000000:
41 from itertools import imap as map # pylint: disable=redefined-builtin
42 from itertools import izip as zip # pylint: disable=redefined-builtin
43 try:
44 from thread import get_ident
45 except ImportError:
46 from dummy_thread import get_ident
47else:
48 from functools import reduce
49 try:
50 from _thread import get_ident
51 except ImportError:
52 from _dummy_thread import get_ident
55def recursive_repr(fillvalue='...'):
56 "Decorator to make a repr function return fillvalue for a recursive call."
57 # pylint: disable=missing-docstring
58 # Copied from reprlib in Python 3
59 # https://hg.python.org/cpython/file/3.6/Lib/reprlib.py
61 def decorating_function(user_function):
62 repr_running = set()
64 @wraps(user_function)
65 def wrapper(self):
66 key = id(self), get_ident()
67 if key in repr_running:
68 return fillvalue
69 repr_running.add(key)
70 try:
71 result = user_function(self)
72 finally:
73 repr_running.discard(key)
74 return result
76 return wrapper
78 return decorating_function
80###############################################################################
81# END Python 2/3 Shims
82###############################################################################
85class SortedList(MutableSequence):
86 """Sorted list is a sorted mutable sequence.
88 Sorted list values are maintained in sorted order.
90 Sorted list values must be comparable. The total ordering of values must
91 not change while they are stored in the sorted list.
93 Methods for adding values:
95 * :func:`SortedList.add`
96 * :func:`SortedList.update`
97 * :func:`SortedList.__add__`
98 * :func:`SortedList.__iadd__`
99 * :func:`SortedList.__mul__`
100 * :func:`SortedList.__imul__`
102 Methods for removing values:
104 * :func:`SortedList.clear`
105 * :func:`SortedList.discard`
106 * :func:`SortedList.remove`
107 * :func:`SortedList.pop`
108 * :func:`SortedList.__delitem__`
110 Methods for looking up values:
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__`
119 Methods for iterating values:
121 * :func:`SortedList.irange`
122 * :func:`SortedList.islice`
123 * :func:`SortedList.__iter__`
124 * :func:`SortedList.__reversed__`
126 Methods for miscellany:
128 * :func:`SortedList.copy`
129 * :func:`SortedList.__len__`
130 * :func:`SortedList.__repr__`
131 * :func:`SortedList._check`
132 * :func:`SortedList._reset`
134 Sorted lists use lexicographical ordering semantics when compared to other
135 sequences.
137 Some methods of mutable sequences are not supported and will raise
138 not-implemented error.
140 """
141 DEFAULT_LOAD_FACTOR = 1000
144 def __init__(self, iterable=None, key=None):
145 """Initialize sorted list instance.
147 Optional `iterable` argument provides an initial iterable of values to
148 initialize the sorted list.
150 Runtime complexity: `O(n*log(n))`
152 >>> sl = SortedList()
153 >>> sl
154 SortedList([])
155 >>> sl = SortedList([3, 1, 2, 5, 4])
156 >>> sl
157 SortedList([1, 2, 3, 4, 5])
159 :param iterable: initial values (optional)
161 """
162 assert key is None
163 self._len = 0
164 self._load = self.DEFAULT_LOAD_FACTOR
165 self._lists = []
166 self._maxes = []
167 self._index = []
168 self._offset = 0
170 if iterable is not None:
171 self._update(iterable)
174 def __new__(cls, iterable=None, key=None):
175 """Create new sorted list or sorted-key list instance.
177 Optional `key`-function argument will return an instance of subtype
178 :class:`SortedKeyList`.
180 >>> sl = SortedList()
181 >>> isinstance(sl, SortedList)
182 True
183 >>> sl = SortedList(key=lambda x: -x)
184 >>> isinstance(sl, SortedList)
185 True
186 >>> isinstance(sl, SortedKeyList)
187 True
189 :param iterable: initial values (optional)
190 :param key: function used to extract comparison key (optional)
191 :return: sorted list or sorted-key list instance
193 """
194 # pylint: disable=unused-argument
195 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')
204 @property
205 def key(self): # pylint: disable=useless-return
206 """Function used to extract comparison key from values.
208 Sorted list compares values directly so the key function is none.
210 """
211 return None
214 def _reset(self, load):
215 """Reset sorted list load factor.
217 The `load` specifies the load-factor of the list. The default load
218 factor of 1000 works well for lists from tens to tens-of-millions of
219 values. Good practice is to use a value that is the cube root of the
220 list size. With billions of elements, the best load factor depends on
221 your usage. It's best to leave the load factor at the default until you
222 start benchmarking.
224 See :doc:`implementation` and :doc:`performance-scale` for more
225 information.
227 Runtime complexity: `O(n)`
229 :param int load: load-factor for sorted list sublists
231 """
232 values = reduce(iadd, self._lists, [])
233 self._clear()
234 self._load = load
235 self._update(values)
238 def clear(self):
239 """Remove all values from sorted list.
241 Runtime complexity: `O(n)`
243 """
244 self._len = 0
245 del self._lists[:]
246 del self._maxes[:]
247 del self._index[:]
248 self._offset = 0
250 _clear = clear
253 def add(self, value):
254 """Add `value` to sorted list.
256 Runtime complexity: `O(log(n))` -- approximate.
258 >>> sl = SortedList()
259 >>> sl.add(3)
260 >>> sl.add(1)
261 >>> sl.add(2)
262 >>> sl
263 SortedList([1, 2, 3])
265 :param value: value to add to sorted list
267 """
268 _lists = self._lists
269 _maxes = self._maxes
271 if _maxes:
272 pos = bisect_right(_maxes, value)
274 if pos == len(_maxes):
275 pos -= 1
276 _lists[pos].append(value)
277 _maxes[pos] = value
278 else:
279 insort(_lists[pos], value)
281 self._expand(pos)
282 else:
283 _lists.append([value])
284 _maxes.append(value)
286 self._len += 1
289 def _expand(self, pos):
290 """Split sublists with length greater than double the load-factor.
292 Updates the index when the sublist length is less than double the load
293 level. This requires incrementing the nodes in a traversal from the
294 leaf node to the root. For an example traversal see
295 ``SortedList._loc``.
297 """
298 _load = self._load
299 _lists = self._lists
300 _index = self._index
302 if len(_lists[pos]) > (_load << 1):
303 _maxes = self._maxes
305 _lists_pos = _lists[pos]
306 half = _lists_pos[_load:]
307 del _lists_pos[_load:]
308 _maxes[pos] = _lists_pos[-1]
310 _lists.insert(pos + 1, half)
311 _maxes.insert(pos + 1, half[-1])
313 del _index[:]
314 else:
315 if _index:
316 child = self._offset + pos
317 while child:
318 _index[child] += 1
319 child = (child - 1) >> 1
320 _index[0] += 1
323 def update(self, iterable):
324 """Update sorted list by adding all values from `iterable`.
326 Runtime complexity: `O(k*log(n))` -- approximate.
328 >>> sl = SortedList()
329 >>> sl.update([3, 1, 2])
330 >>> sl
331 SortedList([1, 2, 3])
333 :param iterable: iterable of values to add
335 """
336 _lists = self._lists
337 _maxes = self._maxes
338 values = sorted(iterable)
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.add
348 for val in values:
349 _add(val)
350 return
352 _load = self._load
353 _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[:]
359 _update = update
362 def __contains__(self, value):
363 """Return true if `value` is an element of the sorted list.
365 ``sl.__contains__(value)`` <==> ``value in sl``
367 Runtime complexity: `O(log(n))`
369 >>> sl = SortedList([1, 2, 3, 4, 5])
370 >>> 3 in sl
371 True
373 :param value: search for value in sorted list
374 :return: true if `value` in sorted list
376 """
377 _maxes = self._maxes
379 if not _maxes:
380 return False
382 pos = bisect_left(_maxes, value)
384 if pos == len(_maxes):
385 return False
387 _lists = self._lists
388 idx = bisect_left(_lists[pos], value)
390 return _lists[pos][idx] == value
393 def discard(self, value):
394 """Remove `value` from sorted list if it is a member.
396 If `value` is not a member, do nothing.
398 Runtime complexity: `O(log(n))` -- approximate.
400 >>> sl = SortedList([1, 2, 3, 4, 5])
401 >>> sl.discard(5)
402 >>> sl.discard(0)
403 >>> sl == [1, 2, 3, 4]
404 True
406 :param value: `value` to discard from sorted list
408 """
409 _maxes = self._maxes
411 if not _maxes:
412 return
414 pos = bisect_left(_maxes, value)
416 if pos == len(_maxes):
417 return
419 _lists = self._lists
420 idx = bisect_left(_lists[pos], value)
422 if _lists[pos][idx] == value:
423 self._delete(pos, idx)
426 def remove(self, value):
427 """Remove `value` from sorted list; `value` must be a member.
429 If `value` is not a member, raise ValueError.
431 Runtime complexity: `O(log(n))` -- approximate.
433 >>> sl = SortedList([1, 2, 3, 4, 5])
434 >>> sl.remove(5)
435 >>> sl == [1, 2, 3, 4]
436 True
437 >>> sl.remove(0)
438 Traceback (most recent call last):
439 ...
440 ValueError: 0 not in list
442 :param value: `value` to remove from sorted list
443 :raises ValueError: if `value` is not in sorted list
445 """
446 _maxes = self._maxes
448 if not _maxes:
449 raise ValueError('{0!r} not in list'.format(value))
451 pos = bisect_left(_maxes, value)
453 if pos == len(_maxes):
454 raise ValueError('{0!r} not in list'.format(value))
456 _lists = self._lists
457 idx = bisect_left(_lists[pos], value)
459 if _lists[pos][idx] == value:
460 self._delete(pos, idx)
461 else:
462 raise ValueError('{0!r} not in list'.format(value))
465 def _delete(self, pos, idx):
466 """Delete value at the given `(pos, idx)`.
468 Combines lists that are less than half the load level.
470 Updates the index when the sublist length is more than half the load
471 level. This requires decrementing the nodes in a traversal from the
472 leaf node to the root. For an example traversal see
473 ``SortedList._loc``.
475 :param int pos: lists index
476 :param int idx: sublist index
478 """
479 _lists = self._lists
480 _maxes = self._maxes
481 _index = self._index
483 _lists_pos = _lists[pos]
485 del _lists_pos[idx]
486 self._len -= 1
488 len_lists_pos = len(_lists_pos)
490 if len_lists_pos > (self._load >> 1):
491 _maxes[pos] = _lists_pos[-1]
493 if _index:
494 child = self._offset + pos
495 while child > 0:
496 _index[child] -= 1
497 child = (child - 1) >> 1
498 _index[0] -= 1
499 elif len(_lists) > 1:
500 if not pos:
501 pos += 1
503 prev = pos - 1
504 _lists[prev].extend(_lists[pos])
505 _maxes[prev] = _lists[prev][-1]
507 del _lists[pos]
508 del _maxes[pos]
509 del _index[:]
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[:]
520 def _loc(self, pos, idx):
521 """Convert an index pair (lists index, sublist index) into a single
522 index number that corresponds to the position of the value in the
523 sorted list.
525 Many queries require the index be built. Details of the index are
526 described in ``SortedList._build_index``.
528 Indexing requires traversing the tree from a leaf node to the root. The
529 parent of each node is easily computable at ``(pos - 1) // 2``.
531 Left-child nodes are always at odd indices and right-child nodes are
532 always at even indices.
534 When traversing up from a right-child node, increment the total by the
535 left-child node.
537 The final index is the sum from traversal and the index in the sublist.
539 For example, using the index from ``SortedList._build_index``::
541 _index = 14 5 9 3 2 4 5
542 _offset = 3
544 Tree::
546 14
547 5 9
548 3 2 4 5
550 Converting an index pair (2, 3) into a single index involves iterating
551 like so:
553 1. Starting at the leaf node: offset + alpha = 3 + 2 = 5. We identify
554 the node as a left-child node. At such nodes, we simply traverse to
555 the parent.
557 2. At node 9, position 2, we recognize the node as a right-child node
558 and accumulate the left-child in our total. Total is now 5 and we
559 traverse to the parent at position 0.
561 3. Iteration ends at the root.
563 The index is then the sum of the total and sublist index: 5 + 3 = 8.
565 :param int pos: lists index
566 :param int idx: sublist index
567 :return: index in sorted list
569 """
570 if not pos:
571 return idx
573 _index = self._index
575 if not _index:
576 self._build_index()
578 total = 0
580 # Increment pos to point in the index to len(self._lists[pos]).
582 pos += self._offset
584 # Iterate until reaching the root of the index tree at pos = 0.
586 while pos:
588 # Right-child nodes are at odd indices. At such indices
589 # account the total below the left child node.
591 if not pos & 1:
592 total += _index[pos - 1]
594 # Advance pos to the parent node.
596 pos = (pos - 1) >> 1
598 return total + idx
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.
605 Many queries require the index be built. Details of the index are
606 described in ``SortedList._build_index``.
608 Indexing requires traversing the tree to a leaf node. Each node has two
609 children which are easily computable. Given an index, pos, the
610 left-child is at ``pos * 2 + 1`` and the right-child is at ``pos * 2 +
611 2``.
613 When the index is less than the left-child, traversal moves to the
614 left sub-tree. Otherwise, the index is decremented by the left-child
615 and traversal moves to the right sub-tree.
617 At a child node, the indexing pair is computed from the relative
618 position of the child node as compared with the offset and the remaining
619 index.
621 For example, using the index from ``SortedList._build_index``::
623 _index = 14 5 9 3 2 4 5
624 _offset = 3
626 Tree::
628 14
629 5 9
630 3 2 4 5
632 Indexing position 8 involves iterating like so:
634 1. Starting at the root, position 0, 8 is compared with the left-child
635 node (5) which it is greater than. When greater the index is
636 decremented and the position is updated to the right child node.
638 2. At node 9 with index 3, we again compare the index to the left-child
639 node with value 4. Because the index is the less than the left-child
640 node, we simply traverse to the left.
642 3. At node 4 with index 3, we recognize that we are at a leaf node and
643 stop iterating.
645 4. To compute the sublist index, we subtract the offset from the index
646 of the leaf node: 5 - 3 = 2. To compute the index in the sublist, we
647 simply use the index remaining from iteration. In this case, 3.
649 The final index pair from our example is (2, 3) which corresponds to
650 index 8 in the sorted list.
652 :param int idx: index in sorted list
653 :return: (lists index, sublist index) pair
655 """
656 if idx < 0:
657 last_len = len(self._lists[-1])
659 if (-idx) <= last_len:
660 return len(self._lists) - 1, last_len + idx
662 idx += self._len
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')
669 if idx < len(self._lists[0]):
670 return 0, idx
672 _index = self._index
674 if not _index:
675 self._build_index()
677 pos = 0
678 child = 1
679 len_index = len(_index)
681 while child < len_index:
682 index_child = _index[child]
684 if idx < index_child:
685 pos = child
686 else:
687 idx -= index_child
688 pos = child + 1
690 child = (pos << 1) + 1
692 return (pos - self._offset, idx)
695 def _build_index(self):
696 """Build a positional index for indexing the sorted list.
698 Indexes are represented as binary trees in a dense array notation
699 similar to a binary heap.
701 For example, given a lists representation storing integers::
703 0: [1, 2, 3]
704 1: [4, 5]
705 2: [6, 7, 8, 9]
706 3: [10, 11, 12, 13, 14]
708 The first transformation maps the sub-lists by their length. The
709 first row of the index is the length of the sub-lists::
711 0: [3, 2, 4, 5]
713 Each row after that is the sum of consecutive pairs of the previous
714 row::
716 1: [5, 9]
717 2: [14]
719 Finally, the index is built by concatenating these lists together::
721 _index = [14, 5, 9, 3, 2, 4, 5]
723 An offset storing the start of the first row is also stored::
725 _offset = 3
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.
730 """
731 row0 = list(map(len, self._lists))
733 if len(row0) == 1:
734 self._index[:] = row0
735 self._offset = 0
736 return
738 head = iter(row0)
739 tail = iter(head)
740 row1 = list(starmap(add, zip(head, tail)))
742 if len(row0) & 1:
743 row1.append(row0[-1])
745 if len(row1) == 1:
746 self._index[:] = row1 + row0
747 self._offset = 1
748 return
750 size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
751 row1.extend(repeat(0, size - len(row1)))
752 tree = [row0, row1]
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)
760 reduce(iadd, reversed(tree), self._index)
761 self._offset = size * 2 - 1
764 def __delitem__(self, index):
765 """Remove value at `index` from sorted list.
767 ``sl.__delitem__(index)`` <==> ``del sl[index]``
769 Supports slicing.
771 Runtime complexity: `O(log(n))` -- approximate.
773 >>> sl = SortedList('abcde')
774 >>> del sl[2]
775 >>> sl
776 SortedList(['a', 'b', 'd', 'e'])
777 >>> del sl[:2]
778 >>> sl
779 SortedList(['d', 'e'])
781 :param index: integer or slice for indexing
782 :raises IndexError: if index out of range
784 """
785 if isinstance(index, slice):
786 start, stop, step = index.indices(self._len)
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)
798 indices = range(start, stop, step)
800 # Delete items from greatest index to least so
801 # that the indices remain valid throughout iteration.
803 if step > 0:
804 indices = reversed(indices)
806 _pos, _delete = self._pos, self._delete
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)
816 def __getitem__(self, index):
817 """Lookup value at `index` in sorted list.
819 ``sl.__getitem__(index)`` <==> ``sl[index]``
821 Supports slicing.
823 Runtime complexity: `O(log(n))` -- approximate.
825 >>> sl = SortedList('abcde')
826 >>> sl[1]
827 'b'
828 >>> sl[-1]
829 'e'
830 >>> sl[2:5]
831 ['c', 'd', 'e']
833 :param index: integer or slice for indexing
834 :return: value or list of values
835 :raises IndexError: if index out of range
837 """
838 _lists = self._lists
840 if isinstance(index, slice):
841 start, stop, step = index.indices(self._len)
843 if step == 1 and start < stop:
844 # Whole slice optimization: start to stop slices the whole
845 # sorted list.
847 if start == 0 and stop == self._len:
848 return reduce(iadd, self._lists, [])
850 start_pos, start_idx = self._pos(start)
851 start_list = _lists[start_pos]
852 stop_idx = start_idx + stop - start
854 # Small slice optimization: start index and stop index are
855 # within the start list.
857 if len(start_list) >= stop_idx:
858 return start_list[start_idx:stop_idx]
860 if stop == self._len:
861 stop_pos = len(_lists) - 1
862 stop_idx = len(_lists[stop_pos])
863 else:
864 stop_pos, stop_idx = self._pos(stop)
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]
871 return result
873 if step == -1 and start > stop:
874 result = self._getitem(slice(stop + 1, start + 1))
875 result.reverse()
876 return result
878 # Return a list because a negative step could
879 # reverse the order of the items and this could
880 # be the desired behavior.
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')
893 if 0 <= index < len(_lists[0]):
894 return _lists[0][index]
896 len_last = len(_lists[-1])
898 if -len_last < index < 0:
899 return _lists[-1][len_last + index]
901 pos, idx = self._pos(index)
902 return _lists[pos][idx]
904 _getitem = __getitem__
907 def __setitem__(self, index, value):
908 """Raise not-implemented error.
910 ``sl.__setitem__(index, value)`` <==> ``sl[index] = value``
912 :raises NotImplementedError: use ``del sl[index]`` and
913 ``sl.add(value)`` instead
915 """
916 message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
917 raise NotImplementedError(message)
920 def __iter__(self):
921 """Return an iterator over the sorted list.
923 ``sl.__iter__()`` <==> ``iter(sl)``
925 Iterating the sorted list while adding or deleting values may raise a
926 :exc:`RuntimeError` or fail to iterate over all values.
928 """
929 return chain.from_iterable(self._lists)
932 def __reversed__(self):
933 """Return a reverse iterator over the sorted list.
935 ``sl.__reversed__()`` <==> ``reversed(sl)``
937 Iterating the sorted list while adding or deleting values may raise a
938 :exc:`RuntimeError` or fail to iterate over all values.
940 """
941 return chain.from_iterable(map(reversed, reversed(self._lists)))
944 def reverse(self):
945 """Raise not-implemented error.
947 Sorted list maintains values in ascending sort order. Values may not be
948 reversed in-place.
950 Use ``reversed(sl)`` for an iterator over values in descending sort
951 order.
953 Implemented to override `MutableSequence.reverse` which provides an
954 erroneous default implementation.
956 :raises NotImplementedError: use ``reversed(sl)`` instead
958 """
959 raise NotImplementedError('use ``reversed(sl)`` instead')
962 def islice(self, start=None, stop=None, reverse=False):
963 """Return an iterator that slices sorted list from `start` to `stop`.
965 The `start` and `stop` index are treated inclusive and exclusive,
966 respectively.
968 Both `start` and `stop` default to `None` which is automatically
969 inclusive of the beginning and end of the sorted list.
971 When `reverse` is `True` the values are yielded from the iterator in
972 reverse order; `reverse` defaults to `False`.
974 >>> sl = SortedList('abcdefghij')
975 >>> it = sl.islice(2, 6)
976 >>> list(it)
977 ['c', 'd', 'e', 'f']
979 :param int start: start index (inclusive)
980 :param int stop: stop index (exclusive)
981 :param bool reverse: yield values in reverse order
982 :return: iterator
984 """
985 _len = self._len
987 if not _len:
988 return iter(())
990 start, stop, _ = slice(start, stop).indices(self._len)
992 if start >= stop:
993 return iter(())
995 _pos = self._pos
997 min_pos, min_idx = _pos(start)
999 if stop == _len:
1000 max_pos = len(self._lists) - 1
1001 max_idx = len(self._lists[-1])
1002 else:
1003 max_pos, max_idx = _pos(stop)
1005 return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
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.
1011 The index pairs are (min_pos, min_idx) and (max_pos, max_idx), the
1012 first inclusive and the latter exclusive. See `_pos` for details on how
1013 an index is converted to an index pair.
1015 When `reverse` is `True`, values are yielded from the iterator in
1016 reverse order.
1018 """
1019 _lists = self._lists
1021 if min_pos > max_pos:
1022 return iter(())
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)
1029 indices = range(min_idx, max_idx)
1030 return map(_lists[min_pos].__getitem__, indices)
1032 next_pos = min_pos + 1
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 )
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 )
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 )
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 )
1072 def irange(self, minimum=None, maximum=None, inclusive=(True, True),
1073 reverse=False):
1074 """Create an iterator of values between `minimum` and `maximum`.
1076 Both `minimum` and `maximum` default to `None` which is automatically
1077 inclusive of the beginning and end of the sorted list.
1079 The argument `inclusive` is a pair of booleans that indicates whether
1080 the minimum and maximum ought to be included in the range,
1081 respectively. The default is ``(True, True)`` such that the range is
1082 inclusive of both minimum and maximum.
1084 When `reverse` is `True` the values are yielded from the iterator in
1085 reverse order; `reverse` defaults to `False`.
1087 >>> sl = SortedList('abcdefghij')
1088 >>> it = sl.irange('c', 'f')
1089 >>> list(it)
1090 ['c', 'd', 'e', 'f']
1092 :param minimum: minimum value to start iterating
1093 :param maximum: maximum value to stop iterating
1094 :param inclusive: pair of booleans
1095 :param bool reverse: yield values in reverse order
1096 :return: iterator
1098 """
1099 _maxes = self._maxes
1101 if not _maxes:
1102 return iter(())
1104 _lists = self._lists
1106 # Calculate the minimum (pos, idx) pair. By default this location
1107 # will be inclusive in our calculation.
1109 if minimum is None:
1110 min_pos = 0
1111 min_idx = 0
1112 else:
1113 if inclusive[0]:
1114 min_pos = bisect_left(_maxes, minimum)
1116 if min_pos == len(_maxes):
1117 return iter(())
1119 min_idx = bisect_left(_lists[min_pos], minimum)
1120 else:
1121 min_pos = bisect_right(_maxes, minimum)
1123 if min_pos == len(_maxes):
1124 return iter(())
1126 min_idx = bisect_right(_lists[min_pos], minimum)
1128 # Calculate the maximum (pos, idx) pair. By default this location
1129 # will be exclusive in our calculation.
1131 if maximum is None:
1132 max_pos = len(_maxes) - 1
1133 max_idx = len(_lists[max_pos])
1134 else:
1135 if inclusive[1]:
1136 max_pos = bisect_right(_maxes, maximum)
1138 if max_pos == len(_maxes):
1139 max_pos -= 1
1140 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)
1146 if max_pos == len(_maxes):
1147 max_pos -= 1
1148 max_idx = len(_lists[max_pos])
1149 else:
1150 max_idx = bisect_left(_lists[max_pos], maximum)
1152 return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
1155 def __len__(self):
1156 """Return the size of the sorted list.
1158 ``sl.__len__()`` <==> ``len(sl)``
1160 :return: size of sorted list
1162 """
1163 return self._len
1166 def bisect_left(self, value):
1167 """Return an index to insert `value` in the sorted list.
1169 If the `value` is already present, the insertion point will be before
1170 (to the left of) any existing values.
1172 Similar to the `bisect` module in the standard library.
1174 Runtime complexity: `O(log(n))` -- approximate.
1176 >>> sl = SortedList([10, 11, 12, 13, 14])
1177 >>> sl.bisect_left(12)
1178 2
1180 :param value: insertion index of value in sorted list
1181 :return: index
1183 """
1184 _maxes = self._maxes
1186 if not _maxes:
1187 return 0
1189 pos = bisect_left(_maxes, value)
1191 if pos == len(_maxes):
1192 return self._len
1194 idx = bisect_left(self._lists[pos], value)
1195 return self._loc(pos, idx)
1198 def bisect_right(self, value):
1199 """Return an index to insert `value` in the sorted list.
1201 Similar to `bisect_left`, but if `value` is already present, the
1202 insertion point will be after (to the right of) any existing values.
1204 Similar to the `bisect` module in the standard library.
1206 Runtime complexity: `O(log(n))` -- approximate.
1208 >>> sl = SortedList([10, 11, 12, 13, 14])
1209 >>> sl.bisect_right(12)
1210 3
1212 :param value: insertion index of value in sorted list
1213 :return: index
1215 """
1216 _maxes = self._maxes
1218 if not _maxes:
1219 return 0
1221 pos = bisect_right(_maxes, value)
1223 if pos == len(_maxes):
1224 return self._len
1226 idx = bisect_right(self._lists[pos], value)
1227 return self._loc(pos, idx)
1229 bisect = bisect_right
1230 _bisect_right = bisect_right
1233 def count(self, value):
1234 """Return number of occurrences of `value` in the sorted list.
1236 Runtime complexity: `O(log(n))` -- approximate.
1238 >>> sl = SortedList([1, 2, 2, 3, 3, 3, 4, 4, 4, 4])
1239 >>> sl.count(3)
1240 3
1242 :param value: value to count in sorted list
1243 :return: count
1245 """
1246 _maxes = self._maxes
1248 if not _maxes:
1249 return 0
1251 pos_left = bisect_left(_maxes, value)
1253 if pos_left == len(_maxes):
1254 return 0
1256 _lists = self._lists
1257 idx_left = bisect_left(_lists[pos_left], value)
1258 pos_right = bisect_right(_maxes, value)
1260 if pos_right == len(_maxes):
1261 return self._len - self._loc(pos_left, idx_left)
1263 idx_right = bisect_right(_lists[pos_right], value)
1265 if pos_left == pos_right:
1266 return idx_right - idx_left
1268 right = self._loc(pos_right, idx_right)
1269 left = self._loc(pos_left, idx_left)
1270 return right - left
1273 def copy(self):
1274 """Return a shallow copy of the sorted list.
1276 Runtime complexity: `O(n)`
1278 :return: new sorted list
1280 """
1281 return self.__class__(self)
1283 __copy__ = copy
1286 def append(self, value):
1287 """Raise not-implemented error.
1289 Implemented to override `MutableSequence.append` which provides an
1290 erroneous default implementation.
1292 :raises NotImplementedError: use ``sl.add(value)`` instead
1294 """
1295 raise NotImplementedError('use ``sl.add(value)`` instead')
1298 def extend(self, values):
1299 """Raise not-implemented error.
1301 Implemented to override `MutableSequence.extend` which provides an
1302 erroneous default implementation.
1304 :raises NotImplementedError: use ``sl.update(values)`` instead
1306 """
1307 raise NotImplementedError('use ``sl.update(values)`` instead')
1310 def insert(self, index, value):
1311 """Raise not-implemented error.
1313 :raises NotImplementedError: use ``sl.add(value)`` instead
1315 """
1316 raise NotImplementedError('use ``sl.add(value)`` instead')
1319 def pop(self, index=-1):
1320 """Remove and return value at `index` in sorted list.
1322 Raise :exc:`IndexError` if the sorted list is empty or index is out of
1323 range.
1325 Negative indices are supported.
1327 Runtime complexity: `O(log(n))` -- approximate.
1329 >>> sl = SortedList('abcde')
1330 >>> sl.pop()
1331 'e'
1332 >>> sl.pop(2)
1333 'c'
1334 >>> sl
1335 SortedList(['a', 'b', 'd'])
1337 :param int index: index of value (default -1)
1338 :return: value
1339 :raises IndexError: if index is out of range
1341 """
1342 if not self._len:
1343 raise IndexError('pop index out of range')
1345 _lists = self._lists
1347 if index == 0:
1348 val = _lists[0][0]
1349 self._delete(0, 0)
1350 return val
1352 if index == -1:
1353 pos = len(_lists) - 1
1354 loc = len(_lists[pos]) - 1
1355 val = _lists[pos][loc]
1356 self._delete(pos, loc)
1357 return val
1359 if 0 <= index < len(_lists[0]):
1360 val = _lists[0][index]
1361 self._delete(0, index)
1362 return val
1364 len_last = len(_lists[-1])
1366 if -len_last < index < 0:
1367 pos = len(_lists) - 1
1368 loc = len_last + index
1369 val = _lists[pos][loc]
1370 self._delete(pos, loc)
1371 return val
1373 pos, idx = self._pos(index)
1374 val = _lists[pos][idx]
1375 self._delete(pos, idx)
1376 return val
1379 def index(self, value, start=None, stop=None):
1380 """Return first index of value in sorted list.
1382 Raise ValueError if `value` is not present.
1384 Index must be between `start` and `stop` for the `value` to be
1385 considered present. The default value, None, for `start` and `stop`
1386 indicate the beginning and end of the sorted list.
1388 Negative indices are supported.
1390 Runtime complexity: `O(log(n))` -- approximate.
1392 >>> sl = SortedList('abcde')
1393 >>> sl.index('d')
1394 3
1395 >>> sl.index('z')
1396 Traceback (most recent call last):
1397 ...
1398 ValueError: 'z' is not in list
1400 :param value: value in sorted list
1401 :param int start: start index (default None, start of sorted list)
1402 :param int stop: stop index (default None, end of sorted list)
1403 :return: index of value
1404 :raises ValueError: if value is not present
1406 """
1407 _len = self._len
1409 if not _len:
1410 raise ValueError('{0!r} is not in list'.format(value))
1412 if start is None:
1413 start = 0
1414 if start < 0:
1415 start += _len
1416 if start < 0:
1417 start = 0
1419 if stop is None:
1420 stop = _len
1421 if stop < 0:
1422 stop += _len
1423 if stop > _len:
1424 stop = _len
1426 if stop <= start:
1427 raise ValueError('{0!r} is not in list'.format(value))
1429 _maxes = self._maxes
1430 pos_left = bisect_left(_maxes, value)
1432 if pos_left == len(_maxes):
1433 raise ValueError('{0!r} is not in list'.format(value))
1435 _lists = self._lists
1436 idx_left = bisect_left(_lists[pos_left], value)
1438 if _lists[pos_left][idx_left] != value:
1439 raise ValueError('{0!r} is not in list'.format(value))
1441 stop -= 1
1442 left = self._loc(pos_left, idx_left)
1444 if start <= left:
1445 if left <= stop:
1446 return left
1447 else:
1448 right = self._bisect_right(value) - 1
1450 if start <= right:
1451 return start
1453 raise ValueError('{0!r} is not in list'.format(value))
1456 def __add__(self, other):
1457 """Return new sorted list containing all values in both sequences.
1459 ``sl.__add__(other)`` <==> ``sl + other``
1461 Values in `other` do not need to be in sorted order.
1463 Runtime complexity: `O(n*log(n))`
1465 >>> sl1 = SortedList('bat')
1466 >>> sl2 = SortedList('cat')
1467 >>> sl1 + sl2
1468 SortedList(['a', 'a', 'b', 'c', 't', 't'])
1470 :param other: other iterable
1471 :return: new sorted list
1473 """
1474 values = reduce(iadd, self._lists, [])
1475 values.extend(other)
1476 return self.__class__(values)
1478 __radd__ = __add__
1481 def __iadd__(self, other):
1482 """Update sorted list with values from `other`.
1484 ``sl.__iadd__(other)`` <==> ``sl += other``
1486 Values in `other` do not need to be in sorted order.
1488 Runtime complexity: `O(k*log(n))` -- approximate.
1490 >>> sl = SortedList('bat')
1491 >>> sl += 'cat'
1492 >>> sl
1493 SortedList(['a', 'a', 'b', 'c', 't', 't'])
1495 :param other: other iterable
1496 :return: existing sorted list
1498 """
1499 self._update(other)
1500 return self
1503 def __mul__(self, num):
1504 """Return new sorted list with `num` shallow copies of values.
1506 ``sl.__mul__(num)`` <==> ``sl * num``
1508 Runtime complexity: `O(n*log(n))`
1510 >>> sl = SortedList('abc')
1511 >>> sl * 3
1512 SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
1514 :param int num: count of shallow copies
1515 :return: new sorted list
1517 """
1518 values = reduce(iadd, self._lists, []) * num
1519 return self.__class__(values)
1521 __rmul__ = __mul__
1524 def __imul__(self, num):
1525 """Update the sorted list with `num` shallow copies of values.
1527 ``sl.__imul__(num)`` <==> ``sl *= num``
1529 Runtime complexity: `O(n*log(n))`
1531 >>> sl = SortedList('abc')
1532 >>> sl *= 3
1533 >>> sl
1534 SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
1536 :param int num: count of shallow copies
1537 :return: existing sorted list
1539 """
1540 values = reduce(iadd, self._lists, []) * num
1541 self._clear()
1542 self._update(values)
1543 return self
1546 def __make_cmp(seq_op, symbol, doc):
1547 "Make comparator method."
1548 def comparer(self, other):
1549 "Compare method for sorted list and sequence."
1550 if not isinstance(other, Sequence):
1551 return NotImplemented
1553 self_len = self._len
1554 len_other = len(other)
1556 if self_len != len_other:
1557 if seq_op is eq:
1558 return False
1559 if seq_op is ne:
1560 return True
1562 for alpha, beta in zip(self, other):
1563 if alpha != beta:
1564 return seq_op(alpha, beta)
1566 return seq_op(self_len, len_other)
1568 seq_op_name = seq_op.__name__
1569 comparer.__name__ = '__{0}__'.format(seq_op_name)
1570 doc_str = """Return true if and only if sorted list is {0} `other`.
1572 ``sl.__{1}__(other)`` <==> ``sl {2} other``
1574 Comparisons use lexicographical order as with sequences.
1576 Runtime complexity: `O(n)`
1578 :param other: `other` sequence
1579 :return: true if sorted list is {0} `other`
1581 """
1582 comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
1583 return comparer
1586 __eq__ = __make_cmp(eq, '==', 'equal to')
1587 __ne__ = __make_cmp(ne, '!=', 'not equal to')
1588 __lt__ = __make_cmp(lt, '<', 'less than')
1589 __gt__ = __make_cmp(gt, '>', 'greater than')
1590 __le__ = __make_cmp(le, '<=', 'less than or equal to')
1591 __ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
1592 __make_cmp = staticmethod(__make_cmp)
1595 def __reduce__(self):
1596 values = reduce(iadd, self._lists, [])
1597 return (type(self), (values,))
1600 @recursive_repr()
1601 def __repr__(self):
1602 """Return string representation of sorted list.
1604 ``sl.__repr__()`` <==> ``repr(sl)``
1606 :return: string representation
1608 """
1609 return '{0}({1!r})'.format(type(self).__name__, list(self))
1612 def _check(self):
1613 """Check invariants of sorted list.
1615 Runtime complexity: `O(n)`
1617 """
1618 try:
1619 assert self._load >= 4
1620 assert len(self._maxes) == len(self._lists)
1621 assert self._len == sum(len(sublist) for sublist in self._lists)
1623 # Check all sublists are sorted.
1625 for sublist in self._lists:
1626 for pos in range(1, len(sublist)):
1627 assert sublist[pos - 1] <= sublist[pos]
1629 # Check beginning/end of sublists are sorted.
1631 for pos in range(1, len(self._lists)):
1632 assert self._lists[pos - 1][-1] <= self._lists[pos][0]
1634 # Check _maxes index is the last value of each sublist.
1636 for pos in range(len(self._maxes)):
1637 assert self._maxes[pos] == self._lists[pos][-1]
1639 # Check sublist lengths are less than double load-factor.
1641 double = self._load << 1
1642 assert all(len(sublist) <= double for sublist in self._lists)
1644 # Check sublist lengths are greater than half load-factor for all
1645 # but the last sublist.
1647 half = self._load >> 1
1648 for pos in range(0, len(self._lists) - 1):
1649 assert len(self._lists[pos]) >= half
1651 if self._index:
1652 assert self._len == self._index[0]
1653 assert len(self._index) == self._offset + len(self._lists)
1655 # Check index leaf nodes equal length of sublists.
1657 for pos in range(len(self._lists)):
1658 leaf = self._index[self._offset + pos]
1659 assert leaf == len(self._lists[pos])
1661 # Check index branch nodes are the sum of their children.
1663 for pos in range(self._offset):
1664 child = (pos << 1) + 1
1665 if child >= len(self._index):
1666 assert self._index[pos] == 0
1667 elif child + 1 == len(self._index):
1668 assert self._index[pos] == self._index[child]
1669 else:
1670 child_sum = self._index[child] + self._index[child + 1]
1671 assert child_sum == self._index[pos]
1672 except:
1673 traceback.print_exc(file=sys.stdout)
1674 print('len', self._len)
1675 print('load', self._load)
1676 print('offset', self._offset)
1677 print('len_index', len(self._index))
1678 print('index', self._index)
1679 print('len_maxes', len(self._maxes))
1680 print('maxes', self._maxes)
1681 print('len_lists', len(self._lists))
1682 print('lists', self._lists)
1683 raise
1686def identity(value):
1687 "Identity function."
1688 return value
1691class SortedKeyList(SortedList):
1692 """Sorted-key list is a subtype of sorted list.
1694 The sorted-key list maintains values in comparison order based on the
1695 result of a key function applied to every value.
1697 All the same methods that are available in :class:`SortedList` are also
1698 available in :class:`SortedKeyList`.
1700 Additional methods provided:
1702 * :attr:`SortedKeyList.key`
1703 * :func:`SortedKeyList.bisect_key_left`
1704 * :func:`SortedKeyList.bisect_key_right`
1705 * :func:`SortedKeyList.irange_key`
1707 Some examples below use:
1709 >>> from operator import neg
1710 >>> neg
1711 <built-in function neg>
1712 >>> neg(1)
1713 -1
1715 """
1716 def __init__(self, iterable=None, key=identity):
1717 """Initialize sorted-key list instance.
1719 Optional `iterable` argument provides an initial iterable of values to
1720 initialize the sorted-key list.
1722 Optional `key` argument defines a callable that, like the `key`
1723 argument to Python's `sorted` function, extracts a comparison key from
1724 each value. The default is the identity function.
1726 Runtime complexity: `O(n*log(n))`
1728 >>> from operator import neg
1729 >>> skl = SortedKeyList(key=neg)
1730 >>> skl
1731 SortedKeyList([], key=<built-in function neg>)
1732 >>> skl = SortedKeyList([3, 1, 2], key=neg)
1733 >>> skl
1734 SortedKeyList([3, 2, 1], key=<built-in function neg>)
1736 :param iterable: initial values (optional)
1737 :param key: function used to extract comparison key (optional)
1739 """
1740 self._key = key
1741 self._len = 0
1742 self._load = self.DEFAULT_LOAD_FACTOR
1743 self._lists = []
1744 self._keys = []
1745 self._maxes = []
1746 self._index = []
1747 self._offset = 0
1749 if iterable is not None:
1750 self._update(iterable)
1753 def __new__(cls, iterable=None, key=identity):
1754 return object.__new__(cls)
1757 @property
1758 def key(self):
1759 "Function used to extract comparison key from values."
1760 return self._key
1763 def clear(self):
1764 """Remove all values from sorted-key list.
1766 Runtime complexity: `O(n)`
1768 """
1769 self._len = 0
1770 del self._lists[:]
1771 del self._keys[:]
1772 del self._maxes[:]
1773 del self._index[:]
1775 _clear = clear
1778 def add(self, value):
1779 """Add `value` to sorted-key list.
1781 Runtime complexity: `O(log(n))` -- approximate.
1783 >>> from operator import neg
1784 >>> skl = SortedKeyList(key=neg)
1785 >>> skl.add(3)
1786 >>> skl.add(1)
1787 >>> skl.add(2)
1788 >>> skl
1789 SortedKeyList([3, 2, 1], key=<built-in function neg>)
1791 :param value: value to add to sorted-key list
1793 """
1794 _lists = self._lists
1795 _keys = self._keys
1796 _maxes = self._maxes
1798 key = self._key(value)
1800 if _maxes:
1801 pos = bisect_right(_maxes, key)
1803 if pos == len(_maxes):
1804 pos -= 1
1805 _lists[pos].append(value)
1806 _keys[pos].append(key)
1807 _maxes[pos] = key
1808 else:
1809 idx = bisect_right(_keys[pos], key)
1810 _lists[pos].insert(idx, value)
1811 _keys[pos].insert(idx, key)
1813 self._expand(pos)
1814 else:
1815 _lists.append([value])
1816 _keys.append([key])
1817 _maxes.append(key)
1819 self._len += 1
1822 def _expand(self, pos):
1823 """Split sublists with length greater than double the load-factor.
1825 Updates the index when the sublist length is less than double the load
1826 level. This requires incrementing the nodes in a traversal from the
1827 leaf node to the root. For an example traversal see
1828 ``SortedList._loc``.
1830 """
1831 _lists = self._lists
1832 _keys = self._keys
1833 _index = self._index
1835 if len(_keys[pos]) > (self._load << 1):
1836 _maxes = self._maxes
1837 _load = self._load
1839 _lists_pos = _lists[pos]
1840 _keys_pos = _keys[pos]
1841 half = _lists_pos[_load:]
1842 half_keys = _keys_pos[_load:]
1843 del _lists_pos[_load:]
1844 del _keys_pos[_load:]
1845 _maxes[pos] = _keys_pos[-1]
1847 _lists.insert(pos + 1, half)
1848 _keys.insert(pos + 1, half_keys)
1849 _maxes.insert(pos + 1, half_keys[-1])
1851 del _index[:]
1852 else:
1853 if _index:
1854 child = self._offset + pos
1855 while child:
1856 _index[child] += 1
1857 child = (child - 1) >> 1
1858 _index[0] += 1
1861 def update(self, iterable):
1862 """Update sorted-key list by adding all values from `iterable`.
1864 Runtime complexity: `O(k*log(n))` -- approximate.
1866 >>> from operator import neg
1867 >>> skl = SortedKeyList(key=neg)
1868 >>> skl.update([3, 1, 2])
1869 >>> skl
1870 SortedKeyList([3, 2, 1], key=<built-in function neg>)
1872 :param iterable: iterable of values to add
1874 """
1875 _lists = self._lists
1876 _keys = self._keys
1877 _maxes = self._maxes
1878 values = sorted(iterable, key=self._key)
1880 if _maxes:
1881 if len(values) * 4 >= self._len:
1882 _lists.append(values)
1883 values = reduce(iadd, _lists, [])
1884 values.sort(key=self._key)
1885 self._clear()
1886 else:
1887 _add = self.add
1888 for val in values:
1889 _add(val)
1890 return
1892 _load = self._load
1893 _lists.extend(values[pos:(pos + _load)]
1894 for pos in range(0, len(values), _load))
1895 _keys.extend(list(map(self._key, _list)) for _list in _lists)
1896 _maxes.extend(sublist[-1] for sublist in _keys)
1897 self._len = len(values)
1898 del self._index[:]
1900 _update = update
1903 def __contains__(self, value):
1904 """Return true if `value` is an element of the sorted-key list.
1906 ``skl.__contains__(value)`` <==> ``value in skl``
1908 Runtime complexity: `O(log(n))`
1910 >>> from operator import neg
1911 >>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
1912 >>> 3 in skl
1913 True
1915 :param value: search for value in sorted-key list
1916 :return: true if `value` in sorted-key list
1918 """
1919 _maxes = self._maxes
1921 if not _maxes:
1922 return False
1924 key = self._key(value)
1925 pos = bisect_left(_maxes, key)
1927 if pos == len(_maxes):
1928 return False
1930 _lists = self._lists
1931 _keys = self._keys
1933 idx = bisect_left(_keys[pos], key)
1935 len_keys = len(_keys)
1936 len_sublist = len(_keys[pos])
1938 while True:
1939 if _keys[pos][idx] != key:
1940 return False
1941 if _lists[pos][idx] == value:
1942 return True
1943 idx += 1
1944 if idx == len_sublist:
1945 pos += 1
1946 if pos == len_keys:
1947 return False
1948 len_sublist = len(_keys[pos])
1949 idx = 0
1952 def discard(self, value):
1953 """Remove `value` from sorted-key list if it is a member.
1955 If `value` is not a member, do nothing.
1957 Runtime complexity: `O(log(n))` -- approximate.
1959 >>> from operator import neg
1960 >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
1961 >>> skl.discard(1)
1962 >>> skl.discard(0)
1963 >>> skl == [5, 4, 3, 2]
1964 True
1966 :param value: `value` to discard from sorted-key list
1968 """
1969 _maxes = self._maxes
1971 if not _maxes:
1972 return
1974 key = self._key(value)
1975 pos = bisect_left(_maxes, key)
1977 if pos == len(_maxes):
1978 return
1980 _lists = self._lists
1981 _keys = self._keys
1982 idx = bisect_left(_keys[pos], key)
1983 len_keys = len(_keys)
1984 len_sublist = len(_keys[pos])
1986 while True:
1987 if _keys[pos][idx] != key:
1988 return
1989 if _lists[pos][idx] == value:
1990 self._delete(pos, idx)
1991 return
1992 idx += 1
1993 if idx == len_sublist:
1994 pos += 1
1995 if pos == len_keys:
1996 return
1997 len_sublist = len(_keys[pos])
1998 idx = 0
2001 def remove(self, value):
2002 """Remove `value` from sorted-key list; `value` must be a member.
2004 If `value` is not a member, raise ValueError.
2006 Runtime complexity: `O(log(n))` -- approximate.
2008 >>> from operator import neg
2009 >>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
2010 >>> skl.remove(5)
2011 >>> skl == [4, 3, 2, 1]
2012 True
2013 >>> skl.remove(0)
2014 Traceback (most recent call last):
2015 ...
2016 ValueError: 0 not in list
2018 :param value: `value` to remove from sorted-key list
2019 :raises ValueError: if `value` is not in sorted-key list
2021 """
2022 _maxes = self._maxes
2024 if not _maxes:
2025 raise ValueError('{0!r} not in list'.format(value))
2027 key = self._key(value)
2028 pos = bisect_left(_maxes, key)
2030 if pos == len(_maxes):
2031 raise ValueError('{0!r} not in list'.format(value))
2033 _lists = self._lists
2034 _keys = self._keys
2035 idx = bisect_left(_keys[pos], key)
2036 len_keys = len(_keys)
2037 len_sublist = len(_keys[pos])
2039 while True:
2040 if _keys[pos][idx] != key:
2041 raise ValueError('{0!r} not in list'.format(value))
2042 if _lists[pos][idx] == value:
2043 self._delete(pos, idx)
2044 return
2045 idx += 1
2046 if idx == len_sublist:
2047 pos += 1
2048 if pos == len_keys:
2049 raise ValueError('{0!r} not in list'.format(value))
2050 len_sublist = len(_keys[pos])
2051 idx = 0
2054 def _delete(self, pos, idx):
2055 """Delete value at the given `(pos, idx)`.
2057 Combines lists that are less than half the load level.
2059 Updates the index when the sublist length is more than half the load
2060 level. This requires decrementing the nodes in a traversal from the
2061 leaf node to the root. For an example traversal see
2062 ``SortedList._loc``.
2064 :param int pos: lists index
2065 :param int idx: sublist index
2067 """
2068 _lists = self._lists
2069 _keys = self._keys
2070 _maxes = self._maxes
2071 _index = self._index
2072 keys_pos = _keys[pos]
2073 lists_pos = _lists[pos]
2075 del keys_pos[idx]
2076 del lists_pos[idx]
2077 self._len -= 1
2079 len_keys_pos = len(keys_pos)
2081 if len_keys_pos > (self._load >> 1):
2082 _maxes[pos] = keys_pos[-1]
2084 if _index:
2085 child = self._offset + pos
2086 while child > 0:
2087 _index[child] -= 1
2088 child = (child - 1) >> 1
2089 _index[0] -= 1
2090 elif len(_keys) > 1:
2091 if not pos:
2092 pos += 1
2094 prev = pos - 1
2095 _keys[prev].extend(_keys[pos])
2096 _lists[prev].extend(_lists[pos])
2097 _maxes[prev] = _keys[prev][-1]
2099 del _lists[pos]
2100 del _keys[pos]
2101 del _maxes[pos]
2102 del _index[:]
2104 self._expand(prev)
2105 elif len_keys_pos:
2106 _maxes[pos] = keys_pos[-1]
2107 else:
2108 del _lists[pos]
2109 del _keys[pos]
2110 del _maxes[pos]
2111 del _index[:]
2114 def irange(self, minimum=None, maximum=None, inclusive=(True, True),
2115 reverse=False):
2116 """Create an iterator of values between `minimum` and `maximum`.
2118 Both `minimum` and `maximum` default to `None` which is automatically
2119 inclusive of the beginning and end of the sorted-key list.
2121 The argument `inclusive` is a pair of booleans that indicates whether
2122 the minimum and maximum ought to be included in the range,
2123 respectively. The default is ``(True, True)`` such that the range is
2124 inclusive of both minimum and maximum.
2126 When `reverse` is `True` the values are yielded from the iterator in
2127 reverse order; `reverse` defaults to `False`.
2129 >>> from operator import neg
2130 >>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
2131 >>> it = skl.irange(14.5, 11.5)
2132 >>> list(it)
2133 [14, 13, 12]
2135 :param minimum: minimum value to start iterating
2136 :param maximum: maximum value to stop iterating
2137 :param inclusive: pair of booleans
2138 :param bool reverse: yield values in reverse order
2139 :return: iterator
2141 """
2142 min_key = self._key(minimum) if minimum is not None else None
2143 max_key = self._key(maximum) if maximum is not None else None
2144 return self._irange_key(
2145 min_key=min_key, max_key=max_key,
2146 inclusive=inclusive, reverse=reverse,
2147 )
2150 def irange_key(self, min_key=None, max_key=None, inclusive=(True, True),
2151 reverse=False):
2152 """Create an iterator of values between `min_key` and `max_key`.
2154 Both `min_key` and `max_key` default to `None` which is automatically
2155 inclusive of the beginning and end of the sorted-key list.
2157 The argument `inclusive` is a pair of booleans that indicates whether
2158 the minimum and maximum ought to be included in the range,
2159 respectively. The default is ``(True, True)`` such that the range is
2160 inclusive of both minimum and maximum.
2162 When `reverse` is `True` the values are yielded from the iterator in
2163 reverse order; `reverse` defaults to `False`.
2165 >>> from operator import neg
2166 >>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
2167 >>> it = skl.irange_key(-14, -12)
2168 >>> list(it)
2169 [14, 13, 12]
2171 :param min_key: minimum key to start iterating
2172 :param max_key: maximum key to stop iterating
2173 :param inclusive: pair of booleans
2174 :param bool reverse: yield values in reverse order
2175 :return: iterator
2177 """
2178 _maxes = self._maxes
2180 if not _maxes:
2181 return iter(())
2183 _keys = self._keys
2185 # Calculate the minimum (pos, idx) pair. By default this location
2186 # will be inclusive in our calculation.
2188 if min_key is None:
2189 min_pos = 0
2190 min_idx = 0
2191 else:
2192 if inclusive[0]:
2193 min_pos = bisect_left(_maxes, min_key)
2195 if min_pos == len(_maxes):
2196 return iter(())
2198 min_idx = bisect_left(_keys[min_pos], min_key)
2199 else:
2200 min_pos = bisect_right(_maxes, min_key)
2202 if min_pos == len(_maxes):
2203 return iter(())
2205 min_idx = bisect_right(_keys[min_pos], min_key)
2207 # Calculate the maximum (pos, idx) pair. By default this location
2208 # will be exclusive in our calculation.
2210 if max_key is None:
2211 max_pos = len(_maxes) - 1
2212 max_idx = len(_keys[max_pos])
2213 else:
2214 if inclusive[1]:
2215 max_pos = bisect_right(_maxes, max_key)
2217 if max_pos == len(_maxes):
2218 max_pos -= 1
2219 max_idx = len(_keys[max_pos])
2220 else:
2221 max_idx = bisect_right(_keys[max_pos], max_key)
2222 else:
2223 max_pos = bisect_left(_maxes, max_key)
2225 if max_pos == len(_maxes):
2226 max_pos -= 1
2227 max_idx = len(_keys[max_pos])
2228 else:
2229 max_idx = bisect_left(_keys[max_pos], max_key)
2231 return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
2233 _irange_key = irange_key
2236 def bisect_left(self, value):
2237 """Return an index to insert `value` in the sorted-key list.
2239 If the `value` is already present, the insertion point will be before
2240 (to the left of) any existing values.
2242 Similar to the `bisect` module in the standard library.
2244 Runtime complexity: `O(log(n))` -- approximate.
2246 >>> from operator import neg
2247 >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
2248 >>> skl.bisect_left(1)
2249 4
2251 :param value: insertion index of value in sorted-key list
2252 :return: index
2254 """
2255 return self._bisect_key_left(self._key(value))
2258 def bisect_right(self, value):
2259 """Return an index to insert `value` in the sorted-key list.
2261 Similar to `bisect_left`, but if `value` is already present, the
2262 insertion point will be after (to the right of) any existing values.
2264 Similar to the `bisect` module in the standard library.
2266 Runtime complexity: `O(log(n))` -- approximate.
2268 >>> from operator import neg
2269 >>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
2270 >>> skl.bisect_right(1)
2271 5
2273 :param value: insertion index of value in sorted-key list
2274 :return: index
2276 """
2277 return self._bisect_key_right(self._key(value))
2279 bisect = bisect_right
2282 def bisect_key_left(self, key):
2283 """Return an index to insert `key` in the sorted-key list.
2285 If the `key` is already present, the insertion point will be before (to
2286 the left of) any existing keys.
2288 Similar to the `bisect` module in the standard library.
2290 Runtime complexity: `O(log(n))` -- approximate.
2292 >>> from operator import neg
2293 >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
2294 >>> skl.bisect_key_left(-1)
2295 4
2297 :param key: insertion index of key in sorted-key list
2298 :return: index
2300 """
2301 _maxes = self._maxes
2303 if not _maxes:
2304 return 0
2306 pos = bisect_left(_maxes, key)
2308 if pos == len(_maxes):
2309 return self._len
2311 idx = bisect_left(self._keys[pos], key)
2313 return self._loc(pos, idx)
2315 _bisect_key_left = bisect_key_left
2318 def bisect_key_right(self, key):
2319 """Return an index to insert `key` in the sorted-key list.
2321 Similar to `bisect_key_left`, but if `key` is already present, the
2322 insertion point will be after (to the right of) any existing keys.
2324 Similar to the `bisect` module in the standard library.
2326 Runtime complexity: `O(log(n))` -- approximate.
2328 >>> from operator import neg
2329 >>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
2330 >>> skl.bisect_key_right(-1)
2331 5
2333 :param key: insertion index of key in sorted-key list
2334 :return: index
2336 """
2337 _maxes = self._maxes
2339 if not _maxes:
2340 return 0
2342 pos = bisect_right(_maxes, key)
2344 if pos == len(_maxes):
2345 return self._len
2347 idx = bisect_right(self._keys[pos], key)
2349 return self._loc(pos, idx)
2351 bisect_key = bisect_key_right
2352 _bisect_key_right = bisect_key_right
2355 def count(self, value):
2356 """Return number of occurrences of `value` in the sorted-key list.
2358 Runtime complexity: `O(log(n))` -- approximate.
2360 >>> from operator import neg
2361 >>> skl = SortedKeyList([4, 4, 4, 4, 3, 3, 3, 2, 2, 1], key=neg)
2362 >>> skl.count(2)
2363 2
2365 :param value: value to count in sorted-key list
2366 :return: count
2368 """
2369 _maxes = self._maxes
2371 if not _maxes:
2372 return 0
2374 key = self._key(value)
2375 pos = bisect_left(_maxes, key)
2377 if pos == len(_maxes):
2378 return 0
2380 _lists = self._lists
2381 _keys = self._keys
2382 idx = bisect_left(_keys[pos], key)
2383 total = 0
2384 len_keys = len(_keys)
2385 len_sublist = len(_keys[pos])
2387 while True:
2388 if _keys[pos][idx] != key:
2389 return total
2390 if _lists[pos][idx] == value:
2391 total += 1
2392 idx += 1
2393 if idx == len_sublist:
2394 pos += 1
2395 if pos == len_keys:
2396 return total
2397 len_sublist = len(_keys[pos])
2398 idx = 0
2401 def copy(self):
2402 """Return a shallow copy of the sorted-key list.
2404 Runtime complexity: `O(n)`
2406 :return: new sorted-key list
2408 """
2409 return self.__class__(self, key=self._key)
2411 __copy__ = copy
2414 def index(self, value, start=None, stop=None):
2415 """Return first index of value in sorted-key list.
2417 Raise ValueError if `value` is not present.
2419 Index must be between `start` and `stop` for the `value` to be
2420 considered present. The default value, None, for `start` and `stop`
2421 indicate the beginning and end of the sorted-key list.
2423 Negative indices are supported.
2425 Runtime complexity: `O(log(n))` -- approximate.
2427 >>> from operator import neg
2428 >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
2429 >>> skl.index(2)
2430 3
2431 >>> skl.index(0)
2432 Traceback (most recent call last):
2433 ...
2434 ValueError: 0 is not in list
2436 :param value: value in sorted-key list
2437 :param int start: start index (default None, start of sorted-key list)
2438 :param int stop: stop index (default None, end of sorted-key list)
2439 :return: index of value
2440 :raises ValueError: if value is not present
2442 """
2443 _len = self._len
2445 if not _len:
2446 raise ValueError('{0!r} is not in list'.format(value))
2448 if start is None:
2449 start = 0
2450 if start < 0:
2451 start += _len
2452 if start < 0:
2453 start = 0
2455 if stop is None:
2456 stop = _len
2457 if stop < 0:
2458 stop += _len
2459 if stop > _len:
2460 stop = _len
2462 if stop <= start:
2463 raise ValueError('{0!r} is not in list'.format(value))
2465 _maxes = self._maxes
2466 key = self._key(value)
2467 pos = bisect_left(_maxes, key)
2469 if pos == len(_maxes):
2470 raise ValueError('{0!r} is not in list'.format(value))
2472 stop -= 1
2473 _lists = self._lists
2474 _keys = self._keys
2475 idx = bisect_left(_keys[pos], key)
2476 len_keys = len(_keys)
2477 len_sublist = len(_keys[pos])
2479 while True:
2480 if _keys[pos][idx] != key:
2481 raise ValueError('{0!r} is not in list'.format(value))
2482 if _lists[pos][idx] == value:
2483 loc = self._loc(pos, idx)
2484 if start <= loc <= stop:
2485 return loc
2486 elif loc > stop:
2487 break
2488 idx += 1
2489 if idx == len_sublist:
2490 pos += 1
2491 if pos == len_keys:
2492 raise ValueError('{0!r} is not in list'.format(value))
2493 len_sublist = len(_keys[pos])
2494 idx = 0
2496 raise ValueError('{0!r} is not in list'.format(value))
2499 def __add__(self, other):
2500 """Return new sorted-key list containing all values in both sequences.
2502 ``skl.__add__(other)`` <==> ``skl + other``
2504 Values in `other` do not need to be in sorted-key order.
2506 Runtime complexity: `O(n*log(n))`
2508 >>> from operator import neg
2509 >>> skl1 = SortedKeyList([5, 4, 3], key=neg)
2510 >>> skl2 = SortedKeyList([2, 1, 0], key=neg)
2511 >>> skl1 + skl2
2512 SortedKeyList([5, 4, 3, 2, 1, 0], key=<built-in function neg>)
2514 :param other: other iterable
2515 :return: new sorted-key list
2517 """
2518 values = reduce(iadd, self._lists, [])
2519 values.extend(other)
2520 return self.__class__(values, key=self._key)
2522 __radd__ = __add__
2525 def __mul__(self, num):
2526 """Return new sorted-key list with `num` shallow copies of values.
2528 ``skl.__mul__(num)`` <==> ``skl * num``
2530 Runtime complexity: `O(n*log(n))`
2532 >>> from operator import neg
2533 >>> skl = SortedKeyList([3, 2, 1], key=neg)
2534 >>> skl * 2
2535 SortedKeyList([3, 3, 2, 2, 1, 1], key=<built-in function neg>)
2537 :param int num: count of shallow copies
2538 :return: new sorted-key list
2540 """
2541 values = reduce(iadd, self._lists, []) * num
2542 return self.__class__(values, key=self._key)
2545 def __reduce__(self):
2546 values = reduce(iadd, self._lists, [])
2547 return (type(self), (values, self.key))
2550 @recursive_repr()
2551 def __repr__(self):
2552 """Return string representation of sorted-key list.
2554 ``skl.__repr__()`` <==> ``repr(skl)``
2556 :return: string representation
2558 """
2559 type_name = type(self).__name__
2560 return '{0}({1!r}, key={2!r})'.format(type_name, list(self), self._key)
2563 def _check(self):
2564 """Check invariants of sorted-key list.
2566 Runtime complexity: `O(n)`
2568 """
2569 try:
2570 assert self._load >= 4
2571 assert len(self._maxes) == len(self._lists) == len(self._keys)
2572 assert self._len == sum(len(sublist) for sublist in self._lists)
2574 # Check all sublists are sorted.
2576 for sublist in self._keys:
2577 for pos in range(1, len(sublist)):
2578 assert sublist[pos - 1] <= sublist[pos]
2580 # Check beginning/end of sublists are sorted.
2582 for pos in range(1, len(self._keys)):
2583 assert self._keys[pos - 1][-1] <= self._keys[pos][0]
2585 # Check _keys matches _key mapped to _lists.
2587 for val_sublist, key_sublist in zip(self._lists, self._keys):
2588 assert len(val_sublist) == len(key_sublist)
2589 for val, key in zip(val_sublist, key_sublist):
2590 assert self._key(val) == key
2592 # Check _maxes index is the last value of each sublist.
2594 for pos in range(len(self._maxes)):
2595 assert self._maxes[pos] == self._keys[pos][-1]
2597 # Check sublist lengths are less than double load-factor.
2599 double = self._load << 1
2600 assert all(len(sublist) <= double for sublist in self._lists)
2602 # Check sublist lengths are greater than half load-factor for all
2603 # but the last sublist.
2605 half = self._load >> 1
2606 for pos in range(0, len(self._lists) - 1):
2607 assert len(self._lists[pos]) >= half
2609 if self._index:
2610 assert self._len == self._index[0]
2611 assert len(self._index) == self._offset + len(self._lists)
2613 # Check index leaf nodes equal length of sublists.
2615 for pos in range(len(self._lists)):
2616 leaf = self._index[self._offset + pos]
2617 assert leaf == len(self._lists[pos])
2619 # Check index branch nodes are the sum of their children.
2621 for pos in range(self._offset):
2622 child = (pos << 1) + 1
2623 if child >= len(self._index):
2624 assert self._index[pos] == 0
2625 elif child + 1 == len(self._index):
2626 assert self._index[pos] == self._index[child]
2627 else:
2628 child_sum = self._index[child] + self._index[child + 1]
2629 assert child_sum == self._index[pos]
2630 except:
2631 traceback.print_exc(file=sys.stdout)
2632 print('len', self._len)
2633 print('load', self._load)
2634 print('offset', self._offset)
2635 print('len_index', len(self._index))
2636 print('index', self._index)
2637 print('len_maxes', len(self._maxes))
2638 print('maxes', self._maxes)
2639 print('len_keys', len(self._keys))
2640 print('keys', self._keys)
2641 print('len_lists', len(self._lists))
2642 print('lists', self._lists)
2643 raise
2646SortedListWithKey = SortedKeyList