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 | |
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 | use core::ops::Range; |
34 | |
35 | /// Trait to enable const construction of empty store. |
36 | pub 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. |
45 | pub 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 | |
75 | pub 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 | |
80 | pub 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 | |
86 | pub 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. |
139 | pub 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 | |
146 | pub 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. |
178 | pub trait StoreFromIterator<K, V>: FromIterator<(K, V)> {} |
179 | |