consistent_hasher/
circularbtreemap.rs

use crate::node::Node;
use std::borrow::BorrowMut;

use std::fmt;
use std::{cell::RefCell, cmp::Ordering, fmt::Debug, rc::Rc};

#[derive(Debug)]
pub enum BTreeError {
    NodeNotFound,
    DuplicateKey,
    InvalidOperation,
    EmptyTree,
    Other(String),
}

impl std::fmt::Display for BTreeError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            BTreeError::NodeNotFound => write!(f, "Node not found in the binary search tree."),
            BTreeError::DuplicateKey => {
                write!(f, "Duplicate key detected in the binary search tree.")
            }
            BTreeError::InvalidOperation => {
                write!(f, "Invalid operation on the binary search tree.")
            }
            BTreeError::EmptyTree => write!(f, "The binary search tree is empty."),
            BTreeError::Other(message) => write!(f, "Error: {}", message),
        }
    }
}

impl std::error::Error for BTreeError {}

#[derive(Debug)]
pub struct CircularBTreeMap<T: Ord> {
    head: Option<Rc<RefCell<Node<T>>>>,
    left_most: Option<Rc<RefCell<Node<T>>>>,
    right_most: Option<Rc<RefCell<Node<T>>>>,
    nodes_count: usize,
}

impl<T: Ord + fmt::Display + Debug + Clone> CircularBTreeMap<T> {
    pub fn new() -> Self {
        Self {
            head: None,
            left_most: None,
            right_most: None,
            nodes_count: 0,
        }
    }

    fn update_cache(&mut self) {
        self.left_most = Some(Self::get_min(&self.head.clone().unwrap()));
        self.right_most = Some(Self::get_max(&self.head.clone().unwrap()));
    }

    pub fn insert_node(&mut self, node_val: T) -> Result<(T,T), BTreeError> {
        let mut new_node = Node::new(node_val);
        if self.head.is_none() {
            let temp = new_node.key.clone();
            self.head = Some(Rc::new(RefCell::new(new_node)));
            self.left_most = Some(self.head.as_ref().unwrap().clone());
            self.right_most = Some(self.head.as_ref().unwrap().clone());
            self.nodes_count = 1;
            return Ok((temp.clone(),temp));
        }

        let mut current = self.head.as_ref().unwrap().clone();
        let mut left_most: Option<Rc<RefCell<Node<T>>>> = None;
        let mut right_most: Option<Rc<RefCell<Node<T>>>> = None;
        loop {
            let cmp_result = RefCell::borrow(&current).key.cmp(&new_node.key);
            match cmp_result {
                Ordering::Less => {
                    let next = RefCell::borrow(&current)
                        .right
                        .as_ref()
                        .map(|right| right.clone());
                    right_most = Some(current.clone());
                    if let Some(right) = next {
                        current = right;
                    } else {
                        RefCell::borrow_mut(&current).right = Some(Rc::new(RefCell::new(new_node)));
                        self.nodes_count += 1;
                        break;
                    }
                }
                Ordering::Greater => {
                    let next = RefCell::borrow(&current)
                        .left
                        .as_ref()
                        .map(|left| left.clone());
                    left_most = Some(current.clone());
                    if let Some(left) = next {
                        current = left;
                    } else {
                        RefCell::borrow_mut(&current).left = Some(Rc::new(RefCell::new(new_node)));
                        self.nodes_count += 1;
                        break;
                    }
                }
                Ordering::Equal => {
                    return Err(BTreeError::DuplicateKey);
                }
            }
        }

        self.update_cache();

        let temp = match (left_most,right_most)
        {
            
            (Some(x),Some(y))=>
            {
                (RefCell::borrow(&x).key.clone(),RefCell::borrow(&y).key.clone())
            },
            (Some(x),None)=>
            {
                (RefCell::borrow(&x).key.clone(),self.get_max_key().unwrap())
            },
            (None,Some(y))=>
            {
                (self.get_min_key().unwrap(),RefCell::borrow(&y).key.clone())
            },
            (None,None)=>
            {
                (self.get_min_key().unwrap(),self.get_max_key().unwrap())
            }
        };
        return Ok(temp);


    }

