Shared via Rust Playground

playground.rs

use std::thread;
use std::sync::Arc;
use std::rc::Rc;
use std::fmt::Debug	;

pub fn get_insertion_index<K: Ord + Debug + Clone>(values: &[K], k: &K) -> usize	{
	let mut index = 0;
	for v in values{
		if *v >= *k { break;}
		index += 1;
	}
	return index;
}
pub fn get_insertion_index2<K: Ord + Debug + Clone, V: Clone + Debug>(values: &[(K, V)], k: &K) -> usize	{
	let mut index = 0;
	for v in values{
		if v.0 >= *k { break;}
		index += 1;
	}
	return index;
}
pub fn upper_bound<K: Ord + Debug + Clone>(keys: &[K], key: &K) -> usize{
	let mut index: i32 = -1;
	for i in 0..keys.len(){
		let ref k = keys[i];
		if *key < *k { index = i as i32; break;}
	}
	if index == -1{ index = keys.len() as i32; }
	return index as usize;
}
#[derive(Debug)]
enum NodeType{
	Node,
	Leaf
}
trait AbstractNode<K: Ord + Debug + Clone, V: Clone + Debug> {
	fn min_key(&self) -> K;
	fn max_key(&self) -> K;
	fn keys_count(&self) -> usize;
	fn keys(&self) -> &[K];
	fn node_type(&self) -> NodeType;
	fn add_key_value(&mut self, k: K, v: V);
	fn add_key(&mut self, k: K);
	fn print_values(&self);
	fn get_keys_values(&self, max_degree: usize) -> Vec<(K, V)>;
	fn add_child(&mut self, node: Rc<AbstractNode<K, V>>);
	fn get_child(&self, index: usize) -> &AbstractNode<K, V>;
	fn get_childs_count(&self) -> usize;
}

struct Node<K, V> {
    keys: Vec<K>,
    childs: Vec<Option<Rc<AbstractNode<K, V>>>>,
    childs_count: usize
}
impl<K: Ord + Debug + Clone, V: Clone + Debug> AbstractNode<K, V> for Node<K, V> {
	fn min_key(&self) -> K { self.keys[0].clone()}
	fn max_key(&self) -> K { self.keys[self.keys.len() - 1].clone()}
	fn keys(&self) -> &[K]{ self.keys.as_slice()}
	fn keys_count(&self) -> usize{ self.keys.len() }
	fn node_type(&self) -> NodeType { NodeType::Node }
	fn add_key_value(&mut self, k: K, v: V) { unimplemented!();}
	fn add_key(&mut self, k: K) { self.keys.push(k);}
	
	fn print_values(&self){ }
	fn get_keys_values(&self, max_degree: usize) -> Vec<(K, V)> { unimplemented!();}
	fn add_child(&mut self, node: Rc<AbstractNode<K, V>>){
		assert!(self.childs_count <= self.childs.len());
		let max_key = node.max_key();
		let index = upper_bound(self.keys.as_slice(), &max_key);
		self.childs[index as usize] = Some(node);
		self.childs_count += 1;
		println!("max_key: {:?}, Index: {:?}, keys: {:?}", max_key, index, self.keys);
	}
	fn get_child(&self, index: usize) ->&AbstractNode<K, V>{
		let c = &self.childs[index];
		match *c {
		    Some(ref node) => return **node,
		    None => { panic!("get_child for index[{:?}]. There was no data!", index); } ,
		}
	}
	fn get_childs_count(&self) -> usize { self.childs_count}
}
impl<K, V> Node<K, V> {
    pub fn new(count: usize) -> Self {
    	let mut childs = Vec::<Option<Rc<AbstractNode<K, V>>>>::with_capacity(count + 1);
    	for i in 0..count + 1{
    		childs.push(Option::None);
    	}
        Node {
            keys: Vec::<K>::with_capacity(count),
            childs: childs,
            childs_count: 0
        }
    }
}

