# Source code for sortedcollections.recipes

    """Sorted collections recipes implementations.

    """

    from collections import abc
    from copy import deepcopy
    from itertools import count

    from sortedcontainers import SortedDict, SortedKeyList, SortedSet
    from sortedcontainers.sortedlist import recursive_repr

    class IndexableDict(SortedDict):
        """Dictionary that supports numerical indexing.

        Keys are numerically indexable using dict views. For example::

            >>> indexable_dict = IndexableDict.fromkeys('abcde')
            >>> keys = indexable_dict.keys()
            >>> sorted(keys[:]) == ['a', 'b', 'c', 'd', 'e']
            True

        The dict views support the sequence abstract base class.

        """

        def __init__(self, *args, **kwargs):
            super().__init__(hash, *args, **kwargs)

    class IndexableSet(SortedSet):
        """Set that supports numerical indexing.

        Values are numerically indexable. For example::

            >>> indexable_set = IndexableSet('abcde')
            >>> sorted(indexable_set[:]) == ['a', 'b', 'c', 'd', 'e']
            True

        `IndexableSet` implements the sequence abstract base class.

        """

        # pylint: disable=too-many-ancestors

        def __init__(self, *args, **kwargs):
            super().__init__(*args, key=hash, **kwargs)

        def __reduce__(self):
            return self.__class__, (set(self),)

    class ItemSortedDict(SortedDict):
        """Sorted dictionary with key-function support for item pairs.

        Requires key function callable specified as the first argument. The
        callable must accept two arguments, key and value, and return a value used
        to determine the sort order. For example::

            def multiply(key, value):
                return key * value
            mapping = ItemSortedDict(multiply, [(3, 2), (4, 1), (2, 5)])
            list(mapping) == [4, 3, 2]

        Above, the key/value item pairs are ordered by ``key * value`` according to
        the callable given as the first argument.

        """

        def __init__(self, *args, **kwargs):
            assert args and callable(args[0])
            args = list(args)
            func = self._func = args[0]

            def key_func(key):
                "Apply key function to (key, value) item pair."
                return func(key, self[key])

            args[0] = key_func
            super().__init__(*args, **kwargs)

        def __delitem__(self, key):
            "``del mapping[key]``"
            if key not in self:
                raise KeyError(key)
            self._list_remove(key)
            dict.__delitem__(self, key)

        def __setitem__(self, key, value):
            "``mapping[key] = value``"
            if key in self:
                self._list_remove(key)
                dict.__delitem__(self, key)
            dict.__setitem__(self, key, value)
            self._list_add(key)

        _setitem = __setitem__

        def copy(self):
            "Return shallow copy of the mapping."
            return self.__class__(self._func, iter(self.items()))

        __copy__ = copy

        def __deepcopy__(self, memo):
            items = (deepcopy(item, memo) for item in self.items())
            return self.__class__(self._func, items)

    class ValueSortedDict(SortedDict):
        """Sorted dictionary that maintains (key, value) item pairs sorted by value.

        - ``ValueSortedDict()`` -> new empty dictionary.

        - ``ValueSortedDict(mapping)`` -> new dictionary initialized from a mapping
          object's (key, value) pairs.

        - ``ValueSortedDict(iterable)`` -> new dictionary initialized as if via::

            d = ValueSortedDict()
            for k, v in iterable:
                d[k] = v

        - ``ValueSortedDict(**kwargs)`` -> new dictionary initialized with the
          name=value pairs in the keyword argument list.  For example::

            ValueSortedDict(one=1, two=2)

        An optional key function callable may be specified as the first
        argument. When so, the callable will be applied to the value of each item
        pair to determine the comparable for sort order as with Python's builtin
        ``sorted`` function.

        """

        def __init__(self, *args, **kwargs):
            args = list(args)
            if args and callable(args[0]):
                func = self._func = args[0]

                def key_func(key):
                    "Apply key function to ``mapping[value]``."
                    return func(self[key])

                args[0] = key_func
            else:
                self._func = None

                def key_func(key):
                    "Return mapping value for key."
                    return self[key]

                if args and args[0] is None:
                    args[0] = key_func
                else:
                    args.insert(0, key_func)
            super().__init__(*args, **kwargs)

        def __delitem__(self, key):
            "``del mapping[key]``"
            if key not in self:
                raise KeyError(key)
            self._list_remove(key)
            dict.__delitem__(self, key)

        def __setitem__(self, key, value):
            "``mapping[key] = value``"
            if key in self:
                self._list_remove(key)
                dict.__delitem__(self, key)
            dict.__setitem__(self, key, value)
            self._list_add(key)

        _setitem = __setitem__

        def copy(self):
            "Return shallow copy of the mapping."
            return self.__class__(self._func, iter(self.items()))

        __copy__ = copy

        def __reduce__(self):
            items = [(key, self[key]) for key in self._list]
            args = (self._func, items)
            return (self.__class__, args)

        @recursive_repr()
        def __repr__(self):
            items = ', '.join(f'{key!r}: {self[key]!r}' for key in self._list)
            return f'{self.__class__.__name__}({self._func!r}, {{{items}}})'

    class OrderedSet(abc.MutableSet, abc.Sequence):
        """Like OrderedDict, OrderedSet maintains the insertion order of elements.

        For example::

            >>> ordered_set = OrderedSet('abcde')
            >>> list(ordered_set) == list('abcde')
            True
            >>> ordered_set = OrderedSet('edcba')
            >>> list(ordered_set) == list('edcba')
            True

        OrderedSet also implements the collections.Sequence interface.

        """

        # pylint: disable=too-many-ancestors

        def __init__(self, iterable=()):
            # pylint: disable=super-init-not-called
            self._keys = {}
            self._nums = SortedDict()
            self._keys_view = self._nums.keys()
            self._count = count()
            self |= iterable

        def __contains__(self, key):
            "``key in ordered_set``"
            return key in self._keys

        count = __contains__

        def __iter__(self):
            "``iter(ordered_set)``"
            return iter(self._nums.values())

        def __reversed__(self):
            "``reversed(ordered_set)``"
            _nums = self._nums
            for key in reversed(_nums):
                yield _nums[key]

        def __getitem__(self, index):
            "``ordered_set[index]`` -> element; lookup element at index."
            num = self._keys_view[index]
            return self._nums[num]

        def __len__(self):
            "``len(ordered_set)``"
            return len(self._keys)

        def index(self, value):
            "Return index of value."
            # pylint: disable=arguments-differ
            try:
                return self._keys[value]
            except KeyError:
                raise ValueError(f'{value!r} is not in {type(self).__name__}')

        def add(self, value):
            "Add element, value, to set."
            if value not in self._keys:
                num = next(self._count)
                self._keys[value] = num
                self._nums[num] = value

        def discard(self, value):
            "Remove element, value, from set if it is a member."
            num = self._keys.pop(value, None)
            if num is not None:
                del self._nums[num]

        def __repr__(self):
            "Text representation of set."
            return f'{type(self).__name__}({list(self)!r})'

        __str__ = __repr__

    class SegmentList(SortedKeyList):
        """List that supports fast random insertion and deletion of elements.

        SegmentList is a special case of a SortedList initialized with a key
        function that always returns 0. As such, several SortedList methods are not
        implemented for SegmentList.

        """

        # pylint: disable=too-many-ancestors

        def __init__(self, iterable=()):
            super().__init__(iterable, self.zero)

        @staticmethod
        def zero(_):
            "Return 0."
            return 0

        def __setitem__(self, index, value):
            if isinstance(index, slice):
                raise NotImplementedError
            pos, idx = self._pos(index)
            self._lists[pos][idx] = value

        def append(self, value):
            if self._len:
                pos = len(self._lists) - 1
                self._lists[pos].append(value)
                self._keys[pos].append(0)
                self._expand(pos)
            else:
                self._lists.append([value])
                self._keys.append([0])
                self._maxes.append(0)
            self._len += 1

        def extend(self, values):
            for value in values:
                self.append(value)

        def insert(self, index, value):
            if index == self._len:
                self.append(value)
                return
            pos, idx = self._pos(index)
            self._lists[pos].insert(idx, value)
            self._keys[pos].insert(idx, 0)
            self._expand(pos)
            self._len += 1

        def reverse(self):
            values = list(self)
            values.reverse()
            self.clear()
            self.extend(values)

        def sort(self, key=None, reverse=False):
            "Stable sort in place."
            values = sorted(self, key=key, reverse=reverse)
            self.clear()
            self.extend(values)

        def _not_implemented(self, *args, **kwargs):
            "Not implemented."
            raise NotImplementedError

        add = _not_implemented
        bisect = _not_implemented
        bisect_left = _not_implemented
        bisect_right = _not_implemented
        bisect_key = _not_implemented
        bisect_key_left = _not_implemented
        bisect_key_right = _not_implemented
        irange = _not_implemented
        irange_key = _not_implemented
        update = _not_implemented