use std::{cell::{Ref, RefCell, RefMut}, rc::{Rc, Weak}};
use super::{Item, TreeCreable, VisitTree};
type TreeItem<K, V> = Weak<RefCell<dyn super::Tree<K, V>>>;
type NodeOption<K, V> = Option<Rc<RefCell<Node<K, V>>>>;
type HasNodeOption<K, V> = Rc<RefCell<Node<K, V>>>;
type NodeOptionVisit<'a, K, V> = Option<&'a Rc<RefCell<Node<K, V>>>>;
type NodeValue<K, V> = Rc<Item<K, V>>;
struct Node<K, V> {
values: Vec<NodeValue<K, V>>,
childs: Vec<HasNodeOption<K, V>>,
parent: NodeOption<K, V>,
tree: TreeItem<K, V>
}
impl <K: PartialOrd, V> Node<K, V> {
fn new(tree: TreeItem<K, V>, parent: NodeOption<K, V>) -> Node<K, V> {
let degree = tree
.upgrade()
.unwrap()
.as_ref()
.borrow()
.get_degree();
let u_degree: usize = degree
.try_into()
.unwrap();
Node::<K, V> {
values: Vec::with_capacity(u_degree),
childs: Vec::with_capacity(u_degree),
parent,
tree
}
}
fn contains_key(&self, key: &K) -> bool {
self
.values
.iter()
.find(|item| {
item.key == *key
})
.is_some()
}
}
fn new_node_item<K: PartialOrd, V>(tree: Weak<RefCell<dyn super::Tree<K, V>>>, parent: NodeOption<K, V>) -> NodeOption<K, V> {
Some(
Rc::new(
RefCell::new(
Node::<K, V>::new(
tree,
parent
)
)
)
)
}
fn temp_internal<K: PartialOrd, V>() -> Weak<RefCell<dyn super::Tree<K, V>>> {
let weak = Weak::<RefCell<Tree<K, V>>>::new();
let raw = weak.into_raw() as *const RefCell<dyn super::Tree<K, V>>;
unsafe { Weak::from_raw(raw) }
}
pub struct Tree<K, V> {
head: NodeOption<K, V>,
degree: i32,
internal: Weak<RefCell<dyn super::Tree<K, V>>>
}
impl <'a, K: PartialOrd, V> TreeCreable<'a, K, V> for Tree<K, V> where K: 'a, V: 'a {
fn new(degree: i32) -> impl super::Tree<K, V> + 'a {
Tree {
degree,
head: None,
internal: temp_internal()
}
}
fn init_internal(&mut self, internal: Weak<RefCell<dyn super::Tree<K, V>>>) {
self.internal = internal;
}
}
impl <K: PartialOrd, V> Tree<K, V> {
fn node_option_as_mut(node_item: &NodeOption<K, V>) -> RefMut<Node<K, V>> {
node_item.as_deref().unwrap().borrow_mut()
}
fn node_option_as(node_item: &NodeOption<K, V>) -> Ref<Node<K, V>> {
node_item.as_deref().unwrap().borrow()
}
fn create_lesser_bigger(node: &Node<K, V>) -> (NodeOption<K, V>, NodeOption<K, V>) {
let binding = node.tree
.upgrade()
.unwrap();
let tree = binding
.as_ref()
.borrow();
let degree = tree.get_degree();
let u_degree: usize = degree
.try_into()
.unwrap();
let median_key = (u_degree-1) / 2;
let lessers = node
.values
.iter()
.take(median_key);
let mut lessers_node = Node::<K, V>::new(
node.tree.clone(),
node.parent.clone()
);
for item in lessers
{
lessers_node.values.push(item.clone());
}
let lessers_node_opt = Some(Rc::new(RefCell::new(lessers_node)));
let biggers = node
.values
.iter()
.skip(median_key + 1);
let mut biggers_node = Node::<K, V>::new(
node.tree.clone(),
node.parent.clone()
);
for item in biggers
{
biggers_node.values.push(item.clone());
}
let biggers_node_opt = Some(Rc::new(RefCell::new(biggers_node)));
(lessers_node_opt, biggers_node_opt)
}
fn split(&mut self, node_item: &NodeOption<K, V>){
let mut node = node_item.as_deref().unwrap().borrow_mut();
let degree = self.degree;
let u_degree: usize = degree
.try_into()
.unwrap();
let mut new_head = false;
if node.parent.is_none() {
node.parent = new_node_item(node.tree.clone(), None);
new_head = true;
}
let (lessers_node_opt, biggers_node_opt) = Self::create_lesser_bigger(&*node);
let median_key = (u_degree-1) / 2;
let median = node.values[median_key].clone();
let parent_opt = &node.parent;
let node_ptr = &*node as *const Node<K, V>;
let lessers_node_len = Self::node_option_as(&lessers_node_opt).values.len();
for i in 0..node.childs.len() {
let mut child = node.childs[i].borrow_mut();
let mut target_node_opt = if i <= lessers_node_len {
child.parent = lessers_node_opt.clone();
Self::node_option_as_mut(&lessers_node_opt)
} else {
child.parent = biggers_node_opt.clone();
Self::node_option_as_mut(&biggers_node_opt)
};
target_node_opt.childs.push(node.childs[i].clone())
}
let parent_childs_len;
{
let mut parent = Self::node_option_as_mut(parent_opt);
parent.values.push(median);
parent_childs_len = parent.childs.len();
}
let mut new_childs = Vec::<HasNodeOption<K, V>>::with_capacity(parent_childs_len + 2);
if !new_head {
let parent = Self::node_option_as(parent_opt);
for i in 0..parent.childs.len() {
let child = &parent.childs[i];
let child_ptr = child.as_ref().as_ptr() as *const Node<K, V>;
if child_ptr == node_ptr {
new_childs.push(lessers_node_opt.unwrap());
new_childs.push(biggers_node_opt.unwrap());
for i in i + 1..parent.childs.len() {
new_childs.push(parent.childs[i].clone());
}
break;
} else {
new_childs.push(parent.childs[i].clone());
}
}
} else {
new_childs.push(lessers_node_opt.unwrap());
new_childs.push(biggers_node_opt.unwrap());
}
{
let mut parent = Self::node_option_as_mut(parent_opt);
parent.childs = new_childs;
}
if new_head {
self.head = node.parent.clone();
}
let need_parent_split = {
let parent = Self::node_option_as(parent_opt);
parent.values.len() >= u_degree
};
if need_parent_split {
self.split(&node.parent);
}
}
fn insert_at_node(&mut self, node_item: &NodeOption<K, V>, key: K, value: V) -> bool {
if node_item.is_none() {
return false
}
{
let mut node = node_item.as_deref().unwrap().borrow_mut();
node.values.push(
Rc::new(
Item {
key,
value
}
)
);
node.values.sort();
}
let u_degree: usize = self.degree
.try_into()
.unwrap();
let need_split = {
let node = node_item.as_deref().unwrap().borrow();
node.values.len() >= u_degree
};
if need_split {
self.split(node_item);
}
true
}
fn get_min_medlst_max(node: &HasNodeOption<K, V>) -> Result<(NodeValue<K, V>, Vec<NodeValue<K, V>>, NodeValue<K, V>), ()> {
let (min, medlst, max) = {
let is_empty = node.as_ref().borrow().values.is_empty();
if is_empty {
return Err(());
}
let intl_node = node.as_ref().borrow();
let mut medlst = Vec::<NodeValue<K, V>>::new();
let length = intl_node.values.len();
let values = &intl_node.values;
if length > 1 {
for item in values.iter().skip(1).take(length - 1) {
medlst.push(item.clone())
}
}
(
values.first().unwrap().clone(),
medlst,
values.last().unwrap().clone()
)
};
Ok((min, medlst, max))
}
fn get_node_to_insert(&self, key: &K) -> NodeOption<K, V> {
let mut node = self.head.clone().unwrap();
loop {
let already_exists = {
let intl_node = node.as_ref().borrow();
let already_exists = {
intl_node.contains_key(key)
let intl_node = node.as_ref().borrow()};
intl_node.contains_key(key)if already_exists {
return None;
};
if already_exists {
return None;
}
loop {
let dont_have_children = {
let intl_node = node.as_ref().borrow();
intl_node.childs.is_empty()
};
if dont_have_children {
return Some(node)
}
let result_min_medlst_max = Self::get_min_medlst_max(&node);
if result_min_medlst_max.is_err() {
return Some(node);
}
let (min, medlst, max) = result_min_medlst_max.unwrap();
let min_key = &min.key;
if *key < *min_key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs.first().unwrap().clone()
};
continue;
}
let max_key = &max.key;
if *key > *max_key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs.last().unwrap().clone()
};
continue;
}
for i in 0..medlst.len() {
let curr = &medlst[i];
if *key < curr.key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs[i + 1].clone()
};
break;
}
}
}
}
fn in_order_visit<'a>(node: &NodeOptionVisit<K, V>, cb: &Box<dyn Fn(&Item<K, V>) + 'a>){
if node.is_none() {
return;
}
let node = node.as_deref().unwrap().borrow();
for i in 0..node.childs.len() {
let child = &node.childs[i];
Self::in_order_visit(&Some(child), cb);
if i < node.values.len() {
cb(node.values[i].as_ref());
}
}
if node.childs.is_empty() {
for item in &node.values {
cb(item.as_ref())
}
}
}
}
impl <K: PartialOrd, V> super::Tree<K, V> for Tree<K, V> {
fn insert(&mut self, key: K, value: V) -> bool {
if let None = self.head {
self.head = new_node_item(
self.internal.clone(),
None
);
}
let node_to_insert = self.get_node_to_insert(&key);
if node_to_insert.is_none() {
return false;
}
self.insert_at_node(&node_to_insert, key, value)
}
fn get_degree(&self) -> i32 {
self.degree
}
fn visit(&self, visit: VisitTree<K, V>) {
match visit.order {
super::TreeOrder::InOrder =>
Self::in_order_visit(&self.head.as_ref(), &visit.cb)
}
}
}
use std::{cell::{Ref, RefCell, RefMut}, rc::{Rc, Weak}};
use super::{Item, TreeCreable, VisitTree};
type TreeItem<K, V> = Weak<RefCell<dyn super::Tree<K, V>>>;
type NodeOption<K, V> = Option<Rc<RefCell<Node<K, V>>>>;
type HasNodeOption<K, V> = Rc<RefCell<Node<K, V>>>;
type NodeOptionVisit<'a, K, V> = Option<&'a Rc<RefCell<Node<K, V>>>>;
type NodeValue<K, V> = Rc<Item<K, V>>;
struct Node<K, V> {
values: Vec<NodeValue<K, V>>,
childs: Vec<HasNodeOption<K, V>>,
parent: NodeOption<K, V>,
tree: TreeItem<K, V>
}
impl <K: PartialOrd, V> Node<K, V> {
fn new(tree: TreeItem<K, V>, parent: NodeOption<K, V>) -> Node<K, V> {
let degree = tree
.upgrade()
.unwrap()
.as_ref()
.borrow()
.get_degree();
let u_degree: usize = degree
.try_into()
.unwrap();
Node::<K, V> {
values: Vec::with_capacity(u_degree),
childs: Vec::with_capacity(u_degree),
parent,
tree
}
}
fn contains_key(&self, key: &K) -> bool {
self
.values
.iter()
.find(|item| {
item.key == *key
})
.is_some()
}
}
fn new_node_item<K: PartialOrd, V>(tree: Weak<RefCell<dyn super::Tree<K, V>>>, parent: NodeOption<K, V>) -> NodeOption<K, V> {
Some(
Rc::new(
RefCell::new(
Node::<K, V>::new(
tree,
parent
)
)
)
)
}
fn temp_internal<K: PartialOrd, V>() -> Weak<RefCell<dyn super::Tree<K, V>>> {
let weak = Weak::<RefCell<Tree<K, V>>>::new();
let raw = weak.into_raw() as *const RefCell<dyn super::Tree<K, V>>;
unsafe { Weak::from_raw(raw) }
}
pub struct Tree<K, V> {
head: NodeOption<K, V>,
degree: i32,
internal: Weak<RefCell<dyn super::Tree<K, V>>>
}
impl <'a, K: PartialOrd, V> TreeCreable<'a, K, V> for Tree<K, V> where K: 'a, V: 'a {
fn new(degree: i32) -> impl super::Tree<K, V> + 'a {
Tree {
degree,
head: None,
internal: temp_internal()
}
}
fn init_internal(&mut self, internal: Weak<RefCell<dyn super::Tree<K, V>>>) {
self.internal = internal;
}
}
impl <K: PartialOrd, V> Tree<K, V> {
fn node_option_as_mut(node_item: &NodeOption<K, V>) -> RefMut<Node<K, V>> {
node_item.as_deref().unwrap().borrow_mut()
}
fn node_option_as(node_item: &NodeOption<K, V>) -> Ref<Node<K, V>> {
node_item.as_deref().unwrap().borrow()
}
fn create_lesser_bigger(node: &Node<K, V>) -> (NodeOption<K, V>, NodeOption<K, V>) {
let binding = node.tree
.upgrade()
.unwrap();
let tree = binding
.as_ref()
.borrow();
let degree = tree.get_degree();
let u_degree: usize = degree
.try_into()
.unwrap();
let median_key = (u_degree-1) / 2;
let lessers = node
.values
.iter()
.take(median_key);
let mut lessers_node = Node::<K, V>::new(
node.tree.clone(),
node.parent.clone()
);
for item in lessers
{
lessers_node.values.push(item.clone());
}
let lessers_node_opt = Some(Rc::new(RefCell::new(lessers_node)));
let biggers = node
.values
.iter()
.skip(median_key + 1);
let mut biggers_node = Node::<K, V>::new(
node.tree.clone(),
node.parent.clone()
);
for item in biggers
{
biggers_node.values.push(item.clone());
}
let biggers_node_opt = Some(Rc::new(RefCell::new(biggers_node)));
(lessers_node_opt, biggers_node_opt)
}
fn split(&mut self, node_item: &NodeOption<K, V>){
let mut node = node_item.as_deref().unwrap().borrow_mut();
let degree = self.degree;
let u_degree: usize = degree
.try_into()
.unwrap();
let mut new_head = false;
if node.parent.is_none() {
node.parent = new_node_item(node.tree.clone(), None);
new_head = true;
}
let (lessers_node_opt, biggers_node_opt) = Self::create_lesser_bigger(&*node);
let median_key = (u_degree-1) / 2;
let median = node.values[median_key].clone();
let parent_opt = &node.parent;
let node_ptr = &*node as *const Node<K, V>;
let lessers_node_len = Self::node_option_as(&lessers_node_opt).values.len();
for i in 0..node.childs.len() {
let mut child = node.childs[i].borrow_mut();
let mut target_node_opt = if i <= lessers_node_len {
child.parent = lessers_node_opt.clone();
Self::node_option_as_mut(&lessers_node_opt)
} else {
child.parent = biggers_node_opt.clone();
Self::node_option_as_mut(&biggers_node_opt)
};
target_node_opt.childs.push(node.childs[i].clone())
}
let parent_childs_len;
{
let mut parent = Self::node_option_as_mut(parent_opt);
parent.values.push(median);
parent_childs_len = parent.childs.len();
}
let mut new_childs = Vec::<HasNodeOption<K, V>>::with_capacity(parent_childs_len + 2);
if !new_head {
let parent = Self::node_option_as(parent_opt);
for i in 0..parent.childs.len() {
let child = &parent.childs[i];
let child_ptr = child.as_ref().as_ptr() as *const Node<K, V>;
if child_ptr == node_ptr {
new_childs.push(lessers_node_opt.unwrap());
new_childs.push(biggers_node_opt.unwrap());
for i in i + 1..parent.childs.len() {
new_childs.push(parent.childs[i].clone());
}
break;
} else {
new_childs.push(parent.childs[i].clone());
}
}
} else {
new_childs.push(lessers_node_opt.unwrap());
new_childs.push(biggers_node_opt.unwrap());
}
{
let mut parent = Self::node_option_as_mut(parent_opt);
parent.childs = new_childs;
}
if new_head {
self.head = node.parent.clone();
}
let need_parent_split = {
let parent = Self::node_option_as(parent_opt);
parent.values.len() >= u_degree
};
if need_parent_split {
self.split(&node.parent);
}
}
fn insert_at_node(&mut self, node_item: &NodeOption<K, V>, key: K, value: V) -> bool {
if node_item.is_none() {
return false
}
{
let mut node = node_item.as_deref().unwrap().borrow_mut();
node.values.push(
Rc::new(
Item {
key,
value
}
)
);
node.values.sort();
}
let u_degree: usize = self.degree
.try_into()
.unwrap();
let need_split = {
let node = node_item.as_deref().unwrap().borrow();
node.values.len() >= u_degree
};
if need_split {
self.split(node_item);
}
true
}
fn get_min_medlst_max(node: &HasNodeOption<K, V>) -> Result<(NodeValue<K, V>, Vec<NodeValue<K, V>>, NodeValue<K, V>), ()> {
let (min, medlst, max) = {
let is_empty = node.as_ref().borrow().values.is_empty();
if is_empty {
return Err(());
}
let intl_node = node.as_ref().borrow();
let mut medlst = Vec::<NodeValue<K, V>>::new();
let length = intl_node.values.len();
let values = &intl_node.values;
if length > 1 {
for item in values.iter().skip(1).take(length - 1) {
medlst.push(item.clone())
}
}
(
values.first().unwrap().clone(),
medlst,
values.last().unwrap().clone()
)
};
Ok((min, medlst, max))
}
fn get_node_to_insert(&self, key: &K) -> NodeOption<K, V> {
let mut node = self.head.clone().unwrap();
let already_exists = {
let intl_node = node.as_ref().borrow();
intl_node.contains_key(key)
};
if already_exists {
return None;
}
loop {
let dont_have_children = {
let intl_node = node.as_ref().borrow();
intl_node.childs.is_empty()
};
if dont_have_children {
return Some(node)
}
let result_min_medlst_max = Self::get_min_medlst_max(&node);
if result_min_medlst_max.is_err() {
return Some(node);
}
let (min, medlst, max) = result_min_medlst_max.unwrap();
let min_key = &min.key;
if *key < *min_key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs.first().unwrap().clone()
};
continue;
}
let max_key = &max.key;
if *key > *max_key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs.last().unwrap().clone()
};
continue;
}
for i in 0..medlst.len() {
let curr = &medlst[i];
if *key < curr.key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs[i + 1].clone()
};
break;
}
}
}
}
fn in_order_visit<'a>(node: &NodeOptionVisit<K, V>, cb: &Box<dyn Fn(&Item<K, V>) + 'a>){
if node.is_none() {
return;
}
let node = node.as_deref().unwrap().borrow();
for i in 0..node.childs.len() {
let child = &node.childs[i];
Self::in_order_visit(&Some(child), cb);
if i < node.values.len() {
cb(node.values[i].as_ref());
}
}
if node.childs.is_empty() {
for item in &node.values {
cb(item.as_ref())
}
}
}
}
impl <K: PartialOrd, V> super::Tree<K, V> for Tree<K, V> {
fn insert(&mut self, key: K, value: V) -> bool {
if let None = self.head {
self.head = new_node_item(
self.internal.clone(),
None
);
}
let node_to_insert = self.get_node_to_insert(&key);
if node_to_insert.is_none() {
return false;
}
self.insert_at_node(&node_to_insert, key, value)
}
fn get_degree(&self) -> i32 {
self.degree
}
fn visit(&self, visit: VisitTree<K, V>) {
match visit.order {
super::TreeOrder::InOrder =>
Self::in_order_visit(&self.head.as_ref(), &visit.cb)
}
}
}
use std::{cell::{Ref, RefCell, RefMut}, rc::{Rc, Weak}};
use super::{Item, TreeCreable, VisitTree};
type TreeItem<K, V> = Weak<RefCell<dyn super::Tree<K, V>>>;
type NodeOption<K, V> = Option<Rc<RefCell<Node<K, V>>>>;
type HasNodeOption<K, V> = Rc<RefCell<Node<K, V>>>;
type NodeOptionVisit<'a, K, V> = Option<&'a Rc<RefCell<Node<K, V>>>>;
type NodeValue<K, V> = Rc<Item<K, V>>;
struct Node<K, V> {
values: Vec<NodeValue<K, V>>,
childs: Vec<HasNodeOption<K, V>>,
parent: NodeOption<K, V>,
tree: TreeItem<K, V>
}
impl <K: PartialOrd, V> Node<K, V> {
fn new(tree: TreeItem<K, V>, parent: NodeOption<K, V>) -> Node<K, V> {
let degree = tree
.upgrade()
.unwrap()
.as_ref()
.borrow()
.get_degree();
let u_degree: usize = degree
.try_into()
.unwrap();
Node::<K, V> {
values: Vec::with_capacity(u_degree),
childs: Vec::with_capacity(u_degree),
parent,
tree
}
}
fn contains_key(&self, key: &K) -> bool {
self
.values
.iter()
.find(|item| {
item.key == *key
})
.is_some()
}
}
fn new_node_item<K: PartialOrd, V>(tree: Weak<RefCell<dyn super::Tree<K, V>>>, parent: NodeOption<K, V>) -> NodeOption<K, V> {
Some(
Rc::new(
RefCell::new(
Node::<K, V>::new(
tree,
parent
)
)
)
)
}
fn temp_internal<K: PartialOrd, V>() -> Weak<RefCell<dyn super::Tree<K, V>>> {
let weak = Weak::<RefCell<Tree<K, V>>>::new();
let raw = weak.into_raw() as *const RefCell<dyn super::Tree<K, V>>;
unsafe { Weak::from_raw(raw) }
}
pub struct Tree<K, V> {
head: NodeOption<K, V>,
degree: i32,
internal: Weak<RefCell<dyn super::Tree<K, V>>>
}
impl <'a, K: PartialOrd, V> TreeCreable<'a, K, V> for Tree<K, V> where K: 'a, V: 'a {
fn new(degree: i32) -> impl super::Tree<K, V> + 'a {
Tree {
degree,
head: None,
internal: temp_internal()
}
}
fn init_internal(&mut self, internal: Weak<RefCell<dyn super::Tree<K, V>>>) {
self.internal = internal;
}
}
impl <K: PartialOrd, V> Tree<K, V> {
fn node_option_as_mut(node_item: &NodeOption<K, V>) -> RefMut<Node<K, V>> {
node_item.as_deref().unwrap().borrow_mut()
}
fn node_option_as(node_item: &NodeOption<K, V>) -> Ref<Node<K, V>> {
node_item.as_deref().unwrap().borrow()
}
fn create_lesser_bigger(node: &Node<K, V>) -> (NodeOption<K, V>, NodeOption<K, V>) {
let binding = node.tree
.upgrade()
.unwrap();
let tree = binding
.as_ref()
.borrow();
let degree = tree.get_degree();
let u_degree: usize = degree
.try_into()
.unwrap();
let median_key = (u_degree-1) / 2;
let lessers = node
.values
.iter()
.take(median_key);
let mut lessers_node = Node::<K, V>::new(
node.tree.clone(),
node.parent.clone()
);
for item in lessers
{
lessers_node.values.push(item.clone());
}
let lessers_node_opt = Some(Rc::new(RefCell::new(lessers_node)));
let biggers = node
.values
.iter()
.skip(median_key + 1);
let mut biggers_node = Node::<K, V>::new(
node.tree.clone(),
node.parent.clone()
);
for item in biggers
{
biggers_node.values.push(item.clone());
}
let biggers_node_opt = Some(Rc::new(RefCell::new(biggers_node)));
(lessers_node_opt, biggers_node_opt)
}
fn split(&mut self, node_item: &NodeOption<K, V>){
let mut node = node_item.as_deref().unwrap().borrow_mut();
let degree = self.degree;
let u_degree: usize = degree
.try_into()
.unwrap();
let mut new_head = false;
if node.parent.is_none() {
node.parent = new_node_item(node.tree.clone(), None);
new_head = true;
}
let (lessers_node_opt, biggers_node_opt) = Self::create_lesser_bigger(&*node);
let median_key = (u_degree-1) / 2;
let median = node.values[median_key].clone();
let parent_opt = &node.parent;
let node_ptr = &*node as *const Node<K, V>;
let lessers_node_len = Self::node_option_as(&lessers_node_opt).values.len();
for i in 0..node.childs.len() {
let mut child = node.childs[i].borrow_mut();
let mut target_node_opt = if i <= lessers_node_len {
child.parent = lessers_node_opt.clone();
Self::node_option_as_mut(&lessers_node_opt)
} else {
child.parent = biggers_node_opt.clone();
Self::node_option_as_mut(&biggers_node_opt)
};
target_node_opt.childs.push(node.childs[i].clone())
}
let parent_childs_len;
{
let mut parent = Self::node_option_as_mut(parent_opt);
parent.values.push(median);
parent_childs_len = parent.childs.len();
}
let mut new_childs = Vec::<HasNodeOption<K, V>>::with_capacity(parent_childs_len + 2);
if !new_head {
let parent = Self::node_option_as(parent_opt);
for i in 0..parent.childs.len() {
let child = &parent.childs[i];
let child_ptr = child.as_ref().as_ptr() as *const Node<K, V>;
if child_ptr == node_ptr {
new_childs.push(lessers_node_opt.unwrap());
new_childs.push(biggers_node_opt.unwrap());
for i in i + 1..parent.childs.len() {
new_childs.push(parent.childs[i].clone());
}
break;
} else {
new_childs.push(parent.childs[i].clone());
}
}
} else {
new_childs.push(lessers_node_opt.unwrap());
new_childs.push(biggers_node_opt.unwrap());
}
{
let mut parent = Self::node_option_as_mut(parent_opt);
parent.childs = new_childs;
}
if new_head {
self.head = node.parent.clone();
}
let need_parent_split = {
let parent = Self::node_option_as(parent_opt);
parent.values.len() >= u_degree
};
if need_parent_split {
self.split(&node.parent);
}
}
fn insert_at_node(&mut self, node_item: &NodeOption<K, V>, key: K, value: V) -> bool {
if node_item.is_none() {
return false
}
{
let mut node = node_item.as_deref().unwrap().borrow_mut();
node.values.push(
Rc::new(
Item {
key,
value
}
)
);
node.values.sort();
}
let u_degree: usize = self.degree
.try_into()
.unwrap();
let need_split = {
let node = node_item.as_deref().unwrap().borrow();
node.values.len() >= u_degree
};
if need_split {
self.split(node_item);
}
true
}
fn get_min_medlst_max(node: &HasNodeOption<K, V>) -> Result<(NodeValue<K, V>, Vec<NodeValue<K, V>>, NodeValue<K, V>), ()> {
let (min, medlst, max) = {
let is_empty = node.as_ref().borrow().values.is_empty();
if is_empty {
return Err(());
}
let intl_node = node.as_ref().borrow();
let mut medlst = Vec::<NodeValue<K, V>>::new();
let length = intl_node.values.len();
let values = &intl_node.values;
if length > 1 {
for item in values.iter().skip(1).take(length - 1) {
medlst.push(item.clone())
}
}
(
values.first().unwrap().clone(),
medlst,
values.last().unwrap().clone()
)
};
Ok((min, medlst, max))
}
fn get_node_to_insert(&self, key: &K) -> NodeOption<K, V> {
let mut node = self.head.clone().unwrap();
loop {
let already_exists = {
let intl_node = node.as_ref().borrow();
intl_node.contains_key(key)
};
if already_exists {
return None;
}
let dont_have_children = {
let intl_node = node.as_ref().borrow();
intl_node.childs.is_empty()
};
if dont_have_children {
return Some(node)
}
let result_min_medlst_max = Self::get_min_medlst_max(&node);
if result_min_medlst_max.is_err() {
return Some(node);
}
let (min, medlst, max) = result_min_medlst_max.unwrap();
let min_key = &min.key;
if *key < *min_key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs.first().unwrap().clone()
};
continue;
}
let max_key = &max.key;
if *key > *max_key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs.last().unwrap().clone()
};
continue;
}
for i in 0..medlst.len() {
let curr = &medlst[i];
if *key < curr.key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs[i + 1].clone()
};
break;
}
}
}
}
fn in_order_visit<'a>(node: &NodeOptionVisit<K, V>, cb: &Box<dyn Fn(&Item<K, V>) + 'a>){
if node.is_none() {
return;
}
let node = node.as_deref().unwrap().borrow();
for i in 0..node.childs.len() {
let child = &node.childs[i];
Self::in_order_visit(&Some(child), cb);
if i < node.values.len() {
cb(node.values[i].as_ref());
}
}
if node.childs.is_empty() {
for item in &node.values {
cb(item.as_ref())
}
}
}
}
impl <K: PartialOrd, V> super::Tree<K, V> for Tree<K, V> {
fn insert(&mut self, key: K, value: V) -> bool {
if let None = self.head {
self.head = new_node_item(
self.internal.clone(),
None
);
}
let node_to_insert = self.get_node_to_insert(&key);
if node_to_insert.is_none() {
return false;
}
self.insert_at_node(&node_to_insert, key, value)
}
fn get_degree(&self) -> i32 {
self.degree
}
fn visit(&self, visit: VisitTree<K, V>) {
match visit.order {
super::TreeOrder::InOrder =>
Self::in_order_visit(&self.head.as_ref(), &visit.cb)
}
}
}
Rust implementation of a BTree
I'm studying rust, and I decided to implement a BTree as a way of learning the language.
Can anyone give me suggestions on the code?
As the language has no inheritance, and we must replace it with delegation, I believe I am a little lost in the concepts of an object-oriented language.
My concerns
1. Best Practices
I believe that my code has many changes to be made so that it meets the conditions of good practice in the Rust language.It's worth mentioning that I started with the book Rust by example.
2. Performance
One thing I noticed was that my implementation is at least 2.1x slower than the official one in std::collections
The code
btree/mod.rs
use std::{borrow::Borrow, cell::RefCell, cmp::Ordering, ops::{Deref, DerefMut}, rc::{Rc, Weak}};
mod non_concurrent;
mod tests;
pub enum TreeOrder {
InOrder
}
pub struct VisitTree<'a, K: PartialOrd, V> {
order: TreeOrder,
cb: Box<dyn Fn(&Item<K, V>) + 'a>
}
impl<'a, K: PartialOrd, V> VisitTree<'a, K, V> {
fn new(order: TreeOrder, cb: impl Fn(&Item<K, V>) + 'a) -> VisitTree<'a, K, V> {
VisitTree {
order,
cb: Box::new(cb)
}
}
}
pub trait Tree<K: PartialOrd, V> {
fn insert(&mut self, key: K, value: V) -> bool;
fn get_degree(&self) -> i32;
fn visit(&self, visit: VisitTree<K, V>);
}
trait TreeCreable<'a, K: PartialOrd, V>: Tree<K, V> {
fn new(degree: i32) -> impl Tree<K, V> + 'a;
fn init_internal(&mut self, internal: Weak<RefCell<dyn Tree<K, V>>>);
}
type DefaultTree<K, V> = non_concurrent::Tree<K, V>;
pub struct Item<K, V> {
key: K,
value: V
}
impl<K: PartialOrd, V> Ord for Item<K, V> {
fn cmp(&self, other: &Self) -> Ordering {
self.key.partial_cmp(&other.key).unwrap()
}
}
impl<K: PartialOrd, V> PartialOrd for Item<K, V> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl<K: PartialOrd, V> PartialEq for Item<K, V> {
fn eq(&self, other: &Self) -> bool {
self.key == other.key
}
}
impl<K: PartialOrd, V> Eq for Item<K, V> {}
pub struct BTree<'a, K, V> {
internal: Rc<RefCell<dyn Tree<K, V> + 'a>>
}
pub enum TreeType {
Default,
NonConcurrent
}
impl <'a, K: PartialOrd, V> BTree<'a, K, V> where K: 'a, V: 'a {
fn intl_create<A: TreeCreable<'a, K, V>>(degree: i32) -> BTree<'a, K, V> {
let internal =
Rc::new(
RefCell::new(
A::new(degree)
)
);
let weak = Rc::downgrade(&internal);
let raw = weak.into_raw() as *const RefCell<dyn Tree<K, V>>;
let weak = unsafe { Weak::from_raw(raw) };
let new_raw = raw as *const RefCell<A>;
let new_weak = unsafe { Weak::from_raw(new_raw) };
let rc = new_weak
.borrow()
.upgrade()
.unwrap();
let mut item = rc
.as_ref()
.borrow_mut();
item.init_internal(weak);
BTree {
internal
}
}
pub fn new(tree_type: TreeType, degree: i32) -> BTree<'a, K, V> {
use TreeType::*;
match tree_type {
Default => {
BTree::<K, V>::intl_create::<DefaultTree<K, V>>(degree)
},
NonConcurrent => {
BTree::<K, V>::intl_create::<non_concurrent::Tree<K, V>>(degree)
}
}
}
}
impl <'a, K, V> Deref for BTree<'a, K, V> where 'a: 'static {
type Target = dyn Tree<K, V>;
fn deref(&self) -> &Self::Target {
unsafe { &*self.internal.as_ptr() }
}
}
impl <'a, K, V> DerefMut for BTree<'a, K, V> where 'a: 'static {
fn deref_mut(&mut self) -> &mut Self::Target {
unsafe { &mut *self.internal.as_ptr() }
}
}
btree/non_concurrent.rs
use std::{cell::{Ref, RefCell, RefMut}, rc::{Rc, Weak}};
use super::{Item, TreeCreable, VisitTree};
type TreeItem<K, V> = Weak<RefCell<dyn super::Tree<K, V>>>;
type NodeOption<K, V> = Option<Rc<RefCell<Node<K, V>>>>;
type HasNodeOption<K, V> = Rc<RefCell<Node<K, V>>>;
type NodeOptionVisit<'a, K, V> = Option<&'a Rc<RefCell<Node<K, V>>>>;
type NodeValue<K, V> = Rc<Item<K, V>>;
struct Node<K, V> {
values: Vec<NodeValue<K, V>>,
childs: Vec<HasNodeOption<K, V>>,
parent: NodeOption<K, V>,
tree: TreeItem<K, V>
}
impl <K: PartialOrd, V> Node<K, V> {
fn new(tree: TreeItem<K, V>, parent: NodeOption<K, V>) -> Node<K, V> {
let degree = tree
.upgrade()
.unwrap()
.as_ref()
.borrow()
.get_degree();
let u_degree: usize = degree
.try_into()
.unwrap();
Node::<K, V> {
values: Vec::with_capacity(u_degree),
childs: Vec::with_capacity(u_degree),
parent,
tree
}
}
fn contains_key(&self, key: &K) -> bool {
self
.values
.iter()
.find(|item| {
item.key == *key
})
.is_some()
}
}
fn new_node_item<K: PartialOrd, V>(tree: Weak<RefCell<dyn super::Tree<K, V>>>, parent: NodeOption<K, V>) -> NodeOption<K, V> {
Some(
Rc::new(
RefCell::new(
Node::<K, V>::new(
tree,
parent
)
)
)
)
}
fn temp_internal<K: PartialOrd, V>() -> Weak<RefCell<dyn super::Tree<K, V>>> {
let weak = Weak::<RefCell<Tree<K, V>>>::new();
let raw = weak.into_raw() as *const RefCell<dyn super::Tree<K, V>>;
unsafe { Weak::from_raw(raw) }
}
pub struct Tree<K, V> {
head: NodeOption<K, V>,
degree: i32,
internal: Weak<RefCell<dyn super::Tree<K, V>>>
}
impl <'a, K: PartialOrd, V> TreeCreable<'a, K, V> for Tree<K, V> where K: 'a, V: 'a {
fn new(degree: i32) -> impl super::Tree<K, V> + 'a {
Tree {
degree,
head: None,
internal: temp_internal()
}
}
fn init_internal(&mut self, internal: Weak<RefCell<dyn super::Tree<K, V>>>) {
self.internal = internal;
}
}
impl <K: PartialOrd, V> Tree<K, V> {
fn node_option_as_mut(node_item: &NodeOption<K, V>) -> RefMut<Node<K, V>> {
node_item.as_deref().unwrap().borrow_mut()
}
fn node_option_as(node_item: &NodeOption<K, V>) -> Ref<Node<K, V>> {
node_item.as_deref().unwrap().borrow()
}
fn create_lesser_bigger(node: &Node<K, V>) -> (NodeOption<K, V>, NodeOption<K, V>) {
let binding = node.tree
.upgrade()
.unwrap();
let tree = binding
.as_ref()
.borrow();
let degree = tree.get_degree();
let u_degree: usize = degree
.try_into()
.unwrap();
let median_key = (u_degree-1) / 2;
let lessers = node
.values
.iter()
.take(median_key);
let mut lessers_node = Node::<K, V>::new(
node.tree.clone(),
node.parent.clone()
);
for item in lessers
{
lessers_node.values.push(item.clone());
}
let lessers_node_opt = Some(Rc::new(RefCell::new(lessers_node)));
let biggers = node
.values
.iter()
.skip(median_key + 1);
let mut biggers_node = Node::<K, V>::new(
node.tree.clone(),
node.parent.clone()
);
for item in biggers
{
biggers_node.values.push(item.clone());
}
let biggers_node_opt = Some(Rc::new(RefCell::new(biggers_node)));
(lessers_node_opt, biggers_node_opt)
}
fn split(&mut self, node_item: &NodeOption<K, V>){
let mut node = node_item.as_deref().unwrap().borrow_mut();
let degree = self.degree;
let u_degree: usize = degree
.try_into()
.unwrap();
let mut new_head = false;
if node.parent.is_none() {
node.parent = new_node_item(node.tree.clone(), None);
new_head = true;
}
let (lessers_node_opt, biggers_node_opt) = Self::create_lesser_bigger(&*node);
let median_key = (u_degree-1) / 2;
let median = node.values[median_key].clone();
let parent_opt = &node.parent;
let node_ptr = &*node as *const Node<K, V>;
let lessers_node_len = Self::node_option_as(&lessers_node_opt).values.len();
for i in 0..node.childs.len() {
let mut child = node.childs[i].borrow_mut();
let mut target_node_opt = if i <= lessers_node_len {
child.parent = lessers_node_opt.clone();
Self::node_option_as_mut(&lessers_node_opt)
} else {
child.parent = biggers_node_opt.clone();
Self::node_option_as_mut(&biggers_node_opt)
};
target_node_opt.childs.push(node.childs[i].clone())
}
let parent_childs_len;
{
let mut parent = Self::node_option_as_mut(parent_opt);
parent.values.push(median);
parent_childs_len = parent.childs.len();
}
let mut new_childs = Vec::<HasNodeOption<K, V>>::with_capacity(parent_childs_len + 2);
if !new_head {
let parent = Self::node_option_as(parent_opt);
for i in 0..parent.childs.len() {
let child = &parent.childs[i];
let child_ptr = child.as_ref().as_ptr() as *const Node<K, V>;
if child_ptr == node_ptr {
new_childs.push(lessers_node_opt.unwrap());
new_childs.push(biggers_node_opt.unwrap());
for i in i + 1..parent.childs.len() {
new_childs.push(parent.childs[i].clone());
}
break;
} else {
new_childs.push(parent.childs[i].clone());
}
}
} else {
new_childs.push(lessers_node_opt.unwrap());
new_childs.push(biggers_node_opt.unwrap());
}
{
let mut parent = Self::node_option_as_mut(parent_opt);
parent.childs = new_childs;
}
if new_head {
self.head = node.parent.clone();
}
let need_parent_split = {
let parent = Self::node_option_as(parent_opt);
parent.values.len() >= u_degree
};
if need_parent_split {
self.split(&node.parent);
}
}
fn insert_at_node(&mut self, node_item: &NodeOption<K, V>, key: K, value: V) -> bool {
if node_item.is_none() {
return false
}
{
let mut node = node_item.as_deref().unwrap().borrow_mut();
node.values.push(
Rc::new(
Item {
key,
value
}
)
);
node.values.sort();
}
let u_degree: usize = self.degree
.try_into()
.unwrap();
let need_split = {
let node = node_item.as_deref().unwrap().borrow();
node.values.len() >= u_degree
};
if need_split {
self.split(node_item);
}
true
}
fn get_min_medlst_max(node: &HasNodeOption<K, V>) -> Result<(NodeValue<K, V>, Vec<NodeValue<K, V>>, NodeValue<K, V>), ()> {
let (min, medlst, max) = {
let is_empty = node.as_ref().borrow().values.is_empty();
if is_empty {
return Err(());
}
let intl_node = node.as_ref().borrow();
let mut medlst = Vec::<NodeValue<K, V>>::new();
let length = intl_node.values.len();
let values = &intl_node.values;
if length > 1 {
for item in values.iter().skip(1).take(length - 1) {
medlst.push(item.clone())
}
}
(
values.first().unwrap().clone(),
medlst,
values.last().unwrap().clone()
)
};
Ok((min, medlst, max))
}
fn get_node_to_insert(&self, key: &K) -> NodeOption<K, V> {
let mut node = self.head.clone().unwrap();
let already_exists = {
let intl_node = node.as_ref().borrow();
intl_node.contains_key(key)
};
if already_exists {
return None;
}
loop {
let dont_have_children = {
let intl_node = node.as_ref().borrow();
intl_node.childs.is_empty()
};
if dont_have_children {
return Some(node)
}
let result_min_medlst_max = Self::get_min_medlst_max(&node);
if result_min_medlst_max.is_err() {
return Some(node);
}
let (min, medlst, max) = result_min_medlst_max.unwrap();
let min_key = &min.key;
if *key < *min_key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs.first().unwrap().clone()
};
continue;
}
let max_key = &max.key;
if *key > *max_key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs.last().unwrap().clone()
};
continue;
}
for i in 0..medlst.len() {
let curr = &medlst[i];
if *key < curr.key {
node = {
let intl_node = node.as_ref().borrow();
intl_node.childs[i + 1].clone()
};
break;
}
}
}
}
fn in_order_visit<'a>(node: &NodeOptionVisit<K, V>, cb: &Box<dyn Fn(&Item<K, V>) + 'a>){
if node.is_none() {
return;
}
let node = node.as_deref().unwrap().borrow();
for i in 0..node.childs.len() {
let child = &node.childs[i];
Self::in_order_visit(&Some(child), cb);
if i < node.values.len() {
cb(node.values[i].as_ref());
}
}
if node.childs.is_empty() {
for item in &node.values {
cb(item.as_ref())
}
}
}
}
impl <K: PartialOrd, V> super::Tree<K, V> for Tree<K, V> {
fn insert(&mut self, key: K, value: V) -> bool {
if let None = self.head {
self.head = new_node_item(
self.internal.clone(),
None
);
}
let node_to_insert = self.get_node_to_insert(&key);
if node_to_insert.is_none() {
return false;
}
self.insert_at_node(&node_to_insert, key, value)
}
fn get_degree(&self) -> i32 {
self.degree
}
fn visit(&self, visit: VisitTree<K, V>) {
match visit.order {
super::TreeOrder::InOrder =>
Self::in_order_visit(&self.head.as_ref(), &visit.cb)
}
}
}
btree/tests.rs
use crate::btree::{TreeOrder, VisitTree};
use super::{BTree, TreeType};
#[test]
fn btree_non_concurrent_can_insert(){
let mut tree: BTree<i32, i32> = BTree::new(TreeType::NonConcurrent, 6);
for i in 1..101 {
tree.insert(i, i);
}
println!("Key: {}", "Donnne!!");
tree.visit(
VisitTree::new(TreeOrder::InOrder, |item|{
println!("Value: {}", item.value);
})
);
println!("Success??!!");
}
If possible, I would like to ask for special attention in terms of performance.
Why is the implementation of std::collections::BTreeMap much faster than the current one? Does it perhaps use unsafe lines or something like that?
lang-rust