sorted dict doc sorted containersindex is an apache2 licensed python sorted collections library written in purepython and fast as cextensions the doc introductionintroduction is the best way to get started sorted dict implementations currentmodule sortedcontainers class sorteddict class sortedkeysview class sorteditemsview class sortedvaluesview begin python 23 shims end python 23 shims sorted dict is a sorted mutable mapping sorted dict keys are maintained in sorted order the design of sorted dict is simple sorted dict inherits from dict to store items and maintains a sorted list of keys sorted dict keys must be hashable and comparable the hash and total ordering of keys must not change while they are stored in the sorted dict mutable mapping methods func sorteddict getitem inherited from dict func sorteddict setitem func sorteddict delitem func sorteddict iter func sorteddict len inherited from dict methods for adding items func sorteddict setdefault func sorteddict update methods for removing items func sorteddict clear func sorteddict pop func sorteddict popitem methods for looking up items func sorteddict contains inherited from dict func sorteddict get inherited from dict func sorteddict peekitem methods for views func sorteddict keys func sorteddict items func sorteddict values methods for miscellany func sorteddict copy func sorteddict fromkeys func sorteddict reversed func sorteddict eq inherited from dict func sorteddict ne inherited from dict func sorteddict repr func sorteddict check sorted list methods available applies to keys func sortedlist bisectleft func sortedlist bisectright func sortedlist count func sortedlist index func sortedlist irange func sortedlist islice func sortedlist reset additional sorted list methods available if keyfunction used func sortedkeylist bisectkeyleft func sortedkeylist bisectkeyright func sortedkeylist irangekey sorted dicts may only be compared for equality and inequality initialize sorted dict instance optional keyfunction argument defines a callable that like the key argument to the builtin sorted function extracts a comparison key from each dictionary key if no function is specified the default compares the dictionary keys directly the keyfunction argument must be provided as a positional argument and must come before all other arguments optional iterable argument provides an initial sequence of pairs to initialize the sorted dict each pair in the sequence defines the key and corresponding value if a key is seen more than once the last value associated with it is stored in the new sorted dict optional mapping argument provides an initial mapping of items to initialize the sorted dict if keyword arguments are given the keywords themselves with their associated values are added as items to the dictionary if a key is specified both in the positional argument and as a keyword argument the value associated with the keyword is stored in the sorted dict sorted dict keys must be hashable per the requirement for python s dictionaries keys or the result of the keyfunction must also be comparable per the requirement for sorted lists d alpha 1 beta 2 sorteddict alpha 1 beta 2 d true sorteddict alpha 1 beta 2 d true sorteddictalpha1 beta2 d true reaching through self list repeatedly adds unnecessary overhead so cache references to sorted list methods expose some sorted list methods publicly function used to extract comparison key from keys sorted dict compares keys directly when the key function is none cached reference of sorted keys view deprecated in version 2 of sorted containers use func sorteddict keys instead pylint disableattributedefinedoutsideinit remove all items from sorted dict runtime complexity on remove item from sorted dict identified by key sd delitemkey del sdkey runtime complexity ologn approximate sd sorteddict a 1 b 2 c 3 del sd b sd sorteddict a 1 c 3 del sd z traceback most recent call last keyerror z param key key for item lookup raises keyerror if key not found return an iterator over the keys of the sorted dict sd iter itersd iterating the sorted dict while adding or deleting items may raise a exc runtimeerror or fail to iterate over all keys return a reverse iterator over the keys of the sorted dict sd reversed reversedsd iterating the sorted dict while adding or deleting items may raise a exc runtimeerror or fail to iterate over all keys store item in sorted dict with key and corresponding value sd setitemkey value sdkey value runtime complexity ologn approximate sd sorteddict sd c 3 sd a 1 sd b 2 sd sorteddict a 1 b 2 c 3 param key key for item param value value for item return a shallow copy of the sorted dict runtime complexity on return new sorted dict return a new sorted dict initailized from iterable and value items in the sorted dict have keys from iterable and values equal to value runtime complexity onlogn return new sorted dict return new sorted keys view of the sorted dict s keys see class sortedkeysview for details return new sorted keys view return new sorted items view of the sorted dict s items see class sorteditemsview for details return new sorted items view return new sorted values view of the sorted dict s values note that the values view is sorted by key see class sortedvaluesview for details return new sorted values view pylint disablenoselfargument pylint disablemissingdocstring unusedargument pylint disabletoofewpublicmethods remove and return value for item identified by key if the key is not found then return default if given if default is not given then raise exc keyerror runtime complexity ologn approximate sd sorteddict a 1 b 2 c 3 sd pop c 3 sd pop z 26 26 sd pop y traceback most recent call last keyerror y param key key for item param default default value if key not found optional return value for item raises keyerror if key not found and default not given remove and return key value pair at index from sorted dict optional argument index defaults to 1 the last item in the sorted dict specify index0 for the first item in the sorted dict if the sorted dict is empty raises exc keyerror if the index is out of range raises exc indexerror runtime complexity ologn sd sorteddict a 1 b 2 c 3 sd popitem c 3 sd popitem0 a 1 sd popitem100 traceback most recent call last indexerror list index out of range param int index index of item default 1 return key and value pair raises keyerror if sorted dict is empty raises indexerror if index out of range return key value pair at index in sorted dict optional argument index defaults to 1 the last item in the sorted dict specify index0 for the first item in the sorted dict unlike func sorteddict popitem the sorted dict is not modified if the index is out of range raises exc indexerror runtime complexity ologn sd sorteddict a 1 b 2 c 3 sd peekitem c 3 sd peekitem0 a 1 sd peekitem100 traceback most recent call last indexerror list index out of range param int index index of item default 1 return key and value pair raises indexerror if index out of range return value for item identified by key in sorted dict if key is in the sorted dict then return its value if key is not in the sorted dict then insert key with value default and return default optional argument default defaults to none runtime complexity ologn approximate sd sorteddict sd setdefault a 1 1 sd setdefault a 10 1 sd sorteddict a 1 param key key for item param default value for item default none return value for item identified by key update sorted dict with items from args and kwargs overwrites existing items optional arguments args and kwargs may be a mapping an iterable of pairs or keyword arguments see func sorteddict init for details param args mapping or iterable of pairs param kwargs keyword arguments mapping support for pickle the tricks played with caching references in func sorteddict init confuse pickle so customize the reducer return string representation of sorted dict sd repr reprsd return string representation check invariants of sorted dict runtime complexity on remove item at index from sorted dict view delitemindex del viewindex supports slicing runtime complexity ologn approximate sd sorteddict a 1 b 2 c 3 view sd keys del view0 sd sorteddict b 2 c 3 del view1 sd sorteddict b 2 del view sd sorteddict param index integer or slice for indexing raises indexerror if index out of range sorted keys view is a dynamic view of the sorted dict s keys when the sorted dict s keys change the view reflects those changes the keys view implements the set and sequence abstract base classes lookup key at index in sorted keys views skv getitemindex skvindex supports slicing runtime complexity ologn approximate sd sorteddict a 1 b 2 c 3 skv sd keys skv0 a skv1 c skv a b c skv100 traceback most recent call last indexerror list index out of range param index integer or slice for indexing return key or list of keys raises indexerror if index out of range sorted items view is a dynamic view of the sorted dict s items when the sorted dict s items change the view reflects those changes the items view implements the set and sequence abstract base classes lookup item at index in sorted items view siv getitemindex sivindex supports slicing runtime complexity ologn approximate sd sorteddict a 1 b 2 c 3 siv sd items siv0 a 1 siv1 c 3 siv a 1 b 2 c 3 siv100 traceback most recent call last indexerror list index out of range param index integer or slice for indexing return item or list of items raises indexerror if index out of range sorted values view is a dynamic view of the sorted dict s values when the sorted dict s values change the view reflects those changes the values view implements the sequence abstract base class lookup value at index in sorted values view siv getitemindex sivindex supports slicing runtime complexity ologn approximate sd sorteddict a 2 b 1 c 3 svv sd values svv0 2 svv1 3 svv 2 1 3 svv100 traceback most recent call last indexerror list index out of range param index integer or slice for indexing return value or list of values raises indexerror if index out of range begin python 2 3 shims end python 2 3 shims sorted dict is a sorted mutable mapping sorted dict keys are maintained in sorted order the design of sorted dict is simple sorted dict inherits from dict to store items and maintains a sorted list of keys sorted dict keys must be hashable and comparable the hash and total ordering of keys must not change while they are stored in the sorted dict mutable mapping methods func sorteddict __getitem__ inherited from dict func sorteddict __setitem__ func sorteddict __delitem__ func sorteddict __iter__ func sorteddict __len__ inherited from dict methods for adding items func sorteddict setdefault func sorteddict update methods for removing items func sorteddict clear func sorteddict pop func sorteddict popitem methods for looking up items func sorteddict __contains__ inherited from dict func sorteddict get inherited from dict func sorteddict peekitem methods for views func sorteddict keys func sorteddict items func sorteddict values methods for miscellany func sorteddict copy func sorteddict fromkeys func sorteddict __reversed__ func sorteddict __eq__ inherited from dict func sorteddict __ne__ inherited from dict func sorteddict __repr__ func sorteddict _check sorted list methods available applies to keys func sortedlist bisect_left func sortedlist bisect_right func sortedlist count func sortedlist index func sortedlist irange func sortedlist islice func sortedlist _reset additional sorted list methods available if key function used func sortedkeylist bisect_key_left func sortedkeylist bisect_key_right func sortedkeylist irange_key sorted dicts may only be compared for equality and inequality initialize sorted dict instance optional key function argument defines a callable that like the key argument to the built in sorted function extracts a comparison key from each dictionary key if no function is specified the default compares the dictionary keys directly the key function argument must be provided as a positional argument and must come before all other arguments optional iterable argument provides an initial sequence of pairs to initialize the sorted dict each pair in the sequence defines the key and corresponding value if a key is seen more than once the last value associated with it is stored in the new sorted dict optional mapping argument provides an initial mapping of items to initialize the sorted dict if keyword arguments are given the keywords themselves with their associated values are added as items to the dictionary if a key is specified both in the positional argument and as a keyword argument the value associated with the keyword is stored in the sorted dict sorted dict keys must be hashable per the requirement for python s dictionaries keys or the result of the key function must also be comparable per the requirement for sorted lists d alpha 1 beta 2 sorteddict alpha 1 beta 2 d true sorteddict alpha 1 beta 2 d true sorteddict alpha 1 beta 2 d true reaching through self _list repeatedly adds unnecessary overhead so cache references to sorted list methods expose some sorted list methods publicly function used to extract comparison key from keys sorted dict compares keys directly when the key function is none cached reference of sorted keys view deprecated in version 2 of sorted containers use func sorteddict keys instead pylint disable attribute defined outside init remove all items from sorted dict runtime complexity o n remove item from sorted dict identified by key sd __delitem__ key del sd key runtime complexity o log n approximate sd sorteddict a 1 b 2 c 3 del sd b sd sorteddict a 1 c 3 del sd z traceback most recent call last keyerror z param key key for item lookup raises keyerror if key not found return an iterator over the keys of the sorted dict sd __iter__ iter sd iterating the sorted dict while adding or deleting items may raise a exc runtimeerror or fail to iterate over all keys return a reverse iterator over the keys of the sorted dict sd __reversed__ reversed sd iterating the sorted dict while adding or deleting items may raise a exc runtimeerror or fail to iterate over all keys store item in sorted dict with key and corresponding value sd __setitem__ key value sd key value runtime complexity o log n approximate sd sorteddict sd c 3 sd a 1 sd b 2 sd sorteddict a 1 b 2 c 3 param key key for item param value value for item return a shallow copy of the sorted dict runtime complexity o n return new sorted dict return a new sorted dict initailized from iterable and value items in the sorted dict have keys from iterable and values equal to value runtime complexity o n log n return new sorted dict return new sorted keys view of the sorted dict s keys see class sortedkeysview for details return new sorted keys view return new sorted items view of the sorted dict s items see class sorteditemsview for details return new sorted items view return new sorted values view of the sorted dict s values note that the values view is sorted by key see class sortedvaluesview for details return new sorted values view pylint disable no self argument pylint disable missing docstring unused argument pylint disable non str assignment to dunder name pylint disable too few public methods remove and return value for item identified by key if the key is not found then return default if given if default is not given then raise exc keyerror runtime complexity o log n approximate sd sorteddict a 1 b 2 c 3 sd pop c 3 sd pop z 26 26 sd pop y traceback most recent call last keyerror y param key key for item param default default value if key not found optional return value for item raises keyerror if key not found and default not given remove and return key value pair at index from sorted dict optional argument index defaults to 1 the last item in the sorted dict specify index 0 for the first item in the sorted dict if the sorted dict is empty raises exc keyerror if the index is out of range raises exc indexerror runtime complexity o log n sd sorteddict a 1 b 2 c 3 sd popitem c 3 sd popitem 0 a 1 sd popitem 100 traceback most recent call last indexerror list index out of range param int index index of item default 1 return key and value pair raises keyerror if sorted dict is empty raises indexerror if index out of range return key value pair at index in sorted dict optional argument index defaults to 1 the last item in the sorted dict specify index 0 for the first item in the sorted dict unlike func sorteddict popitem the sorted dict is not modified if the index is out of range raises exc indexerror runtime complexity o log n sd sorteddict a 1 b 2 c 3 sd peekitem c 3 sd peekitem 0 a 1 sd peekitem 100 traceback most recent call last indexerror list index out of range param int index index of item default 1 return key and value pair raises indexerror if index out of range return value for item identified by key in sorted dict if key is in the sorted dict then return its value if key is not in the sorted dict then insert key with value default and return default optional argument default defaults to none runtime complexity o log n approximate sd sorteddict sd setdefault a 1 1 sd setdefault a 10 1 sd sorteddict a 1 param key key for item param default value for item default none return value for item identified by key update sorted dict with items from args and kwargs overwrites existing items optional arguments args and kwargs may be a mapping an iterable of pairs or keyword arguments see func sorteddict __init__ for details param args mapping or iterable of pairs param kwargs keyword arguments mapping support for pickle the tricks played with caching references in func sorteddict __init__ confuse pickle so customize the reducer return string representation of sorted dict sd __repr__ repr sd return string representation check invariants of sorted dict runtime complexity o n remove item at index from sorted dict view __delitem__ index del view index supports slicing runtime complexity o log n approximate sd sorteddict a 1 b 2 c 3 view sd keys del view 0 sd sorteddict b 2 c 3 del view 1 sd sorteddict b 2 del view sd sorteddict param index integer or slice for indexing raises indexerror if index out of range sorted keys view is a dynamic view of the sorted dict s keys when the sorted dict s keys change the view reflects those changes the keys view implements the set and sequence abstract base classes lookup key at index in sorted keys views skv __getitem__ index skv index supports slicing runtime complexity o log n approximate sd sorteddict a 1 b 2 c 3 skv sd keys skv 0 a skv 1 c skv a b c skv 100 traceback most recent call last indexerror list index out of range param index integer or slice for indexing return key or list of keys raises indexerror if index out of range sorted items view is a dynamic view of the sorted dict s items when the sorted dict s items change the view reflects those changes the items view implements the set and sequence abstract base classes lookup item at index in sorted items view siv __getitem__ index siv index supports slicing runtime complexity o log n approximate sd sorteddict a 1 b 2 c 3 siv sd items siv 0 a 1 siv 1 c 3 siv a 1 b 2 c 3 siv 100 traceback most recent call last indexerror list index out of range param index integer or slice for indexing return item or list of items raises indexerror if index out of range sorted values view is a dynamic view of the sorted dict s values when the sorted dict s values change the view reflects those changes the values view implements the sequence abstract base class lookup value at index in sorted values view siv __getitem__ index siv index supports slicing runtime complexity o log n approximate sd sorteddict a 2 b 1 c 3 svv sd values svv 0 2 svv 1 3 svv 2 1 3 svv 100 traceback most recent call last indexerror list index out of range param index integer or slice for indexing return value or list of values raises indexerror if index out of range
import sys
import warnings

