]>
Commit | Line | Data |
---|---|---|
74b04a01 XL |
1 | use super::{SortedIndexMultiMap, SortedMap}; |
2 | ||
3 | #[test] | |
4 | fn test_sorted_index_multi_map() { | |
5 | let entries: Vec<_> = vec![(2, 0), (1, 0), (2, 1), (3, 0), (2, 2)]; | |
6 | let set: SortedIndexMultiMap<usize, _, _> = entries.iter().copied().collect(); | |
7 | ||
8 | // Insertion order is preserved. | |
9 | assert!(entries.iter().map(|(ref k, ref v)| (k, v)).eq(set.iter())); | |
10 | ||
11 | // Indexing | |
12 | for (i, expect) in entries.iter().enumerate() { | |
13 | assert_eq!(set[i], expect.1); | |
14 | } | |
15 | ||
16 | // `get_by_key` works. | |
136023e0 XL |
17 | assert_eq!(set.get_by_key(3).copied().collect::<Vec<_>>(), vec![0]); |
18 | assert!(set.get_by_key(4).next().is_none()); | |
74b04a01 XL |
19 | |
20 | // `get_by_key` returns items in insertion order. | |
136023e0 | 21 | let twos: Vec<_> = set.get_by_key_enumerated(2).collect(); |
74b04a01 XL |
22 | let idxs: Vec<usize> = twos.iter().map(|(i, _)| *i).collect(); |
23 | let values: Vec<usize> = twos.iter().map(|(_, &v)| v).collect(); | |
24 | ||
25 | assert_eq!(idxs, vec![0, 2, 4]); | |
26 | assert_eq!(values, vec![0, 1, 2]); | |
27 | } | |
dc9dc135 XL |
28 | |
29 | #[test] | |
30 | fn test_insert_and_iter() { | |
31 | let mut map = SortedMap::new(); | |
32 | let mut expected = Vec::new(); | |
33 | ||
dfeec247 | 34 | for x in 0..100 { |
dc9dc135 XL |
35 | assert_eq!(map.iter().cloned().collect::<Vec<_>>(), expected); |
36 | ||
37 | let x = 1000 - x * 2; | |
38 | map.insert(x, x); | |
39 | expected.insert(0, (x, x)); | |
40 | } | |
41 | } | |
42 | ||
43 | #[test] | |
44 | fn test_get_and_index() { | |
45 | let mut map = SortedMap::new(); | |
46 | let mut expected = Vec::new(); | |
47 | ||
dfeec247 | 48 | for x in 0..100 { |
dc9dc135 XL |
49 | let x = 1000 - x; |
50 | if x & 1 == 0 { | |
51 | map.insert(x, x); | |
52 | } | |
53 | expected.push(x); | |
54 | } | |
55 | ||
56 | for mut x in expected { | |
57 | if x & 1 == 0 { | |
58 | assert_eq!(map.get(&x), Some(&x)); | |
59 | assert_eq!(map.get_mut(&x), Some(&mut x)); | |
60 | assert_eq!(map[&x], x); | |
61 | assert_eq!(&mut map[&x], &mut x); | |
62 | } else { | |
63 | assert_eq!(map.get(&x), None); | |
64 | assert_eq!(map.get_mut(&x), None); | |
65 | } | |
66 | } | |
67 | } | |
68 | ||
69 | #[test] | |
70 | fn test_range() { | |
71 | let mut map = SortedMap::new(); | |
72 | map.insert(1, 1); | |
73 | map.insert(3, 3); | |
74 | map.insert(6, 6); | |
75 | map.insert(9, 9); | |
76 | ||
dfeec247 | 77 | let keys = |s: &[(_, _)]| s.into_iter().map(|e| e.0).collect::<Vec<u32>>(); |
dc9dc135 | 78 | |
dfeec247 XL |
79 | for start in 0..11 { |
80 | for end in 0..11 { | |
dc9dc135 | 81 | if end < start { |
dfeec247 | 82 | continue; |
dc9dc135 XL |
83 | } |
84 | ||
85 | let mut expected = vec![1, 3, 6, 9]; | |
86 | expected.retain(|&x| x >= start && x < end); | |
87 | ||
88 | assert_eq!(keys(map.range(start..end)), expected, "range = {}..{}", start, end); | |
89 | } | |
90 | } | |
91 | } | |
92 | ||
dc9dc135 XL |
93 | #[test] |
94 | fn test_offset_keys() { | |
95 | let mut map = SortedMap::new(); | |
96 | map.insert(1, 1); | |
97 | map.insert(3, 3); | |
98 | map.insert(6, 6); | |
99 | ||
100 | map.offset_keys(|k| *k += 1); | |
101 | ||
102 | let mut expected = SortedMap::new(); | |
103 | expected.insert(2, 1); | |
104 | expected.insert(4, 3); | |
105 | expected.insert(7, 6); | |
106 | ||
107 | assert_eq!(map, expected); | |
108 | } | |
109 | ||
110 | fn keys(s: SortedMap<u32, u32>) -> Vec<u32> { | |
111 | s.into_iter().map(|(k, _)| k).collect::<Vec<u32>>() | |
112 | } | |
113 | ||
114 | fn elements(s: SortedMap<u32, u32>) -> Vec<(u32, u32)> { | |
115 | s.into_iter().collect::<Vec<(u32, u32)>>() | |
116 | } | |
117 | ||
118 | #[test] | |
119 | fn test_remove_range() { | |
120 | let mut map = SortedMap::new(); | |
121 | map.insert(1, 1); | |
122 | map.insert(3, 3); | |
123 | map.insert(6, 6); | |
124 | map.insert(9, 9); | |
125 | ||
dfeec247 XL |
126 | for start in 0..11 { |
127 | for end in 0..11 { | |
dc9dc135 | 128 | if end < start { |
dfeec247 | 129 | continue; |
dc9dc135 XL |
130 | } |
131 | ||
132 | let mut expected = vec![1, 3, 6, 9]; | |
133 | expected.retain(|&x| x < start || x >= end); | |
134 | ||
135 | let mut map = map.clone(); | |
dfeec247 | 136 | map.remove_range(start..end); |
dc9dc135 XL |
137 | |
138 | assert_eq!(keys(map), expected, "range = {}..{}", start, end); | |
139 | } | |
140 | } | |
141 | } | |
142 | ||
143 | #[test] | |
144 | fn test_remove() { | |
145 | let mut map = SortedMap::new(); | |
146 | let mut expected = Vec::new(); | |
147 | ||
148 | for x in 0..10 { | |
149 | map.insert(x, x); | |
150 | expected.push((x, x)); | |
151 | } | |
152 | ||
dfeec247 | 153 | for x in 0..10 { |
dc9dc135 XL |
154 | let mut map = map.clone(); |
155 | let mut expected = expected.clone(); | |
156 | ||
157 | assert_eq!(map.remove(&x), Some(x)); | |
158 | expected.remove(x as usize); | |
159 | ||
160 | assert_eq!(map.iter().cloned().collect::<Vec<_>>(), expected); | |
161 | } | |
162 | } | |
163 | ||
164 | #[test] | |
165 | fn test_insert_presorted_non_overlapping() { | |
166 | let mut map = SortedMap::new(); | |
167 | map.insert(2, 0); | |
168 | map.insert(8, 0); | |
169 | ||
170 | map.insert_presorted(vec![(3, 0), (7, 0)]); | |
171 | ||
172 | let expected = vec![2, 3, 7, 8]; | |
173 | assert_eq!(keys(map), expected); | |
174 | } | |
175 | ||
176 | #[test] | |
177 | fn test_insert_presorted_first_elem_equal() { | |
178 | let mut map = SortedMap::new(); | |
179 | map.insert(2, 2); | |
180 | map.insert(8, 8); | |
181 | ||
182 | map.insert_presorted(vec![(2, 0), (7, 7)]); | |
183 | ||
184 | let expected = vec![(2, 0), (7, 7), (8, 8)]; | |
185 | assert_eq!(elements(map), expected); | |
186 | } | |
187 | ||
188 | #[test] | |
189 | fn test_insert_presorted_last_elem_equal() { | |
190 | let mut map = SortedMap::new(); | |
191 | map.insert(2, 2); | |
192 | map.insert(8, 8); | |
193 | ||
194 | map.insert_presorted(vec![(3, 3), (8, 0)]); | |
195 | ||
196 | let expected = vec![(2, 2), (3, 3), (8, 0)]; | |
197 | assert_eq!(elements(map), expected); | |
198 | } | |
199 | ||
200 | #[test] | |
201 | fn test_insert_presorted_shuffle() { | |
202 | let mut map = SortedMap::new(); | |
203 | map.insert(2, 2); | |
204 | map.insert(7, 7); | |
205 | ||
206 | map.insert_presorted(vec![(1, 1), (3, 3), (8, 8)]); | |
207 | ||
208 | let expected = vec![(1, 1), (2, 2), (3, 3), (7, 7), (8, 8)]; | |
209 | assert_eq!(elements(map), expected); | |
210 | } | |
211 | ||
212 | #[test] | |
213 | fn test_insert_presorted_at_end() { | |
214 | let mut map = SortedMap::new(); | |
215 | map.insert(1, 1); | |
216 | map.insert(2, 2); | |
217 | ||
218 | map.insert_presorted(vec![(3, 3), (8, 8)]); | |
219 | ||
220 | let expected = vec![(1, 1), (2, 2), (3, 3), (8, 8)]; | |
221 | assert_eq!(elements(map), expected); | |
222 | } |