1 | // This file is part of ICU4X. For terms of use, please see the file |
2 | // called LICENSE at the top level of the ICU4X source tree |
3 | // (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). |
4 | |
5 | use crate::store::*; |
6 | use alloc::borrow::Borrow; |
7 | use alloc::boxed::Box; |
8 | use alloc::vec::Vec; |
9 | use core::cmp::Ordering; |
10 | use core::iter::FromIterator; |
11 | use core::marker::PhantomData; |
12 | use core::mem; |
13 | use core::ops::{Index, IndexMut, Range}; |
14 | |
15 | /// A simple "flat" map based on a sorted vector |
16 | /// |
17 | /// See the [module level documentation][super] for why one should use this. |
18 | /// |
19 | /// The API is roughly similar to that of [`std::collections::BTreeMap`]. |
20 | #[derive (Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)] |
21 | #[cfg_attr (feature = "yoke" , derive(yoke::Yokeable))] |
22 | pub struct LiteMap<K: ?Sized, V: ?Sized, S = alloc::vec::Vec<(K, V)>> { |
23 | pub(crate) values: S, |
24 | pub(crate) _key_type: PhantomData<K>, |
25 | pub(crate) _value_type: PhantomData<V>, |
26 | } |
27 | |
28 | impl<K, V> LiteMap<K, V> { |
29 | /// Construct a new [`LiteMap`] backed by Vec |
30 | pub const fn new_vec() -> Self { |
31 | Self { |
32 | values: alloc::vec::Vec::new(), |
33 | _key_type: PhantomData, |
34 | _value_type: PhantomData, |
35 | } |
36 | } |
37 | } |
38 | |
39 | impl<K, V, S> LiteMap<K, V, S> { |
40 | /// Construct a new [`LiteMap`] using the given values |
41 | /// |
42 | /// The store must be sorted and have no duplicate keys. |
43 | pub const fn from_sorted_store_unchecked(values: S) -> Self { |
44 | Self { |
45 | values, |
46 | _key_type: PhantomData, |
47 | _value_type: PhantomData, |
48 | } |
49 | } |
50 | } |
51 | |
52 | impl<K, V> LiteMap<K, V, Vec<(K, V)>> { |
53 | /// Convert a [`LiteMap`] into a sorted `Vec<(K, V)>`. |
54 | #[inline ] |
55 | pub fn into_tuple_vec(self) -> Vec<(K, V)> { |
56 | self.values |
57 | } |
58 | } |
59 | |
60 | impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> |
61 | where |
62 | S: StoreConstEmpty<K, V>, |
63 | { |
64 | /// Create a new empty [`LiteMap`] |
65 | pub const fn new() -> Self { |
66 | Self { |
67 | values: S::EMPTY, |
68 | _key_type: PhantomData, |
69 | _value_type: PhantomData, |
70 | } |
71 | } |
72 | } |
73 | |
74 | impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> |
75 | where |
76 | S: Store<K, V>, |
77 | { |
78 | /// The number of elements in the [`LiteMap`] |
79 | pub fn len(&self) -> usize { |
80 | self.values.lm_len() |
81 | } |
82 | |
83 | /// Whether the [`LiteMap`] is empty |
84 | pub fn is_empty(&self) -> bool { |
85 | self.values.lm_is_empty() |
86 | } |
87 | |
88 | /// Get the key-value pair residing at a particular index |
89 | /// |
90 | /// In most cases, prefer [`LiteMap::get()`] over this method. |
91 | #[inline ] |
92 | pub fn get_indexed(&self, index: usize) -> Option<(&K, &V)> { |
93 | self.values.lm_get(index) |
94 | } |
95 | |
96 | /// Get the lowest-rank key/value pair from the `LiteMap`, if it exists. |
97 | /// |
98 | /// # Examples |
99 | /// |
100 | /// ```rust |
101 | /// use litemap::LiteMap; |
102 | /// |
103 | /// let mut map = |
104 | /// LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno" ), (3, "tres" )]); |
105 | /// |
106 | /// assert_eq!(map.first(), Some((&1, &"uno" ))); |
107 | /// ``` |
108 | #[inline ] |
109 | pub fn first(&self) -> Option<(&K, &V)> { |
110 | self.values.lm_get(0).map(|(k, v)| (k, v)) |
111 | } |
112 | |
113 | /// Get the highest-rank key/value pair from the `LiteMap`, if it exists. |
114 | /// |
115 | /// # Examples |
116 | /// |
117 | /// ```rust |
118 | /// use litemap::LiteMap; |
119 | /// |
120 | /// let mut map = |
121 | /// LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno" ), (3, "tres" )]); |
122 | /// |
123 | /// assert_eq!(map.last(), Some((&3, &"tres" ))); |
124 | /// ``` |
125 | #[inline ] |
126 | pub fn last(&self) -> Option<(&K, &V)> { |
127 | self.values.lm_get(self.len() - 1).map(|(k, v)| (k, v)) |
128 | } |
129 | |
130 | /// Returns a new [`LiteMap`] with owned keys and values. |
131 | /// |
132 | /// The trait bounds allow transforming most slice and string types. |
133 | /// |
134 | /// # Examples |
135 | /// |
136 | /// ``` |
137 | /// use litemap::LiteMap; |
138 | /// |
139 | /// let mut map: LiteMap<&str, &str> = LiteMap::new_vec(); |
140 | /// map.insert("one" , "uno" ); |
141 | /// map.insert("two" , "dos" ); |
142 | /// |
143 | /// let boxed_map: LiteMap<Box<str>, Box<str>> = map.to_boxed_keys_values(); |
144 | /// |
145 | /// assert_eq!(boxed_map.get("one" ), Some(&Box::from("uno" ))); |
146 | /// ``` |
147 | pub fn to_boxed_keys_values<KB: ?Sized, VB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, Box<VB>, SB> |
148 | where |
149 | SB: StoreMut<Box<KB>, Box<VB>>, |
150 | K: Borrow<KB>, |
151 | V: Borrow<VB>, |
152 | Box<KB>: for<'a> From<&'a KB>, |
153 | Box<VB>: for<'a> From<&'a VB>, |
154 | { |
155 | let mut values = SB::lm_with_capacity(self.len()); |
156 | for i in 0..self.len() { |
157 | #[allow (clippy::unwrap_used)] // iterating over our own length |
158 | let (k, v) = self.values.lm_get(i).unwrap(); |
159 | values.lm_push(Box::from(k.borrow()), Box::from(v.borrow())) |
160 | } |
161 | LiteMap { |
162 | values, |
163 | _key_type: PhantomData, |
164 | _value_type: PhantomData, |
165 | } |
166 | } |
167 | |
168 | /// Returns a new [`LiteMap`] with owned keys and cloned values. |
169 | /// |
170 | /// The trait bounds allow transforming most slice and string types. |
171 | /// |
172 | /// # Examples |
173 | /// |
174 | /// ``` |
175 | /// use litemap::LiteMap; |
176 | /// |
177 | /// let mut map: LiteMap<&str, usize> = LiteMap::new_vec(); |
178 | /// map.insert("one" , 11); |
179 | /// map.insert("two" , 22); |
180 | /// |
181 | /// let boxed_map: LiteMap<Box<str>, usize> = map.to_boxed_keys(); |
182 | /// |
183 | /// assert_eq!(boxed_map.get("one" ), Some(&11)); |
184 | /// ``` |
185 | pub fn to_boxed_keys<KB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, V, SB> |
186 | where |
187 | V: Clone, |
188 | SB: StoreMut<Box<KB>, V>, |
189 | K: Borrow<KB>, |
190 | Box<KB>: for<'a> From<&'a KB>, |
191 | { |
192 | let mut values = SB::lm_with_capacity(self.len()); |
193 | for i in 0..self.len() { |
194 | #[allow (clippy::unwrap_used)] // iterating over our own length |
195 | let (k, v) = self.values.lm_get(i).unwrap(); |
196 | values.lm_push(Box::from(k.borrow()), v.clone()) |
197 | } |
198 | LiteMap { |
199 | values, |
200 | _key_type: PhantomData, |
201 | _value_type: PhantomData, |
202 | } |
203 | } |
204 | |
205 | /// Returns a new [`LiteMap`] with cloned keys and owned values. |
206 | /// |
207 | /// The trait bounds allow transforming most slice and string types. |
208 | /// |
209 | /// # Examples |
210 | /// |
211 | /// ``` |
212 | /// use litemap::LiteMap; |
213 | /// |
214 | /// let mut map: LiteMap<usize, &str> = LiteMap::new_vec(); |
215 | /// map.insert(11, "uno" ); |
216 | /// map.insert(22, "dos" ); |
217 | /// |
218 | /// let boxed_map: LiteMap<usize, Box<str>> = map.to_boxed_values(); |
219 | /// |
220 | /// assert_eq!(boxed_map.get(&11), Some(&Box::from("uno" ))); |
221 | /// ``` |
222 | pub fn to_boxed_values<VB: ?Sized, SB>(&self) -> LiteMap<K, Box<VB>, SB> |
223 | where |
224 | K: Clone, |
225 | SB: StoreMut<K, Box<VB>>, |
226 | V: Borrow<VB>, |
227 | Box<VB>: for<'a> From<&'a VB>, |
228 | { |
229 | let mut values = SB::lm_with_capacity(self.len()); |
230 | for i in 0..self.len() { |
231 | #[allow (clippy::unwrap_used)] // iterating over our own length |
232 | let (k, v) = self.values.lm_get(i).unwrap(); |
233 | values.lm_push(k.clone(), Box::from(v.borrow())) |
234 | } |
235 | LiteMap { |
236 | values, |
237 | _key_type: PhantomData, |
238 | _value_type: PhantomData, |
239 | } |
240 | } |
241 | } |
242 | |
243 | impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> |
244 | where |
245 | K: Ord, |
246 | S: Store<K, V>, |
247 | { |
248 | /// Get the value associated with `key`, if it exists. |
249 | /// |
250 | /// ```rust |
251 | /// use litemap::LiteMap; |
252 | /// |
253 | /// let mut map = LiteMap::new_vec(); |
254 | /// map.insert(1, "one" ); |
255 | /// map.insert(2, "two" ); |
256 | /// assert_eq!(map.get(&1), Some(&"one" )); |
257 | /// assert_eq!(map.get(&3), None); |
258 | /// ``` |
259 | pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> |
260 | where |
261 | K: Borrow<Q>, |
262 | Q: Ord, |
263 | { |
264 | match self.find_index(key) { |
265 | #[allow (clippy::unwrap_used)] // find_index returns a valid index |
266 | Ok(found) => Some(self.values.lm_get(found).unwrap().1), |
267 | Err(_) => None, |
268 | } |
269 | } |
270 | |
271 | /// Binary search the map with `predicate` to find a key, returning the value. |
272 | pub fn get_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<&V> { |
273 | let index = self.values.lm_binary_search_by(predicate).ok()?; |
274 | self.values.lm_get(index).map(|(_, v)| v) |
275 | } |
276 | |
277 | /// Returns whether `key` is contained in this map |
278 | /// |
279 | /// ```rust |
280 | /// use litemap::LiteMap; |
281 | /// |
282 | /// let mut map = LiteMap::new_vec(); |
283 | /// map.insert(1, "one" ); |
284 | /// map.insert(2, "two" ); |
285 | /// assert!(map.contains_key(&1)); |
286 | /// assert!(!map.contains_key(&3)); |
287 | /// ``` |
288 | pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool |
289 | where |
290 | K: Borrow<Q>, |
291 | Q: Ord, |
292 | { |
293 | self.find_index(key).is_ok() |
294 | } |
295 | |
296 | /// Obtain the index for a given key, or if the key is not found, the index |
297 | /// at which it would be inserted. |
298 | /// |
299 | /// (The return value works equivalently to [`slice::binary_search_by()`]) |
300 | /// |
301 | /// The indices returned can be used with [`Self::get_indexed()`]. Prefer using |
302 | /// [`Self::get()`] directly where possible. |
303 | #[inline ] |
304 | pub fn find_index<Q: ?Sized>(&self, key: &Q) -> Result<usize, usize> |
305 | where |
306 | K: Borrow<Q>, |
307 | Q: Ord, |
308 | { |
309 | self.values.lm_binary_search_by(|k| k.borrow().cmp(key)) |
310 | } |
311 | } |
312 | |
313 | impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> |
314 | where |
315 | S: StoreSlice<K, V>, |
316 | { |
317 | /// Creates a new [`LiteMap`] from a range of the current [`LiteMap`]. |
318 | /// |
319 | /// # Examples |
320 | /// |
321 | /// ``` |
322 | /// use litemap::LiteMap; |
323 | /// |
324 | /// let mut map = LiteMap::new_vec(); |
325 | /// map.insert(1, "one" ); |
326 | /// map.insert(2, "two" ); |
327 | /// map.insert(3, "three" ); |
328 | /// |
329 | /// let mut sub_map = map.get_indexed_range(1..3).expect("valid range" ); |
330 | /// assert_eq!(sub_map.get(&1), None); |
331 | /// assert_eq!(sub_map.get(&2), Some(&"two" )); |
332 | /// assert_eq!(sub_map.get(&3), Some(&"three" )); |
333 | /// ``` |
334 | pub fn get_indexed_range(&self, range: Range<usize>) -> Option<LiteMap<K, V, &S::Slice>> { |
335 | let subslice = self.values.lm_get_range(range)?; |
336 | Some(LiteMap { |
337 | values: subslice, |
338 | _key_type: PhantomData, |
339 | _value_type: PhantomData, |
340 | }) |
341 | } |
342 | |
343 | /// Borrows this [`LiteMap`] as one of its slice type. |
344 | /// |
345 | /// This can be useful in situations where you need a `LiteMap` by value but do not want |
346 | /// to clone the owned version. |
347 | /// |
348 | /// # Examples |
349 | /// |
350 | /// ``` |
351 | /// use litemap::LiteMap; |
352 | /// |
353 | /// let mut map = LiteMap::new_vec(); |
354 | /// map.insert(1, "one" ); |
355 | /// map.insert(2, "two" ); |
356 | /// |
357 | /// let borrowed_map = map.as_sliced(); |
358 | /// assert_eq!(borrowed_map.get(&1), Some(&"one" )); |
359 | /// assert_eq!(borrowed_map.get(&2), Some(&"two" )); |
360 | /// ``` |
361 | pub fn as_sliced(&self) -> LiteMap<K, V, &S::Slice> { |
362 | // Won't panic: 0..self.len() is within range |
363 | #[allow (clippy::unwrap_used)] |
364 | let subslice = self.values.lm_get_range(0..self.len()).unwrap(); |
365 | LiteMap { |
366 | values: subslice, |
367 | _key_type: PhantomData, |
368 | _value_type: PhantomData, |
369 | } |
370 | } |
371 | |
372 | /// Borrows the backing buffer of this [`LiteMap`] as its slice type. |
373 | /// |
374 | /// The slice will be sorted. |
375 | /// |
376 | /// # Examples |
377 | /// |
378 | /// ``` |
379 | /// use litemap::LiteMap; |
380 | /// |
381 | /// let mut map = LiteMap::new_vec(); |
382 | /// map.insert(1, "one" ); |
383 | /// map.insert(2, "two" ); |
384 | /// |
385 | /// let slice = map.as_slice(); |
386 | /// assert_eq!(slice, &[(1, "one" ), (2, "two" )]); |
387 | /// ``` |
388 | pub fn as_slice(&self) -> &S::Slice { |
389 | // Won't panic: 0..self.len() is within range |
390 | #[allow (clippy::unwrap_used)] |
391 | self.values.lm_get_range(0..self.len()).unwrap() |
392 | } |
393 | } |
394 | |
395 | impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> |
396 | where |
397 | S: Store<K, V>, |
398 | { |
399 | /// Returns a new [`LiteMap`] with keys and values borrowed from this one. |
400 | /// |
401 | /// # Examples |
402 | /// |
403 | /// ``` |
404 | /// use litemap::LiteMap; |
405 | /// |
406 | /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec(); |
407 | /// map.insert(Box::new(1), "one" .to_string()); |
408 | /// map.insert(Box::new(2), "two" .to_string()); |
409 | /// |
410 | /// let borrowed_map: LiteMap<&usize, &str> = map.to_borrowed_keys_values(); |
411 | /// |
412 | /// assert_eq!(borrowed_map.get(&1), Some(&"one" )); |
413 | /// ``` |
414 | pub fn to_borrowed_keys_values<KB: ?Sized, VB: ?Sized, SB>( |
415 | &'a self, |
416 | ) -> LiteMap<&'a KB, &'a VB, SB> |
417 | where |
418 | K: Borrow<KB>, |
419 | V: Borrow<VB>, |
420 | SB: StoreMut<&'a KB, &'a VB>, |
421 | { |
422 | let mut values = SB::lm_with_capacity(self.len()); |
423 | for i in 0..self.len() { |
424 | #[allow (clippy::unwrap_used)] // iterating over our own length |
425 | let (k, v) = self.values.lm_get(i).unwrap(); |
426 | values.lm_push(k.borrow(), v.borrow()) |
427 | } |
428 | LiteMap { |
429 | values, |
430 | _key_type: PhantomData, |
431 | _value_type: PhantomData, |
432 | } |
433 | } |
434 | |
435 | /// Returns a new [`LiteMap`] with keys borrowed from this one and cloned values. |
436 | /// |
437 | /// # Examples |
438 | /// |
439 | /// ``` |
440 | /// use litemap::LiteMap; |
441 | /// |
442 | /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec(); |
443 | /// map.insert(Box::new(1), "one" .to_string()); |
444 | /// map.insert(Box::new(2), "two" .to_string()); |
445 | /// |
446 | /// let borrowed_map: LiteMap<&usize, String> = map.to_borrowed_keys(); |
447 | /// |
448 | /// assert_eq!(borrowed_map.get(&1), Some(&"one" .to_string())); |
449 | /// ``` |
450 | pub fn to_borrowed_keys<KB: ?Sized, SB>(&'a self) -> LiteMap<&'a KB, V, SB> |
451 | where |
452 | K: Borrow<KB>, |
453 | V: Clone, |
454 | SB: StoreMut<&'a KB, V>, |
455 | { |
456 | let mut values = SB::lm_with_capacity(self.len()); |
457 | for i in 0..self.len() { |
458 | #[allow (clippy::unwrap_used)] // iterating over our own length |
459 | let (k, v) = self.values.lm_get(i).unwrap(); |
460 | values.lm_push(k.borrow(), v.clone()) |
461 | } |
462 | LiteMap { |
463 | values, |
464 | _key_type: PhantomData, |
465 | _value_type: PhantomData, |
466 | } |
467 | } |
468 | |
469 | /// Returns a new [`LiteMap`] with values borrowed from this one and cloned keys. |
470 | /// |
471 | /// # Examples |
472 | /// |
473 | /// ``` |
474 | /// use litemap::LiteMap; |
475 | /// |
476 | /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec(); |
477 | /// map.insert(Box::new(1), "one" .to_string()); |
478 | /// map.insert(Box::new(2), "two" .to_string()); |
479 | /// |
480 | /// let borrowed_map: LiteMap<Box<usize>, &str> = map.to_borrowed_values(); |
481 | /// |
482 | /// assert_eq!(borrowed_map.get(&1), Some(&"one" )); |
483 | /// ``` |
484 | pub fn to_borrowed_values<VB: ?Sized, SB>(&'a self) -> LiteMap<K, &'a VB, SB> |
485 | where |
486 | K: Clone, |
487 | V: Borrow<VB>, |
488 | SB: StoreMut<K, &'a VB>, |
489 | { |
490 | let mut values = SB::lm_with_capacity(self.len()); |
491 | for i in 0..self.len() { |
492 | #[allow (clippy::unwrap_used)] // iterating over our own length |
493 | let (k, v) = self.values.lm_get(i).unwrap(); |
494 | values.lm_push(k.clone(), v.borrow()) |
495 | } |
496 | LiteMap { |
497 | values, |
498 | _key_type: PhantomData, |
499 | _value_type: PhantomData, |
500 | } |
501 | } |
502 | } |
503 | |
504 | impl<K, V, S> LiteMap<K, V, S> |
505 | where |
506 | S: StoreMut<K, V>, |
507 | { |
508 | /// Construct a new [`LiteMap`] with a given capacity |
509 | pub fn with_capacity(capacity: usize) -> Self { |
510 | Self { |
511 | values: S::lm_with_capacity(capacity), |
512 | _key_type: PhantomData, |
513 | _value_type: PhantomData, |
514 | } |
515 | } |
516 | |
517 | /// Remove all elements from the [`LiteMap`] |
518 | pub fn clear(&mut self) { |
519 | self.values.lm_clear() |
520 | } |
521 | |
522 | /// Reserve capacity for `additional` more elements to be inserted into |
523 | /// the [`LiteMap`] to avoid frequent reallocations. |
524 | /// |
525 | /// See [`Vec::reserve()`] for more information. |
526 | /// |
527 | /// [`Vec::reserve()`]: alloc::vec::Vec::reserve |
528 | pub fn reserve(&mut self, additional: usize) { |
529 | self.values.lm_reserve(additional) |
530 | } |
531 | } |
532 | |
533 | impl<K, V, S> LiteMap<K, V, S> |
534 | where |
535 | K: Ord, |
536 | S: StoreMut<K, V>, |
537 | { |
538 | /// Get the value associated with `key`, if it exists, as a mutable reference. |
539 | /// |
540 | /// ```rust |
541 | /// use litemap::LiteMap; |
542 | /// |
543 | /// let mut map = LiteMap::new_vec(); |
544 | /// map.insert(1, "one" ); |
545 | /// map.insert(2, "two" ); |
546 | /// if let Some(mut v) = map.get_mut(&1) { |
547 | /// *v = "uno" ; |
548 | /// } |
549 | /// assert_eq!(map.get(&1), Some(&"uno" )); |
550 | /// ``` |
551 | pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> |
552 | where |
553 | K: Borrow<Q>, |
554 | Q: Ord, |
555 | { |
556 | match self.find_index(key) { |
557 | #[allow (clippy::unwrap_used)] // find_index returns a valid index |
558 | Ok(found) => Some(self.values.lm_get_mut(found).unwrap().1), |
559 | Err(_) => None, |
560 | } |
561 | } |
562 | |
563 | /// Appends `value` with `key` to the end of the underlying vector, returning |
564 | /// `key` and `value` _if it failed_. Useful for extending with an existing |
565 | /// sorted list. |
566 | /// ```rust |
567 | /// use litemap::LiteMap; |
568 | /// |
569 | /// let mut map = LiteMap::new_vec(); |
570 | /// assert!(map.try_append(1, "uno" ).is_none()); |
571 | /// assert!(map.try_append(3, "tres" ).is_none()); |
572 | /// |
573 | /// assert!( |
574 | /// matches!(map.try_append(3, "tres-updated" ), Some((3, "tres-updated" ))), |
575 | /// "append duplicate of last key" , |
576 | /// ); |
577 | /// |
578 | /// assert!( |
579 | /// matches!(map.try_append(2, "dos" ), Some((2, "dos" ))), |
580 | /// "append out of order" |
581 | /// ); |
582 | /// |
583 | /// assert_eq!(map.get(&1), Some(&"uno" )); |
584 | /// |
585 | /// // contains the original value for the key: 3 |
586 | /// assert_eq!(map.get(&3), Some(&"tres" )); |
587 | /// |
588 | /// // not appended since it wasn't in order |
589 | /// assert_eq!(map.get(&2), None); |
590 | /// ``` |
591 | #[must_use ] |
592 | pub fn try_append(&mut self, key: K, value: V) -> Option<(K, V)> { |
593 | if let Some(last) = self.values.lm_last() { |
594 | if last.0 >= &key { |
595 | return Some((key, value)); |
596 | } |
597 | } |
598 | |
599 | self.values.lm_push(key, value); |
600 | None |
601 | } |
602 | |
603 | /// Insert `value` with `key`, returning the existing value if it exists. |
604 | /// |
605 | /// ```rust |
606 | /// use litemap::LiteMap; |
607 | /// |
608 | /// let mut map = LiteMap::new_vec(); |
609 | /// map.insert(1, "one" ); |
610 | /// map.insert(2, "two" ); |
611 | /// assert_eq!(map.get(&1), Some(&"one" )); |
612 | /// assert_eq!(map.get(&3), None); |
613 | /// ``` |
614 | pub fn insert(&mut self, key: K, value: V) -> Option<V> { |
615 | self.insert_save_key(key, value).map(|(_, v)| v) |
616 | } |
617 | |
618 | /// Version of [`Self::insert()`] that returns both the key and the old value. |
619 | fn insert_save_key(&mut self, key: K, value: V) -> Option<(K, V)> { |
620 | match self.values.lm_binary_search_by(|k| k.cmp(&key)) { |
621 | #[allow (clippy::unwrap_used)] // Index came from binary_search |
622 | Ok(found) => Some(( |
623 | key, |
624 | mem::replace(self.values.lm_get_mut(found).unwrap().1, value), |
625 | )), |
626 | Err(ins) => { |
627 | self.values.lm_insert(ins, key, value); |
628 | None |
629 | } |
630 | } |
631 | } |
632 | |
633 | /// Attempts to insert a unique entry into the map. |
634 | /// |
635 | /// If `key` is not already in the map, inserts it with the corresponding `value` |
636 | /// and returns `None`. |
637 | /// |
638 | /// If `key` is already in the map, no change is made to the map, and the key and value |
639 | /// are returned back to the caller. |
640 | /// |
641 | /// ``` |
642 | /// use litemap::LiteMap; |
643 | /// |
644 | /// let mut map = LiteMap::new_vec(); |
645 | /// map.insert(1, "one" ); |
646 | /// map.insert(3, "three" ); |
647 | /// |
648 | /// // 2 is not yet in the map... |
649 | /// assert_eq!(map.try_insert(2, "two" ), None); |
650 | /// assert_eq!(map.len(), 3); |
651 | /// |
652 | /// // ...but now it is. |
653 | /// assert_eq!(map.try_insert(2, "TWO" ), Some((2, "TWO" ))); |
654 | /// assert_eq!(map.len(), 3); |
655 | /// ``` |
656 | pub fn try_insert(&mut self, key: K, value: V) -> Option<(K, V)> { |
657 | match self.values.lm_binary_search_by(|k| k.cmp(&key)) { |
658 | Ok(_) => Some((key, value)), |
659 | Err(ins) => { |
660 | self.values.lm_insert(ins, key, value); |
661 | None |
662 | } |
663 | } |
664 | } |
665 | |
666 | /// Attempts to insert a unique entry into the map. |
667 | /// |
668 | /// If `key` is not already in the map, invokes the closure to compute `value`, inserts |
669 | /// the pair into the map, and returns a reference to the value. The closure is passed |
670 | /// a reference to the `key` argument. |
671 | /// |
672 | /// If `key` is already in the map, a reference to the existing value is returned. |
673 | /// |
674 | /// Additionally, the index of the value in the map is returned. If it is not desirable |
675 | /// to hold on to the mutable reference's lifetime, the index can be used to access the |
676 | /// element via [`LiteMap::get_indexed()`]. |
677 | /// |
678 | /// The closure returns a `Result` to allow for a fallible insertion function. If the |
679 | /// creation of `value` is infallible, you can use [`core::convert::Infallible`]. |
680 | /// |
681 | /// ``` |
682 | /// use litemap::LiteMap; |
683 | /// |
684 | /// /// Helper function to unwrap an `Infallible` result from the insertion function |
685 | /// fn unwrap_infallible<T>(result: Result<T, core::convert::Infallible>) -> T { |
686 | /// result.unwrap_or_else(|never| match never {}) |
687 | /// } |
688 | /// |
689 | /// let mut map = LiteMap::new_vec(); |
690 | /// map.insert(1, "one" ); |
691 | /// map.insert(3, "three" ); |
692 | /// |
693 | /// // 2 is not yet in the map... |
694 | /// let result1 = unwrap_infallible( |
695 | /// map.try_get_or_insert(2, |_| Ok("two" )) |
696 | /// ); |
697 | /// assert_eq!(result1.1, &"two" ); |
698 | /// assert_eq!(map.len(), 3); |
699 | /// |
700 | /// // ...but now it is. |
701 | /// let result1 = unwrap_infallible( |
702 | /// map.try_get_or_insert(2, |_| Ok("TWO" )) |
703 | /// ); |
704 | /// assert_eq!(result1.1, &"two" ); |
705 | /// assert_eq!(map.len(), 3); |
706 | /// ``` |
707 | pub fn try_get_or_insert<E>( |
708 | &mut self, |
709 | key: K, |
710 | value: impl FnOnce(&K) -> Result<V, E>, |
711 | ) -> Result<(usize, &V), E> { |
712 | let idx = match self.values.lm_binary_search_by(|k| k.cmp(&key)) { |
713 | Ok(idx) => idx, |
714 | Err(idx) => { |
715 | let value = value(&key)?; |
716 | self.values.lm_insert(idx, key, value); |
717 | idx |
718 | } |
719 | }; |
720 | #[allow (clippy::unwrap_used)] // item at idx found or inserted above |
721 | Ok((idx, self.values.lm_get(idx).unwrap().1)) |
722 | } |
723 | |
724 | /// Remove the value at `key`, returning it if it exists. |
725 | /// |
726 | /// ```rust |
727 | /// use litemap::LiteMap; |
728 | /// |
729 | /// let mut map = LiteMap::new_vec(); |
730 | /// map.insert(1, "one" ); |
731 | /// map.insert(2, "two" ); |
732 | /// assert_eq!(map.remove(&1), Some("one" )); |
733 | /// assert_eq!(map.get(&1), None); |
734 | /// ``` |
735 | pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> |
736 | where |
737 | K: Borrow<Q>, |
738 | Q: Ord, |
739 | { |
740 | match self.values.lm_binary_search_by(|k| k.borrow().cmp(key)) { |
741 | Ok(found) => Some(self.values.lm_remove(found).1), |
742 | Err(_) => None, |
743 | } |
744 | } |
745 | } |
746 | |
747 | impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> |
748 | where |
749 | K: Ord, |
750 | S: StoreIterableMut<'a, K, V> + StoreFromIterator<K, V>, |
751 | { |
752 | /// Insert all elements from `other` into this `LiteMap`. |
753 | /// |
754 | /// If `other` contains keys that already exist in `self`, the values in `other` replace the |
755 | /// corresponding ones in `self`, and the rejected items from `self` are returned as a new |
756 | /// `LiteMap`. Otherwise, `None` is returned. |
757 | /// |
758 | /// The implementation of this function is optimized if `self` and `other` have no overlap. |
759 | /// |
760 | /// # Examples |
761 | /// |
762 | /// ``` |
763 | /// use litemap::LiteMap; |
764 | /// |
765 | /// let mut map1 = LiteMap::new_vec(); |
766 | /// map1.insert(1, "one" ); |
767 | /// map1.insert(2, "two" ); |
768 | /// |
769 | /// let mut map2 = LiteMap::new_vec(); |
770 | /// map2.insert(2, "TWO" ); |
771 | /// map2.insert(4, "FOUR" ); |
772 | /// |
773 | /// let leftovers = map1.extend_from_litemap(map2); |
774 | /// |
775 | /// assert_eq!(map1.len(), 3); |
776 | /// assert_eq!(map1.get(&1), Some("one" ).as_ref()); |
777 | /// assert_eq!(map1.get(&2), Some("TWO" ).as_ref()); |
778 | /// assert_eq!(map1.get(&4), Some("FOUR" ).as_ref()); |
779 | /// |
780 | /// let map3 = leftovers.expect("Duplicate keys" ); |
781 | /// assert_eq!(map3.len(), 1); |
782 | /// assert_eq!(map3.get(&2), Some("two" ).as_ref()); |
783 | /// ``` |
784 | pub fn extend_from_litemap(&mut self, other: Self) -> Option<Self> { |
785 | if self.is_empty() { |
786 | self.values = other.values; |
787 | return None; |
788 | } |
789 | if other.is_empty() { |
790 | return None; |
791 | } |
792 | if self.last().map(|(k, _)| k) < other.first().map(|(k, _)| k) { |
793 | // append other to self |
794 | self.values.lm_extend_end(other.values); |
795 | None |
796 | } else if self.first().map(|(k, _)| k) > other.last().map(|(k, _)| k) { |
797 | // prepend other to self |
798 | self.values.lm_extend_start(other.values); |
799 | None |
800 | } else { |
801 | // insert every element |
802 | let leftover_tuples = other |
803 | .values |
804 | .lm_into_iter() |
805 | .filter_map(|(k, v)| self.insert_save_key(k, v)) |
806 | .collect(); |
807 | let ret = LiteMap { |
808 | values: leftover_tuples, |
809 | _key_type: PhantomData, |
810 | _value_type: PhantomData, |
811 | }; |
812 | if ret.is_empty() { |
813 | None |
814 | } else { |
815 | Some(ret) |
816 | } |
817 | } |
818 | } |
819 | } |
820 | |
821 | impl<K, V, S> Default for LiteMap<K, V, S> |
822 | where |
823 | S: Store<K, V> + Default, |
824 | { |
825 | fn default() -> Self { |
826 | Self { |
827 | values: S::default(), |
828 | _key_type: PhantomData, |
829 | _value_type: PhantomData, |
830 | } |
831 | } |
832 | } |
833 | impl<K, V, S> Index<&'_ K> for LiteMap<K, V, S> |
834 | where |
835 | K: Ord, |
836 | S: Store<K, V>, |
837 | { |
838 | type Output = V; |
839 | fn index(&self, key: &K) -> &V { |
840 | #[allow (clippy::panic)] // documented |
841 | match self.get(key) { |
842 | Some(v: &V) => v, |
843 | None => panic!("no entry found for key" ), |
844 | } |
845 | } |
846 | } |
847 | impl<K, V, S> IndexMut<&'_ K> for LiteMap<K, V, S> |
848 | where |
849 | K: Ord, |
850 | S: StoreMut<K, V>, |
851 | { |
852 | fn index_mut(&mut self, key: &K) -> &mut V { |
853 | #[allow (clippy::panic)] // documented |
854 | match self.get_mut(key) { |
855 | Some(v: &mut V) => v, |
856 | None => panic!("no entry found for key" ), |
857 | } |
858 | } |
859 | } |
860 | impl<K, V, S> FromIterator<(K, V)> for LiteMap<K, V, S> |
861 | where |
862 | K: Ord, |
863 | S: StoreFromIterable<K, V>, |
864 | { |
865 | fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self { |
866 | let values: S = S::lm_sort_from_iter(iter); |
867 | Self::from_sorted_store_unchecked(values) |
868 | } |
869 | } |
870 | |
871 | impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> |
872 | where |
873 | S: StoreIterable<'a, K, V>, |
874 | { |
875 | /// Produce an ordered iterator over key-value pairs |
876 | pub fn iter(&'a self) -> impl DoubleEndedIterator<Item = (&'a K, &'a V)> { |
877 | self.values.lm_iter() |
878 | } |
879 | |
880 | /// Produce an ordered iterator over keys |
881 | pub fn iter_keys(&'a self) -> impl DoubleEndedIterator<Item = &'a K> { |
882 | self.values.lm_iter().map(|val: (&K, &V)| val.0) |
883 | } |
884 | |
885 | /// Produce an iterator over values, ordered by their keys |
886 | pub fn iter_values(&'a self) -> impl DoubleEndedIterator<Item = &'a V> { |
887 | self.values.lm_iter().map(|val: (&K, &V)| val.1) |
888 | } |
889 | } |
890 | |
891 | impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> |
892 | where |
893 | S: StoreIterableMut<'a, K, V>, |
894 | { |
895 | /// Produce an ordered mutable iterator over key-value pairs |
896 | pub fn iter_mut(&'a mut self) -> impl DoubleEndedIterator<Item = (&'a K, &'a mut V)> { |
897 | self.values.lm_iter_mut() |
898 | } |
899 | } |
900 | |
901 | impl<K, V, S> LiteMap<K, V, S> |
902 | where |
903 | S: StoreMut<K, V>, |
904 | { |
905 | /// Retains only the elements specified by the predicate. |
906 | /// |
907 | /// In other words, remove all elements such that `f((&k, &v))` returns `false`. |
908 | /// |
909 | /// # Example |
910 | /// |
911 | /// ```rust |
912 | /// use litemap::LiteMap; |
913 | /// |
914 | /// let mut map = LiteMap::new_vec(); |
915 | /// map.insert(1, "one" ); |
916 | /// map.insert(2, "two" ); |
917 | /// map.insert(3, "three" ); |
918 | /// |
919 | /// // Retain elements with odd keys |
920 | /// map.retain(|k, _| k % 2 == 1); |
921 | /// |
922 | /// assert_eq!(map.get(&1), Some(&"one" )); |
923 | /// assert_eq!(map.get(&2), None); |
924 | /// ``` |
925 | #[inline ] |
926 | pub fn retain<F>(&mut self, predicate: F) |
927 | where |
928 | F: FnMut(&K, &V) -> bool, |
929 | { |
930 | self.values.lm_retain(predicate) |
931 | } |
932 | } |
933 | |
934 | impl<'a, K, V> LiteMap<K, V, &'a [(K, V)]> { |
935 | /// Const version of [`LiteMap::len()`] for a slice store. |
936 | /// |
937 | /// Note: This function will no longer be needed if const trait behavior is stabilized. |
938 | /// |
939 | /// # Examples |
940 | /// |
941 | /// ```rust |
942 | /// use litemap::LiteMap; |
943 | /// |
944 | /// static map: LiteMap<&str, usize, &[(&str, usize)]> = |
945 | /// LiteMap::from_sorted_store_unchecked(&[("a" , 11), ("b" , 22)]); |
946 | /// static len: usize = map.const_len(); |
947 | /// assert_eq!(len, 2); |
948 | /// ``` |
949 | #[inline ] |
950 | pub const fn const_len(&self) -> usize { |
951 | self.values.len() |
952 | } |
953 | |
954 | /// Const version of [`LiteMap::is_empty()`] for a slice store. |
955 | /// |
956 | /// Note: This function will no longer be needed if const trait behavior is stabilized. |
957 | /// |
958 | /// # Examples |
959 | /// |
960 | /// ```rust |
961 | /// use litemap::LiteMap; |
962 | /// |
963 | /// static map: LiteMap<&str, usize, &[(&str, usize)]> = |
964 | /// LiteMap::from_sorted_store_unchecked(&[]); |
965 | /// static is_empty: bool = map.const_is_empty(); |
966 | /// assert!(is_empty); |
967 | /// ``` |
968 | #[inline ] |
969 | pub const fn const_is_empty(&self) -> bool { |
970 | self.values.is_empty() |
971 | } |
972 | |
973 | /// Const version of [`LiteMap::get_indexed()`] for a slice store. |
974 | /// |
975 | /// Note: This function will no longer be needed if const trait behavior is stabilized. |
976 | /// |
977 | /// # Panics |
978 | /// |
979 | /// Panics if the index is out of bounds. |
980 | /// |
981 | /// # Examples |
982 | /// |
983 | /// ```rust |
984 | /// use litemap::LiteMap; |
985 | /// |
986 | /// static map: LiteMap<&str, usize, &[(&str, usize)]> = |
987 | /// LiteMap::from_sorted_store_unchecked(&[("a" , 11), ("b" , 22)]); |
988 | /// static t: &(&str, usize) = map.const_get_indexed_or_panic(0); |
989 | /// assert_eq!(t.0, "a" ); |
990 | /// assert_eq!(t.1, 11); |
991 | /// ``` |
992 | #[inline ] |
993 | #[allow (clippy::indexing_slicing)] // documented |
994 | pub const fn const_get_indexed_or_panic(&self, index: usize) -> &'a (K, V) { |
995 | &self.values[index] |
996 | } |
997 | } |
998 | |
999 | const fn const_cmp_bytes(a: &[u8], b: &[u8]) -> Ordering { |
1000 | let (max: usize, default: Ordering) = if a.len() == b.len() { |
1001 | (a.len(), Ordering::Equal) |
1002 | } else if a.len() < b.len() { |
1003 | (a.len(), Ordering::Less) |
1004 | } else { |
1005 | (b.len(), Ordering::Greater) |
1006 | }; |
1007 | let mut i: usize = 0; |
1008 | #[allow (clippy::indexing_slicing)] // indexes in range by above checks |
1009 | while i < max { |
1010 | if a[i] == b[i] { |
1011 | i += 1; |
1012 | continue; |
1013 | } else if a[i] < b[i] { |
1014 | return Ordering::Less; |
1015 | } else { |
1016 | return Ordering::Greater; |
1017 | } |
1018 | } |
1019 | default |
1020 | } |
1021 | |
1022 | impl<'a, V> LiteMap<&'a str, V, &'a [(&'a str, V)]> { |
1023 | /// Const function to get the value associated with a `&str` key, if it exists. |
1024 | /// |
1025 | /// Also returns the index of the value. |
1026 | /// |
1027 | /// Note: This function will no longer be needed if const trait behavior is stabilized. |
1028 | /// |
1029 | /// # Examples |
1030 | /// |
1031 | /// ```rust |
1032 | /// use litemap::LiteMap; |
1033 | /// |
1034 | /// static map: LiteMap<&str, usize, &[(&str, usize)]> = |
1035 | /// LiteMap::from_sorted_store_unchecked(&[ |
1036 | /// ("abc" , 11), |
1037 | /// ("bcd" , 22), |
1038 | /// ("cde" , 33), |
1039 | /// ("def" , 44), |
1040 | /// ("efg" , 55), |
1041 | /// ]); |
1042 | /// |
1043 | /// static d: Option<(usize, &usize)> = map.const_get_with_index("def" ); |
1044 | /// assert_eq!(d, Some((3, &44))); |
1045 | /// |
1046 | /// static n: Option<(usize, &usize)> = map.const_get_with_index("dng" ); |
1047 | /// assert_eq!(n, None); |
1048 | /// ``` |
1049 | pub const fn const_get_with_index(&self, key: &str) -> Option<(usize, &'a V)> { |
1050 | let mut i = 0; |
1051 | let mut j = self.const_len(); |
1052 | while i < j { |
1053 | let mid = (i + j) / 2; |
1054 | #[allow (clippy::indexing_slicing)] // in range |
1055 | let x = &self.values[mid]; |
1056 | match const_cmp_bytes(key.as_bytes(), x.0.as_bytes()) { |
1057 | Ordering::Equal => return Some((mid, &x.1)), |
1058 | Ordering::Greater => i = mid + 1, |
1059 | Ordering::Less => j = mid, |
1060 | }; |
1061 | } |
1062 | None |
1063 | } |
1064 | } |
1065 | |
1066 | impl<'a, V> LiteMap<&'a [u8], V, &'a [(&'a [u8], V)]> { |
1067 | /// Const function to get the value associated with a `&[u8]` key, if it exists. |
1068 | /// |
1069 | /// Also returns the index of the value. |
1070 | /// |
1071 | /// Note: This function will no longer be needed if const trait behavior is stabilized. |
1072 | /// |
1073 | /// # Examples |
1074 | /// |
1075 | /// ```rust |
1076 | /// use litemap::LiteMap; |
1077 | /// |
1078 | /// static map: LiteMap<&[u8], usize, &[(&[u8], usize)]> = |
1079 | /// LiteMap::from_sorted_store_unchecked(&[ |
1080 | /// (b"abc" , 11), |
1081 | /// (b"bcd" , 22), |
1082 | /// (b"cde" , 33), |
1083 | /// (b"def" , 44), |
1084 | /// (b"efg" , 55), |
1085 | /// ]); |
1086 | /// |
1087 | /// static d: Option<(usize, &usize)> = map.const_get_with_index(b"def" ); |
1088 | /// assert_eq!(d, Some((3, &44))); |
1089 | /// |
1090 | /// static n: Option<(usize, &usize)> = map.const_get_with_index(b"dng" ); |
1091 | /// assert_eq!(n, None); |
1092 | /// ``` |
1093 | pub const fn const_get_with_index(&self, key: &[u8]) -> Option<(usize, &'a V)> { |
1094 | let mut i = 0; |
1095 | let mut j = self.const_len(); |
1096 | while i < j { |
1097 | let mid = (i + j) / 2; |
1098 | #[allow (clippy::indexing_slicing)] // in range |
1099 | let x = &self.values[mid]; |
1100 | match const_cmp_bytes(key, x.0) { |
1101 | Ordering::Equal => return Some((mid, &x.1)), |
1102 | Ordering::Greater => i = mid + 1, |
1103 | Ordering::Less => j = mid, |
1104 | }; |
1105 | } |
1106 | None |
1107 | } |
1108 | } |
1109 | |
1110 | macro_rules! impl_const_get_with_index_for_integer { |
1111 | ($integer:ty) => { |
1112 | impl<'a, V> LiteMap<$integer, V, &'a [($integer, V)]> { |
1113 | /// Const function to get the value associated with an integer key, if it exists. |
1114 | /// |
1115 | /// Note: This function will no longer be needed if const trait behavior is stabilized. |
1116 | /// |
1117 | /// Also returns the index of the value. |
1118 | pub const fn const_get_with_index(&self, key: $integer) -> Option<(usize, &'a V)> { |
1119 | let mut i = 0; |
1120 | let mut j = self.const_len(); |
1121 | while i < j { |
1122 | let mid = (i + j) / 2; |
1123 | #[allow(clippy::indexing_slicing)] // in range |
1124 | let x = &self.values[mid]; |
1125 | if key == x.0 { |
1126 | return Some((mid, &x.1)); |
1127 | } else if key > x.0 { |
1128 | i = mid + 1; |
1129 | } else { |
1130 | j = mid; |
1131 | } |
1132 | } |
1133 | return None; |
1134 | } |
1135 | } |
1136 | }; |
1137 | } |
1138 | |
1139 | impl_const_get_with_index_for_integer!(u8); |
1140 | impl_const_get_with_index_for_integer!(u16); |
1141 | impl_const_get_with_index_for_integer!(u32); |
1142 | impl_const_get_with_index_for_integer!(u64); |
1143 | impl_const_get_with_index_for_integer!(u128); |
1144 | impl_const_get_with_index_for_integer!(usize); |
1145 | impl_const_get_with_index_for_integer!(i8); |
1146 | impl_const_get_with_index_for_integer!(i16); |
1147 | impl_const_get_with_index_for_integer!(i32); |
1148 | impl_const_get_with_index_for_integer!(i64); |
1149 | impl_const_get_with_index_for_integer!(i128); |
1150 | impl_const_get_with_index_for_integer!(isize); |
1151 | |
1152 | #[cfg (test)] |
1153 | mod test { |
1154 | use super::*; |
1155 | |
1156 | #[test ] |
1157 | fn from_iterator() { |
1158 | let mut expected = LiteMap::with_capacity(4); |
1159 | expected.insert(1, "updated-one" ); |
1160 | expected.insert(2, "original-two" ); |
1161 | expected.insert(3, "original-three" ); |
1162 | expected.insert(4, "updated-four" ); |
1163 | |
1164 | let actual = [ |
1165 | (1, "original-one" ), |
1166 | (2, "original-two" ), |
1167 | (4, "original-four" ), |
1168 | (4, "updated-four" ), |
1169 | (1, "updated-one" ), |
1170 | (3, "original-three" ), |
1171 | ] |
1172 | .into_iter() |
1173 | .collect::<LiteMap<_, _>>(); |
1174 | |
1175 | assert_eq!(expected, actual); |
1176 | } |
1177 | fn make_13() -> LiteMap<usize, &'static str> { |
1178 | let mut result = LiteMap::new(); |
1179 | result.insert(1, "one" ); |
1180 | result.insert(3, "three" ); |
1181 | result |
1182 | } |
1183 | |
1184 | fn make_24() -> LiteMap<usize, &'static str> { |
1185 | let mut result = LiteMap::new(); |
1186 | result.insert(2, "TWO" ); |
1187 | result.insert(4, "FOUR" ); |
1188 | result |
1189 | } |
1190 | |
1191 | fn make_46() -> LiteMap<usize, &'static str> { |
1192 | let mut result = LiteMap::new(); |
1193 | result.insert(4, "four" ); |
1194 | result.insert(6, "six" ); |
1195 | result |
1196 | } |
1197 | |
1198 | #[test ] |
1199 | fn extend_from_litemap_append() { |
1200 | let mut map = LiteMap::new(); |
1201 | map.extend_from_litemap(make_13()) |
1202 | .ok_or(()) |
1203 | .expect_err("Append to empty map" ); |
1204 | map.extend_from_litemap(make_46()) |
1205 | .ok_or(()) |
1206 | .expect_err("Append to lesser map" ); |
1207 | assert_eq!(map.len(), 4); |
1208 | } |
1209 | |
1210 | #[test ] |
1211 | fn extend_from_litemap_prepend() { |
1212 | let mut map = LiteMap::new(); |
1213 | map.extend_from_litemap(make_46()) |
1214 | .ok_or(()) |
1215 | .expect_err("Prepend to empty map" ); |
1216 | map.extend_from_litemap(make_13()) |
1217 | .ok_or(()) |
1218 | .expect_err("Prepend to lesser map" ); |
1219 | assert_eq!(map.len(), 4); |
1220 | } |
1221 | |
1222 | #[test ] |
1223 | fn extend_from_litemap_insert() { |
1224 | let mut map = LiteMap::new(); |
1225 | map.extend_from_litemap(make_13()) |
1226 | .ok_or(()) |
1227 | .expect_err("Append to empty map" ); |
1228 | map.extend_from_litemap(make_24()) |
1229 | .ok_or(()) |
1230 | .expect_err("Insert with no conflict" ); |
1231 | map.extend_from_litemap(make_46()) |
1232 | .ok_or(()) |
1233 | .expect("Insert with conflict" ); |
1234 | assert_eq!(map.len(), 5); |
1235 | } |
1236 | |
1237 | #[test ] |
1238 | fn test_const_cmp_bytes() { |
1239 | let strs = &["a" , "aa" , "abc" , "abde" , "bcd" , "bcde" ]; |
1240 | for i in 0..strs.len() { |
1241 | for j in 0..strs.len() { |
1242 | let a = strs[i].as_bytes(); |
1243 | let b = strs[j].as_bytes(); |
1244 | assert_eq!(a.cmp(b), const_cmp_bytes(a, b)); |
1245 | } |
1246 | } |
1247 | } |
1248 | } |
1249 | |