import collections
import weakref

class MutableKeyDict(collections.MutableMapping):
    hashdict = {}
    allinstances = []

    def __new__(cls,*args,**kwargs):
        ''' Create a new instance of MutableKeyDict '''
        newinstance = super(MutableKeyDict,cls).__new__(cls,*args,**kwargs)
        cls.allinstances.append(weakref.ref(newinstance))
        return newinstance

    def __init__(self,dictionary = {}):
        self.valdict = {}
        # Each object corresponds to a hash:
        # For example: mutableobject():value becomes
        # hashdict = (hash of mutableobject):mutableobject
        # valdict = (hash of mutableobject):value
        # This leads to inefficient setting and retreiving of values, though
        for key,value in dictionary.iteritems():
            keyhash = self.__gethash__(key)
            self.hashdict[keyhash] = key
            self.valdict[keyhash] = value

    def __updatehashes__(self,hashmap):
        print hashmap
        # Recreate the value dictionary based off of the new hashmap.
        for oldhash,newhash in hashmap.iteritems():
            if oldhash in self.valdict:
                val = self.valdict[oldhash]
                del self.valdict[oldhash]
                self.valdict[newhash] = val

    def __resethashes__(self):
        # Redo hashes of anything that changed. Prevents hash collisions
        newhashdict = {}
        newvaluedict = {}
        hashmapdict = {}
        for oldhash,objtohash in self.hashdict.iteritems():
            newhash = self.__gethash__(objtohash)
            hashmapdict[oldhash] = newhash
            newhashdict[newhash] = objtohash
        self.hashdict = newhashdict
        for inst in self.allinstances:
            inst().__updatehashes__(hashmapdict)

    def __getitem__(self,key):
        # Optimized to prevent unneeded hash calculations
        self.__resethashes__()
        if not key in self.hashdict.values():
            try:
                return self.default
            except AttributeError:
                raise KeyError(key)
        return self.valdict[self.hashdict.keys()[self.hashdict.values().index(key)]]

    def __setitem__(self,key,value):
        # Optimized to prevent unneeded hash calculations
        self.__resethashes__()
        if key in self.hashdict.values():
            self.valdict[self.hashdict.keys()[self.hashdict.values().index(key)]] = value
        else:
            keyhash = self.__gethash__(key)
            self.hashdict[keyhash] = key
            self.valdict[keyhash] = value

    def __delitem__(self,key):
        self.__resethashes__()
        if not key in self.hashdict.values():
            raise KeyError(key)
        else:
            hashtodelete = self.hashdict.keys()[self.hashdict.values().index(key)]
            if not hashtodelete in self.valdict:
                raise KeyError(key)
            del self.valdict[hashtodelete]

    def __gethash__(self,item):
        if isinstance(item,collections.Hashable) and (not isinstance(item,collections.MutableMapping)):
            return hash(item)
        elif hasattr(item,'__dict__'):
            return self.__gethash__(item.__dict__)
        elif type(item) is dict:
            x = 0
            for key,value in item.iteritems():
                k = self.__gethash__(key) + 2
                v = self.__gethash__(value) + 2
                x += k^((k << 6)+(v >> 2) + v)
            return x + self.__gethash__(item.keys())
        elif isinstance(item,list):
            x = 0
            for i in item:
                k = self.__gethash__(i) + 5
                x += x^ ((x << 6) + (k >> 2) + k)
            return x
        elif isinstance(item,dict):
            x = 0
            for i in item:
                k = self.__gethash__(i) + 3
                x += x^ ((x << 6) + (k >> 2) + k)
            return x
        elif isinstance(item,set):
            x = 0
            for i in list(item):
                k = self.__gethash__(i) + 7
                x += x^ ((x << 6) + (k >> 2) + k)
            return x
        else:
            raise RuntimeError("Unhashable type " + type(item))

    def keys(self):
        return [self.hashdict[x] for x in self.valdict.keys()]

    def values(self):
        return self.valdict.values()

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

    def items(self):
        return list(zip(self.keys(),self.values()))

    def iteritems(self):
        for key,value in self.valdict.iteritems():
            yield (self.hashdict[key],value)
        raise StopIteration

    def __iter__(self):
        for key,value in self.valdict.iteritems():
            yield self.hashdict[key]
        raise StopIteration

    def __contains__(self,item):
        return item in self.keys()

    def get(self,item,default=None):
        # Optimized to prevent unneeded hash calculations
        self.__resethashes__()
        if not key in self.hashdict.values():
            return default
        return self.valdict[self.hashdict.keys()[self.hashdict.values().index(key)]]

    def clear(self):
        self.valdict = {}

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

    def pop(self,*args):
        if len(args) > 0:
            key = self.keys()[-1]
            ret = self.get(key,args[0])
            if args[0] in self.keys():
                del self[args[0]]
            return ret
        key = self.keys()[-1]
        ret = self[key]
        del self[key]
        return ret

    def popitem(self):
        key = self.keys()[-1]
        val = self[key]
        del self[key]
        return key,val

    def copy(self):
        return self.__class__(self)

    def update(self,other):
        for key,val in other.iteritems():
            self[key] = val

    def __repr__(self,forMutable=False):
        ret = '{'
        if len(self) == 0:
            return '{}'
        if forMutable:
            return '{...}'
        needsComma = False
        for k,v in self.iteritems():
            if needsComma:
                ret += ','
            needsComma = True
            reprk = k.__repr__(True) if isinstance(k,MutableKeyDict) else repr(k)
            reprv = v.__repr__(True) if isinstance(v,MutableKeyDict) else repr(v)
            ret += reprk + ':' + reprv
        ret += '}'
        return ret