use az::{Az, Cast};
use log::*;
use std::error::Error;
use std::f64::consts::FRAC_1_SQRT_2;
use std::fs::File;
use std::io::Write;
use std::num::NonZero;
use std::path::Path;
use kiddo_v6::{Manhattan, SquaredEuclidean};
use crate::dynamic_index::star_index_container::{DistanceMetric, KdTree};
use crate::structs_f64::{
quad::{PotentialQuad, Quad, QuadCode},
star::Star,
};
use crate::structs_generic::{Flt, Idx};
use memmap::MmapOptions;
use rkyv_08::{
from_bytes_unchecked, rancor::Error as RkyvError, to_bytes, Archive, Deserialize, Serialize,
};
const MAX_AB_USE: usize = 10;
const MAX_TOTAL_REUSE: usize = 80; const MAX_AB_SHRINK_FACTOR: f64 = FRAC_1_SQRT_2;
const MAX_AB2_MIN_AB2_RATIO: f64 = FRAC_1_SQRT_2;
const MIN_AC_MIN_AB_RATIO: f64 = 0.01f64;
const INITIAL_MAX_AB_DEGREES: f64 = 45f64;
const TERMINAL_MIN_AB_DEGREES: f64 = 3f64;
type SIDX = u32; type QIDX = u32; type FLT = f64;
pub type StarKdTree = kiddo_v6::ImmutableKdTree<FLT, 3>;
pub type QuadKdTree = kiddo_v6::ImmutableKdTree<FLT, 4>;
pub struct BestNeighbour<F: Flt, I: Idx> {
pub distance: F,
pub item: I,
}
pub struct NearestNeighbour<F: Flt, I: Idx> {
pub distance: F,
pub item: I,
}
impl<F: Flt + az::Cast<F2>, I: Idx + az::Cast<I2>, F2: Flt, I2: Idx>
From<kiddo_v6::QueryResultItem<(), F, I>> for NearestNeighbour<F2, I2>
where
F: Cast<I2>,
F2: Cast<I2>,
I: Cast<F2>
{
fn from(nn: kiddo_v6::QueryResultItem<(), F, I>) -> Self {
NearestNeighbour {
item: nn.item.az::<I2>(),
distance: nn.distance.az::<F2>(),
}
}
}
impl<F: Flt + az::Cast<F2>, I: Idx + az::Cast<I2>, F2: Flt, I2: Idx>
From<kiddo_v6::QueryResultItem<(), F, I>> for BestNeighbour<F2, I2>
where
F: Cast<I2>,
F2: Cast<I2>,
I: Cast<F2>
{
fn from(bn: kiddo_v6::QueryResultItem<(), F, I>) -> Self {
BestNeighbour {
item: bn.item.az::<I2>(),
distance: bn.distance.az::<F2>(),
}
}
}
pub trait StarIndexTrait<F: Flt> {
fn best_n_stars_within(
&self,
query: [F; 3],
radius: F,
max_qty: NonZero<usize>,
) -> impl Iterator<Item = BestNeighbour<F, u32>>;
fn get_star(&self, index: SIDX) -> ⋆
fn get_quad(&self, index: QIDX) -> &Quad;
fn stars_within_radius(&self, query: &[F; 3], radius: F) -> Vec<NearestNeighbour<F, SIDX>>;
fn quad_codes_within_radius(&self, query: &[F; 4], radius: F)
-> Vec<NearestNeighbour<F, SIDX>>;
}
impl StarIndexTrait<f64> for StarIndex {
fn best_n_stars_within(
&self,
query: [f64; 3],
radius: f64,
max_qty: NonZero<usize>,
) -> impl Iterator<Item = BestNeighbour<f64, SIDX>> {
self.kd_stars
.query(&(f64::conv3::<f64, f64>(&query)))
.best_n_within::<SquaredEuclidean<f64>>(
radius.az::<f64>(),
max_qty,
)
.execute()
.into_iter()
.map(|nn| BestNeighbour {
distance: nn.distance.az::<f64>(),
item: nn.item.az::<SIDX>(),
})
}
fn get_star(&self, index: SIDX) -> &Star {
&self.stars[index as usize]
}
fn get_quad(&self, index: QIDX) -> &Quad {
&self.quads[index as usize]
}
fn stars_within_radius(
&self,
query: &[f64; 3],
radius: f64,
) -> Vec<NearestNeighbour<f64, SIDX>> {
self.kd_stars
.query(&(f64::conv3::<f64, f64>(query)))
.within::<SquaredEuclidean<f64>>(radius.az::<f64>())
.execute()
.into_iter()
.map(|nn| NearestNeighbour {
distance: nn.distance.az::<f64>(),
item: nn.item.az::<SIDX>(),
})
.collect()
}
fn quad_codes_within_radius(
&self,
query: &[f64; 4],
radius: f64,
) -> Vec<NearestNeighbour<f64, SIDX>> {
self.kd_codes
.query(&(f64::conv4::<f64, f64>(query)))
.within::<Manhattan<f64>>(radius.az::<f64>())
.execute()
.into_iter()
.map(|nn| NearestNeighbour {
distance: nn.distance.az::<f64>(),
item: nn.item.az::<SIDX>(),
})
.collect()
}
}
pub struct DynStarIndex {
stars: Vec<Star>,
kd_stars: Box<dyn KdTree<3>>,
quads: Vec<Quad>,
kd_codes: Box<dyn KdTree<4>>,
}
impl StarIndexTrait<f64> for DynStarIndex {
fn best_n_stars_within(
&self,
query: [f64; 3],
radius: f64,
max_qty: NonZero<usize>,
) -> impl Iterator<Item = BestNeighbour<f64, u32>> {
Box::new(
self.kd_stars
.best_n_within_radius(&query, radius, max_qty, DistanceMetric::SquaredEuclidean)
.map(|nn| BestNeighbour {
distance: nn.distance.az::<f64>(),
item: nn.item.az::<SIDX>(),
}),
)
}
fn get_star(&self, index: SIDX) -> &Star {
&self.stars[index as usize]
}
fn get_quad(&self, index: QIDX) -> &Quad {
&self.quads[index as usize]
}
fn stars_within_radius(
&self,
query: &[f64; 3],
radius: f64,
) -> Vec<NearestNeighbour<f64, SIDX>> {
self.kd_stars
.within_radius(query, radius.az::<f64>(), DistanceMetric::SquaredEuclidean)
.into_iter()
.map(|nn| NearestNeighbour {
distance: nn.distance.az::<f64>(),
item: nn.item.az::<SIDX>(),
})
.collect()
}
fn quad_codes_within_radius(
&self,
query: &[f64; 4],
radius: f64,
) -> Vec<NearestNeighbour<f64, SIDX>> {
self.kd_codes
.within_radius(query, radius.az::<f64>(), DistanceMetric::Manhattan)
.into_iter()
.map(|nn| NearestNeighbour {
distance: nn.distance.az::<f64>(),
item: nn.item.az::<SIDX>(),
})
.collect()
}
}
#[derive(Debug, Archive, Serialize, Deserialize)]
#[rkyv(crate=rkyv_08)]
pub struct StarIndex {
pub stars: Vec<Star>,
pub(crate) kd_stars: StarKdTree,
pub quads: Vec<Quad>,
kd_codes: QuadKdTree,
}
impl StarIndex {
pub fn new(
stars: Vec<Star>,
kd_stars: StarKdTree,
quads: Vec<Quad>,
kd_codes: QuadKdTree,
) -> StarIndex {
StarIndex {
stars,
kd_stars,
quads,
kd_codes,
}
}
pub fn from_stars(stars: Vec<Star>) -> StarIndex {
let kd_stars = StarIndex::build_star_kdtree(&stars);
let quads: Vec<Quad> = StarIndex::generate_quad_list(&stars);
let kd_codes = StarIndex::build_code_kdtree(&quads, &stars);
StarIndex::new(stars, kd_stars, quads, kd_codes)
}
pub fn from_stars_and_quads(stars: Vec<Star>, quads: Vec<Quad>) -> StarIndex {
let kd_stars = StarIndex::build_star_kdtree(&stars);
let kd_codes = StarIndex::build_code_kdtree(&quads, &stars);
StarIndex::new(stars, kd_stars, quads, kd_codes)
}
pub fn from_stars_and_quads_and_codes(
stars: Vec<Star>,
quads: Vec<Quad>,
codes: Vec<QuadCode>,
) -> StarIndex {
let kd_stars = StarIndex::build_star_kdtree(&stars);
let kd_codes = StarIndex::build_code_kdtree_from_codes(&codes);
StarIndex::new(stars, kd_stars, quads, kd_codes)
}
fn build_star_kdtree(stars: &[Star]) -> StarKdTree {
let points = stars
.iter()
.map(|star| star.spherical_array())
.collect::<Vec<_>>();
let kd_stars = StarKdTree::new_from_slice(&points).expect("Failed to create KDTree");
info!("Stars added to kd-tree: {:?}", kd_stars.size());
kd_stars
}
fn build_code_kdtree(quads: &[Quad], stars: &[Star]) -> QuadKdTree {
let codes = quads
.iter()
.map(|quad| quad.calc_code(&stars).unwrap())
.collect::<Vec<_>>();
let kdt = QuadKdTree::new_from_slice(&codes).expect("Failed to create KDTree");
info!("Quads added to kd-tree: {:?}", kdt.size());
kdt
}
fn build_code_kdtree_from_codes(codes: &[QuadCode]) -> QuadKdTree {
QuadKdTree::new_from_slice(&codes).expect("Failed to create KDTree")
}
pub fn generate_quad_list(stars: &[Star]) -> Vec<Quad> {
let mut quad_inbox: Vec<Quad> = Vec::with_capacity(stars.len() * 3);
let mut filtered_star_indices: Vec<usize> = Vec::with_capacity(stars.len());
filtered_star_indices.push(0);
let mut i = 0;
filtered_star_indices.resize_with(stars.len() - 1, || {
i += 1;
i
});
let mut max_ab: f64 = INITIAL_MAX_AB_DEGREES;
let mut min_ab: f64 = max_ab * MAX_AB2_MIN_AB2_RATIO;
let mut min_ac = min_ab * MIN_AC_MIN_AB_RATIO;
while min_ab >= TERMINAL_MIN_AB_DEGREES {
info!(
"max_ab = {:}, min_ab = {:}, quads so far: {:}",
max_ab,
min_ab,
quad_inbox.len()
);
let mut stars_times_used = vec![0; stars.len()];
let max_ab2: f64 = max_ab.to_radians() * max_ab.to_radians();
let min_ab2: f64 = min_ab.to_radians() * min_ab.to_radians();
let min_ac2: f64 = min_ac.to_radians() * min_ac.to_radians();
filtered_star_indices = filtered_star_indices
.into_iter()
.filter(|&index| stars_times_used[index] < MAX_TOTAL_REUSE)
.collect();
'b_loop: for (b_pos, &b_idx) in filtered_star_indices.iter().enumerate() {
let b_times_used: usize = stars_times_used[b_idx];
if b_times_used >= MAX_TOTAL_REUSE {
continue;
}
if b_pos % 1000 == 0 {
debug!("b_pos: {:}", b_pos);
}
'a_loop: for (a_pos, &a_idx) in filtered_star_indices.iter().enumerate() {
if a_pos == b_pos {
break;
}
let a_times_used: usize = stars_times_used[a_idx];
if a_times_used >= MAX_TOTAL_REUSE {
continue;
}
if !StarIndex::check_scale(&stars[a_idx], &stars[b_idx], min_ab2, max_ab2) {
continue;
}
let mut ab_used: usize = 0;
let pquad = PotentialQuad::new(a_idx, b_idx, stars);
let interior_star_indices: Vec<usize> = filtered_star_indices
.iter()
.filter(|&&cd_idx: &&usize| {
a_idx != cd_idx
&& b_idx != cd_idx
&& pquad.can_contain(cd_idx, &stars)
&& stars[a_idx].dist_sq_to(&stars[cd_idx]) > min_ac2
&& stars[b_idx].dist_sq_to(&stars[cd_idx]) > min_ac2
})
.copied()
.collect();
'c_loop: for (c_pos, &c_idx) in interior_star_indices.iter().enumerate() {
for &d_idx in interior_star_indices.iter().skip(c_pos + 1) {
if stars[c_idx].dist_sq_to(&stars[d_idx]) < min_ac2 {
continue;
}
if ab_used >= MAX_AB_USE {
continue 'a_loop;
}
let c_times_used: usize = stars_times_used[c_idx];
if c_times_used >= MAX_TOTAL_REUSE {
continue 'c_loop;
}
let d_times_used: usize = stars_times_used[d_idx];
if d_times_used >= MAX_TOTAL_REUSE {
continue;
}
let a_times_used: usize = stars_times_used[a_idx];
if a_times_used == MAX_TOTAL_REUSE {
continue 'a_loop;
}
let b_times_used: usize = stars_times_used[b_idx];
if b_times_used == MAX_TOTAL_REUSE {
continue 'b_loop;
}
stars_times_used[a_idx] = a_times_used + 1;
stars_times_used[b_idx] = b_times_used + 1;
stars_times_used[c_idx] = c_times_used + 1;
stars_times_used[d_idx] = d_times_used + 1;
ab_used += 1;
quad_inbox.push(pquad.to_quad(c_idx, d_idx));
}
}
}
}
debug!("CABD Phase");
'c_loop2: for (c_pos, &c_idx) in filtered_star_indices.iter().enumerate() {
let c_times_used: usize = stars_times_used[c_idx];
if c_times_used >= MAX_TOTAL_REUSE {
debug!("skip B (B overuse)");
continue;
}
if c_pos % 1000 == 0 {
debug!("c_pos: {:}", c_pos);
}
'a_loop2: for (a_pos, &a_idx) in filtered_star_indices.iter().enumerate() {
if c_pos == 0 || a_pos == c_pos - 1
{
break;
}
let a_times_used: usize = stars_times_used[a_idx];
if a_times_used >= MAX_TOTAL_REUSE {
continue;
}
'b_loop2: for (b_pos, &b_idx) in
filtered_star_indices.iter().skip(a_pos + 1).enumerate()
{
if b_pos == c_pos - 1 {
break;
}
if !StarIndex::check_scale(&stars[a_idx], &stars[b_idx], min_ab2, max_ab2) {
continue;
}
let mut ab_used: usize = 0;
let pquad = PotentialQuad::new(a_idx, b_idx, stars);
if !pquad.can_contain(c_idx, &stars) {
continue;
}
let interior_star_indices: Vec<usize> = filtered_star_indices
.iter()
.filter(|&&d_idx| {
d_idx != c_idx
&& b_idx != d_idx
&& a_idx != d_idx
&& pquad.can_contain(d_idx, &stars)
&& stars[a_idx].dist_sq_to(&stars[d_idx]) > min_ac2
&& stars[b_idx].dist_sq_to(&stars[d_idx]) > min_ac2
})
.copied()
.collect();
debug!(
"interior_star_indices length: {:?}",
interior_star_indices.len()
);
for &d_idx in interior_star_indices.iter().skip(c_pos + 1) {
if stars[c_idx].dist_sq_to(&stars[d_idx]) < min_ac2 {
debug!("skip D (too close to C)");
continue;
}
if ab_used >= MAX_AB_USE {
debug!("skip B (AB overuse)");
continue 'a_loop2;
}
let c_times_used: usize = stars_times_used[c_idx];
if c_times_used >= MAX_TOTAL_REUSE {
debug!("skip C (overuse)");
continue 'c_loop2;
}
let d_times_used: usize = stars_times_used[d_idx];
if d_times_used >= MAX_TOTAL_REUSE {
debug!("skip D (overuse)");
continue;
}
let a_times_used: usize = stars_times_used[a_idx];
if a_times_used == MAX_TOTAL_REUSE {
debug!("skip A (overuse)");
continue 'a_loop2;
}
let b_times_used: usize = stars_times_used[b_idx];
if b_times_used == MAX_TOTAL_REUSE {
debug!("skip B (overuse)");
continue 'b_loop2;
}
stars_times_used[a_idx] = a_times_used + 1;
stars_times_used[b_idx] = b_times_used + 1;
stars_times_used[c_idx] = c_times_used + 1;
stars_times_used[d_idx] = d_times_used + 1;
ab_used += 1;
quad_inbox.push(pquad.to_quad(c_idx, d_idx));
debug!(
"CABD Quad #{:?}: ({:?}, {:?}, {:?}, {:?})",
quad_inbox.len(),
a_idx,
b_idx,
c_idx,
d_idx
);
}
}
}
}
max_ab *= MAX_AB_SHRINK_FACTOR;
min_ab = max_ab * MAX_AB2_MIN_AB2_RATIO;
min_ac = min_ab * MIN_AC_MIN_AB_RATIO;
}
quad_inbox
}
fn check_scale(star_a: &Star, star_b: &Star, min_ab_sq: f64, max_ab_sq: f64) -> bool {
let dist: f64 = star_a.dist_sq_to(star_b);
dist >= min_ab_sq && dist <= max_ab_sq
}
pub fn write_to_rkyv(self, filename: &str) -> Result<(), Box<dyn Error>> {
let mut file = File::create(filename)?;
let buf = to_bytes::<RkyvError>(&self).expect("Could not serialize with rkyv");
file.write(&buf)
.expect("Could not write serialized rkyv to file");
Ok(())
}
pub fn deserialize_from_rkyv_file(filename: &Path) -> Result<StarIndex, Box<dyn Error>> {
let buf = unsafe { MmapOptions::new().map(&File::open(filename)?)? };
let index = unsafe { from_bytes_unchecked::<StarIndex, RkyvError>(&buf) }?;
let num_stars = index.stars.len();
let num_quads = index.quads.len();
info!(
"index loaded (Stars: {:?}, Quads: {:?})",
num_stars, num_quads
);
Ok(index)
}
}