    pub fn delete_node(&mut self, key: &T) -> Result<(T,T), BTreeError> {
        if self.head.is_none() {
            return Err(BTreeError::EmptyTree);
        }

        let mut current = self.head.as_ref().unwrap().clone();
        let mut prev = current.clone();
        let mut left_most: Option<Rc<RefCell<Node<T>>>> = None;
        let mut right_most:Option<Rc<RefCell<Node<T>>>> = None;
        let mut rightmin: Option<Rc<RefCell<Node<T>>>> = None;
        let mut leftmax: Option<Rc<RefCell<Node<T>>>> = None;

        loop {
            let cmp_result = RefCell::borrow(&current).key.cmp(&key);
            match cmp_result {
                Ordering::Less => {
                    let next = RefCell::borrow(&current)
                        .right
                        .as_ref()
                        .map(|right| right.clone());
                    right_most = Some(current.clone());
                    if let Some(right) = next {
                        prev = current;
                        current = right;
                    } else {
                        return Err(BTreeError::NodeNotFound);
                    }
                }
                Ordering::Greater => {
                    let next = RefCell::borrow(&current)
                        .left
                        .as_ref()
                        .map(|left| left.clone());
                    left_most = Some(current.clone());
                    if let Some(left) = next {
                        prev = current;
                        current = left;
                    } else {
                        return Err(BTreeError::NodeNotFound);
                    }
                }
                Ordering::Equal => {
                    rightmin = RefCell::borrow(&current).right.clone();
                    if let Some(x) = rightmin.take() {
                        rightmin = Some(Self::get_min(&x));
                    }
                    else {
                        rightmin = None;
                    }
                    leftmax = RefCell::borrow(&current).left.clone();
                    if let Some(x) = leftmax.take() {
                        leftmax = Some(Self::get_max(&x));
                    }
                    else {
                        leftmax = None;
                    }
                    Self::move_left_to_right(&current);
                    if Rc::ptr_eq(&current, &self.head.clone().unwrap()) {
                        let new_head = RefCell::borrow(&self.head.take().unwrap()).right.clone();
                        *self.head.borrow_mut() = new_head;
                    } else {
                        if matches!(
                            RefCell::borrow(&prev)
                                .key
                                .cmp(&RefCell::borrow(&current).key),
                            Ordering::Less
                        ) {
                            RefCell::borrow_mut(&prev).right =
                                RefCell::borrow_mut(&current).right.take();
                        } else {
                            RefCell::borrow_mut(&prev).left =
                                RefCell::borrow_mut(&current).right.take();
                        }
                    }
                    self.nodes_count -= 1;
                    break;
                }
            }
        }
        if self.head.is_some() {
            self.update_cache();
        }
        else {
            return Err(BTreeError::EmptyTree);
        }

        let right_temp = match rightmin
        {
            Some(x)=>
            {
                RefCell::borrow(&x).key.clone()
            },
            None=>
            {
                match left_most {
                    Some(y)=>
                    {
                        RefCell::borrow(&y).key.clone()
                    }
                    None=>
                    {
                        self.get_min_key().unwrap()
                    }
                } 
            }
        };

        let left_temp = match leftmax
        {
            Some(x)=>
            {
                RefCell::borrow(&x).key.clone()
            },
            None=>
            {
                match right_most {
                    Some(y)=>
                    {
                        RefCell::borrow(&y).key.clone()
                    }
                    None=>
                    {
                        self.get_max_key().unwrap()
                    }
                } 
            }
        };
        return Ok((left_temp,right_temp));
    }

    fn move_left_to_right(node: &Rc<RefCell<Node<T>>>) {
        let left = RefCell::borrow_mut(&node).left.take();

        if left.is_none() {
            return;
        }

        if RefCell::borrow(&node).right.is_none() {
            RefCell::borrow_mut(&node).right = left;
            return;
        }
        let last = Self::get_min(&RefCell::borrow(&node).right.as_ref().unwrap());
        RefCell::borrow_mut(&last).left = left;
    }

    pub fn nodes_count(&self) -> usize {
        self.nodes_count
    }

