vendor/litemap/src/store/mod.rs

   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 //! Traits for pluggable LiteMap backends.
   6 //!
   7 //! By default, LiteMap is backed by a `Vec`. However, in some environments, it may be desirable
   8 //! to use a different data store while still using LiteMap to manage proper ordering of items.
   9 //!
  10 //! The general guidelines for a performant data store are:
  11 //!
  12 //! 1. Must support efficient random access for binary search
  13 //! 2. Should support efficient append operations for deserialization
  14 //!
  15 //! To plug a custom data store into LiteMap, implement:
  16 //!
  17 //! - [`Store`] for most of the methods
  18 //! - [`StoreIterable`] for methods that return iterators
  19 //! - [`StoreFromIterator`] to enable `FromIterator` for LiteMap
  20 //!
  21 //! To test your implementation, enable the `"testing"` feature and use [`check_store()`].
  22 //!
  23 //! [`check_store()`]: crate::testing::check_store
  24
  25 mod slice_impl;
  26 #[cfg(feature = "alloc")]
  27 mod vec_impl;
  28
  29 use core::cmp::Ordering;
  30 use core::iter::DoubleEndedIterator;
  31 use core::iter::FromIterator;
  32 use core::iter::Iterator;
  33
  34 /// Trait to enable const construction of empty store.
  35 pub trait StoreConstEmpty<K: ?Sized, V: ?Sized> {
  36     /// An empty store
  37     const EMPTY: Self;
  38 }
  39
  40 /// Trait to enable pluggable backends for LiteMap.
  41 ///
  42 /// Some methods have default implementations provided for convenience; however, it is generally
  43 /// better to implement all methods that your data store supports.
  44 pub trait Store<K: ?Sized, V: ?Sized>: Sized {
  45     /// Returns the number of elements in the store.
  46     fn lm_len(&self) -> usize;
  47
  48     /// Returns whether the store is empty (contains 0 elements).
  49     fn lm_is_empty(&self) -> bool {
  50         self.lm_len() == 0
  51     }
  52
  53     /// Gets a key/value pair at the specified index.
  54     fn lm_get(&self, index: usize) -> Option<(&K, &V)>;
  55
  56     /// Gets the last element in the store, or None if the store is empty.
  57     fn lm_last(&self) -> Option<(&K, &V)> {
  58         let len = self.lm_len();
  59         if len == 0 {
  60             None
  61         } else {
  62             self.lm_get(len - 1)
  63         }
  64     }
  65
  66     /// Searches the store for a particular element with a comparator function.
  67     ///
  68     /// See the binary search implementation on `slice` for more information.
  69     fn lm_binary_search_by<F>(&self, cmp: F) -> Result<usize, usize>
  70     where
  71         F: FnMut(&K) -> Ordering;
  72 }
  73
  74 pub trait StoreMut<K, V>: Store<K, V> {
  75     /// Creates a new store with the specified capacity hint.
  76     ///
  77     /// Implementations may ignore the argument if they do not support pre-allocating capacity.
  78     fn lm_with_capacity(capacity: usize) -> Self;
  79
  80     /// Reserves additional capacity in the store.
  81     ///
  82     /// Implementations may ignore the argument if they do not support pre-allocating capacity.
  83     fn lm_reserve(&mut self, additional: usize);
  84
  85     /// Gets a key/value pair at the specified index, with a mutable value.
  86     fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)>;
  87     /// Pushes one additional item onto the store.
  88     fn lm_push(&mut self, key: K, value: V);
  89
  90     /// Inserts an item at a specific index in the store.
  91     ///
  92     /// # Panics
  93     ///
  94     /// Panics if `index` is greater than the length.
  95     fn lm_insert(&mut self, index: usize, key: K, value: V);
  96
  97     /// Removes an item at a specific index in the store.
  98     ///
  99     /// # Panics
 100     ///
 101     /// Panics if `index` is greater than the length.
 102     fn lm_remove(&mut self, index: usize) -> (K, V);
 103
 104     /// Removes all items from the store.
 105     fn lm_clear(&mut self);
 106
 107     /// Retains items satisfying a predicate in this store.
 108     fn lm_retain<F>(&mut self, mut predicate: F)
 109     where
 110         F: FnMut(&K, &V) -> bool,
 111     {
 112         let mut i = 0;
 113         while i < self.lm_len() {
 114             #[allow(clippy::unwrap_used)] // i is in range
 115             let (k, v) = self.lm_get(i).unwrap();
 116             if predicate(k, v) {
 117                 i += 1;
 118             } else {
 119                 self.lm_remove(i);
 120             }
 121         }
 122     }
 123 }
 124
 125 /// Iterator methods for the LiteMap store.
 126 pub trait StoreIterable<'a, K: 'a, V: 'a>: Store<K, V> {
 127     type KeyValueIter: Iterator<Item = (&'a K, &'a V)> + DoubleEndedIterator + 'a;
 128
 129     /// Returns an iterator over key/value pairs.
 130     fn lm_iter(&'a self) -> Self::KeyValueIter;
 131 }
 132
 133 pub trait StoreIterableMut<'a, K: 'a, V: 'a>: StoreMut<K, V> + StoreIterable<'a, K, V> {
 134     type KeyValueIterMut: Iterator<Item = (&'a K, &'a mut V)> + DoubleEndedIterator + 'a;
 135     type KeyValueIntoIter: Iterator<Item = (K, V)>;
 136
 137     /// Returns an iterator over key/value pairs, with a mutable value.
 138     fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut;
 139
 140     /// Returns an iterator that moves every item from this store.
 141     fn lm_into_iter(self) -> Self::KeyValueIntoIter;
 142
 143     /// Adds items from another store to the end of this store.
 144     fn lm_extend_end(&mut self, other: Self)
 145     where
 146         Self: Sized,
 147     {
 148         for item in other.lm_into_iter() {
 149             self.lm_push(item.0, item.1);
 150         }
 151     }
 152
 153     /// Adds items from another store to the beginning of this store.
 154     fn lm_extend_start(&mut self, other: Self)
 155     where
 156         Self: Sized,
 157     {
 158         for (i, item) in other.lm_into_iter().enumerate() {
 159             self.lm_insert(i, item.0, item.1);
 160         }
 161     }
 162 }
 163
 164 /// A store that can be built from a tuple iterator.
 165 pub trait StoreFromIterator<K, V>: FromIterator<(K, V)> {}