ternary_tree/lib.rs
1/*!
2A Rust implementation of Ternary Search Trees, with no unsafe blocks and a simplified [Wasm binding](
3https://crates.io/crates/ternary-tree-wasm).
4
5[](
6 http://travis-ci.com/julien-montmartin/ternary-tree)
7[](
8 http://codecov.io/gh/julien-montmartin/ternary-tree)
9[](
10 http://crates.io/crates/ternary-tree)
11[](
12 https://docs.rs/ternary-tree/)
13
14A Ternary Search Tree (TST) is a data structure which stores key/value pairs in a tree. The key is a string, and
15its characters are placed in the tree nodes. Each node may have three children (hence the name): a _left_ child, a
16_middle_ child and a _right_ child.
17
18A search in a TST compares the current character in the key with the character of the current node:
19
20* If both matches, the search traverses the middle child, and proceed to the next character in the key
21* If the key character is less than the node one, the search simply goes through the left child, and keep looking
22 for the same key character
23* Respectively, if the key character is greater than the node one, the search simply goes through the right child
24
25The data structure and its algorithm are explained very well in [Dr.Dobb's Ternary Search Trees](
26http://www.drdobbs.com/database/ternary-search-trees/184410528) article.
27
28The following tree is the TST we get after inserting the following keys in order: "aba", "ab", "bc", "ac", "abc",
29"a", "b", "aca", "caa", "cbc", "bac", "c", "cca", "aab", "abb", "aa" (see `tst.dot` produced by code below)
30
31<p align="center"><img alt="An example of a Ternary Search Tree"
32src="https://files.jmontmartin.net/tree.svg"></p>
33
34A checked box "☑" denotes a node which stores a value (it corresponds to the last character of a key). An empty box
35"☐" means that the node has no value.
36
37A TST can be used as a map, but it allows more flexible ways to retrieve values associated with keys. This crate
38provides four ways to iterate over the values of a TST:
39
40* get all values (same as a regular map), with `visit_values` or `iter`
41* get all values whose keys begin with some prefix (i.e. _complete_ some prefix), with `visit_complete_values` or
42 `iter_complete`
43* get all values whose keys are _close_ to some string ([Hamming distance](
44 http://en.wikipedia.org/wiki/Hamming_distance)), with `visit_neighbor_values` or `iter_neighbor`
45* get all values whose keys match a string with some joker (e.g. "a?c"), with `visit_crossword_values` or
46 `iter_crossword`
47
48Visit methods are recursive and apply a closure to found values. They exist in immutable and mutable version
49(i.e. `visit_neighbor_values_mut`). But once a value is found (based on its key), they offer no way to know what
50the actual key is.
51
52Iterators, on the other hand, save their context in a `Vec` and only work on immutable trees. However they are
53double-ended, and support `next` and `next_back` methods to walk the tree from both ends. Moreover, once a value is
54found, they offer the `current_key` and `current_key_back` methods to retrieve the associated key.
55
56The following lines may give you a foretaste of this crate and TSTs
57
58```
59extern crate ternary_tree;
60
61use ternary_tree::Tst;
62use std::fs::File;
63use std::error::Error;
64
65const SOME_KEYS : [&str; 16] = ["aba", "ab", "bc", "ac",
66"abc", "a", "b", "aca", "caa", "cbc", "bac", "c", "cca",
67"aab", "abb", "aa"];
68
69let mut map = Tst::new();
70
71for key in &SOME_KEYS {
72
73 // Say the value is the same as the key,
74 // it makes the example easier !
75 let some_value = *key;
76
77 map.insert(key, some_value);
78}
79
80// Use Graphviz to convert tst.dot to tst.png:
81// dot -T png -o tst.png tst.dot
82let mut file = File::create("tst.dot").unwrap();
83map.pretty_print(&mut file);
84
85let mut v = Vec::new();
86
87// Recursively get all values whose keys match "a?a" pattern
88map.visit_crossword_values("a?a", '?', |s| v.push(s.clone()));
89assert_eq!(v, ["aba", "aca"]);
90
91v.clear();
92
93// Iterate over all values whose keys are close to "abc"
94// (At a Hamming distance of 1 from "abc")
95{
96 let mut it = map.iter_neighbor("abc", 1);
97
98 while let Some(value) = it.next() {
99
100 v.push(*value);
101 }
102 assert_eq!(v, ["ab", "aba", "abb", "abc", "cbc"]);
103
104 v.clear();
105}
106
107// Mutate all values whose keys begin with "c"
108map.visit_complete_values_mut("c", |s| *s = "xxx");
109
110assert_eq!(map.get("caa"), Some(&"xxx"));
111assert_eq!(map.get("cbc"), Some(&"xxx"));
112assert_eq!(map.get("cca"), Some(&"xxx"));
113```
114*/
115
116#![forbid(unsafe_code)]
117
118use std::str::Chars;
119use std::mem::replace;
120use std::cmp::Ordering::Less;
121use std::cmp::Ordering::Equal;
122use std::cmp::Ordering::Greater;
123use std::io::Write;
124use std::ptr;
125use std::fmt;
126use std::mem;
127
128
129/// A `Tst` is a ternary tree structure which stores key value pairs and roughly behave like a map, but allowing
130/// more flexible ways to find and iterate over values.
131///
132/// See the [module documentation]( ./index.html) for example usage and motivation.
133
134pub struct Tst<T> {
135
136 root: Link<T>,
137 count: usize
138}
139
140
141type Link<T> = Option<Box<Node<T>>>;
142
143
144struct Node<T> {
145
146 label: char,
147 value: Option<T>,
148 left: Link<T>,
149 middle: Link<T>,
150 right: Link<T>
151}
152
153
154impl<T> Default for Node<T> {
155
156 fn default() -> Node<T> {
157
158 Node {
159
160 label: '\0',
161 value: None,
162 left: None,
163 middle: None,
164 right: None
165 }
166 }
167}
168
169
170impl<T> fmt::Debug for Node<T> {
171
172 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
173
174 let value_box = match self.value {
175
176 None => "☐", Some(_) => "☑"
177 };
178
179 write!(f, "{}-{}", value_box, self.label)
180 }
181}
182
183
184fn insert_r<T>(link: &mut Link<T>, label: char, mut key_tail: Chars, value: T) -> Option<T> {
185
186 let choose_branch_and_do_insert = |node: &mut Box<Node<T>>| match label.cmp(&node.label) {
187
188 Less => insert_r(&mut node.left, label, key_tail, value),
189
190 Greater => insert_r(&mut node.right, label, key_tail, value),
191
192 Equal => {
193
194 let new_label = key_tail.next();
195
196 match new_label {
197
198 None => replace(&mut node.value, Some(value)),
199
200 Some(label) => insert_r(&mut node.middle, label, key_tail, value)
201 }
202 }
203 };
204
205 match link {
206
207 None => {
208
209 let mut node = Box::new(Node::<T>{label, .. Default::default()});
210
211 let old_value = choose_branch_and_do_insert(&mut node);
212
213 *link = Some(node);
214
215 old_value
216 }
217
218 Some(ref mut node) => choose_branch_and_do_insert(node)
219 }
220}
221
222
223fn get_r<'a, T>(link: &'a Link<T>, label: char, key_tail: &mut Chars) -> Option<&'a T> {
224
225 match *link {
226
227 None => None,
228
229 Some(ref node) => match label.cmp(&node.label) {
230
231 Less => get_r(&node.left, label, key_tail),
232
233 Equal => {
234
235 let new_label = key_tail.next();
236
237 match new_label {
238
239 None => match node.value {
240
241 None => None,
242
243 Some(ref value) => Some(value)
244 }
245
246 Some(label) => get_r(&node.middle, label, key_tail)
247 }
248 },
249
250 Greater => get_r(&node.right, label, key_tail),
251 }
252 }
253}
254
255
256fn get_r_mut<'a, T>(link: &'a mut Link<T>, label: char, key_tail: &mut Chars) -> Option<&'a mut T> {
257
258 match *link {
259
260 None => None,
261
262 Some(ref mut node) => match label.cmp(&node.label) {
263
264 Less => get_r_mut(&mut node.left, label, key_tail),
265
266 Equal => {
267
268 let new_label = key_tail.next();
269
270 match new_label {
271
272 None => match node.value {
273
274 None => None,
275
276 Some(ref mut value) => Some(value)
277 }
278
279 Some(label) => get_r_mut(&mut node.middle, label, key_tail)
280 }
281 },
282
283 Greater => get_r_mut(&mut node.right, label, key_tail),
284 }
285 }
286}
287
288
289fn remove_r<T>(link: &mut Link<T>, label: char, key_tail: &mut Chars) -> (bool, Option<T>) {
290
291 match *link {
292
293 None => (false, None),
294
295 Some(ref mut node) => match label.cmp(&node.label) {
296
297 Less => {
298
299 let (prune, old_value) = remove_r(&mut node.left, label, key_tail);
300
301 if prune {
302
303 node.left = None;
304 }
305
306 let more_pruning = node.value.is_none() && node.left.is_none() && node.middle.is_none() && node.right.is_none();
307 (more_pruning, old_value)
308 }
309
310 Equal => {
311
312 let new_label = key_tail.next();
313
314 match new_label {
315
316 None => {
317
318 let old_value = replace(&mut node.value, None);
319
320 let prune = old_value.is_some() && node.left.is_none() && node.middle.is_none() && node.right.is_none();
321 (prune, old_value)
322 }
323
324 Some(label) => {
325
326 let (prune, old_value) = remove_r(&mut node.middle, label, key_tail);
327
328 if prune {
329
330 node.middle = None;
331 }
332
333 let more_pruning = node.value.is_none() && node.left.is_none() && node.middle.is_none() && node.right.is_none();
334 (more_pruning, old_value)
335 }
336 }
337 }
338
339 Greater => {
340
341 let (prune, old_value) = remove_r(&mut node.right, label, key_tail);
342
343 if prune {
344
345 node.right = None;
346 }
347
348 let more_pruning = node.value.is_none() && node.left.is_none() && node.middle.is_none() && node.right.is_none();
349 (more_pruning, old_value)
350 }
351 }
352 }
353}
354
355
356/// How nodes are distributed. See [Stats]( ./struct.Stats.html) for a brief description.
357
358#[derive(Default,PartialEq,Debug)]
359pub struct DistStat { pub matches: usize, pub sides: usize, pub depth: usize }
360
361
362/// How long are the keys. See [Stats]( ./struct.Stats.html) for a brief description.
363
364#[derive(Default,PartialEq,Debug)]
365pub struct KeyLenStat { pub min: usize, pub max: usize }
366
367
368/// How many nodes and values are in the tree. See [Stats]( ./struct.Stats.html) for a brief description.
369
370#[derive(Default,PartialEq,Debug)]
371pub struct CountStat { pub nodes:usize, pub values: usize }
372
373
374/// Memory used by the tree. See [Stats]( ./struct.Stats.html) for a brief description.
375
376#[derive(Default,PartialEq,Debug)]
377pub struct BytesStat { pub node: usize, pub total: usize }
378
379
380/// Contains various metrics describing the tree: its nodes, keys and values. Mostly used for tuning and debugging
381/// purpose.
382/// * `dist[n].matches` number of values reached by traversing _n_ `middle` links (the number of keys of length
383/// _n_)
384/// * `dist[n].sides` number of values reached by traversing _n_ `left` or `middle` links (those links may indicate
385/// that the tree is not well balanced)
386/// * `dist[n].depth` number of values whose total depth (`middle`, `left` and `right` links) is _n_
387/// * `key_len.min` length of the shortest key inserted in the tree
388/// * `key_len.max` length of the longest key inserted in the tree
389/// * `count.nodes` total number of nodes in the tree
390/// * `count.values` number of nodes which store a value (same as [len]( ./struct.Tst.html#method.len))
391/// * `bytes.node` byte size of a node (including the fixed size of a value, but excluding heap allocated memory of
392/// this value)
393/// * `bytes.total` total number of bytes allocated for nodes (`count.nodes` * `bytes.node`)
394
395#[derive(Default,PartialEq,Debug)]
396pub struct Stats {
397
398 pub dist: Vec<DistStat>,
399 pub key_len: KeyLenStat,
400 pub count: CountStat,
401 pub bytes: BytesStat,
402}
403
404
405fn stat_r<T>(stats: Stats, link: &Link<T>, matches: usize, sides: usize, depth: usize) -> Stats {
406
407 match *link {
408
409 None => stats,
410
411 Some(ref node) => {
412
413 let mut stats = stat_r(stats, &node.left, matches, sides+1, depth+1);
414
415 stats.count.nodes+=1;
416
417 if node.value.is_some() {
418
419 let matches = matches + 1;
420 let depth = depth + 1;
421
422 while stats.dist.len() <= depth {
423
424 stats.dist.push(DistStat { matches: 0, sides: 0, depth: 0 });
425 }
426
427 stats.dist[matches].matches+=1;
428 stats.dist[sides].sides+=1;
429 stats.dist[depth].depth+=1;
430
431 if stats.key_len.min == 0 || matches < stats.key_len.min {
432
433 stats.key_len.min = matches;
434 }
435
436 if matches > stats.key_len.max {
437
438 stats.key_len.max = matches;
439 }
440
441 stats.count.values+=1;
442 }
443
444 let stats = stat_r(stats, &node.middle, matches+1, sides, depth+1);
445 let stats = stat_r(stats, &node.right, matches, sides+1, depth+1);
446
447 stats
448 }
449 }
450}
451
452
453fn find_complete_root_r<'a, T>(link: &'a Link<T>, label: char, mut key_tail: Chars) -> &'a Link<T> {
454
455 match *link {
456
457 None => &link,
458
459 Some(ref node) => match label.cmp(&node.label) {
460
461 Less => find_complete_root_r(&node.left, label, key_tail),
462
463 Greater => find_complete_root_r(&node.right, label, key_tail),
464
465 Equal => {
466
467 let new_label = key_tail.next();
468
469 match new_label {
470
471 None => &node.middle,
472
473 Some(label) => find_complete_root_r(&node.middle, label, key_tail)
474 }
475 }
476 }
477 }
478}
479
480
481fn find_complete_root_r_mut<'a, T>(link: &'a mut Link<T>, label: char, mut key_tail: Chars) -> &'a mut Link<T> {
482
483 match *link {
484
485 None => { link }
486
487 Some(ref mut node) => match label.cmp(&node.label) {
488
489 Less => find_complete_root_r_mut(&mut node.left, label, key_tail),
490
491 Greater => find_complete_root_r_mut(&mut node.right, label, key_tail),
492
493 Equal => {
494
495 let new_label = key_tail.next();
496
497 match new_label {
498
499 None => &mut node.middle,
500
501 Some(label) => find_complete_root_r_mut(&mut node.middle, label, key_tail)
502 }
503 }
504 }
505 }
506}
507
508
509fn visit_values_r<T, C>(link: &Link<T>, callback: &mut C)
510where C: FnMut (&T) {
511
512 match *link {
513
514 None => return,
515
516 Some(ref node) => {
517
518 visit_values_r(&node.left, callback);
519
520 if let Some(ref value) = node.value {
521
522 callback(value);
523 }
524
525 visit_values_r(&node.middle, callback);
526 visit_values_r(&node.right, callback);
527 }
528 }
529}
530
531
532fn visit_values_r_mut<T, C>(link: &mut Link<T>, callback: &mut C)
533where C: FnMut (&mut T) {
534
535 match *link {
536
537 None => return,
538
539 Some(ref mut node) => {
540
541 visit_values_r_mut(&mut node.left, callback);
542
543 if let Some(ref mut value) = node.value {
544
545 callback(value);
546 }
547
548 visit_values_r_mut(&mut node.middle, callback);
549 visit_values_r_mut(&mut node.right, callback);
550 }
551 }
552}
553
554
555fn visit_complete_values_r<T, C>(link: &Link<T>, callback: &mut C)
556where C: FnMut (&T) {
557
558 match *link {
559
560 None => return,
561
562 Some(ref node) => {
563
564 visit_values_r(&node.left, callback);
565
566 if let Some(ref value) = node.value {
567
568 callback(value);
569 }
570
571 visit_values_r(&node.middle, callback);
572 visit_values_r(&node.right, callback);
573 }
574 }
575}
576
577
578fn visit_complete_values_r_mut<T, C>(link: &mut Link<T>, callback: &mut C)
579where C: FnMut (&mut T) {
580
581 match *link {
582
583 None => return,
584
585 Some(ref mut node) => {
586
587 visit_values_r_mut(&mut node.left, callback);
588
589 if let Some(ref mut value) = node.value {
590
591 callback(value);
592 }
593
594 visit_values_r_mut(&mut node.middle, callback);
595 visit_values_r_mut(&mut node.right, callback);
596 }
597 }
598}
599
600
601fn visit_neighbor_values_r<'a, T, C>(link: &'a Link<T>, label: Option<char>, key_tail: &mut Chars, tail_len: usize, range: usize, callback: &mut C)
602where C: FnMut (&T) {
603
604 if range == 0 {
605
606 if let Some(label) = label {
607
608 if let Some(value) = get_r(link, label, key_tail) {
609
610 callback(value);
611 }
612 }
613
614 } else {
615
616 if let Some(ref node) = *link {
617
618 visit_neighbor_values_r(&node.left, label, key_tail, tail_len, range, callback);
619
620 if let Some(ref value) = node.value {
621
622 let new_range = match label {
623
624 None => range-1,
625
626 Some(label) => if label==node.label { range } else { range-1 }
627 };
628
629 if tail_len <= new_range {
630
631 callback(value);
632 }
633 }
634
635 {
636 let new_range = match label {
637
638 None => range-1,
639
640 Some(label) => if label==node.label { range } else { range-1 }
641 };
642
643 let mut new_tail = key_tail.clone();
644 let new_label = new_tail.next();
645
646 let new_len = if tail_len > 0 { tail_len-1 } else { tail_len };
647
648 visit_neighbor_values_r(&node.middle, new_label, &mut new_tail, new_len, new_range, callback);
649 }
650
651 visit_neighbor_values_r(&node.right, label, key_tail, tail_len, range, callback);
652 }
653 }
654}
655
656
657fn visit_neighbor_values_r_mut<'a, T, C>(link: &'a mut Link<T>, label: Option<char>, key_tail: &mut Chars, tail_len: usize, range: usize, callback: &mut C)
658where C: FnMut (&mut T) {
659
660 if range == 0 {
661
662 if let Some(label) = label {
663
664 if let Some(value) = get_r_mut(link, label, key_tail) {
665
666 callback(value);
667 }
668 }
669
670 } else {
671
672 if let Some(ref mut node) = *link {
673
674 let label_tmp = node.label;
675
676 visit_neighbor_values_r_mut(&mut node.left, label, key_tail, tail_len, range, callback);
677
678 if let Some(ref mut value) = node.value {
679
680 let new_range = match label {
681
682 None => range-1,
683
684 Some(label) => if label == label_tmp { range } else { range-1 }
685 };
686
687 if tail_len <= new_range {
688
689 callback(value);
690 }
691 }
692
693 {
694 let new_range = match label {
695
696 None => range-1,
697
698 Some(label) => if label == node.label { range } else { range-1 }
699 };
700
701 let mut new_tail = key_tail.clone();
702 let new_label = new_tail.next();
703
704 let new_len = if tail_len > 0 { tail_len-1 } else { tail_len };
705
706 visit_neighbor_values_r_mut(&mut node.middle, new_label, &mut new_tail, new_len, new_range, callback);
707 }
708
709 visit_neighbor_values_r_mut(&mut node.right, label, key_tail, tail_len, range, callback);
710 }
711 }
712}
713
714
715fn visit_crossword_values_r<'a, T, C>(link: &'a Link<T>, label: char, key_tail: &mut Chars, joker: char, callback: &mut C)
716 where C: FnMut (&T) {
717
718 match *link {
719
720 None => return,
721
722 Some(ref node) => {
723
724 if label == joker || label < node.label {
725
726 visit_crossword_values_r(&node.left, label, key_tail, joker, callback);
727 }
728
729 if label == joker || label == node.label {
730
731 let mut new_tail = key_tail.clone();
732 let new_label = new_tail.next();
733
734 match new_label {
735
736 None => if let Some(ref value) = node.value {
737
738 callback(value);
739 },
740
741 Some(label) => visit_crossword_values_r(&node.middle, label, &mut new_tail, joker, callback)
742 }
743 }
744
745 if label == joker || label > node.label {
746
747 visit_crossword_values_r(&node.right, label, key_tail, joker, callback);
748 }
749 }
750 }
751}
752
753
754fn visit_crossword_values_r_mut<'a, T, C>(link: &'a mut Link<T>, label: char, key_tail: &mut Chars, joker: char, callback: &mut C)
755 where C: FnMut (&mut T) {
756
757 match *link {
758
759 None => return,
760
761 Some(ref mut node) => {
762
763 if label == joker || label < node.label {
764
765 visit_crossword_values_r_mut(&mut node.left, label, key_tail, joker, callback);
766 }
767
768 if label == joker || label == node.label {
769
770 let mut new_tail = key_tail.clone();
771 let new_label = new_tail.next();
772
773 match new_label {
774
775 None => if let Some(ref mut value) = node.value {
776
777 callback(value);
778 },
779
780 Some(label) => visit_crossword_values_r_mut(&mut node.middle, label, &mut new_tail, joker, callback)
781 }
782 }
783
784 if label == joker || label > node.label {
785
786 visit_crossword_values_r_mut(&mut node.right, label, key_tail, joker, callback);
787 }
788 }
789 }
790}
791
792
793fn pretty_print_r<'a, T>(link: &'a Link<T>, ids: &mut Tst<usize>, writer: &mut dyn Write) {
794
795 match *link {
796
797 None => return,
798
799 Some(ref node) => {
800
801 let value_box = match node.value {
802
803 None => "☐", Some(_) => "☑"
804 };
805
806 {
807 let mut get_id = |node: &Box<Node<T>>| {
808
809 let node_addr = format!("{:p}", node);
810
811 let prev_id = match ids.get(&node_addr) {
812
813 None => None,
814
815 Some(id) => Some(*id)
816 };
817
818 match prev_id {
819
820 None => {
821
822 let id = ids.len();
823 ids.insert(&node_addr, id);
824 id
825 }
826
827 Some(id) => id
828 }
829 };
830
831 let _ = writeln!(writer, r#"N{} [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"><TR><TD COLSPAN="3">{} {}</TD></TR><TR><TD PORT="l"></TD><TD PORT="m"></TD><TD PORT="r"></TD></TR></TABLE>>]"#, get_id(node), value_box, node.label);
832
833 let mut print_edge = |link, start, style| if let &Some(ref child) = link {
834
835 let _ = writeln!(writer, r#"N{}:{} -> N{} [style={}]"#, get_id(node), start, get_id(child), style);
836 };
837
838 print_edge(&node.left, "l", "solid");
839 print_edge(&node.middle, "m", "bold");
840 print_edge(&node.right, "r", "solid");
841 }
842
843 pretty_print_r(&node.left, ids, writer);
844 pretty_print_r(&node.middle, ids, writer);
845 pretty_print_r(&node.right, ids, writer);
846 }
847 }
848}
849
850
851impl<T> Tst<T> {
852
853 /// Create a new, empty `Tst`. The key is always a string slice and one needs only to provide a value
854 /// type. The following code creates an empty tree which stores `bool` values
855 ///
856 /// ```
857 /// # use ternary_tree::Tst;
858 /// let mut map: Tst<bool> = Tst::new();
859 /// ```
860 ///
861 /// Although most of the time, type inference and some context allow to simply write
862 /// ```
863 /// # use ternary_tree::Tst;
864 /// let mut map = Tst::new();
865 /// # map.insert("foo", true);
866 ///
867 /// ```
868 /// And the exact value type is properly guessed.
869
870 pub fn new() -> Self {
871
872 Tst { root: None, count: 0 }
873 }
874
875
876 /// Inserts `key` and `value` pair in the tree, returning any value previously associated with `key`.
877 ///
878 /// ```
879 /// # use ternary_tree::Tst;
880 /// let mut map = Tst::new();
881 /// assert_eq!(map.len(), 0);
882 ///
883 /// let old_value = map.insert("foo", "🍄🍄");
884 /// assert_eq!(old_value, None);
885 /// assert_eq!(map.len(), 1);
886 /// ```
887 ///
888 /// Because `key` represents a node path to `value` in the tree, an empty key is meaningless, and its
889 /// associated value cannot be stored in the tree. In such a case, `value` is given back by `insert`
890 ///
891 /// ```
892 /// # use ternary_tree::Tst;
893 /// # let mut map = Tst::new();
894 /// assert_eq!(map.len(), 0);
895 ///
896 /// let this_value = map.insert("", "woups");
897 /// assert_eq!(this_value, Some("woups"));
898 /// assert_eq!(map.len(), 0);
899 /// ```
900 ///
901 /// Another consequence of `key` representing a path in the tree is that `key` is not consumed by `insert`:
902 /// `key` is only borrowed by the tree which needs to iterate over it, but does not need to store it. Thus once
903 /// insertion is done, `key` is given back to the caller.
904
905 pub fn insert(&mut self, key: &str, value: T) -> Option<T> {
906
907 let mut key_tail = key.chars();
908
909 match key_tail.next() {
910
911 None => Some(value),
912
913 Some(label) => {
914
915 let old_value = insert_r(&mut self.root, label, key_tail, value);
916
917 if old_value.is_none() {
918
919 self.count += 1;
920 }
921
922 old_value
923 }
924 }
925 }
926
927
928 /// Returns an immutable reference to the value associated with `key`, or None.
929 ///
930 /// ```
931 /// # use ternary_tree::Tst;
932 /// # let mut map = Tst::new();
933 /// map.insert("foo", "🍄🍄");
934 ///
935 /// let v = map.get("foo");
936 /// assert_eq!(v, Some(&"🍄🍄"));
937
938 pub fn get(&self, key: &str) -> Option<&T> {
939
940 let mut key_tail = key.chars();
941
942 match key_tail.next() {
943
944 None => None,
945
946 Some(label) => get_r(&self.root, label, &mut key_tail)
947 }
948 }
949
950
951 /// Returns an mutable reference to the value associated with `key`, or `None`.
952 ///
953 /// ```
954 /// # use ternary_tree::Tst;
955 /// # let mut map = Tst::new();
956 /// map.insert("foo", "🍄".to_string());
957 ///
958 /// if let Some(v) = map.get_mut("foo") {
959 /// v.push('🍄');
960 /// }
961 ///
962 /// let v = map.get("foo");
963 /// assert_eq!(v, Some(&"🍄🍄".to_string()));
964
965 pub fn get_mut(&mut self, key: &str) -> Option<&mut T> {
966
967 let mut key_tail = key.chars();
968
969 match key_tail.next() {
970
971 None => None,
972
973 Some(label) => get_r_mut(&mut self.root, label, &mut key_tail)
974 }
975 }
976
977
978 /// Removes the value associated with `key` from the tree, and returns it. Does nothing if no value is
979 /// associated with `key`, and returns `None`.
980 ///
981 /// ```
982 /// # use ternary_tree::Tst;
983 /// # let mut map = Tst::new();
984 /// map.insert("foo", "🍄🍄".to_string());
985 ///
986 /// let v = map.remove("foo");
987 /// assert_eq!(v, Some("🍄🍄".to_string()));
988 ///
989 /// let v = map.remove("foo");
990 /// assert_eq!(v, None);
991
992 pub fn remove(&mut self, key: &str) -> Option<T> {
993
994 let mut key_tail = key.chars();
995
996 let (prune, old_value) = match key_tail.next() {
997
998 None => (false, None),
999
1000 Some(label) => remove_r(&mut self.root, label, &mut key_tail)
1001 };
1002
1003 if prune {
1004
1005 self.root = None;
1006 }
1007
1008 if old_value.is_some() {
1009
1010 self.count -= 1;
1011 }
1012
1013 old_value
1014 }
1015
1016
1017 /// Returns the number of values stored in the tree.
1018 ///
1019 /// ```
1020 /// # use ternary_tree::Tst;
1021 /// let mut map = Tst::new();
1022 /// assert_eq!(map.len(), 0);
1023 ///
1024 /// map.insert("foo", "🍄🍄");
1025 /// assert_eq!(map.len(), 1);
1026 /// ```
1027
1028 pub fn len(&self) -> usize {
1029
1030 self.count
1031 }
1032
1033
1034 /// Walks the tree, gathers various metrics about nodes, keys and values, and returns a [`Stats`](
1035 /// ./struct.Stats.html) structure to sum it up.
1036 ///
1037 /// ```
1038 /// # use ternary_tree::Tst;
1039 /// let mut map = Tst::new();
1040 /// assert_eq!(map.len(), 0);
1041 ///
1042 /// map.insert("foo", "🍄🍄");
1043 /// assert_eq!(map.len(), 1);
1044 ///
1045 /// let stats = map.stat();
1046 /// assert_eq!(stats.count.nodes, 3);
1047 /// ```
1048 ///
1049 /// See [Stats]( ./struct.Stats.html) for a detailed description of available fields.
1050
1051 pub fn stat(&self) -> Stats {
1052
1053 let empty_stats: Stats = Default::default();
1054
1055 let mut stats = stat_r(empty_stats, &self.root, 0, 0, 0);
1056
1057 stats.bytes.node = mem::size_of::<Node<T>>();
1058 stats.bytes.total = mem::size_of::<Tst<T>>()+stats.count.nodes*stats.bytes.node;
1059
1060 stats
1061 }
1062
1063
1064 /// Deletes every node and value stored in the tree.
1065 ///
1066 /// ```
1067 /// # use ternary_tree::Tst;
1068 /// let mut map = Tst::new();
1069 /// assert_eq!(map.len(), 0);
1070 ///
1071 /// map.insert("foo", "🍄🍄");
1072 /// assert_eq!(map.len(), 1);
1073 ///
1074 /// map.clear();
1075 /// assert_eq!(map.len(), 0);
1076
1077 pub fn clear(&mut self) {
1078
1079 self.root = None;
1080 self.count = 0;
1081 }
1082
1083
1084 /// Recursively walks the tree and calls `callback` closure on each immutable value. Values are found in
1085 /// alphabetical order of keys. See also the [`iter`]( ./struct.Tst.html#method.iter) method which produces the
1086 /// same sequence of values in a non-recursive way.
1087 ///
1088 /// ```
1089 /// # use ternary_tree::Tst;
1090 /// # use ternary_tree::tst;
1091 /// let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];
1092 ///
1093 /// let mut v = Vec::new();
1094 /// map.visit_values(|s| v.push(s.clone()));
1095 /// assert_eq!(v, ["🐟", "㵅", "🍄🍄"]);
1096 /// ```
1097
1098 pub fn visit_values<C>(&self, mut callback: C)
1099 where C: FnMut (&T) {
1100
1101 visit_values_r(&self.root, &mut callback);
1102 }
1103
1104
1105 /// Recursively walks the tree and calls `callback` closure on each mutable value. The same as
1106 /// [`visit_values`]( ./struct.Tst.html#method.visit_values), except the `_mut` version works on mutable
1107 /// values, and does not have an iterator counterpart.
1108
1109 pub fn visit_values_mut<C>(&mut self, mut callback: C)
1110 where C: FnMut (&mut T) {
1111
1112 visit_values_r_mut(&mut self.root, &mut callback);
1113 }
1114
1115
1116 /// Recursively walks the tree and calls `callback` closure on each immutable value whose key begins with
1117 /// `key_prefix`. Values are found in alphabetical order of keys. See also the [`iter_complete`](
1118 /// ./struct.Tst.html#method.iter_complete) method which produces the same sequence of values in a
1119 /// non-recursive way.
1120 ///
1121 /// ```
1122 /// # use ternary_tree::Tst;
1123 /// # use ternary_tree::tst;
1124 /// let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];
1125 ///
1126 /// let mut v = Vec::new();
1127 /// map.visit_complete_values("ba", |s| v.push(s.clone()));
1128 /// assert_eq!(v, ["🐟", "㵅"]);
1129 /// ```
1130 ///
1131 /// Some key is not a prefix of itself. In the previous example, `visit_complete_values` called with `foo`
1132 /// prefix would find no value
1133 ///
1134 /// ```
1135 /// # use ternary_tree::Tst;
1136 /// # use ternary_tree::tst;
1137 /// # let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];
1138 /// let mut v = Vec::new();
1139 /// map.visit_complete_values("foo", |s| v.push(s.clone()));
1140 /// assert_eq!(v.is_empty(), true);
1141 /// ```
1142 ///
1143 /// If `key_prefix` is empty, `visit_complete_values` behaves as [`visit_values`](
1144 /// ./struct.Tst.html#method.visit_values), and all values stored in the tree are found.
1145
1146 pub fn visit_complete_values<C>(&self, key_prefix: &str, mut callback: C)
1147 where C: FnMut (&T) {
1148
1149 let mut prefix_tail = key_prefix.chars();
1150
1151 match prefix_tail.next() {
1152
1153 None => visit_values_r(&self.root, &mut callback),
1154
1155 Some(label) => {
1156
1157 let new_root = find_complete_root_r(&self.root, label, prefix_tail);
1158 visit_complete_values_r(new_root, &mut callback)
1159 }
1160 }
1161 }
1162
1163
1164 /// Recursively walks the tree and calls `callback` closure on each mutable value whose key begins with
1165 /// `key_prefix`. The same as [`visit_complete_values`]( ./struct.Tst.html#method.visit_complete_values),
1166 /// except the `_mut` version works on mutable values, and does not have an iterator counterpart.
1167
1168 pub fn visit_complete_values_mut<C>(&mut self, key_prefix: &str, mut callback: C)
1169 where C: FnMut (&mut T) {
1170
1171 let mut prefix_tail = key_prefix.chars();
1172
1173 match prefix_tail.next() {
1174
1175 None => visit_values_r_mut(&mut self.root, &mut callback),
1176
1177 Some(label) => {
1178
1179 let mut new_root = find_complete_root_r_mut(&mut self.root, label, prefix_tail);
1180 visit_complete_values_r_mut(&mut new_root, &mut callback)
1181 }
1182 }
1183 }
1184
1185
1186 /// Recursively walks the tree and calls `callback` closure on each immutable value whose key is _close_ to
1187 /// `key`. A key is considered _close_ to `key` within a [Hamming distance](
1188 /// http://en.wikipedia.org/wiki/Hamming_distance) of `range` from `key`. Values are found in alphabetical
1189 /// order of keys. See also the [`iter_neighbor`]( ./struct.Tst.html#method.iter_neighbor) method which
1190 /// produces the same sequence of values in a non-recursive way.
1191 ///
1192 /// ```
1193 /// # use ternary_tree::Tst;
1194 /// # use ternary_tree::tst;
1195 /// let map = tst!["fo" => "🍄", "bar" => "🐟", "baz" => "㵅", "fooo" => "🍄🍄🍄"];
1196 ///
1197 /// let mut v = Vec::new();
1198 /// map.visit_neighbor_values("bar", 1, |s| v.push(s.clone()));
1199 /// assert_eq!(v, ["🐟", "㵅"]);
1200 /// ```
1201 ///
1202 /// An empty `key` is allowed, and with a `range` of _n_, it will find all values whose key length is up to
1203 /// _n_. In the previous example `visit_neighbor_values` called with `""` key and range `3` would find all
1204 /// value whose key length is ≤ 3
1205 ///
1206 /// ```
1207 /// # use ternary_tree::Tst;
1208 /// # use ternary_tree::tst;
1209 /// let map = tst!["fo" => "🍄", "bar" => "🐟", "baz" => "㵅", "fooo" => "🍄🍄🍄"];
1210 ///
1211 /// let mut v = Vec::new();
1212 /// map.visit_neighbor_values("", 3, |s| v.push(s.clone()));
1213 /// assert_eq!(v, ["🐟", "㵅", "🍄"]);
1214 /// ```
1215
1216 pub fn visit_neighbor_values<C>(&self, key: &str, range: usize, mut callback: C)
1217 where C: FnMut (&T) {
1218
1219 let mut key_tail = key.chars();
1220 let key_len = key.chars().count();
1221 let label = key_tail.next();
1222 let tail_len = if key_len == 0 { 0 } else { key_len-1 };
1223
1224 visit_neighbor_values_r(&self.root, label, &mut key_tail, tail_len, range, &mut callback);
1225 }
1226
1227
1228 /// Recursively walks the tree and calls `callback` closure on each mutable value whose key is _close_ to `key`
1229 /// ([Hamming distance]( http://en.wikipedia.org/wiki/Hamming_distance) of `range`). The same as
1230 /// [`visit_neighbor_values`]( ./struct.Tst.html#method.visit_neighbor_values), except the `_mut` version works
1231 /// on mutable values, and does not have an iterator counterpart.
1232
1233 pub fn visit_neighbor_values_mut<C>(&mut self, key: &str, range: usize, mut callback: C)
1234 where C: FnMut (&mut T) {
1235
1236 let mut key_tail = key.chars();
1237 let key_len = key.chars().count();
1238 let label = key_tail.next();
1239 let tail_len = if key_len == 0 { 0 } else { key_len-1 };
1240
1241 visit_neighbor_values_r_mut(&mut self.root, label, &mut key_tail, tail_len, range, &mut callback);
1242 }
1243
1244
1245 /// Recursively walks the tree and calls `callback` closure on each immutable value whose key _matches_
1246 /// `pattern`. The `pattern` is a string slice where each `joker` character stands for _any_ character. Values
1247 /// are found in alphabetical order of keys. See also the [`iter_crossword`](
1248 /// ./struct.Tst.html#method.iter_crossword) method which produces the same sequence of values in a
1249 /// non-recursive way.
1250 ///
1251 /// ```
1252 /// # use ternary_tree::Tst;
1253 /// # use ternary_tree::tst;
1254 /// let map = tst!["fo" => "🍄", "bar" => "🐟", "baz" => "㵅", "fooo" => "🍄🍄🍄"];
1255 ///
1256 /// let mut v = Vec::new();
1257 /// map.visit_crossword_values("?a?", '?', |s| v.push(s.clone()));
1258 /// assert_eq!(v, ["🐟", "㵅"]);
1259 /// ```
1260 ///
1261 /// A `pattern` of _n_ `joker` characters will find all values whose key length is exactly _n_
1262 ///
1263 /// ```
1264 /// # use ternary_tree::Tst;
1265 /// # use ternary_tree::tst;
1266 /// let mut v = Vec::new();
1267 /// let map = tst!["fo" => "🍄", "bar" => "🐟", "baz" => "㵅", "fooo" => "🍄🍄🍄"];
1268 ///
1269 /// map.visit_crossword_values("???", '?', |s| v.push(s.clone()));
1270 /// assert_eq!(v, ["🐟", "㵅"]);
1271 /// ```
1272 ///
1273 /// An empty `pattern` is meaningless, and does not find any value.
1274
1275 pub fn visit_crossword_values<C>(&self, pattern: &str, joker: char, mut callback: C)
1276 where C: FnMut (&T) {
1277
1278 let mut pattern_tail = pattern.chars();
1279
1280 match pattern_tail.next() {
1281
1282 None => return,
1283
1284 Some(label) => visit_crossword_values_r(&self.root, label, &mut pattern_tail, joker, &mut callback)
1285 }
1286 }
1287
1288
1289 /// Recursively walks the tree and calls `callback` closure on each mutable value whose key _matches_ `pattern`
1290 /// with `joker` characters. The same as [`visit_crossword_values`](
1291 /// ./struct.Tst.html#method.visit_crossword_values), except the `_mut` version works on mutable values, and
1292 /// does not have an iterator counterpart.
1293
1294 pub fn visit_crossword_values_mut<C>(&mut self, pattern: &str, joker: char, mut callback: C)
1295 where C: FnMut (&mut T) {
1296
1297 let mut pattern_tail = pattern.chars();
1298
1299 match pattern_tail.next() {
1300
1301 None => return,
1302
1303 Some(label) => visit_crossword_values_r_mut(&mut self.root, label, &mut pattern_tail, joker, &mut callback)
1304 }
1305 }
1306
1307
1308 /// Dump the tree in `writer` using the _dot_ language of [Graphviz]( http://www.graphviz.org) tools. A checked
1309 /// box "☑" denotes a node which stores a value (it corresponds to the last character of a key). An empty box
1310 /// "☐" means that the node has no value. Mostly used for documentation and debugging purpose. See the [module
1311 /// documentation]( ./index.html) for an example.
1312
1313 pub fn pretty_print(&self, writer: &mut dyn Write) {
1314
1315 let _ = writeln!(writer, "digraph {{");
1316 let _ = writeln!(writer, "node [shape=plaintext]");
1317
1318 let mut ids = Tst::new();
1319
1320 pretty_print_r(&self.root, &mut ids, writer);
1321
1322 let _ = writeln!(writer, "}}");
1323 }
1324
1325
1326 /// Create a [double-ended]( http://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html) iterator which
1327 /// successively returns all values of the tree. Values are immutable, and are found in alphabetical order of
1328 /// keys by [`next`]( ./struct.TstIterator.html#method.next), and in the opposite order by [`next_back`](
1329 /// ./struct.TstIterator.html#method.next_back). Methods [`current_key`](
1330 /// ./struct.TstIterator.html#method.current_key) and [`current_key_back`](
1331 /// ./struct.TstIterator.html#method.current_key_back) regenerate the key associated with the last value
1332 /// returned by [`next`]( ./struct.TstIterator.html#method.next) or [`next_back`](
1333 /// struct.TstIterator.html#method.next_back). See also the [`visit_value_mut`](
1334 /// ./struct.Tst.html#method.visit_values_mut) method which produces the same sequence of mutable values.
1335 ///
1336 /// ```
1337 /// # use ternary_tree::Tst;
1338 /// # use ternary_tree::tst;
1339 /// let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];
1340 ///
1341 /// let mut it = map.iter();
1342 ///
1343 /// let first_value = it.next();
1344 /// let last_value = it.next_back();
1345 ///
1346 /// let first_key = it.current_key();
1347 /// let last_key = it.current_key_back();
1348 ///
1349 /// assert_eq!((first_key, first_value), ("bar".to_string(), Some(&"🐟")));
1350 /// assert_eq!((last_key, last_value), ("foo".to_string(), Some(&"🍄🍄")));
1351 /// ```
1352
1353 pub fn iter(&self) -> TstIterator<T> {
1354
1355 TstIterator::<T>::new(&self)
1356 }
1357
1358
1359 /// Create a [double-ended]( http://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html) iterator which
1360 /// successively returns all values whose key begins with `prefix`. Values are immutable, and are found in
1361 /// alphabetical order of keys by [`next`]( ./struct.TstCompleteIterator.html#method.next), and in the opposite
1362 /// order by [`next_back`]( ./struct.TstCompleteIterator.html#method.next_back). Methods [`current_key`](
1363 /// ./struct.TstCompleteIterator.html#method.current_key) and [`current_key_back`](
1364 /// ./struct.TstCompleteIterator.html#method.current_key_back) regenerate the key associated with the last
1365 /// value returned by [`next`]( ./struct.TstCompleteIterator.html#method.next) or [`next_back`](
1366 /// struct.TstCompleteIterator.html#method.next_back). See also the [`visit_complete_value_mut`](
1367 /// ./struct.Tst.html#method.visit_complete_values_mut) method which produces the same sequence of mutable
1368 /// values.
1369 ///
1370 /// ```
1371 /// # use ternary_tree::Tst;
1372 /// # use ternary_tree::tst;
1373 /// let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];
1374 ///
1375 /// let mut it = map.iter_complete("b");
1376 ///
1377 /// let first_value = it.next();
1378 /// let last_value = it.next_back();
1379 ///
1380 /// let first_key = it.current_key();
1381 /// let last_key = it.current_key_back();
1382 ///
1383 /// assert_eq!((first_key, first_value), ("bar".to_string(), Some(&"🐟")));
1384 /// assert_eq!((last_key, last_value), ("baz".to_string(), Some(&"㵅")));
1385 /// ```
1386
1387 pub fn iter_complete(&self, prefix: &str) -> TstCompleteIterator<T> {
1388
1389 TstCompleteIterator::<T>::new(&self, prefix)
1390 }
1391
1392
1393 /// Create a [double-ended]( http://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html) iterator which
1394 /// successively returns all values whose key is _close_ to `key`. A key is considered _close_ to `key` within
1395 /// a [Hamming distance]( http://en.wikipedia.org/wiki/Hamming_distance) of `range` from `key`. An empty `key`
1396 /// is allowed, and with a `range` of _n_, it will find all values whose key length is up to _n_. Values are
1397 /// immutable, and are found in alphabetical order of keys by [`next`](
1398 /// ./struct.TstNeighborIterator.html#method.next), and in the opposite order by [`next_back`](
1399 /// ./struct.TstNeighborIterator.html#method.next_back). Methods [`current_key`](
1400 /// ./struct.TstNeighborIterator.html#method.current_key) and [`current_key_back`](
1401 /// ./struct.TstNeighborIterator.html#method.current_key_back) regenerate the key associated with the last
1402 /// value returned by [`next`]( ./struct.TstNeighborIterator.html#method.next) or [`next_back`](
1403 /// struct.TstNeighborIterator.html#method.next_back). See also the [`visit_neighbor_value_mut`](
1404 /// ./struct.Tst.html#method.visit_neighbor_values_mut) method which produces the same sequence of mutable
1405 /// values.
1406 ///
1407 /// ```
1408 /// # use ternary_tree::Tst;
1409 /// # use ternary_tree::tst;
1410 /// let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];
1411 ///
1412 /// let mut it = map.iter_neighbor("bar", 1);
1413 ///
1414 /// let first_value = it.next();
1415 /// let last_value = it.next_back();
1416 ///
1417 /// let first_key = it.current_key();
1418 /// let last_key = it.current_key_back();
1419 ///
1420 /// assert_eq!((first_key, first_value), ("bar".to_string(), Some(&"🐟")));
1421 /// assert_eq!((last_key, last_value), ("baz".to_string(), Some(&"㵅")));
1422 /// ```
1423
1424 pub fn iter_neighbor<'a, 'b>(&'a self, key: &'b str, range: usize) -> TstNeighborIterator<'a, 'b, T> {
1425
1426 TstNeighborIterator::<T>::new(&self, key, range)
1427 }
1428
1429
1430 /// Create a [double-ended]( http://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html) iterator which
1431 /// successively returns all values whose key _matches_ `pattern`. The `pattern` is a string slice where each
1432 /// `joker` character stands for _any_ character. A `pattern` of _n_ `joker` characters will find all values
1433 /// whose key length is exactly _n_. Values are immutable, and are found in alphabetical order of keys by
1434 /// [`next`]( ./struct.TstCrosswordIterator.html#method.next), and in the opposite order by [`next_back`](
1435 /// ./struct.TstCrosswordIterator.html#method.next_back). Methods [`current_key`](
1436 /// ./struct.TstCrosswordIterator.html#method.current_key) and [`current_key_back`](
1437 /// ./struct.TstCrosswordIterator.html#method.current_key_back) regenerate the key associated with the last
1438 /// value returned by [`next`]( ./struct.TstCrosswordIterator.html#method.next) or [`next_back`](
1439 /// struct.TstCrosswordIterator.html#method.next_back). See also the [`visit_crossword_value_mut`](
1440 /// ./struct.Tst.html#method.visit_crossword_values_mut) method which produces the same sequence of mutable
1441 /// values.
1442 ///
1443 /// ```
1444 /// # use ternary_tree::Tst;
1445 /// # use ternary_tree::tst;
1446 /// let map = tst!["foo" => "🍄🍄", "bar" => "🐟", "baz" => "㵅"];
1447 ///
1448 /// let mut it = map.iter_crossword("?a?", '?');
1449 ///
1450 /// let first_value = it.next();
1451 /// let last_value = it.next_back();
1452 ///
1453 /// let first_key = it.current_key();
1454 /// let last_key = it.current_key_back();
1455 ///
1456 /// assert_eq!((first_key, first_value), ("bar".to_string(), Some(&"🐟")));
1457 /// assert_eq!((last_key, last_value), ("baz".to_string(), Some(&"㵅")));
1458 /// ```
1459
1460 pub fn iter_crossword<'a, 'b>(&'a self, pattern: &'b str, joker: char) -> TstCrosswordIterator<'a, 'b, T> {
1461
1462 TstCrosswordIterator::<T>::new(&self, pattern, joker)
1463 }
1464}
1465
1466
1467/// A shortcut macro to help create a small tree with a list of known `"key" => value` pairs. Calls [`insert`](
1468/// ./struct.Tst.html#method.insert) on each pair, in order.
1469///
1470/// ```
1471/// # use ternary_tree::Tst;
1472/// # use ternary_tree::tst;
1473/// let map = tst!["fo" => "🍄", "bar" => "🐟", "baz" => "㵅", "fooo" => "🍄🍄🍄"];
1474/// assert_eq!(map.len(), 4)
1475/// ````
1476
1477#[macro_export]
1478macro_rules! tst {
1479
1480 () => {{
1481 $crate::Tst::new()
1482 }};
1483
1484 ($($key:expr => $value:expr,)+) => (tst!($($key => $value),+));
1485
1486 ($($key: expr => $val: expr),*) => {{
1487
1488 let mut tst = $crate::Tst::new();
1489 $(
1490 tst.insert($key, $val);
1491 )*
1492
1493 tst
1494 }};
1495}
1496
1497
1498#[derive(Debug, PartialEq)]
1499enum TstIteratorAction {
1500
1501 GoLeft,
1502 Visit,
1503 GoMiddle,
1504 GoRight
1505}
1506
1507use self::TstIteratorAction::*;
1508
1509
1510/// A [double-ended]( http://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html) iterator which
1511/// successively returns all values of the tree. See [`iter`]( struct.Tst.html#method.iter) method for a brief
1512/// description with a short example.
1513
1514#[derive(Debug)]
1515pub struct TstIterator<'a, T: 'a> {
1516
1517 todo_i: Vec<(&'a Node<T>, TstIteratorAction)>,
1518 last_i: Option<&'a Node<T>>,
1519
1520 todo_j: Vec<(&'a Node<T>, TstIteratorAction)>,
1521 last_j: Option<&'a Node<T>>
1522}
1523
1524
1525macro_rules! gen_it_path {
1526
1527 ($path_of_x:ident, $todo_x:ident, $a1:expr, $a2:expr) => (
1528
1529 pub fn $path_of_x(&self) -> String {
1530
1531 let mut path = String::new();
1532
1533 for todo in self.$todo_x.iter() {
1534
1535 if todo.1 == $a1 || todo.1 == $a2 {
1536
1537 path.push(todo.0.label);
1538 }
1539 }
1540
1541 path
1542 }
1543 );
1544}
1545
1546
1547impl<'a, T> TstIterator<'a, T> {
1548
1549 pub fn new(tst: &'a Tst<T>) -> Self {
1550
1551 TstIterator::new_from_root(&tst.root)
1552 }
1553
1554
1555 fn new_from_root(root: &'a Link<T>) -> Self {
1556
1557 let mut it = TstIterator {
1558
1559 todo_i: Vec::new(), last_i: None,
1560 todo_j: Vec::new(), last_j: None,
1561 };
1562
1563 if let Some(ref node) = root {
1564
1565 it.todo_i.push((node, GoLeft));
1566 it.todo_j.push((node, GoRight));
1567 }
1568
1569 it
1570 }
1571
1572
1573 gen_it_path!(current_key, todo_i, GoMiddle, GoRight);
1574 gen_it_path!(current_key_back, todo_j, Visit, GoLeft);
1575}
1576
1577
1578impl<'a, T> Iterator for TstIterator<'a, T> {
1579
1580 type Item = &'a T;
1581
1582 fn next(&mut self) -> Option<&'a T> {
1583
1584 let mut found = None;
1585
1586 while let Some((node, action)) = self.todo_i.pop() {
1587
1588 match action {
1589
1590 GoLeft => {
1591
1592 self.todo_i.push((node, Visit));
1593
1594 if let Some(ref child) = node.left {
1595
1596 self.todo_i.push((child, GoLeft));
1597 }
1598 }
1599
1600 Visit => {
1601
1602 if node.value.is_some() {
1603
1604 if let Some(node_j) = self.last_j {
1605
1606 if ptr::eq(node, node_j) {
1607
1608 self.todo_i.clear();
1609 self.todo_j.clear();
1610
1611 found = None;
1612 break;
1613 }
1614 }
1615 }
1616
1617 self.todo_i.push((node, GoMiddle));
1618
1619 if let Some(ref value) = node.value {
1620
1621 self.last_i = Some(node);
1622 found = Some(value);
1623
1624 break;
1625 }
1626 }
1627
1628 GoMiddle => {
1629
1630 self.todo_i.push((node, GoRight));
1631
1632 if let Some(ref child) = node.middle {
1633
1634 self.todo_i.push((child, GoLeft));
1635 }
1636 }
1637
1638 GoRight => {
1639
1640 if let Some(ref child) = node.right {
1641
1642 self.todo_i.push((child, GoLeft));
1643 }
1644 }
1645 }
1646 }
1647
1648 found
1649 }
1650}
1651
1652
1653impl<'a, T> IntoIterator for &'a Tst<T> {
1654
1655 type Item = &'a T;
1656 type IntoIter = TstIterator<'a, T>;
1657
1658 fn into_iter(self) -> Self::IntoIter {
1659
1660 self.iter()
1661 }
1662}
1663
1664
1665impl<'a, T> DoubleEndedIterator for TstIterator<'a, T> {
1666
1667 fn next_back(&mut self) -> Option<&'a T> {
1668
1669 let mut found = None;
1670
1671 while let Some((node, action)) = self.todo_j.pop() {
1672
1673 match action {
1674
1675 GoRight => {
1676
1677 self.todo_j.push((node, GoMiddle));
1678
1679 if let Some(ref child) = node.right {
1680
1681 self.todo_j.push((child, GoRight));
1682 }
1683 }
1684
1685 Visit => {
1686
1687 if node.value.is_some() {
1688
1689 if let Some(node_i) = self.last_i {
1690
1691 if ptr::eq(node, node_i) {
1692
1693 self.todo_i.clear();
1694 self.todo_j.clear();
1695
1696 found = None;
1697 break;
1698 }
1699 }
1700 }
1701
1702 self.todo_j.push((node, GoLeft));
1703
1704 if let Some(ref value) = node.value {
1705
1706 self.last_j = Some(node);
1707 found = Some(value);
1708
1709 break;
1710 }
1711 }
1712
1713 GoMiddle => {
1714
1715 self.todo_j.push((node, Visit));
1716
1717 if let Some(ref child) = node.middle {
1718
1719 self.todo_j.push((child, GoRight));
1720 }
1721 }
1722
1723 GoLeft => {
1724
1725 if let Some(ref child) = node.left {
1726
1727 self.todo_j.push((child, GoRight));
1728 }
1729 }
1730 }
1731 }
1732
1733 found
1734 }
1735}
1736
1737
1738/// A [double-ended]( http://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html) iterator which
1739/// successively returns all values whose key begins with `prefix`. See [`iter_complete`](
1740/// struct.Tst.html#method.iter_complete) method for a brief description with a short example.
1741
1742#[derive(Debug)]
1743pub struct TstCompleteIterator<'a, T: 'a> {
1744
1745 it: TstIterator<'a, T>,
1746 prefix: String
1747}
1748
1749
1750impl<'a, T> TstCompleteIterator<'a, T> {
1751
1752 pub fn new(tst: &'a Tst<T>, key_prefix: &str) -> Self {
1753
1754 let mut key_tail = key_prefix.chars();
1755
1756 TstCompleteIterator {
1757
1758 it : match key_tail.next() {
1759
1760 None => TstIterator::<T>::new(tst),
1761
1762 Some(label) => {
1763
1764 let new_root = find_complete_root_r(&tst.root, label, key_tail);
1765 TstIterator::<T>::new_from_root(new_root)
1766 }
1767 },
1768
1769 prefix: key_prefix.to_string()
1770 }
1771 }
1772
1773
1774 pub fn current_key(&self) -> String {
1775
1776 self.prefix.clone() + &self.it.current_key()
1777 }
1778
1779
1780 pub fn current_key_back(&self) -> String {
1781
1782 self.prefix.clone() + &self.it.current_key_back()
1783 }
1784}
1785
1786
1787impl<'a, T> Iterator for TstCompleteIterator<'a, T> {
1788
1789 type Item = &'a T;
1790
1791 fn next(&mut self) -> Option<&'a T> {
1792
1793 self.it.next()
1794 }
1795}
1796
1797
1798impl<'a, T> DoubleEndedIterator for TstCompleteIterator<'a, T> {
1799
1800 fn next_back(&mut self) -> Option<&'a T> {
1801
1802 self.it.next_back()
1803 }
1804}
1805
1806
1807/// A [double-ended]( http://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html) iterator which
1808/// successively returns all values whose key is _close_ to `key`. See [`iter_neighbor`](
1809/// struct.Tst.html#method.iter_neighbor) method for a brief description with a short example.
1810
1811#[derive(Debug)]
1812pub struct TstNeighborIterator<'a, 'b, T: 'a> {
1813
1814 todo_i: Vec<(&'a Node<T>, TstIteratorAction, Option<char>, Chars<'b>, usize, usize)>,
1815 last_i: Option<&'a Node<T>>,
1816
1817 todo_j: Vec<(&'a Node<T>, TstIteratorAction, Option<char>, Chars<'b>, usize, usize)>,
1818 last_j: Option<&'a Node<T>>
1819}
1820
1821
1822impl<'a, 'b, T> TstNeighborIterator<'a, 'b, T> {
1823
1824 pub fn new(tst: &'a Tst<T>, key: &'b str, range: usize) -> Self {
1825
1826 let mut it = TstNeighborIterator {
1827
1828 todo_i: Vec::new(), last_i: None,
1829 todo_j: Vec::new(), last_j: None,
1830 };
1831
1832 if let Some(ref node) = &tst.root {
1833
1834 let mut key_tail = key.chars();
1835 let key_len = key.chars().count();
1836 let label = key_tail.next();
1837 let tail_len = if key_len == 0 { 0 } else {key_len-1 };
1838
1839 it.todo_i.push((node, GoLeft, label, key_tail.clone(), tail_len, range));
1840 it.todo_j.push((node, GoRight, label, key_tail, tail_len, range));
1841 }
1842
1843 it
1844 }
1845
1846
1847 gen_it_path!(current_key, todo_i, GoMiddle, GoRight);
1848 gen_it_path!(current_key_back, todo_j, Visit, GoLeft);
1849}
1850
1851
1852impl<'a, 'b, T> Iterator for TstNeighborIterator<'a, 'b, T> {
1853
1854 type Item = &'a T;
1855
1856 fn next(&mut self) -> Option<&'a T> {
1857
1858 let mut found = None;
1859
1860 while let Some((node, action, label, mut key_tail, tail_len, range)) = self.todo_i.pop() {
1861
1862 match action {
1863
1864 GoLeft => {
1865
1866 self.todo_i.push((node, Visit, label, key_tail.clone(), tail_len, range));
1867
1868 if let Some(label) = label {
1869
1870 if range == 0 && label >= node.label {
1871
1872 continue;
1873 }
1874 }
1875
1876 if let Some(ref child) = node.left {
1877
1878 self.todo_i.push((child, GoLeft, label, key_tail, tail_len, range));
1879 }
1880 }
1881
1882 Visit => {
1883
1884 if node.value.is_some() {
1885
1886 if let Some(node_j) = self.last_j {
1887
1888 if ptr::eq(node, node_j) {
1889
1890 self.todo_i.clear();
1891 self.todo_j.clear();
1892
1893 found = None;
1894 break;
1895 }
1896 }
1897 }
1898
1899 self.todo_i.push((node, GoMiddle, label, key_tail, tail_len, range));
1900
1901 if let Some(ref value) = node.value {
1902
1903 let delta = match label {
1904
1905 None => 1,
1906
1907 Some(label) => if label==node.label { 0 } else { 1 }
1908
1909 };
1910
1911 if range >= delta {
1912
1913 let new_range = range - delta;
1914
1915 if tail_len <= new_range {
1916
1917 self.last_i = Some(node);
1918 found = Some(value);
1919
1920 break;
1921 }
1922 }
1923 }
1924 }
1925
1926 GoMiddle => {
1927
1928 self.todo_i.push((node, GoRight, label, key_tail.clone(), tail_len, range));
1929
1930 let delta = match label {
1931
1932 None => 1,
1933
1934 Some(label) => if label==node.label { 0 } else { 1 }
1935 };
1936
1937 if range >= delta {
1938
1939 let new_range = range - delta;
1940
1941 let new_label = key_tail.next();
1942 let new_len = if tail_len > 0 { tail_len-1 } else { tail_len };
1943
1944 if let Some(ref child) = node.middle {
1945
1946 self.todo_i.push((child, GoLeft, new_label, key_tail, new_len, new_range));
1947 }
1948 }
1949 }
1950
1951 GoRight => {
1952
1953 if let Some(label) = label {
1954
1955 if range == 0 && label <= node.label {
1956
1957 continue;
1958 }
1959 }
1960
1961 if let Some(ref child) = node.right {
1962
1963 self.todo_i.push((child, GoLeft, label, key_tail, tail_len, range));
1964 }
1965 }
1966 }
1967 }
1968
1969 found
1970 }
1971}
1972
1973
1974impl<'a, 'b, T> DoubleEndedIterator for TstNeighborIterator<'a, 'b, T> {
1975
1976 fn next_back(&mut self) -> Option<&'a T> {
1977
1978 let mut found = None;
1979
1980 while let Some((node, action, label, mut key_tail, tail_len, range)) = self.todo_j.pop() {
1981
1982 match action {
1983
1984 GoRight => {
1985
1986 self.todo_j.push((node, GoMiddle, label, key_tail.clone(), tail_len, range));
1987
1988 if let Some(label) = label {
1989
1990 if range == 0 && label <= node.label {
1991
1992 continue;
1993 }
1994 }
1995
1996 if let Some(ref child) = node.right {
1997
1998 self.todo_j.push((child, GoRight, label, key_tail, tail_len, range));
1999 }
2000 }
2001
2002 Visit => {
2003
2004 if node.value.is_some() {
2005
2006 if let Some(node_i) = self.last_i {
2007
2008 if ptr::eq(node, node_i) {
2009
2010 self.todo_i.clear();
2011 self.todo_j.clear();
2012
2013 found = None;
2014 break;
2015 }
2016 }
2017 }
2018
2019 self.todo_j.push((node, GoLeft, label, key_tail, tail_len, range));
2020
2021 if let Some(ref value) = node.value {
2022
2023 let delta = match label {
2024
2025 None => 1,
2026
2027 Some(label) => if label==node.label { 0 } else { 1 }
2028
2029 };
2030
2031 if range >= delta {
2032
2033 let new_range = range - delta;
2034
2035 if tail_len <= new_range {
2036
2037 self.last_j = Some(node);
2038 found = Some(value);
2039
2040 break;
2041 }
2042 }
2043 }
2044 }
2045
2046 GoMiddle => {
2047
2048 self.todo_j.push((node, Visit, label, key_tail.clone(), tail_len, range));
2049
2050 let delta = match label {
2051
2052 None => 1,
2053
2054 Some(label) => if label==node.label { 0 } else { 1 }
2055
2056 };
2057
2058 if range >= delta {
2059
2060 let new_range = range - delta;
2061
2062 let new_label = key_tail.next();
2063 let new_len = if tail_len > 0 { tail_len-1 } else { tail_len };
2064
2065 if let Some(ref child) = node.middle {
2066
2067 self.todo_j.push((child, GoRight, new_label, key_tail, new_len, new_range));
2068 }
2069 }
2070 }
2071
2072 GoLeft => {
2073
2074 if let Some(label) = label {
2075
2076 if range == 0 && label >= node.label {
2077
2078 continue;
2079 }
2080 }
2081
2082 if let Some(ref child) = node.left {
2083
2084 self.todo_j.push((child, GoRight, label, key_tail, tail_len, range));
2085 }
2086 }
2087 }
2088 }
2089
2090 found
2091 }
2092}
2093
2094
2095/// A [double-ended]( http://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html) iterator which
2096/// successively returns all values whose key _matches_ `pattern`. See [`iter_crossword`](
2097/// struct.Tst.html#method.iter_crossword) method for a brief description with a short example.
2098
2099#[derive(Debug)]
2100pub struct TstCrosswordIterator<'a, 'b, T: 'a> {
2101
2102 todo_i: Vec<(&'a Node<T>, TstIteratorAction, char, Chars<'b>, usize)>,
2103 last_i: Option<&'a Node<T>>,
2104
2105 todo_j: Vec<(&'a Node<T>, TstIteratorAction, char, Chars<'b>, usize)>,
2106 last_j: Option<&'a Node<T>>,
2107
2108 joker: char
2109}
2110
2111
2112impl<'a, 'b, T> TstCrosswordIterator<'a, 'b, T> {
2113
2114 pub fn new(tst: &'a Tst<T>, key: &'b str, joker: char) -> Self {
2115
2116 let mut it = TstCrosswordIterator {
2117
2118 todo_i: Vec::new(), last_i: None,
2119 todo_j: Vec::new(), last_j: None,
2120 joker,
2121
2122 };
2123
2124 if let Some(ref node) = &tst.root {
2125
2126 let mut key_tail = key.chars();
2127
2128 if let Some(label) = key_tail.next() {
2129
2130 let tail_len = key.chars().count()-1;
2131
2132 it.todo_i.push((node, GoLeft, label, key_tail.clone(), tail_len));
2133 it.todo_j.push((node, GoRight, label, key_tail, tail_len));
2134 }
2135 }
2136
2137 it
2138 }
2139
2140
2141 gen_it_path!(current_key, todo_i, GoMiddle, GoRight);
2142 gen_it_path!(current_key_back, todo_j, Visit, GoLeft);
2143}
2144
2145
2146impl<'a, 'b, T> Iterator for TstCrosswordIterator<'a, 'b, T> {
2147
2148 type Item = &'a T;
2149
2150 fn next(&mut self) -> Option<&'a T> {
2151
2152 let mut found = None;
2153
2154 while let Some((node, action, label, mut key_tail, tail_len)) = self.todo_i.pop() {
2155
2156 match action {
2157
2158 GoLeft => {
2159
2160 self.todo_i.push((node, Visit, label, key_tail.clone(), tail_len));
2161
2162 if label == self.joker || label < node.label {
2163
2164 if let Some(ref child) = node.left {
2165
2166 self.todo_i.push((child, GoLeft, label, key_tail, tail_len));
2167 }
2168 }
2169 }
2170
2171 Visit => {
2172
2173 if node.value.is_some() {
2174
2175 if let Some(node_j) = self.last_j {
2176
2177 if ptr::eq(node, node_j) {
2178
2179 self.todo_i.clear();
2180 self.todo_j.clear();
2181
2182 found = None;
2183 break;
2184 }
2185 }
2186 }
2187
2188 self.todo_i.push((node, GoMiddle, label, key_tail, tail_len));
2189
2190 if let Some(ref value) = node.value {
2191
2192 if tail_len == 0 && (label == self.joker || label == node.label) {
2193
2194 self.last_i = Some(node);
2195 found = Some(value);
2196
2197 break;
2198 }
2199 }
2200 }
2201
2202 GoMiddle => {
2203
2204 self.todo_i.push((node, GoRight, label, key_tail.clone(), tail_len));
2205
2206 if label == self.joker || label == node.label {
2207
2208 if let Some(ref child) = node.middle {
2209
2210 if let Some(new_label) = key_tail.next() {
2211
2212 self.todo_i.push((child, GoLeft, new_label, key_tail, tail_len-1));
2213 }
2214 }
2215 }
2216 }
2217
2218 GoRight => {
2219
2220 if label == self.joker || label > node.label {
2221
2222 if let Some(ref child) = node.right {
2223
2224 self.todo_i.push((child, GoLeft, label, key_tail, tail_len));
2225 }
2226 }
2227 }
2228 }
2229 }
2230
2231 found
2232 }
2233}
2234
2235
2236impl<'a, 'b, T> DoubleEndedIterator for TstCrosswordIterator<'a, 'b, T> {
2237
2238 fn next_back(&mut self) -> Option<&'a T> {
2239
2240 let mut found = None;
2241
2242 while let Some((node, action, label, mut key_tail, tail_len)) = self.todo_j.pop() {
2243
2244 match action {
2245
2246 GoRight => {
2247
2248 self.todo_j.push((node, GoMiddle, label, key_tail.clone(), tail_len));
2249
2250 if label == self.joker || label > node.label {
2251
2252 if let Some(ref child) = node.right {
2253
2254 self.todo_j.push((child, GoRight, label, key_tail, tail_len));
2255 }
2256 }
2257 }
2258
2259 Visit => {
2260
2261 if node.value.is_some() {
2262
2263 if let Some(node_i) = self.last_i {
2264
2265 if ptr::eq(node, node_i) {
2266
2267 self.todo_i.clear();
2268 self.todo_j.clear();
2269
2270 found = None;
2271 break;
2272 }
2273 }
2274 }
2275
2276 self.todo_j.push((node, GoLeft, label, key_tail, tail_len));
2277
2278 if let Some(ref value) = node.value {
2279
2280 if tail_len == 0 && (label == self.joker || label == node.label) {
2281
2282 self.last_j = Some(node);
2283 found = Some(value);
2284
2285 break;
2286 }
2287 }
2288 }
2289
2290 GoMiddle => {
2291
2292 self.todo_j.push((node, Visit, label, key_tail.clone(), tail_len));
2293
2294 if label == self.joker || label == node.label {
2295
2296 if let Some(ref child) = node.middle {
2297
2298 if let Some(new_label) = key_tail.next() {
2299
2300 self.todo_j.push((child, GoRight, new_label, key_tail, tail_len-1));
2301 }
2302 }
2303 }
2304 }
2305
2306 GoLeft => {
2307
2308 if label == self.joker || label < node.label {
2309
2310 if let Some(ref child) = node.left {
2311
2312 self.todo_j.push((child, GoRight, label, key_tail, tail_len));
2313 }
2314 }
2315 }
2316 }
2317 }
2318
2319 found
2320 }
2321}