1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
// 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 ).
//! 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"` 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;
/// 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 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, V: 'a>: 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;
type KeyValueIntoIter: Iterator<Item = (K, V)>;
/// Returns an iterator over key/value pairs, with a mutable value.
fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut;
/// 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)> {}
|
