from typing import Sequence
from typing import Hashable
import difflib


def birnbaum_simil(
    seq_x: Sequence[Hashable], seq_y: Sequence[Hashable], normal: bool = False
) -> float:
    """
    Compute the Birnbaum similarity score with the fast method.

    This implementation uses the experimental method we developed following
    the description in Birnbaum (2003), which is much faster and less
    memory-intensive than the one implemented in the `birnbaum_simil()`
    function. While in most cases the results are comparable, particularly
    after scaling/normalization, and while the ones
    provided by this method might be considered more adequate due to their
    handling of duplicate information, the values are *not* identical.

    Example
    ********

    .. code-block:: python

        >>> seqsim.edit.birnbaum_simil("abc", "bcde")
        3.0

    References
    ***********

    Birnbaum, David J. (2003). "Computer-Assisted Analysis and
    Study of the Structure of Mixed-Content Miscellanies". Scripta &
    Scripta 1:15-64.

    :param seq_x: The first sequence to be compared.
    :param seq_y: The second sequence to be compared.
    :param normal: Whether to normalize the similarity score in range
        [0..1] using sequence lengths.
    :return: The similarity score between the two sequences. The higher
        the similarity score, the more similar the two sequences are;
        a similarity score of zero is the theoretical maximum difference
        between two sequences.
    """

    # If the sequences are equal, we can just compute the score from length
    if seq_x == seq_y:
        length = len(seq_x)
        return (length * (length + 1)) // 2

    # Make sure `seq_x` is shorter or equal in length to `seq_y`
    if len(seq_x) < len(seq_y):
        seq_x, seq_y = seq_y, seq_x

    # Get the opcodes from `SequenceMatcher` and drop the last one (a dummy)
    sm = difflib.SequenceMatcher(None, seq_x, seq_y)
    blocks = sm.get_matching_blocks()[:-1]

    # Sum sizes and return
    sizes = [match.size for match in blocks]
    similarity = sum([(v * (v + 1)) // 2 for v in sizes])

    if normal:
        return float(similarity) / max(
            [
                birnbaum_simil(seq_x, seq_x),
                birnbaum_simil(seq_y, seq_y),
            ]
        )

    return float(similarity)