use std::{collections::HashMap, mem};
use anyhow::{bail, Result};
use log::debug;
use self::iterator::MappingTreeIterator;
use super::MapKey;
pub mod display;
pub mod iterator;
pub mod lf_mapping;
/// A prefix tree
#[derive(Debug)]
pub struct MappingTree {
root: Node,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum NodeValue {
Parent { children: HashMap<MapKey, Node> },
Child { path: String, extandable: bool },
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Node {
value: NodeValue,
}
impl MappingTree {
pub fn new() -> Self {
Self {
root: Node::new_parent(),
}
}
pub fn root_node(&self) -> &Node {
&self.root
}
pub fn iter(&self, ignore_extendable: bool) -> MappingTreeIterator {
MappingTreeIterator::new(&self, ignore_extendable)
}
/// Returns the node at the key, otherwise None. The node can be changed
pub fn get_mut(&mut self, key: &[MapKey]) -> Option<&mut Node> {
let mut current_node = &mut self.root;
for ch in key.iter() {
if let NodeValue::Parent { children } = &mut current_node.value {
current_node = children.get_mut(&ch)?
} else {
return None;
}
}
Some(current_node)
}
/// Returns the node at the key, otherwise the last node that matched.
pub fn try_get(&self, key: &[MapKey]) -> (&Node, Vec<MapKey>) {
let mut current_node = &self.root;
let mut current_key = vec![];
for ch in key.iter() {
if let NodeValue::Parent { children } = ¤t_node.value {
current_node = if let Some(node) = children.get(&ch) {
let (key, _value) = children
.get_key_value(&ch)
.expect("This exists, we checked");
current_key.push(key.clone());
node
} else {
return (current_node, current_key);
};
} else {
return (current_node, current_key);
}
}
(current_node, current_key)
}
pub fn include(&mut self, path: &str) -> Result<()> {
let associated_key = MapKey::new_ones_from_path(path, 1);
self.insert(&associated_key, path)
}
pub fn insert(&mut self, key: &[MapKey], path: &str) -> Result<()> {
self.insert_node(key, Node::new_child(path.to_owned()))
}
pub fn interleave(&mut self, key: &[MapKey], node: Node) -> Result<()> {
let want_to_be_parent = self.get_mut(&key).expect("This value exists");
let (parent_value, _parent_children) = if let NodeValue::Parent { children } = node.value {
(
NodeValue::Parent {
children: children.clone(),
},
children,
)
} else {
unreachable!("This value will be a parent")
};
let child_value = mem::replace(&mut want_to_be_parent.value, parent_value);
assert!(matches!(
child_value,
NodeValue::Child {
path: _,
extandable: _
}
));
let child_value = if let NodeValue::Child {
path,
extandable: _,
} = child_value
{
NodeValue::Child {
path,
extandable: false,
}
} else {
unreachable!("This is only a child value")
};
let child = Node { value: child_value };
let mut new_key = key.to_vec();
new_key.push(MapKey {
key: '.',
part_path: ".".to_owned(),
resolution: 1,
});
self.insert_node(&new_key, child)?;
Ok(())
}
pub fn insert_node(&mut self, key: &[MapKey], node: Node) -> Result<()> {
let (_node, found_key) = self.try_get(key).clone();
if found_key != key {
let needed_nodes_key = key
.strip_prefix(&found_key[..])
.expect("The node's location is a prefix");
let needed_nodes_length = needed_nodes_key.iter().count();
let mut current_node = self
.get_mut(&found_key[..])
.expect("This should always exists");
let mut current_location = found_key.clone();
let mut counter = 1;
for ch in needed_nodes_key.iter() {
current_location.push(ch.to_owned());
let next_node = if counter == needed_nodes_length {
node.clone()
} else {
Node::new_parent()
};
current_node = match ¤t_node.value {
NodeValue::Parent { children } => {
assert_eq!(children.get(&ch), None);
let children =
if let NodeValue::Parent { children } = &mut current_node.value {
children
} else {
unreachable!("This is a parent, we cheched")
};
children.insert(ch.to_owned(), next_node);
children.get_mut(&ch).expect("Was just inserted")
}
NodeValue::Child {
path,
extandable: _,
} => {
// A node that should be a parent was classified
// as child before:
//
// 1. Remove the child node and replace it with a parent one.
// 2. Add the child node to the parent node as child, but with a '.' as MapKey.
// 3. Add the original node also as child to the parent node.
let mut children = HashMap::new();
let move_child_node = Node::new_child(path.to_owned());
children.insert(
MapKey {
key: '.',
part_path: ".".to_owned(),
resolution: 1,
},
move_child_node,
);
children.insert(ch.to_owned(), next_node);
current_node.value = NodeValue::Parent { children };
let children =
if let NodeValue::Parent { children } = &mut current_node.value {
children
} else {
unreachable!("We just inserted the parent value.")
};
children.get_mut(&ch).expect("Was just inserted")
}
};
counter += 1;
}
} else {
fn reduce_string(a: &str) -> Option<char> {
let first_char = a.chars().take(1).last().expect("Should contain one char");
if a.chars().all(|ch| ch == first_char) {
return Some(first_char);
} else {
return None;
}
}
fn check_subset(a: &str, b: &str) -> bool {
if a.len() > b.len() {
let a_prefix: String = a.chars().take(b.len()).collect();
let a_suffix: String = a.chars().skip(b.len()).collect();
if a_prefix == b {
let clean_suffix = reduce_string(&a_suffix);
if let Some(ch) = clean_suffix {
ch == b.chars().last().expect("Will match")
} else {
false
}
} else {
false
}
} else if b.len() > a.len() {
let b_prefix: String = b.chars().take(a.len()).collect();
let b_suffix: String = b.chars().skip(a.len()).collect();
if b_prefix == a {
let clean_suffix = reduce_string(&b_suffix);
if let Some(ch) = clean_suffix {
ch == a.chars().last().expect("Will match")
} else {
false
}
} else {
false
}
} else {
a == b
}
}
// Another node was already inserted with the same key!
// So we simple increase the resolution of the other node and this node, until their
// keys are not the same anymore.
// This only includes the last segment of the `MapKey`
//
// 1. Change both keys, until they are not equal any more
// 2. Move the wrongly placed node to the new place.
// 3. Insert our node.
let mut foreign_key = vec![found_key.last().expect("This will exist").clone()];
let mut our_key = vec![key.last().expect("This will exist").clone()];
debug!(
"'{}' ('{}') and '{}' ('{}') are the same, try to find a better combination!",
MapKey::display(&our_key),
our_key[0].part_path,
MapKey::display(&foreign_key),
foreign_key[0].part_path,
);
// The 'a' and 'b' stuff is here, to ensure that both returning None will not match
// this condition.
if reduce_string(&foreign_key[0].part_path).unwrap_or('a')
== reduce_string(&our_key[0].part_path).unwrap_or('b')
{
bail!(
"\
The foreign_key ('{}', path_part: '{}' -> '{}') and our_key ('{}', path_part: '{}' -> '{}') \
have an identical path_part (when duplicated chars are removed)!
I cannot extended them via incrementation.
Please rename the paths to fix this.
",
MapKey::display(&foreign_key),
&foreign_key[0].part_path,
reduce_string(&foreign_key[0].part_path).expect("Is some here"),
MapKey::display(&our_key),
&our_key[0].part_path,
reduce_string(&our_key[0].part_path).expect("Is some here"),
);
}
if check_subset(&foreign_key[0].part_path, &our_key[0].part_path) {
bail!(
"\
The foreign_key ('{}', path_part: '{}') and our_key ('{}', path_part: '{}') \
are subsets of one another!
A discrimination through incrementation will not work!
Please rename the paths to fix this.
",
MapKey::display(&foreign_key),
&foreign_key[0].part_path,
MapKey::display(&our_key),
&our_key[0].part_path,
);
}
while our_key == foreign_key {
our_key = our_key[0].increment(our_key[our_key.len() - 1].resolution + 1);
foreign_key =
foreign_key[0].increment(foreign_key[foreign_key.len() - 1].resolution + 1);
debug!(
"Now its: '{}' ('{}') and '{}' ('{}')",
MapKey::display(&our_key),
our_key[0].part_path,
MapKey::display(&foreign_key),
foreign_key[0].part_path,
);
}
debug!(
"Found a better one: '{}' ('{}') and '{}' ('{}')",
MapKey::display(&our_key),
our_key[0].part_path,
MapKey::display(&foreign_key),
foreign_key[0].part_path,
);
let parent = self
.get_mut(&found_key[..&found_key.len() - 1])
.expect("This will exist");
if let NodeValue::Parent { children } = &mut parent.value {
if let NodeValue::Child {
path: _,
extandable: _,
} = children
.get(found_key.last().expect("Exists"))
.expect("This node also exists")
.value
{
let old = children
.remove(found_key.last().expect("This will exist"))
.expect("This will be there");
let full_foreign_key: Vec<_> = found_key
.clone()
.into_iter()
.rev()
.skip(1)
.rev()
.chain(foreign_key.clone().into_iter())
.collect();
self.insert_node(&full_foreign_key, old.clone())?;
}
let full_our_key: Vec<_> = key
.to_vec()
.into_iter()
.rev()
.skip(1)
.rev()
.chain(our_key.clone().into_iter())
.collect();
self.insert_node(&full_our_key, node.clone())?;
} else {
unreachable!("This node will be a parent");
}
}
Ok(())
}
}
impl Node {
pub fn new_child(path: String) -> Self {
Self {
value: NodeValue::Child {
path,
extandable: true,
},
}
}
pub fn new_parent() -> Self {
Self {
value: NodeValue::Parent {
children: HashMap::new(),
},
}
}
}