pkgs/lf-make-map: Use trinitrix's keymaps library

The library was largely modelled after the previously used
`MappingTrie`. Thus using that results in code deduplication.

9 files changed, 511 insertions, 753 deletions

diff --git a/pkgs/by-name/lf/lf-make-map/Cargo.lock b/pkgs/by-name/lf/lf-make-map/Cargo.lock
index bcc7853c..51cbf6ad 100644
--- a/pkgs/by-name/lf/lf-make-map/Cargo.lock
+++ b/pkgs/by-name/lf/lf-make-map/Cargo.lock
@@ -1,3 +1,5 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
 # nixos-config - My current NixOS configuration
 #
 # Copyright (C) 2025 Benedikt Peetz <benedikt.peetz@b-peetz.de>
@@ -7,9 +9,6 @@
 #
 # You should have received a copy of the License along with this program.
 # If not, see <https://www.gnu.org/licenses/gpl-3.0.txt>.
-
-# This file is automatically @generated by Cargo.
-# It is not intended for manual editing.
 version = 4
 
 [[package]]
@@ -240,11 +239,21 @@ dependencies = [
 ]
 
 [[package]]
+name = "keymaps"
+version = "1.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2a522bbaa39bddd54945580e369ed37113ea96f4cb8f0322be0d5e04aa4d7293"
+dependencies = [
+ "thiserror",
+]
+
+[[package]]
 name = "lf-make-map"
 version = "0.1.0"
 dependencies = [
  "anyhow",
  "clap",
+ "keymaps",
  "log",
  "stderrlog",
  "walkdir",
@@ -337,9 +346,9 @@ checksum = "7da8b5736845d9f2fcb837ea5d9e2628564b3b043a70948a3f0b778838c5fb4f"
 
 [[package]]
 name = "syn"
-version = "2.0.100"
+version = "2.0.101"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b09a44accad81e1ba1cd74a32461ba89dee89095ba17b32f5d03683b1b1fc2a0"
+checksum = "8ce2b7fc941b3a24138a0a7cf8e858bfc6a992e7978a068a5c760deb0ed43caf"
 dependencies = [
  "proc-macro2",
  "quote",
@@ -356,6 +365,26 @@ dependencies = [
 ]
 
 [[package]]
+name = "thiserror"
+version = "2.0.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "567b8a2dae586314f7be2a752ec7474332959c6460e02bde30d702a66d488708"
+dependencies = [
+ "thiserror-impl",
+]
+
+[[package]]
+name = "thiserror-impl"
+version = "2.0.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7f7cf42b4507d8ea322120659672cf1b9dbb93f8f2d4ecfd6e51350ff5b17a1d"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
 name = "thread_local"
 version = "1.1.8"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/pkgs/by-name/lf/lf-make-map/Cargo.toml b/pkgs/by-name/lf/lf-make-map/Cargo.toml
index 66611590..22860e12 100644
--- a/pkgs/by-name/lf/lf-make-map/Cargo.toml
+++ b/pkgs/by-name/lf/lf-make-map/Cargo.toml
@@ -12,13 +12,14 @@
 name = "lf-make-map"
 description = "An automatic lf cd mapping generator"
 version = "0.1.0"
-edition = "2021"
+edition = "2024"
 
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
 
 [dependencies]
-anyhow = "1.0.97"
-clap = { version = "4.5.35", features = ["derive", "env"] }
+anyhow = "1.0.98"
+clap = { version = "4.5.37", features = ["derive", "env"] }
+keymaps = "1.1.1"
 log = "0.4.27"
 stderrlog = "0.6.0"
 walkdir = "2.5.0"
diff --git a/pkgs/by-name/lf/lf-make-map/src/main.rs b/pkgs/by-name/lf/lf-make-map/src/main.rs
index d3cc9f6f..d5d934e1 100644
--- a/pkgs/by-name/lf/lf-make-map/src/main.rs
+++ b/pkgs/by-name/lf/lf-make-map/src/main.rs
@@ -14,10 +14,10 @@ use anyhow::{Context, Result};
 use clap::Parser;
 use cli::{Args, Command};
 use log::trace;
-use mapping::map_tree::MappingTree;
+use mapping::map_key::MapKey;
 use walkdir::{DirEntry, WalkDir};
 
-use crate::mapping::MapKey;
+use crate::mapping::MappingsTrie;
 
 mod cli;
 mod mapping;
@@ -34,7 +34,7 @@ fn main() -> anyhow::Result<()> {
         .timestamp(stderrlog::Timestamp::Off)
         .init()?;
 
-    let mut mappings = MappingTree::new();
+    let mut mappings = MappingsTrie::new();
 
     let relevant_directories = match &args.command {
         Command::Visualize { options } => &options.relevant_directories,
@@ -42,68 +42,62 @@ fn main() -> anyhow::Result<()> {
     };
 
     for dir in relevant_directories {
-        trace!("Processing '{}'..", dir.display());
-        let path = strip_path(&dir, &args.home_name)?;
+        trace!("START Processing '{}'..", dir.display());
+        let path = strip_path(dir, &args.home_name)?;
 
         mappings
             .include(path_to_str(path)?)
             .with_context(|| format!("Failed to include path: '{}'", path.display()))?;
+        trace!("END Finished processing {}.", dir.display());
+    }
+
+    trace!("Generated mappings for the relevant directories. Starting expanding to max depth.");
+    if log::log_enabled!(log::Level::Trace) {
+        eprintln!("{mappings}");
     }
 
     let home = path_to_str(&args.home_name)?.to_owned();
 
     let mut current_depth = 1;
     while current_depth != args.depth {
-        for (key, value) in mappings.iter(false) {
-            trace!(
-                "Adding to child ('{}' -> '{}')",
-                MapKey::display(&key),
-                value
-            );
+        for (keys, child) in mappings.0.iter().filter(|(_, child)| child.expendable) {
+            trace!("Adding to child '{}' ('{}')", MapKey::display(&keys), child);
 
-            let mut local_mappings = MappingTree::new();
-            for dir in WalkDir::new(extend(&home, &value)?)
+            let mut local_mappings = MappingsTrie::new();
+            for dir in WalkDir::new(extend(&home, &child.path)?)
                 .min_depth(1)
                 .max_depth(1)
                 .into_iter()
                 .filter_entry(|e| is_dir(e) && !is_hidden(e))
             {
-                let directory = dir
-                    .with_context(|| format!("Failed to read dir ('{}')", home.clone() + &value))?;
-                let path_to_strip = &PathBuf::from(extend(&home, &value)?);
-                let path = strip_path(&directory.path(), &path_to_strip)?;
+                let directory = dir.with_context(|| {
+                    format!("Failed to read dir ('{}')", home.clone() + &child.path)
+                })?;
+                let path_to_strip = &PathBuf::from(extend(&home, &child.path)?);
+                let path = strip_path(directory.path(), path_to_strip)?;
                 trace!(
-                    "Including: '{}' (after stripping '{}' from '{}' -> '{}' + '/' + '{}')",
+                    "Including: '{}' (after stripping '{}' from '{}')",
                     path.display(),
-                    directory.path().display(),
                     path_to_strip.display(),
-                    home,
-                    value
+                    directory.path().display(),
                 );
 
                 let gen_key = MapKey::new_ones_from_path(path_to_str(path)?, 1);
                 local_mappings
                     .insert(
                         &gen_key,
-                        path_to_str(strip_path(&directory.path(), &PathBuf::from(&home))?)?,
+                        path_to_str(strip_path(directory.path(), &PathBuf::from(&home))?)?,
                     )
                     .with_context(|| format!("Failed to include path: '{}'", path.display()))?;
             }
 
-            trace!("{}", local_mappings);
-
-            trace!(
-                "'{}' -> '{:#?}'",
-                MapKey::display(&key),
-                local_mappings.root_node()
-            );
-            mappings.interleave(&key, local_mappings.root_node().to_owned())?;
+            mappings.add_trie(&keys, local_mappings)?;
         }
         current_depth += 1;
     }
 
     match args.command {
-        Command::Visualize { .. } => println!("{}", mappings),
+        Command::Visualize { .. } => println!("{}", mappings.0),
         Command::Generate { .. } => println!("{}", mappings.to_lf_mappings(args.home_name)),
     }
 
@@ -130,7 +124,7 @@ fn is_dir(entry: &DirEntry) -> bool {
 }
 
 fn strip_path<'a>(path: &'a Path, to_strip: &Path) -> Result<&'a Path> {
-    path.strip_prefix(&to_strip).with_context(|| {
+    path.strip_prefix(to_strip).with_context(|| {
         format!(
             "'{}' is not under the specified home path ('{}')!",
             path.display(),
diff --git a/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/lf_mapping.rs b/pkgs/by-name/lf/lf-make-map/src/mapping/lf_mapping.rs
index f6ba2c43..f8a6182e 100644
--- a/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/lf_mapping.rs
+++ b/pkgs/by-name/lf/lf-make-map/src/mapping/lf_mapping.rs
@@ -12,17 +12,18 @@ use std::path::PathBuf;
 
 use crate::mapping::MapKey;
 
-use super::MappingTree;
+use super::MappingsTrie;
 
-impl MappingTree {
-    pub fn to_lf_mappings(self, home_path: PathBuf) -> String {
+impl MappingsTrie {
+    pub fn to_lf_mappings(&self, home_path: PathBuf) -> String {
         let mut raw = self
-            .iter(true)
+            .0
+            .iter()
             .map(|(key, value)| {
                 format!(
                     "map g{} cd \"{}\"\n",
                     MapKey::display(&key),
-                    home_path.join(&value).display()
+                    home_path.join(&value.path).display()
                 )
             })
             .collect::<Vec<String>>();
diff --git a/pkgs/by-name/lf/lf-make-map/src/mapping/map_key.rs b/pkgs/by-name/lf/lf-make-map/src/mapping/map_key.rs
new file mode 100644
index 00000000..e66a1635
--- /dev/null
+++ b/pkgs/by-name/lf/lf-make-map/src/mapping/map_key.rs
@@ -0,0 +1,264 @@
+use std::fmt::Write;
+
+use anyhow::bail;
+use log::debug;
+
+#[derive(Clone, Debug)]
+pub struct MapKey {
+    pub key: char,
+
+    pub(crate) resolution: usize,
+
+    /// Part of the path, used to derive the key
+    pub(crate) part_path: String,
+}
+
+impl std::hash::Hash for MapKey {
+    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
+        self.key.hash(state)
+    }
+}
+
+impl Eq for MapKey {}
+impl PartialEq for MapKey {
+    fn eq(&self, other: &Self) -> bool {
+        self.key == other.key
+    }
+}
+
+impl Ord for MapKey {
+    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+        self.key.cmp(&other.key)
+    }
+}
+impl PartialOrd for MapKey {
+    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl MapKey {
+    pub fn new_from_part_path(part_path: &str, resolution: usize) -> Vec<Self> {
+        let key = Self::part_path_to_key(part_path, resolution);
+
+        key.chars()
+            .map(|ch| Self {
+                key: ch,
+                resolution,
+                part_path: part_path.to_owned(),
+            })
+            .collect()
+    }
+
+    pub fn new_ones_from_path(path: &str, number_of_chars: usize) -> Vec<Self> {
+        let key: Vec<MapKey> = path
+            .split('/')
+            .flat_map(|part| Self::new_from_part_path(part, number_of_chars))
+            .collect();
+
+        debug!(
+            "Generated full MapKeys: '{}' -> '{}'",
+            path,
+            MapKey::display(&key)
+        );
+        key
+    }
+
+    pub fn increment(&self, target_resolution: usize) -> Vec<Self> {
+        let new_resolution = target_resolution;
+
+        // debug!("Incrementing: '{}' ('{}')", &self, &self.part_path);
+
+        let added_chars = if new_resolution < self.part_path.len() {
+            MapKey::part_path_to_key(&self.part_path, new_resolution)
+        } else {
+            let mut generated_chars =
+                MapKey::part_path_to_key(&self.part_path, self.part_path.len());
+
+            generated_chars.extend(
+                (0..(new_resolution - self.part_path.len()))
+                    .into_iter()
+                    .map(|_| self.part_path.chars().last().expect("This will exists")),
+            );
+
+            generated_chars
+        };
+
+        let part_path = self.part_path.clone();
+        let output: Vec<Self> = added_chars
+            .chars()
+            .enumerate()
+            .map(|(res, ch)| MapKey {
+                key: ch,
+                resolution: res + 1,
+                part_path: part_path.clone(),
+            })
+            .collect();
+
+        // debug!("Finished increment: '{}' ('{}')", MapKey::display(&output), output[0].part_path);
+        output
+    }
+
+    pub fn display(values: &[Self]) -> String {
+        values.iter().map(|value| value.key.clone()).collect()
+    }
+
+    fn part_path_to_key(part: &str, number_of_chars: usize) -> String {
+        fn make(pat: char, part: &str, number_of_chars: usize) -> String {
+            let mut acc = String::new();
+
+            if !part.split(pat).all(|part| part.len() > 0) {
+                panic!(
+                    "\
+Can't turn this path '{}' to a mapping.
+This should not happen, please report the bug!",
+                    part
+                )
+            }
+
+            let mut last_working = None;
+            for i in 0..number_of_chars {
+                for str in part.split(pat) {
+                    if acc.len() != number_of_chars {
+                        acc.push(match str.chars().nth(i) {
+                            Some(ch) => ch,
+                            None => {
+                                if let Some(last) = last_working {
+                                    str.chars().nth(last).expect("This should always exist")
+                                } else {
+                                    last_working = Some(i - 1);
+                                    str.chars().nth(i - 1).expect("This should always exist")
+                                }
+                            }
+                        })
+                    }
+                }
+            }
+
+            acc
+        }
+
+        let value = if part.contains('_') && !part.starts_with('_') && !part.ends_with('_') {
+            make('_', part, number_of_chars)
+        } else if part.contains('-') && !part.starts_with('-') && !part.ends_with('-') {
+            make('-', part, number_of_chars)
+        } else {
+            part.chars().take(number_of_chars).collect::<String>()
+        };
+
+        assert_eq!(
+            value.len(),
+            number_of_chars,
+            "'{}' does not have expected length of: {}",
+            value,
+            number_of_chars
+        );
+        value
+    }
+
+    /// Checks whether a tiebreak via the [`Self::increment`] function can result in unique keys.
+    pub fn can_tiebreak_with(&self, other: &Self) -> anyhow::Result<()> {
+        /// Check whether the `input` &str is composed of only one character.
+        /// If so, returns this character, otherwise returns None.
+        fn reduce_string(input: &str) -> Option<char> {
+            let first_char = input
+                .chars()
+                .take(1)
+                .last()
+                .expect("Should contain one char");
+
+            if input.chars().all(|ch| ch == first_char) {
+                Some(first_char)
+            } else {
+                None
+            }
+        }
+
+        /// Check whether `a` is a subset of `b` or `b` is a subset of `a`.
+        fn is_subset_either(a: &str, b: &str) -> bool {
+            /// Checks if `subset` is a subset of `set`.
+            ///
+            /// # Examples
+            /// ```
+            /// let a = "a";
+            /// let b = "aa";
+            /// assert!(is_subset(a, b))
+            /// ```
+            ///
+            /// ```
+            /// let a = "abc";
+            /// let b = "def";
+            /// assert!(!is_subset(a, b))
+            /// ```
+            fn is_subset(subset: &str, set: &str) -> bool {
+                let prefix: String = set.chars().take(subset.len()).collect();
+                let suffix: String = set.chars().skip(subset.len()).collect();
+
+                if prefix == subset {
+                    let clean_suffix = reduce_string(&suffix);
+                    if let Some(ch) = clean_suffix {
+                        ch == subset.chars().last().expect("Will exists")
+                    } else {
+                        false
+                    }
+                } else {
+                    false
+                }
+            }
+
+            match a.len().cmp(&b.len()) {
+                std::cmp::Ordering::Less => {
+                    // `b` is the longer string. As such we need to check if `a` is a subset of `b`.
+                    is_subset(a, b)
+                }
+                std::cmp::Ordering::Greater => {
+                    // `a` is the longer string. As such we need to check if `b` is a subset of `a`.
+                    is_subset(b, a)
+                }
+                std::cmp::Ordering::Equal => a == b,
+            }
+        }
+
+        if reduce_string(&other.part_path)
+            .is_some_and(|a| Some(a) == reduce_string(&self.part_path))
+        {
+            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.
+                        ",
+                other,
+                &other.part_path,
+                reduce_string(&other.part_path).expect("Is some here"),
+                self,
+                &self.part_path,
+                reduce_string(&self.part_path).expect("Is some here"),
+            );
+        }
+
+        if is_subset_either(&other.part_path, &self.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.
+                        ",
+                other,
+                &other.part_path,
+                self,
+                &self.part_path,
+            );
+        }
+
+        Ok(())
+    }
+}
+
+impl std::fmt::Display for MapKey {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        f.write_char(self.key)
+    }
+}
diff --git a/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/display.rs b/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/display.rs
deleted file mode 100644
index 4625289a..00000000
--- a/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/display.rs
+++ /dev/null
@@ -1,101 +0,0 @@
-// nixos-config - My current NixOS configuration
-//
-// Copyright (C) 2025 Benedikt Peetz <benedikt.peetz@b-peetz.de>
-// SPDX-License-Identifier: GPL-3.0-or-later
-//
-// This file is part of my nixos-config.
-//
-// You should have received a copy of the License along with this program.
-// If not, see <https://www.gnu.org/licenses/gpl-3.0.txt>.
-
-use std::fmt::Display;
-
-use crate::mapping::{
-    map_tree::{Node, NodeValue},
-    MapKey,
-};
-
-use super::MappingTree;
-
-impl Display for MappingTree {
-    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        fn write_node(
-            f: &mut std::fmt::Formatter<'_>,
-            node: &Node,
-            indention: String,
-            location: Vec<MapKey>,
-            is_last: bool,
-            is_root: bool,
-        ) -> std::fmt::Result {
-            let node_value = match &node.value {
-                NodeValue::Parent { children: _ } => "<Parent>".to_owned(),
-                NodeValue::Child { path, extandable } => {
-                    path.to_owned() + if *extandable { " [exten.]" } else { " [stop]" }
-                }
-            };
-
-            let new_idention = indention.clone()
-                + if is_root {
-                    ""
-                } else {
-                    match is_last {
-                        true => "    ",
-                        false => "│   ",
-                    }
-                };
-
-            let bullet = match is_last {
-                true => String::from("└── "),
-                false => String::from("├── "),
-            };
-
-            if is_root {
-                write!(f, ": {}\n", node_value)?;
-            } else {
-                write!(
-                    f,
-                    "{}{}\x1b[1;33m{}\x1b[0m: {}\n",
-                    indention,
-                    bullet,
-                    MapKey::display(&location),
-                    node_value,
-                )?;
-            };
-
-            match &node.value {
-                NodeValue::Parent { children } => {
-                    let mut children_vec: Vec<(&MapKey, &Node)> = children.iter().collect();
-                    children_vec.sort_by(|(a, _), (b, _)| a.key.cmp(&b.key));
-
-                    let mut counter = 1;
-                    for (key, child) in &children_vec {
-                        let mut new_location = location.clone();
-                        new_location.push((*key).to_owned());
-
-                        write_node(
-                            f,
-                            child,
-                            new_idention.clone(),
-                            new_location.clone(),
-                            counter == children_vec.len(),
-                            false,
-                        )?;
-                        counter += 1;
-                    }
-                }
-                NodeValue::Child {
-                    path: _,
-                    extandable: _,
-                } => {
-                    // Do nothing and stop the recursion
-                }
-            }
-
-            Ok(())
-        }
-
-        write_node(f, &self.root, String::new(), vec![], false, true)?;
-
-        Ok(())
-    }
-}
diff --git a/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/iterator.rs b/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/iterator.rs
deleted file mode 100644
index 7f5ee132..00000000
--- a/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/iterator.rs
+++ /dev/null
@@ -1,63 +0,0 @@
-// nixos-config - My current NixOS configuration
-//
-// Copyright (C) 2025 Benedikt Peetz <benedikt.peetz@b-peetz.de>
-// SPDX-License-Identifier: GPL-3.0-or-later
-//
-// This file is part of my nixos-config.
-//
-// You should have received a copy of the License along with this program.
-// If not, see <https://www.gnu.org/licenses/gpl-3.0.txt>.
-
-use crate::mapping::MapKey;
-
-use super::{MappingTree, Node, NodeValue};
-
-pub struct MappingTreeIterator {
-    children: Vec<(Vec<MapKey>, String)>,
-}
-
-impl MappingTreeIterator {
-    pub fn new(tree: &MappingTree, ignore_extendable: bool) -> Self {
-        let children = extract_child(vec![], &tree.root, ignore_extendable);
-
-        Self { children }
-    }
-}
-
-fn extract_child(
-    current_key: Vec<MapKey>,
-    node: &Node,
-    ignore_extendable: bool,
-) -> Vec<(Vec<MapKey>, String)> {
-    match &node.value {
-        NodeValue::Parent { children } => children
-            .iter()
-            .map(|(key, value)| {
-                let mut new_key = current_key.clone();
-                new_key.push(key.to_owned());
-
-                extract_child(new_key, value, ignore_extendable)
-            })
-            .flatten()
-            .collect(),
-        NodeValue::Child { path, extandable } => {
-            if ignore_extendable {
-                vec![(current_key, path.to_string())]
-            } else {
-                if *extandable {
-                    vec![(current_key, path.to_string())]
-                } else {
-                    vec![]
-                }
-            }
-        }
-    }
-}
-
-impl Iterator for MappingTreeIterator {
-    type Item = (Vec<MapKey>, String);
-
-    fn next(&mut self) -> Option<Self::Item> {
-        self.children.pop()
-    }
-}
diff --git a/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/mod.rs b/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/mod.rs
deleted file mode 100644
index 604c855d..00000000
--- a/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/mod.rs
+++ /dev/null
@@ -1,412 +0,0 @@
-// nixos-config - My current NixOS configuration
-//
-// Copyright (C) 2025 Benedikt Peetz <benedikt.peetz@b-peetz.de>
-// SPDX-License-Identifier: GPL-3.0-or-later
-//
-// This file is part of my nixos-config.
-//
-// You should have received a copy of the License along with this program.
-// If not, see <https://www.gnu.org/licenses/gpl-3.0.txt>.
-
-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 } = &current_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 &current_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(),
-            },
-        }
-    }
-}
diff --git a/pkgs/by-name/lf/lf-make-map/src/mapping/mod.rs b/pkgs/by-name/lf/lf-make-map/src/mapping/mod.rs
index 8ccbfb9a..d869f883 100644
--- a/pkgs/by-name/lf/lf-make-map/src/mapping/mod.rs
+++ b/pkgs/by-name/lf/lf-make-map/src/mapping/mod.rs
@@ -1,166 +1,211 @@
-// nixos-config - My current NixOS configuration
-//
-// Copyright (C) 2025 Benedikt Peetz <benedikt.peetz@b-peetz.de>
-// SPDX-License-Identifier: GPL-3.0-or-later
-//
-// This file is part of my nixos-config.
-//
-// You should have received a copy of the License along with this program.
-// If not, see <https://www.gnu.org/licenses/gpl-3.0.txt>.
+use anyhow::Result;
+use keymaps::map_tree::{Node, Trie};
+use log::{Level, debug, log_enabled, trace};
+use map_key::MapKey;
 
-use std::{
-    fmt::{Display, Write},
-    hash::Hash,
-};
+pub mod lf_mapping;
+pub mod map_key;
 
-use log::debug;
-
-pub mod map_tree;
-
-#[derive(Clone, Debug, Eq)]
-pub struct MapKey {
-    pub key: char,
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
+pub struct MapChild {
+    pub path: String,
+    pub expendable: bool,
+}
 
-    resolution: usize,
+impl std::fmt::Display for MapChild {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        f.write_str(&self.path)?;
+        if !self.expendable {
+            f.write_str(" [stop]")?;
+        }
 
-    /// Part of the path, used to derive the key
-    part_path: String,
+        Ok(())
+    }
 }
 
-impl Hash for MapKey {
-    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
-        self.key.hash(state)
+pub struct MappingsTrie(pub Trie<MapKey, MapChild>);
+impl std::fmt::Display for MappingsTrie {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        self.0.fmt(f)
     }
 }
 
-impl PartialEq for MapKey {
-    fn eq(&self, other: &Self) -> bool {
-        self.key == other.key
+impl MappingsTrie {
+    pub fn new() -> Self {
+        Self(Trie::new())
     }
-}
 
-impl MapKey {
-    pub fn new_from_part_path(part_path: &str, resolution: usize) -> Vec<Self> {
-        let key = Self::part_path_to_key(&part_path, resolution);
+    pub(crate) fn include(&mut self, path: &str) -> Result<()> {
+        let associated_key = MapKey::new_ones_from_path(path, 1);
+        self.insert(&associated_key, path)
+    }
 
-        key.chars()
-            .map(|ch| Self {
-                key: ch,
-                resolution,
-                part_path: part_path.to_owned(),
-            })
-            .collect()
+    pub(crate) fn insert(&mut self, keys: &[MapKey], path: &str) -> Result<()> {
+        let value = Node::new_child(MapChild {
+            path: path.to_owned(),
+            expendable: true,
+        });
+        self.insert_node(keys, value)
     }
 
-    pub fn new_ones_from_path(path: &str, number_of_chars: usize) -> Vec<Self> {
-        let key: Vec<MapKey> = path
-            .split('/')
-            .map(|part| Self::new_from_part_path(part, number_of_chars))
-            .flatten()
-            .collect();
+    pub(crate) fn insert_node(
+        &mut self,
+        keys: &[MapKey],
+        node: Node<MapKey, MapChild>,
+    ) -> Result<()> {
+        if let Err(err) = self.0.insert_node(keys, &node) {
+            match err {
+                keymaps::error::TrieInsert::KeyAlreadySet(found_keys) => {
+                    // 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 no longer equal.
+                    // 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.
+                    assert_eq!(keys, found_keys);
 
-        debug!(
-            "Generated full MapKeys: '{}' -> '{}'",
-            path,
-            MapKey::display(&key)
-        );
-        key
-    }
+                    let mut foreign_keys =
+                        vec![found_keys.last().expect("This will exist").clone()];
+                    let mut our_keys = vec![keys.last().expect("This will exist").clone()];
 
-    pub fn increment(&self, target_resolution: usize) -> Vec<Self> {
-        let new_resolution = target_resolution;
+                    debug!(
+                        "'{}' ('{}') and '{}' ('{}') are the same, trying to find a better combination!",
+                        MapKey::display(&our_keys),
+                        our_keys[0].part_path,
+                        MapKey::display(&foreign_keys),
+                        foreign_keys[0].part_path,
+                    );
 
-        // debug!("Incrementing: '{}' ('{}')", &self, &self.part_path);
+                    our_keys[0].can_tiebreak_with(&foreign_keys[0])?;
 
-        let added_chars = if new_resolution < self.part_path.len() {
-            MapKey::part_path_to_key(&self.part_path, new_resolution)
-        } else {
-            let mut generated_chars =
-                MapKey::part_path_to_key(&self.part_path, self.part_path.len());
+                    while our_keys == foreign_keys {
+                        our_keys =
+                            our_keys[0].increment(our_keys[our_keys.len() - 1].resolution + 1);
+                        foreign_keys = foreign_keys[0]
+                            .increment(foreign_keys[foreign_keys.len() - 1].resolution + 1);
+                        debug!(
+                            "Now its: '{}' ('{}') and '{}' ('{}')",
+                            MapKey::display(&our_keys),
+                            our_keys[0].part_path,
+                            MapKey::display(&foreign_keys),
+                            foreign_keys[0].part_path,
+                        );
+                    }
+                    debug!(
+                        "Found a better one: '{}' ('{}') and '{}' ('{}')",
+                        MapKey::display(&our_keys),
+                        our_keys[0].part_path,
+                        MapKey::display(&foreign_keys),
+                        foreign_keys[0].part_path,
+                    );
 
-            generated_chars.extend(
-                (0..(new_resolution - self.part_path.len()))
-                    .into_iter()
-                    .map(|_| self.part_path.chars().last().expect("This will exists")),
-            );
+                    let parent_keys = &found_keys[..&found_keys.len() - 1];
 
-            generated_chars
-        };
+                    {
+                        if self
+                            .0
+                            .get(&found_keys)
+                            .expect("This will exist")
+                            .value()
+                            .is_some()
+                        {
+                            // This is a child, we must replace it with a parent.
+                            let other_node = self
+                                .0
+                                .replace_node(&found_keys, Node::new_parent())
+                                .expect("This node exists");
 
-        let part_path = self.part_path.clone();
-        let output: Vec<Self> = added_chars
-            .chars()
-            .enumerate()
-            .map(|(res, ch)| MapKey {
-                key: ch,
-                resolution: res + 1,
-                part_path: part_path.clone(),
-            })
-            .collect();
+                            {
+                                let mut full_foreign_keys = parent_keys.to_vec();
+                                full_foreign_keys.append(&mut foreign_keys);
+                                self.0.insert_node(&full_foreign_keys, &other_node)?;
+                            }
+                        }
+                    }
 
-        // debug!("Finished increment: '{}' ('{}')", MapKey::display(&output), output[0].part_path);
-        output
-    }
+                    {
+                        let mut full_our_keys = parent_keys.to_vec();
+                        full_our_keys.append(&mut our_keys);
+                        self.0.insert_node(&full_our_keys, &node)?;
+                    }
 
-    pub fn display(values: &[Self]) -> String {
-        values.iter().map(|value| value.key.clone()).collect()
-    }
-    fn part_path_to_key(part: &str, number_of_chars: usize) -> String {
-        fn make(pat: char, part: &str, number_of_chars: usize) -> String {
-            let mut acc = String::new();
+                    Ok(())
+                }
+                keymaps::error::TrieInsert::KeyIncludesChild {
+                    mut child_key,
+                    child_value,
+                } => {
+                    // 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.
 
-            if !part.split(pat).all(|part| part.len() > 0) {
-                panic!(
-                    "\
-Can't turn this path '{}' to a mapping.
-This should not happen, please report the bug!",
-                    part
-                )
-            }
+                    let child = self
+                        .0
+                        .replace_node(&child_key, Node::new_parent())
+                        .expect("Node exists");
+                    assert_eq!(child.value(), Some(&child_value));
 
-            let mut last_working = None;
-            for i in 0..number_of_chars {
-                for str in part.split(pat) {
-                    if acc.len() != number_of_chars {
-                        acc.push(match str.chars().nth(i) {
-                            Some(ch) => ch,
-                            None => {
-                                if let Some(last) = last_working {
-                                    str.chars().nth(last).expect("This should always exist")
-                                } else {
-                                    last_working = Some(i - 1);
-                                    str.chars().nth(i - 1).expect("This should always exist")
-                                }
-                            }
-                        })
-                    }
+                    child_key.push(MapKey {
+                        key: '.',
+                        part_path: ".".to_owned(),
+                        resolution: 1,
+                    });
+                    self.0
+                        .insert_node(&child_key, &child)
+                        .expect("We just created a parent here");
+
+                    // Recursive call, because this key could have hit the previous child directly
+                    // (thus it will now trigger the `KeyAlreadySet` error.)
+                    self.insert_node(keys, node)
                 }
             }
+        } else {
+            Ok(())
+        }
+    }
 
-            acc
+    /// Add a new [`MappingsTrie`] at the position `keys` into this Trie.
+    pub(crate) fn add_trie(&mut self, keys: &[MapKey], trie: Self) -> Result<()> {
+        if log_enabled!(Level::Trace) {
+            trace!("Adding mappings under '{}':", MapKey::display(keys));
+            eprintln!("{trie}");
+
+            trace!("Self is:");
+            eprintln!("{self}");
         }
 
-        let value = if part.contains('_') && !part.starts_with('_') && !part.ends_with('_') {
-            make('_', part, number_of_chars)
-        } else if part.contains('-') && !part.starts_with('-') && !part.ends_with('-') {
-            make('-', part, number_of_chars)
-        } else {
-            part.chars().take(number_of_chars).collect::<String>()
-        };
+        let replaced = self
+            .0
+            .replace_node(keys, trie.0.root_node().to_owned())
+            .expect("This value exists");
 
-        assert_eq!(
-            value.len(),
-            number_of_chars,
-            "'{}' does not have expected length of: {}",
-            value,
-            number_of_chars
-        );
-        value
-    }
-}
+        if log_enabled!(Level::Trace) {
+            trace!("After replace adding the new trie");
+            eprintln!("{self}");
+        }
 
-impl Display for MapKey {
-    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        f.write_char(self.key)
+        {
+            let mut new_keys = keys.to_vec();
+            new_keys.push(MapKey {
+                key: '.',
+                part_path: ".".to_owned(),
+                resolution: 1,
+            });
+
+            let mut value = replaced.value().expect("Is a child").clone();
+            value.expendable = false;
+
+            trace!("Re-inserting '{}' into self.", MapKey::display(keys));
+            self.0
+                .insert_node(&new_keys, &Node::new_child(value))
+                .expect("This key is not used.");
+        }
+
+        Ok(())
     }
 }