<commit_before>#!/usr/bin/env python
"""
Use the Czech et al. method for generating minimal perfect hashes for strings.
"""

import random
import collections

# Hmm...
from . import forest
from .utils import create_dict_subclass


__all__ = ['hash_parameters', 'make_hash', 'make_dict']


_info_fields = ('t1', 't2', 'g', 'indices')
HashInfo = collections.namedtuple('HashInfo', _info_fields)


class CzechHashBuilder(object):

    """
    A helper class that (iteratively) stores all data needed to create a Czech
    hash.

    The entire hash generation algorithm occurs in  __init__.
    """

    def __init__(self, words, minimize=False):
        # Store the words as an immutable sequence.
        self.words = tuple(words)

        # TODO: Index minimization
        self.indices = range(len(words[0]))

        # Each of the following steps add fields to `self`:

        # Mapping step:
        #  - n, t1, t2, f1, f2, graph
        self.generate_acyclic_graph()
        # Assignment step:
        #  - g
        self.assign()

        # Now hash_info will return the appropriate object.

    @property
    def hash_info(self):
        """
        HashInfo tuple for the created hash.
        """
        return HashInfo(*(getattr(self, key) for key in _info_fields))

    @property
    def hash_function(self):
        """
        Returns the hash function proper. Ensures that `self` is not bound to
        the returned closure.
        """
        assert hasattr(self, 'f1') and hasattr(self, 'f2')

        # These are not just convenient aliases for the given
        # attributes; if `self` would creep into the returned closure,
        # that would ensure that a reference to this big, fat object
        # would be kept alive; hence, any hash function would carry
        # around all of the auxiliary state that was created during the
        # creation of the hash parameters.  Omitting `self` ensures this
        # object has a change to be garbage collected.
        f1, f2, g = self.f1, self.f2, self.g

        def czech_hash(word):
            v1 = f1(word)
            v2 = f2(word)
            return g[v1] + g[v2]

        return czech_hash

    # Algorithm steps.

    def generate_acyclic_graph(self):
        """
        Generates an acyclic graph for the given words.
        Returns graph, and a list of edge-word associations.
        """

        # Maximum length of each table, respectively.
        # Hardcoded n = cm, where c = 3
        # There might be a good way to choose an appropriate C,
        # but [1] suggests the average amount of iterations needed
        # to generate an acyclic graph is sqrt(3).
        self.n = 3 * len(self.words)

        max_tries = len(self.words) ** 2
        for trial in xrange(max_tries):
            try:
                self.generate_or_fail()
            except forest.InvariantError:
                continue
            else:
                self.trials_taken = trial + 1
                break

    def generate_random_table(self):
        """
        Generates random tables for given word lists.
        """
        table = range(0, self.n)
        random.shuffle(table)
        return table

    def generate_or_fail(self):
        """
        Attempts to generate a random acyclic graph, raising an
        InvariantError if unable to.
        """

        t1 = self.generate_random_table()
        t2 = self.generate_random_table()
        f1 = self.generate_func(t1)
        f2 = self.generate_func(t2)
        edges = [(f1(word), f2(word)) for word in self.words]

        # Try to generate that graph, mack!
        # Note that failure to generate the graph here should be caught
        # by the caller.
        graph = forest.ForestGraph(edges=edges)

        # Associate each edge with its corresponding word.
        associations = {}
        for num in xrange(len(self.words)):
            edge = edges[num]
            word = self.words[num]
            associations[graph.canonical_order(edge)] = (num, word)

        # Assign all of these to the object.
        for name in ('t1', 't2', 'f1', 'f2', 'graph', 'associations'):
            self.__dict__[name] = locals()[name]

    def generate_func(self, table):
        """
        Generates a random table based mini-hashing function.
        """

        # Ensure that `self` isn't suddenly in the closure...
        n = self.n

        def func(word):
            return sum(x * ord(c) for x, c in zip(table, word)) % n

        return func

    def assign(self):
        # Create an vector of empty assignments.
        self.g = [None] * (self.n + 1)

        # Assign all vertices.
        for vertex in self.graph.vertices:
            assert isinstance(vertex, int) and vertex <= self.n
            # This vertex has already been assigned.
            if self.g[vertex] is not None:
                continue

            self.g[vertex] = 0
            self.assign_vertex(vertex)

    def assign_vertex(self, vertex,):
        for neighbour in self.graph.neighbours(vertex):
            if self.g[neighbour] is not None:
                # This neighbour has already been assigned.
                continue

            # Get the associated edge number
            edge = self.graph.canonical_order((vertex, neighbour))
            num, _word = self.associations[edge]

            # Assign this vertex such that
            # h(word) == g(vertex) + g(neighbour)
            self.g[neighbour] = num - self.g[vertex]
            self.assign_vertex(neighbour)

