"""Attribute-based learning algorithms from AIMA (Russell & Norvig, Ch. 19).

Vendored subset of aima-python's knowledge.py (MIT License,
Copyright (c) 2016 aima-python contributors):
  https://github.com/aimacode/aima-python/blob/master/knowledge.py
Retrieved 2026-06-10 for the CoursIA SymbolicLearning series (SL-1).

Included (pure-stdlib, attribute/dict-based):
  - current_best_learning  [Figure 19.2] + specializations/generalizations/add_or
  - version_space_learning [Figure 19.3] + version_space_update/all_hypotheses
  - minimal_consistent_det [Figure 19.8] + consistent_det
  - helpers: values_table, build_attr_combinations, build_h_combinations,
    check_all_consistency, check_negative_consistency, disjunction_value,
    guess_value, is_consistent, false_positive, false_negative

Excluded: FOILContainer (FOIL, Figure 19.12) -- depends on aima-python's
logic.py (FolKB, expr); use a full aima-python checkout if you need it.
power_set is inlined from aima-python's utils.py (same license).
"""

from collections import defaultdict
from itertools import chain, combinations, product
from random import shuffle


def power_set(iterable):
    """power_set([1,2,3]) --> (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"""
    s = list(iterable)
    return list(chain.from_iterable(combinations(s, r) for r in range(len(s) + 1)))[1:]



def current_best_learning(examples, h, examples_so_far=None):
    """
    [Figure 19.2]
    The hypothesis is a list of dictionaries, with each dictionary representing
    a disjunction.
    """
    if examples_so_far is None:
        examples_so_far = []
    if not examples:
        return h

    e = examples[0]
    if is_consistent(e, h):
        return current_best_learning(examples[1:], h, examples_so_far + [e])
    elif false_positive(e, h):
        for h2 in specializations(examples_so_far + [e], h):
            h3 = current_best_learning(examples[1:], h2, examples_so_far + [e])
            if h3 != 'FAIL':
                return h3
    elif false_negative(e, h):
        for h2 in generalizations(examples_so_far + [e], h):
            h3 = current_best_learning(examples[1:], h2, examples_so_far + [e])
            if h3 != 'FAIL':
                return h3

    return 'FAIL'


def specializations(examples_so_far, h):
    """Specialize the hypothesis by adding AND operations to the disjunctions"""
    hypotheses = []

    for i, disj in enumerate(h):
        for e in examples_so_far:
            for k, v in e.items():
                if k in disj or k == 'GOAL':
                    continue

                h2 = h[i].copy()
                h2[k] = '!' + v
                h3 = h.copy()
                h3[i] = h2
                if check_all_consistency(examples_so_far, h3):
                    hypotheses.append(h3)

    shuffle(hypotheses)
    return hypotheses


def generalizations(examples_so_far, h):
    """Generalize the hypothesis. First delete operations
    (including disjunctions) from the hypothesis. Then, add OR operations."""
    hypotheses = []

    # Delete disjunctions
    disj_powerset = power_set(range(len(h)))
    for disjs in disj_powerset:
        h2 = h.copy()
        for d in reversed(list(disjs)):
            del h2[d]

        if check_all_consistency(examples_so_far, h2):
            # CoursIA fix (2026-06-10): upstream does `hypotheses += h2` (and
            # `+= h3` below), which EXTENDS the candidate list with the
            # individual *disjuncts* (dicts) instead of appending the hypothesis
            # (a list of dicts). Downstream, guess_value() then iterates over a
            # dict and crashes on its string keys. Unfixed in
            # aimacode/aima-python at retrieval date (their tests never reach
            # these branches).
            hypotheses.append(h2)

    # Delete AND operations in disjunctions
    for i, disj in enumerate(h):
        a_powerset = power_set(disj.keys())
        for attrs in a_powerset:
            h2 = h[i].copy()
            for a in attrs:
                del h2[a]

            if check_all_consistency(examples_so_far, [h2]):
                h3 = h.copy()
                h3[i] = h2.copy()
                hypotheses.append(h3)  # CoursIA fix: same `+=` bug as above

    # Add OR operations
    if hypotheses == [] or hypotheses == [{}]:
        hypotheses = add_or(examples_so_far, h)
    else:
        hypotheses.extend(add_or(examples_so_far, h))

    shuffle(hypotheses)
    return hypotheses


