fork download
copy 
  1. use std::rc::Rc;
  2. use std::cell::RefCell;
  3. type Handle<T> = Option<Rc<RefCell<Node<T>>>>;
  4. type HandleItem<T> = Rc<RefCell<Node<T>>>;
  5. #[derive(PartialEq)]
  6. struct Node<T> {
  7.     value: T,
  8.     prev: Handle<T>,
  9.     next: Handle<T>,
  10. }
  11. impl<T> Node<T> {
  12.     fn new(value: T) -> Node<T> {
  13.         Node {value: value, prev: None, next: None}
  14.     }
  15. }
  16. trait HandleOperation<T> {
  17.     fn new(value: T) -> Handle<T>;
  18.     fn prev(&self) -> Handle<T>;
  19.     fn next(&self) -> Handle<T>;
  20.     fn set_value(&self, value: T);
  21.     fn set_prev(&self, h: Handle<T>);
  22.     fn set_next(&self, h: Handle<T>);
  23.     fn push_prev(&self, h: Handle<T>);
  24.     fn push_next(&self, h: Handle<T>);
  25.     fn pop(&self) -> Handle<T>;
  26.     fn pop_prev(&self) -> Handle<T>;
  27.     fn pop_next(&self) -> Handle<T>;
  28.     fn ptr_eq(this: &Self, other: &Self) -> bool;
  29.     fn iter_prev(&self) -> HandleIterPrev<T>;
  30.     fn iter_next(&self) -> HandleIterNext<T>;
  31. }
  32. impl<T> HandleOperation<T> for Handle<T> {
  33.     fn new(value: T) -> Handle<T> {
  34.         Some(Rc::new(RefCell::new(Node::new(value))))
  35.     }
  36.     fn prev(&self) -> Handle<T> {
  37.         if let Some(rc) = self.as_ref() {rc.borrow().prev.clone()} else {None}
  38.     }
  39.     fn next(&self) -> Handle<T> {
  40.         if let Some(rc) = self.as_ref() {rc.borrow().next.clone()} else {None}
  41.     }
  42.     fn set_value(&self, value: T) {
  43.         if let Some(rc) = self.as_ref() {rc.borrow_mut().value = value;}
  44.     }
  45.     fn set_prev(&self, h: Handle<T>) {
  46.         if let Some(rc) = self.as_ref() {rc.borrow_mut().prev = h;}
  47.     }
  48.     fn set_next(&self, h: Handle<T>) {
  49.         if let Some(rc) = self.as_ref() {rc.borrow_mut().next = h;}
  50.     }
  51.     fn push_prev(&self, h: Handle<T>) {
  52.         if self.is_none() {return;}
  53.         self.prev().set_next(h.clone());
  54.         h.set_prev(self.prev());
  55.         h.set_next(self.clone());
  56.         self.set_prev(h);
  57.     }
  58.     fn push_next(&self, h: Handle<T>) {
  59.         if self.is_none() {return;}
  60.         self.next().set_prev(h.clone());
  61.         h.set_next(self.next());
  62.         h.set_prev(self.clone());
  63.         self.set_next(h);
  64.     }
  65.     fn pop(&self) -> Handle<T> {
  66.         if self.is_none() {return None;}
  67.         self.prev().set_next(self.next());
  68.         self.next().set_prev(self.prev());
  69.         self.set_prev(None);
  70.         self.set_next(None);
  71.         self.clone()
  72.     }
  73.     fn pop_prev(&self) -> Handle<T> {
  74.         if self.is_some() {self.prev().pop()} else {None}
  75.     }
  76.     fn pop_next(&self) -> Handle<T> {
  77.         if self.is_some() {self.next().pop()} else {None}
  78.     }
  79.     fn ptr_eq(this: &Self, other: &Self) -> bool {
  80.         match (this.as_ref(), other.as_ref()) {
  81.             (Some(ref a), Some(ref b)) => &***a as *const RefCell<_> == &***b as *const RefCell<_>,
  82.             (None, None) => true,
  83.             _ => false,
  84.         }
  85.     }
  86.     fn iter_prev(&self) -> HandleIterPrev<T> {HandleIterPrev {current: self.clone()}}
  87.     fn iter_next(&self) -> HandleIterNext<T> {HandleIterNext {current: self.clone()}}
  88. }
  89. struct HandleIterNext<T> {current: Handle<T>}
  90. impl<T> Iterator for HandleIterNext<T> {
  91.     type Item = HandleItem<T>;
  92.     fn next(&mut self) -> Option<Self::Item> {
  93.         let current = self.current.clone();
  94.         self.current = self.current.next();
  95.         current
  96.     }
  97. }
  98. struct HandleIterPrev<T> {current: Handle<T>}
  99. impl<T> Iterator for HandleIterPrev<T> {
  100.     type Item = HandleItem<T>;
  101.     fn next(&mut self) -> Option<Self::Item> {
  102.         let current = self.current.clone();
  103.         self.current = self.current.prev();
  104.         current
  105.     }
  106. }
  107. use std::fmt;
  108. impl<T: fmt::Debug> fmt::Debug for Node<T> {
  109.     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  110.         //write!(f, "Node {{ value: {:?}}}", self.value)
  111.         write!(f, "{:?}", self.value)
  112.     }
  113. }
  114. struct LinkedList<T> {
  115.     front: Handle<T>,
  116.     back: Handle<T>,
  117. }
  118. impl<T> LinkedList<T> {
  119.     fn new() -> LinkedList<T> {LinkedList {front: None, back: None}}
  120.     fn push_front(&mut self, value: T) -> Handle<T> {
  121.         let h = Handle::new(value);
  122.         h.push_next(self.front.clone());
  123.         self.front = h.clone();
  124.         if self.back.is_none() {self.back = h.clone()}
  125.         h
  126.     }
  127.     fn push_back(&mut self, value: T) -> Handle<T> {
  128.         let h = Handle::new(value);
  129.         h.push_prev(self.back.clone());
  130.         self.back = h.clone();
  131.         if self.front.is_none() {self.front = h.clone()}
  132.         h
  133.     }
  134.     fn pop_front(&mut self) -> Handle<T> {
  135.         let next = self.front.next();
  136.         let popped = self.front.pop();
  137.         self.front = next;
  138.         if Handle::ptr_eq(&popped, &self.back) {self.back = None;}
  139.         popped
  140.     }
  141.     fn pop_back(&mut self) -> Handle<T> {
  142.         let prev = self.back.prev();
  143.         let popped = self.back.pop();
  144.         self.back = prev;
  145.         if Handle::ptr_eq(&popped, &self.front) {self.front = None;}
  146.         popped
  147.     }
  148.     fn clear(&mut self) {
  149.         while self.front.is_some() {self.pop_front();}
  150.     }
  151.     fn iter_prev(&self) -> HandleIterPrev<T> {self.back.iter_prev()}
  152.     fn iter_next(&self) -> HandleIterNext<T> {self.front.iter_next()}
  153. }
  154. impl<T: fmt::Debug> fmt::Debug for LinkedList<T> {
  155.     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  156.         write!(f, "{:?}", self.iter_next().map(|rc| Some(rc)).collect::<Vec<_>>())
  157.     }
  158. }
  159. fn main() {
  160.     let mut ll = LinkedList::new();
  161.     let mut v: Vec<Handle<i32>> = Vec::new();
  162.     v.push(ll.push_back(10));
  163.     v.push(ll.push_back(20));
  164.     println!("{:?}\n{:?}\n", ll, v);
  165.     let h = Handle::new(11);
  166.     v[1].push_prev(h.clone()); // O(1)での挿入
  167.     v.insert(1, h); // O(不明？)でのアクセス用配列のケア
  168.     println!("{:?}\n{:?}\n", ll, v);
  169.     v[1].set_value(12); // O(1)での値更新
  170.     println!("{:?}\n{:?}\n", ll, v);
  171.     if let Some(rc) = v[1].as_ref() {rc.borrow_mut().value = 13;} // O(1)でのborrow_mut()
  172.     println!("{:?}\n{:?}\n", ll, v);
  173.     if let Some(rc) = v[1].as_ref() {println!("rc.borrow().value: {}", rc.borrow().value);} // O(1)でのborrow()
  174.     let popped = v[1].pop(); // O(1)での取り外し
  175.     v.remove(1); // O(不明？)でのアクセス用配列のケア
  176.     println!("popped: {:?}", popped);
  177.     println!("{:?}\n{:?}\n", ll, v);
  178.     ll.clear(); // 循環参照をケアしてないのでとりあえずこうやって対処
  179. }
  180.  
Success #stdin #stdout 0s 5520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[Some(RefCell { value: 10 }), Some(RefCell { value: 20 })]
[Some(RefCell { value: 10 }), Some(RefCell { value: 20 })]

[Some(RefCell { value: 10 }), Some(RefCell { value: 11 }), Some(RefCell { value: 20 })]
[Some(RefCell { value: 10 }), Some(RefCell { value: 11 }), Some(RefCell { value: 20 })]

[Some(RefCell { value: 10 }), Some(RefCell { value: 12 }), Some(RefCell { value: 20 })]
[Some(RefCell { value: 10 }), Some(RefCell { value: 12 }), Some(RefCell { value: 20 })]

[Some(RefCell { value: 10 }), Some(RefCell { value: 13 }), Some(RefCell { value: 20 })]
[Some(RefCell { value: 10 }), Some(RefCell { value: 13 }), Some(RefCell { value: 20 })]

rc.borrow().value: 13
popped: Some(RefCell { value: 13 })
[Some(RefCell { value: 10 }), Some(RefCell { value: 20 })]
[Some(RefCell { value: 10 }), Some(RefCell { value: 20 })]
https://ideone.com/IY3aFj
language:
Rust (rust 1.56)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!