use std::alloc::{alloc, Layout};
use std::borrow::Borrow;
use std::collections::HashMap;
use std::fmt::Debug;
use std::hash::Hash;
#[derive(PartialEq, PartialOrd, Eq, Ord, Debug, Hash)]
pub enum UniqueOption<V> {
Some(V),
NonUnique,
None,
}
impl<V> UniqueOption<V> {
pub fn unwrap(self) -> V {
match self {
UniqueOption::Some(v) => v,
_ => unreachable!(),
}
}
}
#[derive(Debug)]
struct Node<K, V> {
value: Option<V>,
links: HashMap<K, Option<*mut Node<K, V>>>,
}
impl<K, V> Node<K, V>
where
K: Eq + Hash + Clone + Debug,
V: Debug,
{
fn new() -> *mut Node<K, V> {
unsafe {
let layout = Layout::new::<Node<K, V>>();
let curr = alloc(layout) as *mut Node<K, V>;
curr.write(Node {
value: None,
links: HashMap::new(),
});
curr
}
}
fn insert(&mut self, path: &[K], value: V) -> bool {
let name = path[0].clone();
let next = self.links.entry(name).or_insert(Some(Node::new()));
match next {
Some(next) => unsafe {
if path.len() == 1 {
(**next).value = Some(value);
true
} else {
(**next).insert(&path[1..], value)
}
},
None => false,
}
}
fn update_aliases<Q>(&mut self, path: &[&Q], path_aliases: &[&[K]])
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized + Debug,
{
if !path.is_empty() {
let name = path[0].clone();
let aliases = path_aliases[0].clone();
let next1 = self.links.get(name).unwrap().unwrap();
for alies in aliases {
match self.links.get(alies.borrow()) {
Some(Some(next2)) => {
if next1 != *next2 {
self.links.insert((*alies).clone(), None);
}
}
Some(None) => {}
None => {
self.links.insert((*alies).clone(), Some(next1));
}
}
}
unsafe {
(*next1).update_aliases(&path[1..], &path_aliases[1..]);
}
}
}
fn get_mut<Q>(&mut self, path: &[&Q]) -> UniqueOption<*mut Node<K, V>>
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized + Debug,
{
if path.len() == 0 {
UniqueOption::Some(self as *mut Node<K, V>)
} else {
let name = path[0];
match self.links.get(name) {
Some(Some(next)) => {
if path.len() == 1 {
UniqueOption::Some(*next)
} else {
unsafe { (**next).get_mut(&path[1..]) }
}
}
Some(None) => UniqueOption::NonUnique,
None => UniqueOption::None,
}
}
}
}
#[derive(Debug)]
pub struct Trie<K, V> {
root: *mut Node<K, V>,
}
impl<K, V> Trie<K, V>
where
K: Eq + Hash + Clone + Debug,
V: Debug,
{
pub fn new() -> Self {
Self { root: Node::new() }
}
pub fn insert(&mut self, path: &[K], value: V) {
unsafe {
(*self.root).insert(path, value);
}
}
pub fn update_aliases<Q>(&mut self, path: &[&Q], aliases: &[&[K]]) -> bool
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized + Debug,
{
unsafe {
match (*self.root).get_mut(path) {
UniqueOption::Some(_) => {
(*self.root).update_aliases(path, aliases);
true
}
_ => false,
}
}
}
pub fn get<Q>(&self, path: &[&Q]) -> UniqueOption<&V>
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized + Debug,
{
unsafe {
match (*self.root).get_mut(path) {
UniqueOption::Some(node_ptr) => {
match (*node_ptr).value {
Some(ref v) => UniqueOption::Some(v),
None => UniqueOption::None,
}
}
UniqueOption::None => UniqueOption::None,
UniqueOption::NonUnique => UniqueOption::NonUnique,
}
}
}
pub fn get_mut<Q>(&mut self, path: &[&Q]) -> UniqueOption<&mut V>
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized + Debug,
{
unsafe {
match (*self.root).get_mut(path) {
UniqueOption::Some(node_ptr) => {
match (*node_ptr).value {
Some(ref mut v) => UniqueOption::Some(v),
None => UniqueOption::None,
}
}
UniqueOption::None => UniqueOption::None,
UniqueOption::NonUnique => UniqueOption::NonUnique,
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use regex::Regex;
#[test]
fn test1() {
let mut trie = Trie::new();
trie.insert(&["a", "b", "c"], 100);
assert_eq!(
trie.update_aliases(&["a", "b"], &[&["A", "aaa"], &["bbb", "b4"]]),
true
);
let value = trie.get(&["A", "b4", "c"]);
assert_eq!(value, UniqueOption::Some(&100));
}
#[test]
fn test2() {
let mut trie = Trie::new();
trie.insert(&["a", "b", "c"], 100);
assert_eq!(
trie.update_aliases(&["a", "b"], &[&["A", "aaa"], &["bbb", "b4"]]),
true
);
let value = trie.get(&["A", "b4", "C"]);
assert_eq!(value, UniqueOption::None);
}
#[test]
fn test3() {
let mut trie = Trie::new();
trie.insert(&["a", "b", "c"], "c");
trie.insert(&["a", "b", "d", "e"], "e");
assert_eq!(
trie.update_aliases(
&["a", "b", "c"],
&[&["A", "aaa"], &["bbb", "b4"], &["C", "X"]],
),
true
);
assert_eq!(
trie.update_aliases(
&["a", "b", "d", "e"],
&[&[], &[], &["D", "X"], &["E", "ee"]],
),
true
);
assert_eq!(
trie.update_aliases(&["a", "b", "X", "e"], &[&[], &[], &["DDD"], &["e5"]],),
false
);
assert_eq!(
trie.update_aliases(&["A", "b", "D", "ee"], &[&[], &[], &["DDDD"], &["e6"]],),
true
);
let value = trie.get(&["A", "b4", "C"]);
assert_eq!(value, UniqueOption::Some(&"c"));
let value = trie.get(&["A", "b4", "X"]);
assert_eq!(value, UniqueOption::NonUnique);
let value = trie.get(&["A", "b4", "d", "ee"]);
assert_eq!(value, UniqueOption::Some(&"e"));
let value = trie.get(&["A", "b4", "X", "e6"]);
assert_eq!(value, UniqueOption::NonUnique);
let value = trie.get(&["A", "b4", "DDDD", "ee"]);
assert_eq!(value, UniqueOption::Some(&"e"));
}
#[test]
fn test4() {
let mut trie = Trie::new();
trie.insert(&["a", "b", "c"], 100);
trie.update_aliases(&["a", "b"], &[&["A", "aaa"], &["bbb", "b4"]]);
let value = trie.get_mut(&["A", "b4", "c"]).unwrap();
*value = 1000;
let value = trie.get(&["A", "b4", "c"]);
assert_eq!(value, UniqueOption::Some(&1000));
}
#[test]
fn test5() {
let names = vec![
"first/Output!",
"first/Output![Demo6A,0].0",
"first/Output![Demo6A,0].1",
"first/self",
"self.b[Demo6B,0].Double",
"self.b[Demo6B,0].Double",
"self.b[Demo6B,0].Double[Demo6A,0].0",
"self.b[Demo6B,0].Double[Demo6A,1].0",
"self.b[Demo6B,0].Double[Demo6A,0].1",
"self.b[Demo6B,0].Double[Demo6A,1].1",
"self.b[Demo6B,0].Multiple",
"self.b[Demo6B,0].Multiple",
"self.b[Demo6B,0].Multiple[Demo6A,0].0",
"self.b[Demo6B,0].Multiple[Demo6A,0].1",
"self.b[Demo6B,0].Single",
"self.b[Demo6B,0].Single[Demo6A,0].0",
"self.b[Demo6B,0].Single[Demo6A,0].1",
];
let mut trie = Trie::new();
for name in names {
let name = format!("{}$", name);
let path = &name.split(".").map(|s| s.to_string()).collect::<Vec<_>>()[..];
trie.insert(path, name);
let re = Regex::new(r"\[[^\[\]]+\]").unwrap();
let path_aliases = path
.iter()
.map(|cell1| {
let cell2 = re.replace(cell1, "").to_string();
if cell1.len() == cell2.len() {
vec![]
} else {
vec![cell2]
}
})
.collect::<Vec<_>>();
let path = &path.iter().map(|s| s).collect::<Vec<_>>()[..];
let path_aliases = &path_aliases
.iter()
.map(|alies| &alies[..])
.collect::<Vec<_>>()[..];
trie.update_aliases(path, path_aliases);
}
let value = trie.get(&["first/Output!$"]);
assert_eq!(value, UniqueOption::Some(&"first/Output!$".to_string()));
let value = trie.get(&["first/Output!", "0$"]);
assert_eq!(
value,
UniqueOption::Some(&"first/Output![Demo6A,0].0$".to_string())
);
let value = trie.get(&["first/Output!", "1$"]);
assert_eq!(
value,
UniqueOption::Some(&"first/Output![Demo6A,0].1$".to_string())
);
let value = trie.get(&["self", "b", "Double$"]);
assert_eq!(
value,
UniqueOption::Some(&"self.b[Demo6B,0].Double$".to_string())
);
let value = trie.get(&["self", "b", "Double", "0$"]);
assert_eq!(value, UniqueOption::NonUnique);
let value = trie.get(&["self", "b", "Double", "1$"]);
assert_eq!(value, UniqueOption::NonUnique);
let value = trie.get(&["self", "b", "Double[Demo6A,1]", "1$"]);
assert_eq!(
value,
UniqueOption::Some(&"self.b[Demo6B,0].Double[Demo6A,1].1$".to_string())
);
}
}