use std::{mem::transmute, ptr::NonNull};
use crate::mem::{
header::LinksHeader,
split::{
generic::external_recursion_less_base::{
ExternalRecursionlessSizeBalancedTreeBase,
ExternalRecursionlessSizeBalancedTreeBaseAbstract,
},
DataPart, IndexPart,
},
traits::LinksTree,
SplitTree,
};
use crate::{mem::SplitUpdateMem, Link};
use data::{Flow, LinkReference, LinksConstants};
use trees::{IterativeSizeBalancedTree, RecursiveSizeBalancedTree};
pub struct ExternalTargetsRecursionlessTree<T: LinkReference> {
base: ExternalRecursionlessSizeBalancedTreeBase<T>,
}
impl<T: LinkReference> ExternalTargetsRecursionlessTree<T> {
pub fn new(
constants: LinksConstants<T>,
data: NonNull<[DataPart<T>]>,
indexes: NonNull<[IndexPart<T>]>,
) -> Self {
Self {
base: ExternalRecursionlessSizeBalancedTreeBase::new(constants, data, indexes),
}
}
}
impl<T: LinkReference> RecursiveSizeBalancedTree<T> for ExternalTargetsRecursionlessTree<T> {
unsafe fn get_left_reference(&self, node: T) -> *const T {
std::ptr::addr_of!(self.get_index_part(node).left_as_target)
}
unsafe fn get_right_reference(&self, node: T) -> *const T {
std::ptr::addr_of!(self.get_index_part(node).right_as_target)
}
unsafe fn get_mut_left_reference(&mut self, node: T) -> *mut T {
std::ptr::addr_of_mut!(self.get_mut_index_part(node).left_as_target)
}
unsafe fn get_mut_right_reference(&mut self, node: T) -> *mut T {
std::ptr::addr_of_mut!(self.get_mut_index_part(node).right_as_target)
}
unsafe fn get_left(&self, node: T) -> T {
self.get_index_part(node).left_as_target
}
unsafe fn get_right(&self, node: T) -> T {
self.get_index_part(node).right_as_target
}
unsafe fn get_size(&self, node: T) -> T {
self.get_index_part(node).size_as_target
}
unsafe fn set_left(&mut self, node: T, left: T) {
self.get_mut_index_part(node).left_as_target = left;
}
unsafe fn set_right(&mut self, node: T, right: T) {
self.get_mut_index_part(node).right_as_target = right;
}
unsafe fn set_size(&mut self, node: T, size: T) {
self.get_mut_index_part(node).size_as_target = size;
}
unsafe fn first_is_to_the_left_of_second(&self, first: T, second: T) -> bool {
let first = self.get_data_part(first);
let second = self.get_data_part(second);
self.first_is_to_the_left_of_second_4(
first.source,
first.target,
second.source,
second.target,
)
}
unsafe fn first_is_to_the_right_of_second(&self, first: T, second: T) -> bool {
let first = self.get_data_part(first);
let second = self.get_data_part(second);
self.first_is_to_the_right_of_second_4(
first.source,
first.target,
second.source,
second.target,
)
}
unsafe fn clear_node(&mut self, node: T) {
let link = self.get_mut_index_part(node);
link.left_as_target = T::from_byte(0);
link.right_as_target = T::from_byte(0);
link.size_as_target = T::from_byte(0);
}
}
impl<T: LinkReference> IterativeSizeBalancedTree<T> for ExternalTargetsRecursionlessTree<T> {}
fn each_usages_core<T: LinkReference, H: FnMut(Link<T>) -> Flow + ?Sized>(
this: &ExternalTargetsRecursionlessTree<T>,
base: T,
link: T,
handler: &mut H,
) -> Flow {
if link == T::from_byte(0) {
return Flow::Continue;
}
unsafe {
let link_base_part = this.get_base_part(link);
if link_base_part > base {
if each_usages_core(this, base, this.get_left_or_default(link), handler).is_break() {
return Flow::Break;
}
} else if link_base_part < base {
if each_usages_core(this, base, this.get_right_or_default(link), handler).is_break() {
return Flow::Break;
}
} else {
if handler(this.get_link_value(link)).is_break() {
return Flow::Break;
}
if each_usages_core(this, base, this.get_left_or_default(link), handler).is_break() {
return Flow::Break;
}
if each_usages_core(this, base, this.get_right_or_default(link), handler).is_break() {
return Flow::Break;
}
}
}
Flow::Continue
}
impl<T: LinkReference> LinksTree<T> for ExternalTargetsRecursionlessTree<T> {
fn count_usages(&self, link: T) -> T {
unsafe {
let mut root = self.get_tree_root();
let total = self.get_size(root);
let mut total_right_ignore = T::from_byte(0);
while root != T::from_byte(0) {
let base = self.get_base_part(root);
if base <= link {
root = self.get_right_or_default(root);
} else {
total_right_ignore =
total_right_ignore + self.get_right_size(root) + T::from_byte(1);
root = self.get_left_or_default(root);
}
}
root = self.get_tree_root();
let mut total_left_ignore = T::from_byte(0);
while root != T::from_byte(0) {
let base = self.get_base_part(root);
if base >= link {
root = self.get_left_or_default(root);
} else {
total_left_ignore =
total_left_ignore + self.get_left_size(root) + T::from_byte(1);
root = self.get_right_or_default(root);
}
}
total - total_right_ignore - total_left_ignore
}
}
fn search(&self, source: T, target: T) -> T {
unsafe {
let mut root = self.get_tree_root();
while root != T::from_byte(0) {
let root_link = self.get_data_part(root);
let root_source = root_link.source;
let root_target = root_link.target;
if self.first_is_to_the_left_of_second_4(source, target, root_source, root_target) {
root = self.get_left_or_default(root);
} else if self.first_is_to_the_right_of_second_4(
source,
target,
root_source,
root_target,
) {
root = self.get_right_or_default(root);
} else {
return root;
}
}
T::from_byte(0)
}
}
fn each_usages<H: FnMut(Link<T>) -> Flow + ?Sized>(&self, root: T, handler: &mut H) -> Flow {
each_usages_core(self, root, self.get_tree_root(), handler)
}
fn detach(&mut self, root: &mut T, index: T) {
unsafe { IterativeSizeBalancedTree::detach(self, root as *mut _, index) }
}
fn attach(&mut self, root: &mut T, index: T) {
unsafe { IterativeSizeBalancedTree::attach(self, root as *mut _, index) }
}
}
impl<T: LinkReference> SplitUpdateMem<T> for ExternalTargetsRecursionlessTree<T> {
fn update_mem(&mut self, data: NonNull<[DataPart<T>]>, indexes: NonNull<[IndexPart<T>]>) {
self.base.indexes = indexes;
self.base.data = data;
}
}
impl<T: LinkReference> SplitTree<T> for ExternalTargetsRecursionlessTree<T> {}
impl<T: LinkReference> ExternalRecursionlessSizeBalancedTreeBaseAbstract<T>
for ExternalTargetsRecursionlessTree<T>
{
fn get_header(&self) -> &LinksHeader<T> {
unsafe { transmute(&self.base.indexes.as_ref()[0]) }
}
fn get_mut_header(&mut self) -> &mut LinksHeader<T> {
unsafe { transmute(&mut self.base.indexes.as_mut()[0]) }
}
fn get_index_part(&self, link: T) -> &IndexPart<T> {
unsafe { &self.base.indexes.as_ref()[link.as_()] }
}
fn get_mut_index_part(&mut self, link: T) -> &mut IndexPart<T> {
unsafe { &mut self.base.indexes.as_mut()[link.as_()] }
}
fn get_data_part(&self, link: T) -> &DataPart<T> {
unsafe { &self.base.data.as_ref()[link.as_()] }
}
fn get_mut_data_part(&mut self, link: T) -> &mut DataPart<T> {
unsafe { &mut self.base.data.as_mut()[link.as_()] }
}
fn get_tree_root(&self) -> T {
self.get_header().root_as_target
}
fn get_base_part(&self, link: T) -> T {
self.get_data_part(link).target
}
fn first_is_to_the_left_of_second_4(
&self,
first_source: T,
first_target: T,
second_source: T,
second_target: T,
) -> bool {
(first_target < second_target)
|| (first_target == second_target && first_source < second_source)
}
fn first_is_to_the_right_of_second_4(
&self,
first_source: T,
first_target: T,
second_source: T,
second_target: T,
) -> bool {
(first_target > second_target)
|| (first_target == second_target && first_source > second_source)
}
}