static_mapset/ordered_slice_map.rs
1use core::{
2 borrow::Borrow,
3 ops::{Bound, Index, RangeBounds}
4};
5
6use crate::internal::ordered_map::{self as internal, order};
7
8/// An iterator over the entries of a `OrderedSliceMap`.
9///
10/// This `struct` is created by the [`iter`] method on [`OrderedSliceMap`]. See its
11/// documentation for more.
12///
13/// [`iter`]: OrderedSliceMap::iter
14pub type Iter<'a, K, V> = internal::Iter<'a, K, V>;
15
16/// An iterator over the keys of a `OrderedSliceMap`.
17///
18/// This `struct` is created by the [`keys`] method on [`OrderedSliceMap`]. See its
19/// documentation for more.
20///
21/// [`keys`]: OrderedSliceMap::keys
22pub type Keys<'a, K, V> = internal::Keys<'a, K, V>;
23
24/// An iterator over a sub-range of entries in a `OrderedSliceMap`.
25///
26/// This `struct` is created by the [`range`] method on [`OrderedSliceMap`]. See its
27/// documentation for more.
28///
29/// [`range`]: OrderedSliceMap::range
30pub type Range<'a, K, V> = internal::Iter<'a, K, V>;
31
32/// An iterator over the values of a `OrderedSliceMap`.
33///
34/// This `struct` is created by the [`values`] method on [`OrderedSliceMap`]. See its
35/// documentation for more.
36///
37/// [`values`]: OrderedSliceMap::values
38pub type Values<'a, K, V> = internal::Values<'a, K, V>;
39
40/// A cursor over a `OrderedSliceMap`.
41///
42/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
43///
44/// Cursors always point to a gap between two elements in the map, and can
45/// operate on the two immediately adjacent elements.
46///
47/// A `Cursor` is created with the [`OrderedSliceMap::lower_bound`] and [`OrderedSliceMap::upper_bound`] methods.
48pub type Cursor<'a, K, V> = internal::Cursor<'a, K, V>;
49
50#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
51/// An ordered map based on an ordered slice.
52/// This structures provides a subset of the methods offered by the standard library's
53/// `BTreeMap`.
54///
55/// # Examples
56///
57/// ```
58/// use static_mapset::OrderedSliceMap;
59///
60/// let movie_reviews_data = [
61/// ("Office Space", "Deals with real issues in the workplace."),
62/// ("Pulp Fiction", "Masterpiece."),
63/// ("The Godfather", "Very enjoyable."),
64/// ("The Blues Brothers", "Eye lyked it a lot.")
65/// ];
66/// let movie_reviews = OrderedSliceMap::new_unchecked(&movie_reviews_data);
67///
68/// // check for a specific one.
69/// if !movie_reviews.contains_key("Les Misérables") {
70/// println!("We've got {} reviews, but Les Misérables ain't one.",
71/// movie_reviews.len());
72/// }
73///
74/// // look up the values associated with some keys.
75/// let to_find = ["Up!", "Office Space"];
76/// for movie in &to_find {
77/// match movie_reviews.get(movie) {
78/// Some(review) => println!("{movie}: {review}"),
79/// None => println!("{movie} is unreviewed.")
80/// }
81/// }
82///
83/// // Look up the value for a key (will panic if the key is not found).
84/// println!("Movie review: {}", movie_reviews[&"Office Space"]);
85///
86/// // iterate over everything.
87/// for (movie, review) in &movie_reviews {
88/// println!("{movie}: \"{review}\"");
89/// }
90/// ```
91pub struct OrderedSliceMap<'a, K, V> {
92 inner: &'a [(K, V)],
93 len: usize
94}
95
96impl<'a, K, V> Clone for OrderedSliceMap<'a, K, V> {
97 fn clone(&self) -> Self {
98 *self
99 }
100}
101
102impl<'a, K, V> Copy for OrderedSliceMap<'a, K, V> {}
103
104impl<'a, K, V> OrderedSliceMap<'a, K, V> {
105 /// Sorts the slice and creates an `OrderedSliceMap`.
106 /// Duplicate keys are removed, keeping the last occurrence.
107 ///
108 /// # Complexity
109 ///
110 /// Linearithmic in `self.len()`.
111 ///
112 /// # Examples
113 ///
114 /// ```
115 /// use static_mapset::OrderedSliceMap;
116 ///
117 /// let mut data = [(2, "b"), (1, "a")];
118 /// let map = OrderedSliceMap::new(&mut data);
119 /// assert_eq!(map.first_key_value(), Some((&1, &"a")));
120 /// ```
121 pub fn new(items: &'a mut [(K, V)]) -> Self
122 where
123 K: Ord
124 {
125 let len = order(items);
126 OrderedSliceMap { inner: items, len }
127 }
128
129 /// Creates an `OrderedSliceMap` from an immutable slice without sorting.
130 ///
131 /// The slice must be sorted in ascending order with no duplicate keys.
132 ///
133 /// # Complexity
134 ///
135 /// Constant.
136 ///
137 /// # Examples
138 ///
139 /// ```
140 /// use static_mapset::OrderedSliceMap;
141 ///
142 /// static MAP: OrderedSliceMap<i32, &str> = OrderedSliceMap::new_unchecked(&[(1, "a"), (2, "b")]);
143 /// assert_eq!(MAP.get(&2), Some(&"b"));
144 ///
145 /// // Incorrect key order or duplicates cause undefined behavior:
146 /// // let map = OrderedSliceMap::new_unchecked(&[(2, "a"), (1, "b")]);
147 /// // let map = OrderedSliceMap::new_unchecked(&[(1, "a"), (1, "b")]);
148 /// ```
149 pub const fn new_unchecked(ordered_items: &'a [(K, V)]) -> Self {
150 OrderedSliceMap {
151 inner: ordered_items,
152 len: ordered_items.len()
153 }
154 }
155
156 /// Returns `true` if the map is ordered correctly.
157 ///
158 /// # Complexity
159 ///
160 /// Linear in `self.len()`.
161 ///
162 /// # Examples
163 ///
164 /// ```
165 /// use static_mapset::OrderedSliceMap;
166 ///
167 /// let map = OrderedSliceMap::new_unchecked(&[(1, "a"), (2, "b"), (3, "b")]);
168 /// assert!(map.is_valid());
169 ///
170 /// let map = OrderedSliceMap::new_unchecked(&[(1, "a"), (2, "b"), (2, "c")]);
171 /// assert!(!map.is_valid());
172 /// let map = OrderedSliceMap::new_unchecked(&[(1.0, "a"), (2.0, "b"), (f64::NAN, "c")]);
173 /// assert!(!map.is_valid());
174 /// ```
175 pub fn is_valid(&self) -> bool
176 where
177 K: PartialOrd
178 {
179 internal::is_valid(&self.inner[..self.len])
180 }
181
182 /// Returns `true` if the map contains a value for the specified key.
183 ///
184 /// The key may be any borrowed form of the map's key type, but the ordering
185 /// on the borrowed form *must* match the ordering on the key type.
186 /// If equal keys are present, this returns `true` if any matching key exists.
187 ///
188 /// # Complexity
189 ///
190 /// Logarithmic in `self.len()`.
191 ///
192 /// # Examples
193 ///
194 /// ```
195 /// use static_mapset::OrderedSliceMap;
196 ///
197 /// let data = [(1, "a")];
198 /// let map = OrderedSliceMap::new_unchecked(&data);
199 /// assert_eq!(map.contains_key(&1), true);
200 /// assert_eq!(map.contains_key(&2), false);
201 ///
202 /// let data = [(1.0, "a"), (2.0, "b")];
203 /// let map = OrderedSliceMap::new_unchecked(&data);
204 /// // f64::NAN is incomparable, so key lookups by NaN never match.
205 /// assert_eq!(map.contains_key(&f64::NAN), false);
206 /// ```
207 pub fn contains_key<Q>(&self, key: &Q) -> bool
208 where
209 K: Borrow<Q>,
210 Q: PartialOrd + ?Sized
211 {
212 internal::contains_key(&self.inner[..self.len], key)
213 }
214
215 /// Returns the first key-value pair in the map.
216 /// The key in this pair is the minimum key in the map.
217 ///
218 /// # Complexity
219 ///
220 /// Constant.
221 ///
222 /// # Examples
223 ///
224 /// ```
225 /// use static_mapset::OrderedSliceMap;
226 ///
227 /// let empty: &[(i32, &str)] = &[];
228 /// let map = OrderedSliceMap::new_unchecked(empty);
229 /// assert_eq!(map.first_key_value(), None);
230 ///
231 /// let data = [(1, "b"), (2, "a")];
232 /// let map = OrderedSliceMap::new_unchecked(&data);
233 /// assert_eq!(map.first_key_value(), Some((&1, &"b")));
234 /// ```
235 pub fn first_key_value(&self) -> Option<(&K, &V)> {
236 internal::first_key_value(&self.inner[..self.len])
237 }
238
239 /// Returns a reference to the value corresponding to the key.
240 ///
241 /// The key may be any borrowed form of the map's key type, but the ordering
242 /// on the borrowed form *must* match the ordering on the key type.
243 ///
244 /// # Complexity
245 ///
246 /// Logarithmic in `self.len()`.
247 ///
248 /// # Examples
249 ///
250 /// ```
251 /// use static_mapset::OrderedSliceMap;
252 ///
253 /// let data = [(1, "a")];
254 /// let map = OrderedSliceMap::new_unchecked(&data);
255 /// assert_eq!(map.get(&1), Some(&"a"));
256 /// assert_eq!(map.get(&2), None);
257 ///
258 /// let data = [(1.0, "a"), (2.0, "b")];
259 /// let map = OrderedSliceMap::new_unchecked(&data);
260 /// // f64::NAN is incomparable, so key lookups by NaN never match.
261 /// assert_eq!(map.get(&f64::NAN), None);
262 /// ```
263 pub fn get<Q>(&self, key: &Q) -> Option<&V>
264 where
265 K: Borrow<Q>,
266 Q: PartialOrd + ?Sized
267 {
268 internal::get(&self.inner[..self.len], key)
269 }
270
271 /// Returns the key-value pair corresponding to the supplied key.
272 ///
273 /// The supplied key may be any borrowed form of the map's key type, but the ordering
274 /// on the borrowed form *must* match the ordering on the key type.
275 /// If equal keys are present, the first matching entry in key order is returned.
276 ///
277 /// # Complexity
278 ///
279 /// Logarithmic in `self.len()`.
280 ///
281 /// # Examples
282 ///
283 /// ```
284 /// use std::cmp::Ordering;
285 /// use static_mapset::OrderedSliceMap;
286 ///
287 /// #[derive(Clone, Copy, Debug)]
288 /// struct S {
289 /// id: u32,
290 /// # #[allow(unused)] // prevents a "field `name` is never read" error
291 /// name: &'static str, // ignored by equality and ordering operations
292 /// }
293 ///
294 /// impl PartialEq for S {
295 /// fn eq(&self, other: &S) -> bool {
296 /// self.id == other.id
297 /// }
298 /// }
299 ///
300 /// impl Eq for S {}
301 ///
302 /// impl PartialOrd for S {
303 /// fn partial_cmp(&self, other: &S) -> Option<Ordering> {
304 /// self.id.partial_cmp(&other.id)
305 /// }
306 /// }
307 ///
308 /// impl Ord for S {
309 /// fn cmp(&self, other: &S) -> Ordering {
310 /// self.id.cmp(&other.id)
311 /// }
312 /// }
313 ///
314 /// let j_a = S { id: 1, name: "Jessica" };
315 /// let j_b = S { id: 1, name: "Jess" };
316 /// let p = S { id: 2, name: "Paul" };
317 /// assert_eq!(j_a, j_b);
318 ///
319 /// let data = [(j_a, "Paris")];
320 /// let map = OrderedSliceMap::new_unchecked(&data);
321 /// assert_eq!(map.get_key_value(&j_a), Some((&j_a, &"Paris")));
322 /// assert_eq!(map.get_key_value(&j_b), Some((&j_a, &"Paris"))); // the notable case
323 /// assert_eq!(map.get_key_value(&p), None);
324 ///
325 /// let data = [(1.0, "a"), (2.0, "b")];
326 /// let map = OrderedSliceMap::new_unchecked(&data);
327 /// // f64::NAN is incomparable, so key lookups by NaN never match.
328 /// assert_eq!(map.get_key_value(&f64::NAN), None);
329 /// ```
330 pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
331 where
332 K: Borrow<Q>,
333 Q: PartialOrd + ?Sized
334 {
335 internal::get_key_value(&self.inner[..self.len], key)
336 }
337
338 /// Returns `true` if the map contains no elements.
339 ///
340 /// # Complexity
341 ///
342 /// Constant.
343 ///
344 /// # Examples
345 ///
346 /// ```
347 /// use static_mapset::OrderedSliceMap;
348 ///
349 /// let map: OrderedSliceMap<i32, &str> = OrderedSliceMap::new_unchecked(&[]);
350 /// assert!(map.is_empty());
351 /// let map = OrderedSliceMap::new_unchecked(&[(1, "a")]);
352 /// assert!(!map.is_empty());
353 /// ```
354 pub const fn is_empty(&self) -> bool {
355 self.len == 0
356 }
357
358 /// Gets an iterator over the entries of the map, sorted by key.
359 ///
360 /// # Complexity
361 ///
362 /// Linear in `self.len()` to iterate all elements.
363 ///
364 /// # Examples
365 ///
366 /// ```
367 /// use static_mapset::OrderedSliceMap;
368 ///
369 /// let mut data = [(2, "b"), (1, "a")];
370 /// let map = OrderedSliceMap::new(&mut data);
371 ///
372 /// let (first_key, first_value) = map.iter().next().unwrap();
373 /// assert_eq!((*first_key, *first_value), (1, "a"));
374 /// ```
375 pub fn iter(&self) -> Iter<'_, K, V> {
376 internal::iter(&self.inner[..self.len])
377 }
378
379 /// Gets an iterator over the keys of the map, in sorted order.
380 ///
381 /// # Complexity
382 ///
383 /// Linear in `self.len()` to iterate all elements.
384 ///
385 /// # Examples
386 ///
387 /// ```
388 /// use static_mapset::OrderedSliceMap;
389 ///
390 /// let mut data = [(2, "b"), (1, "a")];
391 /// let map = OrderedSliceMap::new(&mut data);
392 ///
393 /// let keys: Vec<_> = map.keys().cloned().collect();
394 /// assert_eq!(keys, [1, 2]);
395 /// ```
396 pub fn keys(&self) -> Keys<'_, K, V> {
397 internal::keys(&self.inner[..self.len])
398 }
399
400 /// Returns the last key-value pair in the map.
401 /// The key in this pair is the maximum key in the map.
402 ///
403 /// # Complexity
404 ///
405 /// Constant.
406 ///
407 /// # Examples
408 ///
409 /// ```
410 /// use static_mapset::OrderedSliceMap;
411 ///
412 /// let data = [(1, "b"), (2, "a")];
413 /// let map = OrderedSliceMap::new_unchecked(&data);
414 /// assert_eq!(map.last_key_value(), Some((&2, &"a")));
415 /// ```
416 pub fn last_key_value(&self) -> Option<(&K, &V)> {
417 internal::last_key_value(&self.inner[..self.len])
418 }
419
420 /// Returns the number of elements in the map.
421 ///
422 /// # Complexity
423 ///
424 /// Constant.
425 pub const fn len(&self) -> usize {
426 self.len
427 }
428
429 /// Returns a [`Cursor`] pointing at the gap before the smallest key
430 /// greater than the given bound.
431 ///
432 /// Passing `Bound::Included(x)` will return a cursor pointing to the
433 /// gap before the smallest key greater than or equal to `x`.
434 ///
435 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
436 /// gap before the smallest key greater than `x`.
437 ///
438 /// Passing `Bound::Unbounded` will return a cursor pointing to the
439 /// gap before the smallest key in the map.
440 /// With equal keys, `Included` points before the first equal key and `Excluded` points after the last equal key.
441 ///
442 /// # Complexity
443 ///
444 /// Logarithmic in `self.len()` to find the bounds, and linear in the number of yielded elements to iterate them all.
445 ///
446 /// # Examples
447 ///
448 /// ```
449 /// use static_mapset::OrderedSliceMap;
450 /// use std::ops::Bound;
451 ///
452 /// let data = [
453 /// (1, "a"),
454 /// (2, "b"),
455 /// (3, "c"),
456 /// (4, "d"),
457 /// ];
458 /// let map = OrderedSliceMap::new_unchecked(&data);
459 ///
460 /// let cursor = map.lower_bound(Bound::Included(&2));
461 /// assert_eq!(cursor.peek_prev(), Some((&1, &"a")));
462 /// assert_eq!(cursor.peek_next(), Some((&2, &"b")));
463 ///
464 /// let cursor = map.lower_bound(Bound::Excluded(&2));
465 /// assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
466 /// assert_eq!(cursor.peek_next(), Some((&3, &"c")));
467 ///
468 /// let cursor = map.lower_bound(Bound::Unbounded);
469 /// assert_eq!(cursor.peek_prev(), None);
470 /// assert_eq!(cursor.peek_next(), Some((&1, &"a")));
471 ///
472 /// let data = [(1.0, "a"), (2.0, "b")];
473 /// let map = OrderedSliceMap::new_unchecked(&data);
474 /// // f64::NAN is incomparable, so the cursor points to the gap after the last key.
475 /// let cursor = map.lower_bound(Bound::Included(&f64::NAN));
476 /// assert_eq!(cursor.peek_prev(), Some((&2.0, &"b")));
477 /// ```
478 pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
479 where
480 K: Borrow<Q>,
481 Q: PartialOrd + ?Sized
482 {
483 internal::lower_bound(&self.inner[..self.len], bound)
484 }
485
486 /// Constructs a double-ended iterator over a sub-range of elements in the map.
487 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
488 /// yield elements from min (inclusive) to max (exclusive).
489 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
490 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
491 /// range from 4 to 10.
492 ///
493 /// # Panics
494 ///
495 /// Panics if range `start > end`.
496 /// Panics if range `start == end` and both bounds are `Excluded`.
497 /// Panics if `start` (or `end`() is incomparable and `end` (or `start`) is bounded.
498 ///
499 /// # Complexity
500 ///
501 /// Logarithmic in `self.len()`.
502 ///
503 /// # Examples
504 ///
505 /// ```
506 /// use static_mapset::OrderedSliceMap;
507 /// use std::ops::Bound::Included;
508 ///
509 /// let data = [
510 /// (3, "a"),
511 /// (5, "b"),
512 /// (8, "c"),
513 /// ];
514 /// let map = OrderedSliceMap::new_unchecked(&data);
515 /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
516 /// println!("{key}: {value}");
517 /// }
518 /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
519 /// ```
520 pub fn range<Q, R>(&self, range: R) -> Range<'_, K, V>
521 where
522 K: Borrow<Q>,
523 Q: PartialOrd + ?Sized,
524 R: RangeBounds<Q>
525 {
526 internal::range(&self.inner[..self.len], range)
527 }
528
529 /// Returns a [`Cursor`] pointing at the gap after the greatest key
530 /// smaller than the given bound.
531 ///
532 /// Passing `Bound::Included(x)` will return a cursor pointing to the
533 /// gap after the greatest key smaller than or equal to `x`.
534 ///
535 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
536 /// gap after the greatest key smaller than `x`.
537 ///
538 /// Passing `Bound::Unbounded` will return a cursor pointing to the
539 /// gap after the greatest key in the map.
540 /// With equal keys, `Excluded` points before the first equal key and `Included` points after the last equal key.
541 ///
542 /// # Complexity
543 ///
544 /// Logarithmic in `self.len()`.
545 ///
546 /// # Examples
547 ///
548 /// ```
549 ///
550 /// use static_mapset::OrderedSliceMap;
551 /// use std::ops::Bound;
552 ///
553 /// let data = [
554 /// (1, "a"),
555 /// (2, "b"),
556 /// (3, "c"),
557 /// (4, "d"),
558 /// ];
559 /// let map = OrderedSliceMap::new_unchecked(&data);
560 ///
561 /// let cursor = map.upper_bound(Bound::Included(&3));
562 /// assert_eq!(cursor.peek_prev(), Some((&3, &"c")));
563 /// assert_eq!(cursor.peek_next(), Some((&4, &"d")));
564 ///
565 /// let cursor = map.upper_bound(Bound::Excluded(&3));
566 /// assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
567 /// assert_eq!(cursor.peek_next(), Some((&3, &"c")));
568 ///
569 /// let cursor = map.upper_bound(Bound::Unbounded);
570 /// assert_eq!(cursor.peek_prev(), Some((&4, &"d")));
571 /// assert_eq!(cursor.peek_next(), None);
572 ///
573 /// let data = [(1.0, "a"), (2.0, "b")];
574 /// let map = OrderedSliceMap::new_unchecked(&data);
575 /// // f64::NAN is incomparable, so the cursor points to the gap after the last key.
576 /// let cursor = map.upper_bound(Bound::Included(&f64::NAN));
577 /// assert_eq!(cursor.peek_prev(), Some((&2.0, &"b")));
578 /// ```
579 pub fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
580 where
581 K: Borrow<Q>,
582 Q: PartialOrd + ?Sized
583 {
584 internal::upper_bound(&self.inner[..self.len], bound)
585 }
586
587 /// Gets an iterator over the values of the map, in order by key.
588 ///
589 /// # Complexity
590 ///
591 /// Linear in `self.len()` to iterate all elements.
592 ///
593 /// # Examples
594 ///
595 /// ```
596 /// use static_mapset::OrderedSliceMap;
597 ///
598 /// let mut data = [(2, "b"), (1, "a")];
599 /// let map = OrderedSliceMap::new(&mut data);
600 ///
601 /// let values: Vec<_> = map.values().cloned().collect();
602 /// assert_eq!(values, ["a", "b"]);
603 /// ```
604 pub fn values(&self) -> Values<'_, K, V> {
605 internal::values(&self.inner[..self.len])
606 }
607}
608
609impl<'a, K, V> IntoIterator for &'a OrderedSliceMap<'a, K, V> {
610 type Item = (&'a K, &'a V);
611 type IntoIter = Iter<'a, K, V>;
612
613 fn into_iter(self) -> Self::IntoIter {
614 self.iter()
615 }
616}
617
618impl<'a, K, V, Q> Index<&Q> for OrderedSliceMap<'a, K, V>
619where
620 K: Borrow<Q>,
621 Q: Ord
622{
623 type Output = V;
624
625 fn index(&self, key: &Q) -> &Self::Output {
626 self.get(key).expect("no entry found for key")
627 }
628}
629
630#[cfg(test)]
631mod tests {
632 use core::ops::Bound;
633
634 use super::*;
635
636 #[test]
637 fn test_get() {
638 let data = [(1, 'a'), (3, 'c'), (5, 'e')];
639 let map = OrderedSliceMap::new_unchecked(&data);
640 assert_eq!(map.get(&0), None);
641 assert_eq!(map.get(&1), Some(&'a'));
642 assert_eq!(map.get(&2), None);
643 assert_eq!(map.get(&3), Some(&'c'));
644 assert_eq!(map.get(&5), Some(&'e'));
645 assert_eq!(map.get(&6), None);
646 }
647
648 #[test]
649 fn test_contains_key() {
650 let data = [(2, 4), (4, 16), (6, 36)];
651 let map = OrderedSliceMap::new_unchecked(&data);
652 assert!(map.contains_key(&2));
653 assert!(map.contains_key(&4));
654 assert!(!map.contains_key(&3));
655 assert!(!map.contains_key(&7));
656 }
657
658 #[test]
659 fn test_first_last() {
660 let data = [(1, 1), (2, 4), (3, 9)];
661 let map = OrderedSliceMap::new_unchecked(&data);
662 assert_eq!(map.first_key_value(), Some((&1, &1)));
663 assert_eq!(map.last_key_value(), Some((&3, &9)));
664
665 let empty: &[(i32, i32)] = &[];
666 let empty_map = OrderedSliceMap::new_unchecked(empty);
667 assert_eq!(empty_map.first_key_value(), None);
668 assert_eq!(empty_map.last_key_value(), None);
669 }
670
671 #[test]
672 fn test_iter() {
673 let data = [(1, 'a'), (2, 'b'), (3, 'c')];
674 let map = OrderedSliceMap::new_unchecked(&data);
675 let collected: Vec<_> = map.iter().collect();
676 assert_eq!(collected, vec![(&1, &'a'), (&2, &'b'), (&3, &'c')]);
677 }
678
679 #[test]
680 fn test_into_iter_for_ref() {
681 let data = [(10, 100), (20, 200)];
682 let map = OrderedSliceMap::new_unchecked(&data);
683 let collected: Vec<_> = (&map).into_iter().collect();
684 assert_eq!(collected, vec![(&10, &100), (&20, &200)]);
685 }
686
687 #[test]
688 fn test_index() {
689 let data = [(5, 50), (10, 100)];
690 let map = OrderedSliceMap::new_unchecked(&data);
691 assert_eq!(map[&5], 50);
692 assert_eq!(map[&10], 100);
693 }
694
695 #[test]
696 fn test_lower_bound() {
697 let data = [(1, 1), (3, 9), (5, 25)];
698 let map = OrderedSliceMap::new_unchecked(&data);
699 assert_eq!(map.lower_bound(Bound::Included(&2)).next(), Some((&3, &9)));
700 assert_eq!(map.lower_bound(Bound::Excluded(&3)).next(), Some((&5, &25)));
701 assert_eq!(map.lower_bound(Bound::Unbounded).next(), Some((&1, &1)));
702 assert_eq!(map.lower_bound(Bound::Included(&6)).next(), None);
703 }
704
705 #[test]
706 fn test_upper_bound() {
707 let data = [(1, 1), (3, 9), (5, 25)];
708 let map = OrderedSliceMap::new_unchecked(&data);
709 assert_eq!(map.upper_bound(Bound::Included(&3)).next(), Some((&5, &25)));
710 assert_eq!(map.upper_bound(Bound::Excluded(&3)).next(), Some((&3, &9)));
711 assert_eq!(map.upper_bound(Bound::Unbounded).next(), None);
712 }
713
714 #[test]
715 fn test_is_valid() {
716 let sorted = [(1, 1), (2, 4), (3, 9)];
717 assert!(OrderedSliceMap::new_unchecked(&sorted).keys().is_sorted());
718 let unsorted = [(3, 9), (1, 1)];
719 assert!(!OrderedSliceMap::new_unchecked(&unsorted).keys().is_sorted());
720 }
721}