1use std::vec::Vec;
6
7use uc::UC;
8mod uc {
9 use std::{cell::UnsafeCell, ops::Deref};
10
11 pub struct UC<T>(UnsafeCell<T>);
12
13 impl<T> UC<T> {
14 pub fn get_ref(&self) -> &T {
15 let t = self.0.get();
16 unsafe { t.as_mut().unwrap_unchecked() }
17 }
18
19 pub fn get_mut(&self) -> &mut T {
20 let t = self.0.get();
21 unsafe { t.as_mut().unwrap_unchecked() }
22 }
23
24 pub const fn new(t: T) -> Self {
25 Self(UnsafeCell::new(t))
26 }
27 }
28
29 impl<T> Deref for UC<T> {
30 type Target = T;
31
32 fn deref(&self) -> &T {
33 self.get_ref()
34 }
35 }
36
37 #[cfg(test)]
38 mod tests_of_units {
39 use std::ops::Deref;
40
41 use super::UC;
42
43 #[test]
44 fn get_ref() {
45 let zero = &0usize as *const usize;
46 let uc = UC::new(zero);
47 let test = uc.get_ref();
48
49 assert_eq!(zero as usize, *test as usize);
50 }
51
52 #[test]
53 fn get_mut() {
54 let zero = &0usize as *const usize;
55 let uc = UC::new(zero);
56 let test = uc.get_mut();
57
58 assert_eq!(zero as usize, *test as usize);
59 }
60
61 #[test]
62 fn new() {
63 let uc = UC::new(333);
64 let mut test = uc.0;
65 assert_eq!(333, *test.get_mut());
66 }
67
68 #[test]
69 fn deref() {
70 let uc = UC::new(11);
71 assert_eq!(uc.get_ref(), uc.deref());
72 }
73 }
74}
75
76#[cfg_attr(test, derive(PartialEq))]
78struct Letter {
79 #[cfg(test)]
80 val: char,
81 ab: Option<Alphabet>,
82 ct: Option<usize>,
83}
84
85impl Letter {
86 const fn new() -> Self {
87 Letter {
88 #[cfg(test)]
89 val: '💚',
90 ab: None,
91 ct: None,
92 }
93 }
94
95 const fn ab(&self) -> bool {
96 self.ab.is_some()
97 }
98
99 const fn ct(&self) -> bool {
100 self.ct.is_some()
101 }
102
103 const fn to_mut_ptr(&self) -> *mut Self {
104 (self as *const Self).cast_mut()
105 }
106}
107
108type Alphabet = Box<[Letter]>;
110pub type Ix = fn(char) -> usize;
115
116pub type Re = fn(usize) -> char;
120
121fn ab(len: usize) -> Alphabet {
123 let mut ab = Vec::new();
124 ab.reserve_exact(len);
125
126 #[cfg(test)]
127 #[cfg(feature = "test-ext")]
128 let mut c = 'A' as u8;
129
130 let sc = ab.spare_capacity_mut();
131 for ix in 0..len {
132 let mut _letter = sc[ix].write(Letter::new());
133
134 #[cfg(test)]
135 #[cfg(feature = "test-ext")]
136 {
137 _letter.val = c as char;
138
139 const Z: u8 = 'Z' as u8;
140 c = if c == Z { 'a' as u8 } else { c + 1 }
141 }
142 }
143
144 unsafe { ab.set_len(len) };
145
146 ab.into_boxed_slice()
147}
148
149pub mod english_letters {
153
154 pub const BASE_ALPHABET_LEN: usize = 26;
156 pub const ALPHABET_LEN: usize = BASE_ALPHABET_LEN * 2;
158
159 const A: usize = 'A' as usize;
160 #[allow(non_upper_case_globals)]
161 const a: usize = 'a' as usize;
162
163 pub fn ix(c: char) -> usize {
165 let code_point = c as usize;
166
167 match code_point {
168 | c if c > 64 && c < 91 => c - A,
169 | c if c > 96 && c < 123 => c - a + BASE_ALPHABET_LEN,
170 | _ => {
171 panic!("Index conversion failed because code point `{code_point}` is unsupported.")
172 },
173 }
174 }
175
176 pub fn re(i: usize) -> char {
178 let code_point = match i {
179 | i if i < 26 => i + A,
180 | i if i > 25 && i < 52 => i + a - BASE_ALPHABET_LEN,
181 | _ => {
182 panic!("Char conversion failed because index `{i}` conversion is not supported.")
183 },
184 };
185
186 code_point as u8 as char
187 }
188}
189
190#[derive(Debug)]
192#[derive(PartialEq, Eq)]
193pub enum AddRes {
194 Ok(Option<usize>),
196 ZeroLen,
198}
199
200impl AddRes {
201 pub const fn is_ok(&self) -> bool {
203 match self {
204 | AddRes::Ok(_) => true,
205 | _ => false,
206 }
207 }
208
209 pub const fn is_ok_some(&self) -> bool {
211 if let AddRes::Ok(opt) = self {
212 if let Some(_) = opt {
213 return true;
214 }
215 }
216
217 false
218 }
219
220 pub const fn uproot_ok_some(&self) -> usize {
224 if let AddRes::Ok(opt) = self {
225 if let Some(n) = opt {
226 return *n;
227 }
228 }
229
230 panic!("Not AddRes::Ok(Some(_)) variant.")
231 }
232
233 pub const unsafe fn uproot_ok_some_unchecked(&self) -> usize {
239 if let AddRes::Ok(opt) = self {
240 if let Some(n) = opt {
241 return *n;
242 }
243 }
244 unsafe { std::hint::unreachable_unchecked() }
246 }
247}
248
249#[derive(Debug)]
253#[derive(PartialEq, Eq)]
254pub enum VerRes {
255 Ok(usize),
257 ZeroLen,
259 Unknown,
261}
262
263impl VerRes {
264 pub const fn is_ok(&self) -> bool {
266 match self {
267 | VerRes::Ok(_) => true,
268 | _ => false,
269 }
270 }
271
272 pub const fn uproot(&self) -> usize {
274 match self {
275 | VerRes::Ok(res) => *res,
276 | _ => panic!("Value is not `Ok(usize)` variant."),
277 }
278 }
279
280 pub const unsafe fn uproot_unchecked(&self) -> usize {
284 match self {
285 | VerRes::Ok(res) => *res,
286 | _ => unsafe { std::hint::unreachable_unchecked() },
288 }
289 }
290}
291
292#[cfg_attr(test, derive(PartialEq, Debug))]
293enum TraRes<'a> {
294 Ok(&'a Letter),
295 OkMut(&'a mut Letter),
296 ZeroLen,
297 UnknownForNotEntry,
298 UnknownForAbsentPath,
299}
300
301impl<'a> TraRes<'a> {
302 fn ver_res(&self) -> VerRes {
303 let p = || panic!("Unsupported");
304
305 return match self {
306 | TraRes::ZeroLen => VerRes::ZeroLen,
307 | TraRes::UnknownForNotEntry | TraRes::UnknownForAbsentPath => VerRes::Unknown,
308 | TraRes::Ok(_) => p(),
309 | TraRes::OkMut(_) => p(),
310 };
311 }
312}
313
314fn ext(ab: &Alphabet, buff: &mut String, re: Re, o: &mut Vec<(String, usize)>) {
319 for ix in 0..ab.len() {
320 buff.push(re(ix));
321
322 let letter = &ab[ix];
323
324 if let Some(ct) = letter.ct {
325 let key = buff.clone();
326 o.push((key, ct));
327 }
328
329 if let Some(ab) = letter.ab.as_ref() {
330 ext(ab, buff, re, o);
331 }
332
333 _ = buff.pop();
334 }
335}
336
337pub struct Toc {
363 rt: Alphabet,
365 ix: Ix,
367 re: Option<Re>,
369 al: usize,
371 tr: UC<Vec<*mut Letter>>,
373 ct: usize,
375}
376
377impl Toc {
378 pub fn new() -> Self {
381 Self::new_with(
382 english_letters::ix,
383 Some(english_letters::re),
384 english_letters::ALPHABET_LEN,
385 )
386 }
387
388 pub fn new_with(ix: Ix, re: Option<Re>, ab_len: usize) -> Self {
423 Self {
424 rt: ab(ab_len),
425 ix,
426 re,
427 al: ab_len,
428 tr: UC::new(Vec::new()),
429 ct: 0,
430 }
431 }
432
433 pub fn put_trace_cap(&mut self, approx_cap: usize) -> usize {
462 let tr = &mut self.tr;
463 let cp = tr.capacity();
464
465 if cp < approx_cap {
466 tr.get_mut().reserve(approx_cap);
467 } else if cp > approx_cap {
468 *tr = UC::new(Vec::with_capacity(approx_cap));
469 }
470
471 tr.capacity()
472 }
473
474 pub fn acq_trace_cap(&self) -> usize {
478 self.tr.capacity()
479 }
480
481 pub fn add(&mut self, mut occurrent: impl Iterator<Item = char>, val: Option<usize>) -> AddRes {
491 let c = occurrent.next();
492
493 if c.is_none() {
494 return AddRes::ZeroLen;
495 }
496
497 let c = unsafe { c.unwrap_unchecked() };
498
499 let ix = self.ix;
500 let al = self.al;
501
502 let mut letter = &mut self.rt[ix(c)];
503
504 while let Some(c) = occurrent.next() {
505 let alphabet = letter.ab.get_or_insert_with(|| ab(al));
506 letter = &mut alphabet[ix(c)];
507 }
508
509 let ct = letter.ct;
510
511 let ct_none = ct.is_none();
512 if ct_none {
513 self.ct += 1;
514 }
515
516 letter.ct = Some(if let Some(v) = val {
517 v
518 } else {
519 if ct_none {
520 1
521 } else {
522 unsafe { ct.unwrap_unchecked() }.wrapping_add(1)
523 }
524 });
525
526 AddRes::Ok(ct)
527 }
528
529 pub fn acq(&self, occurrent: impl Iterator<Item = char>) -> VerRes {
533 let track_res = self.track(occurrent, false, false);
534 if let TraRes::Ok(l) = track_res {
535 let ct = l.ct;
536 let ct = unsafe { ct.unwrap_unchecked() };
537 VerRes::Ok(ct)
538 } else {
539 track_res.ver_res()
540 }
541 }
542
543 pub fn put(&mut self, occurrent: impl Iterator<Item = char>, val: usize) -> VerRes {
547 let track_res = self.track(occurrent, false, true);
548
549 if let TraRes::OkMut(l) = track_res {
550 let old = l.ct.replace(val);
551 let old = unsafe { old.unwrap_unchecked() };
552 VerRes::Ok(old)
553 } else {
554 track_res.ver_res()
555 }
556 }
557
558 pub fn rem(&mut self, occurrent: impl Iterator<Item = char>) -> VerRes {
568 let track_res = self.track(occurrent, true, false);
569 let res = if let TraRes::Ok(_) = track_res {
570 let ct = Self::rem_actual(self);
571 self.ct -= 1;
572 VerRes::Ok(ct)
573 } else {
574 track_res.ver_res()
575 };
576
577 self.tr.get_mut().clear();
578 res
579 }
580
581 fn rem_actual(&mut self) -> usize {
582 let mut trace = self.tr.iter().map(|x| unsafe { x.as_mut() }.unwrap());
583 let entry = unsafe { trace.next_back().unwrap_unchecked() };
584
585 let ct = entry.ct.take();
586
587 if !entry.ab() {
588 while let Some(l) = trace.next_back() {
589 let alphabet = l.ab.as_ref().unwrap();
590 let mut remove_alphab = true;
591
592 for ix in 0..self.al {
593 let letter = &alphabet[ix];
594
595 if letter.ab() || letter.ct() {
596 remove_alphab = false;
597 break;
598 }
599 }
600
601 if remove_alphab {
602 l.ab = None;
603 } else {
604 break;
605 }
606
607 if l.ct() {
608 break;
609 }
610 }
611 }
612
613 unsafe { ct.unwrap_unchecked() }
614 }
615
616 fn track(
620 &self,
621 mut occurrent: impl Iterator<Item = char>,
622 tracing: bool,
623 okmut: bool,
624 ) -> TraRes {
625 let c = occurrent.next();
626
627 if c.is_none() {
628 return TraRes::ZeroLen;
629 }
630
631 let c = unsafe { c.unwrap_unchecked() };
632
633 let ix = &self.ix;
634 let tr = self.tr.get_mut();
635
636 let mut letter = &self.rt[ix(c)];
637
638 loop {
639 if tracing {
640 tr.push(letter.to_mut_ptr())
641 }
642
643 if let Some(c) = occurrent.next() {
644 if let Some(ab) = letter.ab.as_ref() {
645 letter = &ab[ix(c)];
646 } else {
647 return TraRes::UnknownForAbsentPath;
648 }
649 } else {
650 break;
651 }
652 }
653
654 if letter.ct() {
655 if okmut {
656 let l_mut = unsafe { letter.to_mut_ptr().as_mut().unwrap_unchecked() };
657 TraRes::OkMut(l_mut)
658 } else {
659 TraRes::Ok(letter)
660 }
661 } else {
662 TraRes::UnknownForNotEntry
663 }
664 }
665
666 pub fn ext(&self) -> Option<Vec<(String, usize)>> {
678 if let Some(re) = self.re {
679 if self.ct == 0 {
680 return None;
681 }
682
683 let mut buff = String::with_capacity(1000);
685
686 let mut res = Vec::with_capacity(1000);
688
689 ext(&self.rt, &mut buff, re, &mut res);
690 Some(res)
691 } else {
692 panic!("This method is unsupported when `new_with` `re` parameter is provided with `None`.");
693 }
694 }
695
696 pub fn clr(&mut self) -> usize {
702 self.rt = ab(self.al);
703 let ct = self.ct;
704 self.ct = 0;
705 ct
706 }
707
708 pub const fn ct(&self) -> usize {
710 self.ct
711 }
712}
713
714#[cfg(test)]
715mod tests_of_units {
716
717 use crate::Letter;
718 use std::fmt::{Debug, Formatter};
719
720 impl Debug for Letter {
721 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
722 let ab = some_none(self.ab.as_ref());
723
724 return f.write_fmt(format_args!(
725 "Letter {{\n val: {}\n ab: {}\n ct: {:?}\n}}",
726 self.val, ab, self.ct
727 ));
728
729 fn some_none<T>(val: Option<&T>) -> &'static str {
730 if val.is_some() {
731 "Some"
732 } else {
733 "None"
734 }
735 }
736 }
737 }
738
739 mod letter {
740
741 use crate::{Letter, ab as ab_fn};
742
743 #[test]
744 fn new() {
745 let letter = Letter::new();
746
747 assert_eq!('💚', letter.val);
748 assert!(letter.ab.is_none());
749 assert!(letter.ct.is_none());
750 }
751
752 #[test]
753 fn ab() {
754 let mut letter = Letter::new();
755 assert_eq!(false, letter.ab());
756
757 letter.ab = Some(ab_fn(0));
758 assert_eq!(true, letter.ab());
759 }
760
761 #[test]
762 fn ct() {
763 let mut letter = Letter::new();
764 assert_eq!(false, letter.ct());
765
766 letter.ct = Some(0);
767 assert_eq!(true, letter.ct());
768 }
769 }
770
771 mod ab {
772
773 use crate::english_letters::ALPHABET_LEN;
774 use crate::ab as ab_fn;
775
776 #[test]
777 fn ab() {
778 let ab = ab_fn(ALPHABET_LEN);
779 assert_eq!(ALPHABET_LEN, ab.len());
780
781 #[cfg(feature = "test-ext")]
782 {
783 let chain = ('A'..='Z').chain('a'..='z');
784
785 for (ix, c) in chain.enumerate() {
786 let letter = &ab[ix];
787
788 assert_eq!(c, letter.val);
789 assert!(letter.ab.is_none());
790 assert!(letter.ct.is_none());
791 }
792 }
793 }
794
795 #[test]
796 fn zero_len() {
797 let ab = ab_fn(0);
798 assert_eq!(0, ab.len());
799 }
800 }
801
802 mod english_letters {
803
804 use crate::english_letters::{ALPHABET_LEN, BASE_ALPHABET_LEN};
805
806 #[test]
807 fn consts() {
808 assert_eq!(26, BASE_ALPHABET_LEN);
809 assert_eq!(52, ALPHABET_LEN);
810 }
811
812 mod ix {
813 use crate::english_letters::ix;
814 use std::panic::catch_unwind;
815
816 #[test]
817 fn ixes() {
818 assert_eq!(0, ix('A'));
819 assert_eq!(25, ix('Z'));
820 assert_eq!(26, ix('a'));
821 assert_eq!(51, ix('z'));
822 }
823
824 #[test]
825 fn unsupported_char() {
826 let ucs = unsupported_chars();
827
828 for (c, cp) in ucs.map(|x| (x as char, x)) {
829 let result = catch_unwind(|| ix(c));
830 assert!(result.is_err());
831
832 let err = unsafe { result.unwrap_err_unchecked() };
833 let downcast = err.downcast_ref::<String>().unwrap();
834 let proof = format!(
835 "Index conversion failed because code point `{cp}` is unsupported."
836 );
837 assert_eq!(&proof, downcast);
838 }
839 }
840
841 fn unsupported_chars() -> [u8; 4] {
842 #[rustfmt::skip] let ucs =
843 [
844 'A' as u8 -1, 'Z' as u8 +1, 'a' as u8 -1, 'z' as u8 +1, ];
847 ucs
848 }
849 }
850
851 mod re {
852 use crate::english_letters::re;
853
854 #[test]
855 fn ixes() {
856 assert_eq!('A', re(0));
857 assert_eq!('Z', re(25));
858 assert_eq!('a', re(26));
859 assert_eq!('z', re(51));
860 }
861
862 #[test]
863 #[should_panic(
864 expected = "Char conversion failed because index `52` conversion is not supported."
865 )]
866 fn unsupported_ix() {
867 _ = re(52)
868 }
869 }
870 }
871
872 mod add_res {
873 use crate::AddRes;
874
875 #[test]
876 fn is_ok() {
877 assert_eq!(true, AddRes::Ok(None).is_ok());
878 assert_eq!(false, AddRes::ZeroLen.is_ok());
879 }
880
881 #[test]
882 fn is_ok_some_some() {
883 assert_eq!(true, AddRes::Ok(Some(3)).is_ok_some());
884 }
885
886 #[test]
887 fn is_ok_some_none() {
888 assert_eq!(false, AddRes::Ok(None).is_ok_some());
889 }
890
891 #[test]
892 fn is_ok_some_not_ok() {
893 assert_eq!(false, AddRes::ZeroLen.is_ok_some());
894 }
895
896 #[test]
897 fn uproot_ok_some_some() {
898 let val = 3;
899 assert_eq!(val, AddRes::Ok(Some(val)).uproot_ok_some());
900 }
901
902 #[test]
903 #[should_panic(expected = "Not AddRes::Ok(Some(_)) variant.")]
904 fn uproot_ok_some_none() {
905 _ = AddRes::Ok(None).uproot_ok_some()
906 }
907
908 #[test]
909 #[should_panic(expected = "Not AddRes::Ok(Some(_)) variant.")]
910 fn uproot_ok_some_not_ok() {
911 _ = AddRes::ZeroLen.uproot_ok_some()
912 }
913
914 #[test]
915 fn uproot_ok_some_unchecked() {
916 let val = 3;
917 let uproot = unsafe { AddRes::Ok(Some(val)).uproot_ok_some_unchecked() };
918 assert_eq!(val, uproot);
919 }
920 }
921
922 mod ver_res {
923 use crate::VerRes;
924
925 #[test]
926 fn is_ok() {
927 assert_eq!(true, VerRes::Ok(0).is_ok());
928 assert_eq!(false, VerRes::Unknown.is_ok());
929 assert_eq!(false, VerRes::ZeroLen.is_ok());
930 }
931
932 #[test]
933 fn uproot() {
934 assert_eq!(33, VerRes::Ok(33).uproot());
935 }
936
937 #[test]
938 #[should_panic(expected = "Value is not `Ok(usize)` variant.")]
939 fn uproot_panic() {
940 VerRes::ZeroLen.uproot();
941 }
942
943 #[test]
944 fn uproot_unchecked() {
945 const VAL: usize = 77;
946 let test = unsafe { VerRes::Ok(VAL).uproot_unchecked() };
947 assert_eq!(VAL, test);
948 }
949 }
950
951 mod ext {
952
953 type Nest = (char, usize);
954
955 use crate::{ab as ab_ctor, ext, Alphabet};
956 use crate::english_letters::{ALPHABET_LEN, ix, re};
957
958 fn ab_fn() -> Alphabet {
959 ab_ctor(ALPHABET_LEN)
960 }
961
962 #[test]
963 fn basic_test() {
964 let mut ab = ab_fn();
965
966 ab[ix('A')].ct = Some(1);
967 ab[ix('z')].ct = Some(2);
968
969 let mut buff = String::new();
970 let mut test = Vec::new();
971
972 ext(&ab, &mut buff, re, &mut test);
973
974 let proof = vec![(String::from("A"), 1), (String::from("z"), 2)];
975 assert_eq!(proof, test);
976 }
977
978 #[test]
979 fn nesting() {
980 let mut root = ab_fn();
981
982 let nesting = [
983 (('A', 3), ('z', 5)),
984 (('B', 5), ('y', 8)),
985 (('y', 10), ('B', 12)),
986 (('z', 99), ('A', 103)),
987 ];
988
989 for n in nesting {
990 prep(&mut root, n);
991 }
992
993 let mut buff = String::new();
994 let mut test = Vec::new();
995
996 ext(&root, &mut buff, re, &mut test);
997
998 let proof = vec![
999 (String::from("A"), 3),
1000 (String::from("Az"), 5),
1001 (String::from("B"), 5),
1002 (String::from("By"), 8),
1003 (String::from("y"), 10),
1004 (String::from("yB"), 12),
1005 (String::from("z"), 99),
1006 (String::from("zA"), 103),
1007 ];
1008
1009 assert_eq!(proof, test);
1010
1011 fn prep(ab: &mut Alphabet, n: (Nest, Nest)) {
1012 let ultra = n.0;
1013 let infra = n.1;
1014
1015 let u_l = &mut ab[ix(ultra.0)];
1016 let mut ul_ab = ab_fn();
1017
1018 let i_l = &mut ul_ab[ix(infra.0)];
1019 i_l.ct = Some(infra.1);
1020
1021 u_l.ab = Some(ul_ab);
1022 u_l.ct = Some(ultra.1);
1023 }
1024 }
1025
1026 #[test]
1027 fn in_depth_recursion() {
1028 let mut root = ab_fn();
1029
1030 let paths = [
1031 ("AA", 13),
1032 ("AzBq", 11),
1033 ("By", 329),
1034 ("ZaZazAzAzAbYyb", 55),
1035 ("yBC", 7),
1036 ("ybXr", 53),
1037 ("ybXrQUTmop", 33),
1038 ("ybXrQUTmopFVB", 99),
1039 ("ybXrQUTmopRFG", 80),
1040 ("zAzAZaZaZaByYB", 44),
1041 ];
1042
1043 for p in paths {
1044 let mut chars = p.0.chars();
1045 let mut le = &mut root[ix(chars.next().unwrap())];
1046
1047 while let Some(c) = chars.next() {
1048 let ab = le.ab.get_or_insert_with(|| ab_fn());
1049 le = &mut ab[ix(c)];
1050 }
1051
1052 le.ct = Some(p.1)
1053 }
1054
1055 let mut buff = String::new();
1056 let mut test = Vec::new();
1057
1058 ext(&root, &mut buff, re, &mut test);
1059
1060 let proof = vec![
1061 (String::from("AA"), 13),
1062 (String::from("AzBq"), 11),
1063 (String::from("By"), 329),
1064 (String::from("ZaZazAzAzAbYyb"), 55),
1065 (String::from("yBC"), 7),
1066 (String::from("ybXr"), 53),
1067 (String::from("ybXrQUTmop"), 33),
1068 (String::from("ybXrQUTmopFVB"), 99),
1069 (String::from("ybXrQUTmopRFG"), 80),
1070 (String::from("zAzAZaZaZaByYB"), 44),
1071 ];
1072
1073 assert_eq!(proof, test);
1074 }
1075 }
1076
1077 mod track_res {
1078 use crate::{TraRes, Letter, VerRes};
1079
1080 #[test]
1081 fn ver_res_convertible() {
1082 assert_eq!(VerRes::ZeroLen, TraRes::ZeroLen.ver_res());
1083 assert_eq!(VerRes::Unknown, TraRes::UnknownForAbsentPath.ver_res());
1084 assert_eq!(VerRes::Unknown, TraRes::UnknownForNotEntry.ver_res());
1085 }
1086
1087 use std::{ops::Deref, panic::catch_unwind};
1088 #[test]
1089 fn ver_res_nonconvertible() {
1090 let err = catch_unwind(|| TraRes::Ok(&Letter::new()).ver_res());
1091
1092 assert_eq!(true, err.is_err());
1093 assert_eq!(
1094 &"Unsupported",
1095 err.unwrap_err().downcast::<&str>().unwrap().deref()
1096 );
1097
1098 let err = catch_unwind(|| TraRes::OkMut(&mut Letter::new()).ver_res());
1099
1100 assert_eq!(true, err.is_err());
1101 assert_eq!(
1102 &"Unsupported",
1103 err.unwrap_err().downcast::<&str>().unwrap().deref()
1104 );
1105 }
1106 }
1107
1108 mod toc {
1109 use crate::{Toc, ab};
1110 use crate::english_letters::{ix, re, ALPHABET_LEN};
1111
1112 #[test]
1113 fn new() {
1114 let toc = Toc::new();
1115 assert_eq!(ALPHABET_LEN, toc.al);
1116 assert_eq!(ix as usize, toc.ix as usize);
1117 assert_eq!(re as usize, toc.re.unwrap() as usize);
1118 }
1119
1120 #[test]
1121 fn new_with() {
1122 fn test_ix(_c: char) -> usize {
1123 0
1124 }
1125
1126 fn test_re(_i: usize) -> char {
1127 '\0'
1128 }
1129
1130 let ab_len = 10;
1131 let toc = Toc::new_with(test_ix, Some(test_re), ab_len);
1132
1133 assert_eq!(ab(ab_len), toc.rt);
1134 assert_eq!(ab_len, toc.al);
1135 assert_eq!(test_ix as usize, toc.ix as usize);
1136 assert_eq!(test_re as usize, toc.re.unwrap() as usize);
1137 assert_eq!(0, toc.tr.capacity());
1138 assert_eq!(0, toc.ct);
1139 }
1140
1141 mod put_trace_cap {
1142 use crate::{Toc, uc::UC};
1143
1144 #[test]
1145 fn extend() {
1146 const NEW_CAP: usize = 10;
1147
1148 let mut toc = Toc::new();
1149 assert!(toc.tr.capacity() < NEW_CAP);
1150
1151 let size = toc.put_trace_cap(NEW_CAP);
1152 assert!(size >= NEW_CAP);
1153 assert!(toc.tr.capacity() >= NEW_CAP);
1154 }
1155
1156 #[test]
1157 fn shrink() {
1158 const NEW_CAP: usize = 10;
1159 const OLD_CAP: usize = 50;
1160
1161 let mut toc = Toc::new();
1162 toc.tr = UC::new(Vec::with_capacity(OLD_CAP));
1163
1164 let size = toc.put_trace_cap(NEW_CAP);
1165 assert!(size >= NEW_CAP && size < OLD_CAP);
1166 let cap = toc.tr.capacity();
1167 assert!(cap >= NEW_CAP && cap < OLD_CAP);
1168 }
1169
1170 #[test]
1171 fn same() {
1172 let mut toc = Toc::new();
1173 let cap = toc.tr.capacity();
1174
1175 let size = toc.put_trace_cap(cap);
1176 assert_eq!(cap, size);
1177 assert_eq!(cap, toc.tr.capacity());
1178 }
1179 }
1180
1181 #[test]
1182 fn acq_trace_cap() {
1183 const VAL: usize = 10;
1184
1185 let mut toc = Toc::new();
1186 let tr = &mut toc.tr;
1187
1188 assert!(tr.capacity() < VAL);
1189 tr.get_mut().reserve_exact(VAL);
1190 assert_eq!(VAL, toc.acq_trace_cap());
1191 }
1192
1193 mod add {
1194 use crate::{Toc, AddRes};
1195 use crate::english_letters::ix;
1196
1197 #[test]
1198 fn basic_test() {
1199 let entry = || "impreciseness".chars();
1200
1201 let mut toc = Toc::new();
1202 assert_eq!(AddRes::Ok(None), toc.add(entry(), None));
1203 assert_eq!(1, toc.ct);
1204
1205 let chars: Vec<char> = entry().collect();
1206 let len = chars.len();
1207 let last_ix = len - 1;
1208
1209 let mut sup_ab = &toc.rt;
1210 for c_ix in 0..len {
1211 let c = chars[c_ix];
1212 let l = &sup_ab[ix(c)];
1213
1214 let terminal_it = c_ix == last_ix;
1215
1216 let sub_ab = l.ab.as_ref();
1217 assert_eq!(terminal_it, sub_ab.is_none(), "{c_ix}, {c}, {terminal_it}",);
1218
1219 if terminal_it {
1220 let ct = l.ct.as_ref();
1221 assert!(ct.is_some());
1222 let ct = unsafe { ct.unwrap_unchecked() };
1223 assert_eq!(&1, ct);
1224 } else {
1225 sup_ab = unsafe { sub_ab.unwrap_unchecked() };
1226 }
1227 }
1228 }
1229
1230 #[test]
1231 fn zero_occurrent() {
1232 let mut toc = Toc::new();
1233 assert_eq!(AddRes::ZeroLen, toc.add("".chars(), None));
1234 assert_eq!(0, toc.ct);
1235 }
1236
1237 #[test]
1238 fn singular_occurrent() {
1239 let mut toc = Toc::new();
1240 assert_eq!(AddRes::Ok(None), toc.add("a".chars(), None));
1241 assert_eq!(Some(1), toc.rt[ix('a')].ct);
1242 assert_eq!(1, toc.ct);
1243 }
1244
1245 #[test]
1246 fn double_add() {
1247 let entry = || "impreciseness".chars();
1248
1249 let mut toc = Toc::new();
1250 assert_eq!(AddRes::Ok(None), toc.add(entry(), None));
1251 assert_eq!(1, toc.ct);
1252
1253 assert_eq!(AddRes::Ok(Some(1)), toc.add(entry(), None));
1254 assert_eq!(1, toc.ct);
1255
1256 let chars: Vec<char> = entry().collect();
1257 let len = chars.len();
1258 let last_ix = len - 1;
1259
1260 let mut sup_ab = &toc.rt;
1261 for c_ix in 0..len {
1262 let c = chars[c_ix];
1263 let l = &sup_ab[ix(c)];
1264
1265 let terminal_it = c_ix == last_ix;
1266
1267 let sub_ab = l.ab.as_ref();
1268 assert_eq!(terminal_it, sub_ab.is_none(), "{c_ix}, {c}, {terminal_it}",);
1269
1270 if terminal_it {
1271 let ct = l.ct.as_ref();
1272 assert!(ct.is_some());
1273 let ct = unsafe { ct.unwrap_unchecked() };
1274 assert_eq!(&2, ct);
1275 } else {
1276 sup_ab = unsafe { sub_ab.unwrap_unchecked() };
1277 }
1278 }
1279 }
1280
1281 #[test]
1282 fn exact() {
1283 let entry = || "impreciseness".chars();
1284 const VAL: usize = 15;
1285
1286 let mut toc = Toc::new();
1287 assert_eq!(AddRes::Ok(None), toc.add(entry(), Some(VAL)));
1288 assert_eq!(1, toc.ct);
1289
1290 assert_eq!(VerRes::Ok(VAL), toc.acq(entry()));
1291 }
1292
1293 #[test]
1294 fn exact_over() {
1295 let entry = || "impreciseness".chars();
1296 const VAL: usize = 15;
1297
1298 let mut toc = Toc::new();
1299 _ = toc.add(entry(), None);
1300 assert_eq!(1, toc.ct);
1301
1302 assert_eq!(AddRes::Ok(Some(1)), toc.add(entry(), Some(VAL)));
1303 assert_eq!(1, toc.ct);
1304
1305 assert_eq!(VerRes::Ok(VAL), toc.acq(entry()));
1306 }
1307
1308 use crate::VerRes;
1309
1310 #[test]
1311 #[allow(non_snake_case)]
1312 #[rustfmt::skip]
1313 #[cfg(feature = "test-ext")]
1314 fn load() {
1315
1316 let strs = [
1317 ("zzbb", 44_441), ("zzaa", 88_999),
1318 ("xya", 77_666), ("xyz", 22_333),
1319 ("abc", 33_222), ("abd", 74_332),
1320 ("abcd", 11_234), ("abce", 11_234),
1321 ("qaa", 16_678), ("qrs", 24_555),
1322 ("qrt", 900_001), ("qua", 130_901),
1323 ("qwa", 2_006),
1324 ("percent", 77_110), ("percentile", 99_888),
1325 ("quail", 20_333), ("qualification", 33_111),
1326 ("quality", 555_666), ("quantity", 116_777),
1327 ("XYAB", 544_555), ("XYABA", 111_900),
1328 ("JUI", 30_000), ("JUN", 100_000),
1329 ("XYA", 80_000), ("XYQ", 11_111),
1330 ("XYZ", 111_333), ("XYABC", 222_000),
1331 ("MOMENT", 15_999), ("INSTANT", 34_341),
1332 ("JUNCTURE", 789_223),
1333 ("ABC", 14_234), ("ABD", 34_123)
1334 ];
1335
1336 let mut toc = Toc::new();
1337 for (s, c) in strs {
1338 for i in 0..c {
1339 let res = toc.add(s.chars(), None);
1340 let prev = if i > 0 {
1341 Some(i)
1342 } else {
1343 None
1344 };
1345 assert_eq!(AddRes::Ok(prev), res);
1346 }
1347 }
1348
1349 for (s, c) in strs {
1350 let res = toc.acq(s.chars());
1351 assert_eq!(VerRes::Ok(c), res);
1352 }
1353
1354 assert_eq!(strs.len(), toc.ct);
1355 }
1356
1357 #[test]
1358 fn overflow_wrap() {
1359 let mut toc = Toc::new();
1360
1361 let entry = || "a".chars();
1362
1363 _ = toc.add(entry(), None);
1364 _ = toc.put(entry(), usize::MAX);
1365 _ = toc.add(entry(), None);
1366 assert_eq!(VerRes::Ok(0), toc.acq(entry()));
1367 assert_eq!(1, toc.ct);
1368 }
1369 }
1370
1371 mod acq {
1372 use crate::{Toc, VerRes};
1373
1374 #[test]
1375 #[allow(non_upper_case_globals)]
1376 fn known_unknown() {
1377 let a = || "a".chars();
1378 let b = || "b".chars();
1379
1380 let mut toc = Toc::new();
1381 _ = toc.add(a(), None);
1382
1383 assert_eq!(VerRes::Ok(1), toc.acq(a()));
1384 assert_eq!(VerRes::Unknown, toc.acq(b()));
1385 }
1386
1387 #[test]
1388 fn zero_occurrent() {
1389 let toc = Toc::new();
1390 assert_eq!(VerRes::ZeroLen, toc.acq("".chars()));
1391 }
1392 }
1393
1394 mod put {
1395 use crate::{Toc, VerRes};
1396
1397 #[test]
1398 #[allow(non_upper_case_globals)]
1399 fn known_unknown() {
1400 let a = || "a".chars();
1401 let b = || "b".chars();
1402
1403 let mut toc = Toc::new();
1404 _ = toc.add(a(), None);
1405
1406 assert_eq!(VerRes::Ok(1), toc.put(a(), 3));
1407 assert_eq!(VerRes::Ok(3), toc.acq(a()));
1408 assert_eq!(VerRes::Unknown, toc.put(b(), 3));
1409 }
1410
1411 #[test]
1412 fn zero_occurrent() {
1413 let mut toc = Toc::new();
1414 assert_eq!(VerRes::ZeroLen, toc.put("".chars(), 3));
1415 }
1416 }
1417
1418 mod rem {
1419 use crate::{Toc, VerRes};
1420
1421 #[test]
1422 fn known_unknown() {
1423 let known = || "VigilantAndVigourous".chars();
1424 let unknown = || "NeglectfulAndFeeble".chars();
1425
1426 let mut toc = Toc::new();
1427 _ = toc.add(known(), None);
1428
1429 assert_eq!(VerRes::Unknown, toc.rem(unknown()));
1430 assert_eq!(0, toc.tr.len());
1431
1432 assert_eq!(1, toc.ct());
1433
1434 assert_eq!(VerRes::Ok(1), toc.rem(known()));
1435 assert_eq!(VerRes::Unknown, toc.acq(known()));
1436 assert_eq!(0, toc.tr.len());
1437
1438 assert_eq!(0, toc.ct());
1439 }
1440
1441 #[test]
1442 fn zero_occurrent() {
1443 let mut toc = Toc::new();
1444 assert_eq!(VerRes::ZeroLen, toc.rem("".chars()));
1445 }
1446 }
1447
1448 mod rem_actual {
1449 use crate::{Toc, VerRes, TraRes};
1450 use crate::english_letters::ix;
1451
1452 #[test]
1453 fn basic_test() {
1454 let entry = || "ABCxyz".chars();
1455 let mut toc = Toc::new();
1456 _ = toc.add(entry(), None);
1457
1458 _ = toc.track(entry(), true, false);
1459
1460 assert_eq!(1, Toc::rem_actual(&mut toc));
1461
1462 #[allow(non_snake_case)]
1463 let K = &toc.rt[ix('A')];
1464 assert_eq!(false, K.ab());
1465 }
1466
1467 #[test]
1468 fn ab_len_test() {
1469 let ix = |c| match c {
1470 | 'a' => 0,
1471 | 'z' => 99,
1472 | _ => panic!(),
1473 };
1474
1475 let key_1 = || "aaa".chars();
1476 let key_2 = || "aaz".chars();
1477
1478 let key_1_val = 50;
1479 let key_2_val = 60;
1480
1481 let mut toc = Toc::new_with(ix, None, 100);
1482 _ = toc.add(key_1(), Some(key_1_val));
1483 _ = toc.add(key_2(), Some(key_2_val));
1484
1485 _ = toc.track(key_1(), true, false);
1486
1487 assert_eq!(key_1_val, Toc::rem_actual(&mut toc));
1488 assert!(toc.acq(key_2()).is_ok());
1489 }
1490
1491 #[test]
1492 fn inner_entry() {
1493 let mut toc = Toc::new();
1494
1495 let outer = || "Keyword".chars();
1496 _ = toc.add(outer(), None);
1497
1498 let inner = || "Key".chars();
1499 _ = toc.add(inner(), None);
1500
1501 _ = toc.track(inner(), true, false);
1502
1503 assert_eq!(1, Toc::rem_actual(&mut toc));
1504 assert_eq!(VerRes::Unknown, toc.acq(inner()));
1505 assert_eq!(VerRes::Ok(1), toc.acq(outer()));
1506 }
1507
1508 #[test]
1509 fn entry_with_peer_entry() {
1510 let mut toc = Toc::new();
1511
1512 let peer = || "Keyworder".chars();
1513 _ = toc.add(peer(), None);
1514
1515 let test = || "Keywordee".chars();
1516 _ = toc.add(test(), None);
1517
1518 _ = toc.track(test(), true, false);
1519
1520 assert_eq!(1, Toc::rem_actual(&mut toc));
1521 assert_eq!(VerRes::Unknown, toc.acq(test()));
1522 assert_eq!(VerRes::Ok(1), toc.acq(peer()));
1523 }
1524
1525 #[test]
1526 fn entry_with_peer_with_alphabet() {
1527 let mut toc = Toc::new();
1528
1529 let peer = || "Keyworders".chars();
1530 _ = toc.add(peer(), None);
1531
1532 let test = || "Keywordee".chars();
1533 _ = toc.add(test(), None);
1534
1535 _ = toc.track(test(), true, false);
1536
1537 assert_eq!(1, Toc::rem_actual(&mut toc));
1538 assert_eq!(VerRes::Unknown, toc.acq(test()));
1539 assert_eq!(VerRes::Ok(1), toc.acq(peer()));
1540 }
1541
1542 #[test]
1543 fn entry_under_entry() {
1544 let mut toc = Toc::new();
1545
1546 let above = || "Keyworder".chars();
1547 _ = toc.add(above(), None);
1548
1549 let under = || "Keyworders".chars();
1550 _ = toc.add(under(), None);
1551
1552 _ = toc.track(under(), true, false);
1553
1554 assert_eq!(1, Toc::rem_actual(&mut toc));
1555 assert_eq!(VerRes::Unknown, toc.acq(under()));
1556 assert_eq!(VerRes::Ok(1), toc.acq(above()));
1557
1558 let res = toc.track(above(), false, false);
1559 if let TraRes::Ok(l) = res {
1560 #[cfg(feature = "test-ext")]
1561 assert_eq!('r', l.val);
1562 assert_eq!(false, l.ab());
1563 } else {
1564 panic!("TraRes::Ok(_) was expected, instead {:?}.", res);
1565 }
1566 }
1567 }
1568
1569 mod track {
1570 use crate::{Toc, TraRes};
1571
1572 #[test]
1573 fn zero_occurrent() {
1574 let toc = Toc::new();
1575 let res = toc.track("".chars(), false, false);
1576 assert_eq!(TraRes::ZeroLen, res);
1577 }
1578
1579 #[test]
1580 #[cfg(feature = "test-ext")]
1581 fn singular_occurrent() {
1582 let entry = || "A".chars();
1583
1584 let mut toc = Toc::new();
1585
1586 _ = toc.add(entry(), None);
1587 let res = toc.track(entry(), true, false);
1588
1589 if let TraRes::Ok(l) = res {
1590 let l_val = l.val;
1591 let tr = &toc.tr;
1592
1593 assert_eq!('A', l_val);
1594 assert_eq!(1, tr.len());
1595
1596 let l = unsafe { tr[0].as_ref() }.unwrap();
1597 assert_eq!('A', l.val)
1598 } else {
1599 panic!("TraRes::Ok(_) was expected, instead {:?}.", res);
1600 }
1601 }
1602
1603 #[test]
1604 #[cfg(feature = "test-ext")]
1605 fn tracing() {
1606 let entry = || "DictionaryLexicon".chars();
1607
1608 let mut toc = Toc::new();
1609 _ = toc.add(entry(), None);
1610 _ = toc.track(entry(), true, false);
1611
1612 let proof = entry().collect::<Vec<char>>();
1613 let tr = &toc.tr;
1614
1615 assert_eq!(proof.len(), tr.len());
1616
1617 for (x, &c) in proof.iter().enumerate() {
1618 let l = tr[x];
1619 let l = unsafe { l.as_ref() }.unwrap();
1620 assert_eq!(c, l.val);
1621 }
1622 }
1623
1624 #[test]
1625 #[cfg(feature = "test-ext")]
1626 fn ok_variants() {
1627 let entry = || "Wordbook".chars();
1628 let last = 'k';
1629
1630 let mut toc = Toc::new();
1631 _ = toc.add(entry(), None);
1632 let res = toc.track(entry(), false, false);
1633
1634 match res {
1635 | TraRes::Ok(l) => assert_eq!(last, l.val),
1636 | _ => panic!("TraRes::Ok(_) was expected, instead {:?}.", res),
1637 }
1638
1639 let res = toc.track(entry(), false, true);
1640 match res {
1641 | TraRes::OkMut(l) => assert_eq!(last, l.val),
1642 | _ => panic!("TraRes::OkMut(_) was expected, instead {:?}.", res),
1643 }
1644 }
1645
1646 #[test]
1647 fn unknown_not_path() {
1648 let key = || "Wordbook".chars();
1649 let bad_key = || "Wordbooks".chars();
1650
1651 let mut toc = Toc::new();
1652 _ = toc.add(key(), None);
1653 let res = toc.track(bad_key(), false, false);
1654 assert_eq!(TraRes::UnknownForAbsentPath, res);
1655 }
1656
1657 #[test]
1658 fn unknown_not_entry() {
1659 let key = || "Wordbooks".chars();
1660 let bad_key = || "Wordbook".chars();
1661
1662 let mut toc = Toc::new();
1663 _ = toc.add(key(), None);
1664 let res = toc.track(bad_key(), false, false);
1665 assert_eq!(TraRes::UnknownForNotEntry, res);
1666 }
1667 }
1668
1669 mod ext {
1670 use crate::{Toc, VerRes};
1671 use crate::english_letters::ix;
1672
1673 #[test]
1674 fn basic_test() {
1675 let proof = vec![
1676 (String::from("AA"), 13),
1677 (String::from("AzBq"), 11),
1678 (String::from("By"), 329),
1679 (String::from("ZaZazAzAzAbYyb"), 55),
1680 (String::from("yBC"), 7),
1681 (String::from("ybXr"), 53),
1682 (String::from("ybXrQUTmop"), 33),
1683 (String::from("ybXrQUTmopFVB"), 99),
1684 (String::from("ybXrQUTmopRFG"), 80),
1685 (String::from("zAzAZaZaZaByYB"), 44),
1686 ];
1687
1688 let mut toc = Toc::new();
1689 for p in proof.iter() {
1690 _ = toc.add(p.0.chars(), Some(p.1));
1691 }
1692
1693 let ext = toc.ext();
1694 assert_eq!(true, ext.is_some());
1695
1696 let ext = ext.unwrap();
1697 assert_eq!(proof.len(), ext.len());
1698 assert_eq!(proof, ext);
1699 assert_eq!(true, ext.capacity() >= 1000);
1700
1701 for p in proof.iter() {
1702 assert_eq!(VerRes::Ok(p.1), toc.acq(p.0.chars()));
1703 }
1704 }
1705
1706 #[test]
1707 #[should_panic(
1708 expected = "This method is unsupported when `new_with` `re` parameter is provided with `None`."
1709 )]
1710 fn re_not_provided() {
1711 _ = Toc::new_with(ix, None, 0).ext()
1712 }
1713
1714 #[test]
1715 fn empty_tree() {
1716 let toc = Toc::new();
1717 assert_eq!(None, toc.ext());
1718 }
1719 }
1720
1721 use crate::VerRes;
1722
1723 #[test]
1724 fn clr() {
1725 let key = || "abc".chars();
1726
1727 let mut toc = Toc::new();
1728 _ = toc.add(key(), None);
1729 assert_eq!(1, toc.clr());
1730
1731 assert_eq!(VerRes::Unknown, toc.acq(key()));
1732 assert_eq!(ab(ALPHABET_LEN), toc.rt);
1733 assert_eq!(0, toc.ct);
1734 }
1735
1736 #[test]
1737 fn ct() {
1738 let test = 3;
1739 let mut toc = Toc::new();
1740 assert_eq!(0, toc.ct());
1741 toc.ct = test;
1742 assert_eq!(test, toc.ct());
1743 }
1744 }
1745}
1746
1747