use std::iter::{Iterator, FromIterator};
use std::rc::{Rc, Weak};
use std::fmt::{self, Display};
use std::cell::RefCell;
use std::collections::{HashMap, hash_map::Entry};
use std::hash::{Hash, Hasher};
use std::ops::Add;
#[derive(Debug)]
struct ConfPathData {
name: Option<String>,
parent: Weak<ConfPathData>,
children: RefCell<HashMap<String, Rc<ConfPathData>>>
}
#[derive(Debug, Clone)]
pub struct ConfPath {
data: Rc<ConfPathData>,
root: Rc<ConfPathData>
}
impl Default for ConfPath {
fn default() -> Self {
let root_node = Rc::new(ConfPathData {
name: None,
parent: Weak::new(),
children: RefCell::new(HashMap::default())
});
Self {
data: root_node.clone(),
root: root_node
}
}
}
impl Hash for ConfPath {
fn hash<H: Hasher>(&self, state: &mut H) {
for component in self.clone() {
component.data.name.hash(state);
}
}
}
impl PartialEq for ConfPath {
fn eq(&self, other: &Self) -> bool {
if Rc::ptr_eq(&self.data, &other.data) {
true
} else {
if Rc::ptr_eq(&self.root, &other.root) {
false
} else {
let mut s = self.clone();
let mut o = other.clone();
loop {
match (s.pop(), o.pop()) {
(Some((s_c_name, s_cp)), Some((o_c_name, o_cp))) if s_c_name == o_c_name => { s = s_cp; o = o_cp; } (None, None) => break true,
_ => break false
}
}
}
}
}
}
impl Eq for ConfPath {
}
impl Add<&str> for ConfPath {
type Output = Self;
fn add(self, other: &str) -> Self {
self.push(other)
}
}
impl IntoIterator for ConfPath {
type Item = ConfPath;
type IntoIter = std::iter::Rev<std::vec::IntoIter<Self>>;
fn into_iter(self) -> Self::IntoIter {
let mut path = Vec::with_capacity(5);
let mut pos = self;
while !pos.is_root() {
path.push(pos.clone());
pos = pos.pop().unwrap().1; }
path.into_iter().rev()
}
}
impl Display for ConfPath {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let mut pos = self.clone();
let mut add_delimiter = false;
while !pos.is_root() {
if add_delimiter {
write!(f, ".")?;
}
write!(f, "{}", pos.tail_component_name().unwrap())?;
pos = pos.pop().unwrap().1;
add_delimiter = true;
}
Ok(())
}
}
impl <'a, T: AsRef<[&'a str]>> From<T> for ConfPath {
fn from(components: T) -> Self {
Self::default().push_all(components.as_ref())
}
}
impl ConfPath {
fn new(root: &Rc<ConfPathData>, data: Rc<ConfPathData>) -> Self {
Self {
data,
root: root.clone() }
}
pub fn push(&self, component: &str) -> Self {
match self.data.children.borrow_mut().entry(component.to_owned()) {
Entry::Occupied(child) => Self::new(&self.root, child.get().clone()),
Entry::Vacant(child) => Self::new(&self.root, child.insert(Rc::new(ConfPathData {
name: Some(component.to_owned()),
parent: Rc::downgrade(&self.data),
children: RefCell::new(HashMap::default())
})).clone())
}
}
pub fn push_all<S: AsRef<str>, T: IntoIterator<Item = S>>(&self, iter: T) -> Self {
iter.into_iter().fold(self.clone(), |prev, c| prev.push(c.as_ref()))
}
pub fn pop(&self) -> Option<(&str, Self)> {
if self.is_root() {
None
} else {
let parent = self.data.parent.upgrade().unwrap();
Some((self.data.name.as_ref().unwrap(), Self::new(&self.root, parent))) }
}
pub fn is_root(&self) -> bool {
Rc::ptr_eq(&self.data, &self.root)
}
pub fn tail_component_name(&self) -> Option<&str> {
self.data.name.as_deref()
}
pub fn iter(&self) -> impl Iterator<Item=Self> {
self.clone().into_iter()
}
pub fn children(&self) -> impl Iterator<Item=ConfPath> {
Vec::from_iter(self.data.children.borrow().values().map(|v| ConfPath::new(&self.root, v.clone()))).into_iter()
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::hash_set::HashSet;
use std::collections::hash_map::DefaultHasher;
fn check_path(cp: &ConfPath, components: &[&str]) {
assert_eq!(cp.iter().zip(components.iter()).filter(|(l, &r)| l.tail_component_name().unwrap() == r).count(), components.len());
}
fn hash_pair(cp1: ConfPath, cp2: ConfPath) -> (u64, u64) {
let mut hasher1 = DefaultHasher::new();
let mut hasher2 = DefaultHasher::new();
cp1.hash(&mut hasher1);
cp2.hash(&mut hasher2);
(hasher1.finish(), hasher2.finish())
}
#[test]
fn creation() {
let cp = ConfPath::default().push_all(&["a", "b", "c"]);
check_path(&cp, &["a", "b", "c"]);
}
#[test]
fn pop() {
let cp = ConfPath::default().push_all(&["a", "b"]);
let (part, cp) = cp.pop().unwrap();
assert_eq!(part, "b");
let (part, cp) = cp.pop().unwrap();
assert_eq!(part, "a");
assert!(cp.pop().is_none());
}
#[test]
fn push() {
let cp = ConfPath::default().push_all(&["a", "b"]);
let cp = cp.push("c");
check_path(&cp, &["a", "b", "c"]);
let cp = cp.push_all(&["d", "e"]);
check_path(&cp, &["a", "b", "c", "d", "e"]);
}
#[test]
fn iterator() {
let cp = ConfPath::default().push_all(&["a", "b"]);
let mut cp_iter = cp.into_iter();
assert_eq!(cp_iter.next().unwrap().tail_component_name().unwrap(), "a");
assert_eq!(cp_iter.next().unwrap().tail_component_name().unwrap(), "b");
assert!(cp_iter.next().is_none());
assert!(cp_iter.next().is_none());
}
#[test]
fn is_root() {
let cp_root = ConfPath::default();
let cp_node = cp_root.push("a");
assert!(cp_root.is_root());
assert!(!cp_node.is_root());
}
#[test]
fn add() {
let cp = ConfPath::default();
check_path(&(cp + "a"), &["a"]);
}
#[test]
fn comparison() {
let root1 = ConfPath::default();
let root2 = ConfPath::default();
assert_eq!(root1, root1);
assert_eq!(root2, root2);
assert_eq!(root1, root2);
assert_eq!(root1.push("a"), root1.push("a"));
assert_eq!(root1.push_all(&["a", "b"]), root1.clone() + "a" + "b");
assert_ne!(root1.push_all(&["a", "b"]), root1.push("a"));
assert_ne!(root1.push_all(&["a", "b"]), root1.push("b"));
assert_eq!(root1.push("a"), root2.push("a"));
assert_eq!(root1.push_all(&["a", "b"]), root2.push_all(&["a", "b"]));
assert_ne!(root1.push("a"), root2.push("b"));
assert_ne!(root1.push_all(&["a", "b"]), root2.push_all(&["a", "b", "c"]));
}
#[test]
fn hash() {
let cp = ConfPath::default();
let (h1, h2) = hash_pair(cp.push_all(&["a", "b"]), cp.push_all(&["a", "b"]));
assert_eq!(h1, h2);
let (h1, h2) = hash_pair(cp.push_all(&["a", "b", "c"]), cp.push_all(&["a", "b", "c"]));
assert_eq!(h1, h2);
let (h1, h2) = hash_pair(cp.push_all(&["a", "b"]), cp.push_all(&["a"]));
assert_ne!(h1, h2);
let (h1, h2) = hash_pair(cp.push_all(&["a", "b"]), cp.push_all(&["b"]));
assert_ne!(h1, h2);
let (h1, h2) = hash_pair(cp.push_all(&["a", "b", "c"]), cp.push_all(&["a", "bc"]));
assert_ne!(h1, h2);
}
#[test]
fn free() {
let wr_root;
let wr_inode;
{
let lnode;
{
let root = ConfPath::default();
let inode = root.push("internal");
lnode = inode.push("leaf");
wr_root = Rc::downgrade(&root.data);
wr_inode = Rc::downgrade(&inode.data);
assert!(wr_root.upgrade().is_some());
assert!(wr_inode.upgrade().is_some());
}
lnode.push("test");
assert!(wr_root.upgrade().is_some());
assert!(wr_inode.upgrade().is_some());
}
assert!(wr_root.upgrade().is_none());
assert!(wr_inode.upgrade().is_none());
}
#[test]
fn enum_children() {
let cp = ConfPath::default();
cp.push("a");
cp.push("b");
cp.push_all(&["a", "a1"]);
let mut reference_set: HashSet<ConfPath> = HashSet::from_iter([ConfPath::from(&["a"]), ConfPath::from(&["b"])].iter().cloned());
cp.children().for_each(|c| assert!(reference_set.remove(&c), "Iterator returned to many elements."));
assert_eq!(reference_set.len(), 0, "Iterator returned not enough elements.");
let mut reference_set: HashSet<ConfPath> = HashSet::from_iter([ConfPath::from(&["a", "a1"])].iter().cloned());
cp.push("a").children().for_each(|c| assert!(reference_set.remove(&c), "Iterator returned to many elements."));
assert_eq!(reference_set.len(), 0, "Iterator returned not enough elements.");
}
#[test]
fn enum_children_const() {
let cp = ConfPath::default();
cp.push("a");
cp.push("b");
let root_child_iter = cp.children();
cp.push("d");
let mut reference_set: HashSet<ConfPath> = HashSet::from_iter([ConfPath::from(&["a"]), ConfPath::from(&["b"])].iter().cloned());
root_child_iter.for_each(|c| assert!(reference_set.remove(&c), "Iterator returned to many elements."));
assert_eq!(reference_set.len(), 0, "Iterator returned not enough elements.");
}
}