wl_tools/tree/word_char.rs
1use std::ops::RangeInclusive;
2
3use crate::Words;
4
5/// An iterator over the words of a [`WordCharTreeRootNode`]
6struct Iter<'a, W> {
7 root: &'a WordCharTreeRootNode<'a, W>,
8 curr_edge: usize,
9 curr_node: Option<&'a WordCharTreeNode<'a, W>>,
10 curr_node_visitor: Option<WordCharTreeNodeVisitor<'a, W>>,
11}
12
13impl<'a, W> Iter<'a, W> {
14 fn boxed(root: &'a WordCharTreeRootNode<'a, W>) -> Box<Self> {
15 let (curr_node, curr_node_visitor) = if root.edges.is_empty() {
16 (None, None)
17 } else {
18 (
19 Some(&root.edges[0].child_node),
20 Some(WordCharTreeNodeVisitor::new(&root.edges[0].child_node)),
21 )
22 };
23 Box::new(Self {
24 root,
25 curr_edge: 0,
26 curr_node,
27 curr_node_visitor,
28 })
29 }
30}
31
32impl<'a, W> Iterator for Iter<'a, W> {
33 type Item = &'a W;
34
35 fn next(&mut self) -> Option<Self::Item> {
36 let Some(visitor) = &mut self.curr_node_visitor else { return None };
37 match visitor.next() {
38 None => {
39 // Proceed to next edge unless we've already reached the end of the edges.
40 if self.curr_edge < self.root.edges.len() {
41 self.curr_edge += 1;
42 }
43 // If there are no edges left, we signal end of iteration.
44 if self.curr_edge == self.root.edges.len() {
45 self.curr_node = None;
46 self.curr_node_visitor = None;
47 return None;
48 }
49
50 let curr_node = &self.root.edges[self.curr_edge].child_node;
51 self.curr_node = Some(curr_node);
52 let curr_node_visitor = WordCharTreeNodeVisitor::new(curr_node);
53 self.curr_node_visitor = Some(curr_node_visitor);
54 (self.curr_node_visitor.as_mut().unwrap()).next()
55 }
56 Some(w) => Some(w),
57 }
58 }
59}
60
61struct WordCharTreeNodeVisitor<'a, W> {
62 node: &'a WordCharTreeNode<'a, W>,
63 has_visited_own_node: bool,
64 has_initialized_children: bool,
65 curr_edge: usize,
66 curr_node: Option<&'a WordCharTreeNode<'a, W>>,
67 curr_node_visitor: Option<Box<WordCharTreeNodeVisitor<'a, W>>>,
68}
69
70impl<'a, W> WordCharTreeNodeVisitor<'a, W> {
71 fn new(node: &'a WordCharTreeNode<'a, W>) -> Self {
72 Self {
73 node,
74 has_visited_own_node: false,
75 has_initialized_children: false,
76 curr_edge: 0,
77 curr_node: None,
78 curr_node_visitor: None,
79 }
80 }
81}
82
83impl<'a, W> Iterator for WordCharTreeNodeVisitor<'a, W> {
84 type Item = &'a W;
85
86 fn next(&mut self) -> Option<Self::Item> {
87 // Visit own node before visiting children
88 if !self.has_visited_own_node {
89 self.has_visited_own_node = true;
90 if self.node.word.is_some() {
91 return self.node.word.as_ref();
92 }
93 }
94
95 if !self.has_initialized_children {
96 self.has_initialized_children = true;
97 if self.node.edges.is_empty() {
98 self.curr_node = None;
99 self.curr_node_visitor = None;
100 } else {
101 let curr_node = &self.node.edges[0].child_node;
102 self.curr_node = Some(curr_node);
103 self.curr_node_visitor = Some(Box::new(WordCharTreeNodeVisitor::new(curr_node)));
104 }
105 }
106
107 let Some(visitor) = &mut self.curr_node_visitor else { return None };
108 match visitor.next() {
109 None => {
110 // Proceed to next edge unless we've already reached the end of the edges.
111 if self.curr_edge < self.node.edges.len() {
112 self.curr_edge += 1;
113 }
114 // If there are no edges left, signal to parent that subtree is done.
115 if self.curr_edge == self.node.edges.len() {
116 self.curr_node = None;
117 self.curr_node_visitor = None;
118 return None;
119 }
120
121 let curr_node = &self.node.edges[self.curr_edge].child_node;
122 self.curr_node = Some(curr_node);
123 let curr_node_visitor = WordCharTreeNodeVisitor::new(curr_node);
124 self.curr_node_visitor = Some(Box::new(curr_node_visitor));
125 (self.curr_node_visitor.as_mut().unwrap()).next()
126 }
127 Some(w) => Some(w),
128 }
129 }
130}
131
132/// The root node of a tree, where the edges are [`char`]s and the nodes are `Option<W>` words
133///
134/// Regarding the `Option<W>` words in the tree, see in particular the following:
135/// - [`Self::is_fully_well_formed`]
136/// - [`Self::is_suitable_for_iterative_char_search`]
137/// - [`Self::words`]
138pub struct WordCharTreeRootNode<'a, W> {
139 edges: &'a [WordCharTreeEdge<'a, W>],
140}
141
142impl<W> WordCharTreeRootNode<'_, W> {
143 /// Get the max depth of the tree
144 ///
145 /// Measured in number of lowercase [`char`] edges from the root node
146 /// to the deepest node in the tree.
147 ///
148 /// In a [fully well-formed](`Self::is_fully_well_formed`) word char tree, this depth
149 /// corresponds to the length in `char`s of the longest word in the tree.
150 pub fn get_max_depth(&self) -> usize {
151 self.edges
152 .iter()
153 .map(|edge| edge.get_max_depth(0))
154 .max()
155 .unwrap_or(0)
156 }
157 /// The tree is *fully well-formed* as long as either of the following is true:
158 /// - The tree is empty, or
159 /// - every leaf node (node without child edges) corresponds to a word `W`.
160 ///
161 /// Additional notes:
162 /// - Non-leaf nodes are allowed to have `word: None`.
163 /// - Non-leaf nodes are allowed to have `word: Some(W)`.
164 ///
165 /// The tree is NOT *fully well-formed* if any of the leaf nodes have `word: None`.
166 pub fn is_fully_well_formed(&self) -> bool {
167 self.edges
168 .iter()
169 .map(|edge| edge.is_fully_well_formed())
170 .all(|b| b)
171 }
172 /// The tree is *suitable for iterative char search* for words `W` if the following is true:
173 /// - Every non-leaf node has `word: None`.
174 ///
175 /// Additional notes:
176 /// - Leaf nodes are allowed to have `word: None`.
177 /// - Leaf nodes are allowed to have `word: Some(W)`.
178 ///
179 /// In *iterative char search*, words are fed into the search one [`char`] at a time.
180 /// Because of this, the search will return a match as soon as the shortest match is found.
181 ///
182 /// Example:
183 /// 1. You have a list of words `[..., arm, army, ..., man, ...]`.
184 /// 2. You have the string "army man".
185 /// 3. You start an iterative char search on the string
186 /// to find words from the list in your string.
187 /// 4. The iterative char search will return a match for the word `arm`.
188 /// You wanted to find the word `army`.
189 /// 5. In this case, it was not appropriate to use iterative char search,
190 /// because the wordlist was not suitable for iterative char search.
191 pub fn is_suitable_for_iterative_char_search(&self) -> bool {
192 self.edges
193 .iter()
194 .map(|edge| edge.is_suitable_for_iterative_char_search())
195 .all(|b| b)
196 }
197 /// Returns an iterator over the words `W` of a word char tree
198 pub fn words(&self) -> Words<W> {
199 Words::new(Iter::boxed(self))
200 }
201}
202
203struct WordCharTreeEdge<'a, W> {
204 char_lowercase: char,
205 idx_range: RangeInclusive<usize>,
206 child_node: WordCharTreeNode<'a, W>,
207}
208
209impl<W> WordCharTreeEdge<'_, W> {
210 fn get_max_depth(&self, depth_at_parent_node: usize) -> usize {
211 self.child_node.get_max_depth(depth_at_parent_node)
212 }
213 fn is_fully_well_formed(&self) -> bool {
214 self.child_node.is_fully_well_formed()
215 }
216 fn is_suitable_for_iterative_char_search(&self) -> bool {
217 self.child_node.is_suitable_for_iterative_char_search()
218 }
219}
220
221struct WordCharTreeNode<'a, W> {
222 word: Option<W>,
223 edges: &'a [WordCharTreeEdge<'a, W>],
224}
225
226impl<W> WordCharTreeNode<'_, W> {
227 fn get_max_depth(&self, depth_at_parent_edge: usize) -> usize {
228 let curr_depth = depth_at_parent_edge + 1;
229 self.edges
230 .iter()
231 .map(|edge| edge.get_max_depth(curr_depth))
232 .max()
233 .unwrap_or(curr_depth)
234 }
235 fn is_fully_well_formed(&self) -> bool {
236 self.edges
237 .iter()
238 .map(|edge| edge.is_fully_well_formed())
239 .all(|b| b)
240 }
241 fn is_suitable_for_iterative_char_search(&self) -> bool {
242 if self.edges.is_empty() {
243 true
244 } else if self.word.is_some() {
245 false
246 } else {
247 self.edges
248 .iter()
249 .map(|edge| edge.is_suitable_for_iterative_char_search())
250 .all(|b| b)
251 }
252 }
253}
254
255#[cfg(test)]
256mod test {
257 use super::*;
258 use test_case::test_case;
259
260 #[derive(Debug, PartialEq)]
261 pub enum ExampleWords1 {
262 Get,
263 Give,
264 Go,
265 }
266
267 #[derive(Debug, PartialEq)]
268 pub enum ExampleWords2 {
269 Arm,
270 Army,
271 Man,
272 }
273
274 #[derive(Debug, PartialEq)]
275 pub enum ExampleWords3 {
276 A,
277 }
278
279 #[derive(Debug, PartialEq)]
280 pub enum ExampleWords4 {
281 An,
282 }
283
284 #[derive(Debug, PartialEq)]
285 pub enum ExampleWords5 {
286 Ant,
287 }
288
289 #[derive(Debug, PartialEq)]
290 pub enum ExampleWords6 {
291 A,
292 An,
293 Ant,
294 }
295
296 #[derive(Debug, PartialEq)]
297 pub enum ExampleWords7 {
298 Ant,
299 Art,
300 I,
301 Main,
302 Man,
303 Mane,
304 Mango,
305 Mare,
306 More,
307 XRAM,
308 XRay,
309 Zebra,
310 Zero,
311 Zinc,
312 Zombie,
313 Zoo,
314 }
315
316 /// A well-formed example empty wordlist
317 /// Suitable for iterative char search (although it would be rather pointless in this case :P)
318 pub const EXAMPLE_WORDLIST_EMPTY: WordCharTreeRootNode<()> =
319 WordCharTreeRootNode { edges: &[] };
320
321 /// A well-formed example wordlist
322 /// Suitable for iterative char search
323 pub const EXAMPLE_WORDLIST_1: WordCharTreeRootNode<ExampleWords1> = WordCharTreeRootNode {
324 edges: &[WordCharTreeEdge {
325 char_lowercase: 'g',
326 idx_range: 0..=2,
327 child_node: WordCharTreeNode {
328 word: None,
329 edges: &[
330 WordCharTreeEdge {
331 char_lowercase: 'e',
332 idx_range: 0..=0,
333 child_node: WordCharTreeNode {
334 word: None,
335 edges: &[WordCharTreeEdge {
336 char_lowercase: 't',
337 idx_range: 0..=0,
338 child_node: WordCharTreeNode {
339 word: Some(ExampleWords1::Get),
340 edges: &[],
341 },
342 }],
343 },
344 },
345 WordCharTreeEdge {
346 char_lowercase: 'i',
347 idx_range: 1..=1,
348 child_node: WordCharTreeNode {
349 word: None,
350 edges: &[WordCharTreeEdge {
351 char_lowercase: 'v',
352 idx_range: 1..=1,
353 child_node: WordCharTreeNode {
354 word: None,
355 edges: &[WordCharTreeEdge {
356 char_lowercase: 'e',
357 idx_range: 1..=1,
358 child_node: WordCharTreeNode {
359 word: Some(ExampleWords1::Give),
360 edges: &[],
361 },
362 }],
363 },
364 }],
365 },
366 },
367 WordCharTreeEdge {
368 char_lowercase: 'o',
369 idx_range: 2..=2,
370 child_node: WordCharTreeNode {
371 word: Some(ExampleWords1::Go),
372 edges: &[],
373 },
374 },
375 ],
376 },
377 }],
378 };
379
380 /// A well-formed example wordlist
381 /// Not suitable for iterative char search
382 pub const EXAMPLE_WORDLIST_2: WordCharTreeRootNode<ExampleWords2> = WordCharTreeRootNode {
383 edges: &[
384 WordCharTreeEdge {
385 char_lowercase: 'a',
386 idx_range: 0..=1,
387 child_node: WordCharTreeNode {
388 word: None,
389 edges: &[WordCharTreeEdge {
390 char_lowercase: 'r',
391 idx_range: 0..=1,
392 child_node: WordCharTreeNode {
393 word: None,
394 edges: &[WordCharTreeEdge {
395 char_lowercase: 'm',
396 idx_range: 0..=1,
397 child_node: WordCharTreeNode {
398 word: Some(ExampleWords2::Arm),
399 edges: &[WordCharTreeEdge {
400 char_lowercase: 'y',
401 idx_range: 1..=1,
402 child_node: WordCharTreeNode {
403 word: Some(ExampleWords2::Army),
404 edges: &[],
405 },
406 }],
407 },
408 }],
409 },
410 }],
411 },
412 },
413 WordCharTreeEdge {
414 char_lowercase: 'm',
415 idx_range: 2..=2,
416 child_node: WordCharTreeNode {
417 word: None,
418 edges: &[WordCharTreeEdge {
419 char_lowercase: 'a',
420 idx_range: 2..=2,
421 child_node: WordCharTreeNode {
422 word: None,
423 edges: &[WordCharTreeEdge {
424 char_lowercase: 'n',
425 idx_range: 2..=2,
426 child_node: WordCharTreeNode {
427 word: Some(ExampleWords2::Man),
428 edges: &[],
429 },
430 }],
431 },
432 }],
433 },
434 },
435 ],
436 };
437
438 /// A well-formed example wordlist
439 /// Suitable for iterative char search
440 pub const EXAMPLE_WORDLIST_3: WordCharTreeRootNode<ExampleWords3> = WordCharTreeRootNode {
441 edges: &[WordCharTreeEdge {
442 char_lowercase: 'a',
443 idx_range: 0..=0,
444 child_node: WordCharTreeNode {
445 word: Some(ExampleWords3::A),
446 edges: &[],
447 },
448 }],
449 };
450
451 /// A well-formed example wordlist
452 /// Suitable for iterative char search
453 pub const EXAMPLE_WORDLIST_4: WordCharTreeRootNode<ExampleWords4> = WordCharTreeRootNode {
454 edges: &[WordCharTreeEdge {
455 char_lowercase: 'a',
456 idx_range: 0..=0,
457 child_node: WordCharTreeNode {
458 word: None,
459 edges: &[WordCharTreeEdge {
460 char_lowercase: 'n',
461 idx_range: 0..=0,
462 child_node: WordCharTreeNode {
463 word: Some(ExampleWords4::An),
464 edges: &[],
465 },
466 }],
467 },
468 }],
469 };
470
471 /// A well-formed example wordlist
472 /// Suitable for iterative char search
473 pub const EXAMPLE_WORDLIST_5: WordCharTreeRootNode<ExampleWords5> = WordCharTreeRootNode {
474 edges: &[WordCharTreeEdge {
475 char_lowercase: 'a',
476 idx_range: 0..=0,
477 child_node: WordCharTreeNode {
478 word: None,
479 edges: &[WordCharTreeEdge {
480 char_lowercase: 'n',
481 idx_range: 0..=0,
482 child_node: WordCharTreeNode {
483 word: None,
484 edges: &[WordCharTreeEdge {
485 char_lowercase: 't',
486 idx_range: 0..=0,
487 child_node: WordCharTreeNode {
488 word: Some(ExampleWords5::Ant),
489 edges: &[],
490 },
491 }],
492 },
493 }],
494 },
495 }],
496 };
497
498 /// A well-formed example wordlist
499 /// Not suitable for iterative char search
500 pub const EXAMPLE_WORDLIST_6: WordCharTreeRootNode<ExampleWords6> = WordCharTreeRootNode {
501 edges: &[WordCharTreeEdge {
502 char_lowercase: 'a',
503 idx_range: 0..=2,
504 child_node: WordCharTreeNode {
505 word: Some(ExampleWords6::A),
506 edges: &[WordCharTreeEdge {
507 char_lowercase: 'n',
508 idx_range: 1..=2,
509 child_node: WordCharTreeNode {
510 word: Some(ExampleWords6::An),
511 edges: &[WordCharTreeEdge {
512 char_lowercase: 't',
513 idx_range: 2..=2,
514 child_node: WordCharTreeNode {
515 word: Some(ExampleWords6::Ant),
516 edges: &[],
517 },
518 }],
519 },
520 }],
521 },
522 }],
523 };
524
525 /// A well-formed example wordlist
526 /// Not suitable for iterative char search
527 pub const EXAMPLE_WORDLIST_7: WordCharTreeRootNode<ExampleWords7> = WordCharTreeRootNode {
528 edges: &[
529 WordCharTreeEdge {
530 char_lowercase: 'a',
531 idx_range: 0..=1,
532 child_node: WordCharTreeNode {
533 word: None,
534 edges: &[
535 WordCharTreeEdge {
536 char_lowercase: 'n',
537 idx_range: 0..=0,
538 child_node: WordCharTreeNode {
539 word: None,
540 edges: &[WordCharTreeEdge {
541 char_lowercase: 't',
542 idx_range: 0..=0,
543 child_node: WordCharTreeNode {
544 word: Some(ExampleWords7::Ant),
545 edges: &[],
546 },
547 }],
548 },
549 },
550 WordCharTreeEdge {
551 char_lowercase: 'r',
552 idx_range: 1..=1,
553 child_node: WordCharTreeNode {
554 word: None,
555 edges: &[WordCharTreeEdge {
556 char_lowercase: 't',
557 idx_range: 1..=1,
558 child_node: WordCharTreeNode {
559 word: Some(ExampleWords7::Art),
560 edges: &[],
561 },
562 }],
563 },
564 },
565 ],
566 },
567 },
568 WordCharTreeEdge {
569 char_lowercase: 'i',
570 idx_range: 2..=2,
571 child_node: WordCharTreeNode {
572 word: Some(ExampleWords7::I),
573 edges: &[],
574 },
575 },
576 WordCharTreeEdge {
577 char_lowercase: 'm',
578 idx_range: 3..=8,
579 child_node: WordCharTreeNode {
580 word: None,
581 edges: &[
582 WordCharTreeEdge {
583 char_lowercase: 'a',
584 idx_range: 3..=7,
585 child_node: WordCharTreeNode {
586 word: None,
587 edges: &[
588 WordCharTreeEdge {
589 char_lowercase: 'i',
590 idx_range: 3..=3,
591 child_node: WordCharTreeNode {
592 word: None,
593 edges: &[WordCharTreeEdge {
594 char_lowercase: 'n',
595 idx_range: 3..=3,
596 child_node: WordCharTreeNode {
597 word: Some(ExampleWords7::Main),
598 edges: &[],
599 },
600 }],
601 },
602 },
603 WordCharTreeEdge {
604 char_lowercase: 'n',
605 idx_range: 4..=6,
606 child_node: WordCharTreeNode {
607 word: Some(ExampleWords7::Man),
608 edges: &[
609 WordCharTreeEdge {
610 char_lowercase: 'e',
611 idx_range: 5..=5,
612 child_node: WordCharTreeNode {
613 word: Some(ExampleWords7::Mane),
614 edges: &[],
615 },
616 },
617 WordCharTreeEdge {
618 char_lowercase: 'g',
619 idx_range: 6..=6,
620 child_node: WordCharTreeNode {
621 word: None,
622 edges: &[WordCharTreeEdge {
623 char_lowercase: 'o',
624 idx_range: 6..=6,
625 child_node: WordCharTreeNode {
626 word: Some(ExampleWords7::Mango),
627 edges: &[],
628 },
629 }],
630 },
631 },
632 ],
633 },
634 },
635 WordCharTreeEdge {
636 char_lowercase: 'r',
637 idx_range: 7..=7,
638 child_node: WordCharTreeNode {
639 word: None,
640 edges: &[WordCharTreeEdge {
641 char_lowercase: 'e',
642 idx_range: 7..=7,
643 child_node: WordCharTreeNode {
644 word: Some(ExampleWords7::Mare),
645 edges: &[],
646 },
647 }],
648 },
649 },
650 ],
651 },
652 },
653 WordCharTreeEdge {
654 char_lowercase: 'o',
655 idx_range: 8..=8,
656 child_node: WordCharTreeNode {
657 word: None,
658 edges: &[WordCharTreeEdge {
659 char_lowercase: 'r',
660 idx_range: 8..=8,
661 child_node: WordCharTreeNode {
662 word: None,
663 edges: &[WordCharTreeEdge {
664 char_lowercase: 'e',
665 idx_range: 8..=8,
666 child_node: WordCharTreeNode {
667 word: Some(ExampleWords7::More),
668 edges: &[],
669 },
670 }],
671 },
672 }],
673 },
674 },
675 ],
676 },
677 },
678 WordCharTreeEdge {
679 char_lowercase: 'x',
680 idx_range: 9..=10,
681 child_node: WordCharTreeNode {
682 word: None,
683 edges: &[WordCharTreeEdge {
684 char_lowercase: 'r',
685 idx_range: 9..=10,
686 child_node: WordCharTreeNode {
687 word: None,
688 edges: &[WordCharTreeEdge {
689 char_lowercase: 'a',
690 idx_range: 9..=10,
691 child_node: WordCharTreeNode {
692 word: None,
693 edges: &[
694 WordCharTreeEdge {
695 char_lowercase: 'm',
696 idx_range: 9..=9,
697 child_node: WordCharTreeNode {
698 word: Some(ExampleWords7::XRAM),
699 edges: &[],
700 },
701 },
702 WordCharTreeEdge {
703 char_lowercase: 'y',
704 idx_range: 10..=10,
705 child_node: WordCharTreeNode {
706 word: Some(ExampleWords7::XRay),
707 edges: &[],
708 },
709 },
710 ],
711 },
712 }],
713 },
714 }],
715 },
716 },
717 WordCharTreeEdge {
718 char_lowercase: 'z',
719 idx_range: 11..=15,
720 child_node: WordCharTreeNode {
721 word: None,
722 edges: &[
723 WordCharTreeEdge {
724 char_lowercase: 'e',
725 idx_range: 11..=12,
726 child_node: WordCharTreeNode {
727 word: None,
728 edges: &[
729 WordCharTreeEdge {
730 char_lowercase: 'b',
731 idx_range: 11..=11,
732 child_node: WordCharTreeNode {
733 word: None,
734 edges: &[WordCharTreeEdge {
735 char_lowercase: 'r',
736 idx_range: 11..=11,
737 child_node: WordCharTreeNode {
738 word: None,
739 edges: &[WordCharTreeEdge {
740 char_lowercase: 'a',
741 idx_range: 11..=11,
742 child_node: WordCharTreeNode {
743 word: Some(ExampleWords7::Zebra),
744 edges: &[],
745 },
746 }],
747 },
748 }],
749 },
750 },
751 WordCharTreeEdge {
752 char_lowercase: 'r',
753 idx_range: 12..=12,
754 child_node: WordCharTreeNode {
755 word: None,
756 edges: &[WordCharTreeEdge {
757 char_lowercase: 'o',
758 idx_range: 12..=12,
759 child_node: WordCharTreeNode {
760 word: Some(ExampleWords7::Zero),
761 edges: &[],
762 },
763 }],
764 },
765 },
766 ],
767 },
768 },
769 WordCharTreeEdge {
770 char_lowercase: 'i',
771 idx_range: 13..=13,
772 child_node: WordCharTreeNode {
773 word: None,
774 edges: &[WordCharTreeEdge {
775 char_lowercase: 'n',
776 idx_range: 13..=13,
777 child_node: WordCharTreeNode {
778 word: None,
779 edges: &[WordCharTreeEdge {
780 char_lowercase: 'c',
781 idx_range: 13..=13,
782 child_node: WordCharTreeNode {
783 word: Some(ExampleWords7::Zinc),
784 edges: &[],
785 },
786 }],
787 },
788 }],
789 },
790 },
791 WordCharTreeEdge {
792 char_lowercase: 'o',
793 idx_range: 14..=15,
794 child_node: WordCharTreeNode {
795 word: None,
796 edges: &[
797 WordCharTreeEdge {
798 char_lowercase: 'm',
799 idx_range: 14..=14,
800 child_node: WordCharTreeNode {
801 word: None,
802 edges: &[WordCharTreeEdge {
803 char_lowercase: 'b',
804 idx_range: 14..=14,
805 child_node: WordCharTreeNode {
806 word: None,
807 edges: &[WordCharTreeEdge {
808 char_lowercase: 'i',
809 idx_range: 14..=14,
810 child_node: WordCharTreeNode {
811 word: None,
812 edges: &[WordCharTreeEdge {
813 char_lowercase: 'e',
814 idx_range: 14..=14,
815 child_node: WordCharTreeNode {
816 word: Some(
817 ExampleWords7::Zombie,
818 ),
819 edges: &[],
820 },
821 }],
822 },
823 }],
824 },
825 }],
826 },
827 },
828 WordCharTreeEdge {
829 char_lowercase: 'o',
830 idx_range: 15..=15,
831 child_node: WordCharTreeNode {
832 word: Some(ExampleWords7::Zoo),
833 edges: &[],
834 },
835 },
836 ],
837 },
838 },
839 ],
840 },
841 },
842 ],
843 };
844
845 #[test_case(EXAMPLE_WORDLIST_EMPTY, 0)]
846 #[test_case(EXAMPLE_WORDLIST_1, 4)]
847 #[test_case(EXAMPLE_WORDLIST_2, 4)]
848 #[test_case(EXAMPLE_WORDLIST_3, 1)]
849 #[test_case(EXAMPLE_WORDLIST_4, 2)]
850 #[test_case(EXAMPLE_WORDLIST_5, 3)]
851 #[test_case(EXAMPLE_WORDLIST_6, 3)]
852 #[test_case(EXAMPLE_WORDLIST_7, 6)]
853 fn test_positive_max_depth_value<W>(root: WordCharTreeRootNode<W>, expected_value: usize) {
854 assert_eq!(root.get_max_depth(), expected_value);
855 }
856
857 #[test_case(EXAMPLE_WORDLIST_EMPTY)]
858 #[test_case(EXAMPLE_WORDLIST_1)]
859 #[test_case(EXAMPLE_WORDLIST_2)]
860 #[test_case(EXAMPLE_WORDLIST_3)]
861 #[test_case(EXAMPLE_WORDLIST_4)]
862 #[test_case(EXAMPLE_WORDLIST_5)]
863 #[test_case(EXAMPLE_WORDLIST_6)]
864 #[test_case(EXAMPLE_WORDLIST_7)]
865 fn test_positive_fully_well_formed<W>(root: WordCharTreeRootNode<W>) {
866 assert!(root.is_fully_well_formed());
867 }
868
869 #[test_case(EXAMPLE_WORDLIST_EMPTY)]
870 #[test_case(EXAMPLE_WORDLIST_1)]
871 #[test_case(EXAMPLE_WORDLIST_3)]
872 #[test_case(EXAMPLE_WORDLIST_4)]
873 #[test_case(EXAMPLE_WORDLIST_5)]
874 fn test_positive_suitable_iterative_char_search<W>(root: WordCharTreeRootNode<W>) {
875 assert!(root.is_suitable_for_iterative_char_search());
876 }
877
878 #[test_case(EXAMPLE_WORDLIST_2)]
879 #[test_case(EXAMPLE_WORDLIST_6)]
880 #[test_case(EXAMPLE_WORDLIST_7)]
881 fn test_negative_suitable_iterative_char_search<W>(root: WordCharTreeRootNode<W>) {
882 assert!(!root.is_suitable_for_iterative_char_search());
883 }
884
885 #[test_case(EXAMPLE_WORDLIST_EMPTY, vec![])]
886 #[test_case(EXAMPLE_WORDLIST_1, vec![&ExampleWords1::Get, &ExampleWords1::Give, &ExampleWords1::Go])]
887 #[test_case(EXAMPLE_WORDLIST_2, vec![&ExampleWords2::Arm, &ExampleWords2::Army, &ExampleWords2::Man])]
888 #[test_case(EXAMPLE_WORDLIST_3, vec![&ExampleWords3::A])]
889 #[test_case(EXAMPLE_WORDLIST_4, vec![&ExampleWords4::An])]
890 #[test_case(EXAMPLE_WORDLIST_5, vec![&ExampleWords5::Ant])]
891 #[test_case(EXAMPLE_WORDLIST_6, vec![&ExampleWords6::A, &ExampleWords6::An, &ExampleWords6::Ant])]
892 #[test_case(EXAMPLE_WORDLIST_7, vec![
893 /* ○ (Root node) */
894 /* ┣╸a╺○╸n╺○╸t╺● */ &ExampleWords7::Ant,
895 /* ┃ ┗╸r╺○╸t╺● */ &ExampleWords7::Art,
896 /* ┣╸i╺● */ &ExampleWords7::I,
897 /* ┣╸m╺○╸a╺○╸i╺○╸n╺● */ &ExampleWords7::Main,
898 /* ┃ ┃ ┣╸n╺● */ &ExampleWords7::Man,
899 /* ┃ ┃ ┃ ┣╸e╺● */ &ExampleWords7::Mane,
900 /* ┃ ┃ ┃ ┗╸g╺○╸o╺● */ &ExampleWords7::Mango,
901 /* ┃ ┃ ┗╸r╺○╸e╺● */ &ExampleWords7::Mare,
902 /* ┃ ┗╸o╺○╸r╺○╸e╺● */ &ExampleWords7::More,
903 /* ┣╸x╺○╸r╺○╸a╺○╸m╺● */ &ExampleWords7::XRAM,
904 /* ┃ ┗╸y╺● */ &ExampleWords7::XRay,
905 /* ┗╸z╺○╸e╺○╸b╺○╸r╺○╸a╺● */ &ExampleWords7::Zebra,
906 /* ┃ ┗╸r╺○╸o╺● */ &ExampleWords7::Zero,
907 /* ┣╸i╺○╸n╺○╸c╺● */ &ExampleWords7::Zinc,
908 /* ┗╸o╺○╸m╺○╸b╺○╸i╺○╸e╺● */ &ExampleWords7::Zombie,
909 /* ┗╸o╺● */ &ExampleWords7::Zoo,
910 ])]
911 fn test_positive_words<W>(root: WordCharTreeRootNode<W>, expected_words: Vec<&W>)
912 where
913 W: std::fmt::Debug + std::cmp::PartialEq,
914 {
915 assert_eq!(root.words().collect::<Vec<_>>(), expected_words);
916 }
917}