from typing import Counter


def _compute_consensus_annotation(annotations, min_consensus,
                                  unassignable_label):
    """ Compute the consensus of a collection of annotations
        Parameters
        ----------
        annotations : list of lists
            Taxonomic annotations to compute the consensus of.
        min_consensus : float
            The minimum fraction of the annotations that a specfic annotation
            must be present in for that annotation to be accepted. This must
            be greater than or equal to 0.51.
        unassignable_label : str
            The label to apply if no acceptable annotations are identified.
        Result
        ------
        consensus_annotation
            List containing the consensus assignment
        consensus_fraction
            Fraction of input annotations that agreed at the deepest
            level of assignment
    """
    if min_consensus <= 0.5:
        raise ValueError("min_consensus must be greater than 0.5.")
    num_input_annotations = len(annotations)
    consensus_annotation = []

    # if the annotations don't all have the same number
    # of levels, the resulting annotation will have a max number
    # of levels equal to the number of levels in the assignment
    # with the fewest number of levels. this is to avoid
    # a case where, for example, there are n assignments, one of
    # which has 7 levels, and the other n-1 assignments have 6 levels.
    # A 7th level in the result would be misleading because it
    # would appear to the user as though it was the consensus
    # across all n assignments.
    num_levels = min([len(a) for a in annotations])

    # iterate over the assignment levels
    for level in range(num_levels):
        # count the different taxonomic assignments at the current level.
        # the counts are computed based on the current level and all higher
        # levels to reflect that, for example, 'p__A; c__B; o__C' and
        # 'p__X; c__Y; o__C' represent different taxa at the o__ level (since
        # they are different at the p__ and c__ levels).
        current_level_annotations = \
            Counter([tuple(e[:level + 1]) for e in annotations])
        # identify the most common taxonomic assignment, and compute the
        # fraction of annotations that contained it. it's safe to compute the
        # fraction using num_assignments because the deepest level we'll
        # ever look at here is num_levels (see above comment on how that
        # is decided).
        tax, max_count = current_level_annotations.most_common(1)[0]
        max_consensus_fraction = max_count / num_input_annotations
        # check whether the most common taxonomic assignment is observed
        # in at least min_consensus of the sequences
        if max_consensus_fraction >= min_consensus:
            # if so, append the current level only (e.g., 'o__C' if tax is
            # 'p__A; c__B; o__C', and continue on to the next level
            consensus_annotation.append((tax[-1], max_consensus_fraction))
        else:
            # if not, there is no assignment at this level, and we're
            # done iterating over levels
            break

    # construct the results
    # determine the number of levels in the consensus assignment
    consensus_annotation_depth = len(consensus_annotation)
    if consensus_annotation_depth > 0:
        # if it's greater than 0, generate a list of the
        # taxa assignments at each level
        annotation = [a[0] for a in consensus_annotation]
        # and assign the consensus_fraction_result as the
        # consensus fraction at the deepest level
        consensus_fraction_result = \
            consensus_annotation[consensus_annotation_depth - 1][1]
    else:
        # if there are zero assignments, indicate that the taxa is
        # unknown
        annotation = [unassignable_label]
        # and assign the consensus_fraction_result to 1.0 (this is
        # somewhat arbitrary, but could be interpreted as all of the
        # assignments suggest an unknown taxonomy)
        consensus_fraction_result = 1.0

    return annotation, consensus_fraction_result