struct Leaf<K, V> {
    keys: Vec<K>,
    values: Vec<V>,
    next: Option<Rc<Leaf<K, V>>>
}
impl<K: Ord + Debug + Clone, V: Clone + Debug> AbstractNode<K, V> for Leaf<K, V> {
	fn min_key(&self) -> K { self.keys[0].clone()}
	fn max_key(&self) -> K { self.keys[self.keys.len() - 1].clone()}
	fn keys(&self) -> &[K]{ self.keys.as_slice()}
	fn keys_count(&self) -> usize{ self.keys.len() }
	fn node_type(&self) -> NodeType { NodeType::Leaf }
	fn add_key_value(&mut self, k: K, v: V) {
		let index = get_insertion_index(&self.keys, &k);
		assert!(self.keys.capacity() > index);
		self.keys.insert(index, k);
		self.values.insert(index, v);
	}
	fn add_key(&mut self, k: K){ unimplemented!();}
	fn get_keys_values(&self, max_degree: usize) -> Vec<(K, V)>{
		let mut v = Vec::<(K, V)>::with_capacity(max_degree);
		for i in 0..self.keys.len(){
			v.push((self.keys[i].clone(), self.values[i].clone()));
		}
		return v;
	}
	fn print_values(&self){ 
		for i in &self.keys{
			println!("{:?}", i);
		}
	}
	fn add_child(&mut self, node: Rc<AbstractNode<K, V>>){ unimplemented!();}
	fn get_childs_count(&self) -> usize { unimplemented!();}
	fn get_child(&self, index: usize) -> &AbstractNode<K, V>{ unimplemented!();}
}
impl<K, V> Leaf<K, V> {
    pub fn new(count: usize) -> Leaf<K, V> {
        Leaf {
            keys: Vec::<K>::with_capacity(count),
            values: Vec::<V>::with_capacity(count),
            next: None
        }
    }
}
struct BPlusTree<K: 'static, V: 'static> {
    pub root: Box<AbstractNode<K, V> + 'static>,
    max_degree: u16,
}
impl<K: Ord + Debug + Clone, V:  Debug + Clone> BPlusTree<K, V> {
    pub fn new(max_degree: u16) -> Self {
        let leaf = Leaf::<K, V>::new(max_degree as usize);
        BPlusTree {
            root: Box::new(leaf),
            max_degree: max_degree,
        }
    }
    pub fn split_to_leaves(&mut self, k: K, v: V) -> (Rc<Leaf<K, V>>, Rc<Leaf<K, V>>){
		let mut buffer = self.root.get_keys_values(self.max_degree as usize);
		let index = get_insertion_index2(&buffer, &k);
		assert!(buffer.capacity() > index);
		buffer.insert(index, (k, v));
		let mid = ((buffer.len() as f32) / 2 as f32).ceil() as usize;
		println!("len: {}, mid: {:?}, buffer: {:?}", buffer.len(), mid, buffer);
		let mut leaf1 = Leaf::<K, V>::new(self.max_degree as usize);
		let mut leaf2 = Leaf::<K, V>::new(self.max_degree as usize);
		for i in 0..mid {
			leaf1.keys.push(buffer[i].0.clone());
			leaf1.values.push(buffer[i].1.clone());
		}
		for i in mid..buffer.len(){
			leaf2.keys.push(buffer[i].0.clone());
			leaf2.values.push(buffer[i].1.clone());
		}
		leaf2.next = None;
		let leaf2 = Rc::new(leaf2);
		leaf1.next = Some(leaf2.clone());
		return (Rc::new(leaf1), leaf2);
	}
    pub fn insert(&mut self, k: K, v: V){
    	let root_node_type = self.root.node_type();
    	let keys_count = self.root.keys_count()  as u16;
    	println!("Root type: {:?} max_degree: {}. leaf.keys_count: {}", root_node_type, self.max_degree, self.root.keys_count());
    	match root_node_type {
    	     NodeType::Leaf => {
    	     	if keys_count < self.max_degree	- 1 {
    	     		self.root.add_key_value(k, v);    	     		
    	     	}
    	     	else{
    	     		let (leaf1, leaf2) = self.split_to_leaves(k, v);
    	     		let min_key = leaf2.keys[0].clone();
    	     		let mut new_root = Node::<K, V>::new(self.max_degree as usize);
    	     		new_root.add_key(min_key);
    	     		new_root.add_child(leaf1);
    	     		new_root.add_child(leaf2);
    	     		self.root = Box::new(new_root);
    	     	}
    	     }
    	     NodeType::Node	=>  {
    	     	println!("Root is node!. Childs: {:?}", self.root.get_childs_count());
    	     	self.choose_subtree(&*self.root, &k);
    	     },
    	 }
    }   
    pub fn print(&self){
    	self.root.print_values();
    }
    fn choose_subtree<'a>(&'a self, node: &'a AbstractNode<K, V>, k: &K) -> &AbstractNode<K, V>{
    	let index = upper_bound(node.keys(), &k);
    	println!("Child index: {:?}", index);
    	return node;
    	// match node.node_type() {
    	//      NodeType::Leaf => { return node;}
    	//      NodeType::Node	=> { return self.choose_subtree(node.get_child(index), k);}
    	// }
    }
}
#[derive(Debug)]
struct Foo {
    childs: Vec<Option<Rc<i32>>>
}
impl Foo{
	fn get_child(&self, index: usize) -> &i32{
		let ref c = self.childs[index];
		match *c {
		    Some(node) => return &*node,
		    None => { panic!("get_child for index[{:?}]. There was no data!", index); } ,
		}
	}
}
fn main() {
	let foo = Foo { childs: vec![Some(Rc::new(5))]};

	let mut btree = BPlusTree::<i32, i32>::new(4);
	btree.insert(4, 1);
	btree.insert(3, 1);
	btree.insert(2, 1);
	btree.insert(1, 1);
	btree.insert(0, 1);
	btree.print();
	return;
}