fork download 
  1. /*
  2. ・注意：双方向リストだけど循環参照は未解決のまま
  3. ・注意：要素への参照を使っての操作はリスト側には未反映
  4. 　（front, backを正しく再設定し直したりはしないということ）
  5. 　（両端の要素の外側に追加したときとかおかしくなるはず）
  6. ・手元の1.8.0で主に動作チェック
  7. ・基本的によく分かってないので妙な箇所があるはず
  8. ・イテレータを提供したかったがよく分からなかったので諦めた
  9. ・fmt::Debug for LinkedList<T>は本来はもっとスッキリ書けるはず
  10. ・push_prev(&self, h)などが何も返さないのは、selfを返すかhを返すか
  11. 　どっちを返すのが自然なのかという判断に迷って決め切れなかったため
  12. */
  13. use std::rc::Rc;
  14. use std::cell::RefCell;
  15. type Handle<T> = Option<Rc<RefCell<Node<T>>>>;
  16. #[derive(PartialEq)]
  17. struct Node<T> {
  18.     value: T,
  19.     prev: Handle<T>,
  20.     next: Handle<T>,
  21. }
  22. impl<T> Node<T> {
  23.     fn new(value: T) -> Node<T> {
  24.         Node {value: value, prev: None, next: None}
  25.     }
  26. }
  27. trait HandleOperation<T> {
  28.     fn new(value: T) -> Handle<T>;
  29.     fn prev(&self) -> Handle<T>;
  30.     fn next(&self) -> Handle<T>;
  31.     fn set_value(&self, value: T);
  32.     fn set_prev(&self, h: Handle<T>);
  33.     fn set_next(&self, h: Handle<T>);
  34.     fn push_prev(&self, h: Handle<T>);
  35.     fn push_next(&self, h: Handle<T>);
  36.     fn pop(&self) -> Handle<T>;
  37.     fn pop_prev(&self) -> Handle<T>;
  38.     fn pop_next(&self) -> Handle<T>;
  39.     fn ptr_eq(this: &Self, other: &Self) -> bool;
  40. }
  41. impl<T> HandleOperation<T> for Handle<T> {
  42.     fn new(value: T) -> Handle<T> {
  43.         Some(Rc::new(RefCell::new(Node::new(value))))
  44.     }
  45.     fn prev(&self) -> Handle<T> {
  46.         if let Some(rc) = self.as_ref() {rc.borrow().prev.clone()} else {None}
  47.     }
  48.     fn next(&self) -> Handle<T> {
  49.         if let Some(rc) = self.as_ref() {rc.borrow().next.clone()} else {None}
  50.     }
  51.     fn set_value(&self, value: T) {
  52.         if let Some(rc) = self.as_ref() {rc.borrow_mut().value = value;}
  53.     }
  54.     fn set_prev(&self, h: Handle<T>) {
  55.         if let Some(rc) = self.as_ref() {rc.borrow_mut().prev = h;}
  56.     }
  57.     fn set_next(&self, h: Handle<T>) {
  58.         if let Some(rc) = self.as_ref() {rc.borrow_mut().next = h;}
  59.     }
  60.     fn push_prev(&self, h: Handle<T>) {
  61.         if self.is_none() {return;}
  62.         self.prev().set_next(h.clone());
  63.         h.set_prev(self.prev());
  64.         h.set_next(self.clone());
  65.         self.set_prev(h);
  66.     }
  67.     fn push_next(&self, h: Handle<T>) {
  68.         if self.is_none() {return;}
  69.         self.next().set_prev(h.clone());
  70.         h.set_next(self.next());
  71.         h.set_prev(self.clone());
  72.         self.set_next(h);
  73.     }
  74.     fn pop(&self) -> Handle<T> {
  75.         if self.is_none() {return None;}
  76.         self.prev().set_next(self.next());
  77.         self.next().set_prev(self.prev());
  78.         self.set_prev(None);
  79.         self.set_next(None);
  80.         self.clone()
  81.     }
  82.     fn pop_prev(&self) -> Handle<T> {
  83.         if self.is_some() {self.prev().pop()} else {None}
  84.     }
  85.     fn pop_next(&self) -> Handle<T> {
  86.         if self.is_some() {self.next().pop()} else {None}
  87.     }
  88.     fn ptr_eq(this: &Self, other: &Self) -> bool {
  89.         match (this.as_ref(), other.as_ref()) {
  90.             (Some(ref a), Some(ref b)) => &***a as *const RefCell<_> == &***b as *const RefCell<_>,
  91.             (None, None) => true,
  92.             _ => false,
  93.         }
  94.     }
  95. }
  96. use std::fmt;
  97. impl<T: fmt::Debug> fmt::Debug for Node<T> {
  98.     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  99.         //write!(f, "Node {{ value: {:?}}}", self.value)
  100.         write!(f, "{:?}", self.value)
  101.     }
  102. }
  103. struct LinkedList<T> {
  104.     front: Handle<T>,
  105.     back: Handle<T>,
  106. }
  107. impl<T> LinkedList<T> {
  108.     fn new() -> LinkedList<T> {LinkedList {front: None, back: None}}
  109.     fn push_front(&mut self, value: T) -> Handle<T> {
  110.         let h = Handle::new(value);
  111.         h.push_next(self.front.clone());
  112.         self.front = h.clone();
  113.         if self.back.is_none() {self.back = h.clone()}
  114.         h
  115.     }
  116.     fn push_back(&mut self, value: T) -> Handle<T> {
  117.         let h = Handle::new(value);
  118.         h.push_prev(self.back.clone());
  119.         self.back = h.clone();
  120.         if self.front.is_none() {self.front = h.clone()}
  121.         h
  122.     }
  123.     fn pop_front(&mut self) -> Handle<T> {
  124.         let next = self.front.next();
  125.         let popped = self.front.pop();
  126.         self.front = next;
  127.         if Handle::ptr_eq(&popped, &self.back) {self.back = None;}
  128.         popped
  129.     }
  130.     fn pop_back(&mut self) -> Handle<T> {
  131.         let prev = self.back.prev();
  132.         let popped = self.back.pop();
  133.         self.back = prev;
  134.         if Handle::ptr_eq(&popped, &self.front) {self.front = None;}
  135.         popped
  136.     }
  137.     fn clear(&mut self) {
  138.         while self.front.is_some() {self.pop_front();}
  139.     }
  140. }
  141. impl<T: fmt::Debug> fmt::Debug for LinkedList<T> {
  142.     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  143.         let mut p = self.front.clone();
  144.         let mut v = Vec::new();
  145.         while p.is_some() {
  146.             v.push(p.clone());
  147.             p = p.next();
  148.         }
  149.         write!(f, "{:?}", v)
  150.     }
  151. }
  152. fn main() {
  153.     let mut ll = LinkedList::new();
  154.     let mut v: Vec<Handle<i32>> = Vec::new();
  155.     v.push(ll.push_back(10));
  156.     v.push(ll.push_back(20));
  157.     println!("{:?}\n{:?}\n", ll, v);
  158.     let h = Handle::new(11);
  159.     v[1].push_prev(h.clone()); // O(1)での挿入
  160.     v.insert(1, h); // O(不明？)でのアクセス用配列のケア
  161.     println!("{:?}\n{:?}\n", ll, v);
  162.     v[1].set_value(12); // O(1)での値更新
  163.     println!("{:?}\n{:?}\n", ll, v);
  164.     if let Some(rc) = v[1].as_ref() {rc.borrow_mut().value = 13;} // O(1)でのborrow_mut()
  165.     println!("{:?}\n{:?}\n", ll, v);
  166.     if let Some(rc) = v[1].as_ref() {println!("borrow().value: {}", rc.borrow().value);} // O(1)でのborrow()
  167.     let popped = v[1].pop(); // O(1)での取り外し
  168.     v.remove(1); // O(不明？)でのアクセス用配列のケア
  169.     println!("popped: {:?}", popped);
  170.     println!("{:?}\n{:?}\n", ll, v);
  171.     ll.clear(); // 循環参照をケアしてないのでとりあえずこうやって対処
  172. }
  173.  
Success #stdin #stdout 0.01s 5464KB
comments (?)
stdin 
Standard input is empty
stdout 
[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 })]

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/bd0cFx
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!