- [derive(Debug)]
enum Node<T: Sized> {
Terminal {
key: u32,
data: T,
},
Nonterminal {
left: Box<Node<T>>,
right: Box<Node<T>>,
},
None,
}
- [derive(Debug)]
struct Tree<T: Sized> {
root: Node<T>,
}
- [inline]
fn radix_bit(num: u32, radix: u8) -> bool {
num & (1 << (32 - radix)) != 0
} impl<T: Sized> Node<T> {
fn terminal(key: u32, data: T) -> Self {
Node::Terminal {
key: key,
data: data,
}
}
fn nonterminal(left: Self, right: Self) -> Self {
Node::Nonterminal {
left: Box::new(left),
right: Box::new(right),
}
}
fn none() -> Self {
Node::None
}
fn insert(&mut self, index: u8, key: u32, data: T)->Option<T> {
//println!("insert {}",index);
match *self {
Node::None => {
let n = if radix_bit(key, index) {
Node::nonterminal(Node::none(), Node::terminal(key, data))
} else {
Node::nonterminal(Node::terminal(key, data), Node::none())
};
*self = n;
None
}
Node::Nonterminal {
ref mut left,
ref mut right,
} => {
let next = if radix_bit(key, index) {
right.as_mut()
} else {
left.as_mut()
};
next.insert(index + 1, key, data)
//next
}
Node::Terminal {
key: self_key,
data:ref mut self_data,
} => {
if self_key == key{
return Some(std::mem::replace(self_data, data));
}
let s = std::mem::replace(self, Node::None);
let res;
//eprintln!("{:?}", self);
*self = match (radix_bit(self_key, index), radix_bit(key, index)) {
(true, true) => {
let mut node =
Node::nonterminal(Node::None, s);
res = node.insert(index, key, data);
node
}
(false, false) => {
let mut node =
Node::nonterminal(s, Node::None);
res = node.insert(index, key, data);
node
}
(true, false) => {
//eprintln!("{:?}", self);
res = None;
Node::nonterminal(
Node::terminal(key, data),
s,
)
}
(false, true) => {
//eprintln!("{:?}", self);
res = None;
Node::nonterminal(
s,
Node::terminal(key, data),
)
}
};
res
}
}
}
}
impl<T: Sized> Tree<T> {
fn new() -> Self {
Self { root: Node::none() }
}
fn insert(&mut self, key: u32, data: T) {
self.root.insert(1, key, data);
}
fn find(&self, key: &u32) -> Option<&T> {
let mut node = &self.root;
let mut radix = 0u8;
loop {
//eprintln!("{}, {:?}",radix, node);
radix += 1;
//println!("find radix: {} {:?}",radix, node);
match node {
Node::Terminal {
key: termial_key,
data,
} if termial_key == key => break Some(data),
Node::Nonterminal { left, right } => {
node = match radix_bit(*key, radix) {
true => right.as_ref(),
false => left.as_ref(),
}
}
_ => break None,
}
}
}
} fn main(){
//let mut tree = Tree::new(); let mut tree:Tree<[u8; 4096]> = Tree::new();
}