Implement index-based tree that can be build after all relevant elements are added

Signed-off-by: Matthias Beyer <mail@beyermatthias.de>

3 files changed, 140 insertions, 0 deletions

diff --git a/lib/etc/libimagutil/Cargo.toml b/lib/etc/libimagutil/Cargo.toml
index 62909ea4..c56fe6ef 100644
--- a/lib/etc/libimagutil/Cargo.toml
+++ b/lib/etc/libimagutil/Cargo.toml
@@ -33,4 +33,5 @@ log = "0.4.6"
 regex = "1.1.7"
 tempfile = "3.0.9"
 chrono = "0.4.7"
+failure = "0.1"
 
diff --git a/lib/etc/libimagutil/src/lib.rs b/lib/etc/libimagutil/src/lib.rs
index c62f425d..8041deb3 100644
--- a/lib/etc/libimagutil/src/lib.rs
+++ b/lib/etc/libimagutil/src/lib.rs
@@ -37,6 +37,7 @@
 
 #[macro_use] extern crate lazy_static;
 #[macro_use] extern crate log;
+#[macro_use] extern crate failure;
 extern crate regex;
 extern crate url;
 extern crate boolinator;
@@ -51,6 +52,7 @@ pub mod edit;
 pub mod info_result;
 pub mod info_option;
 pub mod key_value_split;
+pub mod tree;
 pub mod variants;
 pub mod warn_exit;
 pub mod warn_result;
diff --git a/lib/etc/libimagutil/src/tree.rs b/lib/etc/libimagutil/src/tree.rs
new file mode 100644
index 00000000..e3f4dfac
--- /dev/null
+++ b/lib/etc/libimagutil/src/tree.rs
@@ -0,0 +1,137 @@
+//
+// imag - the personal information management suite for the commandline
+// Copyright (C) 2015-2020 Matthias Beyer <mail@beyermatthias.de> and contributors
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; version
+// 2.1 of the License.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public
+// License along with this library; if not, write to the Free Software
+// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+//
+
+use std::iter::FromIterator;
+
+use failure::Fallible as Result;
+
+pub struct Tree<T: Sized> {
+    elements: Vec<TreeElement<T>>
+}
+
+impl<T: Sized> Tree<T> {
+
+    pub fn new() -> Self {
+        Tree { elements: Vec::new() }
+    }
+
+    pub fn with_capacity(cap: usize) -> Self {
+        Tree { elements: Vec::with_capacity(cap) }
+    }
+
+    pub fn add_node(&mut self, t: T) {
+        self.elements.push(TreeElement {
+            parent_idx: None,
+            childs_indexes: Vec::new(),
+            element: t
+        });
+    }
+
+    pub fn build_tree<ID, IG>(&mut self, ig: IG) -> TreeBuilder<T, ID, IG>
+        where ID: PartialEq + Sized,
+              IG: IdGetter<T, ID = ID>
+    {
+        TreeBuilder(self, ig)
+    }
+}
+
+impl<A> FromIterator<A> for Tree<A>
+    where A: Sized
+{
+    fn from_iter<T>(iter: T) -> Self
+    where
+        T: IntoIterator<Item = A>
+    {
+        Tree { elements: Vec::from_iter(iter.into_iter().map(|e| TreeElement::new(e))) }
+    }
+}
+
+
+struct TreeElement<T> {
+    pub parent_idx: Option<usize>,
+    pub childs_indexes: Vec<usize>,
+    pub element: T
+}
+
+impl<T> TreeElement<T> {
+    fn new(t: T) -> Self {
+        TreeElement {
+            parent_idx: None,
+            childs_indexes: Vec::new(),
+            element: t
+        }
+    }
+}
+
+
+pub trait IdGetter<T>
+    where T: Sized,
+{
+    type ID: PartialEq + Sized;
+
+    fn get_id_for_node(&self, node: &T)      -> Result<Self::ID>;
+    fn get_id_for_parent_of(&self, node: &T) -> Result<Self::ID>;
+}
+
+pub struct TreeBuilder<'a, T, ID, IG>(&'a mut Tree<T>, IG)
+    where T: Sized,
+          ID: PartialEq + Sized,
+          IG: IdGetter<T, ID = ID>;
+
+impl<'a, T, ID, IG> TreeBuilder<'a, T, ID, IG>
+    where T: Sized,
+          ID: PartialEq + Sized,
+          IG: IdGetter<T, ID = ID>
+{
+    pub fn build(&mut self) -> Result<()> {
+        let mut i = 0;
+        while let Some(node) = self.0.elements.get(i) {
+            let parent_id = self.1.get_id_for_parent_of(&node.element)?;
+
+            if let Some(parent_idx) = self.find_node_idx(&parent_id)? {
+                if let Some(parent) = self.0.elements.get_mut(parent_idx) {
+                    parent.childs_indexes.push(i);
+                }
+
+                if let Some(child) = self.0.elements.get_mut(i) {
+                    child.parent_idx = Some(parent_idx);
+                }
+            }
+
+            i += 1
+        }
+
+        Ok(())
+    }
+
+    fn find_node_idx<'t>(&'t self, search_id: &IG::ID) -> Result<Option<usize>> {
+        let mut i = 0;
+
+        while let Some(node) = self.0.elements.get(i) {
+            let id = self.1.get_id_for_node(&node.element)?;
+            if id == *search_id {
+                return Ok(Some(i))
+            }
+
+            i += 1
+        }
+
+        return Ok(None)
+    }
+}