Match compounds greedily based on score function.

    Args:
        reaction: Reaction equation :class:`psamm.reaction.Reaction`.
        compound_formula: Dictionary mapping compound IDs to
            :class:`psamm.formula.Formula`. Formulas must be flattened.
        score_func: Function that takes two :class:`_CompoundInstance` and
            returns the score.

def _match_greedily(reaction, compound_formula, score_func):
    """Match compounds greedily based on score function.

    Args:
        reaction: Reaction equation :class:`psamm.reaction.Reaction`.
        compound_formula: Dictionary mapping compound IDs to
            :class:`psamm.formula.Formula`. Formulas must be flattened.
        score_func: Function that takes two :class:`_CompoundInstance` and
            returns the score.
    """
    uninstantiated_left, uninstantiated_right = _reaction_to_dicts(reaction)

    def compound_instances(uninstantiated):
        instances = []
        for compound, value in iteritems(uninstantiated):
            if value > 0:
                f = compound_formula[compound.name]
                instances.append(_CompoundInstance(compound, value, f))

        for inst in instances:
            uninstantiated[inst.compound] -= 1

        return instances

    def instantiate(uninstantiated, compound):
        n = uninstantiated[compound]
        if n > 0:
            f = compound_formula[compound.name]
            inst = _CompoundInstance(compound, n, f)
            uninstantiated[compound] -= 1
            return inst

        return None

    left = compound_instances(uninstantiated_left)
    right = compound_instances(uninstantiated_right)
    instances = left + right

    pairs = {}
    for inst1, inst2 in product(left, right):
        result = score_func(inst1, inst2)
        if result is not None:
            pairs[inst1, inst2] = result

    def inst_pair_sort_key(entry):
        """Sort key for finding best match among instance pairs.

        Rank by score in general but always match identical compounds first
        (these will always have score equal to one but are handled specially
        to put them ahead of other compounds with score equal to one). Use
        compound names to break ties to produce a deterministic result.
        """
        (inst1, inst2), score = entry
        c1, c2 = inst1.compound, inst2.compound
        same_compound = c1.name == c2.name and c1.compartment != c2.compartment
        return same_compound, score, c1.name, c2.name

    transfer = {}
    while len(pairs) > 0:
        (inst1, inst2), _ = max(iteritems(pairs), key=inst_pair_sort_key)
        common = inst1.formula & inst2.formula

        key = (inst1.compound, inst1.index), (inst2.compound, inst2.index)
        if key not in transfer:
            transfer[key] = Formula()
        transfer[key] |= common

        for inst in (inst1, inst2):
            inst.formula -= common

        to_insert = set()

        inst = instantiate(uninstantiated_left, inst1.compound)
        if inst is not None:
            left.append(inst)
            instances.append(inst)
            to_insert.add(inst)

        inst = instantiate(uninstantiated_right, inst2.compound)
        if inst is not None:
            right.append(inst)
            instances.append(inst)
            to_insert.add(inst)

        to_update = {inst1, inst2}

        to_delete = set()
        for inst1, inst2 in pairs:
            if inst1 in to_update or inst2 in to_update:
                if len(inst1.formula) > 0 and len(inst2.formula) > 0:
                    result = score_func(inst1, inst2)
                    if result is None:
                        to_delete.add((inst1, inst2))
                    else:
                        pairs[inst1, inst2] = result
                else:
                    to_delete.add((inst1, inst2))

        for pair in to_delete:
            del pairs[pair]

        for inst1, inst2 in product(left, right):
            if inst1 in to_insert or inst2 in to_insert:
                result = score_func(inst1, inst2)
                if result is not None:
                    pairs[inst1, inst2] = result

    balance = {}
    for inst in instances:
        if len(inst.formula) > 0:
            key = inst.compound, inst.index
            balance[key] = inst.formula

    return transfer, balance