SHARE
TWEET

Untitled

a guest Jul 17th, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. use std::cell::RefCell;
  2. use std::rc::Rc;
  3. use std::fmt;
  4.  
  5. type NodePtr<T> = Rc<RefCell<Node<T>>>;
  6.  
  7. #[derive(Clone)]
  8. enum Zipper<T> {
  9.     Clean,
  10.     Dirty(NodePtr<T>, Option<NodePtr<T>>),
  11. }
  12.  
  13. struct Node<T> {
  14.     value: T,
  15.     next: Option<NodePtr<T>>,
  16.     zipper: Zipper<T>,
  17. }
  18.  
  19. impl<T: Clone> Node<T> {
  20.     fn alloc(node: Node<T>) -> NodePtr<T> {
  21.         Rc::from(RefCell::from(node))
  22.     }
  23.  
  24.     fn create_lazy(x: &Option<NodePtr<T>>, y: Option<NodePtr<T>>) -> Option<NodePtr<T>> {
  25.         if let Some(x) = x {
  26.             let xb = x.borrow();
  27.             let y = y.expect("create_lazy: imbalance");
  28.  
  29.             Some(Node::alloc(Node {
  30.                 value: xb.value.clone(),
  31.                 next: xb.next.clone(),
  32.                 zipper: Zipper::Dirty(y, None),
  33.             }))
  34.         } else {
  35.             y
  36.         }
  37.     }
  38.  
  39.     fn rotate_zipper(x: &NodePtr<T>) {
  40.         let xb = x.borrow();
  41.         if let Zipper::Dirty(c, d) = xb.zipper.clone() {
  42.             let cb = c.borrow();
  43.  
  44.             let node_1 = Node {
  45.                 value: cb.value.clone(),
  46.                 next: d,
  47.                 zipper: Zipper::Clean,
  48.             };
  49.  
  50.             let node_1_ptr = Node::alloc(node_1);
  51.  
  52.             let new_next;
  53.  
  54.             let cb_next = cb.next.clone()
  55.                 .expect("rotate_zipper: imbalance");
  56.  
  57.             if let Some(next) = xb.next.clone() {
  58.                 let nextb = next.borrow();
  59.                 new_next = Node {
  60.                     value: nextb.value.clone(),
  61.                     next: nextb.next.clone(),
  62.                     zipper: Zipper::Dirty(cb_next, Some(node_1_ptr)),
  63.                 };
  64.             } else {
  65.                 new_next = Node {
  66.                     value: cb_next.borrow().value.clone(),
  67.                     next: Some(node_1_ptr),
  68.                     zipper: Zipper::Clean
  69.                 };
  70.             }
  71.  
  72.             let new_node = Node {
  73.                 value: xb.value.clone(),
  74.                 next: Some(Node::alloc(new_next)),
  75.                 zipper: Zipper::Clean,
  76.             };
  77.  
  78.             drop(xb);
  79.  
  80.             x.replace(new_node);
  81.         }
  82.     }
  83. }
  84.  
  85. #[derive(Clone)]
  86. struct Queue<T> {
  87.     front: Option<NodePtr<T>>,
  88.     back: Option<NodePtr<T>>,
  89.     jump: Option<NodePtr<T>>,
  90. }
  91.  
  92. impl<T: Clone> Queue<T> {
  93.     fn new() -> Queue<T> {
  94.         Queue {
  95.             front: None,
  96.             back: None,
  97.             jump: None,
  98.         }
  99.     }
  100.  
  101.     fn pop_front(self) -> Option<(Queue<T>, T)> {
  102.         let front = self.front?;
  103.         let res = front.borrow().value.clone();
  104.  
  105.         let res_queue;
  106.  
  107.         if let Some(jump) = self.jump {
  108.             Node::rotate_zipper(&jump);
  109.  
  110.             let jumpb = jump.borrow();
  111.  
  112.             let frontb = front.borrow();
  113.             res_queue = Queue {
  114.                 front: frontb.next.clone(),
  115.                 back: self.back,
  116.                 jump: jumpb.next.clone(),
  117.             }
  118.         } else {
  119.             let frontb = front.borrow();
  120.             let zipper = Node::create_lazy(&frontb.next, self.back);
  121.             res_queue = Queue {
  122.                 front: zipper.clone(),
  123.                 back: None,
  124.                 jump: zipper,
  125.             }
  126.         }
  127.  
  128.         Some((res_queue, res))
  129.     }
  130.  
  131.     fn push_back(self, v: T) -> Queue<T> {
  132.         let new_node = Node::alloc(Node {
  133.             value: v,
  134.             next: self.back.clone(),
  135.             zipper: Zipper::Clean,
  136.         });
  137.  
  138.         if let Some(jump) = self.jump {
  139.             Node::rotate_zipper(&jump);
  140.  
  141.             let jumpb = jump.borrow();
  142.  
  143.             Queue {
  144.                 front: self.front.clone(),
  145.                 back: Some(new_node),
  146.                 jump: jumpb.next.clone(),
  147.             }
  148.         } else {
  149.             let zipper = Node::create_lazy(&self.front, Some(new_node));
  150.  
  151.             Queue {
  152.                 front: zipper.clone(),
  153.                 back: None,
  154.                 jump: zipper,
  155.             }
  156.         }
  157.     }
  158. }
  159.  
  160. struct QueueIter<T> {
  161.     dat: Queue<T>
  162. }
  163.  
  164. impl<T: Clone> Iterator for QueueIter<T> {
  165.     type Item = T;
  166.  
  167.     fn next(&mut self) -> Option<T> {
  168.         let (next, res) = self.dat.clone().pop_front()?;
  169.         self.dat = next;
  170.         Some(res)
  171.     }
  172. }
  173.  
  174. impl<T: Clone> IntoIterator for Queue<T> {
  175.     type Item = T;
  176.     type IntoIter = QueueIter<T>;
  177.  
  178.     fn into_iter(self) -> QueueIter<T> {
  179.         QueueIter { dat: self }
  180.     }
  181. }
  182.  
  183. impl<T: fmt::Debug + Clone> fmt::Debug for Queue<T> {
  184.     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  185.         let vec: Vec<T> = self.clone().into_iter().collect();
  186.         write!(f, "Queue{:?}", vec)
  187.     }
  188. }
  189.  
  190. fn main() {
  191.     let a: Queue<u32> = Queue::new()
  192.         .push_back(3)
  193.         .push_back(4)
  194.         .push_back(5);
  195.  
  196.     println!("a = {:?}", a);
  197.  
  198.     println!("-----");
  199.  
  200.     // Cloning is fast -- only a few pointers copied
  201.     let (b, x) = a.clone()
  202.         .pop_front().unwrap();
  203.  
  204.  
  205.     println!("a = {:?} (unchanged)", a);
  206.     println!();
  207.     println!("b = {:?}", b);
  208.     println!("x = {:?}", x);
  209.  
  210.     println!("-----");
  211.  
  212.     let c = b.clone().push_back(7);
  213.     let d = b.clone().push_back(8);
  214.     let e = a.clone().push_back(9);
  215.  
  216.     println!("a = {:?} (unchanged)", a);
  217.     println!("b = {:?} (unchanged)", b);
  218.     println!();
  219.     println!("c = {:?}", c);
  220.     println!("d = {:?}", d);
  221.     println!("e = {:?}", e);
  222. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top