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) -> &mut AbstractNode<K, V>;
	fn get_childern_count(&self) -> usize;
	fn insert(&mut self, max_degree: usize, k: K, v: V) -> (Option<Box<AbstractNode<K, V>>>, Option<Box<AbstractNode<K, V>>>);
	fn split(&mut self) -> (Rc<AbstractNode<K, V>>, K);
}

fn choose_subtree<'a, K: Ord + Debug + Clone, V: Clone + Debug>(root: &'a mut AbstractNode<K, V>, k: &K) ->  &'a mut AbstractNode<K, V>{
    	match root.node_type() {
    		NodeType::Leaf => { return root;}
    		NodeType::Node	=> {
    			let index = upper_bound(root.keys(), &k);
    			println!("Child index: {:?}", index);
    			let mut child = root.get_child(index);
    			return choose_subtree(child, k);
    		}
    	}
}

struct Node<K, V> {
    keys: Vec<K>,
    childern: Vec<Option<Rc<AbstractNode<K, V>>>>,
    childern_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.childern_count <= self.childern.len());
		let max_key = node.max_key();
		let index = upper_bound(self.keys.as_slice(), &max_key);
		self.childern[index as usize] = Some(node);
		self.childern_count += 1;
		println!("max_key: {:?}, Index: {:?}, keys: {:?}", max_key, index, self.keys);
	}
	fn get_child(&self, index: usize) -> &mut AbstractNode<K, V>{
		let c = &self.childern[index];
		match *c {
		    Some(ref mut node) => return &mut **node,
		    None => { panic!("get_child for index[{:?}]. There was no data!", index); } ,
		}
	}
	fn get_childern_count(&self) -> usize { self.childern_count}
	fn insert(&mut self, max_degree: usize, k: K, v: V) -> (Option<Box<AbstractNode<K, V>>>, Option<Box<AbstractNode<K, V>>>){

		return (Option::None, Option::None);
	}
	fn split(&mut self) -> (Rc<AbstractNode<K, V>>, K){ unimplemented!();}
}
impl<K, V> Node<K, V> {
    pub fn new(count: usize) -> Self {
    	let mut childern = Vec::<Option<Rc<AbstractNode<K, V>>>>::with_capacity(count + 1);
    	for i in 0..count + 1{
    		childern.push(Option::None);
    	}
        Node {
            keys: Vec::<K>::with_capacity(count),
            childern: childern,
            childern_count: 0
        }
    }
}

struct Leaf<K: Ord + Debug + Clone + 'static, V: Clone + Debug + 'static> {
    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_childern_count(&self) -> usize { unimplemented!();}
	fn get_child(&self, index: usize) -> &mut AbstractNode<K, V>{ unimplemented!();}
	fn insert(&mut self, max_degree: usize, k: K, v: V) -> (Option<Box<AbstractNode<K, V>>>, Option<Box<AbstractNode<K, V>>>){
		if self.keys_count() >= max_degree - 1{
			let (new_leaf, min_key_in_new_leaf) = self.split();
		}
		return (Option::None, Option::None);
	}
	fn split(&mut self) -> (Rc<AbstractNode<K, V>>, K) {
		// Break down the node into two partitions.
		// The first should hold ceil of (N-1)/2 key values
		// The second partition can hold rest of the key values
		let keys_cnt = self.keys_count();
		let first_hold = ((keys_cnt - 1) as f32 / 2 as f32) as usize;
		let mut new_leaf = Leaf::<K, V>::new(self.keys.capacity());
		let min_key_in_new_leaf = self.keys[first_hold].clone();
		let original_next = self.next.clone();
		for i in first_hold..keys_cnt{
			let k = self.keys[i].clone();
			let v = self.values[i].clone();
			new_leaf.add_key_value(k, v);
		}
		for i in first_hold..keys_cnt{
			self.keys.remove(first_hold);
			self.values.remove(first_hold);
		}
		new_leaf.next = original_next;
		let new_leaf = Rc::new(new_leaf);
		self.next = Some(new_leaf.clone());
		return (new_leaf, min_key_in_new_leaf);
	}
}
impl<K: Ord + Debug + Clone, V: Clone + Debug> 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(&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());
    	let mut node = choose_subtree(&mut *self.root, &k);
    	println!("Node type: {:?}", node.node_type());
    	// print_type_of(&node);
    	let (new_child, new_pivot) = node.insert(self.max_degree as usize, k, v);
    	
    	// 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!. childern: {:?}", self.root.get_childern_count());
    	//      	let node = self.choose_subtree(&*self.root, &k);
    	//      	println!("Node type: {:?}", node.node_type());
    	//      },
    	//  }
    }   
    pub fn print(&self){
    	self.root.print_values();
    }
}
fn main() {
	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;
}