diff options
-rw-r--r-- | lib/etc/libimagutil/Cargo.toml | 1 | ||||
-rw-r--r-- | lib/etc/libimagutil/src/lib.rs | 2 | ||||
-rw-r--r-- | lib/etc/libimagutil/src/tree.rs | 137 |
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) + } +} |