기수 탐색 트라이

#[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();
    
}