src/bisection_tree/btfn.rs

use crate::mapping::{
    BasicDecomposition, DifferentiableImpl, DifferentiableMapping, Instance, Mapping, Space,
};
use crate::types::Float;
use numeric_literals::replace_float_literals;
use std::iter::Sum;
use std::marker::PhantomData;
use std::sync::Arc;
//use crate::linops::{Apply, Linear};
use super::aggregator::*;
use super::bt::*;
use super::either::*;
use super::refine::*;
use super::support::*;
use crate::bounds::MinMaxMapping;
use crate::fe_model::base::RealLocalModel;
use crate::fe_model::p2_local_model::*;
use crate::loc::Loc;
use crate::sets::Cube;
use crate::sets::Set;

/// Presentation for (mathematical) functions constructed as a sum of components functions with
/// typically small support.
///
/// The domain of the function is [`Loc`]`<N, F>`, where `F` is the type of floating point numbers,
/// and `N` the dimension.
///
/// The `generator` lists the component functions that have to implement [`Support`].
/// Identifiers of the components ([`SupportGenerator::Id`], usually `usize`) are stored stored
/// in a [bisection tree][BTImpl], when one is provided as `bt`. However `bt` may also be `()`
/// for a [`PreBTFN`] that is only useful for vector space operations with a full [`BTFN`].
#[derive(Clone, Debug)]
pub struct BTFN<F: Float, G: SupportGenerator<N, F>, BT /*: BTImpl< N, F>*/, const N: usize> /*where G::SupportType : LocalAnalysis<F, A, N>*/
{
    bt: BT,
    generator: Arc<G>,
    _phantoms: PhantomData<F>,
}

impl<F: Float, G, BT, const N: usize> Space for BTFN<F, G, BT, N>
where
    G: SupportGenerator<N, F, Id = BT::Data>,
    G::SupportType: LocalAnalysis<F, BT::Agg, N>,
    BT: BTImpl<N, F>,
{
    type Decomp = BasicDecomposition;
}

impl<F: Float, G, BT, const N: usize> BTFN<F, G, BT, N>
where
    G: SupportGenerator<N, F, Id = BT::Data>,
    G::SupportType: LocalAnalysis<F, BT::Agg, N>,
    BT: BTImpl<N, F>,
{
    /// Create a new BTFN from a support generator and a pre-initialised bisection tree.
    ///
    /// The bisection tree `bt` should be pre-initialised to correspond to the `generator`.
    /// Use [`Self::construct`] if no preinitialised tree is available. Use [`Self::new_refresh`]
    /// when the aggregators of the tree may need updates.
    ///
    /// See the documentation for [`BTFN`] on the role of the `generator`.
    pub fn new(bt: BT, generator: G) -> Self {
        Self::new_arc(bt, Arc::new(generator))
    }

    fn new_arc(bt: BT, generator: Arc<G>) -> Self {
        BTFN {
            bt: bt,
            generator: generator,
            _phantoms: std::marker::PhantomData,
        }
    }

    /// Create a new BTFN support generator and a pre-initialised bisection tree,
    /// cloning the tree and refreshing aggregators.
    ///
    /// The bisection tree `bt` should be pre-initialised to correspond to the `generator`, but
    /// the aggregator may be out of date.
    ///
    /// See the documentation for [`BTFN`] on the role of the `generator`.
    pub fn new_refresh(bt: &BT, generator: G) -> Self {
        // clone().refresh_aggregator(…) as opposed to convert_aggregator
        // ensures that type is maintained. Due to Rc-pointer copy-on-write,
        // the effort is not significantly different.
        let mut btnew = bt.clone();
        btnew.refresh_aggregator(&generator);
        BTFN::new(btnew, generator)
    }

    /// Create a new BTFN from a support generator, domain, and depth for a new [`BT`].
    ///
    /// The top node of the created [`BT`] will have the given `domain`.
    ///
    /// See the documentation for [`BTFN`] on the role of the `generator`.
    pub fn construct(domain: Cube<N, F>, depth: BT::Depth, generator: G) -> Self {
        Self::construct_arc(domain, depth, Arc::new(generator))
    }

    fn construct_arc(domain: Cube<N, F>, depth: BT::Depth, generator: Arc<G>) -> Self {
        let mut bt = BT::new(domain, depth);
        for (d, support) in generator.all_data() {
            bt.insert(d, &support);
        }
        Self::new_arc(bt, generator)
    }

    /// Convert the aggregator of the [`BTFN`] to a different one.
    ///
    /// This will construct a [`BTFN`] with the same components and generator as the (consumed)
    /// `self`, but a new `BT` with [`Aggregator`]s of type `ANew`.
    pub fn convert_aggregator<ANew>(self) -> BTFN<F, G, BT::Converted<ANew>, N>
    where
        ANew: Aggregator,
        G: SupportGenerator<N, F, Id = BT::Data>,
        G::SupportType: LocalAnalysis<F, ANew, N>,
    {
        BTFN::new_arc(self.bt.convert_aggregator(&*self.generator), self.generator)
    }

    /// Change the generator (after, e.g., a scaling of the latter).
    fn new_generator(&self, generator: G) -> Self {
        BTFN::new_refresh(&self.bt, generator)
    }

    /// Refresh aggregator after updates to generator
    fn refresh_aggregator(&mut self) {
        self.bt.refresh_aggregator(&*self.generator);
    }
}

