use crate::forme::MemberId;
use crate::forme::subgraph::SubgraphId;
use crate::forme::lens::ProjectionLens;
use serde::{Deserialize, Serialize};
use std::collections::{HashMap, HashSet};
#[derive(Clone, Debug, Serialize, Deserialize)]
#[serde(bound = "")]
pub struct TreeTopology<N: MemberId> {
parent: HashMap<N, N>,
children: HashMap<N, Vec<N>>,
roots: Vec<N>,
insertion_order: Vec<N>,
}
impl<N: MemberId> Default for TreeTopology<N> {
fn default() -> Self {
Self::new()
}
}
impl<N: MemberId> TreeTopology<N> {
pub fn new() -> Self {
Self {
parent: HashMap::new(),
children: HashMap::new(),
roots: Vec::new(),
insertion_order: Vec::new(),
}
}
pub fn attach_child(&mut self, child: N, parent: &N) -> bool {
if child == *parent || self.contains(&child) || !self.contains(parent) {
return false;
}
self.parent.insert(child.clone(), parent.clone());
self.children
.entry(parent.clone())
.or_default()
.push(child.clone());
if !self.insertion_order.contains(&child) {
self.insertion_order.push(child);
}
true
}
pub fn attach_sibling(&mut self, member: N, sibling_of: &N) -> bool {
if !self.contains(sibling_of) {
return false;
}
if let Some(parent) = self.parent.get(sibling_of).cloned() {
self.attach_child(member, &parent)
} else {
self.attach_root(member)
}
}
pub fn attach_root(&mut self, member: N) -> bool {
if self.contains(&member) {
return false;
}
self.roots.push(member.clone());
self.insertion_order.push(member);
true
}
pub fn reparent(&mut self, member: &N, new_parent: &N) -> bool {
if member == new_parent {
return false;
}
if !self.contains(member) || !self.contains(new_parent) {
return false;
}
if self.is_ancestor_of(member, new_parent) {
return false;
}
self.detach_from_parent(member);
self.parent.insert(member.clone(), new_parent.clone());
self.children
.entry(new_parent.clone())
.or_default()
.push(member.clone());
true
}
pub fn detach(&mut self, member: &N) -> Vec<N> {
let subtree = self.descendants_inclusive(member);
self.detach_from_parent(member);
for node in &subtree {
self.parent.remove(node);
self.children.remove(node);
self.insertion_order.retain(|n| n != node);
}
subtree
}
pub fn reattach_child(&mut self, child: N, parent: &N) {
self.parent.insert(child.clone(), parent.clone());
self.children
.entry(parent.clone())
.or_default()
.push(child.clone());
if !self.insertion_order.contains(&child) {
self.insertion_order.push(child);
}
}
pub fn detach_single(&mut self, member: &N) {
self.detach_from_parent(member);
self.insertion_order.retain(|n| n != member);
if let Some(children) = self.children.remove(member) {
for child in &children {
self.parent.remove(child);
}
}
}
pub fn promote_to_root(&mut self, member: &N) {
if !self.insertion_order.contains(member) {
return;
}
if let Some(parent) = self.parent.remove(member) {
if let Some(siblings) = self.children.get_mut(&parent) {
siblings.retain(|n| n != member);
}
}
if !self.roots.contains(member) {
self.roots.push(member.clone());
}
}
pub fn reorder_children(&mut self, parent: &N, new_order: Vec<N>) {
if let Some(children) = self.children.get_mut(parent) {
let valid: std::collections::HashSet<&N> = children.iter().collect();
let mut reordered: Vec<N> = new_order
.into_iter()
.filter(|n| valid.contains(n))
.collect();
let explicit: std::collections::HashSet<N> = reordered.iter().cloned().collect();
for child in children.iter() {
if !explicit.contains(child) {
reordered.push(child.clone());
}
}
*children = reordered;
}
}
pub fn parent_of(&self, member: &N) -> Option<&N> {
self.parent.get(member)
}
pub fn children_of(&self, member: &N) -> &[N] {
self.children
.get(member)
.map(|v| v.as_slice())
.unwrap_or(&[])
}
pub fn roots(&self) -> &[N] {
&self.roots
}
pub fn insertion_order(&self) -> &[N] {
&self.insertion_order
}
pub fn contains(&self, member: &N) -> bool {
self.roots.contains(member) || self.parent.contains_key(member)
}
pub fn has_children(&self, member: &N) -> bool {
self.children.get(member).is_some_and(|c| !c.is_empty())
}
pub fn depth_of(&self, member: &N) -> usize {
let mut depth = 0;
let mut current = member;
while let Some(p) = self.parent.get(current) {
depth += 1;
current = p;
}
depth
}
pub fn descendants(&self, member: &N) -> Vec<N> {
let mut result = Vec::new();
self.collect_descendants(member, &mut result);
result
}
pub fn ancestors(&self, member: &N) -> Vec<N> {
let mut result = Vec::new();
let mut current = member;
while let Some(p) = self.parent.get(current) {
result.push(p.clone());
current = p;
}
result
}
pub fn siblings(&self, member: &N) -> Vec<N> {
if let Some(parent) = self.parent.get(member) {
self.children_of(parent)
.iter()
.filter(|n| *n != member)
.cloned()
.collect()
} else {
self.roots
.iter()
.filter(|n| *n != member)
.cloned()
.collect()
}
}
pub fn visible_walk<'a>(
&'a self,
expanded: &'a HashSet<N>,
_lens: &ProjectionLens,
) -> Vec<TreeRow<'a, N>> {
let mut rows = Vec::new();
for root in &self.roots {
self.walk_node(root, 0, expanded, &mut rows);
}
rows
}
pub fn len(&self) -> usize {
self.insertion_order.len()
}
pub fn is_empty(&self) -> bool {
self.insertion_order.is_empty()
}
fn detach_from_parent(&mut self, member: &N) {
if let Some(parent) = self.parent.remove(member) {
if let Some(siblings) = self.children.get_mut(&parent) {
siblings.retain(|n| n != member);
}
} else {
self.roots.retain(|n| n != member);
}
}
fn descendants_inclusive(&self, member: &N) -> Vec<N> {
let mut result = vec![member.clone()];
self.collect_descendants(member, &mut result);
result
}
fn collect_descendants(&self, member: &N, result: &mut Vec<N>) {
if let Some(children) = self.children.get(member) {
for child in children {
result.push(child.clone());
self.collect_descendants(child, result);
}
}
}
fn walk_node<'a>(
&'a self,
member: &'a N,
depth: usize,
expanded: &HashSet<N>,
rows: &mut Vec<TreeRow<'a, N>>,
) {
let has_children = self.has_children(member);
let is_expanded = expanded.contains(member);
let is_last = self.is_last_sibling(member);
rows.push(TreeRow {
member,
depth,
is_expanded: is_expanded && has_children,
has_children,
is_last_sibling: is_last,
subgraph_id: None, });
if has_children && is_expanded {
for child in self.children_of(member) {
self.walk_node(child, depth + 1, expanded, rows);
}
}
}
fn is_last_sibling(&self, member: &N) -> bool {
if let Some(parent) = self.parent.get(member) {
self.children_of(parent).last() == Some(member)
} else {
self.roots.last() == Some(member)
}
}
fn is_ancestor_of(&self, ancestor: &N, descendant: &N) -> bool {
if ancestor == descendant {
return true;
}
let mut current = descendant;
while let Some(p) = self.parent.get(current) {
if p == ancestor {
return true;
}
current = p;
}
false
}
pub fn assert_invariants(&self) {
for (child, parent) in &self.parent {
let children = self.children_of(parent);
assert!(
children.contains(child),
"child {:?} claims parent {:?}, but parent's children list doesn't contain it",
child,
parent
);
}
for (parent, children) in &self.children {
for child in children {
assert_eq!(
self.parent.get(child),
Some(parent),
"parent {:?} lists child {:?}, but child's parent pointer is {:?}",
parent,
child,
self.parent.get(child)
);
}
}
for root in &self.roots {
assert!(
!self.parent.contains_key(root),
"root {:?} has a parent pointer",
root
);
}
for node in &self.insertion_order {
if !self.parent.contains_key(node) {
assert!(
self.roots.contains(node),
"node {:?} has no parent but is not a root",
node
);
}
}
for (parent, children) in &self.children {
let unique: HashSet<&N> = children.iter().collect();
assert_eq!(
unique.len(),
children.len(),
"parent {:?} has duplicate children",
parent
);
}
let unique_roots: HashSet<&N> = self.roots.iter().collect();
assert_eq!(unique_roots.len(), self.roots.len(), "duplicate roots");
let reachable = self.all_reachable_from_roots();
for node in &self.insertion_order {
assert!(
reachable.contains(node),
"node {:?} is in insertion_order but not reachable from any root",
node
);
}
for node in &reachable {
assert!(
self.insertion_order.contains(node),
"node {:?} is reachable from roots but missing from insertion_order",
node
);
}
}
fn all_reachable_from_roots(&self) -> HashSet<N> {
let mut reachable = HashSet::new();
for root in &self.roots {
self.collect_reachable(root, &mut reachable);
}
reachable
}
fn collect_reachable(&self, node: &N, reachable: &mut HashSet<N>) {
if !reachable.insert(node.clone()) {
return; }
if let Some(children) = self.children.get(node) {
for child in children {
self.collect_reachable(child, reachable);
}
}
}
}
#[derive(Clone, Debug)]
pub struct TreeRow<'a, N: MemberId> {
pub member: &'a N,
pub depth: usize,
pub is_expanded: bool,
pub has_children: bool,
pub is_last_sibling: bool,
pub subgraph_id: Option<SubgraphId>,
}
#[derive(Clone, Debug)]
pub enum PlacementPolicy {
ChildOfConnection,
SiblingOfConnection,
ChildOfAnchor,
}
pub fn derive_topology<N, E, Ix>(
graph: &petgraph::Graph<N, E, petgraph::Directed, Ix>,
roots: &[petgraph::graph::NodeIndex<Ix>],
selector: impl Fn(&E) -> bool,
policy: &PlacementPolicy,
) -> TreeTopology<N>
where
N: MemberId,
Ix: petgraph::graph::IndexType,
{
use petgraph::visit::EdgeRef;
use std::collections::VecDeque;
let mut topo = TreeTopology::new();
let mut visited: HashSet<petgraph::graph::NodeIndex<Ix>> = HashSet::new();
let weight = |idx: petgraph::graph::NodeIndex<Ix>| -> &N { &graph[idx] };
let mut queue: VecDeque<petgraph::graph::NodeIndex<Ix>> = VecDeque::new();
for &root_idx in roots {
if visited.insert(root_idx) {
topo.attach_root(weight(root_idx).clone());
queue.push_back(root_idx);
}
}
while let Some(current_idx) = queue.pop_front() {
for edge in graph.edges(current_idx) {
if !selector(edge.weight()) {
continue;
}
let target_idx = edge.target();
if !visited.insert(target_idx) {
continue;
}
let target = weight(target_idx).clone();
let current = weight(current_idx).clone();
match policy {
PlacementPolicy::ChildOfConnection => {
topo.attach_child(target, ¤t);
},
PlacementPolicy::SiblingOfConnection => {
topo.attach_sibling(target, ¤t);
},
PlacementPolicy::ChildOfAnchor => {
let mut ancestor = current.clone();
while let Some(p) = topo.parent_of(&ancestor) {
ancestor = p.clone();
}
topo.attach_child(target, &ancestor);
},
}
queue.push_back(target_idx);
}
}
topo
}
#[cfg(test)]
mod tests;