Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_data/src/interval.rs

20.0 KiB, 5 runs

created by r1870400018:17526, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! An ordered map from disjoint half-open integer intervals to values.
2//!
3//! An [`IntervalMap`] partitions a subset of the `u64` line into non-overlapping
4//! half-open intervals `[start, end)`, each carrying one value. The map is the
5//! natural shape for interval bookkeeping: recording which stretches of an index
6//! space are spoken for, and by what.
7//!
8//! Insertion is last-writer-wins. A new interval displaces whatever occupied the
9//! ground it covers, splitting the intervals it partly overlaps so that only the
10//! uncovered remainders survive. The invariant that no two intervals overlap is
11//! therefore maintained by construction rather than checked afterwards.
12//!
13//! Adjacent intervals carrying equal values are coalesced, so the map never
14//! holds two neighbours that a reader could not tell apart. Representation is
15//! thus canonical for a given covering: two maps built by different sequences of
16//! insertions compare equal whenever they describe the same covering.
17
18use oxedyne_fe2o3_core::prelude::*;
19
20use std::collections::BTreeMap;
21use std::ops::Range;
22
23
24/// An ordered map from disjoint half-open `u64` intervals to values.
25///
26/// Entries are keyed by interval start and ordered by it. No two intervals in
27/// the map overlap, and no two adjacent intervals carry equal values.
28///
29/// # Type Parameters
30///
31/// * `V` - The value carried by an interval. `Clone` is needed to split an
32/// interval in two, and `PartialEq` to decide whether neighbours coalesce.
33#[derive(Clone, Debug, Eq, PartialEq)]
34pub struct IntervalMap<V> {
35 /// Start of each interval mapped to its exclusive end and its value.
36 map: BTreeMap<u64, (u64, V)>,
37}
38
39impl<V> Default for IntervalMap<V> {
40 fn default() -> Self {
41 Self { map: BTreeMap::new() }
42 }
43}
44
45impl<V> IntervalMap<V> {
46
47 /// Constructs an empty map.
48 pub fn new() -> Self {
49 Self { map: BTreeMap::new() }
50 }
51
52 /// Returns the number of intervals in the map.
53 ///
54 /// This counts intervals, not the points they cover, and coalescing can
55 /// lower it: inserting into a map of two intervals may leave one.
56 pub fn len(&self) -> usize {
57 self.map.len()
58 }
59
60 /// Reports whether the map holds no intervals.
61 pub fn is_empty(&self) -> bool {
62 self.map.is_empty()
63 }
64
65 /// Removes every interval, leaving the map empty.
66 pub fn clear(&mut self) {
67 self.map.clear();
68 }
69
70 /// Returns the value covering `point`, if any.
71 ///
72 /// The interval `[s, e)` covers `point` when `s <= point < e`, so the value
73 /// is returned at an interval's start but not at its end.
74 pub fn get(&self, point: u64)
75 -> Option<&V>
76 {
77 self.entry(point).map(|(_, val)| val)
78 }
79
80 /// Returns the interval covering `point` together with its value.
81 pub fn entry(&self, point: u64)
82 -> Option<(Range<u64>, &V)>
83 {
84 match self.map.range(..=point).next_back() {
85 Some((start, (end, val))) if *end > point =>
86 Some((*start..*end, val)),
87 _ => None,
88 }
89 }
90
91 /// Reports whether any interval covers `point`.
92 pub fn contains(&self, point: u64) -> bool {
93 self.get(point).is_some()
94 }
95
96 /// Iterates over the intervals in ascending order of start.
97 pub fn iter(&self)
98 -> impl Iterator<Item = (Range<u64>, &V)>
99 {
100 self.map.iter().map(|(start, (end, val))| (*start..*end, val))
101 }
102
103 /// Iterates over the intervals overlapping `range`, in ascending order of
104 /// start.
105 ///
106 /// Intervals are yielded as they are stored, so the first and last may reach
107 /// beyond `range`; a caller wanting only the covered ground clips them. An
108 /// empty or reversed `range` overlaps nothing and yields nothing.
109 ///
110 /// # Examples
111 ///
112 /// ```
113 /// use oxedyne_fe2o3_data::interval::IntervalMap;
114 ///
115 /// let mut map: IntervalMap<char> = IntervalMap::new();
116 /// assert!(map.insert(0..10, 'a').is_ok());
117 /// assert!(map.insert(20..30, 'b').is_ok());
118 ///
119 /// let hit: Vec<char> = map.overlapping(5..25).map(|(_, v)| *v).collect();
120 /// assert_eq!(hit, vec!['a', 'b']);
121 /// assert_eq!(map.overlapping(10..20).count(), 0);
122 /// ```
123 pub fn overlapping(&self, range: Range<u64>)
124 -> impl Iterator<Item = (Range<u64>, &V)>
125 {
126 let (start, end) = (range.start, range.end);
127 let live = end > start;
128 // At most one interval begins before the range and reaches into it; the
129 // rest begin inside it.
130 let head = match self.map.range(..start).next_back() {
131 Some((s, (e, val))) if live && *e > start => Some((*s..*e, val)),
132 _ => None,
133 };
134 let hi = if live { end } else { start };
135 head.into_iter()
136 .chain(self.map.range(start..hi).map(|(s, (e, val))| (*s..*e, val)))
137 }
138}
139
140impl<V: Clone + PartialEq> IntervalMap<V> {
141
142 /// Inserts `val` over `range`, overwriting whatever it covers.
143 ///
144 /// The contract is last-writer-wins over the covered ground, and nothing
145 /// else. Every point in `range` afterwards maps to `val`; every point
146 /// outside it keeps the value it had. An existing interval that `range`
147 /// covers entirely is removed; one that `range` covers in part is split, and
148 /// only the uncovered remainder survives, carrying a clone of the original
149 /// value.
150 ///
151 /// Once the ground is taken, the new interval is coalesced with either
152 /// neighbour that abuts it and carries an equal value, so the map stays
153 /// canonical.
154 ///
155 /// Fails when the range is empty, that is, when `end <= start`. An empty
156 /// range would name no ground and so could not be an intelligible claim on
157 /// any.
158 ///
159 /// # Examples
160 ///
161 /// ```
162 /// use oxedyne_fe2o3_data::interval::IntervalMap;
163 ///
164 /// let mut map: IntervalMap<char> = IntervalMap::new();
165 /// assert!(map.insert(0..100, 'a').is_ok());
166 /// assert!(map.insert(40..60, 'b').is_ok());
167 ///
168 /// // The later write holds the middle, and the first survives either side.
169 /// assert_eq!(map.get(39), Some(&'a'));
170 /// assert_eq!(map.get(40), Some(&'b'));
171 /// assert_eq!(map.get(60), Some(&'a'));
172 /// assert_eq!(map.len(), 3);
173 /// ```
174 pub fn insert(&mut self, range: Range<u64>, val: V)
175 -> Outcome<()>
176 {
177 let (start, end) = (range.start, range.end);
178 if end <= start {
179 return Err(err!(
180 "The interval [{}, {}) is empty; a range must satisfy start < end.",
181 start, end;
182 Invalid, Input, Range));
183 }
184 self.vacate(start, end);
185 self.map.insert(start, (end, val));
186 self.coalesce(start);
187 Ok(())
188 }
189
190 /// Removes every interval, and part-interval, lying within `range`.
191 ///
192 /// Points inside `range` are afterwards covered by nothing; points outside
193 /// it are untouched, an interval straddling an edge being split rather than
194 /// dropped. Fails on an empty range, as [`IntervalMap::insert`] does.
195 pub fn remove(&mut self, range: Range<u64>)
196 -> Outcome<()>
197 {
198 let (start, end) = (range.start, range.end);
199 if end <= start {
200 return Err(err!(
201 "The interval [{}, {}) is empty; a range must satisfy start < end.",
202 start, end;
203 Invalid, Input, Range));
204 }
205 self.vacate(start, end);
206 Ok(())
207 }
208
209 /// Clears `[start, end)`, splitting any interval that straddles an edge.
210 ///
211 /// Leaves the map free of any coverage inside the range, and unchanged
212 /// outside it.
213 fn vacate(&mut self, start: u64, end: u64) {
214 // The starts of every interval overlapping the range. At most one
215 // begins before the range and reaches into it; the rest begin inside.
216 let mut hits = Vec::new();
217 if let Some((s, (e, _))) = self.map.range(..start).next_back() {
218 if *e > start {
219 hits.push(*s);
220 }
221 }
222 for (s, _) in self.map.range(start..end) {
223 hits.push(*s);
224 }
225 for s in hits {
226 // Take the interval out, then put back whatever falls outside the
227 // range. A hit straddling both edges yields two remainders.
228 if let Some((e, val)) = self.map.remove(&s) {
229 if s < start {
230 self.map.insert(s, (start, val.clone()));
231 }
232 if e > end {
233 self.map.insert(end, (e, val));
234 }
235 }
236 }
237 }
238
239 /// Merges the interval starting at `start` with any abutting equal
240 /// neighbour.
241 ///
242 /// Does nothing if no interval starts there.
243 fn coalesce(&mut self, start: u64) {
244 let (end, val) = match self.map.get(&start) {
245 Some((e, v)) => (*e, v.clone()),
246 None => return,
247 };
248 let mut lo = start;
249 let mut hi = end;
250 // A left neighbour abuts when its end is this interval's start.
251 if let Some((s, (e, v))) = self.map.range(..start).next_back() {
252 if *e == start && *v == val {
253 lo = *s;
254 }
255 }
256 // A right neighbour abuts when it is keyed at this interval's end.
257 if let Some((e, v)) = self.map.get(&end) {
258 if *v == val {
259 hi = *e;
260 }
261 }
262 if lo != start {
263 self.map.remove(&lo);
264 }
265 if hi != end {
266 self.map.remove(&end);
267 }
268 self.map.remove(&start);
269 self.map.insert(lo, (hi, val));
270 }
271}
272
273
274// ┌───────────────────────────────────────────────────────────────────────────┐
275// │ TESTS │
276// └───────────────────────────────────────────────────────────────────────────┘
277
278#[cfg(test)]
279mod tests {
280 use super::*;
281
282 /// Collects the map into a comparable form, so a test can state the whole
283 /// expected covering in one line.
284 fn dump(map: &IntervalMap<char>) -> Vec<(u64, u64, char)> {
285 map.iter().map(|(r, v)| (r.start, r.end, *v)).collect()
286 }
287
288 #[test]
289 fn test_a_new_map_is_empty_00() {
290 let map: IntervalMap<char> = IntervalMap::new();
291 assert!(map.is_empty());
292 assert_eq!(map.len(), 0);
293 assert_eq!(map.get(0), None);
294 assert_eq!(map.get(u64::MAX), None);
295 }
296
297 #[test]
298 fn test_an_empty_range_is_refused_00() {
299 let mut map: IntervalMap<char> = IntervalMap::new();
300 assert!(map.insert(5..5, 'a').is_err(),
301 "a zero-width range names no ground");
302 assert!(map.insert(9..5, 'a').is_err(),
303 "a reversed range names no ground");
304 assert!(map.remove(5..5).is_err());
305 assert!(map.is_empty(),
306 "a refused insertion must leave the map untouched");
307 }
308
309 #[test]
310 fn test_a_point_query_respects_both_boundaries_00() {
311 let mut map = IntervalMap::new();
312 assert!(map.insert(10..20, 'a').is_ok());
313 assert_eq!(map.get(9), None, "the point before the start is outside");
314 assert_eq!(map.get(10), Some(&'a'), "the start is inside");
315 assert_eq!(map.get(15), Some(&'a'));
316 assert_eq!(map.get(19), Some(&'a'), "the last covered point is inside");
317 assert_eq!(map.get(20), None, "the end is exclusive");
318 assert_eq!(map.get(21), None);
319 assert!(map.contains(10));
320 assert!(!map.contains(20));
321 }
322
323 #[test]
324 fn test_entry_reports_the_covering_interval_00() {
325 let mut map = IntervalMap::new();
326 assert!(map.insert(10..20, 'a').is_ok());
327 assert_eq!(map.entry(14), Some((10..20, &'a')));
328 assert_eq!(map.entry(20), None);
329 }
330
331 #[test]
332 fn test_disjoint_insertions_are_kept_apart_00() {
333 let mut map = IntervalMap::new();
334 assert!(map.insert(0..10, 'a').is_ok());
335 assert!(map.insert(20..30, 'b').is_ok());
336 assert!(map.insert(10..20, 'c').is_ok());
337 assert_eq!(dump(&map), vec![(0, 10, 'a'), (10, 20, 'c'), (20, 30, 'b')]);
338 assert_eq!(map.get(15), Some(&'c'));
339 }
340
341 #[test]
342 fn test_an_overwrite_wholly_inside_splits_in_three_00() {
343 let mut map = IntervalMap::new();
344 assert!(map.insert(0..100, 'a').is_ok());
345 assert!(map.insert(40..60, 'b').is_ok());
346 assert_eq!(dump(&map), vec![(0, 40, 'a'), (40, 60, 'b'), (60, 100, 'a')]);
347 assert_eq!(map.get(39), Some(&'a'));
348 assert_eq!(map.get(40), Some(&'b'));
349 assert_eq!(map.get(59), Some(&'b'));
350 assert_eq!(map.get(60), Some(&'a'));
351 }
352
353 #[test]
354 fn test_an_overwrite_spanning_an_interval_replaces_it_00() {
355 let mut map = IntervalMap::new();
356 assert!(map.insert(40..60, 'a').is_ok());
357 assert!(map.insert(0..100, 'b').is_ok());
358 assert_eq!(dump(&map), vec![(0, 100, 'b')]);
359 assert_eq!(map.get(50), Some(&'b'));
360 }
361
362 #[test]
363 fn test_an_overwrite_on_the_left_edge_trims_the_start_00() {
364 let mut map = IntervalMap::new();
365 assert!(map.insert(10..20, 'a').is_ok());
366 assert!(map.insert(5..15, 'b').is_ok());
367 assert_eq!(dump(&map), vec![(5, 15, 'b'), (15, 20, 'a')]);
368 assert_eq!(map.get(14), Some(&'b'));
369 assert_eq!(map.get(15), Some(&'a'));
370 }
371
372 #[test]
373 fn test_an_overwrite_on_the_right_edge_trims_the_end_00() {
374 let mut map = IntervalMap::new();
375 assert!(map.insert(10..20, 'a').is_ok());
376 assert!(map.insert(15..25, 'b').is_ok());
377 assert_eq!(dump(&map), vec![(10, 15, 'a'), (15, 25, 'b')]);
378 assert_eq!(map.get(14), Some(&'a'));
379 assert_eq!(map.get(15), Some(&'b'));
380 assert_eq!(map.get(24), Some(&'b'));
381 assert_eq!(map.get(25), None);
382 }
383
384 #[test]
385 fn test_an_exact_overwrite_replaces_the_value_00() {
386 let mut map = IntervalMap::new();
387 assert!(map.insert(10..20, 'a').is_ok());
388 assert!(map.insert(10..20, 'b').is_ok());
389 assert_eq!(dump(&map), vec![(10, 20, 'b')]);
390 assert_eq!(map.len(), 1);
391 }
392
393 #[test]
394 fn test_an_overwrite_across_several_intervals_00() {
395 let mut map = IntervalMap::new();
396 assert!(map.insert(0..10, 'a').is_ok());
397 assert!(map.insert(10..20, 'b').is_ok());
398 assert!(map.insert(20..30, 'c').is_ok());
399 assert!(map.insert(30..40, 'd').is_ok());
400 // Straddles the first, swallows the middle two, straddles the last.
401 assert!(map.insert(5..35, 'z').is_ok());
402 assert_eq!(dump(&map), vec![(0, 5, 'a'), (5, 35, 'z'), (35, 40, 'd')]);
403 assert_eq!(map.get(4), Some(&'a'));
404 assert_eq!(map.get(5), Some(&'z'));
405 assert_eq!(map.get(34), Some(&'z'));
406 assert_eq!(map.get(35), Some(&'d'));
407 }
408
409 #[test]
410 fn test_an_overwrite_covering_everything_leaves_one_interval_00() {
411 let mut map = IntervalMap::new();
412 for i in 0..10u64 {
413 assert!(map.insert(i * 10..(i + 1) * 10, 'a').is_ok());
414 }
415 // Ten equal-valued neighbours have already coalesced into one.
416 assert_eq!(dump(&map), vec![(0, 100, 'a')]);
417 assert!(map.insert(0..100, 'b').is_ok());
418 assert_eq!(dump(&map), vec![(0, 100, 'b')]);
419 }
420
421 #[test]
422 fn test_an_abutting_equal_neighbour_coalesces_on_the_left_00() {
423 let mut map = IntervalMap::new();
424 assert!(map.insert(0..10, 'a').is_ok());
425 assert!(map.insert(10..20, 'a').is_ok());
426 assert_eq!(dump(&map), vec![(0, 20, 'a')]);
427 assert_eq!(map.len(), 1);
428 }
429
430 #[test]
431 fn test_an_abutting_equal_neighbour_coalesces_on_the_right_00() {
432 let mut map = IntervalMap::new();
433 assert!(map.insert(10..20, 'a').is_ok());
434 assert!(map.insert(0..10, 'a').is_ok());
435 assert_eq!(dump(&map), vec![(0, 20, 'a')]);
436 }
437
438 #[test]
439 fn test_an_insertion_between_two_equals_coalesces_both_00() {
440 let mut map = IntervalMap::new();
441 assert!(map.insert(0..10, 'a').is_ok());
442 assert!(map.insert(20..30, 'a').is_ok());
443 assert_eq!(map.len(), 2, "the two are not yet adjacent");
444 assert!(map.insert(10..20, 'a').is_ok());
445 assert_eq!(dump(&map), vec![(0, 30, 'a')]);
446 }
447
448 #[test]
449 fn test_an_unequal_neighbour_does_not_coalesce_00() {
450 let mut map = IntervalMap::new();
451 assert!(map.insert(0..10, 'a').is_ok());
452 assert!(map.insert(10..20, 'b').is_ok());
453 assert!(map.insert(20..30, 'a').is_ok());
454 assert_eq!(dump(&map), vec![(0, 10, 'a'), (10, 20, 'b'), (20, 30, 'a')]);
455 }
456
457 #[test]
458 fn test_a_split_remainder_coalesces_with_the_new_value_00() {
459 let mut map = IntervalMap::new();
460 assert!(map.insert(0..100, 'a').is_ok());
461 // The write agrees with what it partly covers, so nothing is divided.
462 assert!(map.insert(40..60, 'a').is_ok());
463 assert_eq!(dump(&map), vec![(0, 100, 'a')]);
464 // And a write past the end simply extends it.
465 assert!(map.insert(90..120, 'a').is_ok());
466 assert_eq!(dump(&map), vec![(0, 120, 'a')]);
467 }
468
469 #[test]
470 fn test_the_representation_is_canonical_00() {
471 let mut a = IntervalMap::new();
472 assert!(a.insert(0..30, 'x').is_ok());
473 let mut b = IntervalMap::new();
474 assert!(b.insert(0..10, 'x').is_ok());
475 assert!(b.insert(10..20, 'x').is_ok());
476 assert!(b.insert(20..30, 'x').is_ok());
477 assert_eq!(a, b,
478 "the same covering reached two ways must compare equal");
479 }
480
481 #[test]
482 fn test_remove_clears_the_range_and_splits_the_edges_00() {
483 let mut map = IntervalMap::new();
484 assert!(map.insert(0..100, 'a').is_ok());
485 assert!(map.remove(40..60).is_ok());
486 assert_eq!(dump(&map), vec![(0, 40, 'a'), (60, 100, 'a')]);
487 assert_eq!(map.get(39), Some(&'a'));
488 assert_eq!(map.get(40), None);
489 assert_eq!(map.get(59), None);
490 assert_eq!(map.get(60), Some(&'a'));
491 }
492
493 #[test]
494 fn test_clear_empties_the_map_00() {
495 let mut map = IntervalMap::new();
496 assert!(map.insert(0..10, 'a').is_ok());
497 assert!(map.insert(20..30, 'b').is_ok());
498 map.clear();
499 assert!(map.is_empty());
500 assert_eq!(map.get(5), None);
501 }
502
503 #[test]
504 fn test_iteration_is_in_ascending_order_00() {
505 let mut map = IntervalMap::new();
506 assert!(map.insert(50..60, 'c').is_ok());
507 assert!(map.insert(0..10, 'a').is_ok());
508 assert!(map.insert(20..30, 'b').is_ok());
509 let starts: Vec<u64> = map.iter().map(|(r, _)| r.start).collect();
510 assert_eq!(starts, vec![0, 20, 50]);
511 }
512
513 /// Checks the map against an independent model: a plain array of points,
514 /// one slot per position, which cannot get splitting or coalescing wrong
515 /// because it does neither. Any disagreement is the map's.
516 #[test]
517 fn test_the_map_agrees_with_a_point_by_point_model_00() {
518 const N: u64 = 64;
519 let mut map: IntervalMap<char> = IntervalMap::new();
520 let mut model = [None::<char>; N as usize];
521 // A small linear congruential generator, so the sequence is fixed and a
522 // failure can be reproduced.
523 let mut seed = 0x2545_F491_4F6C_DD1Du64;
524 let mut next = || {
525 seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
526 seed >> 33
527 };
528 for step in 0..2_000 {
529 let a = next() % N;
530 let b = next() % N;
531 let (lo, hi) = if a <= b { (a, b + 1) } else { (b, a + 1) };
532 let hi = hi.min(N);
533 // Three values only, so coalescing is exercised often.
534 let val = [b'x', b'y', b'z'][(next() % 3) as usize] as char;
535 let removing = next() % 4 == 0;
536 if removing {
537 assert!(map.remove(lo..hi).is_ok(), "step {}", step);
538 for p in lo..hi {
539 model[p as usize] = None;
540 }
541 } else {
542 assert!(map.insert(lo..hi, val).is_ok(), "step {}", step);
543 for p in lo..hi {
544 model[p as usize] = Some(val);
545 }
546 }
547 for p in 0..N {
548 assert_eq!(map.get(p).copied(), model[p as usize],
549 "step {}, point {}", step, p);
550 }
551 // No two intervals may overlap, abut with equal values, or be empty.
552 let mut prev: Option<(u64, u64, char)> = None;
553 for (r, v) in map.iter() {
554 assert!(r.start < r.end, "step {}: an empty interval survived", step);
555 if let Some((_, pe, pv)) = prev {
556 assert!(pe <= r.start, "step {}: intervals overlap", step);
557 assert!(pe < r.start || pv != *v,
558 "step {}: equal neighbours were left uncoalesced", step);
559 }
560 prev = Some((r.start, r.end, *v));
561 }
562 }
563 }
564
565 #[test]
566 fn test_overlapping_yields_only_what_it_touches_00() {
567 let mut map = IntervalMap::new();
568 assert!(map.insert(0..10, 'a').is_ok());
569 assert!(map.insert(20..30, 'b').is_ok());
570 assert!(map.insert(40..50, 'c').is_ok());
571 let hit = |r: Range<u64>| -> Vec<(u64, u64, char)> {
572 map.overlapping(r).map(|(i, v)| (i.start, i.end, *v)).collect()
573 };
574 assert_eq!(hit(0..50), vec![(0, 10, 'a'), (20, 30, 'b'), (40, 50, 'c')]);
575 assert_eq!(hit(10..20), vec![],
576 "the gap between two intervals overlaps neither");
577 assert_eq!(hit(5..25), vec![(0, 10, 'a'), (20, 30, 'b')],
578 "an interval reaching into the range from the left is included whole");
579 assert_eq!(hit(9..10), vec![(0, 10, 'a')]);
580 assert_eq!(hit(10..11), vec![], "the end of an interval is exclusive");
581 assert_eq!(hit(29..31), vec![(20, 30, 'b')]);
582 assert_eq!(hit(30..31), vec![]);
583 }
584
585 #[test]
586 fn test_overlapping_refuses_to_be_confused_by_an_empty_range_00() {
587 let mut map = IntervalMap::new();
588 assert!(map.insert(0..100, 'a').is_ok());
589 assert_eq!(map.overlapping(50..50).count(), 0,
590 "a zero-width range covers no ground");
591 assert_eq!(map.overlapping(60..50).count(), 0,
592 "a reversed range covers no ground");
593 }
594
595 #[test]
596 fn test_the_extremes_of_the_line_are_covered_00() {
597 let mut map = IntervalMap::new();
598 assert!(map.insert(0..1, 'a').is_ok());
599 assert!(map.insert(u64::MAX - 1..u64::MAX, 'b').is_ok());
600 assert_eq!(map.get(0), Some(&'a'));
601 assert_eq!(map.get(1), None);
602 assert_eq!(map.get(u64::MAX - 1), Some(&'b'));
603 assert_eq!(map.get(u64::MAX), None,
604 "the end is exclusive even at the top of the range");
605 }
606}