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 Dict
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 dict implementations:
10.. currentmodule:: sortedcontainers
12* :class:`SortedDict`
13* :class:`SortedKeysView`
14* :class:`SortedItemsView`
15* :class:`SortedValuesView`
17"""
19import sys
20import warnings
22from itertools import chain
24from .sortedlist import SortedList, recursive_repr
25from .sortedset import SortedSet
27###############################################################################
28# BEGIN Python 2/3 Shims
29###############################################################################
31try:
32 from collections.abc import (
33 ItemsView, KeysView, Mapping, ValuesView, Sequence
34 )
35except ImportError:
36 from collections import ItemsView, KeysView, Mapping, ValuesView, Sequence
38###############################################################################
39# END Python 2/3 Shims
40###############################################################################
43class SortedDict(dict):
44 """Sorted dict is a sorted mutable mapping.
46 Sorted dict keys are maintained in sorted order. The design of sorted dict
47 is simple: sorted dict inherits from dict to store items and maintains a
48 sorted list of keys.
50 Sorted dict keys must be hashable and comparable. The hash and total
51 ordering of keys must not change while they are stored in the sorted dict.
53 Mutable mapping methods:
55 * :func:`SortedDict.__getitem__` (inherited from dict)
56 * :func:`SortedDict.__setitem__`
57 * :func:`SortedDict.__delitem__`
58 * :func:`SortedDict.__iter__`
59 * :func:`SortedDict.__len__` (inherited from dict)
61 Methods for adding items:
63 * :func:`SortedDict.setdefault`
64 * :func:`SortedDict.update`
66 Methods for removing items:
68 * :func:`SortedDict.clear`
69 * :func:`SortedDict.pop`
70 * :func:`SortedDict.popitem`
72 Methods for looking up items:
74 * :func:`SortedDict.__contains__` (inherited from dict)
75 * :func:`SortedDict.get` (inherited from dict)
76 * :func:`SortedDict.peekitem`
78 Methods for views:
80 * :func:`SortedDict.keys`
81 * :func:`SortedDict.items`
82 * :func:`SortedDict.values`
84 Methods for miscellany:
86 * :func:`SortedDict.copy`
87 * :func:`SortedDict.fromkeys`
88 * :func:`SortedDict.__reversed__`
89 * :func:`SortedDict.__eq__` (inherited from dict)
90 * :func:`SortedDict.__ne__` (inherited from dict)
91 * :func:`SortedDict.__repr__`
92 * :func:`SortedDict._check`
94 Sorted list methods available (applies to keys):
96 * :func:`SortedList.bisect_left`
97 * :func:`SortedList.bisect_right`
98 * :func:`SortedList.count`
99 * :func:`SortedList.index`
100 * :func:`SortedList.irange`
101 * :func:`SortedList.islice`
102 * :func:`SortedList._reset`
104 Additional sorted list methods available, if key-function used:
106 * :func:`SortedKeyList.bisect_key_left`
107 * :func:`SortedKeyList.bisect_key_right`
108 * :func:`SortedKeyList.irange_key`
110 Sorted dicts may only be compared for equality and inequality.
112 """
113 def __init__(self, *args, **kwargs):
114 """Initialize sorted dict instance.
116 Optional key-function argument defines a callable that, like the `key`
117 argument to the built-in `sorted` function, extracts a comparison key
118 from each dictionary key. If no function is specified, the default
119 compares the dictionary keys directly. The key-function argument must
120 be provided as a positional argument and must come before all other
121 arguments.
123 Optional iterable argument provides an initial sequence of pairs to
124 initialize the sorted dict. Each pair in the sequence defines the key
125 and corresponding value. If a key is seen more than once, the last
126 value associated with it is stored in the new sorted dict.
128 Optional mapping argument provides an initial mapping of items to
129 initialize the sorted dict.
131 If keyword arguments are given, the keywords themselves, with their
132 associated values, are added as items to the dictionary. If a key is
133 specified both in the positional argument and as a keyword argument,
134 the value associated with the keyword is stored in the
135 sorted dict.
137 Sorted dict keys must be hashable, per the requirement for Python's
138 dictionaries. Keys (or the result of the key-function) must also be
139 comparable, per the requirement for sorted lists.
141 >>> d = {'alpha': 1, 'beta': 2}
142 >>> SortedDict([('alpha', 1), ('beta', 2)]) == d
143 True
144 >>> SortedDict({'alpha': 1, 'beta': 2}) == d
145 True
146 >>> SortedDict(alpha=1, beta=2) == d
147 True
149 """
150 if args and (args[0] is None or callable(args[0])):
151 _key = self._key = args[0]
152 args = args[1:]
153 else:
154 _key = self._key = None
156 self._list = SortedList(key=_key)
158 # Reaching through ``self._list`` repeatedly adds unnecessary overhead
159 # so cache references to sorted list methods.
161 _list = self._list
162 self._list_add = _list.add
163 self._list_clear = _list.clear
164 self._list_iter = _list.__iter__
165 self._list_reversed = _list.__reversed__
166 self._list_pop = _list.pop
167 self._list_remove = _list.remove
168 self._list_update = _list.update
170 # Expose some sorted list methods publicly.
172 self.bisect_left = _list.bisect_left
173 self.bisect = _list.bisect_right
174 self.bisect_right = _list.bisect_right
175 self.index = _list.index
176 self.irange = _list.irange
177 self.islice = _list.islice
178 self._reset = _list._reset
180 if _key is not None:
181 self.bisect_key_left = _list.bisect_key_left
182 self.bisect_key_right = _list.bisect_key_right
183 self.bisect_key = _list.bisect_key
184 self.irange_key = _list.irange_key
186 self._update(*args, **kwargs)
189 @property
190 def key(self):
191 """Function used to extract comparison key from keys.
193 Sorted dict compares keys directly when the key function is none.
195 """
196 return self._key
199 @property
200 def iloc(self):
201 """Cached reference of sorted keys view.
203 Deprecated in version 2 of Sorted Containers. Use
204 :func:`SortedDict.keys` instead.
206 """
207 # pylint: disable=attribute-defined-outside-init
208 try:
209 return self._iloc
210 except AttributeError:
211 warnings.warn(
212 'sorted_dict.iloc is deprecated.'
213 ' Use SortedDict.keys() instead.',
214 DeprecationWarning,
215 stacklevel=2,
216 )
217 _iloc = self._iloc = SortedKeysView(self)
218 return _iloc
221 def clear(self):
223 """Remove all items from sorted dict.
225 Runtime complexity: `O(n)`
227 """
228 dict.clear(self)
229 self._list_clear()
232 def __delitem__(self, key):
233 """Remove item from sorted dict identified by `key`.
235 ``sd.__delitem__(key)`` <==> ``del sd[key]``
237 Runtime complexity: `O(log(n))` -- approximate.
239 >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
240 >>> del sd['b']
241 >>> sd
242 SortedDict({'a': 1, 'c': 3})
243 >>> del sd['z']
244 Traceback (most recent call last):
245 ...
246 KeyError: 'z'
248 :param key: `key` for item lookup
249 :raises KeyError: if key not found
251 """
252 dict.__delitem__(self, key)
253 self._list_remove(key)
256 def __iter__(self):
257 """Return an iterator over the keys of the sorted dict.
259 ``sd.__iter__()`` <==> ``iter(sd)``
261 Iterating the sorted dict while adding or deleting items may raise a
262 :exc:`RuntimeError` or fail to iterate over all keys.
264 """
265 return self._list_iter()
268 def __reversed__(self):
269 """Return a reverse iterator over the keys of the sorted dict.
271 ``sd.__reversed__()`` <==> ``reversed(sd)``
273 Iterating the sorted dict while adding or deleting items may raise a
274 :exc:`RuntimeError` or fail to iterate over all keys.
276 """
277 return self._list_reversed()
280 def __setitem__(self, key, value):
281 """Store item in sorted dict with `key` and corresponding `value`.
283 ``sd.__setitem__(key, value)`` <==> ``sd[key] = value``
285 Runtime complexity: `O(log(n))` -- approximate.
287 >>> sd = SortedDict()
288 >>> sd['c'] = 3
289 >>> sd['a'] = 1
290 >>> sd['b'] = 2
291 >>> sd
292 SortedDict({'a': 1, 'b': 2, 'c': 3})
294 :param key: key for item
295 :param value: value for item
297 """
298 if key not in self:
299 self._list_add(key)
300 dict.__setitem__(self, key, value)
302 _setitem = __setitem__
305 def __or__(self, other):
306 if not isinstance(other, Mapping):
307 return NotImplemented
308 items = chain(self.items(), other.items())
309 return self.__class__(self._key, items)
312 def __ror__(self, other):
313 if not isinstance(other, Mapping):
314 return NotImplemented
315 items = chain(other.items(), self.items())
316 return self.__class__(self._key, items)
319 def __ior__(self, other):
320 self._update(other)
321 return self
324 def copy(self):
325 """Return a shallow copy of the sorted dict.
327 Runtime complexity: `O(n)`
329 :return: new sorted dict
331 """
332 return self.__class__(self._key, self.items())
334 __copy__ = copy
337 @classmethod
338 def fromkeys(cls, iterable, value=None):
339 """Return a new sorted dict initailized from `iterable` and `value`.
341 Items in the sorted dict have keys from `iterable` and values equal to
342 `value`.
344 Runtime complexity: `O(n*log(n))`
346 :return: new sorted dict
348 """
349 return cls((key, value) for key in iterable)
352 def keys(self):
353 """Return new sorted keys view of the sorted dict's keys.
355 See :class:`SortedKeysView` for details.
357 :return: new sorted keys view
359 """
360 return SortedKeysView(self)
363 def items(self):
364 """Return new sorted items view of the sorted dict's items.
366 See :class:`SortedItemsView` for details.
368 :return: new sorted items view
370 """
371 return SortedItemsView(self)
374 def values(self):
375 """Return new sorted values view of the sorted dict's values.
377 See :class:`SortedValuesView` for details.
379 :return: new sorted values view
381 """
382 return SortedValuesView(self)
385 if sys.hexversion < 0x03000000:
386 def __make_raise_attributeerror(original, alternate):
387 # pylint: disable=no-self-argument
388 message = (
389 'SortedDict.{original}() is not implemented.'
390 ' Use SortedDict.{alternate}() instead.'
391 ).format(original=original, alternate=alternate)
392 def method(self):
393 # pylint: disable=missing-docstring,unused-argument
394 raise AttributeError(message)
395 method.__name__ = original # pylint: disable=non-str-assignment-to-dunder-name
396 method.__doc__ = message
397 return property(method)
399 iteritems = __make_raise_attributeerror('iteritems', 'items')
400 iterkeys = __make_raise_attributeerror('iterkeys', 'keys')
401 itervalues = __make_raise_attributeerror('itervalues', 'values')
402 viewitems = __make_raise_attributeerror('viewitems', 'items')
403 viewkeys = __make_raise_attributeerror('viewkeys', 'keys')
404 viewvalues = __make_raise_attributeerror('viewvalues', 'values')
407 class _NotGiven(object):
408 # pylint: disable=too-few-public-methods
409 def __repr__(self):
410 return '<not-given>'
412 __not_given = _NotGiven()
414 def pop(self, key, default=__not_given):
415 """Remove and return value for item identified by `key`.
417 If the `key` is not found then return `default` if given. If `default`
418 is not given then raise :exc:`KeyError`.
420 Runtime complexity: `O(log(n))` -- approximate.
422 >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
423 >>> sd.pop('c')
424 3
425 >>> sd.pop('z', 26)
426 26
427 >>> sd.pop('y')
428 Traceback (most recent call last):
429 ...
430 KeyError: 'y'
432 :param key: `key` for item
433 :param default: `default` value if key not found (optional)
434 :return: value for item
435 :raises KeyError: if `key` not found and `default` not given
437 """
438 if key in self:
439 self._list_remove(key)
440 return dict.pop(self, key)
441 else:
442 if default is self.__not_given:
443 raise KeyError(key)
444 return default
447 def popitem(self, index=-1):
448 """Remove and return ``(key, value)`` pair at `index` from sorted dict.
450 Optional argument `index` defaults to -1, the last item in the sorted
451 dict. Specify ``index=0`` for the first item in the sorted dict.
453 If the sorted dict is empty, raises :exc:`KeyError`.
455 If the `index` is out of range, raises :exc:`IndexError`.
457 Runtime complexity: `O(log(n))`
459 >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
460 >>> sd.popitem()
461 ('c', 3)
462 >>> sd.popitem(0)
463 ('a', 1)
464 >>> sd.popitem(100)
465 Traceback (most recent call last):
466 ...
467 IndexError: list index out of range
469 :param int index: `index` of item (default -1)
470 :return: key and value pair
471 :raises KeyError: if sorted dict is empty
472 :raises IndexError: if `index` out of range
474 """
475 if not self:
476 raise KeyError('popitem(): dictionary is empty')
478 key = self._list_pop(index)
479 value = dict.pop(self, key)
480 return (key, value)
483 def peekitem(self, index=-1):
484 """Return ``(key, value)`` pair at `index` in sorted dict.
486 Optional argument `index` defaults to -1, the last item in the sorted
487 dict. Specify ``index=0`` for the first item in the sorted dict.
489 Unlike :func:`SortedDict.popitem`, the sorted dict is not modified.
491 If the `index` is out of range, raises :exc:`IndexError`.
493 Runtime complexity: `O(log(n))`
495 >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
496 >>> sd.peekitem()
497 ('c', 3)
498 >>> sd.peekitem(0)
499 ('a', 1)
500 >>> sd.peekitem(100)
501 Traceback (most recent call last):
502 ...
503 IndexError: list index out of range
505 :param int index: index of item (default -1)
506 :return: key and value pair
507 :raises IndexError: if `index` out of range
509 """
510 key = self._list[index]
511 return key, self[key]
514 def setdefault(self, key, default=None):
515 """Return value for item identified by `key` in sorted dict.
517 If `key` is in the sorted dict then return its value. If `key` is not
518 in the sorted dict then insert `key` with value `default` and return
519 `default`.
521 Optional argument `default` defaults to none.
523 Runtime complexity: `O(log(n))` -- approximate.
525 >>> sd = SortedDict()
526 >>> sd.setdefault('a', 1)
527 1
528 >>> sd.setdefault('a', 10)
529 1
530 >>> sd
531 SortedDict({'a': 1})
533 :param key: key for item
534 :param default: value for item (default None)
535 :return: value for item identified by `key`
537 """
538 if key in self:
539 return self[key]
540 dict.__setitem__(self, key, default)
541 self._list_add(key)
542 return default
545 def update(self, *args, **kwargs):
546 """Update sorted dict with items from `args` and `kwargs`.
548 Overwrites existing items.
550 Optional arguments `args` and `kwargs` may be a mapping, an iterable of
551 pairs or keyword arguments. See :func:`SortedDict.__init__` for
552 details.
554 :param args: mapping or iterable of pairs
555 :param kwargs: keyword arguments mapping
557 """
558 if not self:
559 dict.update(self, *args, **kwargs)
560 self._list_update(dict.__iter__(self))
561 return
563 if not kwargs and len(args) == 1 and isinstance(args[0], dict):
564 pairs = args[0]
565 else:
566 pairs = dict(*args, **kwargs)
568 if (10 * len(pairs)) > len(self):
569 dict.update(self, pairs)
570 self._list_clear()
571 self._list_update(dict.__iter__(self))
572 else:
573 for key in pairs:
574 self._setitem(key, pairs[key])
576 _update = update
579 def __reduce__(self):
580 """Support for pickle.
582 The tricks played with caching references in
583 :func:`SortedDict.__init__` confuse pickle so customize the reducer.
585 """
586 items = dict.copy(self)
587 return (type(self), (self._key, items))
590 @recursive_repr()
591 def __repr__(self):
592 """Return string representation of sorted dict.
594 ``sd.__repr__()`` <==> ``repr(sd)``
596 :return: string representation
598 """
599 _key = self._key
600 type_name = type(self).__name__
601 key_arg = '' if _key is None else '{0!r}, '.format(_key)
602 item_format = '{0!r}: {1!r}'.format
603 items = ', '.join(item_format(key, self[key]) for key in self._list)
604 return '{0}({1}{{{2}}})'.format(type_name, key_arg, items)
607 def _check(self):
608 """Check invariants of sorted dict.
610 Runtime complexity: `O(n)`
612 """
613 _list = self._list
614 _list._check()
615 assert len(self) == len(_list)
616 assert all(key in self for key in _list)
619def _view_delitem(self, index):
620 """Remove item at `index` from sorted dict.
622 ``view.__delitem__(index)`` <==> ``del view[index]``
624 Supports slicing.
626 Runtime complexity: `O(log(n))` -- approximate.
628 >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
629 >>> view = sd.keys()
630 >>> del view[0]
631 >>> sd
632 SortedDict({'b': 2, 'c': 3})
633 >>> del view[-1]
634 >>> sd
635 SortedDict({'b': 2})
636 >>> del view[:]
637 >>> sd
638 SortedDict({})
640 :param index: integer or slice for indexing
641 :raises IndexError: if index out of range
643 """
644 _mapping = self._mapping
645 _list = _mapping._list
646 dict_delitem = dict.__delitem__
647 if isinstance(index, slice):
648 keys = _list[index]
649 del _list[index]
650 for key in keys:
651 dict_delitem(_mapping, key)
652 else:
653 key = _list.pop(index)
654 dict_delitem(_mapping, key)
657class SortedKeysView(KeysView, Sequence):
658 """Sorted keys view is a dynamic view of the sorted dict's keys.
660 When the sorted dict's keys change, the view reflects those changes.
662 The keys view implements the set and sequence abstract base classes.
664 """
665 __slots__ = ()
668 @classmethod
669 def _from_iterable(cls, it):
670 return SortedSet(it)
673 def __getitem__(self, index):
674 """Lookup key at `index` in sorted keys views.
676 ``skv.__getitem__(index)`` <==> ``skv[index]``
678 Supports slicing.
680 Runtime complexity: `O(log(n))` -- approximate.
682 >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
683 >>> skv = sd.keys()
684 >>> skv[0]
685 'a'
686 >>> skv[-1]
687 'c'
688 >>> skv[:]
689 ['a', 'b', 'c']
690 >>> skv[100]
691 Traceback (most recent call last):
692 ...
693 IndexError: list index out of range
695 :param index: integer or slice for indexing
696 :return: key or list of keys
697 :raises IndexError: if index out of range
699 """
700 return self._mapping._list[index]
703 __delitem__ = _view_delitem
706class SortedItemsView(ItemsView, Sequence):
707 """Sorted items view is a dynamic view of the sorted dict's items.
709 When the sorted dict's items change, the view reflects those changes.
711 The items view implements the set and sequence abstract base classes.
713 """
714 __slots__ = ()
717 @classmethod
718 def _from_iterable(cls, it):
719 return SortedSet(it)
722 def __getitem__(self, index):
723 """Lookup item at `index` in sorted items view.
725 ``siv.__getitem__(index)`` <==> ``siv[index]``
727 Supports slicing.
729 Runtime complexity: `O(log(n))` -- approximate.
731 >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
732 >>> siv = sd.items()
733 >>> siv[0]
734 ('a', 1)
735 >>> siv[-1]
736 ('c', 3)
737 >>> siv[:]
738 [('a', 1), ('b', 2), ('c', 3)]
739 >>> siv[100]
740 Traceback (most recent call last):
741 ...
742 IndexError: list index out of range
744 :param index: integer or slice for indexing
745 :return: item or list of items
746 :raises IndexError: if index out of range
748 """
749 _mapping = self._mapping
750 _mapping_list = _mapping._list
752 if isinstance(index, slice):
753 keys = _mapping_list[index]
754 return [(key, _mapping[key]) for key in keys]
756 key = _mapping_list[index]
757 return key, _mapping[key]
760 __delitem__ = _view_delitem
763class SortedValuesView(ValuesView, Sequence):
764 """Sorted values view is a dynamic view of the sorted dict's values.
766 When the sorted dict's values change, the view reflects those changes.
768 The values view implements the sequence abstract base class.
770 """
771 __slots__ = ()
774 def __getitem__(self, index):
775 """Lookup value at `index` in sorted values view.
777 ``siv.__getitem__(index)`` <==> ``siv[index]``
779 Supports slicing.
781 Runtime complexity: `O(log(n))` -- approximate.
783 >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
784 >>> svv = sd.values()
785 >>> svv[0]
786 1
787 >>> svv[-1]
788 3
789 >>> svv[:]
790 [1, 2, 3]
791 >>> svv[100]
792 Traceback (most recent call last):
793 ...
794 IndexError: list index out of range
796 :param index: integer or slice for indexing
797 :return: value or list of values
798 :raises IndexError: if index out of range
800 """
801 _mapping = self._mapping
802 _mapping_list = _mapping._list
804 if isinstance(index, slice):
805 keys = _mapping_list[index]
806 return [_mapping[key] for key in keys]
808 key = _mapping_list[index]
809 return _mapping[key]
812 __delitem__ = _view_delitem