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