impl<F: Float, G, BT, const N: usize> BTFN<F, G, BT, N>
where
    G: SupportGenerator<N, F>,
{
    /// Change the [bisection tree][BTImpl] of the [`BTFN`] to a different one.
    ///
    /// This can be used to convert a [`PreBTFN`] to a full [`BTFN`], or the change
    /// the aggreagator; see also [`self.convert_aggregator`].
    pub fn instantiate<BTNew: BTImpl<N, F, Data = G::Id>>(
        self,
        domain: Cube<N, F>,
        depth: BTNew::Depth,
    ) -> BTFN<F, G, BTNew, N>
    where
        G::SupportType: LocalAnalysis<F, BTNew::Agg, N>,
    {
        BTFN::construct_arc(domain, depth, self.generator)
    }
}

/// A BTFN with no bisection tree.
///
/// Most BTFN methods are not available, but if a BTFN is going to be summed with another
/// before other use, it will be more efficient to not construct an unnecessary bisection tree
/// that would be shortly dropped.
pub type PreBTFN<F, G, const N: usize> = BTFN<F, G, (), N>;

impl<F: Float, G, const N: usize> PreBTFN<F, G, N>
where
    G: SupportGenerator<N, F>,
{
    /// Create a new [`PreBTFN`] with no bisection tree.
    pub fn new_pre(generator: G) -> Self {
        BTFN {
            bt: (),
            generator: Arc::new(generator),
            _phantoms: std::marker::PhantomData,
        }
    }
}

impl<F: Float, G, BT, const N: usize> BTFN<F, G, BT, N>
where
    G: SupportGenerator<N, F, Id = usize>,
    G::SupportType: LocalAnalysis<F, BT::Agg, N>,
    BT: BTImpl<N, F, Data = usize>,
{
    /// Helper function for implementing [`std::ops::Add`].
    fn add_another<G2>(&self, g2: Arc<G2>) -> BTFN<F, BothGenerators<G, G2>, BT, N>
    where
        G2: SupportGenerator<N, F, Id = usize>,
        G2::SupportType: LocalAnalysis<F, BT::Agg, N>,
    {
        let mut bt = self.bt.clone();
        let both = BothGenerators(Arc::clone(&self.generator), g2);

        for (d, support) in both.all_right_data() {
            bt.insert(d, &support);
        }

        BTFN {
            bt: bt,
            generator: Arc::new(both),
            _phantoms: std::marker::PhantomData,
        }
    }
}

macro_rules! make_btfn_add {
    ($lhs:ty, $preprocess:path, $($extra_trait:ident)?) => {
        impl<'a, F : Float, G1, G2, BT1, BT2, const N : usize>
        std::ops::Add<BTFN<F, G2, BT2, N>> for
        $lhs
        where BT1 : BTImpl< N, F,  Data=usize>,
              G1 : SupportGenerator< N, F, Id=usize> + $($extra_trait)?,
              G2 : SupportGenerator< N, F, Id=usize>,
              G1::SupportType : LocalAnalysis<F, BT1::Agg, N>,
              G2::SupportType : LocalAnalysis<F, BT1::Agg, N> {
            type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>;
            #[inline]
            fn add(self, other : BTFN<F, G2, BT2, N>) -> Self::Output {
                $preprocess(self).add_another(other.generator)
            }
        }

        impl<'a, 'b, F : Float, G1, G2,  BT1, BT2, const N : usize>
        std::ops::Add<&'b BTFN<F, G2, BT2, N>> for
        $lhs
        where BT1 : BTImpl< N, F,  Data=usize>,
              G1 : SupportGenerator< N, F, Id=usize> + $($extra_trait)?,
              G2 : SupportGenerator< N, F, Id=usize>,
              G1::SupportType : LocalAnalysis<F, BT1::Agg, N>,
              G2::SupportType : LocalAnalysis<F, BT1::Agg, N> {

            type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>;
            #[inline]
            fn add(self, other : &'b BTFN<F, G2, BT2, N>) -> Self::Output {
                $preprocess(self).add_another(other.generator.clone())
            }
        }
    }
}

