import hashlib


class MaglevHash(object):
    def __init__(self, m=65537):
        self.m = m
        self.permutation = {}
        self.entry = [None] * self.m

    def add(self, node):
        if node in self.permutation.keys():
            raise KeyError("Node already exist")

        permutation = self._generate_permutation(node)
        self.permutation[node] = permutation

    def remove(self, node):
        if node not in self.permutation.keys():
            raise KeyError("Node not found")

        del self.permutation[node]

    def populate(self):
        entry = self._populate_entry()
        distance = [
            a == b for a, b in zip(self.entry, entry)].count(False)
        self.entry = entry

        return distance

    def lookup(self, key):
        index_hash = int(hashlib.sha256(
            "{}:lookup".format(key).encode("ascii")).hexdigest(), 16)
        index = index_hash % self.m

        return self.entry[index]

    def _generate_permutation(self, node):
        offset_hash = int(hashlib.sha256(
            "{}:offset".format(node).encode("ascii")).hexdigest(), 16)
        offset = offset_hash % self.m
        skip_hash = int(hashlib.sha256(
            "{}:skip".format(node).encode("ascii")).hexdigest(), 16)
        skip = (skip_hash % (self.m - 1)) + 1

        permutation = [None] * self.m
        for j in range(self.m):
            permutation[j] = (offset + j * skip) % self.m

        return permutation

    def _populate_entry(self):
        if not self.permutation:
            return [None] * self.m, self.m

        next_tracker = dict.fromkeys(self.permutation.keys(), 0)
        entry = [None] * self.m

        n = 0
        while True:
            for node in sorted(self.permutation.keys()):
                c = self.permutation[node][next_tracker[node]]
                while entry[c] is not None:
                    next_tracker[node] += 1
                    c = self.permutation[node][next_tracker[node]]

                entry[c] = node
                next_tracker[node] += 1
                n += 1

                if n == self.m:
                    return entry