1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| use std::cell::RefCell; use std::rc::Rc;
type Rcc<T> = Rc<RefCell<T>>; pub fn rcc<T>(t: T) -> Rcc<T> { Rc::new(RefCell::new(t)) }
#[derive(Debug)] pub struct SkipNode<T: PartialOrd> { right: Option<Rcc<SkipNode<T>>>, down: Option<Rcc<SkipNode<T>>>, data: Rcc<T>, }
impl<T: PartialOrd> SkipNode<T> { pub fn new(t: T) -> Self { SkipNode { right: None, down: None, data: rcc(t), } }
pub fn insert(&mut self, dt: T) -> Option<Rcc<SkipNode<T>>> { if let Some(ref mut rt) = self.right { if dt > *rt.borrow().data.borrow() { return rt.borrow_mut().insert(dt); } }
if let Some(ref dw) = self.down { return match dw.borrow_mut().insert(dt) { Some(child) => match rand::random::<bool>() { true => { let dt = child.borrow().data.clone(); let nn = SkipNode { right: self.right.take(), data: dt, down: Some(child), }; let res = rcc(nn); self.right = Some(res.clone()); Some(res) } false => None, }, None => None, }; }
let mut nn = SkipNode::new(dt); nn.right = self.right.take(); let res = rcc(nn); self.right = Some(res.clone()); Some(res) } }
fn main() { let mut s = SkipNode::new(4); s.insert(4); s.insert(6); s.insert(77); s.insert(84); s.insert(23); s.insert(1); println!("{:?}", s); println!("Hello, world!"); }
|