import copy


class DefaultDict(dict):
    """Dictionary with a default value for unknown keys."""

    def __init__(self, default):
        self.default = default

    def __getitem__(self, key):
        if key in self: return self.get(key)
        return self.setdefault(key, copy.deepcopy(self.default))

    def sorted(self, rev=True):
        counts = [(w, c) for w, c in self.items()]
        counts.sort(reverse=rev)
        return counts


class CountingDict(DefaultDict):
    def __init__(self):
        DefaultDict.__init__(self, 0)
