use crate::interop::{CompressedEdge, RegionEdge};
use crate::types::*;
use crate::util::arena::Arena;
#[derive(Debug, Clone)]
pub struct AltTreeEdge {
pub alt_tree_node: AltTreeIdx,
pub edge: CompressedEdge,
}
impl AltTreeEdge {
pub fn empty() -> Self {
AltTreeEdge {
alt_tree_node: AltTreeIdx(u32::MAX),
edge: CompressedEdge::empty(),
}
}
pub fn new(alt_tree_node: AltTreeIdx, edge: CompressedEdge) -> Self {
AltTreeEdge {
alt_tree_node,
edge,
}
}
pub fn is_empty(&self) -> bool {
self.alt_tree_node.0 == u32::MAX
}
}
pub struct AltTreePruneResult {
pub orphan_edges: Vec<AltTreeEdge>,
pub pruned_path_region_edges: Vec<RegionEdge>,
pub regions_to_clear: Vec<RegionIdx>,
}
pub struct AltTreeNode {
pub inner_region: Option<RegionIdx>,
pub outer_region: Option<RegionIdx>,
pub inner_to_outer_edge: CompressedEdge,
pub parent: Option<AltTreeEdge>,
pub children: Vec<AltTreeEdge>,
pub visited: bool,
}
impl Default for AltTreeNode {
fn default() -> Self {
AltTreeNode {
inner_region: None,
outer_region: None,
inner_to_outer_edge: CompressedEdge::empty(),
parent: None,
children: Vec::new(),
visited: false,
}
}
}
impl AltTreeNode {
pub fn reset_for_reuse(&mut self) {
self.inner_region = None;
self.outer_region = None;
self.inner_to_outer_edge = CompressedEdge::empty();
self.parent = None;
self.children.clear();
self.visited = false;
}
pub fn new_root(outer_region: RegionIdx) -> Self {
AltTreeNode {
inner_region: None,
outer_region: Some(outer_region),
inner_to_outer_edge: CompressedEdge::empty(),
parent: None,
children: Vec::new(),
visited: false,
}
}
pub fn new_pair(
inner_region: RegionIdx,
outer_region: RegionIdx,
inner_to_outer_edge: CompressedEdge,
) -> Self {
AltTreeNode {
inner_region: Some(inner_region),
outer_region: Some(outer_region),
inner_to_outer_edge,
parent: None,
children: Vec::new(),
visited: false,
}
}
pub fn add_child(
&mut self,
self_idx: AltTreeIdx,
child: AltTreeEdge,
arena: &mut Arena<AltTreeNode>,
) {
let child_idx = child.alt_tree_node;
let reversed_edge = child.edge.reversed();
self.children.push(child);
arena[child_idx.0].parent = Some(AltTreeEdge::new(self_idx, reversed_edge));
}
pub fn become_root(self_idx: AltTreeIdx, arena: &mut Arena<AltTreeNode>) {
let parent_edge = arena[self_idx.0].parent.clone();
if parent_edge.is_none() {
return; }
let parent_edge = parent_edge.unwrap();
let old_parent_idx = parent_edge.alt_tree_node;
AltTreeNode::become_root(old_parent_idx, arena);
let self_inner = arena[self_idx.0].inner_region;
let self_inner_to_outer = arena[self_idx.0].inner_to_outer_edge;
let parent_edge_val = arena[self_idx.0].parent.as_ref().unwrap().edge;
arena[old_parent_idx.0].inner_region = self_inner;
arena[old_parent_idx.0].inner_to_outer_edge = parent_edge_val;
arena[self_idx.0].inner_region = None;
unstable_erase_by_node(&mut arena[old_parent_idx.0].children, self_idx);
arena[self_idx.0].parent = None;
let edge_to_old_parent = self_inner_to_outer.reversed();
let child_edge = AltTreeEdge::new(old_parent_idx, edge_to_old_parent);
let reversed = edge_to_old_parent.reversed();
arena[self_idx.0].children.push(child_edge);
arena[old_parent_idx.0].parent = Some(AltTreeEdge::new(self_idx, reversed));
arena[self_idx.0].inner_to_outer_edge = CompressedEdge::empty();
}
pub fn most_recent_common_ancestor(
node_a: AltTreeIdx,
node_b: AltTreeIdx,
arena: &mut Arena<AltTreeNode>,
) -> Option<AltTreeIdx> {
arena[node_a.0].visited = true;
arena[node_b.0].visited = true;
let mut a_cur = node_a;
let mut b_cur = node_b;
let common_ancestor;
loop {
let a_parent = arena[a_cur.0]
.parent
.as_ref()
.map(|e| e.alt_tree_node);
let b_parent = arena[b_cur.0]
.parent
.as_ref()
.map(|e| e.alt_tree_node);
if a_parent.is_some() || b_parent.is_some() {
if let Some(ap) = a_parent {
a_cur = ap;
if arena[a_cur.0].visited {
common_ancestor = a_cur;
break;
}
arena[a_cur.0].visited = true;
}
if let Some(bp) = b_parent {
b_cur = bp;
if arena[b_cur.0].visited {
common_ancestor = b_cur;
break;
}
arena[b_cur.0].visited = true;
}
} else {
Self::clear_visited_upward(node_a, arena);
Self::clear_visited_upward(node_b, arena);
return None;
}
}
arena[common_ancestor.0].visited = false;
let mut cleanup = arena[common_ancestor.0]
.parent
.as_ref()
.map(|e| e.alt_tree_node);
while let Some(idx) = cleanup {
if !arena[idx.0].visited {
break;
}
arena[idx.0].visited = false;
cleanup = arena[idx.0].parent.as_ref().map(|e| e.alt_tree_node);
}
Some(common_ancestor)
}
fn clear_visited_upward(start: AltTreeIdx, arena: &mut Arena<AltTreeNode>) {
let mut cur = Some(start);
while let Some(idx) = cur {
if !arena[idx.0].visited {
break;
}
arena[idx.0].visited = false;
cur = arena[idx.0].parent.as_ref().map(|e| e.alt_tree_node);
}
}
pub fn prune_upward_path_stopping_before(
self_idx: AltTreeIdx,
arena: &mut Arena<AltTreeNode>,
prune_parent: AltTreeIdx,
back: bool,
) -> AltTreePruneResult {
let mut orphan_edges: Vec<AltTreeEdge> = Vec::new();
let mut pruned_path_region_edges: Vec<RegionEdge> = Vec::new();
let mut regions_to_clear: Vec<RegionIdx> = Vec::new();
let mut current = self_idx;
while current != prune_parent {
let children = std::mem::take(&mut arena[current.0].children);
orphan_edges.extend(children);
let inner = arena[current.0].inner_region.unwrap();
let outer = arena[current.0].outer_region.unwrap();
let i2o = arena[current.0].inner_to_outer_edge;
let parent_edge = arena[current.0].parent.as_ref().unwrap().clone();
let parent_idx = parent_edge.alt_tree_node;
let parent_outer = arena[parent_idx.0].outer_region.unwrap();
if back {
pruned_path_region_edges.push(RegionEdge {
region: inner,
edge: i2o,
});
pruned_path_region_edges.push(RegionEdge {
region: parent_outer,
edge: parent_edge.edge.reversed(),
});
} else {
pruned_path_region_edges.push(RegionEdge {
region: outer,
edge: i2o.reversed(),
});
pruned_path_region_edges.push(RegionEdge {
region: inner,
edge: parent_edge.edge,
});
}
unstable_erase_by_node(&mut arena[parent_idx.0].children, current);
regions_to_clear.push(inner);
regions_to_clear.push(outer);
let to_free = current;
current = parent_idx;
arena.free(to_free.0);
}
AltTreePruneResult {
orphan_edges,
pruned_path_region_edges,
regions_to_clear,
}
}
}
pub fn unstable_erase_by_node(vec: &mut Vec<AltTreeEdge>, target: AltTreeIdx) -> bool {
if let Some(pos) = vec.iter().position(|e| e.alt_tree_node == target) {
let last = vec.len() - 1;
if pos != last {
vec.swap(pos, last);
}
vec.pop();
true
} else {
false
}
}