]>
Commit | Line | Data |
---|---|---|
fe692bf9 FG |
1 | use super::*; |
2 | use std::string::String; | |
3 | ||
4 | #[test] | |
5 | fn it_works() { | |
6 | let mut map = IndexMap::new(); | |
7 | assert_eq!(map.is_empty(), true); | |
8 | map.insert(1, ()); | |
9 | map.insert(1, ()); | |
10 | assert_eq!(map.len(), 1); | |
11 | assert!(map.get(&1).is_some()); | |
12 | assert_eq!(map.is_empty(), false); | |
13 | } | |
14 | ||
15 | #[test] | |
16 | fn new() { | |
17 | let map = IndexMap::<String, String>::new(); | |
18 | println!("{:?}", map); | |
19 | assert_eq!(map.capacity(), 0); | |
20 | assert_eq!(map.len(), 0); | |
21 | assert_eq!(map.is_empty(), true); | |
22 | } | |
23 | ||
24 | #[test] | |
25 | fn insert() { | |
26 | let insert = [0, 4, 2, 12, 8, 7, 11, 5]; | |
27 | let not_present = [1, 3, 6, 9, 10]; | |
28 | let mut map = IndexMap::with_capacity(insert.len()); | |
29 | ||
30 | for (i, &elt) in insert.iter().enumerate() { | |
31 | assert_eq!(map.len(), i); | |
32 | map.insert(elt, elt); | |
33 | assert_eq!(map.len(), i + 1); | |
34 | assert_eq!(map.get(&elt), Some(&elt)); | |
35 | assert_eq!(map[&elt], elt); | |
36 | } | |
37 | println!("{:?}", map); | |
38 | ||
39 | for &elt in ¬_present { | |
40 | assert!(map.get(&elt).is_none()); | |
41 | } | |
42 | } | |
43 | ||
44 | #[test] | |
45 | fn insert_full() { | |
46 | let insert = vec![9, 2, 7, 1, 4, 6, 13]; | |
47 | let present = vec![1, 6, 2]; | |
48 | let mut map = IndexMap::with_capacity(insert.len()); | |
49 | ||
50 | for (i, &elt) in insert.iter().enumerate() { | |
51 | assert_eq!(map.len(), i); | |
52 | let (index, existing) = map.insert_full(elt, elt); | |
53 | assert_eq!(existing, None); | |
54 | assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); | |
55 | assert_eq!(map.len(), i + 1); | |
56 | } | |
57 | ||
58 | let len = map.len(); | |
59 | for &elt in &present { | |
60 | let (index, existing) = map.insert_full(elt, elt); | |
61 | assert_eq!(existing, Some(elt)); | |
62 | assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); | |
63 | assert_eq!(map.len(), len); | |
64 | } | |
65 | } | |
66 | ||
67 | #[test] | |
68 | fn insert_2() { | |
69 | let mut map = IndexMap::with_capacity(16); | |
70 | ||
71 | let mut keys = vec![]; | |
72 | keys.extend(0..16); | |
73 | keys.extend(if cfg!(miri) { 32..64 } else { 128..267 }); | |
74 | ||
75 | for &i in &keys { | |
76 | let old_map = map.clone(); | |
77 | map.insert(i, ()); | |
78 | for key in old_map.keys() { | |
79 | if map.get(key).is_none() { | |
80 | println!("old_map: {:?}", old_map); | |
81 | println!("map: {:?}", map); | |
82 | panic!("did not find {} in map", key); | |
83 | } | |
84 | } | |
85 | } | |
86 | ||
87 | for &i in &keys { | |
88 | assert!(map.get(&i).is_some(), "did not find {}", i); | |
89 | } | |
90 | } | |
91 | ||
92 | #[test] | |
93 | fn insert_order() { | |
94 | let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; | |
95 | let mut map = IndexMap::new(); | |
96 | ||
97 | for &elt in &insert { | |
98 | map.insert(elt, ()); | |
99 | } | |
100 | ||
101 | assert_eq!(map.keys().count(), map.len()); | |
102 | assert_eq!(map.keys().count(), insert.len()); | |
103 | for (a, b) in insert.iter().zip(map.keys()) { | |
104 | assert_eq!(a, b); | |
105 | } | |
106 | for (i, k) in (0..insert.len()).zip(map.keys()) { | |
107 | assert_eq!(map.get_index(i).unwrap().0, k); | |
108 | } | |
109 | } | |
110 | ||
111 | #[test] | |
112 | fn grow() { | |
113 | let insert = [0, 4, 2, 12, 8, 7, 11]; | |
114 | let not_present = [1, 3, 6, 9, 10]; | |
115 | let mut map = IndexMap::with_capacity(insert.len()); | |
116 | ||
117 | for (i, &elt) in insert.iter().enumerate() { | |
118 | assert_eq!(map.len(), i); | |
119 | map.insert(elt, elt); | |
120 | assert_eq!(map.len(), i + 1); | |
121 | assert_eq!(map.get(&elt), Some(&elt)); | |
122 | assert_eq!(map[&elt], elt); | |
123 | } | |
124 | ||
125 | println!("{:?}", map); | |
126 | for &elt in &insert { | |
127 | map.insert(elt * 10, elt); | |
128 | } | |
129 | for &elt in &insert { | |
130 | map.insert(elt * 100, elt); | |
131 | } | |
132 | for (i, &elt) in insert.iter().cycle().enumerate().take(100) { | |
133 | map.insert(elt * 100 + i as i32, elt); | |
134 | } | |
135 | println!("{:?}", map); | |
136 | for &elt in ¬_present { | |
137 | assert!(map.get(&elt).is_none()); | |
138 | } | |
139 | } | |
140 | ||
141 | #[test] | |
142 | fn reserve() { | |
143 | let mut map = IndexMap::<usize, usize>::new(); | |
144 | assert_eq!(map.capacity(), 0); | |
145 | map.reserve(100); | |
146 | let capacity = map.capacity(); | |
147 | assert!(capacity >= 100); | |
148 | for i in 0..capacity { | |
149 | assert_eq!(map.len(), i); | |
150 | map.insert(i, i * i); | |
151 | assert_eq!(map.len(), i + 1); | |
152 | assert_eq!(map.capacity(), capacity); | |
153 | assert_eq!(map.get(&i), Some(&(i * i))); | |
154 | } | |
155 | map.insert(capacity, std::usize::MAX); | |
156 | assert_eq!(map.len(), capacity + 1); | |
157 | assert!(map.capacity() > capacity); | |
158 | assert_eq!(map.get(&capacity), Some(&std::usize::MAX)); | |
159 | } | |
160 | ||
161 | #[test] | |
162 | fn try_reserve() { | |
163 | let mut map = IndexMap::<usize, usize>::new(); | |
164 | assert_eq!(map.capacity(), 0); | |
165 | assert_eq!(map.try_reserve(100), Ok(())); | |
166 | assert!(map.capacity() >= 100); | |
167 | assert!(map.try_reserve(usize::MAX).is_err()); | |
168 | } | |
169 | ||
170 | #[test] | |
171 | fn shrink_to_fit() { | |
172 | let mut map = IndexMap::<usize, usize>::new(); | |
173 | assert_eq!(map.capacity(), 0); | |
174 | for i in 0..100 { | |
175 | assert_eq!(map.len(), i); | |
176 | map.insert(i, i * i); | |
177 | assert_eq!(map.len(), i + 1); | |
178 | assert!(map.capacity() >= i + 1); | |
179 | assert_eq!(map.get(&i), Some(&(i * i))); | |
180 | map.shrink_to_fit(); | |
181 | assert_eq!(map.len(), i + 1); | |
182 | assert_eq!(map.capacity(), i + 1); | |
183 | assert_eq!(map.get(&i), Some(&(i * i))); | |
184 | } | |
185 | } | |
186 | ||
187 | #[test] | |
188 | fn remove() { | |
189 | let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; | |
190 | let mut map = IndexMap::new(); | |
191 | ||
192 | for &elt in &insert { | |
193 | map.insert(elt, elt); | |
194 | } | |
195 | ||
196 | assert_eq!(map.keys().count(), map.len()); | |
197 | assert_eq!(map.keys().count(), insert.len()); | |
198 | for (a, b) in insert.iter().zip(map.keys()) { | |
199 | assert_eq!(a, b); | |
200 | } | |
201 | ||
202 | let remove_fail = [99, 77]; | |
203 | let remove = [4, 12, 8, 7]; | |
204 | ||
205 | for &key in &remove_fail { | |
206 | assert!(map.swap_remove_full(&key).is_none()); | |
207 | } | |
208 | println!("{:?}", map); | |
209 | for &key in &remove { | |
210 | //println!("{:?}", map); | |
211 | let index = map.get_full(&key).unwrap().0; | |
212 | assert_eq!(map.swap_remove_full(&key), Some((index, key, key))); | |
213 | } | |
214 | println!("{:?}", map); | |
215 | ||
216 | for key in &insert { | |
217 | assert_eq!(map.get(key).is_some(), !remove.contains(key)); | |
218 | } | |
219 | assert_eq!(map.len(), insert.len() - remove.len()); | |
220 | assert_eq!(map.keys().count(), insert.len() - remove.len()); | |
221 | } | |
222 | ||
223 | #[test] | |
224 | fn remove_to_empty() { | |
225 | let mut map = indexmap! { 0 => 0, 4 => 4, 5 => 5 }; | |
226 | map.swap_remove(&5).unwrap(); | |
227 | map.swap_remove(&4).unwrap(); | |
228 | map.swap_remove(&0).unwrap(); | |
229 | assert!(map.is_empty()); | |
230 | } | |
231 | ||
232 | #[test] | |
233 | fn swap_remove_index() { | |
234 | let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; | |
235 | let mut map = IndexMap::new(); | |
236 | ||
237 | for &elt in &insert { | |
238 | map.insert(elt, elt * 2); | |
239 | } | |
240 | ||
241 | let mut vector = insert.to_vec(); | |
242 | let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1]; | |
243 | ||
244 | // check that the same swap remove sequence on vec and map | |
245 | // have the same result. | |
246 | for &rm in remove_sequence { | |
247 | let out_vec = vector.swap_remove(rm); | |
248 | let (out_map, _) = map.swap_remove_index(rm).unwrap(); | |
249 | assert_eq!(out_vec, out_map); | |
250 | } | |
251 | assert_eq!(vector.len(), map.len()); | |
252 | for (a, b) in vector.iter().zip(map.keys()) { | |
253 | assert_eq!(a, b); | |
254 | } | |
255 | } | |
256 | ||
257 | #[test] | |
258 | fn partial_eq_and_eq() { | |
259 | let mut map_a = IndexMap::new(); | |
260 | map_a.insert(1, "1"); | |
261 | map_a.insert(2, "2"); | |
262 | let mut map_b = map_a.clone(); | |
263 | assert_eq!(map_a, map_b); | |
264 | map_b.swap_remove(&1); | |
265 | assert_ne!(map_a, map_b); | |
266 | ||
267 | let map_c: IndexMap<_, String> = map_b.into_iter().map(|(k, v)| (k, v.into())).collect(); | |
268 | assert_ne!(map_a, map_c); | |
269 | assert_ne!(map_c, map_a); | |
270 | } | |
271 | ||
272 | #[test] | |
273 | fn extend() { | |
274 | let mut map = IndexMap::new(); | |
275 | map.extend(vec![(&1, &2), (&3, &4)]); | |
276 | map.extend(vec![(5, 6)]); | |
277 | assert_eq!( | |
278 | map.into_iter().collect::<Vec<_>>(), | |
279 | vec![(1, 2), (3, 4), (5, 6)] | |
280 | ); | |
281 | } | |
282 | ||
283 | #[test] | |
284 | fn entry() { | |
285 | let mut map = IndexMap::new(); | |
286 | ||
287 | map.insert(1, "1"); | |
288 | map.insert(2, "2"); | |
289 | { | |
290 | let e = map.entry(3); | |
291 | assert_eq!(e.index(), 2); | |
292 | let e = e.or_insert("3"); | |
293 | assert_eq!(e, &"3"); | |
294 | } | |
295 | ||
296 | let e = map.entry(2); | |
297 | assert_eq!(e.index(), 1); | |
298 | assert_eq!(e.key(), &2); | |
299 | match e { | |
300 | Entry::Occupied(ref e) => assert_eq!(e.get(), &"2"), | |
301 | Entry::Vacant(_) => panic!(), | |
302 | } | |
303 | assert_eq!(e.or_insert("4"), &"2"); | |
304 | } | |
305 | ||
306 | #[test] | |
307 | fn entry_and_modify() { | |
308 | let mut map = IndexMap::new(); | |
309 | ||
310 | map.insert(1, "1"); | |
311 | map.entry(1).and_modify(|x| *x = "2"); | |
312 | assert_eq!(Some(&"2"), map.get(&1)); | |
313 | ||
314 | map.entry(2).and_modify(|x| *x = "doesn't exist"); | |
315 | assert_eq!(None, map.get(&2)); | |
316 | } | |
317 | ||
318 | #[test] | |
319 | fn entry_or_default() { | |
320 | let mut map = IndexMap::new(); | |
321 | ||
322 | #[derive(Debug, PartialEq)] | |
323 | enum TestEnum { | |
324 | DefaultValue, | |
325 | NonDefaultValue, | |
326 | } | |
327 | ||
328 | impl Default for TestEnum { | |
329 | fn default() -> Self { | |
330 | TestEnum::DefaultValue | |
331 | } | |
332 | } | |
333 | ||
334 | map.insert(1, TestEnum::NonDefaultValue); | |
335 | assert_eq!(&mut TestEnum::NonDefaultValue, map.entry(1).or_default()); | |
336 | ||
337 | assert_eq!(&mut TestEnum::DefaultValue, map.entry(2).or_default()); | |
338 | } | |
339 | ||
340 | #[test] | |
341 | fn occupied_entry_key() { | |
342 | // These keys match hash and equality, but their addresses are distinct. | |
343 | let (k1, k2) = (&mut 1, &mut 1); | |
344 | let k1_ptr = k1 as *const i32; | |
345 | let k2_ptr = k2 as *const i32; | |
346 | assert_ne!(k1_ptr, k2_ptr); | |
347 | ||
348 | let mut map = IndexMap::new(); | |
349 | map.insert(k1, "value"); | |
350 | match map.entry(k2) { | |
351 | Entry::Occupied(ref e) => { | |
352 | // `OccupiedEntry::key` should reference the key in the map, | |
353 | // not the key that was used to find the entry. | |
354 | let ptr = *e.key() as *const i32; | |
355 | assert_eq!(ptr, k1_ptr); | |
356 | assert_ne!(ptr, k2_ptr); | |
357 | } | |
358 | Entry::Vacant(_) => panic!(), | |
359 | } | |
360 | } | |
361 | ||
362 | #[test] | |
363 | fn keys() { | |
364 | let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; | |
365 | let map: IndexMap<_, _> = vec.into_iter().collect(); | |
366 | let keys: Vec<_> = map.keys().copied().collect(); | |
367 | assert_eq!(keys.len(), 3); | |
368 | assert!(keys.contains(&1)); | |
369 | assert!(keys.contains(&2)); | |
370 | assert!(keys.contains(&3)); | |
371 | } | |
372 | ||
373 | #[test] | |
374 | fn into_keys() { | |
375 | let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; | |
376 | let map: IndexMap<_, _> = vec.into_iter().collect(); | |
377 | let keys: Vec<i32> = map.into_keys().collect(); | |
378 | assert_eq!(keys.len(), 3); | |
379 | assert!(keys.contains(&1)); | |
380 | assert!(keys.contains(&2)); | |
381 | assert!(keys.contains(&3)); | |
382 | } | |
383 | ||
384 | #[test] | |
385 | fn values() { | |
386 | let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; | |
387 | let map: IndexMap<_, _> = vec.into_iter().collect(); | |
388 | let values: Vec<_> = map.values().copied().collect(); | |
389 | assert_eq!(values.len(), 3); | |
390 | assert!(values.contains(&'a')); | |
391 | assert!(values.contains(&'b')); | |
392 | assert!(values.contains(&'c')); | |
393 | } | |
394 | ||
395 | #[test] | |
396 | fn values_mut() { | |
397 | let vec = vec![(1, 1), (2, 2), (3, 3)]; | |
398 | let mut map: IndexMap<_, _> = vec.into_iter().collect(); | |
399 | for value in map.values_mut() { | |
400 | *value *= 2 | |
401 | } | |
402 | let values: Vec<_> = map.values().copied().collect(); | |
403 | assert_eq!(values.len(), 3); | |
404 | assert!(values.contains(&2)); | |
405 | assert!(values.contains(&4)); | |
406 | assert!(values.contains(&6)); | |
407 | } | |
408 | ||
409 | #[test] | |
410 | fn into_values() { | |
411 | let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; | |
412 | let map: IndexMap<_, _> = vec.into_iter().collect(); | |
413 | let values: Vec<char> = map.into_values().collect(); | |
414 | assert_eq!(values.len(), 3); | |
415 | assert!(values.contains(&'a')); | |
416 | assert!(values.contains(&'b')); | |
417 | assert!(values.contains(&'c')); | |
418 | } | |
419 | ||
420 | #[test] | |
421 | #[cfg(feature = "std")] | |
422 | fn from_array() { | |
423 | let map = IndexMap::from([(1, 2), (3, 4)]); | |
424 | let mut expected = IndexMap::new(); | |
425 | expected.insert(1, 2); | |
426 | expected.insert(3, 4); | |
427 | ||
428 | assert_eq!(map, expected) | |
429 | } | |
430 | ||
431 | #[test] | |
432 | fn iter_default() { | |
433 | struct K; | |
434 | struct V; | |
435 | fn assert_default<T>() | |
436 | where | |
437 | T: Default + Iterator, | |
438 | { | |
439 | assert!(T::default().next().is_none()); | |
440 | } | |
441 | assert_default::<Iter<'static, K, V>>(); | |
442 | assert_default::<IterMut<'static, K, V>>(); | |
443 | assert_default::<IntoIter<K, V>>(); | |
444 | assert_default::<Keys<'static, K, V>>(); | |
445 | assert_default::<IntoKeys<K, V>>(); | |
446 | assert_default::<Values<'static, K, V>>(); | |
447 | assert_default::<ValuesMut<'static, K, V>>(); | |
448 | assert_default::<IntoValues<K, V>>(); | |
449 | } | |
4b012472 FG |
450 | |
451 | #[test] | |
452 | fn test_binary_search_by() { | |
453 | // adapted from std's test for binary_search | |
454 | let b: IndexMap<_, i32> = [] | |
455 | .into_iter() | |
456 | .enumerate() | |
457 | .map(|(i, x)| (i + 100, x)) | |
458 | .collect(); | |
459 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(0)); | |
460 | ||
461 | let b: IndexMap<_, i32> = [4] | |
462 | .into_iter() | |
463 | .enumerate() | |
464 | .map(|(i, x)| (i + 100, x)) | |
465 | .collect(); | |
466 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&3)), Err(0)); | |
467 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&4)), Ok(0)); | |
468 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(1)); | |
469 | ||
470 | let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9] | |
471 | .into_iter() | |
472 | .enumerate() | |
473 | .map(|(i, x)| (i + 100, x)) | |
474 | .collect(); | |
475 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(3)); | |
476 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Ok(3)); | |
477 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Err(4)); | |
478 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Ok(4)); | |
479 | ||
480 | let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8] | |
481 | .into_iter() | |
482 | .enumerate() | |
483 | .map(|(i, x)| (i + 100, x)) | |
484 | .collect(); | |
485 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&9)), Err(6)); | |
486 | ||
487 | let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9] | |
488 | .into_iter() | |
489 | .enumerate() | |
490 | .map(|(i, x)| (i + 100, x)) | |
491 | .collect(); | |
492 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Ok(3)); | |
493 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(3)); | |
494 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Ok(5)); | |
495 | ||
496 | let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9] | |
497 | .into_iter() | |
498 | .enumerate() | |
499 | .map(|(i, x)| (i + 100, x)) | |
500 | .collect(); | |
501 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Err(5)); | |
502 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&0)), Err(0)); | |
503 | ||
504 | let b: IndexMap<_, i32> = [1, 3, 3, 3, 7] | |
505 | .into_iter() | |
506 | .enumerate() | |
507 | .map(|(i, x)| (i + 100, x)) | |
508 | .collect(); | |
509 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&0)), Err(0)); | |
510 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&1)), Ok(0)); | |
511 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&2)), Err(1)); | |
512 | assert!(match b.binary_search_by(|_, x| x.cmp(&3)) { | |
513 | Ok(1..=3) => true, | |
514 | _ => false, | |
515 | }); | |
516 | assert!(match b.binary_search_by(|_, x| x.cmp(&3)) { | |
517 | Ok(1..=3) => true, | |
518 | _ => false, | |
519 | }); | |
520 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&4)), Err(4)); | |
521 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(4)); | |
522 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Err(4)); | |
523 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Ok(4)); | |
524 | assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Err(5)); | |
525 | } | |
526 | ||
527 | #[test] | |
528 | fn test_binary_search_by_key() { | |
529 | // adapted from std's test for binary_search | |
530 | let b: IndexMap<_, i32> = [] | |
531 | .into_iter() | |
532 | .enumerate() | |
533 | .map(|(i, x)| (i + 100, x)) | |
534 | .collect(); | |
535 | assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(0)); | |
536 | ||
537 | let b: IndexMap<_, i32> = [4] | |
538 | .into_iter() | |
539 | .enumerate() | |
540 | .map(|(i, x)| (i + 100, x)) | |
541 | .collect(); | |
542 | assert_eq!(b.binary_search_by_key(&3, |_, &x| x), Err(0)); | |
543 | assert_eq!(b.binary_search_by_key(&4, |_, &x| x), Ok(0)); | |
544 | assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(1)); | |
545 | ||
546 | let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9] | |
547 | .into_iter() | |
548 | .enumerate() | |
549 | .map(|(i, x)| (i + 100, x)) | |
550 | .collect(); | |
551 | assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(3)); | |
552 | assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Ok(3)); | |
553 | assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Err(4)); | |
554 | assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Ok(4)); | |
555 | ||
556 | let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8] | |
557 | .into_iter() | |
558 | .enumerate() | |
559 | .map(|(i, x)| (i + 100, x)) | |
560 | .collect(); | |
561 | assert_eq!(b.binary_search_by_key(&9, |_, &x| x), Err(6)); | |
562 | ||
563 | let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9] | |
564 | .into_iter() | |
565 | .enumerate() | |
566 | .map(|(i, x)| (i + 100, x)) | |
567 | .collect(); | |
568 | assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Ok(3)); | |
569 | assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(3)); | |
570 | assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Ok(5)); | |
571 | ||
572 | let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9] | |
573 | .into_iter() | |
574 | .enumerate() | |
575 | .map(|(i, x)| (i + 100, x)) | |
576 | .collect(); | |
577 | assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Err(5)); | |
578 | assert_eq!(b.binary_search_by_key(&0, |_, &x| x), Err(0)); | |
579 | ||
580 | let b: IndexMap<_, i32> = [1, 3, 3, 3, 7] | |
581 | .into_iter() | |
582 | .enumerate() | |
583 | .map(|(i, x)| (i + 100, x)) | |
584 | .collect(); | |
585 | assert_eq!(b.binary_search_by_key(&0, |_, &x| x), Err(0)); | |
586 | assert_eq!(b.binary_search_by_key(&1, |_, &x| x), Ok(0)); | |
587 | assert_eq!(b.binary_search_by_key(&2, |_, &x| x), Err(1)); | |
588 | assert!(match b.binary_search_by_key(&3, |_, &x| x) { | |
589 | Ok(1..=3) => true, | |
590 | _ => false, | |
591 | }); | |
592 | assert!(match b.binary_search_by_key(&3, |_, &x| x) { | |
593 | Ok(1..=3) => true, | |
594 | _ => false, | |
595 | }); | |
596 | assert_eq!(b.binary_search_by_key(&4, |_, &x| x), Err(4)); | |
597 | assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(4)); | |
598 | assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Err(4)); | |
599 | assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Ok(4)); | |
600 | assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Err(5)); | |
601 | } | |
602 | ||
603 | #[test] | |
604 | fn test_partition_point() { | |
605 | // adapted from std's test for partition_point | |
606 | let b: IndexMap<_, i32> = [] | |
607 | .into_iter() | |
608 | .enumerate() | |
609 | .map(|(i, x)| (i + 100, x)) | |
610 | .collect(); | |
611 | assert_eq!(b.partition_point(|_, &x| x < 5), 0); | |
612 | ||
613 | let b: IndexMap<_, i32> = [4] | |
614 | .into_iter() | |
615 | .enumerate() | |
616 | .map(|(i, x)| (i + 100, x)) | |
617 | .collect(); | |
618 | assert_eq!(b.partition_point(|_, &x| x < 3), 0); | |
619 | assert_eq!(b.partition_point(|_, &x| x < 4), 0); | |
620 | assert_eq!(b.partition_point(|_, &x| x < 5), 1); | |
621 | ||
622 | let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9] | |
623 | .into_iter() | |
624 | .enumerate() | |
625 | .map(|(i, x)| (i + 100, x)) | |
626 | .collect(); | |
627 | assert_eq!(b.partition_point(|_, &x| x < 5), 3); | |
628 | assert_eq!(b.partition_point(|_, &x| x < 6), 3); | |
629 | assert_eq!(b.partition_point(|_, &x| x < 7), 4); | |
630 | assert_eq!(b.partition_point(|_, &x| x < 8), 4); | |
631 | ||
632 | let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8] | |
633 | .into_iter() | |
634 | .enumerate() | |
635 | .map(|(i, x)| (i + 100, x)) | |
636 | .collect(); | |
637 | assert_eq!(b.partition_point(|_, &x| x < 9), 6); | |
638 | ||
639 | let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9] | |
640 | .into_iter() | |
641 | .enumerate() | |
642 | .map(|(i, x)| (i + 100, x)) | |
643 | .collect(); | |
644 | assert_eq!(b.partition_point(|_, &x| x < 6), 3); | |
645 | assert_eq!(b.partition_point(|_, &x| x < 5), 3); | |
646 | assert_eq!(b.partition_point(|_, &x| x < 8), 5); | |
647 | ||
648 | let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9] | |
649 | .into_iter() | |
650 | .enumerate() | |
651 | .map(|(i, x)| (i + 100, x)) | |
652 | .collect(); | |
653 | assert_eq!(b.partition_point(|_, &x| x < 7), 5); | |
654 | assert_eq!(b.partition_point(|_, &x| x < 0), 0); | |
655 | ||
656 | let b: IndexMap<_, i32> = [1, 3, 3, 3, 7] | |
657 | .into_iter() | |
658 | .enumerate() | |
659 | .map(|(i, x)| (i + 100, x)) | |
660 | .collect(); | |
661 | assert_eq!(b.partition_point(|_, &x| x < 0), 0); | |
662 | assert_eq!(b.partition_point(|_, &x| x < 1), 0); | |
663 | assert_eq!(b.partition_point(|_, &x| x < 2), 1); | |
664 | assert_eq!(b.partition_point(|_, &x| x < 3), 1); | |
665 | assert_eq!(b.partition_point(|_, &x| x < 4), 4); | |
666 | assert_eq!(b.partition_point(|_, &x| x < 5), 4); | |
667 | assert_eq!(b.partition_point(|_, &x| x < 6), 4); | |
668 | assert_eq!(b.partition_point(|_, &x| x < 7), 4); | |
669 | assert_eq!(b.partition_point(|_, &x| x < 8), 5); | |
670 | } |