use crate::{
id::PersyId,
index::config::IndexTypeInternal,
index::keeper::IndexKeeper,
index::tree::nodes::{Leaf, Node, NodeRef, Nodes, Value},
inspect::{TreeInspector, TreeInspectorResult},
};
pub(crate) fn inspect_tree<K, V, I>(tree: &mut dyn IndexKeeper<K, V>, inspector: &mut I) -> TreeInspectorResult<()>
where
K: IndexTypeInternal,
V: IndexTypeInternal,
I: TreeInspector<K::Wrapped, V::Wrapped>,
{
let root = tree.get_root()?;
if let Some(r) = root {
inspect_node(tree, &r, inspector)?;
} else {
inspector.empty()?;
}
Ok(())
}
fn inspect_node<K, V, I>(tree: &mut dyn IndexKeeper<K, V>, node: &NodeRef, inspector: &mut I) -> TreeInspectorResult<()>
where
K: IndexTypeInternal,
V: IndexTypeInternal,
I: TreeInspector<K::Wrapped, V::Wrapped>,
{
match tree.failable_load(node)? {
Some(Node::Node(n)) => {
inspector.start_node(
PersyId(node.clone()),
n.get_prev().clone().map(|k| k.unwrap()),
n.get_next().clone().map(|k| k.unwrap()),
)?;
inspect_nodes(tree, &n, inspector)?;
inspector.end_node(PersyId(node.clone()))?;
}
Some(Node::Leaf(l)) => {
inspector.start_leaf(
PersyId(node.clone()),
l.get_prev().clone().map(|k| k.unwrap()),
l.get_next().clone().map(|k| k.unwrap()),
)?;
inspect_leaf(tree, &l, inspector)?;
inspector.end_leaf(PersyId(node.clone()))?;
}
None => {
inspector.failed_load(PersyId(node.clone()))?;
}
}
Ok(())
}
fn inspect_nodes<K, V, I>(
tree: &mut dyn IndexKeeper<K, V>,
node: &Nodes<K>,
inspector: &mut I,
) -> TreeInspectorResult<()>
where
K: IndexTypeInternal,
V: IndexTypeInternal,
I: TreeInspector<K::Wrapped, V::Wrapped>,
{
for i in 0..node.len() {
if i != 0 {
inspector.start_key(i as u32, node.keys[i - 1].clone().unwrap())?
}
inspect_node(tree, &node.pointers[i], inspector)?;
if i != 0 {
inspector.end_key(i as u32, node.keys[i - 1].clone().unwrap())?
}
}
Ok(())
}
fn inspect_leaf<K, V, I>(
tree: &mut dyn IndexKeeper<K, V>,
leaf: &Leaf<K, V>,
inspector: &mut I,
) -> TreeInspectorResult<()>
where
K: IndexTypeInternal,
V: IndexTypeInternal,
I: TreeInspector<K::Wrapped, V::Wrapped>,
{
for i in 0..leaf.len() {
inspector.start_key(i as u32, leaf.entries[i].key.clone().unwrap())?;
inspect_values(tree, &leaf.entries[i].value, inspector)?;
inspector.end_key(i as u32, leaf.entries[i].key.clone().unwrap())?;
}
Ok(())
}
fn inspect_values<K, V, I>(
_tree: &mut dyn IndexKeeper<K, V>,
value: &Value<V>,
inspector: &mut I,
) -> TreeInspectorResult<()>
where
K: IndexTypeInternal,
V: IndexTypeInternal,
I: TreeInspector<K::Wrapped, V::Wrapped>,
{
match value {
Value::Cluster(x) => {
for i in 0..x.len() {
inspector.value(i as u32, x[i].clone().unwrap())?;
}
}
Value::Single(v) => {
inspector.value(0, v.clone().unwrap())?;
}
}
Ok(())
}
pub struct PrintTreeInspector {
depth: usize,
padding: String,
in_leaf: bool,
count: u32,
print_leaf: bool,
}
impl<'a> PrintTreeInspector {
#[allow(dead_code)]
pub fn new_print_leaf() -> Self {
Self {
depth: 0,
padding: String::new(),
in_leaf: false,
count: 0,
print_leaf: true,
}
}
#[allow(dead_code)]
pub fn new() -> Self {
Self {
depth: 0,
padding: String::new(),
in_leaf: false,
count: 0,
print_leaf: false,
}
}
fn write(&mut self, data: String) -> TreeInspectorResult<()> {
println!("{}{}", self.padding, data);
Ok(())
}
fn inc_depth(&mut self) {
self.depth += 1;
let mut padding = String::new();
for _x in 0..self.depth {
padding.push_str("┆ ".into());
}
self.padding = padding;
}
fn dec_depth(&mut self) {
self.depth -= 1;
let mut padding = String::new();
for _x in 0..self.depth {
padding.push_str("┆ ".into());
}
self.padding = padding;
}
}
impl<'a, K, V> TreeInspector<K, V> for PrintTreeInspector
where
K: std::fmt::Display,
V: std::fmt::Display,
{
fn start_node(&mut self, node_id: PersyId, prev: Option<K>, next: Option<K>) -> TreeInspectorResult<()> {
self.write(format!(
"({}) PREV-KEY:{}, NEXT-KEY:{}",
node_id,
prev.map(|k| format!("Some({})", k)).unwrap_or("None".to_owned()),
next.map(|k| format!("Some({})", k)).unwrap_or("None".to_owned())
))?;
self.write(format!("├──┐"))?;
self.inc_depth();
Ok(())
}
fn end_node(&mut self, _node_id: PersyId) -> TreeInspectorResult<()> {
self.dec_depth();
self.write(format!("├──┘"))?;
Ok(())
}
fn start_leaf(&mut self, node_id: PersyId, prev: Option<K>, next: Option<K>) -> TreeInspectorResult<()> {
self.write(format!(
"├──┐ ({}) PREV-KEY:{}, NEXT-KEY:{}",
node_id,
prev.map(|k| format!("Some({})", k)).unwrap_or("None".to_owned()),
next.map(|k| format!("Some({})", k)).unwrap_or("None".to_owned())
))?;
self.inc_depth();
self.in_leaf = true;
Ok(())
}
fn end_leaf(&mut self, _node_id: PersyId) -> TreeInspectorResult<()> {
self.dec_depth();
self.write(format!("├──┘ ({})", self.count))?;
self.count = 0;
self.in_leaf = false;
Ok(())
}
fn start_key(&mut self, _node_pos: u32, k: K) -> TreeInspectorResult<()> {
if !self.in_leaf || self.print_leaf {
self.write(format!("├──{}", k))?;
}
Ok(())
}
fn end_key(&mut self, _node_pos: u32, _k: K) -> TreeInspectorResult<()> {
Ok(())
}
fn value(&mut self, _node_pos: u32, v: V) -> TreeInspectorResult<()> {
if self.print_leaf {
self.write(format!("│ {}", v))?;
}
self.count += 1;
Ok(())
}
fn failed_load(&mut self, node_id: PersyId) -> TreeInspectorResult<()> {
self.write(format!("│ FAILED({}) ", node_id))?;
Ok(())
}
fn empty(&mut self) -> TreeInspectorResult<()> {
self.write("───────EMTPY───────".to_owned())?;
Ok(())
}
}