litemap/

map.rs

// This file is part of ICU4X. For terms of use, please see the file
// called LICENSE at the top level of the ICU4X source tree
// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).

use crate::store::*;
use alloc::borrow::Borrow;
use alloc::boxed::Box;
use alloc::vec::Vec;
use core::cmp::Ordering;
use core::iter::FromIterator;
use core::marker::PhantomData;
use core::mem;
use core::ops::{Index, IndexMut, Range};

/// A simple "flat" map based on a sorted vector
///
/// See the [module level documentation][super] for why one should use this.
///
/// The API is roughly similar to that of [`std::collections::BTreeMap`].
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "yoke", derive(yoke::Yokeable))]
pub struct LiteMap<K: ?Sized, V: ?Sized, S = alloc::vec::Vec<(K, V)>> {
    pub(crate) values: S,
    pub(crate) _key_type: PhantomData<K>,
    pub(crate) _value_type: PhantomData<V>,
}

impl<K, V> LiteMap<K, V> {
    /// Construct a new [`LiteMap`] backed by Vec
    pub const fn new_vec() -> Self {
        Self {
            values: alloc::vec::Vec::new(),
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }
}

impl<K, V, S> LiteMap<K, V, S> {
    /// Construct a new [`LiteMap`] using the given values
    ///
    /// The store must be sorted and have no duplicate keys.
    pub const fn from_sorted_store_unchecked(values: S) -> Self {
        Self {
            values,
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }
}

impl<K, V> LiteMap<K, V, Vec<(K, V)>> {
    /// Convert a [`LiteMap`] into a sorted `Vec<(K, V)>`.
    #[inline]
    pub fn into_tuple_vec(self) -> Vec<(K, V)> {
        self.values
    }
}

impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
where
    S: StoreConstEmpty<K, V>,
{
    /// Create a new empty [`LiteMap`]
    pub const fn new() -> Self {
        Self {
            values: S::EMPTY,
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }
}

impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
where
    S: Store<K, V>,
{
    /// The number of elements in the [`LiteMap`]
    pub fn len(&self) -> usize {
        self.values.lm_len()
    }

    /// Whether the [`LiteMap`] is empty
    pub fn is_empty(&self) -> bool {
        self.values.lm_is_empty()
    }

    /// Get the key-value pair residing at a particular index
    ///
    /// In most cases, prefer [`LiteMap::get()`] over this method.
    #[inline]
    pub fn get_indexed(&self, index: usize) -> Option<(&K, &V)> {
        self.values.lm_get(index)
    }

    /// Get the lowest-rank key/value pair from the `LiteMap`, if it exists.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// let mut map =
    ///     LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno"), (3, "tres")]);
    ///
    /// assert_eq!(map.first(), Some((&1, &"uno")));
    /// ```
    #[inline]
    pub fn first(&self) -> Option<(&K, &V)> {
        self.values.lm_get(0)
    }

    /// Get the highest-rank key/value pair from the `LiteMap`, if it exists.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// let mut map =
    ///     LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno"), (3, "tres")]);
    ///
    /// assert_eq!(map.last(), Some((&3, &"tres")));
    /// ```
    #[inline]
    pub fn last(&self) -> Option<(&K, &V)> {
        self.values.lm_last()
    }

    /// Returns a new [`LiteMap`] with owned keys and values.
    ///
    /// The trait bounds allow transforming most slice and string types.
    ///
    /// # Examples
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// let mut map: LiteMap<&str, &str> = LiteMap::new_vec();
    /// map.insert("one", "uno");
    /// map.insert("two", "dos");
    ///
    /// let boxed_map: LiteMap<Box<str>, Box<str>> = map.to_boxed_keys_values();
    ///
    /// assert_eq!(boxed_map.get("one"), Some(&Box::from("uno")));
    /// ```
    pub fn to_boxed_keys_values<KB: ?Sized, VB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, Box<VB>, SB>
    where
        SB: StoreMut<Box<KB>, Box<VB>>,
        K: Borrow<KB>,
        V: Borrow<VB>,
        Box<KB>: for<'a> From<&'a KB>,
        Box<VB>: for<'a> From<&'a VB>,
    {
        let mut values = SB::lm_with_capacity(self.len());
        for i in 0..self.len() {
            #[allow(clippy::unwrap_used)] // iterating over our own length
            let (k, v) = self.values.lm_get(i).unwrap();
            values.lm_push(Box::from(k.borrow()), Box::from(v.borrow()))
        }
        LiteMap {
            values,
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }

    /// Returns a new [`LiteMap`] with owned keys and cloned values.
    ///
    /// The trait bounds allow transforming most slice and string types.
    ///
    /// # Examples
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// let mut map: LiteMap<&str, usize> = LiteMap::new_vec();
    /// map.insert("one", 11);
    /// map.insert("two", 22);
    ///
    /// let boxed_map: LiteMap<Box<str>, usize> = map.to_boxed_keys();
    ///
    /// assert_eq!(boxed_map.get("one"), Some(&11));
    /// ```
    pub fn to_boxed_keys<KB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, V, SB>
    where
        V: Clone,
        SB: StoreMut<Box<KB>, V>,
        K: Borrow<KB>,
        Box<KB>: for<'a> From<&'a KB>,
    {
        let mut values = SB::lm_with_capacity(self.len());
        for i in 0..self.len() {
            #[allow(clippy::unwrap_used)] // iterating over our own length
            let (k, v) = self.values.lm_get(i).unwrap();
            values.lm_push(Box::from(k.borrow()), v.clone())
        }
        LiteMap {
            values,
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }

    /// Returns a new [`LiteMap`] with cloned keys and owned values.
    ///
    /// The trait bounds allow transforming most slice and string types.
    ///
    /// # Examples
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// let mut map: LiteMap<usize, &str> = LiteMap::new_vec();
    /// map.insert(11, "uno");
    /// map.insert(22, "dos");
    ///
    /// let boxed_map: LiteMap<usize, Box<str>> = map.to_boxed_values();
    ///
    /// assert_eq!(boxed_map.get(&11), Some(&Box::from("uno")));
    /// ```
    pub fn to_boxed_values<VB: ?Sized, SB>(&self) -> LiteMap<K, Box<VB>, SB>
    where
        K: Clone,
        SB: StoreMut<K, Box<VB>>,
        V: Borrow<VB>,
        Box<VB>: for<'a> From<&'a VB>,
    {
        let mut values = SB::lm_with_capacity(self.len());
        for i in 0..self.len() {
            #[allow(clippy::unwrap_used)] // iterating over our own length
            let (k, v) = self.values.lm_get(i).unwrap();
            values.lm_push(k.clone(), Box::from(v.borrow()))
        }
        LiteMap {
            values,
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }
}

impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
where
    K: Ord,
    S: Store<K, V>,
{
    /// Get the value associated with `key`, if it exists.
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// let mut map = LiteMap::new_vec();
    /// map.insert(1, "one");
    /// map.insert(2, "two");
    /// assert_eq!(map.get(&1), Some(&"one"));
    /// assert_eq!(map.get(&3), None);
    /// ```
    pub fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        match self.find_index(key) {
            #[allow(clippy::unwrap_used)] // find_index returns a valid index
            Ok(found) => Some(self.values.lm_get(found).unwrap().1),
            Err(_) => None,
        }
    }

    /// Binary search the map with `predicate` to find a key, returning the value.
    pub fn get_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<&V> {
        let index = self.values.lm_binary_search_by(predicate).ok()?;
        self.values.lm_get(index).map(|(_, v)| v)
    }

    /// Returns whether `key` is contained in this map
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// let mut map = LiteMap::new_vec();
    /// map.insert(1, "one");
    /// map.insert(2, "two");
    /// assert!(map.contains_key(&1));
    /// assert!(!map.contains_key(&3));
    /// ```
    pub fn contains_key<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.find_index(key).is_ok()
    }

    /// Obtain the index for a given key, or if the key is not found, the index
    /// at which it would be inserted.
    ///
    /// (The return value works equivalently to [`slice::binary_search_by()`])
    ///
    /// The indices returned can be used with [`Self::get_indexed()`]. Prefer using
    /// [`Self::get()`] directly where possible.
    #[inline]
    pub fn find_index<Q>(&self, key: &Q) -> Result<usize, usize>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.values.lm_binary_search_by(|k| k.borrow().cmp(key))
    }
}

impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
where
    S: StoreSlice<K, V>,
{
    /// Creates a new [`LiteMap`] from a range of the current [`LiteMap`].
    ///
    /// # Examples
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// let mut map = LiteMap::new_vec();
    /// map.insert(1, "one");
    /// map.insert(2, "two");
    /// map.insert(3, "three");
    ///
    /// let mut sub_map = map.get_indexed_range(1..3).expect("valid range");
    /// assert_eq!(sub_map.get(&1), None);
    /// assert_eq!(sub_map.get(&2), Some(&"two"));
    /// assert_eq!(sub_map.get(&3), Some(&"three"));
    /// ```
    pub fn get_indexed_range(&self, range: Range<usize>) -> Option<LiteMap<K, V, &S::Slice>> {
        let subslice = self.values.lm_get_range(range)?;
        Some(LiteMap {
            values: subslice,
            _key_type: PhantomData,
            _value_type: PhantomData,
        })
    }

    /// Borrows this [`LiteMap`] as one of its slice type.
    ///
    /// This can be useful in situations where you need a `LiteMap` by value but do not want
    /// to clone the owned version.
    ///
    /// # Examples
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// let mut map = LiteMap::new_vec();
    /// map.insert(1, "one");
    /// map.insert(2, "two");
    ///
    /// let borrowed_map = map.as_sliced();
    /// assert_eq!(borrowed_map.get(&1), Some(&"one"));
    /// assert_eq!(borrowed_map.get(&2), Some(&"two"));
    /// ```
    pub fn as_sliced(&self) -> LiteMap<K, V, &S::Slice> {
        // Won't panic: 0..self.len() is within range
        #[allow(clippy::unwrap_used)]
        let subslice = self.values.lm_get_range(0..self.len()).unwrap();
        LiteMap {
            values: subslice,
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }

    /// Borrows the backing buffer of this [`LiteMap`] as its slice type.
    ///
    /// The slice will be sorted.
    ///
    /// # Examples
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// let mut map = LiteMap::new_vec();
    /// map.insert(1, "one");
    /// map.insert(2, "two");
    ///
    /// let slice = map.as_slice();
    /// assert_eq!(slice, &[(1, "one"), (2, "two")]);
    /// ```
    pub fn as_slice(&self) -> &S::Slice {
        // Won't panic: 0..self.len() is within range
        #[allow(clippy::unwrap_used)]
        self.values.lm_get_range(0..self.len()).unwrap()
    }
}

impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
where
    S: Store<K, V>,
{
    /// Returns a new [`LiteMap`] with keys and values borrowed from this one.
    ///
    /// # Examples
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec();
    /// map.insert(Box::new(1), "one".to_string());
    /// map.insert(Box::new(2), "two".to_string());
    ///
    /// let borrowed_map: LiteMap<&usize, &str> = map.to_borrowed_keys_values();
    ///
    /// assert_eq!(borrowed_map.get(&1), Some(&"one"));
    /// ```
    pub fn to_borrowed_keys_values<KB: ?Sized, VB: ?Sized, SB>(
        &'a self,
    ) -> LiteMap<&'a KB, &'a VB, SB>
    where
        K: Borrow<KB>,
        V: Borrow<VB>,
        SB: StoreMut<&'a KB, &'a VB>,
    {
        let mut values = SB::lm_with_capacity(self.len());
        for i in 0..self.len() {
            #[allow(clippy::unwrap_used)] // iterating over our own length
            let (k, v) = self.values.lm_get(i).unwrap();
            values.lm_push(k.borrow(), v.borrow())
        }
        LiteMap {
            values,
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }

    /// Returns a new [`LiteMap`] with keys borrowed from this one and cloned values.
    ///
    /// # Examples
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec();
    /// map.insert(Box::new(1), "one".to_string());
    /// map.insert(Box::new(2), "two".to_string());
    ///
    /// let borrowed_map: LiteMap<&usize, String> = map.to_borrowed_keys();
    ///
    /// assert_eq!(borrowed_map.get(&1), Some(&"one".to_string()));
    /// ```
    pub fn to_borrowed_keys<KB: ?Sized, SB>(&'a self) -> LiteMap<&'a KB, V, SB>
    where
        K: Borrow<KB>,
        V: Clone,
        SB: StoreMut<&'a KB, V>,
    {
        let mut values = SB::lm_with_capacity(self.len());
        for i in 0..self.len() {
            #[allow(clippy::unwrap_used)] // iterating over our own length
            let (k, v) = self.values.lm_get(i).unwrap();
            values.lm_push(k.borrow(), v.clone())
        }
        LiteMap {
            values,
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }

    /// Returns a new [`LiteMap`] with values borrowed from this one and cloned keys.
    ///
    /// # Examples
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec();
    /// map.insert(Box::new(1), "one".to_string());
    /// map.insert(Box::new(2), "two".to_string());
    ///
    /// let borrowed_map: LiteMap<Box<usize>, &str> = map.to_borrowed_values();
    ///
    /// assert_eq!(borrowed_map.get(&1), Some(&"one"));
    /// ```
    pub fn to_borrowed_values<VB: ?Sized, SB>(&'a self) -> LiteMap<K, &'a VB, SB>
    where
        K: Clone,
        V: Borrow<VB>,
        SB: StoreMut<K, &'a VB>,
    {
        let mut values = SB::lm_with_capacity(self.len());
        for i in 0..self.len() {
            #[allow(clippy::unwrap_used)] // iterating over our own length
            let (k, v) = self.values.lm_get(i).unwrap();
            values.lm_push(k.clone(), v.borrow())
        }
        LiteMap {
            values,
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }
}

impl<K, V, S> LiteMap<K, V, S>
where
    S: StoreMut<K, V>,
{
    /// Construct a new [`LiteMap`] with a given capacity
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            values: S::lm_with_capacity(capacity),
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }

    /// Remove all elements from the [`LiteMap`]
    pub fn clear(&mut self) {
        self.values.lm_clear()
    }

    /// Reserve capacity for `additional` more elements to be inserted into
    /// the [`LiteMap`] to avoid frequent reallocations.
    ///
    /// See [`Vec::reserve()`] for more information.
    ///
    /// [`Vec::reserve()`]: alloc::vec::Vec::reserve
    pub fn reserve(&mut self, additional: usize) {
        self.values.lm_reserve(additional)
    }
}

impl<K, V, S> LiteMap<K, V, S>
where
    K: Ord,
    S: StoreMut<K, V>,
{
    /// Get the value associated with `key`, if it exists, as a mutable reference.
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// let mut map = LiteMap::new_vec();
    /// map.insert(1, "one");
    /// map.insert(2, "two");
    /// if let Some(mut v) = map.get_mut(&1) {
    ///     *v = "uno";
    /// }
    /// assert_eq!(map.get(&1), Some(&"uno"));
    /// ```
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        match self.find_index(key) {
            #[allow(clippy::unwrap_used)] // find_index returns a valid index
            Ok(found) => Some(self.values.lm_get_mut(found).unwrap().1),
            Err(_) => None,
        }
    }

    /// Appends `value` with `key` to the end of the underlying vector, returning
    /// `key` and `value` _if it failed_. Useful for extending with an existing
    /// sorted list.
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// let mut map = LiteMap::new_vec();
    /// assert!(map.try_append(1, "uno").is_none());
    /// assert!(map.try_append(3, "tres").is_none());
    ///
    /// assert!(
    ///     matches!(map.try_append(3, "tres-updated"), Some((3, "tres-updated"))),
    ///     "append duplicate of last key",
    /// );
    ///
    /// assert!(
    ///     matches!(map.try_append(2, "dos"), Some((2, "dos"))),
    ///     "append out of order"
    /// );
    ///
    /// assert_eq!(map.get(&1), Some(&"uno"));
    ///
    /// // contains the original value for the key: 3
    /// assert_eq!(map.get(&3), Some(&"tres"));
    ///
    /// // not appended since it wasn't in order
    /// assert_eq!(map.get(&2), None);
    /// ```
    #[must_use]
    pub fn try_append(&mut self, key: K, value: V) -> Option<(K, V)> {
        if let Some(last) = self.values.lm_last() {
            if last.0 >= &key {
                return Some((key, value));
            }
        }

        self.values.lm_push(key, value);
        None
    }

    /// Insert `value` with `key`, returning the existing value if it exists.
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// let mut map = LiteMap::new_vec();
    /// map.insert(1, "one");
    /// map.insert(2, "two");
    /// assert_eq!(map.get(&1), Some(&"one"));
    /// assert_eq!(map.get(&3), None);
    /// ```
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        self.insert_save_key(key, value).map(|(_, v)| v)
    }

    /// Version of [`Self::insert()`] that returns both the key and the old value.
    fn insert_save_key(&mut self, key: K, value: V) -> Option<(K, V)> {
        match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
            #[allow(clippy::unwrap_used)] // Index came from binary_search
            Ok(found) => Some((
                key,
                mem::replace(self.values.lm_get_mut(found).unwrap().1, value),
            )),
            Err(ins) => {
                self.values.lm_insert(ins, key, value);
                None
            }
        }
    }

    /// Attempts to insert a unique entry into the map.
    ///
    /// If `key` is not already in the map, inserts it with the corresponding `value`
    /// and returns `None`.
    ///
    /// If `key` is already in the map, no change is made to the map, and the key and value
    /// are returned back to the caller.
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// let mut map = LiteMap::new_vec();
    /// map.insert(1, "one");
    /// map.insert(3, "three");
    ///
    /// // 2 is not yet in the map...
    /// assert_eq!(map.try_insert(2, "two"), None);
    /// assert_eq!(map.len(), 3);
    ///
    /// // ...but now it is.
    /// assert_eq!(map.try_insert(2, "TWO"), Some((2, "TWO")));
    /// assert_eq!(map.len(), 3);
    /// ```
    pub fn try_insert(&mut self, key: K, value: V) -> Option<(K, V)> {
        match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
            Ok(_) => Some((key, value)),
            Err(ins) => {
                self.values.lm_insert(ins, key, value);
                None
            }
        }
    }

    /// Attempts to insert a unique entry into the map.
    ///
    /// If `key` is not already in the map, invokes the closure to compute `value`, inserts
    /// the pair into the map, and returns a reference to the value. The closure is passed
    /// a reference to the `key` argument.
    ///
    /// If `key` is already in the map, a reference to the existing value is returned.
    ///
    /// Additionally, the index of the value in the map is returned. If it is not desirable
    /// to hold on to the mutable reference's lifetime, the index can be used to access the
    /// element via [`LiteMap::get_indexed()`].
    ///
    /// The closure returns a `Result` to allow for a fallible insertion function. If the
    /// creation of `value` is infallible, you can use [`core::convert::Infallible`].
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// /// Helper function to unwrap an `Infallible` result from the insertion function
    /// fn unwrap_infallible<T>(result: Result<T, core::convert::Infallible>) -> T {
    ///     result.unwrap_or_else(|never| match never {})
    /// }
    ///
    /// let mut map = LiteMap::new_vec();
    /// map.insert(1, "one");
    /// map.insert(3, "three");
    ///
    /// // 2 is not yet in the map...
    /// let result1 = unwrap_infallible(
    ///     map.try_get_or_insert(2, |_| Ok("two"))
    /// );
    /// assert_eq!(result1.1, &"two");
    /// assert_eq!(map.len(), 3);
    ///
    /// // ...but now it is.
    /// let result1 = unwrap_infallible(
    ///     map.try_get_or_insert(2, |_| Ok("TWO"))
    /// );
    /// assert_eq!(result1.1, &"two");
    /// assert_eq!(map.len(), 3);
    /// ```
    pub fn try_get_or_insert<E>(
        &mut self,
        key: K,
        value: impl FnOnce(&K) -> Result<V, E>,
    ) -> Result<(usize, &V), E> {
        let idx = match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
            Ok(idx) => idx,
            Err(idx) => {
                let value = value(&key)?;
                self.values.lm_insert(idx, key, value);
                idx
            }
        };
        #[allow(clippy::unwrap_used)] // item at idx found or inserted above
        Ok((idx, self.values.lm_get(idx).unwrap().1))
    }

    /// Remove the value at `key`, returning it if it exists.
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// let mut map = LiteMap::new_vec();
    /// map.insert(1, "one");
    /// map.insert(2, "two");
    /// assert_eq!(map.remove(&1), Some("one"));
    /// assert_eq!(map.get(&1), None);
    /// ```
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        match self.values.lm_binary_search_by(|k| k.borrow().cmp(key)) {
            Ok(found) => Some(self.values.lm_remove(found).1),
            Err(_) => None,
        }
    }
}

impl<K, V, S> LiteMap<K, V, S>
where
    K: Ord,
    S: StoreIntoIterator<K, V> + StoreFromIterator<K, V>,
{
    /// Insert all elements from `other` into this `LiteMap`.
    ///
    /// If `other` contains keys that already exist in `self`, the values in `other` replace the
    /// corresponding ones in `self`, and the rejected items from `self` are returned as a new
    /// `LiteMap`. Otherwise, `None` is returned.
    ///
    /// The implementation of this function is optimized if `self` and `other` have no overlap.
    ///
    /// # Examples
    ///
    /// ```
    /// use litemap::LiteMap;
    ///
    /// let mut map1 = LiteMap::new_vec();
    /// map1.insert(1, "one");
    /// map1.insert(2, "two");
    ///
    /// let mut map2 = LiteMap::new_vec();
    /// map2.insert(2, "TWO");
    /// map2.insert(4, "FOUR");
    ///
    /// let leftovers = map1.extend_from_litemap(map2);
    ///
    /// assert_eq!(map1.len(), 3);
    /// assert_eq!(map1.get(&1), Some("one").as_ref());
    /// assert_eq!(map1.get(&2), Some("TWO").as_ref());
    /// assert_eq!(map1.get(&4), Some("FOUR").as_ref());
    ///
    /// let map3 = leftovers.expect("Duplicate keys");
    /// assert_eq!(map3.len(), 1);
    /// assert_eq!(map3.get(&2), Some("two").as_ref());
    /// ```
    pub fn extend_from_litemap(&mut self, other: Self) -> Option<Self> {
        if self.is_empty() {
            self.values = other.values;
            return None;
        }
        if other.is_empty() {
            return None;
        }
        if self.last().map(|(k, _)| k) < other.first().map(|(k, _)| k) {
            // append other to self
            self.values.lm_extend_end(other.values);
            None
        } else if self.first().map(|(k, _)| k) > other.last().map(|(k, _)| k) {
            // prepend other to self
            self.values.lm_extend_start(other.values);
            None
        } else {
            // insert every element
            let leftover_tuples = other
                .values
                .lm_into_iter()
                .filter_map(|(k, v)| self.insert_save_key(k, v))
                .collect();
            let ret = LiteMap {
                values: leftover_tuples,
                _key_type: PhantomData,
                _value_type: PhantomData,
            };
            if ret.is_empty() {
                None
            } else {
                Some(ret)
            }
        }
    }
}

impl<K, V, S> Default for LiteMap<K, V, S>
where
    S: Store<K, V> + Default,
{
    fn default() -> Self {
        Self {
            values: S::default(),
            _key_type: PhantomData,
            _value_type: PhantomData,
        }
    }
}
impl<K, V, S> Index<&'_ K> for LiteMap<K, V, S>
where
    K: Ord,
    S: Store<K, V>,
{
    type Output = V;
    fn index(&self, key: &K) -> &V {
        #[allow(clippy::panic)] // documented
        match self.get(key) {
            Some(v) => v,
            None => panic!("no entry found for key"),
        }
    }
}
impl<K, V, S> IndexMut<&'_ K> for LiteMap<K, V, S>
where
    K: Ord,
    S: StoreMut<K, V>,
{
    fn index_mut(&mut self, key: &K) -> &mut V {
        #[allow(clippy::panic)] // documented
        match self.get_mut(key) {
            Some(v) => v,
            None => panic!("no entry found for key"),
        }
    }
}
impl<K, V, S> FromIterator<(K, V)> for LiteMap<K, V, S>
where
    K: Ord,
    S: StoreFromIterable<K, V>,
{
    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
        let values = S::lm_sort_from_iter(iter);
        Self::from_sorted_store_unchecked(values)
    }
}

impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
where
    S: StoreIterable<'a, K, V>,
{
    /// Produce an ordered iterator over key-value pairs
    pub fn iter(&'a self) -> impl DoubleEndedIterator<Item = (&'a K, &'a V)> {
        self.values.lm_iter()
    }

    /// Produce an ordered iterator over keys
    pub fn iter_keys(&'a self) -> impl DoubleEndedIterator<Item = &'a K> {
        self.values.lm_iter().map(|val| val.0)
    }

    /// Produce an iterator over values, ordered by their keys
    pub fn iter_values(&'a self) -> impl DoubleEndedIterator<Item = &'a V> {
        self.values.lm_iter().map(|val| val.1)
    }
}

impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
where
    S: StoreIterableMut<'a, K, V>,
{
    /// Produce an ordered mutable iterator over key-value pairs
    pub fn iter_mut(&'a mut self) -> impl DoubleEndedIterator<Item = (&'a K, &'a mut V)> {
        self.values.lm_iter_mut()
    }
}

impl<K, V, S> IntoIterator for LiteMap<K, V, S>
where
    S: StoreIntoIterator<K, V>,
{
    type Item = (K, V);
    type IntoIter = S::KeyValueIntoIter;

    fn into_iter(self) -> Self::IntoIter {
        self.values.lm_into_iter()
    }
}

impl<K, V, S> LiteMap<K, V, S>
where
    S: StoreMut<K, V>,
{
    /// Retains only the elements specified by the predicate.
    ///
    /// In other words, remove all elements such that `f((&k, &v))` returns `false`.
    ///
    /// # Example
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// let mut map = LiteMap::new_vec();
    /// map.insert(1, "one");
    /// map.insert(2, "two");
    /// map.insert(3, "three");
    ///
    /// // Retain elements with odd keys
    /// map.retain(|k, _| k % 2 == 1);
    ///
    /// assert_eq!(map.get(&1), Some(&"one"));
    /// assert_eq!(map.get(&2), None);
    /// ```
    #[inline]
    pub fn retain<F>(&mut self, predicate: F)
    where
        F: FnMut(&K, &V) -> bool,
    {
        self.values.lm_retain(predicate)
    }
}

impl<'a, K, V> LiteMap<K, V, &'a [(K, V)]> {
    /// Const version of [`LiteMap::len()`] for a slice store.
    ///
    /// Note: This function will no longer be needed if const trait behavior is stabilized.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// static map: LiteMap<&str, usize, &[(&str, usize)]> =
    ///     LiteMap::from_sorted_store_unchecked(&[("a", 11), ("b", 22)]);
    /// static len: usize = map.const_len();
    /// assert_eq!(len, 2);
    /// ```
    #[inline]
    pub const fn const_len(&self) -> usize {
        self.values.len()
    }

    /// Const version of [`LiteMap::is_empty()`] for a slice store.
    ///
    /// Note: This function will no longer be needed if const trait behavior is stabilized.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// static map: LiteMap<&str, usize, &[(&str, usize)]> =
    ///     LiteMap::from_sorted_store_unchecked(&[]);
    /// static is_empty: bool = map.const_is_empty();
    /// assert!(is_empty);
    /// ```
    #[inline]
    pub const fn const_is_empty(&self) -> bool {
        self.values.is_empty()
    }

    /// Const version of [`LiteMap::get_indexed()`] for a slice store.
    ///
    /// Note: This function will no longer be needed if const trait behavior is stabilized.
    ///
    /// # Panics
    ///
    /// Panics if the index is out of bounds.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// static map: LiteMap<&str, usize, &[(&str, usize)]> =
    ///     LiteMap::from_sorted_store_unchecked(&[("a", 11), ("b", 22)]);
    /// static t: &(&str, usize) = map.const_get_indexed_or_panic(0);
    /// assert_eq!(t.0, "a");
    /// assert_eq!(t.1, 11);
    /// ```
    #[inline]
    #[allow(clippy::indexing_slicing)] // documented
    pub const fn const_get_indexed_or_panic(&self, index: usize) -> &'a (K, V) {
        &self.values[index]
    }
}

const fn const_cmp_bytes(a: &[u8], b: &[u8]) -> Ordering {
    let (max, default) = if a.len() == b.len() {
        (a.len(), Ordering::Equal)
    } else if a.len() < b.len() {
        (a.len(), Ordering::Less)
    } else {
        (b.len(), Ordering::Greater)
    };
    let mut i = 0;
    #[allow(clippy::indexing_slicing)] // indexes in range by above checks
    while i < max {
        if a[i] == b[i] {
            i += 1;
            continue;
        } else if a[i] < b[i] {
            return Ordering::Less;
        } else {
            return Ordering::Greater;
        }
    }
    default
}

impl<'a, V> LiteMap<&'a str, V, &'a [(&'a str, V)]> {
    /// Const function to get the value associated with a `&str` key, if it exists.
    ///
    /// Also returns the index of the value.
    ///
    /// Note: This function will no longer be needed if const trait behavior is stabilized.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// static map: LiteMap<&str, usize, &[(&str, usize)]> =
    ///     LiteMap::from_sorted_store_unchecked(&[
    ///         ("abc", 11),
    ///         ("bcd", 22),
    ///         ("cde", 33),
    ///         ("def", 44),
    ///         ("efg", 55),
    ///     ]);
    ///
    /// static d: Option<(usize, &usize)> = map.const_get_with_index("def");
    /// assert_eq!(d, Some((3, &44)));
    ///
    /// static n: Option<(usize, &usize)> = map.const_get_with_index("dng");
    /// assert_eq!(n, None);
    /// ```
    pub const fn const_get_with_index(&self, key: &str) -> Option<(usize, &'a V)> {
        let mut i = 0;
        let mut j = self.const_len();
        while i < j {
            let mid = (i + j) / 2;
            #[allow(clippy::indexing_slicing)] // in range
            let x = &self.values[mid];
            match const_cmp_bytes(key.as_bytes(), x.0.as_bytes()) {
                Ordering::Equal => return Some((mid, &x.1)),
                Ordering::Greater => i = mid + 1,
                Ordering::Less => j = mid,
            };
        }
        None
    }
}

