# Hash implementations from
# http://www.partow.net/programming/hashfunctions/index.html
# Author: @luminousmen

class BloomFilter:
    def __init__(self, size: int):
        self.size = size
        self.bitmap = size * [0]

    def FNV(self, key: str):
        fnv_prime = 0x811C9DC5
        hash = 0
        for i in range(len(key)):
            hash *= fnv_prime
            hash ^= ord(key[i])
        return hash

    def DJB(self, key: str):
        hash = 5381
        for i in range(len(key)):
            hash = ((hash << 5) + hash) + ord(key[i])
        return hash

    def calculate_hash(self, value):
        # FNV
        hash1 = self.FNV(value) % self.size
        # MurMur
        hash2 = self.DJB(value) % self.size
        return hash1, hash2

    def add(self, value: str):
        for h in self.calculate_hash(value):
            self.bitmap[h] = 1

    def check(self, value):
        for h in self.calculate_hash(value):
            if not self.bitmap[h]:
                return False
        return True


if __name__ == "__main__":
    coffees = [
        "Iced Coffee",
        "Iced Coffee with Milk",
        "Espresso",
        "Espresso Macchiato",
        "Flat White",
        "Latte Macchiato",
        "Americano",
        "Mocha",
    ]

    bloom = BloomFilter(20)
    for drink in coffees:
        bloom.add(drink)
        print(bloom.bitmap)

    print(bloom.check("Flat White"))
    print(bloom.check("Cappuccino"))