codekingpro/portable-devtools

1"""Sorted Dict2==============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 dict implementations:9 10.. currentmodule:: sortedcontainers11 12* :class:`SortedDict`13* :class:`SortedKeysView`14* :class:`SortedItemsView`15* :class:`SortedValuesView`16 17"""18 19import sys20import warnings21 22from itertools import chain23 24from .sortedlist import SortedList, recursive_repr25from .sortedset import SortedSet26 27###############################################################################28# BEGIN Python 2/3 Shims29###############################################################################30 31try:32    from collections.abc import (33        ItemsView, KeysView, Mapping, ValuesView, Sequence34    )35except ImportError:36    from collections import ItemsView, KeysView, Mapping, ValuesView, Sequence37 38###############################################################################39# END Python 2/3 Shims40###############################################################################41 42 43class SortedDict(dict):44    """Sorted dict is a sorted mutable mapping.45 46    Sorted dict keys are maintained in sorted order. The design of sorted dict47    is simple: sorted dict inherits from dict to store items and maintains a48    sorted list of keys.49 50    Sorted dict keys must be hashable and comparable. The hash and total51    ordering of keys must not change while they are stored in the sorted dict.52 53    Mutable mapping methods:54 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)60 61    Methods for adding items:62 63    * :func:`SortedDict.setdefault`64    * :func:`SortedDict.update`65 66    Methods for removing items:67 68    * :func:`SortedDict.clear`69    * :func:`SortedDict.pop`70    * :func:`SortedDict.popitem`71 72    Methods for looking up items:73 74    * :func:`SortedDict.__contains__` (inherited from dict)75    * :func:`SortedDict.get` (inherited from dict)76    * :func:`SortedDict.peekitem`77 78    Methods for views:79 80    * :func:`SortedDict.keys`81    * :func:`SortedDict.items`82    * :func:`SortedDict.values`83 84    Methods for miscellany:85 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`93 94    Sorted list methods available (applies to keys):95 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`103 104    Additional sorted list methods available, if key-function used:105 106    * :func:`SortedKeyList.bisect_key_left`107    * :func:`SortedKeyList.bisect_key_right`108    * :func:`SortedKeyList.irange_key`109 110    Sorted dicts may only be compared for equality and inequality.111 112    """113    def __init__(self, *args, **kwargs):114        """Initialize sorted dict instance.115 116        Optional key-function argument defines a callable that, like the `key`117        argument to the built-in `sorted` function, extracts a comparison key118        from each dictionary key. If no function is specified, the default119        compares the dictionary keys directly. The key-function argument must120        be provided as a positional argument and must come before all other121        arguments.122 123        Optional iterable argument provides an initial sequence of pairs to124        initialize the sorted dict. Each pair in the sequence defines the key125        and corresponding value. If a key is seen more than once, the last126        value associated with it is stored in the new sorted dict.127 128        Optional mapping argument provides an initial mapping of items to129        initialize the sorted dict.130 131        If keyword arguments are given, the keywords themselves, with their132        associated values, are added as items to the dictionary. If a key is133        specified both in the positional argument and as a keyword argument,134        the value associated with the keyword is stored in the135        sorted dict.136 137        Sorted dict keys must be hashable, per the requirement for Python's138        dictionaries. Keys (or the result of the key-function) must also be139        comparable, per the requirement for sorted lists.140 141        >>> d = {'alpha': 1, 'beta': 2}142        >>> SortedDict([('alpha', 1), ('beta', 2)]) == d143        True144        >>> SortedDict({'alpha': 1, 'beta': 2}) == d145        True146        >>> SortedDict(alpha=1, beta=2) == d147        True148 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 = None155 156        self._list = SortedList(key=_key)157 158        # Reaching through ``self._list`` repeatedly adds unnecessary overhead159        # so cache references to sorted list methods.160 161        _list = self._list162        self._list_add = _list.add163        self._list_clear = _list.clear164        self._list_iter = _list.__iter__165        self._list_reversed = _list.__reversed__166        self._list_pop = _list.pop167        self._list_remove = _list.remove168        self._list_update = _list.update169 170        # Expose some sorted list methods publicly.171 172        self.bisect_left = _list.bisect_left173        self.bisect = _list.bisect_right174        self.bisect_right = _list.bisect_right175        self.index = _list.index176        self.irange = _list.irange177        self.islice = _list.islice178        self._reset = _list._reset179 180        if _key is not None:181            self.bisect_key_left = _list.bisect_key_left182            self.bisect_key_right = _list.bisect_key_right183            self.bisect_key = _list.bisect_key184            self.irange_key = _list.irange_key185 186        self._update(*args, **kwargs)187 188 189    @property190    def key(self):191        """Function used to extract comparison key from keys.192 193        Sorted dict compares keys directly when the key function is none.194 195        """196        return self._key197 198 199    @property200    def iloc(self):201        """Cached reference of sorted keys view.202 203        Deprecated in version 2 of Sorted Containers. Use204        :func:`SortedDict.keys` instead.205 206        """207        # pylint: disable=attribute-defined-outside-init208        try:209            return self._iloc210        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 _iloc219 220 221    def clear(self):222 223        """Remove all items from sorted dict.224 225        Runtime complexity: `O(n)`226 227        """228        dict.clear(self)229        self._list_clear()230 231 232    def __delitem__(self, key):233        """Remove item from sorted dict identified by `key`.234 235        ``sd.__delitem__(key)`` <==> ``del sd[key]``236 237        Runtime complexity: `O(log(n))` -- approximate.238 239        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})240        >>> del sd['b']241        >>> sd242        SortedDict({'a': 1, 'c': 3})243        >>> del sd['z']244        Traceback (most recent call last):245          ...246        KeyError: 'z'247 248        :param key: `key` for item lookup249        :raises KeyError: if key not found250 251        """252        dict.__delitem__(self, key)253        self._list_remove(key)254 255 256    def __iter__(self):257        """Return an iterator over the keys of the sorted dict.258 259        ``sd.__iter__()`` <==> ``iter(sd)``260 261        Iterating the sorted dict while adding or deleting items may raise a262        :exc:`RuntimeError` or fail to iterate over all keys.263 264        """265        return self._list_iter()266 267 268    def __reversed__(self):269        """Return a reverse iterator over the keys of the sorted dict.270 271        ``sd.__reversed__()`` <==> ``reversed(sd)``272 273        Iterating the sorted dict while adding or deleting items may raise a274        :exc:`RuntimeError` or fail to iterate over all keys.275 276        """277        return self._list_reversed()278 279 280    def __setitem__(self, key, value):281        """Store item in sorted dict with `key` and corresponding `value`.282 283        ``sd.__setitem__(key, value)`` <==> ``sd[key] = value``284 285        Runtime complexity: `O(log(n))` -- approximate.286 287        >>> sd = SortedDict()288        >>> sd['c'] = 3289        >>> sd['a'] = 1290        >>> sd['b'] = 2291        >>> sd292        SortedDict({'a': 1, 'b': 2, 'c': 3})293 294        :param key: key for item295        :param value: value for item296 297        """298        if key not in self:299            self._list_add(key)300        dict.__setitem__(self, key, value)301 302    _setitem = __setitem__303 304 305    def __or__(self, other):306        if not isinstance(other, Mapping):307            return NotImplemented308        items = chain(self.items(), other.items())309        return self.__class__(self._key, items)310 311 312    def __ror__(self, other):313        if not isinstance(other, Mapping):314            return NotImplemented315        items = chain(other.items(), self.items())316        return self.__class__(self._key, items)317 318 319    def __ior__(self, other):320        self._update(other)321        return self322 323 324    def copy(self):325        """Return a shallow copy of the sorted dict.326 327        Runtime complexity: `O(n)`328 329        :return: new sorted dict330 331        """332        return self.__class__(self._key, self.items())333 334    __copy__ = copy335 336 337    @classmethod338    def fromkeys(cls, iterable, value=None):339        """Return a new sorted dict initailized from `iterable` and `value`.340 341        Items in the sorted dict have keys from `iterable` and values equal to342        `value`.343 344        Runtime complexity: `O(n*log(n))`345 346        :return: new sorted dict347 348        """349        return cls((key, value) for key in iterable)350 351 352    def keys(self):353        """Return new sorted keys view of the sorted dict's keys.354 355        See :class:`SortedKeysView` for details.356 357        :return: new sorted keys view358 359        """360        return SortedKeysView(self)361 362 363    def items(self):364        """Return new sorted items view of the sorted dict's items.365 366        See :class:`SortedItemsView` for details.367 368        :return: new sorted items view369 370        """371        return SortedItemsView(self)372 373 374    def values(self):375        """Return new sorted values view of the sorted dict's values.376 377        See :class:`SortedValuesView` for details.378 379        :return: new sorted values view380 381        """382        return SortedValuesView(self)383 384 385    if sys.hexversion < 0x03000000:386        def __make_raise_attributeerror(original, alternate):387            # pylint: disable=no-self-argument388            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-argument394                raise AttributeError(message)395            method.__name__ = original  # pylint: disable=non-str-assignment-to-dunder-name396            method.__doc__ = message397            return property(method)398 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')405 406 407    class _NotGiven(object):408        # pylint: disable=too-few-public-methods409        def __repr__(self):410            return '<not-given>'411 412    __not_given = _NotGiven()413 414    def pop(self, key, default=__not_given):415        """Remove and return value for item identified by `key`.416 417        If the `key` is not found then return `default` if given. If `default`418        is not given then raise :exc:`KeyError`.419 420        Runtime complexity: `O(log(n))` -- approximate.421 422        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})423        >>> sd.pop('c')424        3425        >>> sd.pop('z', 26)426        26427        >>> sd.pop('y')428        Traceback (most recent call last):429          ...430        KeyError: 'y'431 432        :param key: `key` for item433        :param default: `default` value if key not found (optional)434        :return: value for item435        :raises KeyError: if `key` not found and `default` not given436 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 default445 446 447    def popitem(self, index=-1):448        """Remove and return ``(key, value)`` pair at `index` from sorted dict.449 450        Optional argument `index` defaults to -1, the last item in the sorted451        dict. Specify ``index=0`` for the first item in the sorted dict.452 453        If the sorted dict is empty, raises :exc:`KeyError`.454 455        If the `index` is out of range, raises :exc:`IndexError`.456 457        Runtime complexity: `O(log(n))`458 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 range468 469        :param int index: `index` of item (default -1)470        :return: key and value pair471        :raises KeyError: if sorted dict is empty472        :raises IndexError: if `index` out of range473 474        """475        if not self:476            raise KeyError('popitem(): dictionary is empty')477 478        key = self._list_pop(index)479        value = dict.pop(self, key)480        return (key, value)481 482 483    def peekitem(self, index=-1):484        """Return ``(key, value)`` pair at `index` in sorted dict.485 486        Optional argument `index` defaults to -1, the last item in the sorted487        dict. Specify ``index=0`` for the first item in the sorted dict.488 489        Unlike :func:`SortedDict.popitem`, the sorted dict is not modified.490 491        If the `index` is out of range, raises :exc:`IndexError`.492 493        Runtime complexity: `O(log(n))`494 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 range504 505        :param int index: index of item (default -1)506        :return: key and value pair507        :raises IndexError: if `index` out of range508 509        """510        key = self._list[index]511        return key, self[key]512 513 514    def setdefault(self, key, default=None):515        """Return value for item identified by `key` in sorted dict.516 517        If `key` is in the sorted dict then return its value. If `key` is not518        in the sorted dict then insert `key` with value `default` and return519        `default`.520 521        Optional argument `default` defaults to none.522 523        Runtime complexity: `O(log(n))` -- approximate.524 525        >>> sd = SortedDict()526        >>> sd.setdefault('a', 1)527        1528        >>> sd.setdefault('a', 10)529        1530        >>> sd531        SortedDict({'a': 1})532 533        :param key: key for item534        :param default: value for item (default None)535        :return: value for item identified by `key`536 537        """538        if key in self:539            return self[key]540        dict.__setitem__(self, key, default)541        self._list_add(key)542        return default543 544 545    def update(self, *args, **kwargs):546        """Update sorted dict with items from `args` and `kwargs`.547 548        Overwrites existing items.549 550        Optional arguments `args` and `kwargs` may be a mapping, an iterable of551        pairs or keyword arguments. See :func:`SortedDict.__init__` for552        details.553 554        :param args: mapping or iterable of pairs555        :param kwargs: keyword arguments mapping556 557        """558        if not self:559            dict.update(self, *args, **kwargs)560            self._list_update(dict.__iter__(self))561            return562 563        if not kwargs and len(args) == 1 and isinstance(args[0], dict):564            pairs = args[0]565        else:566            pairs = dict(*args, **kwargs)567 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])575 576    _update = update577 578 579    def __reduce__(self):580        """Support for pickle.581 582        The tricks played with caching references in583        :func:`SortedDict.__init__` confuse pickle so customize the reducer.584 585        """586        items = dict.copy(self)587        return (type(self), (self._key, items))588 589 590    @recursive_repr()591    def __repr__(self):592        """Return string representation of sorted dict.593 594        ``sd.__repr__()`` <==> ``repr(sd)``595 596        :return: string representation597 598        """599        _key = self._key600        type_name = type(self).__name__601        key_arg = '' if _key is None else '{0!r}, '.format(_key)602        item_format = '{0!r}: {1!r}'.format603        items = ', '.join(item_format(key, self[key]) for key in self._list)604        return '{0}({1}{{{2}}})'.format(type_name, key_arg, items)605 606 607    def _check(self):608        """Check invariants of sorted dict.609 610        Runtime complexity: `O(n)`611 612        """613        _list = self._list614        _list._check()615        assert len(self) == len(_list)616        assert all(key in self for key in _list)617 618 619def _view_delitem(self, index):620    """Remove item at `index` from sorted dict.621 622    ``view.__delitem__(index)`` <==> ``del view[index]``623 624    Supports slicing.625 626    Runtime complexity: `O(log(n))` -- approximate.627 628    >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})629    >>> view = sd.keys()630    >>> del view[0]631    >>> sd632    SortedDict({'b': 2, 'c': 3})633    >>> del view[-1]634    >>> sd635    SortedDict({'b': 2})636    >>> del view[:]637    >>> sd638    SortedDict({})639 640    :param index: integer or slice for indexing641    :raises IndexError: if index out of range642 643    """644    _mapping = self._mapping645    _list = _mapping._list646    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)655 656 657class SortedKeysView(KeysView, Sequence):658    """Sorted keys view is a dynamic view of the sorted dict's keys.659 660    When the sorted dict's keys change, the view reflects those changes.661 662    The keys view implements the set and sequence abstract base classes.663 664    """665    __slots__ = ()666 667 668    @classmethod669    def _from_iterable(cls, it):670        return SortedSet(it)671 672 673    def __getitem__(self, index):674        """Lookup key at `index` in sorted keys views.675 676        ``skv.__getitem__(index)`` <==> ``skv[index]``677 678        Supports slicing.679 680        Runtime complexity: `O(log(n))` -- approximate.681 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 range694 695        :param index: integer or slice for indexing696        :return: key or list of keys697        :raises IndexError: if index out of range698 699        """700        return self._mapping._list[index]701 702 703    __delitem__ = _view_delitem704 705 706class SortedItemsView(ItemsView, Sequence):707    """Sorted items view is a dynamic view of the sorted dict's items.708 709    When the sorted dict's items change, the view reflects those changes.710 711    The items view implements the set and sequence abstract base classes.712 713    """714    __slots__ = ()715 716 717    @classmethod718    def _from_iterable(cls, it):719        return SortedSet(it)720 721 722    def __getitem__(self, index):723        """Lookup item at `index` in sorted items view.724 725        ``siv.__getitem__(index)`` <==> ``siv[index]``726 727        Supports slicing.728 729        Runtime complexity: `O(log(n))` -- approximate.730 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 range743 744        :param index: integer or slice for indexing745        :return: item or list of items746        :raises IndexError: if index out of range747 748        """749        _mapping = self._mapping750        _mapping_list = _mapping._list751 752        if isinstance(index, slice):753            keys = _mapping_list[index]754            return [(key, _mapping[key]) for key in keys]755 756        key = _mapping_list[index]757        return key, _mapping[key]758 759 760    __delitem__ = _view_delitem761 762 763class SortedValuesView(ValuesView, Sequence):764    """Sorted values view is a dynamic view of the sorted dict's values.765 766    When the sorted dict's values change, the view reflects those changes.767 768    The values view implements the sequence abstract base class.769 770    """771    __slots__ = ()772 773 774    def __getitem__(self, index):775        """Lookup value at `index` in sorted values view.776 777        ``siv.__getitem__(index)`` <==> ``siv[index]``778 779        Supports slicing.780 781        Runtime complexity: `O(log(n))` -- approximate.782 783        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})784        >>> svv = sd.values()785        >>> svv[0]786        1787        >>> svv[-1]788        3789        >>> svv[:]790        [1, 2, 3]791        >>> svv[100]792        Traceback (most recent call last):793          ...794        IndexError: list index out of range795 796        :param index: integer or slice for indexing797        :return: value or list of values798        :raises IndexError: if index out of range799 800        """801        _mapping = self._mapping802        _mapping_list = _mapping._list803 804        if isinstance(index, slice):805            keys = _mapping_list[index]806            return [_mapping[key] for key in keys]807 808        key = _mapping_list[index]809        return _mapping[key]810 811 812    __delitem__ = _view_delitem813