def add_or(examples_so_far, h):
    """Add an OR operation to the hypothesis. The AND operations in the disjunction
    are generated by the last example (which is the problematic one)."""
    ors = []
    e = examples_so_far[-1]

    attrs = {k: v for k, v in e.items() if k != 'GOAL'}
    a_powerset = power_set(attrs.keys())

    for c in a_powerset:
        h2 = {}
        for k in c:
            h2[k] = attrs[k]

        if check_negative_consistency(examples_so_far, h2):
            h3 = h.copy()
            h3.append(h2)
            ors.append(h3)

    return ors


# ______________________________________________________________________________


def version_space_learning(examples):
    """
    [Figure 19.3]
    The version space is a list of hypotheses, which in turn are a list
    of dictionaries/disjunctions.
    """
    V = all_hypotheses(examples)
    for e in examples:
        if V:
            V = version_space_update(V, e)

    return V


def version_space_update(V, e):
    return [h for h in V if is_consistent(e, h)]


def all_hypotheses(examples):
    """Build a list of all the possible hypotheses"""
    values = values_table(examples)
    h_powerset = power_set(values.keys())
    hypotheses = []
    for s in h_powerset:
        hypotheses.extend(build_attr_combinations(s, values))

    hypotheses.extend(build_h_combinations(hypotheses))

    return hypotheses


def values_table(examples):
    """Build a table with all the possible values for each attribute.
    Returns a dictionary with keys the attribute names and values a list
    with the possible values for the corresponding attribute."""
    values = defaultdict(lambda: [])
    for e in examples:
        for k, v in e.items():
            if k == 'GOAL':
                continue

            mod = '!'
            if e['GOAL']:
                mod = ''

            if mod + v not in values[k]:
                values[k].append(mod + v)

    values = dict(values)
    return values


def build_attr_combinations(s, values):
    """Given a set of attributes, builds all the combinations of values.
    If the set holds more than one attribute, recursively builds the
    combinations."""
    if len(s) == 1:
        # s holds just one attribute, return its list of values
        k = values[s[0]]
        h = [[{s[0]: v}] for v in values[s[0]]]
        return h

    h = []
    for i, a in enumerate(s):
        rest = build_attr_combinations(s[i + 1:], values)
        for v in values[a]:
            o = {a: v}
            for r in rest:
                t = o.copy()
                for d in r:
                    t.update(d)
                h.append([t])

    return h


def build_h_combinations(hypotheses):
    """Given a set of hypotheses, builds and returns all the combinations of the
    hypotheses."""
    h = []
    h_powerset = power_set(range(len(hypotheses)))

    for s in h_powerset:
        t = []
        for i in s:
            t.extend(hypotheses[i])
        h.append(t)

    return h


# ______________________________________________________________________________


def minimal_consistent_det(E, A):
    """Return a minimal set of attributes which give consistent determination"""
    n = len(A)

    for i in range(n + 1):
        for A_i in combinations(A, i):
            if consistent_det(A_i, E):
                return set(A_i)


def consistent_det(A, E):
    """Check if the attributes(A) is consistent with the examples(E)"""
    H = {}

    for e in E:
        attr_values = tuple(e[attr] for attr in A)
        if attr_values in H and H[attr_values] != e['GOAL']:
            return False
        H[attr_values] = e['GOAL']

    return True


# ______________________________________________________________________________


def check_all_consistency(examples, h):
    """Check for the consistency of all examples under h."""
    for e in examples:
        if not is_consistent(e, h):
            return False

    return True


def check_negative_consistency(examples, h):
    """Check if the negative examples are consistent under h."""
    for e in examples:
        if e['GOAL']:
            continue

        if not is_consistent(e, [h]):
            return False

    return True


def disjunction_value(e, d):
    """The value of example e under disjunction d."""
    for k, v in d.items():
        if v[0] == '!':
            # v is a NOT expression
            # e[k], thus, should not be equal to v
            if e[k] == v[1:]:
                return False
        elif e[k] != v:
            return False

    return True


def guess_value(e, h):
    """Guess value of example e under hypothesis h."""
    for d in h:
        if disjunction_value(e, d):
            return True

    return False


def is_consistent(e, h):
    return e['GOAL'] == guess_value(e, h)


def false_positive(e, h):
    return guess_value(e, h) and not e['GOAL']


def false_negative(e, h):
    return e['GOAL'] and not guess_value(e, h)