1mod node;
2mod set;
3mod tree;
4
5pub use self::set::SplaySet;
6pub use self::tree::SplayTree;
7
8#[cfg(test)]
9mod test {
10
11 use rand::random;
12
13 use super::*;
14 use std::cmp::Ordering;
15 use std::i32;
16
17 fn int_comparator(a: &i32, b: &i32) -> Ordering {
18 a.cmp(b)
19 }
20
21 #[test]
22 fn insert_simple() {
23 let mut t = SplayTree::new(int_comparator);
24 assert_eq!(t.insert(1, 2), None);
25 assert_eq!(t.insert(1, 3), Some(2));
26 assert_eq!(t.insert(2, 3), None);
27
28 assert_eq!(t.len(), 2);
29 assert_eq!(t.min(), Some(&1));
30 assert_eq!(t.max(), Some(&2));
31
32 assert_eq!(int_comparator(&1, &2), Ordering::Less);
33
34 assert_eq!(t.next(&1), Some((&2, &3)));
35 assert_eq!(t.next(&2), None);
36
37 assert_eq!(t.prev(&2), Some((&1, &3)));
38 assert_eq!(t.prev(&1), None);
39 assert_eq!(t.prev(&100), Some((&2, &3)));
40 }
41
42 #[test]
43 fn remove_simple() {
44 let mut t = SplayTree::new(int_comparator);
45 assert_eq!(t.insert(1, 2), None);
46 assert_eq!(t.insert(2, 3), None);
47 assert_eq!(t.insert(3, 4), None);
48 assert_eq!(t.insert(0, 5), None);
49 assert_eq!(t.remove(&1), Some(2));
50
51 assert_eq!(t.len(), 3);
52 assert_eq!(t.min(), Some(&0));
53 assert_eq!(t.max(), Some(&3));
54
55 assert_eq!(t.next(&0), Some((&2, &3)));
56 assert_eq!(t.next(&1), Some((&2, &3)));
57 assert_eq!(t.next(&2), Some((&3, &4)));
58 assert_eq!(t.next(&3), None);
59
60 assert_eq!(t.prev(&2), Some((&0, &5)));
61 assert_eq!(t.prev(&0), None);
62 assert_eq!(t.prev(&100), Some((&3, &4)));
63 }
64
65 #[test]
66 fn pop_simple() {
67 let mut t = SplayTree::new(int_comparator);
68 assert_eq!(t.insert(1, 2), None);
69 assert_eq!(t.insert(2, 3), None);
70 assert_eq!(t.insert(3, 4), None);
71 assert_eq!(t.insert(0, 5), None);
72
73 assert_eq!(t.min(), Some(&0));
74 assert_eq!(t.max(), Some(&3));
75
76 assert_eq!(t.prev(&0), None);
77 assert_eq!(t.prev(&1), Some((&0, &5)));
78 assert_eq!(t.next(&0), Some((&1, &2)));
79 assert_eq!(t.next(&1), Some((&2, &3)));
80 assert_eq!(t.next(&2), Some((&3, &4)));
81 assert_eq!(t.next(&3), None);
82
83 assert_eq!(t.remove(&1), Some(2));
84 assert_eq!(t.remove(&1), None);
85 assert_eq!(t.remove(&0), Some(5));
86
87 assert_eq!(t.min(), Some(&2));
88 assert_eq!(t.max(), Some(&3));
89 }
90
91 #[test]
92 fn test_len() {
93 let mut m = SplayTree::new(int_comparator);
94 assert_eq!(m.insert(3, 6), None);
95 assert_eq!(m.len(), 1);
96 assert_eq!(m.insert(0, 0), None);
97 assert_eq!(m.len(), 2);
98 assert_eq!(m.insert(4, 8), None);
99 assert_eq!(m.len(), 3);
100 assert_eq!(m.remove(&3), Some(6));
101 assert_eq!(m.len(), 2);
102 assert_eq!(m.remove(&5), None);
103 assert_eq!(m.len(), 2);
104 assert_eq!(m.insert(2, 4), None);
105 assert_eq!(m.len(), 3);
106 assert_eq!(m.insert(1, 2), None);
107 assert_eq!(m.len(), 4);
108 }
109
110 #[test]
111 fn test_clear() {
112 let mut m = SplayTree::new(int_comparator);
113 m.clear();
114 assert_eq!(m.insert(5, 11), None);
115 assert_eq!(m.insert(12, -3), None);
116 assert_eq!(m.insert(19, 2), None);
117 m.clear();
118 assert_eq!(m.get(&5), None);
119 assert_eq!(m.get(&12), None);
120 assert_eq!(m.get(&19), None);
121 assert!(m.is_empty());
122 }
123
124 #[test]
125 fn insert_replace() {
126 let mut m = SplayTree::new(int_comparator);
127 assert_eq!(m.insert(5, 2), None);
128 assert_eq!(m.insert(2, 9), None);
129 assert_eq!(m.insert(2, 11), Some(9));
130 assert_eq!(m[&2], 11);
131 }
132
133 #[test]
134 fn find_empty() {
135 let m = SplayTree::<i32, i32, _>::new(int_comparator);
136 assert_eq!(m.get(&5), None);
137 }
138
139 #[test]
140 fn find_not_found() {
141 let mut m = SplayTree::new(int_comparator);
142 assert_eq!(m.insert(1, 2), None);
143 assert_eq!(m.insert(5, 3), None);
144 assert_eq!(m.insert(9, 3), None);
145 assert_eq!(m.get(&2), None);
146 }
147
148 #[test]
149 fn get_works() {
150 let mut m = SplayTree::new(int_comparator);
151 m.insert(1, 1);
152 assert_eq!(m[&1], 1);
153 }
154
155 #[test]
156 fn into_iter() {
157 let mut m = SplayTree::new(int_comparator);
158 m.insert(1, 1);
159 m.insert(2, 1);
160 m.insert(0, 1);
161 let mut cur = 0;
162 for (k, v) in m {
163 assert_eq!(k, cur);
164 assert_eq!(v, 1);
165 cur += 1;
166 }
167 }
168
169 #[test]
170 fn into_iter_backwards() {
171 let mut m = SplayTree::new(int_comparator);
172 m.insert(1, 1);
173 m.insert(2, 1);
174 m.insert(0, 1);
175 let mut cur = 2;
176 for (k, v) in m.into_iter().rev() {
177 assert_eq!(k, cur);
178 assert_eq!(v, 1);
179 cur -= 1;
180 }
181 }
182
183 #[test]
184 fn large() {
185 let mut m = SplayTree::new(int_comparator);
186 let mut v = Vec::new();
187 let mut min = i32::MAX;
188 let mut max = i32::MIN;
189
190 for _ in 0..400 {
191 let i: i32 = random();
192 m.insert(i, i);
193 v.push(i);
194 min = i32::min(min, i);
195 max = i32::max(max, i);
196 }
197
198 for i in v.iter() {
199 assert!(m.contains(i));
200 assert_eq!(&m[i], i);
201 match m.next(i) {
202 Some((next, _)) => {
203 assert!(*next > *i);
204 assert_eq!(m.prev(&next), Some((i, i)));
205 }
206 None => assert_eq!(*i, max),
207 }
208 match m.prev(i) {
209 Some((prev, _)) => {
210 assert!(*prev < *i);
211 assert_eq!(m.next(&prev), Some((i, i)));
212 }
213 None => assert_eq!(*i, min),
214 }
215 }
216 assert_eq!(m.min(), Some(&min));
217 assert_eq!(m.max(), Some(&max));
218 }
219}