impl<'a, V> LiteMap<&'a [u8], V, &'a [(&'a [u8], V)]> {
    /// Const function to get the value associated with a `&[u8]` key, if it exists.
    ///
    /// Also returns the index of the value.
    ///
    /// Note: This function will no longer be needed if const trait behavior is stabilized.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use litemap::LiteMap;
    ///
    /// static map: LiteMap<&[u8], usize, &[(&[u8], usize)]> =
    ///     LiteMap::from_sorted_store_unchecked(&[
    ///         (b"abc", 11),
    ///         (b"bcd", 22),
    ///         (b"cde", 33),
    ///         (b"def", 44),
    ///         (b"efg", 55),
    ///     ]);
    ///
    /// static d: Option<(usize, &usize)> = map.const_get_with_index(b"def");
    /// assert_eq!(d, Some((3, &44)));
    ///
    /// static n: Option<(usize, &usize)> = map.const_get_with_index(b"dng");
    /// assert_eq!(n, None);
    /// ```
    pub const fn const_get_with_index(&self, key: &[u8]) -> Option<(usize, &'a V)> {
        let mut i = 0;
        let mut j = self.const_len();
        while i < j {
            let mid = (i + j) / 2;
            #[allow(clippy::indexing_slicing)] // in range
            let x = &self.values[mid];
            match const_cmp_bytes(key, x.0) {
                Ordering::Equal => return Some((mid, &x.1)),
                Ordering::Greater => i = mid + 1,
                Ordering::Less => j = mid,
            };
        }
        None
    }
}

