## poor man's perfect_dict implementation
class Entry:
    def __init__(self, key, value):
        self.key = key
        self.value = value
InvalidEntry = Entry(None, 0)

class perfect_dict:
    "XXX: this implementation does not handle collisions"
    
    def __init__(self, G, d=None):
        N = len(G) - 1
        self.G = G
        self.N = N
        self.entries = [InvalidEntry] * N
        if d is not None:
            for key, value in d.iteritems():
                self.set(key, value)

    def perfect_hash_fast(self, h):
        N = self.N
        G = self.G
        i = h & (N-1)
        j = i+1
        res = G[i] + G[j]
        res = res & N-1
        return res

    def perfect_hash(self, key):
        h = hash(key)
        return self.perfect_hash_fast(h)

    def set(self, key, value):
        i = self.perfect_hash(key)
        if self.entries[i] is not InvalidEntry:
            raise NotImplementedError
        else:
            self.entries[i] = Entry(key, value)

    def get(self, default, key):
        h = hash(key)
        return self.get_fast(key, default, h)

    def get_fast(self, key, default, h):
        i = self.perfect_hash_fast(h)
        entry = self.entries[i]
        if entry.key is key:
            return entry.value
        else:
            # do a full lookup
            raise NotImplementedError