from itertools import chain

from .sortedlist import SortedList, recursive_repr
from .sortedset import SortedSet





try:
    from collections.abc import (
        ItemsView, KeysView, Mapping, ValuesView, Sequence
    )
except ImportError:
    from collections import ItemsView, KeysView, Mapping, ValuesView, Sequence






class SortedDict(dict):
    
    def __init__(self, *args, **kwargs):
        
        if args and (args[0] is None or callable(args[0])):
            _key = self._key = args[0]
            args = args[1:]
        else:
            _key = self._key = None

        self._list = SortedList(key=_key)

        
        

        _list = self._list
        self._list_add = _list.add
        self._list_clear = _list.clear
        self._list_iter = _list.__iter__
        self._list_reversed = _list.__reversed__
        self._list_pop = _list.pop
        self._list_remove = _list.remove
        self._list_update = _list.update

        

        self.bisect_left = _list.bisect_left
        self.bisect = _list.bisect_right
        self.bisect_right = _list.bisect_right
        self.index = _list.index
        self.irange = _list.irange
        self.islice = _list.islice
        self._reset = _list._reset

        if _key is not None:
            self.bisect_key_left = _list.bisect_key_left
            self.bisect_key_right = _list.bisect_key_right
            self.bisect_key = _list.bisect_key
            self.irange_key = _list.irange_key

        self._update(*args, **kwargs)


    @property
    def key(self):
        
        return self._key


    @property
    def iloc(self):
        
        
        try:
            return self._iloc
        except AttributeError:
            warnings.warn(
                'sorted_dict.iloc is deprecated.'
                ' Use SortedDict.keys() instead.',
                DeprecationWarning,
                stacklevel=2,
            )
            _iloc = self._iloc = SortedKeysView(self)
            return _iloc


    def clear(self):

        
        dict.clear(self)
        self._list_clear()


    def __delitem__(self, key):
        
        dict.__delitem__(self, key)
        self._list_remove(key)


    def __iter__(self):
        
        return self._list_iter()


    def __reversed__(self):
        
        return self._list_reversed()


    def __setitem__(self, key, value):
        
        if key not in self:
            self._list_add(key)
        dict.__setitem__(self, key, value)

    _setitem = __setitem__


    def __or__(self, other):
        if not isinstance(other, Mapping):
            return NotImplemented
        items = chain(self.items(), other.items())
        return self.__class__(self._key, items)


    def __ror__(self, other):
        if not isinstance(other, Mapping):
            return NotImplemented
        items = chain(other.items(), self.items())
        return self.__class__(self._key, items)


    def __ior__(self, other):
        self._update(other)
        return self


    def copy(self):
        
        return self.__class__(self._key, self.items())

    __copy__ = copy


    @classmethod
    def fromkeys(cls, iterable, value=None):
        
        return cls((key, value) for key in iterable)


    def keys(self):
        
        return SortedKeysView(self)


    def items(self):
        
        return SortedItemsView(self)


    def values(self):
        
        return SortedValuesView(self)


    if sys.hexversion < 0x03000000:
        def __make_raise_attributeerror(original, alternate):
            
            message = (
                'SortedDict.{original}() is not implemented.'
                ' Use SortedDict.{alternate}() instead.'
            ).format(original=original, alternate=alternate)
            def method(self):
                
                raise AttributeError(message)
            method.__name__ = original  
            method.__doc__ = message
            return property(method)

        iteritems = __make_raise_attributeerror('iteritems', 'items')
        iterkeys = __make_raise_attributeerror('iterkeys', 'keys')
        itervalues = __make_raise_attributeerror('itervalues', 'values')
        viewitems = __make_raise_attributeerror('viewitems', 'items')
        viewkeys = __make_raise_attributeerror('viewkeys', 'keys')
        viewvalues = __make_raise_attributeerror('viewvalues', 'values')


    class _NotGiven(object):
        
        def __repr__(self):
            return '<not-given>'

    __not_given = _NotGiven()

    def pop(self, key, default=__not_given):
        
        if key in self:
            self._list_remove(key)
            return dict.pop(self, key)
        else:
            if default is self.__not_given:
                raise KeyError(key)
            return default


    def popitem(self, index=-1):
        
        if not self:
            raise KeyError('popitem(): dictionary is empty')

        key = self._list_pop(index)
        value = dict.pop(self, key)
        return (key, value)


    def peekitem(self, index=-1):
        
        key = self._list[index]
        return key, self[key]


    def setdefault(self, key, default=None):
        
        if key in self:
            return self[key]
        dict.__setitem__(self, key, default)
        self._list_add(key)
        return default


    def update(self, *args, **kwargs):
        
        if not self:
            dict.update(self, *args, **kwargs)
            self._list_update(dict.__iter__(self))
            return

        if not kwargs and len(args) == 1 and isinstance(args[0], dict):
            pairs = args[0]
        else:
            pairs = dict(*args, **kwargs)

        if (10 * len(pairs)) > len(self):
            dict.update(self, pairs)
            self._list_clear()
            self._list_update(dict.__iter__(self))
        else:
            for key in pairs:
                self._setitem(key, pairs[key])

    _update = update


    def __reduce__(self):
        
        items = dict.copy(self)
        return (type(self), (self._key, items))


    @recursive_repr()
    def __repr__(self):
        
        _key = self._key
        type_name = type(self).__name__
        key_arg = '' if _key is None else '{0!r}, '.format(_key)
        item_format = '{0!r}: {1!r}'.format
        items = ', '.join(item_format(key, self[key]) for key in self._list)
        return '{0}({1}{{{2}}})'.format(type_name, key_arg, items)


    def _check(self):
        
        _list = self._list
        _list._check()
        assert len(self) == len(_list)
        assert all(key in self for key in _list)


