Revision control
Copy as Markdown
Other Tools
// 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
//! Traits for pluggable LiteMap backends.
//!
//! By default, LiteMap is backed by a `Vec`. However, in some environments, it may be desirable
//! to use a different data store while still using LiteMap to manage proper ordering of items.
//!
//! The general guidelines for a performant data store are:
//!
//! 1. Must support efficient random access for binary search
//! 2. Should support efficient append operations for deserialization
//!
//! To plug a custom data store into LiteMap, implement:
//!
//! - [`Store`] for most of the methods
//! - [`StoreIterable`] for methods that return iterators
//! - [`StoreFromIterator`] to enable `FromIterator` for LiteMap
//!
//! To test your implementation, enable the `"testing"` Cargo feature and use [`check_store()`].
//!
//! [`check_store()`]: crate::testing::check_store
mod slice_impl;
#[cfg(feature = "alloc")]
mod vec_impl;
use core::cmp::Ordering;
use core::iter::DoubleEndedIterator;
use core::iter::FromIterator;
use core::iter::Iterator;
use core::ops::Range;
/// Trait to enable const construction of empty store.
pub trait StoreConstEmpty<K: ?Sized, V: ?Sized> {
/// An empty store
const EMPTY: Self;
}
/// Trait to enable pluggable backends for LiteMap.
///
/// Some methods have default implementations provided for convenience; however, it is generally
/// better to implement all methods that your data store supports.
pub trait Store<K: ?Sized, V: ?Sized>: Sized {
/// Returns the number of elements in the store.
fn lm_len(&self) -> usize;
/// Returns whether the store is empty (contains 0 elements).
fn lm_is_empty(&self) -> bool {
self.lm_len() == 0
}
/// Gets a key/value pair at the specified index.
fn lm_get(&self, index: usize) -> Option<(&K, &V)>;
/// Gets the last element in the store, or `None` if the store is empty.
fn lm_last(&self) -> Option<(&K, &V)> {
let len = self.lm_len();
if len == 0 {
None
} else {
self.lm_get(len - 1)
}
}
/// Searches the store for a particular element with a comparator function.
///
/// See the binary search implementation on `slice` for more information.
fn lm_binary_search_by<F>(&self, cmp: F) -> Result<usize, usize>
where
F: FnMut(&K) -> Ordering;
}
pub trait StoreFromIterable<K, V>: Store<K, V> {
/// Create a sorted store from `iter`.
fn lm_sort_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self;
}
pub trait StoreSlice<K: ?Sized, V: ?Sized>: Store<K, V> {
type Slice: ?Sized;
fn lm_get_range(&self, range: Range<usize>) -> Option<&Self::Slice>;
}
pub trait StoreMut<K, V>: Store<K, V> {
/// Creates a new store with the specified capacity hint.
///
/// Implementations may ignore the argument if they do not support pre-allocating capacity.
fn lm_with_capacity(capacity: usize) -> Self;
/// Reserves additional capacity in the store.
///
/// Implementations may ignore the argument if they do not support pre-allocating capacity.
fn lm_reserve(&mut self, additional: usize);
/// Gets a key/value pair at the specified index, with a mutable value.
fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)>;
/// Pushes one additional item onto the store.
fn lm_push(&mut self, key: K, value: V);
/// Inserts an item at a specific index in the store.
///
/// # Panics
///
/// Panics if `index` is greater than the length.
fn lm_insert(&mut self, index: usize, key: K, value: V);
/// Removes an item at a specific index in the store.
///
/// # Panics
///
/// Panics if `index` is greater than the length.
fn lm_remove(&mut self, index: usize) -> (K, V);
/// Removes all items from the store.
fn lm_clear(&mut self);
/// Retains items satisfying a predicate in this store.
fn lm_retain<F>(&mut self, mut predicate: F)
where
F: FnMut(&K, &V) -> bool,
{
let mut i = 0;
while i < self.lm_len() {
#[allow(clippy::unwrap_used)] // i is in range
let (k, v) = self.lm_get(i).unwrap();
if predicate(k, v) {
i += 1;
} else {
self.lm_remove(i);
}
}
}
}
/// Iterator methods for the LiteMap store.
pub trait StoreIterable<'a, K: 'a + ?Sized, V: 'a + ?Sized>: Store<K, V> {
type KeyValueIter: Iterator<Item = (&'a K, &'a V)> + DoubleEndedIterator + 'a;
/// Returns an iterator over key/value pairs.
fn lm_iter(&'a self) -> Self::KeyValueIter;
}
pub trait StoreIterableMut<'a, K: 'a, V: 'a>: StoreMut<K, V> + StoreIterable<'a, K, V> {
type KeyValueIterMut: Iterator<Item = (&'a K, &'a mut V)> + DoubleEndedIterator + 'a;
/// Returns an iterator over key/value pairs, with a mutable value.
fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut;
}
pub trait StoreIntoIterator<K, V>: StoreMut<K, V> {
type KeyValueIntoIter: Iterator<Item = (K, V)>;
/// Returns an iterator that moves every item from this store.
fn lm_into_iter(self) -> Self::KeyValueIntoIter;
/// Adds items from another store to the end of this store.
fn lm_extend_end(&mut self, other: Self)
where
Self: Sized,
{
for item in other.lm_into_iter() {
self.lm_push(item.0, item.1);
}
}
/// Adds items from another store to the beginning of this store.
fn lm_extend_start(&mut self, other: Self)
where
Self: Sized,
{
for (i, item) in other.lm_into_iter().enumerate() {
self.lm_insert(i, item.0, item.1);
}
}
}
/// A store that can be built from a tuple iterator.
pub trait StoreFromIterator<K, V>: FromIterator<(K, V)> {}