kvtree/
key.rs

1//! Key Module
2
3use crate::mask::{Atom, Mask};
4use std::{
5    borrow::Borrow,
6    cmp::Ordering as StdOrdering,
7    fmt::Debug,
8    ops::{
9        Add, ControlFlow, Index, Range, RangeFrom, RangeFull, RangeInclusive, RangeTo,
10        RangeToInclusive,
11    },
12    slice::SliceIndex,
13};
14
15/// Key comparaison result
16#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
17pub enum Ordering {
18    /// An ordering where a compared key is equal to another.
19    Equal,
20    /// An ordering where a compared key is a parent to another.
21    Parent,
22    /// An ordering where a compared key is a child to another.
23    Child,
24    /// An ordering where a compared key share a common prefix and the divergent part is less than another.
25    Less,
26    /// An ordering where a compared key share a common prefix and the divergent part is greater than another.
27    Greater,
28}
29
30impl AsRef<StdOrdering> for Ordering {
31    fn as_ref(&self) -> &StdOrdering {
32        match self {
33            Ordering::Equal => &StdOrdering::Equal,
34            Ordering::Parent => &StdOrdering::Less,
35            Ordering::Child => &StdOrdering::Greater,
36            Ordering::Less => &StdOrdering::Less,
37            Ordering::Greater => &StdOrdering::Greater,
38        }
39    }
40}
41
42impl From<Ordering> for StdOrdering {
43    fn from(value: Ordering) -> StdOrdering {
44        match value {
45            Ordering::Equal => StdOrdering::Equal,
46            Ordering::Parent => StdOrdering::Less,
47            Ordering::Child => StdOrdering::Greater,
48            Ordering::Less => StdOrdering::Less,
49            Ordering::Greater => StdOrdering::Greater,
50        }
51    }
52}
53
54/// Matches a single key part
55pub trait MatchAtom<K>: Send + Sync {
56    /// return true if the atom matches
57    fn match_atom(&self, atom: &K) -> bool;
58}
59
60/// Trait that matches keys
61pub trait Match<K>: Send + Sync {
62    /// Returns true if self matches the given [Key]
63    fn match_key(&self, key: &Key<K>) -> bool;
64
65    /// Returns true if self can match a children of the given [Key]
66    fn match_children(&self, key: &Key<K>) -> bool;
67}
68
69impl<K> MatchAtom<K> for () {
70    fn match_atom(&self, _: &K) -> bool {
71        true
72    }
73}
74
75impl<K> Match<K> for () {
76    fn match_key(&self, _: &Key<K>) -> bool {
77        true
78    }
79
80    fn match_children(&self, _: &Key<K>) -> bool {
81        true
82    }
83}
84
85impl<K> Match<K> for Range<Key<K>>
86where
87    K: Ord + Send + Sync,
88{
89    fn match_key(&self, key: &Key<K>) -> bool {
90        &self.start <= key && &self.end > key
91    }
92
93    fn match_children(&self, key: &Key<K>) -> bool {
94        self.match_key(key)
95    }
96}
97
98impl<K> Match<K> for RangeFrom<Key<K>>
99where
100    K: Ord + Send + Sync,
101{
102    fn match_key(&self, key: &Key<K>) -> bool {
103        &self.start <= key
104    }
105
106    fn match_children(&self, key: &Key<K>) -> bool {
107        self.match_key(key)
108    }
109}
110
111impl<K> Match<K> for RangeFull {
112    fn match_key(&self, _: &Key<K>) -> bool {
113        true
114    }
115
116    fn match_children(&self, _: &Key<K>) -> bool {
117        true
118    }
119}
120
121impl<K> Match<K> for RangeInclusive<Key<K>>
122where
123    K: Ord + Send + Sync,
124{
125    fn match_key(&self, key: &Key<K>) -> bool {
126        self.start() <= key && self.end() >= key
127    }
128
129    fn match_children(&self, key: &Key<K>) -> bool {
130        self.match_key(key)
131    }
132}
133
134impl<K> Match<K> for RangeTo<Key<K>>
135where
136    K: Ord + Send + Sync,
137{
138    fn match_key(&self, key: &Key<K>) -> bool {
139        &self.end > key
140    }
141
142    fn match_children(&self, key: &Key<K>) -> bool {
143        self.match_key(key)
144    }
145}
146
147impl<K> Match<K> for RangeToInclusive<Key<K>>
148where
149    K: Ord + Send + Sync,
150{
151    fn match_key(&self, key: &Key<K>) -> bool {
152        &self.end >= key
153    }
154
155    fn match_children(&self, key: &Key<K>) -> bool {
156        self.match_key(key)
157    }
158}
159
160/// Hierarchic key
161#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
162pub struct Key<K>(Box<[K]>);
163
164impl<K> Key<K> {
165    /// new key with 1 element
166    #[inline]
167    pub fn new(k: K) -> Self {
168        Key([k].into())
169    }
170
171    /// return true if this key contains no elements
172    #[inline]
173    pub fn is_empty(&self) -> bool {
174        self.0.is_empty()
175    }
176
177    /// number if elements in this key
178    #[inline]
179    pub fn len(&self) -> usize {
180        self.0.len()
181    }
182
183    /// reverse the order of elements in this key
184    #[inline]
185    pub fn reverse(&mut self) {
186        self.0.reverse()
187    }
188}
189
190impl<K> Key<K>
191where
192    K: Ord,
193{
194    /// Compare 2 keys and return the [Ordering] relative to self
195    ///
196    /// Example:
197    /// ```rust
198    /// # use kvtree::{Key, key};
199    /// let k1 = Key::new("a");
200    /// let k2 = Key::from(["a", "b"]);
201    ///
202    /// assert_eq!(k1.key_cmp(&k2), key::Ordering::Parent);
203    /// assert_eq!(k2.key_cmp(&k1), key::Ordering::Child);
204    /// assert_eq!(k2.key_cmp(&["a", "b"].into()), key::Ordering::Equal);
205    /// assert_eq!(k2.key_cmp(&["a", "a"].into()), key::Ordering::Greater);
206    /// assert_eq!(k1.key_cmp(&["b"].into()), key::Ordering::Less);
207    /// ```
208    #[inline]
209    pub fn key_cmp(&self, other: &Self) -> Ordering {
210        let nb = self.0.len().min(other.0.len());
211        match self
212            .0
213            .iter()
214            .zip(other.0.iter())
215            .take(nb)
216            .enumerate()
217            .try_fold(None, |x, (i, (l, r))| {
218                if l == r {
219                    ControlFlow::Continue(Some(i + 1))
220                } else {
221                    ControlFlow::Break(x)
222                }
223            }) {
224            ControlFlow::Break(Some(i)) | ControlFlow::Continue(Some(i)) => {
225                if i == self.len() && i == other.len() {
226                    Ordering::Equal
227                } else if i == self.len() {
228                    Ordering::Parent
229                } else if i == other.len() {
230                    Ordering::Child
231                } else {
232                    match self[i].cmp(&other[i]) {
233                        StdOrdering::Less => Ordering::Less,
234                        StdOrdering::Greater => Ordering::Greater,
235                        StdOrdering::Equal => unreachable!(),
236                    }
237                }
238            }
239            _ => match self.0.first().cmp(&other.0.first()) {
240                StdOrdering::Less => Ordering::Less,
241                StdOrdering::Equal => Ordering::Equal,
242                StdOrdering::Greater => Ordering::Greater,
243            },
244        }
245    }
246
247    // TODO: see if it's usefull to implement is_parent_of, is_children_of, etc...
248}
249
250impl<K: Clone> Key<K> {
251    /// creates a new key by cloning and concatenating other after self
252    ///
253    /// Example:
254    /// ```rust
255    /// # use kvtree::Key;
256    /// let k = Key::new("abc");
257    /// assert_eq!(k.join(&["def", "ghi"].into()), Key::from(["abc", "def", "ghi"]));
258    /// ```
259    pub fn join(&self, other: &Self) -> Self {
260        Self(self.into_iter().chain(other).cloned().collect())
261    }
262}
263
264impl<K: ToString> Key<K> {
265    /// create a string that concatenates all members of a key and separate them with `sep`
266    ///
267    /// Example:
268    /// ```rust
269    /// # use kvtree::Key;
270    /// assert_eq!(Key::new(1234).to_string("/"), "1234");
271    /// assert_eq!(Key::<i32>::from([1234, 5678]).to_string("/"), "1234/5678");
272    /// assert_eq!(Key::<&str>::from(["foo", "bar"]).to_string("."), "foo.bar");
273    /// ```
274    pub fn to_string(&self, sep: &str) -> String {
275        let mut out = String::new();
276        let len = self.len();
277        if !self.is_empty() {
278            for i in 0..(len - 1) {
279                out.push_str(&self[i].to_string());
280                out.push_str(sep);
281            }
282            out.push_str(&self[len - 1].to_string());
283        }
284        out
285    }
286}
287
288impl<K> From<Vec<K>> for Key<K> {
289    #[inline]
290    fn from(value: Vec<K>) -> Self {
291        Key(value.into_iter().collect())
292    }
293}
294
295impl<K, const N: usize> From<[K; N]> for Key<K> {
296    #[inline]
297    fn from(value: [K; N]) -> Self {
298        Key(value.into_iter().collect())
299    }
300}
301
302impl<K> From<&[K]> for Key<K>
303where
304    K: Clone,
305{
306    #[inline]
307    fn from(value: &[K]) -> Self {
308        Key(value.iter().cloned().collect())
309    }
310}
311
312impl<K> FromIterator<Key<K>> for Key<K> {
313    fn from_iter<T: IntoIterator<Item = Key<K>>>(iter: T) -> Self {
314        Key(iter.into_iter().flatten().collect())
315    }
316}
317
318impl<K> FromIterator<K> for Key<K> {
319    fn from_iter<T: IntoIterator<Item = K>>(iter: T) -> Self {
320        Key(iter.into_iter().collect())
321    }
322}
323
324impl<K> Add<K> for Key<K> {
325    type Output = Key<K>;
326
327    fn add(self, rhs: K) -> Self::Output {
328        Key(Vec::from(self.0)
329            .into_iter()
330            .chain([rhs])
331            .collect::<Box<[K]>>())
332    }
333}
334
335impl<K> Add<Key<K>> for Key<K> {
336    type Output = Key<K>;
337
338    fn add(self, rhs: Key<K>) -> Self::Output {
339        Key(Vec::from(self.0)
340            .into_iter()
341            .chain(Vec::from(rhs.0))
342            .collect::<Box<[K]>>())
343    }
344}
345
346impl<K, C> TryFrom<Mask<K, C>> for Key<K> {
347    type Error = Mask<K, C>;
348
349    fn try_from(value: Mask<K, C>) -> Result<Self, Self::Error> {
350        let mut r = Vec::with_capacity(value.len());
351        let mut it = value.into_iter();
352        while let Some(x) = it.next() {
353            match x {
354                Atom::Key(x) => r.push(x),
355                x @ (Atom::Any | Atom::Many | Atom::Other(_)) => {
356                    return Err(r
357                        .into_iter()
358                        .map(Atom::Key)
359                        .chain(std::iter::once(x))
360                        .chain(it)
361                        .collect())
362                }
363            }
364        }
365        Ok(r.into())
366    }
367}
368
369impl<K> AsRef<[K]> for Key<K> {
370    #[inline]
371    fn as_ref(&self) -> &[K] {
372        &self.0
373    }
374}
375
376impl<K> Borrow<[K]> for Key<K> {
377    #[inline]
378    fn borrow(&self) -> &[K] {
379        self.0.borrow()
380    }
381}
382
383impl<K, I> Index<I> for Key<K>
384where
385    I: SliceIndex<[K]>,
386{
387    type Output = <I as SliceIndex<[K]>>::Output;
388
389    #[inline]
390    fn index(&self, index: I) -> &Self::Output {
391        self.0.index(index)
392    }
393}
394
395impl<'a, K> IntoIterator for &'a Key<K> {
396    type Item = <&'a [K] as IntoIterator>::Item;
397    type IntoIter = <&'a [K] as IntoIterator>::IntoIter;
398
399    #[inline]
400    fn into_iter(self) -> Self::IntoIter {
401        self.0.iter()
402    }
403}
404
405impl<K> IntoIterator for Key<K> {
406    type Item = <Vec<K> as IntoIterator>::Item;
407    type IntoIter = <Vec<K> as IntoIterator>::IntoIter;
408
409    #[inline]
410    fn into_iter(self) -> Self::IntoIter {
411        Vec::from(self.0).into_iter()
412    }
413}
414
415impl<K: Ord> PartialOrd for Key<K> {
416    fn partial_cmp(&self, other: &Self) -> Option<StdOrdering> {
417        Some(self.cmp(other))
418    }
419}
420
421impl<K: Ord> Ord for Key<K> {
422    fn cmp(&self, other: &Self) -> StdOrdering {
423        self.key_cmp(other).into()
424    }
425}
426
427impl<K> Match<K> for Key<K>
428where
429    K: Ord + Send + Sync,
430{
431    fn match_key(&self, key: &Key<K>) -> bool {
432        self == key
433    }
434
435    fn match_children(&self, key: &Key<K>) -> bool {
436        matches!(self.key_cmp(key), Ordering::Child)
437    }
438}
439
440#[cfg(test)]
441mod tests {
442    use super::Key;
443    use crate::key::Ordering;
444
445    #[test]
446    fn test_key_cmp() {
447        let k: Key<&'static str> = Key(Box::new([]));
448        assert_eq!(k.key_cmp(&Key(Box::new([]))), Ordering::Equal);
449        assert_eq!(k.key_cmp(&Key::from(["a"])), Ordering::Less);
450        assert_eq!(Key::from(["a"]).key_cmp(&k), Ordering::Greater);
451        assert_eq!(
452            Key::from(["boo"]).key_cmp(&Key::from(["foo"])),
453            Ordering::Less
454        );
455        assert_eq!(
456            Key::from(["foo"]).key_cmp(&Key::from(["boo"])),
457            Ordering::Greater
458        );
459        assert_eq!(Key::from(["a"]).key_cmp(&Key::from(["a"])), Ordering::Equal);
460        assert_eq!(
461            Key::from(["a"]).key_cmp(&Key::from(["a", "b"])),
462            Ordering::Parent
463        );
464        assert_eq!(
465            Key::from(["a", "b"]).key_cmp(&Key::from(["a"])),
466            Ordering::Child
467        );
468        assert_eq!(
469            Key::from(["a", "b"]).key_cmp(&Key::from(["a", "c"])),
470            Ordering::Less
471        );
472        assert_eq!(
473            Key::from(["a", "c"]).key_cmp(&Key::from(["a", "b"])),
474            Ordering::Greater
475        );
476        assert_eq!(
477            Key::from(["a", "c", "a"]).key_cmp(&Key::from(["a", "b", "a"])),
478            Ordering::Greater
479        );
480        assert_eq!(
481            Key::from(["a", "b", "a"]).key_cmp(&Key::from(["a", "c", "a"])),
482            Ordering::Less
483        );
484        assert_eq!(
485            Key::from(["with"]).key_cmp(&Key::from(["uuid", "foo"])),
486            Ordering::Greater
487        );
488        assert_eq!(
489            Key::from(["uuid"]).key_cmp(&Key::from(["with"])),
490            Ordering::Less
491        );
492        assert_eq!(
493            Key::from(["a", "b"]).key_cmp(&Key::from(["b"])),
494            Ordering::Less
495        )
496    }
497}
kvtree/key.rs

kvtree/
key.rs
