import math
from typing import List, Optional, Sequence

from .charts_histogram_bins_types import Bin, BinMethod
from .charts_ticks_tick_step import tick_spec
from .math_pow import pow as pow_float
from .math_round_float import round_float
from .stats_percentile import percentile

_MAX_BINS = 10000


def histogram_bins(values: Sequence[float], method: BinMethod, bin_width: Optional[float]) -> List[Bin]:
    """Histogram bins on round edges, as d3.bin lays them out. Each bin holds
    x0 <= v < x1; the last also holds its right edge. See the README."""
    if method == "fixed-width":
        if bin_width is None or isinstance(bin_width, bool) or not isinstance(bin_width, (int, float)) or not math.isfinite(bin_width) or bin_width <= 0:
            raise ValueError(f"fixed-width needs a binWidth greater than 0; got {bin_width}")
    elif method in ("sturges", "freedman-diaconis"):
        if bin_width is not None:
            raise ValueError(f"binWidth is only for fixed-width; pass null for {method}")
    else:
        raise ValueError(f'unknown bin method "{method}"')
    n = len(values)
    if n == 0:
        return []
    for v in values:
        if isinstance(v, bool) or not isinstance(v, (int, float)) or not math.isfinite(v):
            raise ValueError(f"values must be finite numbers; got {v}")
    lo = float(min(values))
    hi = float(max(values))

    if method == "fixed-width":
        mul, div = float(bin_width), 1.0
    else:
        if lo == hi:
            return [Bin(x0=lo + 0.0, x1=hi + 0.0, count=n)]
        if method == "sturges":
            # ceil(log2 n) + 1, by doubling rather than a logarithm.
            bits, power = 0, 1
            while power < n:
                power *= 2
                bits += 1
            count = bits + 1
        else:
            # Freedman and Diaconis: bin width 2 IQR n^(-1/3); d3 falls back
            # to one bin when the interquartile range is zero.
            iqr = percentile(values, 75, "linear", 12) - percentile(values, 25, "linear", 12)
            width = 2 * iqr * pow_float(float(n), -1 / 3)
            bins = math.ceil((hi - lo) / width) if width > 0 else 1
            if bins > _MAX_BINS:
                raise ValueError(f"too many bins: more than {_MAX_BINS}")
            count = max(1, bins)
        mul, div = tick_spec(lo, hi, count)

    def edge(i: int) -> float:
        # One exact operation on a whole number, cleaned at 12 places.
        return round_float(i / div if div > 1 else i * mul, 12)

    first = math.floor(lo * div if div > 1 else lo / mul)
    while edge(first) > lo:
        first -= 1
    while edge(first + 1) <= lo:
        first += 1
    last = first + 1
    while edge(last) < hi:
        last += 1
        if last - first > _MAX_BINS:
            raise ValueError(f"too many bins: more than {_MAX_BINS}")

    edges = [edge(i) for i in range(first, last + 1)]
    counts = [0] * (len(edges) - 1)
    for v in values:
        a, b = 0, len(counts) - 1
        while a < b:
            mid = (a + b + 1) // 2
            if edges[mid] <= v:
                a = mid
            else:
                b = mid - 1
        counts[a] += 1
    return [Bin(x0=edges[i], x1=edges[i + 1], count=c) for i, c in enumerate(counts)]