make_btfn_add!(BTFN<F, G1, BT1, N>, std::convert::identity, );
make_btfn_add!(&'a BTFN<F, G1, BT1, N>, Clone::clone,);

macro_rules! make_btfn_sub {
    ($lhs:ty, $preprocess:path, $($extra_trait:ident)?) => {
        impl<'a, F : Float, G1, G2, BT1, BT2, const N : usize>
        std::ops::Sub<BTFN<F, G2, BT2, N>> for
        $lhs
        where BT1 : BTImpl< N, F,  Data=usize>,
              G1 : SupportGenerator< N, F, Id=usize> + $($extra_trait)?,
              G2 : SupportGenerator< N, F, Id=usize>,
              G1::SupportType : LocalAnalysis<F, BT1::Agg, N>,
              G2::SupportType : LocalAnalysis<F, BT1::Agg, N> {
            type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>;
            #[inline]
            fn sub(self, other : BTFN<F, G2, BT2, N>) -> Self::Output {
                $preprocess(self).add_another(Arc::new(
                    Arc::try_unwrap(other.generator)
                        .unwrap_or_else(|arc| (*arc).clone())
                        .neg()
                ))
            }
        }

        impl<'a, 'b, F : Float, G1, G2,  BT1, BT2, const N : usize>
        std::ops::Sub<&'b BTFN<F, G2, BT2, N>> for
        $lhs
        where BT1 : BTImpl< N, F,  Data=usize>,
              G1 : SupportGenerator< N, F, Id=usize> + $($extra_trait)?,
              G2 : SupportGenerator< N, F, Id=usize> + Clone,
              G1::SupportType : LocalAnalysis<F, BT1::Agg, N>,
              G2::SupportType : LocalAnalysis<F, BT1::Agg, N>,
              &'b G2 : std::ops::Neg<Output=G2> {

            type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>;
            #[inline]
            fn sub(self, other : &'b BTFN<F, G2, BT2, N>) -> Self::Output {
                $preprocess(self).add_another(Arc::new((*other.generator).clone().neg()))
            }
        }
    }
}