# API functions  ##############################################################


def hash_parameters(words, minimize_indices=False):
    """
    Gives hash parameters for the given set of words.

    >>> info = hash_parameters('sun mon tue wed thu fri sat'.split())
    >>> len(info.t1)
    21
    >>> len(info.t2)
    21
    >>> len(info.g) # g values are 1-indexed...
    22
    """
    # Ensure that we have an indexable sequence.
    words = tuple(words)

    # Delegate to the hash builder.<commit_msg>Ensured input is always deduplicated and ordered; added tests for this.<commit_after>#!/usr/bin/env python
"""
Use the Czech et al. method for generating minimal perfect hashes for strings.
"""

import random
import collections

from . import forest
from .utils import create_dict_subclass


__all__ = ['hash_parameters', 'make_hash', 'make_dict']


_info_fields = ('t1', 't2', 'g', 'indices')
HashInfo = collections.namedtuple('HashInfo', _info_fields)


class CzechHashBuilder(object):

    """
    A helper class that (iteratively) stores all data needed to create a Czech
    hash.

    The entire hash generation algorithm occurs in  __init__.

    >>> duplicated_input = 'guacala'
    >>> unique_len = len(set(duplicated_input))
    >>> info = CzechHashBuilder(duplicated_input)
    >>> 2 * unique_len <= info.n <= 3 * unique_len
    True
    >>> info.trials_taken <= info.n ** 0.5
    True
    >>> hf = info.hash_function
    >>> [hf(x) for x in 'lacug']
    [4, 2, 3, 1, 0]
    """

    def __init__(self, words, minimize=False):
        # Store the words as an immutable sequence.
        self.words = ordered_deduplicate(words)

        # TODO: Index minimization
        self.indices = range(len(words[0]))

        # Each of the following steps add fields to `self`:

        # Mapping step:
        #  - n, t1, t2, f1, f2, graph
        self.generate_acyclic_graph()
        # Assignment step:
        #  - g
        self.assign()
        # Now hash_info will return the appropriate object.

    @property
    def hash_info(self):
        """
        HashInfo tuple for the created hash.
        """
        return HashInfo(*(getattr(self, key) for key in _info_fields))

    @property
    def hash_function(self):
        """
        Returns the hash function proper. Ensures that `self` is not bound to
        the returned closure.
        """
        assert hasattr(self, 'f1') and hasattr(self, 'f2')

        # These are not just convenient aliases for the given
        # attributes; if `self` would creep into the returned closure,
        # that would ensure that a reference to this big, fat object
        # would be kept alive; hence, any hash function would carry
        # around all of the auxiliary state that was created during the
        # generation of the hash parameters.  Omitting `self` ensures
        # this object has a chance to be garbage collected.
        f1, f2, g = self.f1, self.f2, self.g

        def czech_hash(word):
            v1 = f1(word)
            v2 = f2(word)
            return g[v1] + g[v2]

        return czech_hash

    # Algorithm steps.

    def generate_acyclic_graph(self):
        """
        Generates an acyclic graph for the given words.
        Adds the graph, and a list of edge-word associations to the object.
        """

        # Maximum length of each table, respectively.
        # Hardcoded n = cm, where c = 3
        # There might be a good way to choose an appropriate C,
        # but [1] suggests the average amount of iterations needed
        # to generate an acyclic graph is sqrt(3).
        self.n = 3 * len(self.words)

        max_tries = len(self.words) ** 2
        for trial in xrange(max_tries):
            try:
                self.generate_or_fail()
            except forest.InvariantError:
                continue
            else:
                # Generated successfully!
                self.trials_taken = trial + 1
                return

        raise RuntimeError("Could not generate graph in "
                           "{} tries".format(max_tries))

    def generate_random_table(self):
        """
        Generates random tables for given word lists.
        """
        table = range(0, self.n)
        random.shuffle(table)
        return table

    def generate_or_fail(self):
        """
        Attempts to generate a random acyclic graph, raising an
        InvariantError if unable to.
        """

        t1 = self.generate_random_table()
        t2 = self.generate_random_table()
        f1 = self.generate_func(t1)
        f2 = self.generate_func(t2)
        edges = [(f1(word), f2(word)) for word in self.words]

        # Try to generate that graph, mack!
        # Note that failure to generate the graph here should be caught
        # by the caller.
        graph = forest.ForestGraph(edges=edges)

        # Associate each edge with its corresponding word.
        associations = {}
        for num in xrange(len(self.words)):
            edge = edges[num]
            word = self.words[num]
            associations[graph.canonical_order(edge)] = (num, word)

        # Assign all of these to the object.
        for name in ('t1', 't2', 'f1', 'f2', 'graph', 'associations'):
            self.__dict__[name] = locals()[name]

    def generate_func(self, table):
        """
        Generates a random table based mini-hashing function.
        """

        # Ensure that `self` isn't suddenly in the closure...
        n = self.n

        def func(word):
            return sum(x * ord(c) for x, c in zip(table, word)) % n

        return func

    def assign(self):
        # Create an vector of empty assignments.
        # **g is 1-indexed!**
        self.g = [None] * (self.n + 1)

        # Assign all vertices.
        for vertex in self.graph.vertices:
            assert isinstance(vertex, int) and vertex <= self.n
            # This vertex has already been assigned.
            if self.g[vertex] is not None:
                continue

            self.g[vertex] = 0
            self.assign_vertex(vertex)

    def assign_vertex(self, vertex):
        for neighbour in self.graph.neighbours(vertex):
            if self.g[neighbour] is not None:
                # This neighbour has already been assigned.
                continue

            # Get the associated edge number
            edge = self.graph.canonical_order((vertex, neighbour))
            num, _word = self.associations[edge]

            # Assign this vertex such that
            # h(word) == g(vertex) + g(neighbour)
            self.g[neighbour] = num - self.g[vertex]
            self.assign_vertex(neighbour)


