basic_trie/
lib.rs

1//! # Basic Trie
2//!
3//! [![Test CI](https://github.com/lukascobbler/basic_trie/actions/workflows/rust.yml/badge.svg)](https://github.com/lukascobbler/basic_trie/actions/workflows/rust.yml)
4//!
5//! The trie data structure is used for quick access to words and
6//! data that should (could) be associated with them.
7//!
8//! **Basic Trie** is implemented as a tree where each node holds a single character
9//! that could point at any other character thus allowing insertion of arbitrary words.
10//!
11//! #### There are two major implementations:
12//! - Trie where words are inserted with nothing attached to them
13//! - Data Trie where each word has a corresponding vector of data attached to it
14//!
15//! Regular tries are often used for word lookups and prefix matching, and data tries are
16//! often used for finding all data that is connected to some prefix.
17//!
18//! For example, when inserting a whole book in the trie, you could insert every word with
19//! the corresponding page number it's on. Later when searching for the word, you could get all
20//! the pages the word is on with no added performance cost.
21//!
22//! ## Global features
23//! - insertion / removal of words
24//! - fast contains check
25//! - finding words based on a prefix
26//! - longest / shortest words in the trie
27//! - generic methods: `is_empty`, `len`, `clear`
28//! - Trie equality with `==`
29//! - Trie merging with `+` or `+=`
30//!
31//! ## Data Trie features
32//! - generic type implementation for associating a word to any type, with zero trait constraints
33//! - finding data of words based on exact match or prefix
34//!
35//! ## Optional features
36//! - unicode support via the 'unicode' feature with the `unicode-segmentation` crate (enabled by default)
37//! - data trie support via the 'data' feature (enabled by default)
38//! - serialization and deserialization via the 'serde' feature with the `serde` crate
39//!
40//! ## Dependencies
41//! - `unicode-segmentation` (enabled by default)
42//! - `serde` (only with 'serde' feature flag)
43//! - `fxhash`
44//! - `thin-vec`
45//! - `arrayvec`
46//!
47//! ## License
48//! The software is licensed under the MIT license.
49//!
50//! ## Examples
51//!
52//! ```rust
53//!  use basic_trie::Trie;
54//!
55//!  let mut trie = Trie::new();
56//!  trie.insert("eat");
57//!  trie.insert("eating");
58//!  trie.insert("wizard");
59//!
60//!  let mut found_longest_words = trie.get_longest();
61//!  found_longest_words.sort();
62//!
63//!  assert!(trie.contains("wizard"));
64//!  assert_eq!(vec![String::from("eating"), String::from("wizard")], found_longest_words);
65//!  assert_eq!(vec![String::from("eat")], trie.get_shortest());
66//!  assert_eq!(3, trie.len());
67//!  ```
68//!
69//!  ```rust
70//!  use basic_trie::DataTrie;
71//!
72//!  let mut data_trie = DataTrie::<u32>::new();
73//!  data_trie.insert("apple", 1);
74//!  data_trie.insert("apple", 2);
75//!  data_trie.insert_no_data("banana");
76//!  data_trie.insert("avocado", 15);
77//!
78//! let mut found_data = data_trie.get_data("apple", false).unwrap();
79//! found_data.sort();
80//! assert_eq!(vec![&1, &2], found_data);
81//!
82//! let mut found_data = data_trie.get_data("a", true).unwrap();
83//! found_data.sort();
84//! assert_eq!(vec![&1, &2, &15], found_data);
85//!
86//! assert_eq!(vec![15], data_trie.remove("avocado").unwrap());
87//!  ```
88//!
89//! ## Changelog
90//! - **2.0.0** - Major redesign: increased memory efficiency for the regular Trie (used to be Dataless Trie);
91//! Changed API names to better match the standard library; splitting the two implementations code-wise thus
92//! fixing the documentation not rendering bug.
93//! - **1.2.3** – Adding dependencies for even more memory layout optimisations.
94//! - **1.2.2** – More memory optimisations with Box.
95//! - **1.2.1** – Memory performance upgrade with Box. Mutable data retrieval.
96//! - **1.2.0** – Equality and addition operators support between
97//! same Trie types via `==`, `+` and `+=`.
98//! - **1.1.1** – Adding `FxHashMap` dependency for boosted performance.
99//! - **1.1.0** – Serialization with the `serde` crate and the 'serde' feature.
100//! - **1.0.3** – Optimisation of `number_of_words()`. Removing lifetime requirements
101//! for word insertion for much better flexibility at the same logical memory cost.
102//! - **1.0.2** – Bug fixes.
103//! - **1.0.1** – `insert_no_data()` for `DataTrie`. Bugfixes.
104//! - **1.0.0** – Separation of `DataTrie` and `DatalessTrie`. Optimizing
105//! performance for `DatalessTrie`. Incompatible with older versions.
106//! - **<1.0.0** – Simple `Trie` with data and base features.
107//!
108mod trie;
109mod trie_node;
110
111#[cfg(feature = "data")]
112pub use trie::DataTrie;
113
114pub use trie::Trie;
115
116// Tests which are the same for both implementations,
117// Regular is used for less verbose code.
118#[cfg(test)]
119mod general_trie_tests {
120    use crate::Trie;
121
122    #[test]
123    fn find_words() {
124        let found_words_correct = vec![
125            String::from("word1"),
126            String::from("word2"),
127            String::from("word3"),
128        ];
129
130        let mut trie = Trie::new();
131
132        trie.insert("word1");
133        trie.insert("word2");
134        trie.insert("word3");
135
136        let mut found_words = trie.get("word").unwrap();
137        found_words.sort();
138        assert_eq!(found_words, found_words_correct);
139    }
140
141    #[test]
142    fn longest_word() {
143        let mut trie = Trie::new();
144
145        trie.insert("a");
146        assert_eq!(trie.get_longest(), vec![String::from("a")]);
147
148        trie.insert("aa");
149        assert_eq!(trie.get_longest(), vec![String::from("aa")]);
150
151        trie.insert("aaa");
152        assert_eq!(trie.get_longest(), vec![String::from("aaa")]);
153
154        trie.insert("aaaa");
155        assert_eq!(trie.get_longest(), vec![String::from("aaaa")]);
156
157        trie.insert("a");
158        assert_eq!(trie.get_longest(), vec![String::from("aaaa")]);
159    }
160
161    #[test]
162    fn multiple_longest_words() {
163        let mut trie = Trie::new();
164
165        trie.insert("abba");
166        trie.insert("cddc");
167
168        let mut found_words = trie.get_longest();
169        found_words.sort();
170
171        assert_eq!(
172            vec![String::from("abba"), String::from("cddc")],
173            found_words
174        );
175    }
176
177    #[test]
178    fn shortest_word() {
179        let mut trie = Trie::new();
180
181        trie.insert("a");
182        assert_eq!(trie.get_shortest(), vec![String::from("a")]);
183
184        trie.insert("aa");
185        assert_eq!(trie.get_shortest(), vec![String::from("a")]);
186
187        trie.insert("aaa");
188        assert_eq!(trie.get_shortest(), vec![String::from("a")]);
189
190        trie.insert("aaaa");
191        assert_eq!(trie.get_shortest(), vec![String::from("a")]);
192
193        trie.insert("a");
194        assert_eq!(trie.get_shortest(), vec![String::from("a")]);
195    }
196
197    #[test]
198    fn multiple_shortest_words() {
199        let mut trie = Trie::new();
200
201        trie.insert("aaa");
202        trie.insert("aaaa");
203        trie.insert("aa");
204        trie.insert("bb");
205
206        let mut found_words = trie.get_shortest();
207        found_words.sort();
208
209        assert_eq!(vec![String::from("aa"), String::from("bb")], found_words);
210    }
211
212    #[test]
213    fn number_of_words() {
214        let mut trie = Trie::new();
215
216        trie.insert("a");
217        trie.insert("b");
218        trie.insert("c");
219        trie.insert("d");
220
221        assert_eq!(4, trie.len());
222    }
223
224    #[test]
225    fn same_word_twice() {
226        let mut trie = Trie::new();
227
228        trie.insert("twice");
229        trie.insert("twice");
230
231        assert_eq!(vec!["twice"], trie.get("twice").unwrap());
232    }
233
234    #[test]
235    fn all_words() {
236        let mut trie = Trie::new();
237
238        trie.insert("a");
239        trie.insert("ab");
240        trie.insert("abc");
241        trie.insert("abcd");
242
243        let all_words = vec![
244            String::from("a"),
245            String::from("ab"),
246            String::from("abc"),
247            String::from("abcd"),
248        ];
249
250        assert_eq!(all_words, trie.get_all())
251    }
252
253    #[cfg(feature = "unicode")]
254    #[test]
255    fn unicode() {
256        let mut trie = Trie::new();
257
258        trie.insert("а");
259        trie.insert("аб");
260        trie.insert("абц");
261        trie.insert("абцд");
262
263        let all_words = vec![
264            String::from("а"),
265            String::from("аб"),
266            String::from("абц"),
267            String::from("абцд"),
268        ];
269
270        assert_eq!(all_words, trie.get_all())
271    }
272
273    #[test]
274    fn clear() {
275        let mut trie = Trie::new();
276        trie.insert("word1");
277        trie.insert("word2");
278        trie.insert("word3");
279        trie.insert("word4");
280        trie.insert("word5");
281
282        trie.clear();
283    }
284}
285
286#[cfg(feature = "data")]
287#[cfg(test)]
288mod data_trie_tests {
289    use super::DataTrie;
290
291    #[test]
292    fn find_data_soft_match() {
293        let found_data_correct = vec![&1, &2, &3];
294
295        let mut trie = DataTrie::new();
296
297        trie.insert("word1", 1);
298        trie.insert("word2", 2);
299        trie.insert("word3", 3);
300
301        let mut found_data = trie.get_data("word", true).unwrap();
302        found_data.sort();
303        assert_eq!(found_data, found_data_correct);
304    }
305
306    #[test]
307    fn find_str_data_soft_match() {
308        let found_data_correct = vec![&"data1", &"data2", &"data3"];
309
310        let mut trie = DataTrie::new();
311
312        trie.insert("word1", "data1");
313        trie.insert("word2", "data2");
314        trie.insert("word3", "data3");
315
316        let mut found_data = trie.get_data("word", true).unwrap();
317        found_data.sort();
318        assert_eq!(found_data, found_data_correct);
319    }
320
321    #[test]
322    fn find_data_hard_match() {
323        let found_data_correct = vec![&1];
324
325        let mut trie = DataTrie::new();
326
327        trie.insert("word1", 1);
328        trie.insert("word2", 2);
329        trie.insert("word3", 3);
330
331        let mut found_data = trie.get_data("word1", false).unwrap();
332        found_data.sort();
333        assert_eq!(found_data, found_data_correct);
334    }
335
336    #[test]
337    fn find_data_hard_match_not_found() {
338        let found_data_correct = None;
339
340        let mut trie = DataTrie::new();
341
342        trie.insert("word1", 1);
343        trie.insert("word2", 2);
344        trie.insert("word3", 3);
345
346        let found_data = trie.get_data("word", false);
347
348        assert_eq!(found_data, found_data_correct);
349    }
350
351    #[test]
352    fn same_word_twice_different_data() {
353        let mut trie = DataTrie::new();
354
355        trie.insert("twice", 5);
356        trie.insert("twice", 3);
357
358        assert_eq!(vec![&5, &3], trie.get_data("twice", true).unwrap());
359    }
360
361    #[test]
362    fn clear_word_data() {
363        let mut trie = DataTrie::new();
364
365        trie.insert("twice", 5);
366        let data = trie.clear_data("twice");
367        trie.insert("twice", 3);
368
369        assert_eq!(vec![&3], trie.get_data("twice", true).unwrap());
370        assert_eq!(vec![5], data.unwrap());
371    }
372
373    #[test]
374    fn clear_word_no_data() {
375        let mut trie = DataTrie::new();
376
377        trie.insert("word1", 5);
378        let data = trie.clear_data("word2");
379
380        assert_eq!(None, data);
381    }
382
383    #[test]
384    fn remove_word1() {
385        let mut trie = DataTrie::new();
386
387        trie.insert("a", 5);
388        trie.insert("ab", 5);
389        trie.insert("abc", 5);
390        trie.insert("abcd", 5);
391
392        trie.remove("a");
393
394        let all_words = vec![
395            String::from("ab"),
396            String::from("abc"),
397            String::from("abcd"),
398        ];
399
400        assert_eq!(all_words, trie.get_all())
401    }
402
403    #[test]
404    fn remove_word_final() {
405        let mut trie = DataTrie::new();
406
407        trie.insert("a", 5);
408        trie.insert("ab", 5);
409        trie.insert("abc", 5);
410        trie.insert("abcd", 5);
411
412        trie.remove("abcd");
413
414        let all_correct_words = vec![String::from("a"), String::from("ab"), String::from("abc")];
415
416        let mut all_words = trie.get_all();
417        all_words.sort();
418
419        assert_eq!(all_correct_words, all_words);
420    }
421
422    #[test]
423    fn remove_word_2() {
424        let mut trie = DataTrie::new();
425
426        trie.insert("a", 5);
427        trie.insert("ab", 5);
428        trie.insert("abc", 5);
429        trie.insert("abcd", 5);
430
431        trie.remove("abc");
432
433        let all_correct_words = vec![String::from("a"), String::from("ab"), String::from("abcd")];
434
435        let mut all_words = trie.get_all();
436        all_words.sort();
437
438        assert_eq!(all_correct_words, all_words);
439        assert_eq!(vec![&5, &5, &5], trie.get_data("a", true).unwrap());
440    }
441
442    #[test]
443    fn remove_word_3() {
444        let mut trie = DataTrie::new();
445
446        trie.insert("eat", 5);
447        trie.insert("eating", 5);
448        trie.insert("eats", 5);
449        trie.insert("eatings", 5);
450
451        trie.remove("eating");
452
453        let all_correct_words = vec![
454            String::from("eat"),
455            String::from("eatings"),
456            String::from("eats"),
457        ];
458
459        let mut all_words = trie.get_all();
460        all_words.sort();
461
462        assert_eq!(all_correct_words, all_words);
463    }
464
465    #[test]
466    fn remove_word_4() {
467        let mut trie = DataTrie::new();
468
469        trie.insert("eat", 5);
470        trie.insert("eating", 5);
471        trie.insert("eats", 5);
472        trie.insert("eatings", 5);
473
474        trie.remove("eatings");
475
476        let all_correct_words = vec![
477            String::from("eat"),
478            String::from("eating"),
479            String::from("eats"),
480        ];
481
482        let mut all_words = trie.get_all();
483        all_words.sort();
484
485        assert_eq!(all_correct_words, all_words);
486    }
487
488    #[test]
489    fn remove_word_5() {
490        let mut trie = DataTrie::new();
491
492        trie.insert("eat", 5);
493        trie.insert("eating", 5);
494        trie.insert("eats", 5);
495        trie.insert("eatings", 5);
496
497        let data = trie.remove("eatin");
498
499        let all_correct_words = vec![
500            String::from("eat"),
501            String::from("eating"),
502            String::from("eatings"),
503            String::from("eats"),
504        ];
505
506        let mut all_words = trie.get_all();
507        all_words.sort();
508
509        assert_eq!(all_correct_words, all_words);
510        assert_eq!(None, data);
511    }
512
513    #[test]
514    fn remove_word_6() {
515        let mut trie = DataTrie::new();
516
517        trie.insert("eat", 5);
518        trie.insert("eatings", 5);
519
520        trie.remove("eatings");
521
522        let all_correct_words = vec![String::from("eat")];
523
524        let mut all_words = trie.get_all();
525        all_words.sort();
526
527        assert_eq!(all_correct_words, all_words);
528    }
529
530    #[test]
531    fn remove_word_7() {
532        let mut trie = DataTrie::new();
533
534        trie.insert("eat", 3);
535        trie.insert("eatings", 5);
536
537        let data1 = trie.remove("eatings");
538
539        let all_correct_words = vec![String::from("eat")];
540
541        let mut all_words = trie.get_all();
542        all_words.sort();
543
544        assert_eq!(all_correct_words, all_words);
545
546        assert_eq!(vec![5], data1.unwrap());
547
548        let data2 = trie.remove("eat");
549
550        assert_eq!(vec![3], data2.unwrap());
551    }
552
553    #[test]
554    fn remove_word_8() {
555        let mut trie = DataTrie::new();
556
557        trie.insert("eat", 3);
558        trie.insert("eats", 4);
559        trie.insert("eatings", 5);
560
561        let data = trie.remove("eats");
562
563        let all_correct_words = vec![String::from("eat"), String::from("eatings")];
564
565        let mut all_words = trie.get_all();
566        all_words.sort();
567
568        assert_eq!(all_correct_words, all_words);
569        assert_eq!(vec![4], data.unwrap());
570
571        let mut remaining_data = trie.get_data("eat", true).unwrap();
572        remaining_data.sort();
573
574        assert_eq!(vec![&3, &5], remaining_data);
575    }
576
577    #[test]
578    fn remove_prefix_1() {
579        let mut trie = DataTrie::new();
580
581        trie.insert("eat", 3);
582        trie.insert("eating", 4);
583        trie.insert("eats", 5);
584        trie.insert("eatings", 6);
585        trie.insert("ea", 7);
586
587        let mut removed_data = trie.remove_prefix("ea").unwrap();
588        removed_data.sort();
589
590        assert_eq!(vec![String::from("ea")], trie.get_all());
591        assert_eq!(vec![3, 4, 5, 6], removed_data);
592        assert_eq!(1, trie.len());
593    }
594
595    #[test]
596    fn remove_prefix_2() {
597        let mut trie = DataTrie::new();
598
599        trie.insert("a1", 3);
600        trie.insert("b2", 4);
601        trie.insert("c3", 5);
602
603        let mut removed_data = trie.remove_prefix("").unwrap();
604        removed_data.sort();
605
606        assert_eq!(Vec::<String>::new(), trie.get_all());
607        assert!(trie.is_empty());
608        assert_eq!(0, trie.len());
609        assert_eq!(vec![3, 4, 5], removed_data);
610    }
611
612    #[cfg(feature = "unicode")]
613    #[test]
614    fn unicode_data() {
615        let mut trie = DataTrie::new();
616
617        trie.insert("а", 5);
618        trie.insert("аб", 5);
619        trie.insert("абц", 5);
620        trie.insert("абцд", 5);
621
622        let all_data = vec![&5, &5, &5, &5];
623
624        assert_eq!(all_data, trie.get_data("а", true).unwrap())
625    }
626
627    #[test]
628    fn insert_no_data() {
629        let mut trie = DataTrie::<&str>::new();
630
631        trie.insert_no_data("word1");
632        assert_eq!(vec![String::from("word1")], trie.get_all());
633
634        trie.insert("word1", "somedata");
635        assert_eq!(vec![&"somedata"], trie.get_data("word1", false).unwrap());
636    }
637
638    #[test]
639    fn equals_1() {
640        let mut data_trie_1 = DataTrie::new();
641        data_trie_1.insert("test", 1);
642
643        let mut data_trie_2 = DataTrie::new();
644        data_trie_2.insert("test", 1);
645
646        assert_eq!(data_trie_1, data_trie_2);
647    }
648
649    #[test]
650    fn equals_2() {
651        let mut data_trie_1 = DataTrie::new();
652        data_trie_1.insert("test", 1);
653
654        let mut data_trie_2 = DataTrie::new();
655        data_trie_2.insert("test", 1);
656        data_trie_2.insert("test2", 1);
657
658        assert_ne!(data_trie_1, data_trie_2);
659    }
660
661    #[test]
662    fn equals_3() {
663        let mut data_trie_1 = DataTrie::new();
664        data_trie_1.insert("test", 1);
665        data_trie_1.insert("test2", 1);
666
667        let mut data_trie_2 = DataTrie::new();
668        data_trie_2.insert("test", 1);
669
670        assert_ne!(data_trie_1, data_trie_2);
671    }
672
673    #[test]
674    fn add_two_tries_1() {
675        let mut t1 = DataTrie::<i32>::new();
676        t1.insert("word1", 1000);
677        t1.insert("word2", 1000);
678        t1.insert("apple", 1000);
679        t1.insert("banana", 1000);
680
681        let mut t2 = DataTrie::<i32>::new();
682        t2.insert("word3", 1000);
683        t2.insert("word4", 1000);
684        t2.insert("potato", 1000);
685        t2.insert("watermelon", 1000);
686
687        let t3 = t1 + t2;
688
689        let mut correct = DataTrie::<i32>::new();
690        correct.insert("word1", 1000);
691        correct.insert("word2", 1000);
692        correct.insert("apple", 1000);
693        correct.insert("banana", 1000);
694        correct.insert("word3", 1000);
695        correct.insert("word4", 1000);
696        correct.insert("potato", 1000);
697        correct.insert("watermelon", 1000);
698
699        let mut t3_words = t3.get_all();
700        let mut correct_words = correct.get_all();
701
702        t3_words.sort();
703        correct_words.sort();
704        assert_eq!(t3_words, correct_words);
705        assert_eq!(t3, correct);
706
707        let t3_data = t3.get_data("", true).unwrap();
708        assert_eq!(t3_data, Vec::from([&1000; 8]));
709    }
710
711    #[test]
712    fn add_two_tries_2() {
713        let mut t1 = DataTrie::<i32>::new();
714        t1.insert("word1", 1000);
715        t1.insert("word2", 1000);
716        t1.insert("apple", 1000);
717        t1.insert("banana", 1000);
718
719        let mut t2 = DataTrie::<i32>::new();
720        t2.insert("word3", 1000);
721        t2.insert("word4", 1000);
722        t2.insert("potato", 1000);
723        t2.insert("watermelon", 1000);
724
725        t1 += t2;
726
727        let mut correct = DataTrie::<i32>::new();
728        correct.insert("word1", 1000);
729        correct.insert("word2", 1000);
730        correct.insert("apple", 1000);
731        correct.insert("banana", 1000);
732        correct.insert("word3", 1000);
733        correct.insert("word4", 1000);
734        correct.insert("potato", 1000);
735        correct.insert("watermelon", 1000);
736
737        let mut t1_words = t1.get_all();
738        let mut correct_words = correct.get_all();
739
740        t1_words.sort();
741        correct_words.sort();
742        assert_eq!(t1_words, correct_words);
743        assert_eq!(t1, correct);
744
745        let t1_data = t1.get_data("", true).unwrap();
746        assert_eq!(t1_data, Vec::from([&1000; 8]));
747    }
748
749    #[test]
750    fn add_two_tries_3() {
751        let mut t1 = DataTrie::<i32>::new();
752        t1.insert("word1", 500);
753
754        let mut t2 = DataTrie::<i32>::new();
755        t2.insert("word2", 500);
756        t2.insert("word", 500);
757
758        t1 += t2;
759
760        let mut correct = DataTrie::<i32>::new();
761        correct.insert("word", 500);
762        correct.insert("word1", 500);
763        correct.insert("word2", 500);
764
765        let mut t1_words = t1.get_all();
766        let mut correct_words = correct.get_all();
767
768        t1_words.sort();
769        correct_words.sort();
770        assert_eq!(t1_words, correct_words);
771        assert_eq!(t1, correct);
772
773        let t1_data = t1.get_data("", true).unwrap();
774        assert_eq!(t1_data, Vec::from([&500; 3]));
775    }
776
777    #[test]
778    fn add_two_tries_4() {
779        let mut t1 = DataTrie::<i32>::new();
780        t1.insert("word1", 500);
781        t1.insert("word1", 500);
782        t1.insert("word1", 500);
783
784        let mut t2 = DataTrie::<i32>::new();
785        t2.insert("word1", 500);
786        t2.insert("word1", 500);
787        t2.insert("word1", 500);
788
789        t1 += t2;
790
791        let mut correct = DataTrie::<i32>::new();
792        correct.insert("word1", 500);
793
794        let mut t1_words = t1.get_all();
795        let mut correct_words = correct.get_all();
796
797        t1_words.sort();
798        correct_words.sort();
799        assert_eq!(t1_words, correct_words);
800
801        let t1_data = t1.get_data("", true).unwrap();
802        assert_eq!(t1_data, Vec::from([&500; 6]));
803    }
804
805    #[test]
806    fn add_two_tries_5() {
807        let mut t1 = DataTrie::<i32>::new();
808        t1.insert("word1", 500);
809        t1.insert("word1", 500);
810        t1.insert("word1", 500);
811
812        let mut t2 = DataTrie::<i32>::new();
813        t2.insert("word1", 500);
814        t2.insert("word1", 500);
815        t2.insert("word1", 500);
816
817        t1 += t2;
818
819        let mut correct = DataTrie::<i32>::new();
820        correct.insert("word1", 500);
821
822        let mut t1_words = t1.get_all();
823        let mut correct_words = correct.get_all();
824
825        t1_words.sort();
826        correct_words.sort();
827        assert_eq!(t1_words, correct_words);
828
829        let t1_data = t1.get_data("", true).unwrap();
830        assert_eq!(t1_data, Vec::from([&500; 6]));
831    }
832}
833
834#[cfg(test)]
835mod regular_trie_tests {
836    use crate::Trie;
837
838    #[test]
839    fn insert_no_data() {
840        let mut trie = Trie::new();
841
842        let found_words_correct = vec![
843            String::from("word1"),
844            String::from("word2"),
845            String::from("word3"),
846        ];
847
848        trie.insert("word1");
849        trie.insert("word2");
850        trie.insert("word3");
851
852        let mut found_words = trie.get("word").unwrap();
853        found_words.sort();
854
855        assert_eq!(found_words, found_words_correct);
856    }
857
858    #[test]
859    fn remove_word1() {
860        let mut trie = Trie::new();
861
862        trie.insert("a");
863        trie.insert("ab");
864        trie.insert("abc");
865        trie.insert("abcd");
866
867        trie.remove("a");
868
869        let all_words = vec![
870            String::from("ab"),
871            String::from("abc"),
872            String::from("abcd"),
873        ];
874
875        assert_eq!(all_words, trie.get_all())
876    }
877
878    #[test]
879    fn remove_word_final() {
880        let mut trie = Trie::new();
881
882        trie.insert("a");
883        trie.insert("ab");
884        trie.insert("abc");
885        trie.insert("abcd");
886
887        trie.remove("abcd");
888
889        let all_correct_words = vec![String::from("a"), String::from("ab"), String::from("abc")];
890
891        let mut all_words = trie.get_all();
892        all_words.sort();
893
894        assert_eq!(all_correct_words, all_words);
895    }
896
897    #[test]
898    fn remove_word_2() {
899        let mut trie = Trie::new();
900
901        trie.insert("a");
902        trie.insert("ab");
903        trie.insert("abc");
904        trie.insert("abcd");
905
906        trie.remove("abc");
907
908        let all_correct_words = vec![String::from("a"), String::from("ab"), String::from("abcd")];
909
910        let mut all_words = trie.get_all();
911        all_words.sort();
912
913        assert_eq!(all_correct_words, all_words);
914    }
915
916    #[test]
917    fn remove_word_3() {
918        let mut trie = Trie::new();
919
920        trie.insert("eat");
921        trie.insert("eating");
922        trie.insert("eats");
923        trie.insert("eatings");
924
925        trie.remove("eating");
926
927        let all_correct_words = vec![
928            String::from("eat"),
929            String::from("eatings"),
930            String::from("eats"),
931        ];
932
933        let mut all_words = trie.get_all();
934        all_words.sort();
935
936        assert_eq!(all_correct_words, all_words);
937    }
938
939    #[test]
940    fn remove_word_4() {
941        let mut trie = Trie::new();
942
943        trie.insert("eat");
944        trie.insert("eating");
945        trie.insert("eats");
946        trie.insert("eatings");
947
948        trie.remove("eatings");
949
950        let all_correct_words = vec![
951            String::from("eat"),
952            String::from("eating"),
953            String::from("eats"),
954        ];
955
956        let mut all_words = trie.get_all();
957        all_words.sort();
958
959        assert_eq!(all_correct_words, all_words);
960    }
961
962    #[test]
963    fn remove_word_5() {
964        let mut trie = Trie::new();
965
966        trie.insert("eat");
967        trie.insert("eating");
968        trie.insert("eats");
969        trie.insert("eatings");
970
971        trie.remove("eatin");
972
973        let all_correct_words = vec![
974            String::from("eat"),
975            String::from("eating"),
976            String::from("eatings"),
977            String::from("eats"),
978        ];
979
980        let mut all_words = trie.get_all();
981        all_words.sort();
982
983        assert_eq!(all_correct_words, all_words);
984    }
985
986    #[test]
987    fn remove_word_6() {
988        let mut trie = Trie::new();
989
990        trie.insert("eat");
991        trie.insert("eatings");
992
993        trie.remove("eatings");
994
995        let all_correct_words = vec![String::from("eat")];
996
997        let mut all_words = trie.get_all();
998        all_words.sort();
999
1000        assert_eq!(all_correct_words, all_words);
1001    }
1002
1003    #[test]
1004    fn remove_word_7() {
1005        let mut trie = Trie::new();
1006
1007        trie.insert("eat");
1008        trie.insert("eatings");
1009
1010        trie.remove("eatings");
1011
1012        let all_correct_words = vec![String::from("eat")];
1013
1014        let mut all_words = trie.get_all();
1015        all_words.sort();
1016
1017        assert_eq!(all_correct_words, all_words);
1018    }
1019
1020    #[test]
1021    fn remove_word_8() {
1022        let mut trie = Trie::new();
1023
1024        trie.insert("eat");
1025        trie.insert("eats");
1026        trie.insert("eating");
1027
1028        trie.remove("eats");
1029
1030        let all_correct_words = vec![String::from("eat"), String::from("eating")];
1031
1032        let mut all_words = trie.get_all();
1033        all_words.sort();
1034
1035        assert_eq!(all_correct_words, all_words);
1036    }
1037
1038    #[test]
1039    fn remove_word_9() {
1040        let mut trie = Trie::new();
1041
1042        trie.insert("123");
1043        trie.insert("1234");
1044        trie.insert("12345");
1045
1046        trie.remove("1234");
1047
1048        let all_correct_words = vec![String::from("123"), String::from("12345")];
1049
1050        let mut all_words = trie.get_all();
1051        all_words.sort();
1052
1053        assert_eq!(all_correct_words, all_words);
1054    }
1055
1056    #[test]
1057    fn remove_prefix_1() {
1058        let mut trie = Trie::new();
1059
1060        trie.insert("eat");
1061        trie.insert("eating");
1062        trie.insert("eats");
1063        trie.insert("eatings");
1064        trie.insert("ea");
1065
1066        trie.remove_prefix("ea");
1067
1068        assert_eq!(vec![String::from("ea")], trie.get_all());
1069        assert_eq!(1, trie.len());
1070    }
1071
1072    #[test]
1073    fn remove_prefix_2() {
1074        let mut trie = Trie::new();
1075
1076        trie.insert("a1");
1077        trie.insert("b2");
1078        trie.insert("c3");
1079
1080        trie.remove_prefix("");
1081
1082        assert_eq!(Vec::<String>::new(), trie.get_all());
1083        assert!(trie.is_empty());
1084        assert_eq!(0, trie.len());
1085    }
1086
1087    #[test]
1088    fn equals() {
1089        let mut trie_1 = Trie::new();
1090        trie_1.insert("test");
1091
1092        let mut trie_2 = Trie::new();
1093        trie_2.insert("test");
1094
1095        assert_eq!(trie_1, trie_2);
1096    }
1097
1098    #[test]
1099    fn add_two_tries_1() {
1100        let mut t1 = Trie::new();
1101        t1.insert("word1");
1102        t1.insert("word2");
1103        t1.insert("apple");
1104        t1.insert("banana");
1105
1106        let mut t2 = Trie::new();
1107        t2.insert("word3");
1108        t2.insert("word4");
1109        t2.insert("potato");
1110        t2.insert("pineapple");
1111
1112        let t3 = t1 + t2;
1113
1114        let mut correct = Trie::new();
1115        correct.insert("word1");
1116        correct.insert("word2");
1117        correct.insert("apple");
1118        correct.insert("banana");
1119        correct.insert("word3");
1120        correct.insert("word4");
1121        correct.insert("potato");
1122        correct.insert("pineapple");
1123
1124        let mut t3_words = t3.get_all();
1125        let mut correct_words = correct.get_all();
1126
1127        t3_words.sort();
1128        correct_words.sort();
1129        assert_eq!(t3_words, correct_words);
1130    }
1131
1132    #[test]
1133    fn add_two_tries_2() {
1134        let mut t1 = Trie::new();
1135        t1.insert("word1");
1136        t1.insert("word2");
1137        t1.insert("apple");
1138        t1.insert("banana");
1139
1140        let mut t2 = Trie::new();
1141        t2.insert("word3");
1142        t2.insert("word4");
1143        t2.insert("potato");
1144        t2.insert("watermelon");
1145
1146        t1 += t2;
1147
1148        let mut correct = Trie::new();
1149        correct.insert("word1");
1150        correct.insert("word2");
1151        correct.insert("apple");
1152        correct.insert("banana");
1153        correct.insert("word3");
1154        correct.insert("word4");
1155        correct.insert("potato");
1156        correct.insert("watermelon");
1157
1158        let mut t1_words = t1.get_all();
1159        let mut correct_words = correct.get_all();
1160
1161        t1_words.sort();
1162        correct_words.sort();
1163        assert_eq!(t1_words, correct_words);
1164    }
1165
1166    #[test]
1167    fn add_two_tries_3() {
1168        let mut t1 = Trie::new();
1169        t1.insert("word1");
1170
1171        let mut t2 = Trie::new();
1172        t2.insert("word2");
1173        t2.insert("word");
1174
1175        t1 += t2;
1176
1177        let mut correct = Trie::new();
1178        correct.insert("word");
1179        correct.insert("word1");
1180        correct.insert("word2");
1181
1182        let mut t1_words = t1.get_all();
1183        let mut correct_words = correct.get_all();
1184
1185        t1_words.sort();
1186        correct_words.sort();
1187        assert_eq!(t1_words, correct_words);
1188    }
1189}
basic_trie/lib.rs

basic_trie/
lib.rs
