t_oc/
lib.rs

1//! Trie Occurrence Counter is frequency dictionary that uses any `impl Iterator<Item = char>` type as occurrent.
2//!
3//! Support for English letters A–Za–z OOB.
4
5use 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/// `Letter` is `Alphabet` element, represents tree node.
77#[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
108/// Tree node arms. Consists of `Letter`s.
109type Alphabet = Box<[Letter]>;
110/// Index conversion function. Tighten with alphabet used.
111/// Returns corresponding `usize`d index of `char`.
112///
113/// For details see `english_letters::ix` implementation.
114pub type Ix = fn(char) -> usize;
115
116/// Reversal index conversion function. Symmetrically mirrors `Ix` function.
117///
118/// For details see `english_letters::re` implementation.
119pub type Re = fn(usize) -> char;
120
121/// Alphabet function, tree arms generation of length specified.
122fn 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
149/// Module for working with English alphabet letters, A-Za-z.
150///
151/// For details see `Toc::new_with()`.
152pub mod english_letters {
153
154    /// 26
155    pub const BASE_ALPHABET_LEN: usize = 26;
156    /// 52
157    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    /// Index conversion function.
164    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    /// Index reversal conversion function.
177    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///  Addition result enumeration.
191#[derive(Debug)]
192#[derive(PartialEq, Eq)]
193pub enum AddRes {
194    /// Addition accomplished. Optionally carries previous value, based on its existence.
195    Ok(Option<usize>),
196    /// Attempt to add zero occurrent.
197    ZeroLen,
198}
199
200impl AddRes {
201    /// Returns `true` only for `AddRes::Ok(_)`.
202    pub const fn is_ok(&self) -> bool {
203        match self {
204            | AddRes::Ok(_) => true,
205            | _ => false,
206        }
207    }
208
209    /// Returns `true` only for `AddRes::Ok(Some(_))`.
210    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    /// Returns `usize` of `AddRes::Ok(Some(usize))` or _panics_ if:
221    /// - not that variant
222    /// - `Option<usize>` is `None`
223    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    /// Returns `usize` of `AddRes::Ok(Some(usize))` and does not _panic_ (UB) if:
234    /// - not that variant
235    /// - `Option<usize>` is `None`
236    ///
237    /// Check with `std::hint::unreachable_unchecked` for more information.
238    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        // SAFETY: the safety contract must be upheld by the caller.
245        unsafe { std::hint::unreachable_unchecked() }
246    }
247}
248
249/// Versatile result enumeration.
250///
251/// Used by various methods in versatile way.
252#[derive(Debug)]
253#[derive(PartialEq, Eq)]
254pub enum VerRes {
255    /// Operation accomplished.
256    Ok(usize),
257    /// Zero occurrent usage.
258    ZeroLen,
259    /// Unknown occurrent usage.
260    Unknown,
261}
262
263impl VerRes {
264    /// Returns `true` only for `VerRes::Ok(_)`.
265    pub const fn is_ok(&self) -> bool {
266        match self {
267            | VerRes::Ok(_) => true,
268            | _ => false,
269        }
270    }
271
272    /// Returns `usize` of `VerRes::Ok(usize)` or _panics_ if not that variant.
273    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    /// Returns `usize` of `VerRes::Ok(usize)` and does not _panic_ if not that variant (UB).
281    ///
282    /// Check with `std::hint::unreachable_unchecked` for more information.
283    pub const unsafe fn uproot_unchecked(&self) -> usize {
284        match self {
285            | VerRes::Ok(res) => *res,
286            // SAFETY: the safety contract must be upheld by the caller.
287            | _ => 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
314// TC: Ω(n ⋅ alphabet size) ⇒ Ω(n), n = nodes count
315// SC: Θ(s + n) ⇒ Θ(s), n = nodes count, s = key lengths sum
316// to lower estimation add unpredictible count of string clonings
317// and buffers (capacity-) reallocations
318fn 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
337/// Trie Occurrence Counter is frequency dictionary that uses any `impl Iterator<Item = char>` type as occurrent.
338///
339/// OOB English letters A–Za–z support only.
340///
341/// ```
342/// use t_oc::Toc;
343/// use std::panic::catch_unwind;
344///
345/// let mut toc = Toc::new();
346/// let occurrent = "true";
347///
348/// _ = toc.add(occurrent.chars(), None);
349/// _ = toc.add(true.to_string().chars(), None);
350///
351/// assert_eq!(2, toc.acq(occurrent.chars()).uproot());
352/// toc.put(occurrent.chars(), 15);
353/// assert_eq!(15, toc.acq(occurrent.chars()).uproot());
354///
355/// let catch = catch_unwind(move|| _ = toc.add("#&%".chars(), None));
356/// assert!(catch.is_err());
357/// ```
358///
359/// When asymptotic computational complexity is not explicitly specified , it is:
360/// - TC: Θ(c) where c is count of `char`s iterated over.
361/// - SC: Θ(0).
362pub struct Toc {
363    // tree root
364    rt: Alphabet,
365    // index fn
366    ix: Ix,
367    // rev index fn
368    re: Option<Re>,
369    // alphabet len
370    al: usize,
371    // backtrace buff
372    tr: UC<Vec<*mut Letter>>,
373    // occurrent count
374    ct: usize,
375}
376
377impl Toc {
378    /// Constructs default version of `Toc`, i.e. via
379    /// `fn new_with()` with `english_letters::{ix, re, ALPHABET_LEN}`.
380    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    /// Allows to use custom alphabet different from default alphabet.
389    ///
390    /// ```
391    /// use t_oc::Toc;
392    ///
393    /// fn ix(c: char) -> usize {
394    ///     match c {
395    ///         '&' => 0,
396    ///         '|' => 1,
397    ///         _ => panic!(),
398    ///     }
399    /// }
400    ///
401    /// // if `fn Toc::ext` will not be used, pass `None` for `re`
402    /// fn re(i: usize) -> char {
403    ///     match i {
404    ///         0 => '&',
405    ///         1 => '|',
406    ///         _ => panic!(),
407    ///     }
408    /// }
409    ///
410    /// let ab_len = 2;
411    ///
412    /// let mut toc = Toc::new_with(ix, Some(re), ab_len);
413    /// let a = "&";
414    /// let b = "|";
415    /// let aba = "&|&";
416    /// _ = toc.add(a.chars(), None);
417    /// _ = toc.add(a.chars(), None);
418    /// _ = toc.add(b.chars(), None);
419    /// _ = toc.add(aba.chars(), None);
420    /// assert_eq!(2, toc.acq(a.chars()).uproot());
421    /// assert_eq!(1, toc.acq(aba.chars()).uproot());
422    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    /// Used to set internal backtracing buffer capacity.
434    ///
435    /// `Toc` uses internal buffer, to avoid excessive allocations and copying, which grows
436    /// over time due backtracing in `rem` method which backtraces whole path from entry
437    /// node to root node.
438    ///
439    /// Use this method to shrink or extend it to fit actual program needs. Neither shrinking nor extending
440    /// is guaranteed to be exact. See `Vec::with_capacity()` and `Vec::reserve()`. For optimal `rem` performance, set `approx_cap` to, at least, `occurrent.count()`.
441    ///
442    /// Some high value is sufficient anyway. Since buffer continuous
443    /// usage, its capacity will likely expand at some point in time to size sufficient to all occurrents.
444    ///
445    /// Return value is actual buffer capacity.
446    ///
447    /// **Note:** While `String` is UTF8 encoded, its byte length does not have to equal its `char` count
448    /// which is either equal or lesser.
449    /// ```
450    /// let sights = "🤩";
451    /// assert_eq!(4, sights.len());
452    /// assert_eq!(1, sights.chars().count());
453    ///
454    /// let yes = "sí";
455    /// assert_eq!(3, yes.len());
456    /// assert_eq!(2, yes.chars().nth(1).unwrap().len_utf8());
457    ///
458    /// let abc = "abc";
459    /// assert_eq!(3, abc.len());
460    /// ```
461    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    /// Used to obtain internal backtracing buffer capacity.
475    ///
476    /// Check with `fn put_trace_cap` for details.
477    pub fn acq_trace_cap(&self) -> usize {
478        self.tr.capacity()
479    }
480
481    /// Used to add occurence to tree.
482    ///
483    /// Counter is of word size. Add overflow is wrapped using `wrapping_add`.
484    ///
485    /// Optional `val` parameter can be used to insert exact value.
486    ///
487    /// Return value is `AddRes::Ok(Option<usize>)` for non-zero `occurrent` and holds previous value, if there was some.
488    ///
489    /// - SC: Θ(q) where q is number of unique nodes, i.e. `char`s in respective branches.
490    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    /// Used to acquire value for `occurrent`.
530    ///
531    /// If `VerRes::Ok(usize)`, `usize` is `occurrent` occurrences count.
532    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    /// Used to put new value for `occurrent` occurrences.
544    ///
545    /// If `VerRes::Ok(usize)`, `usize` is previous value.
546    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    /// Used to remove `occurrent` from tree.
559    ///
560    /// If `VerRes::Ok(usize)`, `usize` is `occurrent` occurrences count.
561    ///
562    /// - _c_ is count of `char`s iterated over.
563    /// - TC: Ω(c) or ϴ(c) (backtracing buffer capacity dependent complexity).
564    /// - SC: ϴ(c).
565    ///
566    /// Check with `put_trace_cap` for details on backtracing.
567    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    // - s is count of `char`s iterated over
617    // - TC: Ω(s) when `tracing = true`, ϴ(s) otherwise
618    // - SC: ϴ(s) when `tracing = true`, ϴ(0) otherwise
619    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    /// Used to extract occurences from tree.
667    ///
668    /// Extraction is alphabetically ordered. Does not clear tree. Use `fn clr` for clearing.
669    ///
670    /// Return value is `None` for empty `Toc`.
671    ///
672    /// - TC: Ω(n) where n is count of nodes in tree.
673    /// - SC: Θ(s) where s is occurrent lengths summation.
674    ///
675    /// Returned set can be overcapacitated, i.e. its capacity
676    /// will not be shrunken according to its length.
677    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            // capacity is prebuffered to 1000
684            let mut buff = String::with_capacity(1000);
685
686            // capacity is prebuffered to 1000
687            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    /// Used to clear tree.
697    ///
698    /// Return value is count of occurrents in tree before clearing.
699    ///
700    /// TC: Θ(n) where n is count of nodes in tree.
701    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    /// Used to acquire count of occurrents in tree.
709    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, // 65–90
845                    'a' as u8 -1, 'z' as u8 +1, // 97–122
846                ];
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// cargo fmt && cargo test --features test-ext --release
1748// cargo fmt && cargo test --release