fr-trie 0.0.4

Fuzzy Radix Trie
Documentation 
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

//! The Trie Key trait
use std::sync::Arc;
use serde::{Serialize, Deserialize};
use crate::matcher::{MatchType, StateSequence};

/// The Trie Key prefix trait
pub trait KeyPrefix {

    fn key_chars(&self) -> Vec<char>;

    fn key_len(&self) -> usize;

    fn empty() -> Self;

    fn new_from_key_prefix(&self, index: usize) -> Self;

    fn new_from_postfix(&self, index: usize) -> Self;

    #[inline]
    fn compiled(&self) -> Vec<Arc<StateSequence>> {
        let mut state_seq = Vec::new();
        let mut buff: Vec<char> = Vec::new();
        for ch in self.key_chars() {
            buff.push(ch);
        }
        if !buff.is_empty() {
            state_seq.push(Arc::new(StateSequence {
                match_type: MatchType::Literal,
                sequence: buff,
            }));
        }
        state_seq
    }
}

#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct TrieKey<K> {
    pub(crate) key: K,
    pub(crate) seq: Vec<Arc<StateSequence>>,
}

impl <K: KeyPrefix> TrieKey<K> {

    #[inline]
    pub fn new(key: K) -> Self {
        Self {
            seq: key.compiled(),
            key,
        }
    }

    #[inline]
    pub fn is_empty(&self) -> bool {
        self.seq.is_empty()
    }

    #[inline]
    pub fn lcp(&self, other: &Self) -> (usize, bool, bool) {
        let mut lcp = 0;
        let w0l = self.key.key_len();
        let w1l = other.key.key_len();
        let mlen = std::cmp::min(w0l, w1l);
        let mut w0i = self.key.key_chars().into_iter();
        let mut w1i = other.key.key_chars().into_iter();
        let mut preceeding = true;
        for _ in 0 .. mlen {
            let char0 = w0i.next().unwrap();
            let char1 = w1i.next().unwrap();
            if char0.eq(&char1) {
                lcp += 1;
            }
            else {
                if char1.lt(&char0) {
                    preceeding = false;
                }
                break;
            }
        }
        let full_match = w0l == w1l && lcp == w0l;
        (lcp, preceeding, full_match)
    }
}

impl KeyPrefix for String {

    #[inline]
    fn key_chars(&self) -> Vec<char> {
        self.chars().into_iter().collect()
    }

    #[inline]
    fn key_len(&self) -> usize {
        self.len()
    }

    #[inline]
    fn empty() -> Self {
        String::new()
    }

    #[inline]
    fn new_from_key_prefix(&self, index: usize) -> Self {
        self[..index].to_string()
    }

    #[inline]
    fn new_from_postfix(&self, index: usize) -> Self {
        self[index..].to_string()
    }
}

pub trait ValueMerge {
    fn merge(&self, other: &Self) -> Self;

    fn merge_mut(&mut self, other: &Self);
}