    pub fn search_node(&self, key: T) -> bool {
        if self.head.is_none() {
            return false;
        }

        let mut current = self.head.as_ref().unwrap().clone();

        loop {
            let cmp_result = RefCell::borrow(&current).key.cmp(&key);
            match cmp_result {
                Ordering::Less => {
                    let next = RefCell::borrow(&current)
                        .right
                        .as_ref()
                        .map(|right| right.clone());
                    if let Some(right) = next {
                        current = right;
                    } else {
                        break;
                    }
                }
                Ordering::Greater => {
                    let next = RefCell::borrow(&current)
                        .left
                        .as_ref()
                        .map(|left| left.clone());
                    if let Some(left) = next {
                        current = left;
                    } else {
                        break;
                    }
                }
                Ordering::Equal => {
                    return true;
                }
            }
        }
        return false;
    }

    pub fn val_in_node(&self, val: &T) -> Result<T, BTreeError> {
        if self.head.is_none() {
            return Err(BTreeError::EmptyTree);
        }

        {
            let max = &self.right_most.clone().unwrap().borrow().key.clone();
            let min = &self.left_most.clone().unwrap().borrow().key.clone();
            if matches!(val.cmp(&max), Ordering::Greater) | matches!(val.cmp(&min), Ordering::Less)
            {
                return Ok(min.clone());
            }
        }

        let mut current = self.head.as_ref().unwrap().clone();
        loop {
            let cmp_result = RefCell::borrow(&current).key.cmp(&val);
            match cmp_result {
                Ordering::Equal => {
                    return Ok(current.borrow().key.clone());
                }
                Ordering::Less => {
                    let next = RefCell::borrow(&current)
                        .right
                        .as_ref()
                        .map(|right| right.clone());
                    if let Some(right) = next {
                        current = right;
                    }
                }
                Ordering::Greater => {
                    let next = RefCell::borrow(&current)
                        .left
                        .as_ref()
                        .map(|left| left.clone());
                    if let Some(left) = next {
                        if Self::get_max_value(&left).cmp(&val) == Ordering::Less {
                            return Ok(RefCell::borrow(&current).key.clone());
                        }
                        current = left;
                    } else {
                        return Ok(RefCell::borrow(&current).key.clone());
                    }
                }
            }
        }
    }

    fn get_min(branch: &Rc<RefCell<Node<T>>>) -> Rc<RefCell<Node<T>>> {
        let mut current = branch.clone();
        loop {
            let left = {
                let current_ref = RefCell::borrow(&current);
                current_ref.left.clone() // Clone the Rc<RefCell<Node<T>>> if it exists
            };

            match left {
                Some(left_node) => current = left_node,
                None => return current,
            }
        }
    }
    fn get_min_value(branch: &Rc<RefCell<Node<T>>>) -> T {
        Self::get_min(branch).try_borrow().unwrap().key.clone()
    }

    fn get_max(branch: &Rc<RefCell<Node<T>>>) -> Rc<RefCell<Node<T>>> {
        let mut current = branch.clone();
        loop {
            let right = {
                let current_ref = RefCell::borrow(&current);
                current_ref.right.clone() // Clone the Rc<RefCell<Node<T>>> if it exists
            };

            match right {
                Some(right_node) => current = right_node,
                None => return current,
            }
        }
    }
    fn get_max_value(branch: &Rc<RefCell<Node<T>>>) -> T {
        Self::get_max(branch).try_borrow().unwrap().key.clone()
    }

    pub fn get_min_key(&self) -> Option<T> {
        if self.head.is_none() {
            return None;
        }
        Some(Self::get_min_value(&self.head.clone().unwrap()))
    }
    pub fn get_max_key(&self) -> Option<T> {
        if self.head.is_none() {
            return None;
        }
        Some(Self::get_max_value(&self.head.clone().unwrap()))
    }

    pub fn print(&self) {
        CircularBTreeMap::print_rec(&self.head, 1);
        println!("nodes count: {}", self.nodes_count());
    }
    fn print_rec(head: &Option<Rc<RefCell<Node<T>>>>, level: usize) {
        if !head.is_none() {
            CircularBTreeMap::print_rec(&RefCell::borrow(&head.clone().unwrap()).right, level + 1);
            println!(
                "[{}] - {}",
                level,
                RefCell::borrow(&(head.as_ref().unwrap()))
            );
            CircularBTreeMap::print_rec(&RefCell::borrow(&head.clone().unwrap()).left, level + 1);
        }
    }
}
consistent_hasher/circularbtreemap.rs

consistent_hasher/
circularbtreemap.rs