def _view_delitem(self, index):
    
    _mapping = self._mapping
    _list = _mapping._list
    dict_delitem = dict.__delitem__
    if isinstance(index, slice):
        keys = _list[index]
        del _list[index]
        for key in keys:
            dict_delitem(_mapping, key)
    else:
        key = _list.pop(index)
        dict_delitem(_mapping, key)


class SortedKeysView(KeysView, Sequence):
    
    __slots__ = ()


    @classmethod
    def _from_iterable(cls, it):
        return SortedSet(it)


    def __getitem__(self, index):
        
        return self._mapping._list[index]


    __delitem__ = _view_delitem


class SortedItemsView(ItemsView, Sequence):
    
    __slots__ = ()


    @classmethod
    def _from_iterable(cls, it):
        return SortedSet(it)


    def __getitem__(self, index):
        
        _mapping = self._mapping
        _mapping_list = _mapping._list

        if isinstance(index, slice):
            keys = _mapping_list[index]
            return [(key, _mapping[key]) for key in keys]

        key = _mapping_list[index]
        return key, _mapping[key]


    __delitem__ = _view_delitem


class SortedValuesView(ValuesView, Sequence):
    
    __slots__ = ()


    def __getitem__(self, index):
        
        _mapping = self._mapping
        _mapping_list = _mapping._list

        if isinstance(index, slice):
            keys = _mapping_list[index]
            return [_mapping[key] for key in keys]

        key = _mapping_list[index]
        return _mapping[key]


    __delitem__ = _view_delitem