# An implementation of https://en.wikipedia.org/wiki/Rendezvous_hashing
from typing import Callable, List, Tuple
import mmh3
import heapq

Hasher = Callable[[str, str], int]
Member = str
Members = List[str]
Key = str


def assign(
    key: Key, members: Members, hasher: Hasher, replication: int
) -> List[Member]:
    """Assigns a key to a member using the rendezvous hashing algorithm
    Args:
        key: The key to assign
        members: The list of members to assign the key to
        hasher: The hashing function to use
        replication: The number of members to assign the key to
    Returns:
        A list of members that the key has been assigned to
    """

    if replication > len(members):
        raise ValueError(
            "Replication factor cannot be greater than the number of members"
        )
    if len(members) == 0:
        raise ValueError("Cannot assign key to empty memberlist")
    if len(members) == 1:
        # Don't copy the input list for some safety
        return [members[0]]
    if key == "":
        raise ValueError("Cannot assign empty key")

    member_score_heap: List[Tuple[int, Member]] = []
    for member in members:
        score = -hasher(member, key)
        # Invert the score since heapq is a min heap
        heapq.heappush(member_score_heap, (score, member))

    output_members: List[Member] = []
    for _ in range(replication):
        member_and_score = heapq.heappop(member_score_heap)
        output_members.append(member_and_score[1])

    return output_members


def merge_hashes(x: int, y: int) -> int:
    """murmurhash3 mix 64-bit"""
    acc = x ^ y
    acc ^= acc >> 33
    acc = (
        acc * 0xFF51AFD7ED558CCD
    ) % 2**64  # We need to mod here to prevent python from using arbitrary size int
    acc ^= acc >> 33
    acc = (acc * 0xC4CEB9FE1A85EC53) % 2**64
    acc ^= acc >> 33
    return acc


def murmur3hasher(member: Member, key: Key) -> int:
    """Hashes the key and member using the murmur3 hashing algorithm"""
    member_hash = mmh3.hash64(member, signed=False)[0]
    key_hash = mmh3.hash64(key, signed=False)[0]
    return merge_hashes(member_hash, key_hash)