macro_rules! impl_const_get_with_index_for_integer {
    ($integer:ty) => {
        impl<'a, V> LiteMap<$integer, V, &'a [($integer, V)]> {
            /// Const function to get the value associated with an integer key, if it exists.
            ///
            /// Note: This function will no longer be needed if const trait behavior is stabilized.
            ///
            /// Also returns the index of the value.
            pub const fn const_get_with_index(&self, key: $integer) -> Option<(usize, &'a V)> {
                let mut i = 0;
                let mut j = self.const_len();
                while i < j {
                    let mid = (i + j) / 2;
                    #[allow(clippy::indexing_slicing)] // in range
                    let x = &self.values[mid];
                    if key == x.0 {
                        return Some((mid, &x.1));
                    } else if key > x.0 {
                        i = mid + 1;
                    } else {
                        j = mid;
                    }
                }
                return None;
            }
        }
    };
}

impl_const_get_with_index_for_integer!(u8);
impl_const_get_with_index_for_integer!(u16);
impl_const_get_with_index_for_integer!(u32);
impl_const_get_with_index_for_integer!(u64);
impl_const_get_with_index_for_integer!(u128);
impl_const_get_with_index_for_integer!(usize);
impl_const_get_with_index_for_integer!(i8);
impl_const_get_with_index_for_integer!(i16);
impl_const_get_with_index_for_integer!(i32);
impl_const_get_with_index_for_integer!(i64);
impl_const_get_with_index_for_integer!(i128);
impl_const_get_with_index_for_integer!(isize);

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn from_iterator() {
        let mut expected = LiteMap::with_capacity(4);
        expected.insert(1, "updated-one");
        expected.insert(2, "original-two");
        expected.insert(3, "original-three");
        expected.insert(4, "updated-four");

        let actual = [
            (1, "original-one"),
            (2, "original-two"),
            (4, "original-four"),
            (4, "updated-four"),
            (1, "updated-one"),
            (3, "original-three"),
        ]
        .into_iter()
        .collect::<LiteMap<_, _>>();

        assert_eq!(expected, actual);
    }
    fn make_13() -> LiteMap<usize, &'static str> {
        let mut result = LiteMap::new();
        result.insert(1, "one");
        result.insert(3, "three");
        result
    }

    fn make_24() -> LiteMap<usize, &'static str> {
        let mut result = LiteMap::new();
        result.insert(2, "TWO");
        result.insert(4, "FOUR");
        result
    }

    fn make_46() -> LiteMap<usize, &'static str> {
        let mut result = LiteMap::new();
        result.insert(4, "four");
        result.insert(6, "six");
        result
    }

    #[test]
    fn extend_from_litemap_append() {
        let mut map = LiteMap::new();
        map.extend_from_litemap(make_13())
            .ok_or(())
            .expect_err("Append to empty map");
        map.extend_from_litemap(make_46())
            .ok_or(())
            .expect_err("Append to lesser map");
        assert_eq!(map.len(), 4);
    }

    #[test]
    fn extend_from_litemap_prepend() {
        let mut map = LiteMap::new();
        map.extend_from_litemap(make_46())
            .ok_or(())
            .expect_err("Prepend to empty map");
        map.extend_from_litemap(make_13())
            .ok_or(())
            .expect_err("Prepend to lesser map");
        assert_eq!(map.len(), 4);
    }

    #[test]
    fn extend_from_litemap_insert() {
        let mut map = LiteMap::new();
        map.extend_from_litemap(make_13())
            .ok_or(())
            .expect_err("Append to empty map");
        map.extend_from_litemap(make_24())
            .ok_or(())
            .expect_err("Insert with no conflict");
        map.extend_from_litemap(make_46())
            .ok_or(())
            .expect("Insert with conflict");
        assert_eq!(map.len(), 5);
    }

    #[test]
    fn test_const_cmp_bytes() {
        let strs = &["a", "aa", "abc", "abde", "bcd", "bcde"];
        for i in 0..strs.len() {
            for j in 0..strs.len() {
                let a = strs[i].as_bytes();
                let b = strs[j].as_bytes();
                assert_eq!(a.cmp(b), const_cmp_bytes(a, b));
            }
        }
    }

    #[test]
    fn into_iterator() {
        let mut map = LiteMap::<_, _, Vec<(_, _)>>::new();
        map.insert(4, "four");
        map.insert(6, "six");
        let mut reference = vec![(6, "six"), (4, "four")];

        for i in map {
            let r = reference.pop().unwrap();
            assert_eq!(r, i);
        }
        assert!(reference.is_empty());
    }
}