use crate::core::geo::component2d::{Component2D, WithinRelation};
use crate::core::index::point_values::Relation;
use crate::core::util::core_helper::CoreHelper;
use crate::core::util::error::lucene_error::{LuceneError, Result};
use std::cmp::Ordering;
#[derive(Default)]
pub struct ComponentTree<T> {
min_y: f64,
max_y: f64,
min_x: f64,
max_x: f64,
left: Option<Box<ComponentTree<T>>>,
right: Option<Box<ComponentTree<T>>>,
split_x: bool,
component: T,
}
impl<T> ComponentTree<T>
where
T: Component2D,
{
pub(crate) fn new(component: T, split_x: bool) -> Self {
let min_y = component.get_min_y();
let max_y = component.get_max_y();
let min_x = component.get_min_x();
let max_x = component.get_max_x();
Self {
min_y,
max_y,
min_x,
max_x,
left: None,
right: None,
split_x,
component,
}
}
}
impl<T> Component2D for ComponentTree<T>
where
T: Component2D,
{
fn get_min_x(&self) -> f64 {
self.min_x
}
fn get_max_x(&self) -> f64 {
self.max_x
}
fn get_min_y(&self) -> f64 {
self.min_y
}
fn get_max_y(&self) -> f64 {
self.max_y
}
fn contains(&self, x: f64, y: f64) -> bool {
if y <= self.max_y && x <= self.max_x {
if self.component.contains(x, y) {
return true;
}
if let Some(left) = &self.left
&& left.contains(x, y)
{
return true;
}
if let Some(right) = &self.right
&& ((!self.split_x && y >= self.component.get_min_y())
|| (self.split_x && x >= self.component.get_min_x()))
&& right.contains(x, y)
{
return true;
}
}
false
}
fn relate(&self, min_x: f64, max_x: f64, min_y: f64, max_y: f64) -> Result<Relation> {
if min_y <= self.max_y && min_x <= self.max_x {
let relation = self.component.relate(min_x, max_x, min_y, max_y)?;
if relation != Relation::CellOutsideQuery {
return Ok(relation);
}
if let Some(left) = &self.left {
let relation = left.relate(min_x, max_x, min_y, max_y)?;
if relation != Relation::CellOutsideQuery {
return Ok(relation);
}
}
if let Some(right) = &self.right
&& ((!self.split_x && max_y >= self.component.get_min_y())
|| (self.split_x && max_x >= self.component.get_min_x()))
{
let relation = right.relate(min_x, max_x, min_y, max_y)?;
if relation != Relation::CellOutsideQuery {
return Ok(relation);
}
}
}
Ok(Relation::CellOutsideQuery)
}
fn intersects_line(
&self,
min_x: f64,
max_x: f64,
min_y: f64,
max_y: f64,
a_x: f64,
a_y: f64,
b_x: f64,
b_y: f64,
) -> bool {
if min_y <= self.max_y && min_x <= self.max_x {
if self
.component
.intersects_line(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y)
{
return true;
}
if let Some(left) = &self.left
&& left.intersects_line(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y)
{
return true;
}
if let Some(right) = &self.right
&& ((!self.split_x && max_y >= self.component.get_min_y())
|| (self.split_x && max_x >= self.component.get_min_x()))
&& right.intersects_line(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y)
{
return true;
}
}
false
}
fn intersects_triangle(
&self,
min_x: f64,
max_x: f64,
min_y: f64,
max_y: f64,
a_x: f64,
a_y: f64,
b_x: f64,
b_y: f64,
c_x: f64,
c_y: f64,
) -> bool {
if min_y <= self.max_y && min_x <= self.max_x {
if self
.component
.intersects_triangle(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y, c_x, c_y)
{
return true;
}
if let Some(left) = &self.left
&& left.intersects_triangle(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y, c_x, c_y)
{
return true;
}
if let Some(right) = &self.right
&& ((!self.split_x && max_y >= self.component.get_min_y())
|| (self.split_x && max_x >= self.component.get_min_x()))
&& right.intersects_triangle(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y, c_x, c_y)
{
return true;
}
}
false
}
fn contains_line(
&self,
min_x: f64,
max_x: f64,
min_y: f64,
max_y: f64,
a_x: f64,
a_y: f64,
b_x: f64,
b_y: f64,
) -> bool {
if min_y <= self.max_y && min_x <= self.max_x {
if self
.component
.contains_line(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y)
{
return true;
}
if let Some(left) = &self.left
&& left.contains_line(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y)
{
return true;
}
if let Some(right) = &self.right
&& ((!self.split_x && max_y >= self.component.get_min_y())
|| (self.split_x && max_x >= self.component.get_min_x()))
&& right.contains_line(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y)
{
return true;
}
}
false
}
fn contains_triangle(
&self,
min_x: f64,
max_x: f64,
min_y: f64,
max_y: f64,
a_x: f64,
a_y: f64,
b_x: f64,
b_y: f64,
c_x: f64,
c_y: f64,
) -> bool {
if min_y <= self.max_y && min_x <= self.max_x {
if self
.component
.contains_triangle(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y, c_x, c_y)
{
return true;
}
if let Some(left) = &self.left
&& left.contains_triangle(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y, c_x, c_y)
{
return true;
}
if let Some(right) = &self.right
&& ((!self.split_x && max_y >= self.component.get_min_y())
|| (self.split_x && max_x >= self.component.get_min_x()))
&& right.contains_triangle(min_x, max_x, min_y, max_y, a_x, a_y, b_x, b_y, c_x, c_y)
{
return true;
}
}
false
}
fn within_point(&self, x: f64, y: f64) -> Result<WithinRelation> {
if self.left.is_some() || self.right.is_some() {
return Err(LuceneError::illegal_argument(
"within_point is not supported for shapes with more than one component",
));
}
self.component.within_point(x, y)
}
fn within_line(
&self,
min_x: f64,
max_x: f64,
min_y: f64,
max_y: f64,
a_x: f64,
a_y: f64,
ab: bool,
b_x: f64,
b_y: f64,
) -> Result<WithinRelation> {
if self.left.is_some() || self.right.is_some() {
return Err(LuceneError::illegal_argument(
"within_line is not supported for shapes with more than one component",
));
}
self
.component
.within_line(min_x, max_x, min_y, max_y, a_x, a_y, ab, b_x, b_y)
}
fn within_triangle(
&self,
min_x: f64,
max_x: f64,
min_y: f64,
max_y: f64,
a_x: f64,
a_y: f64,
ab: bool,
b_x: f64,
b_y: f64,
bc: bool,
c_x: f64,
c_y: f64,
ca: bool,
) -> Result<WithinRelation> {
if self.left.is_some() || self.right.is_some() {
return Err(LuceneError::illegal_argument(
"within_triangle is not supported for shapes with more than one component",
));
}
self.component.within_triangle(
min_x, max_x, min_y, max_y, a_x, a_y, ab, b_x, b_y, bc, c_x, c_y, ca,
)
}
}
pub(crate) fn create<T, C>(mut components: C) -> Result<ComponentTree<T>>
where
T: Component2D,
C: AsMut<[T]> + IntoIterator<Item = T>,
C::IntoIter: ExactSizeIterator,
{
if components.as_mut().is_empty() {
return Err(LuceneError::illegal_argument(
"components must not be empty",
));
}
if components.as_mut().len() == 1 {
let mut components = components.into_iter();
let component = components
.next()
.ok_or_else(|| LuceneError::illegal_state("component missing during tree construction"))?;
return Ok(ComponentTree::new(component, false));
}
let mut min_y = f64::INFINITY;
let mut min_x = f64::INFINITY;
for component in components.as_mut().iter() {
min_y = CoreHelper::min_f64(min_y, component.get_min_y());
min_x = CoreHelper::min_f64(min_x, component.get_min_x());
}
let component_count = components.as_mut().len();
partition_components(components.as_mut(), 0, component_count - 1, false);
let mut components = components.into_iter();
let mut root = create_tree(&mut components, component_count, false)?.ok_or_else(|| {
LuceneError::illegal_state("failed to build component tree from non-empty components")
})?;
if components.len() != 0 {
return Err(LuceneError::illegal_state(
"not all components were consumed during tree construction",
));
}
root.min_y = min_y;
root.min_x = min_x;
Ok(root)
}
fn partition_components<T>(components: &mut [T], low: usize, high: usize, split_x: bool)
where
T: Component2D,
{
if low >= high {
return;
}
let mid = (low + high) >> 1;
let relative_mid = mid - low;
components[low..=high].select_nth_unstable_by(relative_mid, |left, right| {
compare_components(left, right, split_x)
});
if mid > low {
partition_components(components, low, mid - 1, !split_x);
}
if mid < high {
partition_components(components, mid + 1, high, !split_x);
}
}
fn create_tree<T, I>(
components: &mut I,
component_count: usize,
split_x: bool,
) -> Result<Option<ComponentTree<T>>>
where
T: Component2D,
I: Iterator<Item = T>,
{
if component_count == 0 {
return Ok(None);
}
let left_count = (component_count - 1) >> 1;
let right_count = component_count - left_count - 1;
let left = create_tree(components, left_count, !split_x)?;
let component = components
.next()
.ok_or_else(|| LuceneError::illegal_state("component missing during tree construction"))?;
let mut new_node = ComponentTree::new(component, split_x);
new_node.left = left.map(Box::new);
new_node.right = create_tree(components, right_count, !split_x)?.map(Box::new);
if let Some(left) = &new_node.left {
new_node.max_x = CoreHelper::max_f64(new_node.max_x, left.get_max_x());
new_node.max_y = CoreHelper::max_f64(new_node.max_y, left.get_max_y());
}
if let Some(right) = &new_node.right {
new_node.max_x = CoreHelper::max_f64(new_node.max_x, right.get_max_x());
new_node.max_y = CoreHelper::max_f64(new_node.max_y, right.get_max_y());
}
Ok(Some(new_node))
}
fn compare_components<T>(left: &T, right: &T, split_x: bool) -> Ordering
where
T: Component2D,
{
if split_x {
CoreHelper::compare_f64(left.get_min_x(), right.get_min_x())
.then_with(|| CoreHelper::compare_f64(left.get_max_x(), right.get_max_x()))
} else {
CoreHelper::compare_f64(left.get_min_y(), right.get_min_y())
.then_with(|| CoreHelper::compare_f64(left.get_max_y(), right.get_max_y()))
}
}