180627dcb6df7102484b2e79289937122a026f32
[rust-101.git] / solutions / src / list.rs
1
2 use std::ptr;
3 use std::mem;
4 use std::marker::PhantomData;
5
6 fn box_into_raw<T>(b: Box<T>) -> *mut T {
7     unsafe { mem::transmute(b) }
8 }
9 unsafe fn raw_into_box<T>(r: *mut T) -> Box<T> {
10     mem::transmute(r)
11 }
12
13 struct Node<T> {
14     data: T,
15     next: NodePtr<T>,
16     prev: NodePtr<T>,
17 }
18 type NodePtr<T> = *mut Node<T>;
19
20 pub struct LinkedList<T> {
21     first: NodePtr<T>,
22     last:  NodePtr<T>,
23     _marker: PhantomData<T>,
24 }
25
26 impl<T> LinkedList<T> {
27     pub fn new() -> Self {
28         LinkedList { first: ptr::null_mut(), last: ptr::null_mut(), _marker: PhantomData }
29     }
30
31     pub fn push_back(&mut self, t: T) {
32         // Create the new node.
33         let new = Box::new( Node { data: t, next: ptr::null_mut(), prev: self.last } );
34         let new = box_into_raw(new);
35         // Update other points to this node.
36         if self.last.is_null() {
37             debug_assert!(self.first.is_null());
38             self.first = new;
39         } else {
40             debug_assert!(!self.first.is_null());
41             unsafe { (*self.last).next  = new; }
42         }
43         // Make this the last node.
44         self.last = new;
45     }
46
47     pub fn pop_back(&mut self) -> Option<T> {
48         if self.last.is_null() {
49             None
50         } else {
51             let last = self.last;
52             let new_last = unsafe { (*self.last).prev };
53             self.last = new_last;
54             if new_last.is_null() {
55                 // The list is now empty.
56                 self.first = new_last;
57             }
58             let last = unsafe { raw_into_box(last) } ;
59             Some(last.data)
60         }
61     }
62
63     pub fn push_front(&mut self, t: T) {
64         // Create the new node.
65         let new = Box::new( Node { data: t, next: self.first, prev: ptr::null_mut() } );
66         let new = box_into_raw(new);
67         // Update other points to this node.
68         if self.first.is_null() {
69             debug_assert!(self.last.is_null());
70             self.last = new;
71         }
72         else {
73             debug_assert!(!self.last.is_null());
74             unsafe { (*self.first).prev = new; }
75         }
76         // Make this the first node.
77         self.first = new;
78     }
79
80     pub fn pop_front(&mut self) -> Option<T> {
81         if self.first.is_null() {
82             None
83         } else {
84             let first = self.first;
85             let new_first = unsafe { (*self.first).next };
86             self.first = new_first;
87             if new_first.is_null() {
88                 // The list is now empty.
89                 self.last = new_first;
90             }
91             let first = unsafe { raw_into_box(first) } ;
92             Some(first.data)
93         }
94     }
95
96     pub fn for_each<F: FnMut(&mut T)>(&mut self, mut f: F) {
97         let mut cur_ptr = self.first;
98         while !cur_ptr.is_null() {
99             // Iterate over every node, and call `f`.
100             f(unsafe{ &mut (*cur_ptr).data });
101             cur_ptr = unsafe{ (*cur_ptr).next };
102         }
103     }
104
105     pub fn iter_mut(&self) -> IterMut<T> {
106         IterMut { next: self.first, _marker: PhantomData  }
107     }
108 }
109
110 pub struct IterMut<'a, T> where T: 'a {
111     next: NodePtr<T>,
112     _marker: PhantomData<&'a T>,
113 }
114
115 impl<'a, T> Iterator for IterMut<'a, T> {
116     type Item = &'a mut T;
117
118     fn next(&mut self) -> Option<Self::Item> {
119         if self.next.is_null() {
120            None
121         } else {
122             let ret = unsafe{ &mut (*self.next).data };
123             self.next = unsafe { (*self.next).next };
124             Some(ret)
125         }
126     }
127 }
128
129 impl<T> Drop for LinkedList<T> {
130     fn drop(&mut self) {
131         let mut cur_ptr = self.first;
132         while !cur_ptr.is_null() {
133             let cur = unsafe { raw_into_box(cur_ptr) };
134             cur_ptr = cur.next;
135             drop(cur);
136         }
137     }
138 }
139
140 #[cfg(test)]
141 mod tests {
142     use std::rc::Rc;
143     use std::cell::Cell;
144     use super::LinkedList;
145
146     #[test]
147     fn test_pop_back() {
148         let mut l: LinkedList<i32> = LinkedList::new();
149         for i in 0..3 {
150             l.push_front(-i);
151             l.push_back(i);
152         }
153
154         assert_eq!(l.pop_back(), Some(2));
155         assert_eq!(l.pop_back(), Some(1));
156         assert_eq!(l.pop_back(), Some(0));
157         assert_eq!(l.pop_back(), Some(-0));
158         assert_eq!(l.pop_back(), Some(-1));
159         assert_eq!(l.pop_back(), Some(-2));
160         assert_eq!(l.pop_back(), None);
161         assert_eq!(l.pop_back(), None);
162     }
163
164     #[test]
165     fn test_pop_front() {
166         let mut l: LinkedList<i32> = LinkedList::new();
167         for i in 0..3 {
168             l.push_front(-i);
169             l.push_back(i);
170         }
171
172         assert_eq!(l.pop_front(), Some(-2));
173         assert_eq!(l.pop_front(), Some(-1));
174         assert_eq!(l.pop_front(), Some(-0));
175         assert_eq!(l.pop_front(), Some(0));
176         assert_eq!(l.pop_front(), Some(1));
177         assert_eq!(l.pop_front(), Some(2));
178         assert_eq!(l.pop_front(), None);
179         assert_eq!(l.pop_front(), None);
180     }
181
182     #[derive(Clone)]
183     struct DropChecker {
184         count: Rc<Cell<usize>>,
185     }
186     impl Drop for DropChecker {
187         fn drop(&mut self) {
188             self.count.set(self.count.get() + 1);
189         }
190     }
191
192     #[test]
193     fn test_drop() {
194         let count = DropChecker { count: Rc::new(Cell::new(0)) };
195         {
196             let mut l = LinkedList::new();
197             for _ in 0..10 {
198                 l.push_back(count.clone());
199                 l.push_front(count.clone());
200             }
201         }
202         assert_eq!(count.count.get(), 20);
203     }
204 }