1 #[cfg(feature = "levenshtein")]
2 use fst::automaton::Levenshtein;
3 use fst::automaton::{Str, Subsequence};
4 #[cfg(feature = "levenshtein")]
5 use fst::raw::{Builder, Fst};
6 use fst::set::Set;
7 use fst::{self, Automaton, IntoStreamer, Streamer};
8
9 static WORDS: &'static str = include_str!("../data/words-10000");
10
get_set() -> Set<Vec<u8>>11 fn get_set() -> Set<Vec<u8>> {
12 Set::from_iter(WORDS.lines()).unwrap()
13 }
14
15 #[cfg(feature = "levenshtein")]
fst_set<I, S>(ss: I) -> Fst<Vec<u8>> where I: IntoIterator<Item = S>, S: AsRef<[u8]>,16 fn fst_set<I, S>(ss: I) -> Fst<Vec<u8>>
17 where
18 I: IntoIterator<Item = S>,
19 S: AsRef<[u8]>,
20 {
21 let mut bfst = Builder::memory();
22 let mut ss: Vec<Vec<u8>> =
23 ss.into_iter().map(|s| s.as_ref().to_vec()).collect();
24 ss.sort();
25 for s in ss.iter().into_iter() {
26 bfst.add(s).unwrap();
27 }
28 let fst = bfst.into_fst();
29 ss.dedup();
30 assert_eq!(fst.len(), ss.len());
31 fst
32 }
33
34 #[cfg(feature = "levenshtein")]
35 #[test]
levenshtein_simple()36 fn levenshtein_simple() {
37 let set = fst_set(vec!["woof", "wood", "banana"]);
38 let q = Levenshtein::new("woog", 1).unwrap();
39 let vs = set.search(&q).into_stream().into_byte_keys();
40 assert_eq!(vs, vec!["wood".as_bytes(), "woof".as_bytes()]);
41 }
42
43 #[cfg(feature = "levenshtein")]
44 #[test]
levenshtein_unicode()45 fn levenshtein_unicode() {
46 let set = fst_set(vec!["woof", "wood", "banana", "☃snowman☃"]);
47 let q = Levenshtein::new("snoman", 3).unwrap();
48 let vs = set.search(&q).into_stream().into_byte_keys();
49 assert_eq!(vs, vec!["☃snowman☃".as_bytes()]);
50 }
51
52 #[cfg(feature = "levenshtein")]
53 #[test]
complement_small()54 fn complement_small() {
55 let keys = vec!["fa", "fo", "fob", "focus", "foo", "food", "foul"];
56 let set = Set::from_iter(keys).unwrap();
57 let lev = Levenshtein::new("foo", 1).unwrap();
58 let stream = set.search(lev.complement()).into_stream();
59
60 let keys = stream.into_strs().unwrap();
61 assert_eq!(keys, vec!["fa", "focus", "foul"]);
62 }
63
64 #[cfg(feature = "levenshtein")]
65 #[test]
startswith_small()66 fn startswith_small() {
67 let keys = vec![
68 "", "cooing", "fa", "fo", "fob", "focus", "foo", "food", "foul",
69 "fritter", "frothing",
70 ];
71 let set = Set::from_iter(keys).unwrap();
72 let lev = Levenshtein::new("foo", 1).unwrap();
73 let stream = set.search(lev.starts_with()).into_stream();
74
75 let keys = stream.into_strs().unwrap();
76 assert_eq!(
77 keys,
78 vec![
79 "cooing", "fo", "fob", "focus", "foo", "food", "foul", "frothing",
80 ]
81 );
82 }
83
84 #[cfg(feature = "levenshtein")]
85 #[test]
intersection_small()86 fn intersection_small() {
87 let keys = vec!["fab", "fo", "fob", "focus", "foo", "food", "foul", "goo"];
88 let set = Set::from_iter(keys).unwrap();
89 let lev = Levenshtein::new("foo", 1).unwrap();
90 let prefix = Str::new("fo").starts_with();
91 let stream = set.search(lev.intersection(prefix)).into_stream();
92
93 let keys = stream.into_strs().unwrap();
94 assert_eq!(keys, vec!["fo", "fob", "foo", "food"]);
95 }
96
97 #[cfg(feature = "levenshtein")]
98 #[test]
union_small()99 fn union_small() {
100 let keys = vec!["fab", "fob", "focus", "foo", "food", "goo"];
101 let set = Set::from_iter(keys).unwrap();
102 let lev = Levenshtein::new("foo", 1).unwrap();
103 let prefix = Str::new("fo").starts_with();
104 let stream = set.search(lev.union(prefix)).into_stream();
105
106 let keys = stream.into_strs().unwrap();
107 assert_eq!(keys, vec!["fob", "focus", "foo", "food", "goo"]);
108 }
109
110 #[cfg(feature = "levenshtein")]
111 #[test]
intersection_large()112 fn intersection_large() {
113 use fst::set::OpBuilder;
114
115 let set = get_set();
116 let lev = Levenshtein::new("foo", 3).unwrap();
117 let prefix = Str::new("fa").starts_with();
118 let mut stream1 = set.search((&lev).intersection(&prefix)).into_stream();
119 let mut stream2 = OpBuilder::new()
120 .add(set.search(&lev))
121 .add(set.search(&prefix))
122 .intersection();
123 while let Some(key1) = stream1.next() {
124 assert_eq!(stream2.next(), Some(key1));
125 }
126 assert_eq!(stream2.next(), None);
127 }
128
129 #[cfg(feature = "levenshtein")]
130 #[test]
union_large()131 fn union_large() {
132 use fst::set::OpBuilder;
133
134 let set = get_set();
135 let lev = Levenshtein::new("foo", 3).unwrap();
136 let prefix = Str::new("fa").starts_with();
137 let mut stream1 = set.search((&lev).union(&prefix)).into_stream();
138 let mut stream2 = OpBuilder::new()
139 .add(set.search(&lev))
140 .add(set.search(&prefix))
141 .union();
142 while let Some(key1) = stream1.next() {
143 assert_eq!(stream2.next(), Some(key1));
144 }
145 assert_eq!(stream2.next(), None);
146 }
147
148 #[test]
str()149 fn str() {
150 let set = get_set();
151
152 let exact = Str::new("vatican");
153 let mut stream = set.search(&exact).into_stream();
154 assert_eq!(stream.next().unwrap(), b"vatican");
155 assert_eq!(stream.next(), None);
156
157 let exact_mismatch = Str::new("abracadabra");
158 let mut stream = set.search(&exact_mismatch).into_stream();
159 assert_eq!(stream.next(), None);
160
161 let starts_with = Str::new("vati").starts_with();
162 let mut stream = set.search(&starts_with).into_stream();
163 assert_eq!(stream.next().unwrap(), b"vatican");
164 assert_eq!(stream.next().unwrap(), b"vation");
165 assert_eq!(stream.next(), None);
166 }
167
168 #[test]
subsequence()169 fn subsequence() {
170 let set = get_set();
171 let subseq = Subsequence::new("nockbunsurrundd");
172
173 let mut stream = set.search(&subseq).into_stream();
174 assert_eq!(stream.next().unwrap(), b"bannockburnsurrounded");
175 assert_eq!(stream.next(), None);
176 }
177
178 #[test]
implements_default()179 fn implements_default() {
180 let map: fst::Map<Vec<u8>> = Default::default();
181 assert!(map.is_empty());
182
183 let set: fst::Set<Vec<u8>> = Default::default();
184 assert!(set.is_empty());
185 }
186