기수 탐색 트라이

1. [derive(Debug)]

enum Node<T: Sized> {

   Terminal {
       key: u32,
       data: T,
   },
   Nonterminal {
       left: Box<Node<T>>,
       right: Box<Node<T>>,
   },
   None,

}

1. [derive(Debug)]

struct Tree<T: Sized> {

   root: Node<T>,

}

1. [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();
   

}