diff options
Diffstat (limited to 'pkgs/sources/lf-make-map/src/mapping/map_tree/mod.rs')
| -rw-r--r-- | pkgs/sources/lf-make-map/src/mapping/map_tree/mod.rs | 402 |
1 files changed, 0 insertions, 402 deletions
diff --git a/pkgs/sources/lf-make-map/src/mapping/map_tree/mod.rs b/pkgs/sources/lf-make-map/src/mapping/map_tree/mod.rs deleted file mode 100644 index 35e6d91d..00000000 --- a/pkgs/sources/lf-make-map/src/mapping/map_tree/mod.rs +++ /dev/null @@ -1,402 +0,0 @@ -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(), - }, - } - } -} |