def ordered_deduplicate(sequence):
    """
    Returns the sequence as a tuple with the duplicates removed,
    preserving input order.  Any duplicates following the first
    occurrence are removed.

    >>> ordered_deduplicate([1, 2, 3, 1, 32, 1, 2])
    (1, 2, 3, 32)

    Based on recipe from this StackOverflow post:
    http://stackoverflow.com/a/480227
    """

    seen = set()
    # Micro optimization: each call to seen_add saves an extra attribute
    # lookup in most iterations of the loop.
    seen_add = seen.add

    return tuple(x for x in sequence if not (x in seen or seen_add(x)))


# API functions  ##############################################################

def hash_parameters(words, minimize_indices=False):
    """
    Gives hash parameters for the given set of words.

    >>> info = hash_parameters('sun mon tue wed thu fri sat'.split())
    >>> len(info.t1)
    21
    >>> len(info.t2)
    21
    >>> len(info.g) # g values are 1-indexed...
    22
    """
    # Ensure that we have an indexable sequence.
    words = tuple(words)

    # Delegate to the hash builder.
{'fraction_non_alphanumeric': 0.10286016149724549, 'fraction_numerical': 0.009584182325862198, 'mean_word_length': 2.074709976798144, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 51, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2838740', 'n_tokens_mistral': 3851, 'n_tokens_neox': 3660, 'n_words': 1286}