import itertools


def _solve_bruteforce(D, all_solutions, valid, spin, value):
    """_solve_bruteforce.

    Helper function for solve_pubo_bruteforce, solve_puso_bruteforce,
    solve_qubo_bruteforce, and solve_quso_bruteforce.

    Iterate through all the possible solutions to a BO formulated problem
    and find the best one (the one that gives the minimum objective value). Do
    not use for large problem sizes! This is meant only for testing very small
    problems.

    Parameters
    ----------
    D : dict.
    all_solutions : boolean (optional, defaults to False).
        If all_solutions is set to True, all the best solutions to the problem
        will be returned rather than just one of the best. If the problem is
        very big, then it is best if ``all_solutions`` is False, otherwise this
        function will use a lot of memory.
    valid : function.
        ``valid`` takes in a bitstring or spinstring and outputs a boolean
        indicating whether that bitstring or spinstring is a valid solutions.
    spin : bool.
        Whether we're bruteforce solving a spin model or boolean model.
    value : function.
        One of ``qubo_value``, ``quso_value``, ``pubo_value``, or
        ``puso_value``.

    Returns
    -------
    res : tuple (objective, solution).

        if all_solutions is False:
            objective : float.
                The best value of the problem.
            solution : dict.
                Maps the binary variable label to its solution value,
                {0, 1} if not spin else {-1, 1}.

        if all_solutions is True:
            objective : float.
                The best value of the problem
            solution : list of dicts.
                Each dictionary maps the label to the value of each binary
                variable. Ie each ``s`` in ``solution`` is a solution that
                gives the best objective function value.

    """
    if not D:
        return 0, ({} if not all_solutions else [{}])
    elif () in D:
        offset = D.pop(())
        if not D:
            D[()] = offset
            return offset, ({} if not all_solutions else [{}])
        D[()] = offset

    # if D is a Matrix object or QUBO, PUBO, etc, then these are defined
    try:
        N = D.num_binary_variables
        # could do D.reverse_mapping, but that creates a copy. We just need to
        # not mutate it here, then we don't have to waste time copying.
        mapping = D._reverse_mapping
    except AttributeError:
        var = set()
        for x in D:
            var.update(set(x))
        N = len(var)

        # map qubit name to 0 through N-1
        mapping = dict(enumerate(var))

    best = None, {}
    all_sols = {None: [{}]}

    for test_sol in itertools.product((1, -1) if spin else (0, 1), repeat=N):
        x = {mapping[i]: v for i, v in enumerate(test_sol)}
        if not valid(x):
            continue
        v = value(x, D)
        if all_solutions and (best[0] is None or v <= best[0]):
            best = v, x
            all_sols.setdefault(v, []).append(x)
        elif best[0] is None or v < best[0]:
            best = v, x

    if all_solutions:
        best = best[0], all_sols[best[0]]

    return best