import math
from typing import Dict, Optional


class ComplexityScorer:
    """
    Complexity scoring for feature selection algorithms
    based on instantiated time and space complexity.
    """

    def __init__(self, alpha: float = 0.7, log_base: float = math.e):
        """
        Parameters
        ----------
        alpha : float
            Weight for time complexity in the final score.
            Typical values: 0.6 ~ 0.8
        log_base : float
            Base of logarithm (default: natural log).
        """
        self.alpha = alpha
        self.log_base = log_base

    # ------------------------------
    # Core scoring functions
    # ------------------------------

    def _log(self, x: float) -> float:
        """Logarithm with configurable base."""
        if self.log_base == math.e:
            return math.log(x)
        return math.log(x, self.log_base)

    def complexity_score(self, value: float, min_value: float) -> float:
        """
        Generic complexity-to-score mapping.

        Parameters
        ----------
        value : float
            Instantiated complexity value of an algorithm.
        min_value : float
            Minimum complexity among all compared algorithms.

        Returns
        -------
        score : float
            Normalized score in (0, 1].
        """
        if value <= 0 or min_value <= 0:
            raise ValueError("Complexity values must be positive.")

        ratio = value / min_value
        return 1.0 / (1.0 + self._log(ratio))

    def time_score(self, f_t: float, f_t_min: float) -> float:
        """Time complexity score."""
        return self.complexity_score(f_t, f_t_min)

    def space_score(self, f_s: float, f_s_min: float) -> float:
        """Space complexity score."""
        return self.complexity_score(f_s, f_s_min)

    def total_score(
        self,
        f_t: float,
        f_t_min: float,
        f_s: float,
        f_s_min: float,
    ) -> float:
        """Combined complexity score."""
        s_t = self.time_score(f_t, f_t_min)
        s_s = self.space_score(f_s, f_s_min)
        return self.alpha * s_t + (1.0 - self.alpha) * s_s


# --------------------------------------
# Utility: instantiate complexity formula
# --------------------------------------

def instantiate_complexity(
    formula: str,
    n: int,
    d: int,
    k: Optional[int] = None
) -> float:
    """
    Instantiate asymptotic complexity formula.

    Supported variables: n, d, k

    Examples
    --------
    "n * d**2"
    "n * d * k"
    "d**2"
    "d + k"
    """
    local_vars = {"n": n, "d": d}
    if k is not None:
        local_vars["k"] = k

    try:
        return float(eval(formula, {"__builtins__": {}}, local_vars))
    except Exception as e:
        raise ValueError(f"Invalid complexity formula: {formula}") from e


n, d, k = 1000, 50, 10

algorithms = {
    "mRMR": {"time": "n * d**2", "space": "d**2"},
    "JMIM": {"time": "n * d * k", "space": "d * k"},
    "CFR": {"time": "n * d * k","space": "d + k"},
    "DCSF": {"time": "n * d * k", "space": "d + k"},
    "IWFS": {"time": "n * d * k", "space": "d + k"},
    "MRI": {"time": "n * d * k", "space": "d + k"},
    "MRMD": {"time": "n * d**2", "space": "d**2"},
    "UCRFS": {"time": "n * d + n**2", "space": "n**2"},


}

# Instantiate complexities
time_vals = []
space_vals = {}

for name, comp in algorithms.items():
    f_t = instantiate_complexity(comp["time"], n, d, k)
    f_s = instantiate_complexity(comp["space"], n, d, k)
    time_vals.append(f_t)
    space_vals[name] = (f_t, f_s)

f_t_min = min(time_vals)
f_s_min = min(v[1] for v in space_vals.values())

scorer = ComplexityScorer(alpha=0.7)

for name, (f_t, f_s) in space_vals.items():
    score = scorer.total_score(f_t, f_t_min, f_s, f_s_min)
    print(f"{name}: complexity score = {score:.4f}")