1 files changed, 103 insertions, 0 deletions
diff --git a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs
new file mode 100644
index 00000000..44165ed1
--- /dev/null
+++ b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs
@@ -0,0 +1,103 @@
+use std::collections::HashMap;
+
+use super::{error, Mapping};
+
+/// A prefix tree
+pub struct MappingTree {
+    root: Node,
+}
+
+#[derive(Clone)]
+pub struct Node {
+    children: HashMap<char, Node>,
+    value: Option<Mapping>,
+
+    /// The key needed to get to this node
+    location: String,
+}
+
+impl MappingTree {
+    pub fn new() -> Self {
+        Self {
+            root: Node::new(String::new(), None),
+        }
+    }
+
+    /// Returns the node at the key, otherwise None
+    pub fn get(&self, key: &str) -> Option<&Node> {
+        let mut current_node = &self.root;
+        for ch in key.chars() {
+            current_node = current_node.children.get(&ch)?
+        }
+
+        Some(current_node)
+    }
+    /// Returns the node at the key, otherwise None. The node can be changed
+    pub fn get_mut(&mut self, key: &str) -> Option<&mut Node> {
+        let mut current_node = &mut self.root;
+        for ch in key.chars() {
+            current_node = current_node.children.get_mut(&ch)?
+        }
+
+        Some(current_node)
+    }
+
+    /// Returns the node at the key, otherwise the last node that matched.
+    pub fn try_get(&self, key: &str) -> &Node {
+        let mut current_node = &self.root;
+        for ch in key.chars() {
+            if let Some(node) = current_node.children.get(&ch) {
+                current_node = node;
+            } else {
+                return current_node;
+            }
+        }
+
+        current_node
+    }
+
+    pub fn insert(&mut self, key: &str, mapping: Mapping) -> Result<(), error::Error> {
+        let node = self.try_get(key).clone();
+        if node.location.as_str() != key {
+            let needed_nodes_key = key.trim_start_matches(node.location.as_str());
+            let needed_nodes_length = needed_nodes_key.chars().count();
+
+            let mut current_node = self
+                .get_mut(&node.location)
+                .expect("This should always exists");
+            let mut current_location = node.location.clone();
+            let mut counter = 0;
+
+            for ch in needed_nodes_key.chars() {
+                current_location.push(ch);
+
+                let next_node = if counter == needed_nodes_length {
+                    Node::new(current_location.clone(), Some(mapping.clone()))
+                } else {
+                    Node::new(current_location.clone(), None)
+                };
+
+                current_node.children.insert(ch, next_node);
+                current_node = current_node
+                    .children
+                    .get_mut(&ch)
+                    .expect("Was just inserted");
+                counter += 1;
+            }
+        } else {
+            return Err(error::Error::NodeExits(key.to_owned()));
+        }
+
+        Ok(())
+    }
+}
+
+impl Node {
+    pub fn new(location: String, mapping: Option<Mapping>) -> Self {
+        Self {
+            children: HashMap::new(),
+            location,
+            value: mapping,
+        }
+    }
+}