fr_trie/
key.rs

1//! The Trie Key trait
2use std::sync::Arc;
3use serde::{Serialize, Deserialize};
4use crate::matcher::{MatchType, StateSequence};
5
6/// The Trie Key prefix trait
7pub trait KeyPrefix {
8
9    fn key_chars(&self) -> Vec<char>;
10
11    fn key_len(&self) -> usize;
12
13    fn empty() -> Self;
14
15    fn new_from_key_prefix(&self, index: usize) -> Self;
16
17    fn new_from_postfix(&self, index: usize) -> Self;
18
19    #[inline]
20    fn compiled(&self) -> Vec<Arc<StateSequence>> {
21        let mut state_seq = Vec::new();
22        let mut buff: Vec<char> = Vec::new();
23        for ch in self.key_chars() {
24            buff.push(ch);
25        }
26        if !buff.is_empty() {
27            state_seq.push(Arc::new(StateSequence {
28                match_type: MatchType::Literal,
29                sequence: buff,
30            }));
31        }
32        state_seq
33    }
34}
35
36#[derive(Clone, Debug, Serialize, Deserialize)]
37pub struct TrieKey<K> {
38    pub(crate) key: K,
39    pub(crate) seq: Vec<Arc<StateSequence>>,
40}
41
42impl <K: KeyPrefix> TrieKey<K> {
43
44    #[inline]
45    pub fn new(key: K) -> Self {
46        Self {
47            seq: key.compiled(),
48            key,
49        }
50    }
51
52    #[inline]
53    pub fn is_empty(&self) -> bool {
54        self.seq.is_empty()
55    }
56
57    #[inline]
58    pub fn lcp(&self, other: &Self) -> (usize, bool, bool) {
59        let mut lcp = 0;
60        let w0l = self.key.key_len();
61        let w1l = other.key.key_len();
62        let mlen = std::cmp::min(w0l, w1l);
63        let mut w0i = self.key.key_chars().into_iter();
64        let mut w1i = other.key.key_chars().into_iter();
65        let mut preceeding = true;
66        for _ in 0 .. mlen {
67            let char0 = w0i.next().unwrap();
68            let char1 = w1i.next().unwrap();
69            if char0.eq(&char1) {
70                lcp += 1;
71            }
72            else {
73                if char1.lt(&char0) {
74                    preceeding = false;
75                }
76                break;
77            }
78        }
79        let full_match = w0l == w1l && lcp == w0l;
80        (lcp, preceeding, full_match)
81    }
82}
83
84impl KeyPrefix for String {
85
86    #[inline]
87    fn key_chars(&self) -> Vec<char> {
88        self.chars().into_iter().collect()
89    }
90
91    #[inline]
92    fn key_len(&self) -> usize {
93        self.len()
94    }
95
96    #[inline]
97    fn empty() -> Self {
98        String::new()
99    }
100
101    #[inline]
102    fn new_from_key_prefix(&self, index: usize) -> Self {
103        self[..index].to_string()
104    }
105
106    #[inline]
107    fn new_from_postfix(&self, index: usize) -> Self {
108        self[index..].to_string()
109    }
110}
111
112pub trait ValueMerge {
113    fn merge(&self, other: &Self) -> Self;
114
115    fn merge_mut(&mut self, other: &Self);
116}
fr_trie/key.rs

fr_trie/
key.rs
