"""A lazily-created dictionary.

It should be equivalent to a dictionary, but uses less memory if most
dictionaries will be empty."""

# A dummy empty dictionary to make some code a bit simpler.
_zerodict = {}

# An object which will be used as a default parameter.
class _singletontype(object):
    __slots__ = []
_singleton = _singletontype()

class lazydict(object):
    __slots__ = [ "__realdict__", "__doc__" ]
        
    def __init__(self, other = None):
        if other is None:
            self.__realdict__ = _zerodict
        elif other is lazydict and other.__realdict__ is _zerodict:
            self.__realdict__ = _zerodict
        else:
            self.__realdict__ = dict(other)

        self.__doc__ = _zerodict.__doc__

    def __repr__(self):
        return self.__realdict__.__repr__()
    
    def __str__(self):
        return self.__realdict__.__str()
    
    def __lt__(self, other):
        return self.__realdict__.__lt__(other)
    
    def __le__(self, other):
        return self.__realdict__.__le__(other)
    
    def __eq__(self, other):
        return self.__realdict__.__eq__(other)
    
    def __ne__(self, other):
        return self.__realdict__.__ne__(other)
    
    def __gt__(self, other):
        return self.__realdict__.__gt__(other)
    
    def __ge__(self, other):
        return self.__realdict__.__ge__(other)
    
    def __cmp__(self, other):
        return self.__realdict__.__cmp__(other)
    
    def __hash__(self):
        return self.__realdict__.__hash__()
    
    def __len__(self):
        return self.__realdict__.__len__()
    
    def __getitem__(self, key):
        return self.__realdict__.__getitem__(key)
    
    def __setitem__(self, key, value):
        # Do we need to create the dictionary?
        if self.__realdict__ is _zerodict:
            self.__realdict__ = dict()
            
        self.__realdict__.__setitem__(key, value)

    def __delitem__(self, key):
        self.__realdict__.__delitem__(key)
        
    def __iter__(self):
        # This iterator will be writable!
        # Luckily, if we're using the zero dictionary it'll return straight
        # away, so we don't have to worry about trashing that.
        return self.__realdict__.__iter__()
    
    def __contains__(self, item):
        return self.__realdict__.__contains__(item)

    # Pickle this as a plain dictionary
    def __reduce__(self):
        return self.__realdict__.__reduce__()
    
    def __reduce_ex__(self, version):
        return self.__realdict__.__reduce_ex__(version)
    
    def clear(self):
        # Someone might have lazily wrapped an existing dictionary,
        # so better really clear this instead of changing it back
        # to _zerodict.
        self.__realdict__.clear()
        
    def copy(self):
        return lazydict(self)
    
    @staticmethod
    def fromkeys(S, v = None):
        result = dict.fromkeys(S, v)
        if len(result) == 0:
            return lazydict()
        else:
            return result
    
    def get(self, k, d = None):
        return self.__realdict__.get(k, d)
    
    def has_key(self, k):
        return self.__realdict__.has_key(k)
    
    def items(self):
        return self.__realdict__.items()
    
    def iteritems(self):
        return self.__realdict__.iteritems()
    
    def iterkeys(self):
        return self.__realdict__.iterkeys()
    
    def itervalues(self):
        return self.__realdict__.itervalues()
    
    def keys(self):
        return self.__realdict__.keys()
    
    def pop(self, k, d = _singleton):
        if d is _singleton:
            return self.__realdict__.pop(k)
        else:
            return self.__realdict__.pop(k, d)
        
    def popitem(self):
        return self.__realdict__.popitem()
    
    def setdefault(self, k, d = None):
        if self.__realdict__ is _zerodict:
            self.__realdict__ = dict()
            
        self.__realdict__.setdefault(k, d)
        
    def update(self, e, **f):
        if self.__realdict__ is _zerodict:
            self.__realdict__ = dict()
            
        self.__realdict__.update(e, **f)
        
    def values(self):
        return self.__realdict__.values()