rustdb/src/basic_structure/skiplist.rs

///# Skiplist
///<p>skiplist is an important data structure of database and many database use this as the basic structure in memory.
/// In the database I also use two Skiplist in memory to store datas temperary.</p>
///</p> We refer the source of leveldb,however we know that the first time, google use C++ writting leveldb and then rewrite it by go.</p> 


#[allow(unused)]
pub mod skip_lists
{
    
    use std::{borrow::{Borrow, BorrowMut}, cell::{Ref, RefCell}, collections::btree_map::Values, rc::Rc};
    use std::cmp::PartialOrd;
    use crate::algorithm::{baisc_data::basic_data, random};
    use crate::algorithm::baisc_data;


    pub enum InsertResult
    {
        Successful,
        Fault,
        Exist
    }
    #[derive(Debug,Clone)]
    ///## Node of skiplist
    ///
    /// <p>We will build a kv database,so the node has two members key and value.</p>
    ///
    /// <p>The node would never be used out of the mod.</p>
    struct Node<K:PartialOrd,V>
    where  K:Copy ,
           V:Clone                             
    {
        key:K,
        value:V,
        level:usize,
        forward:Vec<Option<Rc<RefCell<Node<K,V>>>>>
    }
    impl<K:PartialOrd,V> Node<K,V>
    where  K:Copy, 
           V:Clone{
        fn new(_key:K,_value:V,_level:usize)->Rc<RefCell<Self>>
        {
            Rc::new(
                RefCell::new(
                    Node
                    {
                        key:_key,
                        value:_value,
                        level:_level,
                        forward:vec![None;_level+1]
                    }
                )
            )
        }
    }
    
    
    ///## Skiplist
    /// 
    /// 
    #[derive(Debug)]
    pub struct Skiplists<K,V>
    where  K:Copy,
           K:PartialOrd,
           V:Clone 
    {
        max_level:usize,
        current_level:usize,
        current_size:usize,
        max_size:usize,
        head:Vec<Option<Rc<RefCell<Node<K,V>>>>>
    }

    impl<K:PartialOrd,V> Skiplists<K,V>
    where  K:Copy,
           V:Clone 
    {
        pub fn new(_max_size:usize)->Self
        {
            
            Skiplists
            {
                max_level:_max_size,
                current_level:0,
                current_size:0,
                max_size:basic_data::MAX_SIZE_OF_SKIPLIST,
                head:vec![None;_max_size+1]

            }
        }

        fn creat_node(_key:K,_value:V,_level:usize)->Rc<RefCell<Node<K,V>>>
        {
            Node::new(_key, _value, _level)
        }


        pub fn insert(&mut self,key:K,value:V)->InsertResult
        {
            if self.current_size==0                //如果shiplist是全空的,直接将点插入
            {
                let random_level: usize=random::random::lgc(self.max_level);
                let new_node: Rc<RefCell<Node<K, V>>>=Self::creat_node(key,value,random_level);      //创建新的节点
                for i in 0..=random_level
                {
                    self.head[i]=Some(new_node.clone());
                }
            }
            else                    //当list不为空的时候需要判定插入的位置
            {
                let random_level:usize=random::random::lgc(self.max_level);
                let mut cur_point:Option<Rc<RefCell<Node<K,V>>>>=None;
                let mut cur_node:Vec<Option<Rc<RefCell<Node<K,V>>>>>=vec![None;self.max_level];
                let mut cur_level: i32=(self.current_level-1) as i32;
                
                while(cur_level>=0)
                {
                    
                    if self.head[cur_level as usize].is_none()                //如果起始点为空则直接跳过（在这一层不会有节点）
                    {
                        cur_level=cur_level-1;
                        continue;
                    }
                    else {                                        //判定每一层的起始位置
                        if cur_level <=((self.max_level) as i32)-2               //如果self.max_level小于2那么这个显然不成立
                        {
                            if cur_node[cur_level as usize+1].is_none()             //如果在之前的层全为空则跳过，从当前的头节点开始
                            {
                                cur_point=self.head[cur_level as usize].clone();
                                if (*(cur_point.clone().unwrap())).borrow().key<key                  //如果第一个节点key就大于当前数据（主要是没有一个空的头节点就比较复杂）
                                {
                                    cur_level=cur_level-1;
                                    continue;          
                                }
                                else if (*(cur_point.clone().unwrap())).borrow().key==key
                                {
                                    (*(*(cur_point.clone().unwrap())).borrow_mut()).value=value.clone();
                                    return InsertResult::Exist;
                                } 
                            }
                        }
                        else {
                            cur_point=cur_node[cur_level as usize+1].clone();
                        }
                        loop 
                        {
                            if (*(*(cur_point.clone().unwrap())).borrow_mut()).forward[cur_level as usize].is_none()
                            {
                                cur_node[cur_level as usize]=cur_point.clone();
                                break;
                            }
                            else if (*(((*(*(cur_point.clone().unwrap())).borrow_mut()).forward[cur_level as usize]).clone()).unwrap()).borrow().key==key
                            {
                                (*(((*(*(cur_point.clone().unwrap())).borrow_mut()).forward[cur_level as usize]).clone()).unwrap()).borrow_mut().key=key;      //将对应的节点数据修改
                                return InsertResult::Exist;
                            }
                            else if (*(((*(*(cur_point.clone().unwrap())).borrow_mut()).forward[cur_level as usize]).clone()).unwrap()).borrow().key<key
                            {
                                cur_node[cur_level as usize]=cur_point.clone();
                                break;
                            }
                            else
                            {
                                cur_point=(*((cur_point.clone()).unwrap())).borrow().forward[cur_level as usize].clone();
                            }

                        }
                        cur_level=cur_level-1;
                    }
                }
                let mut middle_ptr:Option<Rc<RefCell<Node<K,V>>>>=None;
                let mut new_nodes:Rc<RefCell<Node<K, V>>> =Self::creat_node(key, value, random_level);
                for i in 0..=random_level-1
                {
                    if cur_node[i].is_none()
                    {
                        self.head[i]=Some(new_nodes.clone());
                    }
                    else
                    {
                        (*new_nodes).borrow_mut().forward[i]=((*(*((cur_node[i].clone()).unwrap())).borrow_mut()).forward[i]).clone();
                        (*(cur_node[i].clone().unwrap())).borrow_mut().forward[i]=Some(new_nodes.clone());
                    }
                }
            }
            InsertResult::Successful
            
        }
    }
}