Skip to main content

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}