frozendict.py

from bisect import bisect_left
from collections import Mapping
from functools import total_ordering


@total_ordering
class frozendict(Mapping):
    """
    Sorted immutable mapping with hash and total ordering.

    frozendict()         -> new empty frozendict
    frozendict(mapping)  -> initialized from a mapping  (key, value) pairs
    frozendict(iterable) -> initialized from a iterable (key, value) pairs
    frozendict(**kwargs) -> initialized with the name=value
                            pairs in the keyword argument list.

    >>> x = frozendict([('b', 2), ('a', 1)])
    >>> y = frozendict({'a': 1, 'b': 2})
    >>> z = frozendict(a=1, b=3)
    >>> x
    frozendict({'a': 1, 'b': 2})
    >>> x == y and z > x and z != 1
    True
    >>> z > 1
    Traceback (most recent call last):
      ...
    TypeError: unorderable types: frozendict() > int()
    """

    def __init__(self, it=(), **kwargs):
        data      = dict(it, **kwargs)
        data      = sorted(data.items())
        self.data = tuple(map(tuple, zip(*data)))

    def __len__(self):
        return len(self.data)

    def __hash__(self):
        return hash(self.data)

    def __repr__(self):
        s = ', '.join('{}: {}'.format(repr(k), repr(v))
                      for k, v in self.items())
        return 'frozendict({%s})' % s

#   Methods for key-index retrival
    def __getindex__(self, key):
        index = bisect_left(self.data[0], key)
        if index == len(self):
            return None
        if self.data[0][index] != key:
            return None
        return index

    def __contains__(self, key):
        index = self.__getindex__(key)
        return index is not None

    def __getitem__(self, key):
        index = self.__getindex__(key)
        if index is None:
            raise KeyError
        return self.data[1][index]

#   Methods for iteration
    def __iter__(self):
        return iter(self.data[0])

    def values(self):
        return iter(self.data[1])

    def items(self):
        return iter(zip(*self.data))

#   Methods for total ordering
    def __eq__(self, other):
        if isinstance(other, frozendict):
            return self.data == other.data
        return super().__eq__(other)

    def __lt__(self, other):
        if isinstance(other, frozendict):
            return self.data < other.data
        return NotImplemented

if __name__ == '__main__':
    import doctest
    doctest.testmod()