make_btfn_sub!(BTFN<F, G1, BT1, N>, std::convert::identity, );
make_btfn_sub!(&'a BTFN<F, G1, BT1, N>, std::convert::identity,);

macro_rules! make_btfn_scalarop_rhs {
    ($trait:ident, $fn:ident, $trait_assign:ident, $fn_assign:ident) => {
        impl<F: Float, G, BT, const N: usize> std::ops::$trait_assign<F> for BTFN<F, G, BT, N>
        where
            BT: BTImpl<N, F>,
            G: SupportGenerator<N, F, Id = BT::Data>,
            G::SupportType: LocalAnalysis<F, BT::Agg, N>,
        {
            #[inline]
            fn $fn_assign(&mut self, t: F) {
                Arc::make_mut(&mut self.generator).$fn_assign(t);
                self.refresh_aggregator();
            }
        }

        impl<F: Float, G, BT, const N: usize> std::ops::$trait<F> for BTFN<F, G, BT, N>
        where
            BT: BTImpl<N, F>,
            G: SupportGenerator<N, F, Id = BT::Data>,
            G::SupportType: LocalAnalysis<F, BT::Agg, N>,
        {
            type Output = Self;
            #[inline]
            fn $fn(mut self, t: F) -> Self::Output {
                Arc::make_mut(&mut self.generator).$fn_assign(t);
                self.refresh_aggregator();
                self
            }
        }

        impl<'a, F: Float, G, BT, const N: usize> std::ops::$trait<F> for &'a BTFN<F, G, BT, N>
        where
            BT: BTImpl<N, F>,
            G: SupportGenerator<N, F, Id = BT::Data>,
            G::SupportType: LocalAnalysis<F, BT::Agg, N>,
            &'a G: std::ops::$trait<F, Output = G>,
        {
            type Output = BTFN<F, G, BT, N>;
            #[inline]
            fn $fn(self, t: F) -> Self::Output {
                self.new_generator(self.generator.$fn(t))
            }
        }
    };
}

make_btfn_scalarop_rhs!(Mul, mul, MulAssign, mul_assign);
make_btfn_scalarop_rhs!(Div, div, DivAssign, div_assign);

macro_rules! make_btfn_scalarop_lhs {
    ($trait:ident, $fn:ident, $fn_assign:ident, $($f:ident)+) => { $(
        impl<G, BT, const N : usize>
        std::ops::$trait<BTFN<$f, G, BT, N>>
        for $f
        where BT : BTImpl< N, $f>,
              G : SupportGenerator< N, $f, Id=BT::Data>,
              G::SupportType : LocalAnalysis<$f, BT::Agg, N> {
            type Output = BTFN<$f, G, BT, N>;
            #[inline]
            fn $fn(self, mut a : BTFN<$f, G, BT, N>) -> Self::Output {
                Arc::make_mut(&mut a.generator).$fn_assign(self);
                a.refresh_aggregator();
                a
            }
        }

        impl<'a, G, BT, const N : usize>
        std::ops::$trait<&'a BTFN<$f, G, BT, N>>
        for $f
        where BT : BTImpl< N, $f>,
              G : SupportGenerator< N, $f, Id=BT::Data> + Clone,
              G::SupportType : LocalAnalysis<$f, BT::Agg, N>,
              // FIXME: This causes compiler overflow
              /*&'a G : std::ops::$trait<$f,Output=G>*/ {
            type Output = BTFN<$f, G, BT, N>;
            #[inline]
            fn $fn(self, a : &'a BTFN<$f, G, BT, N>) -> Self::Output {
                let mut tmp = (*a.generator).clone();
                tmp.$fn_assign(self);
                a.new_generator(tmp)
                // FIXME: Prevented by the compiler overflow above.
                //a.new_generator(a.generator.$fn(a))
            }
        }
    )+ }
}

make_btfn_scalarop_lhs!(Mul, mul, mul_assign, f32 f64);
make_btfn_scalarop_lhs!(Div, div, div_assign, f32 f64);

macro_rules! make_btfn_unaryop {
    ($trait:ident, $fn:ident) => {
        impl<F: Float, G, BT, const N: usize> std::ops::$trait for BTFN<F, G, BT, N>
        where
            BT: BTImpl<N, F>,
            G: SupportGenerator<N, F, Id = BT::Data>,
            G::SupportType: LocalAnalysis<F, BT::Agg, N>,
        {
            type Output = Self;
            #[inline]
            fn $fn(mut self) -> Self::Output {
                self.generator = Arc::new(Arc::unwrap_or_clone(self.generator).$fn());
                self.refresh_aggregator();
                self
            }
        }

        /*impl<'a, F : Float, G, BT, const N : usize>
        std::ops::$trait
        for &'a BTFN<F, G, BT, N>
        where BT : BTImpl< N, F>,
              G : SupportGenerator< N, F, Id=BT::Data>,
              G::SupportType : LocalAnalysis<F, BT::Agg, N>,
              &'a G : std::ops::$trait<Output=G> {
            type Output = BTFN<F, G, BT, N>;
            #[inline]
            fn $fn(self) -> Self::Output {
                self.new_generator(std::ops::$trait::$fn(&self.generator))
            }
        }*/
    };
}

make_btfn_unaryop!(Neg, neg);

//
// Apply, Mapping, Differentiate
//

impl<F: Float, G, BT, V, const N: usize> Mapping<Loc<N, F>> for BTFN<F, G, BT, N>
where
    BT: BTImpl<N, F>,
    G: SupportGenerator<N, F, Id = BT::Data>,
    G::SupportType: LocalAnalysis<F, BT::Agg, N> + Mapping<Loc<N, F>, Codomain = V>,
    V: Sum + Space,
{
    type Codomain = V;

    fn apply<I: Instance<Loc<N, F>>>(&self, x: I) -> Self::Codomain {
        let xc = x.cow();
        self.bt
            .iter_at(&*xc)
            .map(|&d| self.generator.support_for(d).apply(&*xc))
            .sum()
    }
}

impl<F: Float, G, BT, V, const N: usize> DifferentiableImpl<Loc<N, F>> for BTFN<F, G, BT, N>
where
    BT: BTImpl<N, F>,
    G: SupportGenerator<N, F, Id = BT::Data>,
    G::SupportType:
        LocalAnalysis<F, BT::Agg, N> + DifferentiableMapping<Loc<N, F>, DerivativeDomain = V>,
    V: Sum + Space,
{
    type Derivative = V;

    fn differential_impl<I: Instance<Loc<N, F>>>(&self, x: I) -> Self::Derivative {
        let xc = x.cow();
        self.bt
            .iter_at(&*xc)
            .map(|&d| self.generator.support_for(d).differential(&*xc))
            .sum()
    }
}

//
// GlobalAnalysis
//

impl<F: Float, G, BT, const N: usize> GlobalAnalysis<F, BT::Agg> for BTFN<F, G, BT, N>
where
    BT: BTImpl<N, F>,
    G: SupportGenerator<N, F, Id = BT::Data>,
    G::SupportType: LocalAnalysis<F, BT::Agg, N>,
{
    #[inline]
    fn global_analysis(&self) -> BT::Agg {
        self.bt.global_analysis()
    }
}

//
// Blanket implementation of BTFN as a linear functional over objects
// that are linear functionals over BTFN.
//

/*
impl<'b, X, F : Float, G, BT, const N : usize> Apply<&'b X, F>
for BTFN<F, G, BT, N>
where BT : BTImpl< N, F>,
      G : SupportGenerator< N, F, Id=BT::Data>,
      G::SupportType : LocalAnalysis<F, BT::Agg, N>,
      X : for<'a> Apply<&'a BTFN<F, G, BT, N>, F> {

    #[inline]
    fn apply(&self, x : &'b X) -> F {
        x.apply(&self)
    }
}

impl<X, F : Float, G, BT, const N : usize> Apply<X, F>
for BTFN<F, G, BT, N>
where BT : BTImpl< N, F>,
      G : SupportGenerator< N, F, Id=BT::Data>,
      G::SupportType : LocalAnalysis<F, BT::Agg, N>,
      X : for<'a> Apply<&'a BTFN<F, G, BT, N>, F> {

    #[inline]
    fn apply(&self, x : X) -> F {
        x.apply(&self)
    }
}

impl<X, F : Float, G, BT, const N : usize> Linear<X>
for BTFN<F, G, BT, N>
where BT : BTImpl< N, F>,
      G : SupportGenerator< N, F, Id=BT::Data>,
      G::SupportType : LocalAnalysis<F, BT::Agg, N>,
      X : for<'a> Apply<&'a BTFN<F, G, BT, N>, F> {
    type Codomain = F;
}
*/

/// Helper trait for performing approximate minimisation using P2 elements.
///
/// `U` is the domain, generally [`Loc`]`<F, N>`, and `F` the type of floating point numbers.
/// `Self` is generally a set of `U`, for example, [`Cube`]`<F, N>`.
pub trait P2Minimise<U: Space, F: Float>: Set<U> {
    /// Minimise `g` over the set presented by `Self`.
    ///
    /// The function returns `(x, v)` where `x` is the minimiser `v` an approximation of `g(x)`.
    fn p2_minimise<G: Fn(&U) -> F>(&self, g: G) -> (U, F);
}

impl<F: Float> P2Minimise<Loc<1, F>, F> for Cube<1, F> {
    fn p2_minimise<G: Fn(&Loc<1, F>) -> F>(&self, g: G) -> (Loc<1, F>, F) {
        let interval = Simplex(self.corners());
        interval.p2_model(&g).minimise(&interval)
    }
}

#[replace_float_literals(F::cast_from(literal))]
impl<F: Float> P2Minimise<Loc<2, F>, F> for Cube<2, F> {
    fn p2_minimise<G: Fn(&Loc<2, F>) -> F>(&self, g: G) -> (Loc<2, F>, F) {
        if false {
            // Split into two triangle (simplex) with separate P2 model in each.
            // The six nodes of each triangle are the corners and the edges.
            let [a, b, c, d] = self.corners();
            let [va, vb, vc, vd] = [g(&a), g(&b), g(&c), g(&d)];

            let ab = midpoint(&a, &b);
            let bc = midpoint(&b, &c);
            let ca = midpoint(&c, &a);
            let cd = midpoint(&c, &d);
            let da = midpoint(&d, &a);
            let [vab, vbc, vca, vcd, vda] = [g(&ab), g(&bc), g(&ca), g(&cd), g(&da)];

            let s1 = Simplex([a, b, c]);
            let m1 =
                P2LocalModel::<F, 2, 3>::new(&[a, b, c, ab, bc, ca], &[va, vb, vc, vab, vbc, vca]);

            let r1 @ (_, v1) = m1.minimise(&s1);

            let s2 = Simplex([c, d, a]);
            let m2 =
                P2LocalModel::<F, 2, 3>::new(&[c, d, a, cd, da, ca], &[vc, vd, va, vcd, vda, vca]);

            let r2 @ (_, v2) = m2.minimise(&s2);

            if v1 < v2 {
                r1
            } else {
                r2
            }
        } else {
            // Single P2 model for the entire cube.
            let [a, b, c, d] = self.corners();
            let [va, vb, vc, vd] = [g(&a), g(&b), g(&c), g(&d)];
            let [e, f] = match 'r' {
                'm' => [(&a + &b + &c) / 3.0, (&c + &d + &a) / 3.0],
                'c' => [midpoint(&a, &b), midpoint(&a, &d)],
                'w' => [(&a + &b * 2.0) / 3.0, (&a + &d * 2.0) / 3.0],
                'r' => {
                    // Pseudo-randomise edge midpoints
                    let Loc([x, y]) = a;
                    let tmp: f64 = (x + y).as_();
                    match tmp.to_bits() % 4 {
                        0 => [midpoint(&a, &b), midpoint(&a, &d)],
                        1 => [midpoint(&c, &d), midpoint(&a, &d)],
                        2 => [midpoint(&a, &b), midpoint(&b, &c)],
                        _ => [midpoint(&c, &d), midpoint(&b, &c)],
                    }
                }
                _ => [self.center(), (&a + &b) / 2.0],
            };
            let [ve, vf] = [g(&e), g(&f)];

            let m1 = P2LocalModel::<F, 2, 3>::new(&[a, b, c, d, e, f], &[va, vb, vc, vd, ve, vf]);

            m1.minimise(self)
        }
    }
}

/// Helper type to use [`P2Refiner`] for maximisation.
struct RefineMax;

/// Helper type to use [`P2Refiner`] for minimisation.
struct RefineMin;

/// A bisection tree [`Refiner`] for maximising or minimising a [`BTFN`].
///
/// The type parameter `T` should be either [`RefineMax`] or [`RefineMin`].
struct P2Refiner<F: Float, T> {
    /// The maximum / minimum should be above / below this threshold.
    /// If the threshold cannot be satisfied, the refiner will return `None`.
    bound: Option<F>,
    /// Tolerance for function value estimation.
    tolerance: F,
    /// Maximum number of steps to execute the refiner for
    max_steps: usize,
    /// Either [`RefineMax`] or [`RefineMin`]. Used only for type system purposes.
    #[allow(dead_code)] // `how` is just for type system purposes.
    how: T,
}

impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for P2Refiner<F, RefineMax>
where
    Cube<N, F>: P2Minimise<Loc<N, F>, F>,
    G: SupportGenerator<N, F>,
    G::SupportType: Mapping<Loc<N, F>, Codomain = F> + LocalAnalysis<F, Bounds<F>, N>,
{
    type Result = Option<(Loc<N, F>, F)>;
    type Sorting = UpperBoundSorting<F>;

    fn refine(
        &self,
        aggregator: &Bounds<F>,
        cube: &Cube<N, F>,
        data: &[G::Id],
        generator: &G,
        step: usize,
    ) -> RefinerResult<Bounds<F>, Self::Result> {
        if self
            .bound
            .map_or(false, |b| aggregator.upper() <= b + self.tolerance)
        {
            // The upper bound is below the maximisation threshold. Don't bother with this cube.
            return RefinerResult::Uncertain(*aggregator, None);
        }

        // g gives the negative of the value of the function presented by `data` and `generator`.
        let g = move |x: &Loc<N, F>| {
            let f = move |&d| generator.support_for(d).apply(x);
            -data.iter().map(f).sum::<F>()
        };
        // … so the negative of the minimum is the maximm we want.
        let (x, _neg_v) = cube.p2_minimise(g);
        //let v = -neg_v;
        let v = -g(&x);

        if step < self.max_steps
            && (aggregator.upper() > v + self.tolerance/*|| aggregator.lower() > v - self.tolerance*/)
        {
            // The function isn't refined enough in `cube`, so return None
            // to indicate that further subdivision is required.
            RefinerResult::NeedRefinement
        } else {
            // The data is refined enough, so return new hopefully better bounds
            // and the maximiser.
            let res = (x, v);
            let bounds = Bounds(v, v);
            RefinerResult::Uncertain(bounds, Some(res))
        }
    }

    fn fuse_results(r1: &mut Self::Result, r2: Self::Result) {
        match (*r1, r2) {
            (Some((_, v1)), Some((_, v2))) => {
                if v1 < v2 {
                    *r1 = r2
                }
            }
            (None, Some(_)) => *r1 = r2,
            (_, _) => {}
        }
    }
}

impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for P2Refiner<F, RefineMin>
where
    Cube<N, F>: P2Minimise<Loc<N, F>, F>,
    G: SupportGenerator<N, F>,
    G::SupportType: Mapping<Loc<N, F>, Codomain = F> + LocalAnalysis<F, Bounds<F>, N>,
{
    type Result = Option<(Loc<N, F>, F)>;
    type Sorting = LowerBoundSorting<F>;

    fn refine(
        &self,
        aggregator: &Bounds<F>,
        cube: &Cube<N, F>,
        data: &[G::Id],
        generator: &G,
        step: usize,
    ) -> RefinerResult<Bounds<F>, Self::Result> {
        if self
            .bound
            .map_or(false, |b| aggregator.lower() >= b - self.tolerance)
        {
            // The lower bound is above the minimisation threshold. Don't bother with this cube.
            return RefinerResult::Uncertain(*aggregator, None);
        }

        // g gives the value of the function presented by `data` and `generator`.
        let g = move |x: &Loc<N, F>| {
            let f = move |&d| generator.support_for(d).apply(x);
            data.iter().map(f).sum::<F>()
        };
        // Minimise it.
        let (x, _v) = cube.p2_minimise(g);
        let v = g(&x);

        if step < self.max_steps
            && (aggregator.lower() < v - self.tolerance/*|| aggregator.upper() < v + self.tolerance*/)
        {
            // The function isn't refined enough in `cube`, so return None
            // to indicate that further subdivision is required.
            RefinerResult::NeedRefinement
        } else {
            // The data is refined enough, so return new hopefully better bounds
            // and the minimiser.
            let res = (x, v);
            let l = aggregator.lower();
            let bounds = if l > v {
                eprintln!("imprecision!");
                Bounds(l, l)
            } else {
                Bounds(v, v)
            };
            RefinerResult::Uncertain(bounds, Some(res))
        }
    }

    fn fuse_results(r1: &mut Self::Result, r2: Self::Result) {
        match (*r1, r2) {
            (Some((_, v1)), Some((_, v2))) => {
                if v1 > v2 {
                    *r1 = r2
                }
            }
            (_, Some(_)) => *r1 = r2,
            (_, _) => {}
        }
    }
}

/// A bisection tree [`Refiner`] for checking that a [`BTFN`] is within a stated
//// upper or lower bound.
///
/// The type parameter `T` should be either [`RefineMax`] for upper bound or [`RefineMin`]
/// for lower bound.

struct BoundRefiner<F: Float, T> {
    /// The upper/lower bound to check for
    bound: F,
    /// Tolerance for function value estimation.
    tolerance: F,
    /// Maximum number of steps to execute the refiner for
    max_steps: usize,
    #[allow(dead_code)] // `how` is just for type system purposes.
    /// Either [`RefineMax`] or [`RefineMin`]. Used only for type system purposes.
    how: T,
}

impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for BoundRefiner<F, RefineMax>
where
    G: SupportGenerator<N, F>,
{
    type Result = bool;
    type Sorting = UpperBoundSorting<F>;

    fn refine(
        &self,
        aggregator: &Bounds<F>,
        _cube: &Cube<N, F>,
        _data: &[G::Id],
        _generator: &G,
        step: usize,
    ) -> RefinerResult<Bounds<F>, Self::Result> {
        if aggregator.upper() <= self.bound + self.tolerance {
            // Below upper bound within tolerances. Indicate uncertain success.
            RefinerResult::Uncertain(*aggregator, true)
        } else if aggregator.lower() >= self.bound - self.tolerance {
            // Above upper bound within tolerances. Indicate certain failure.
            RefinerResult::Certain(false)
        } else if step < self.max_steps {
            // No decision possible, but within step bounds - further subdivision is required.
            RefinerResult::NeedRefinement
        } else {
            // No decision possible, but past step bounds
            RefinerResult::Uncertain(*aggregator, false)
        }
    }

    fn fuse_results(r1: &mut Self::Result, r2: Self::Result) {
        *r1 = *r1 && r2;
    }
}

impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for BoundRefiner<F, RefineMin>
where
    G: SupportGenerator<N, F>,
{
    type Result = bool;
    type Sorting = UpperBoundSorting<F>;

    fn refine(
        &self,
        aggregator: &Bounds<F>,
        _cube: &Cube<N, F>,
        _data: &[G::Id],
        _generator: &G,
        step: usize,
    ) -> RefinerResult<Bounds<F>, Self::Result> {
        if aggregator.lower() >= self.bound - self.tolerance {
            // Above lower bound within tolerances. Indicate uncertain success.
            RefinerResult::Uncertain(*aggregator, true)
        } else if aggregator.upper() <= self.bound + self.tolerance {
            // Below lower bound within tolerances. Indicate certain failure.
            RefinerResult::Certain(false)
        } else if step < self.max_steps {
            // No decision possible, but within step bounds - further subdivision is required.
            RefinerResult::NeedRefinement
        } else {
            // No decision possible, but past step bounds
            RefinerResult::Uncertain(*aggregator, false)
        }
    }

    fn fuse_results(r1: &mut Self::Result, r2: Self::Result) {
        *r1 = *r1 && r2;
    }
}

// FIXME: The most likely reason for the “Refiner failure” expectation in the methods below
// is numerical inaccuracy: the `glb` maintained in `HeapContainer` (`refine.rs`) becomes bigger
// than the *upper bound* of nodes attempted to be inserted into the `heap` in the container.
// But the `glb` is there exactly to prevent that. Due to numerical inaccuracy, however, a
// newly subdivided node may have lower upper bound than the original lower bound that should
// have been above the `glb` since the node was picked from the queue. Due to the subdivision
// process, if a node whose lower bound is at the `glb` is picked, all of its refined subnodes
// should have lower bound at least the old `glb`, so in a single-threaded situation there should
// always be nodes above the `glb` in the queue. In a multi-threaded situation a node below the
// `glb` may be picked by some thread. When that happens, that thread inserts no new nodes into
// the queue. If the queue empties as a result of that, the thread goes to wait for other threads
// to produce results. Since some node had a node whose lower bound was above the `glb`, eventually
// there should be a result, or new nodes above the `glb` inserted into the queue. Then the waiting
// threads can also continue processing. If, however, numerical inaccuracy destroyes the `glb`,
// the queue may run out, and we get “Refiner failure”.
impl<F: Float, G, BT, const N: usize> MinMaxMapping<N, F> for BTFN<F, G, BT, N>
where
    BT: BTSearch<N, F, Agg = Bounds<F>>,
    G: SupportGenerator<N, F, Id = BT::Data>,
    G::SupportType: Mapping<Loc<N, F>, Codomain = F> + LocalAnalysis<F, Bounds<F>, N>,
    Cube<N, F>: P2Minimise<Loc<N, F>, F>,
{
    fn maximise(&mut self, tolerance: F, max_steps: usize) -> (Loc<N, F>, F) {
        let refiner = P2Refiner {
            tolerance,
            max_steps,
            how: RefineMax,
            bound: None,
        };
        self.bt
            .search_and_refine(refiner, &self.generator)
            .expect("Refiner failure.")
            .unwrap()
    }

    fn maximise_above(
        &mut self,
        bound: F,
        tolerance: F,
        max_steps: usize,
    ) -> Option<(Loc<N, F>, F)> {
        let refiner = P2Refiner {
            tolerance,
            max_steps,
            how: RefineMax,
            bound: Some(bound),
        };
        self.bt
            .search_and_refine(refiner, &self.generator)
            .expect("Refiner failure.")
    }

    fn minimise(&mut self, tolerance: F, max_steps: usize) -> (Loc<N, F>, F) {
        let refiner = P2Refiner {
            tolerance,
            max_steps,
            how: RefineMin,
            bound: None,
        };
        self.bt
            .search_and_refine(refiner, &self.generator)
            .expect("Refiner failure.")
            .unwrap()
    }

    fn minimise_below(
        &mut self,
        bound: F,
        tolerance: F,
        max_steps: usize,
    ) -> Option<(Loc<N, F>, F)> {
        let refiner = P2Refiner {
            tolerance,
            max_steps,
            how: RefineMin,
            bound: Some(bound),
        };
        self.bt
            .search_and_refine(refiner, &self.generator)
            .expect("Refiner failure.")
    }

    fn has_upper_bound(&mut self, bound: F, tolerance: F, max_steps: usize) -> bool {
        let refiner = BoundRefiner {
            bound,
            tolerance,
            max_steps,
            how: RefineMax,
        };
        self.bt
            .search_and_refine(refiner, &self.generator)
            .expect("Refiner failure.")
    }

    fn has_lower_bound(&mut self, bound: F, tolerance: F, max_steps: usize) -> bool {
        let refiner = BoundRefiner {
            bound,
            tolerance,
            max_steps,
            how: RefineMin,
        };
        self.bt
            .search_and_refine(refiner, &self.generator)
            .expect("Refiner failure.")
    }
}