use std::borrow::Borrow;
use std::collections::BTreeSet;
use std::fmt::Debug;
use std::hash::Hash;
use num_traits::Float;
use crate::binary_search_interval;
use crate::multispline::MultiSpline;
#[derive(Debug, Clone)]
pub struct SearchNode<T>
where
T: Float + Debug,
{
interval: [usize; 2],
children: [usize; 2],
parent: usize,
minmaxs: Vec<[T; 2]>,
}
impl<T: Float + Debug> SearchNode<T> {
pub fn root<K: Eq + Hash>(pps: &MultiSpline<K, T>) -> Self {
let first: usize = 0;
let last: usize = pps.len() - 1;
let mut minmaxs: Vec<[T; 2]> = Vec::new();
for k in 0..pps.number_variables() {
let first_val = pps.get_break_for_index_by_idx(k, first).unwrap();
let last_val = pps.get_break_for_index_by_idx(k, last).unwrap();
minmaxs.push([T::min(first_val, last_val), T::max(first_val, last_val)]);
}
Self {
interval: [first, last],
children: [0; 2],
parent: 0,
minmaxs,
}
}
pub fn null<K: Eq + Hash>(pps: &MultiSpline<K, T>) -> Self {
let mut minmaxs: Vec<[T; 2]> = Vec::new();
for _ in 0..pps.number_variables() {
minmaxs.push([T::zero(); 2]);
}
Self {
interval: [0; 2],
children: [0; 2],
parent: 0,
minmaxs,
}
}
}
#[derive(Debug)]
pub struct SearchTree<'a, K, T>
where
T: Float + Debug,
K: Eq + Hash,
{
pub nodes: Vec<SearchNode<T>>,
pub pps: &'a MultiSpline<K, T>,
}
impl<'a, K, T> SearchTree<'a, K, T>
where
T: Float + Debug,
K: Eq + Hash,
{
pub fn new(pps: &'a MultiSpline<K, T>) -> Self {
let mut tree = Self {
nodes: vec![SearchNode::null(pps), SearchNode::root(pps)],
pps,
};
let extrema = tree.search_extrema_linear();
for extrema_item in &extrema {
tree.split_node_at(1, extrema_item.0);
}
tree
}
pub fn search_extrema_linear(&self) -> Vec<(usize, usize)> {
let mut previous: Vec<T> = vec![T::zero(); self.nodes[1].minmaxs.len()];
let mut indices: Vec<usize> = vec![0usize; self.nodes[1].minmaxs.len()];
let mut setprev: Vec<bool> = vec![false; self.nodes[1].minmaxs.len()];
let mut increasing: Vec<bool> = vec![false; self.nodes[1].minmaxs.len()];
let mut res: Vec<(usize, usize)> = Vec::new();
for k in 0..self.pps.len() {
for m in 0..indices.len() {
let brk = self.pps.get_break_for_index_by_idx(m, k).unwrap();
if k == 0 {
previous[m] = brk;
continue;
}
if brk < previous[m] {
if k >= 2 && increasing[m] {
res.push((k - 1, m));
}
indices[m] = k;
previous[m] = brk;
increasing[m] = false;
setprev[m] = true;
} else {
if k >= 2 && !increasing[m] {
res.push((k - 1, m));
}
indices[m] = k;
previous[m] = brk;
increasing[m] = true;
setprev[m] = true;
}
}
}
res
}
pub fn split_node_at(&mut self, nindex: usize, new_index: usize) -> Option<(usize, usize)> {
if new_index <= self.nodes[nindex].interval[0]
|| new_index >= self.nodes[nindex].interval[1]
{
return None;
}
if self.nodes[nindex].children[0] > 0 {
if let Some(res) = self.split_node_at(self.nodes[nindex].children[0], new_index) {
return Some(res);
}
{
let res = self.split_node_at(self.nodes[nindex].children[1], new_index)?;
return Some(res);
}
}
let left = self.nodes[nindex].clone();
let right = self.nodes[nindex].clone();
let idx_left = self.nodes.len();
let idx_right = self.nodes.len() + 1;
self.nodes.push(left);
self.nodes.push(right);
self.nodes[nindex].children = [idx_left, idx_right];
self.nodes[idx_left].parent = nindex;
self.nodes[idx_right].parent = nindex;
for m in 0..self.nodes[nindex].minmaxs.len() {
let interval_left = self.nodes[nindex].interval[0];
let interval_right = self.nodes[nindex].interval[1];
let value_left = self
.pps
.get_break_for_index_by_idx(m, interval_left)
.unwrap();
let value_right = self
.pps
.get_break_for_index_by_idx(m, interval_right)
.unwrap();
let value_middle = self.pps.get_break_for_index_by_idx(m, new_index).unwrap();
self.nodes[idx_left].minmaxs[m] = [
T::min(value_left, value_middle),
T::max(value_left, value_middle),
];
self.nodes[idx_right].minmaxs[m] = [
T::min(value_middle, value_right),
T::max(value_middle, value_right),
];
}
self.nodes[idx_left].interval = [self.nodes[nindex].interval[0], new_index];
self.nodes[idx_right].interval = [new_index, self.nodes[nindex].interval[1]];
self.update_parent(idx_left);
self.update_parent(idx_right);
Some((idx_left, idx_right))
}
fn update_parent(&mut self, nindex: usize) {
if nindex == 0 {
return;
}
let parent = self.nodes[nindex].parent;
if parent == 0 {
return;
}
for k in 0..self.nodes[nindex].minmaxs.len() {
if self.nodes[nindex].minmaxs[k][0] < self.nodes[parent].minmaxs[k][0] {
self.nodes[parent].minmaxs[k][0] = self.nodes[nindex].minmaxs[k][0];
}
if self.nodes[nindex].minmaxs[k][1] > self.nodes[parent].minmaxs[k][1] {
self.nodes[parent].minmaxs[k][1] = self.nodes[nindex].minmaxs[k][1];
}
}
}
pub fn interval_indices<Q>(&self, key: &Q, _x: &T) -> Vec<T>
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized,
{
match self.pps.keys.get(key) {
None => Vec::new(),
Some(None) => {
todo!();
}
Some(Some(_idx)) => {
todo!();
}
}
}
pub fn interval_indices_by_idx(&self, idx: usize, x: &T) -> BTreeSet<usize> {
let mut res: BTreeSet<usize> = BTreeSet::new();
self.interval_indices_by_idx_(idx, x, &mut res, 1);
res
}
fn interval_indices_by_idx_(&self, idx: usize, x: &T, res: &mut BTreeSet<usize>, index: usize) {
if *x < self.nodes[index].minmaxs[idx][0] || *x > self.nodes[index].minmaxs[idx][1] {
return;
}
if self.nodes[index].children[0] > 0 {
self.interval_indices_by_idx_(idx, x, res, self.nodes[index].children[0]);
self.interval_indices_by_idx_(idx, x, res, self.nodes[index].children[1]);
return;
}
if let Some(ix) = self.binary_search_monotonic_by_idx(
idx,
x,
self.nodes[index].interval[0],
self.nodes[index].interval[1],
) {
res.insert(ix);
}
}
fn binary_search_monotonic_by_idx(
&self,
idx: usize,
x: &T,
index0: usize,
index1: usize,
) -> Option<usize> {
binary_search_interval(index1 - index0 + 1, x, |ix| {
self.pps.pps[idx].0.breaks_x[ix + index0]
})
.map(|idx| idx + index0)
}
fn binary_search_monotonic_principal(
&self,
x: &T,
index0: usize,
index1: usize,
) -> Option<usize> {
binary_search_interval(index1 - index0 + 1, x, |ix| self.pps.tt[ix + index0])
.map(|idx| idx + index0)
}
pub fn interpolate<Q>(&self, keyx: &Q, keyy: &Q, x: &T) -> Vec<T>
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized,
{
match (self.pps.keys.get(keyx), self.pps.keys.get(keyy)) {
(None, _) | (_, None) => Vec::new(),
(Some(None), Some(Some(idx))) => {
match self.binary_search_monotonic_principal(
x,
self.nodes[1].interval[0],
self.nodes[1].interval[1],
) {
Some(index) => {
vec![self
.pps
.interpolate_for_index_by_pc2idx(*idx, x, index)
.unwrap()]
}
None => {
vec![]
}
}
}
(Some(Some(idx)), Some(None)) => {
let indices = self.interval_indices_by_idx(*idx, x);
let mut res: Vec<T> = Vec::new();
for index in indices.into_iter() {
res.push(
self.pps
.interpolate_for_index_by_idx2pc(*idx, x, index)
.unwrap(),
);
}
res
}
(Some(Some(idx0)), Some(Some(idx1))) => {
let indices = self.interval_indices_by_idx(*idx0, x);
let mut res: Vec<T> = Vec::new();
for index in indices.into_iter() {
let t = self
.pps
.interpolate_for_index_by_idx2pc(*idx0, x, index)
.unwrap();
res.push(
self.pps
.interpolate_for_index_by_pc2idx(*idx1, &t, index)
.unwrap(),
);
}
res
}
(Some(None), Some(None)) => {
vec![*x]
}
}
}
}