louds_rs/louds/
louds_impl.rs

1use super::{ChildIndexIter, ChildNodeIter, Louds, LoudsIndex, LoudsNodeNum, AncestorNodeIter};
2use fid_rs::Fid;
3
4impl From<&str> for Louds {
5    /// Prepares for building [Louds](struct.Louds.html) from LBS (LOUDS Bit vector).
6    ///
7    /// It takes _O(log `s`)_ time for validation.
8    ///
9    /// # Panics
10    /// If `s` does not represent a LOUDS tree. `s` must satisfy the following condition as LBS.
11    ///
12    /// - Starts from "10"
13    /// - In the range of _[0, i]_ for any _i (< length of LBS)_;
14    ///     - _<u>the number of '0'</u> <= <u>the number of '1'</u> + 1_, because:
15    ///         - Each node, including virtual root (node num = 0), has one '0'.
16    ///         - Each node is derived from one '1'.
17    /// - In the range of _[0, <u>length of LBS</u>)_;
18    ///     - _<u>the number of '0'</u> == <u>the number of '1'</u> + 1_
19    fn from(s: &str) -> Self {
20        let s: String = s
21            .chars()
22            .filter(|c| match c {
23                '0' | '1' => true,
24                '_' => false,
25                _ => panic!("not allowed"),
26            })
27            .collect();
28        let fid = Fid::from(s.as_str());
29        Self::validate_lbs(&fid);
30        Louds { lbs: fid }
31    }
32}
33
34impl From<&[bool]> for Louds {
35    /// Prepares for building [Louds](struct.Louds.html) from LBS (LOUDS Bit vector).
36    ///
37    /// It takes _O(log `bits`)_ time for validation.
38    ///
39    /// # Panics
40    /// Same as [Louds::from::<&str>()](struct.Louds.html#implementations).
41    fn from(bits: &[bool]) -> Self {
42        let fid = Fid::from(bits);
43        Self::validate_lbs(&fid);
44        Louds { lbs: fid }
45    }
46}
47
48impl Louds {
49    /// # Panics
50    /// `node_num` does not exist in this LOUDS.
51    pub fn node_num_to_index(&self, node_num: LoudsNodeNum) -> LoudsIndex {
52        assert!(node_num.0 > 0);
53
54        let index = self
55            .lbs
56            .select(node_num.0)
57            .unwrap_or_else(|| panic!("NodeNum({}) does not exist in this LOUDS", node_num.0,));
58        LoudsIndex(index)
59    }
60
61    /// # Panics
62    /// `index` does not point to any node in this LOUDS.
63    pub fn index_to_node_num(&self, index: LoudsIndex) -> LoudsNodeNum {
64        self.validate_index(index);
65
66        let node_num = self.lbs.rank(index.0);
67        LoudsNodeNum(node_num)
68    }
69
70    /// # Panics
71    /// - `index` does not point to any node in this LOUDS.
72    /// - `index == 0`: (node#1 is root and doesn't have parent)
73    pub fn child_to_parent(&self, index: LoudsIndex) -> LoudsNodeNum {
74        self.validate_index(index);
75        assert!(index.0 != 0, "node#1 is root and doesn't have parent");
76
77        let parent_node_num = self.lbs.rank0(index.0);
78        LoudsNodeNum(parent_node_num)
79    }
80
81    /// Return an iterator to the `child` and its ancestors' node numbers.
82    pub fn child_to_ancestors(&self, child: LoudsNodeNum) -> AncestorNodeIter {
83        AncestorNodeIter {
84            inner: self,
85            node: child,
86        }
87    }
88
89    /// # Panics
90    /// `node_num` does not exist in this LOUDS.
91    pub fn parent_to_children(&self, node_num: LoudsNodeNum) -> Vec<LoudsIndex> {
92        self.parent_to_children_indices(node_num).collect()
93    }
94
95    /// # Panics
96    /// `node_num` does not exist in this LOUDS.
97    pub fn parent_to_children_indices(&self, node_num: LoudsNodeNum) -> ChildIndexIter {
98        assert!(node_num.0 > 0);
99
100        ChildIndexIter {
101            inner: self,
102            node: node_num,
103            start: None,
104            end: None,
105        }
106    }
107
108    /// # Panics
109    /// `node_num` does not exist in this LOUDS.
110    pub fn parent_to_children_nodes(&self, node_num: LoudsNodeNum) -> ChildNodeIter {
111        ChildNodeIter(self.parent_to_children_indices(node_num))
112    }
113
114    /// Checks if `lbs` satisfy the LBS's necessary and sufficient condition:
115    fn validate_lbs(lbs: &Fid) {
116        assert!(lbs[0]);
117        assert!(!lbs[1]);
118
119        let (mut cnt0, mut cnt1) = (0u64, 0u64);
120        for (i, bit) in lbs.iter().enumerate() {
121            if bit {
122                cnt1 += 1
123            } else {
124                cnt0 += 1
125            };
126            assert!(
127                cnt0 <= cnt1 + 1,
128                "At index {}, the number of '0' ({}) == (the number of '1' ({})) + 2.",
129                i,
130                cnt0,
131                cnt1,
132            );
133        }
134        assert_eq!(cnt0, cnt1 + 1);
135    }
136
137    /// # Panics
138    /// `index` does not point to any node in this LOUDS.
139    fn validate_index(&self, index: LoudsIndex) {
140        assert!(
141            self.lbs[index.0],
142            "LBS[index={:?}] must be '1'",
143            index,
144        );
145    }
146}
147
148impl<'a> ChildIndexIter<'a> {
149    /// Return the length of the iterator.
150    ///
151    /// It costs _O(log N)_ if the iterator has not had `.next()` and
152    /// `.next_back()` called.
153    ///
154    /// Question: Why not implement [std::iter::ExactSizeIterator]? One could
155    /// but they'd be required to do it one of two ways because its signature is
156    /// `fn len(&self) -> usize`; `&self` is not mutable:
157    ///
158    /// 1. Use interior mutability in [ChildIndexIter]. This was attempted with
159    /// a [std::cell::RefCell] but it hurt performance slightly.
160    ///
161    /// 2. Initialize [ChildIndexIter] with the start and end. However
162    ///    initializing start and end costs _O(log N)_ each.
163    pub fn len(&mut self) -> usize {
164        if self.start.is_none() {
165            self.start = Some(
166                self.inner.lbs.select0(self.node.0).unwrap_or_else(|| {
167                    panic!("NodeNum({}) does not exist in this LOUDS", self.node.0,)
168                }) + 1,
169            );
170        }
171        if self.end.is_none() {
172            self.end = Some(
173                self.inner.lbs.select0(self.node.0 + 1).unwrap_or_else(|| {
174                    panic!("NodeNum({}) does not exist in this LOUDS", self.node.0 + 1,)
175                }) - 1,
176            );
177        }
178        let start = self.start.unwrap();
179        let end = self.end.unwrap();
180        (end + 1 - start) as usize
181    }
182
183    /// Returns whether the iterator is empty.
184    pub fn is_empty(&mut self) -> bool {
185        self.len() == 0
186    }
187}
188
189impl<'a> Iterator for ChildIndexIter<'a> {
190    type Item = LoudsIndex;
191    #[inline]
192    fn next(&mut self) -> Option<Self::Item> {
193        if self.start.is_none() {
194            self.start = Some(
195                self.inner.lbs.select0(self.node.0).unwrap_or_else(|| {
196                    panic!("NodeNum({}) does not exist in this LOUDS", self.node.0,)
197                }) + 1,
198            );
199        }
200        let start = self.start.unwrap();
201        self.end
202            .map(|last| start <= last)
203            .unwrap_or_else(|| self.inner.lbs[start])
204            .then(|| {
205                self.start = Some(start + 1);
206                LoudsIndex(start)
207            })
208    }
209}
210
211impl<'a> DoubleEndedIterator for ChildIndexIter<'a> {
212    #[inline]
213    fn next_back(&mut self) -> Option<Self::Item> {
214        if self.end.is_none() {
215            self.end = Some(
216                self.inner.lbs.select0(self.node.0 + 1).unwrap_or_else(|| {
217                    panic!("NodeNum({}) does not exist in this LOUDS", self.node.0 + 1,)
218                }) - 1,
219            );
220        }
221        let end = self.end.unwrap();
222        self.start
223            .map(|first| first <= end)
224            .unwrap_or_else(|| self.inner.lbs[end])
225            .then(|| {
226                self.end = Some(end - 1);
227                LoudsIndex(end)
228            })
229    }
230}
231
232impl<'a> Iterator for ChildNodeIter<'a> {
233    type Item = LoudsNodeNum;
234    #[inline]
235    fn next(&mut self) -> Option<Self::Item> {
236        self.0
237            .next()
238            .map(|index| self.0.inner.index_to_node_num(index))
239    }
240}
241
242impl<'a> Iterator for AncestorNodeIter<'a> {
243    type Item = LoudsNodeNum;
244    #[inline]
245    fn next(&mut self) -> Option<Self::Item> {
246        if self.node.0 <= 1 {
247            None
248        } else {
249            let result = self.node;
250            let index = self.inner.node_num_to_index(self.node);
251            self.node = LoudsNodeNum(self.inner.lbs.rank0(index.0));
252            Some(result)
253        }
254    }
255}
256
257impl<'a> DoubleEndedIterator for ChildNodeIter<'a> {
258    #[inline]
259    fn next_back(&mut self) -> Option<Self::Item> {
260        self.0
261            .next_back()
262            .map(|index| self.0.inner.index_to_node_num(index))
263    }
264}
265
266impl<'a> ChildNodeIter<'a> {
267    /// See [ChildIndexIter::len].
268    pub fn len(&mut self) -> usize {
269        self.0.len()
270    }
271
272    /// Returns whether the iterator is empty.
273    pub fn is_empty(&mut self) -> bool {
274        self.len() == 0
275    }
276}
277
278#[cfg(test)]
279mod validate_lbs_success_tests {
280    use crate::Louds;
281    use fid_rs::Fid;
282
283    macro_rules! parameterized_tests {
284        ($($name:ident: $value:expr,)*) => {
285        $(
286            #[test]
287            fn $name() {
288                let s = $value;
289                let fid = Fid::from(s);
290                Louds::validate_lbs(&fid);
291            }
292        )*
293        }
294    }
295
296    parameterized_tests! {
297        t1: "10_0",
298        t2: "10_10_0",
299        t3: "10_1110_10_0_1110_0_0_10_110_0_0_0",
300        t4: "10_11111111110_0_0_0_0_0_0_0_0_0_0",
301    }
302}
303
304#[cfg(test)]
305mod validate_lbs_failure_tests {
306    use crate::Louds;
307    use fid_rs::Fid;
308
309    macro_rules! parameterized_tests {
310        ($($name:ident: $value:expr,)*) => {
311        $(
312            #[test]
313            #[should_panic]
314            fn $name() {
315                let s = $value;
316                let fid = Fid::from(s);
317                Louds::validate_lbs(&fid);
318            }
319        )*
320        }
321    }
322
323    parameterized_tests! {
324        t1: "0",
325        t2: "1",
326        t3: "00",
327        t4: "01",
328        t5: "10",
329        t6: "11",
330        t7: "00_0",
331        t8: "01_0",
332        t9: "11_0",
333        t10: "10_1",
334        t11: "10_10",
335        t12: "10_01",
336        t13: "10_1110_10_0_1110_0_0_10_110_0_0_1",
337    }
338}
339
340#[cfg(test)]
341mod node_num_to_index_success_tests {
342    use crate::{Louds, LoudsIndex, LoudsNodeNum};
343
344    macro_rules! parameterized_tests {
345        ($($name:ident: $value:expr,)*) => {
346        $(
347            #[test]
348            fn $name() {
349                let (in_s, node_num, expected_index) = $value;
350                let louds = Louds::from(in_s);
351                let index = louds.node_num_to_index(LoudsNodeNum(node_num));
352                assert_eq!(index, LoudsIndex(expected_index));
353            }
354        )*
355        }
356    }
357
358    parameterized_tests! {
359        t1_1: ("10_0", 1, 0),
360
361        t2_1: ("10_10_0", 1, 0),
362        t2_2: ("10_10_0", 2, 2),
363
364        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 1, 0),
365        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 2, 2),
366        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 3, 3),
367        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 4, 4),
368        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 5, 6),
369        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 6, 9),
370        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 7, 10),
371        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 8, 11),
372        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 9, 15),
373        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 10, 17),
374        t3_11: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 11, 18),
375    }
376}
377
378#[cfg(test)]
379mod node_num_to_index_failure_tests {
380    use crate::{Louds, LoudsNodeNum};
381
382    macro_rules! parameterized_node_not_found_tests {
383        ($($name:ident: $value:expr,)*) => {
384        $(
385            #[test]
386            #[should_panic]
387            fn $name() {
388                let (in_s, node_num) = $value;
389                let louds = Louds::from(in_s);
390                let _ = louds.node_num_to_index(LoudsNodeNum(node_num));
391            }
392        )*
393        }
394    }
395
396    parameterized_node_not_found_tests! {
397        t1_1: ("10_0", 0),
398        t1_2: ("10_0", 2),
399
400        t2_1: ("10_10_0", 0),
401        t2_2: ("10_10_0", 3),
402
403        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 0),
404        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 12),
405    }
406}
407
408#[cfg(test)]
409mod index_to_node_num_success_tests {
410    use crate::{Louds, LoudsIndex, LoudsNodeNum};
411
412    macro_rules! parameterized_tests {
413        ($($name:ident: $value:expr,)*) => {
414        $(
415            #[test]
416            fn $name() {
417                let (in_s, index, expected_node_num) = $value;
418                let louds = Louds::from(in_s);
419                let node_num = louds.index_to_node_num(LoudsIndex(index));
420                assert_eq!(node_num, LoudsNodeNum(expected_node_num));
421            }
422        )*
423        }
424    }
425
426    parameterized_tests! {
427        t1_1: ("10_0", 0, 1),
428
429        t2_1: ("10_10_0", 0, 1),
430        t2_2: ("10_10_0", 2, 2),
431
432        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 0, 1),
433        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 2, 2),
434        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 3, 3),
435        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 4, 4),
436        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 6, 5),
437        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 9, 6),
438        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 10, 7),
439        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 11, 8),
440        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 15, 9),
441        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 17, 10),
442        t3_11: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 18, 11),
443    }
444}
445
446#[cfg(test)]
447mod index_to_node_num_failure_tests {
448    use crate::{Louds, LoudsIndex};
449
450    macro_rules! parameterized_index_not_point_to_node_tests {
451        ($($name:ident: $value:expr,)*) => {
452        $(
453            #[test]
454            #[should_panic]
455            fn $name() {
456                let (in_s, index) = $value;
457                let louds = Louds::from(in_s);
458                let _ = louds.index_to_node_num(LoudsIndex(index));
459            }
460        )*
461        }
462    }
463
464    parameterized_index_not_point_to_node_tests! {
465        t1_1: ("10_0", 1),
466        t1_2: ("10_0", 3),
467
468        t2_1: ("10_10_0", 1),
469        t2_2: ("10_10_0", 3),
470        t2_3: ("10_10_0", 4),
471        t2_4: ("10_10_0", 5),
472
473        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 1),
474        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 5),
475        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 7),
476        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 8),
477        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 12),
478        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 13),
479        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 14),
480        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 16),
481        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 19),
482        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 20),
483        t3_11: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 21),
484        t3_12: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 22),
485        t3_13: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 23),
486        t3_14: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 24),
487    }
488}
489
490#[cfg(test)]
491mod child_to_parent_success_tests {
492    use crate::{Louds, LoudsIndex, LoudsNodeNum};
493
494    macro_rules! parameterized_tests {
495        ($($name:ident: $value:expr,)*) => {
496        $(
497            #[test]
498            fn $name() {
499                let (in_s, index, expected_parent) = $value;
500                let louds = Louds::from(in_s);
501                let parent = louds.child_to_parent(LoudsIndex(index));
502                assert_eq!(parent, LoudsNodeNum(expected_parent));
503            }
504        )*
505        }
506    }
507
508    parameterized_tests! {
509        t2_1: ("10_10_0", 2, 1),
510
511        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 2, 1),
512        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 3, 1),
513        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 4, 1),
514        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 6, 2),
515        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 9, 4),
516        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 10, 4),
517        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 11, 4),
518        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 15, 7),
519        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 17, 8),
520        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 18, 8),
521    }
522}
523
524#[cfg(test)]
525mod child_to_parent_failure_tests {
526    use crate::{Louds, LoudsIndex};
527
528    macro_rules! parameterized_index_not_point_to_node_tests {
529        ($($name:ident: $value:expr,)*) => {
530        $(
531            #[test]
532            #[should_panic]
533            fn $name() {
534                let (in_s, index) = $value;
535                let louds = Louds::from(in_s);
536                let _ = louds.child_to_parent(LoudsIndex(index));
537            }
538        )*
539        }
540    }
541
542    parameterized_index_not_point_to_node_tests! {
543        t1_1: ("10_0", 1),
544        t1_2: ("10_0", 3),
545
546        t2_1: ("10_10_0", 1),
547        t2_2: ("10_10_0", 3),
548        t2_3: ("10_10_0", 4),
549        t2_4: ("10_10_0", 5),
550
551        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 1),
552        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 5),
553        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 7),
554        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 8),
555        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 12),
556        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 13),
557        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 14),
558        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 16),
559        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 19),
560        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 20),
561        t3_11: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 21),
562        t3_12: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 22),
563        t3_13: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 23),
564        t3_14: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 24),
565    }
566
567    macro_rules! parameterized_root_not_have_parent_tests {
568        ($($name:ident: $value:expr,)*) => {
569        $(
570            #[test]
571            #[should_panic]
572            fn $name() {
573                let in_s = $value;
574                let louds = Louds::from(in_s);
575                let _ = louds.child_to_parent(LoudsIndex(0));
576            }
577        )*
578        }
579    }
580
581    parameterized_root_not_have_parent_tests! {
582        t1: "10_0",
583        t2: "10_10_0",
584        t3: "10_1110_10_0_1110_0_0_10_110_0_0_0",
585    }
586}
587
588#[cfg(test)]
589mod parent_to_children_success_tests {
590    use crate::{Louds, LoudsIndex, LoudsNodeNum};
591
592    macro_rules! parameterized_tests {
593        ($($name:ident: $value:expr,)*) => {
594        $(
595            #[test]
596            fn $name() {
597                let (in_s, node_num, expected_children) = $value;
598                let louds = Louds::from(in_s);
599                let children: Vec<_> = louds.parent_to_children(LoudsNodeNum(node_num));
600                assert_eq!(children, expected_children.iter().map(|c| LoudsIndex(*c)).collect::<Vec<LoudsIndex>>());
601            }
602        )*
603        }
604    }
605
606    parameterized_tests! {
607        t1_1: ("10_0", 1, vec!()),
608
609        t2_1: ("10_10_0", 1, vec!(2)),
610        t2_2: ("10_10_0", 2, vec!()),
611
612        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 1, vec!(2, 3, 4)),
613        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 2, vec!(6)),
614        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 3, vec!()),
615        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 4, vec!(9, 10, 11)),
616        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 5, vec!()),
617        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 6, vec!()),
618        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 7, vec!(15)),
619        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 8, vec!(17, 18)),
620        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 9, vec!()),
621        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 10, vec!()),
622        t3_11: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 11, vec!()),
623    }
624}
625
626#[cfg(test)]
627mod child_to_ancestors_success_tests {
628    use crate::{Louds, LoudsNodeNum};
629
630    macro_rules! parameterized_tests {
631        ($($name:ident: $value:expr,)*) => {
632        $(
633            #[test]
634            fn $name() {
635                let (in_s, node_num, expected_children) = $value;
636                let louds = Louds::from(in_s);
637                let children: Vec<_> = louds.child_to_ancestors(LoudsNodeNum(node_num)).collect();
638                assert_eq!(children, expected_children.iter().map(|c| LoudsNodeNum(*c)).collect::<Vec<LoudsNodeNum>>());
639            }
640        )*
641        }
642    }
643
644    parameterized_tests! {
645        t1_1: ("10_0", 1, vec!()),
646
647        t2_1: ("10_10_0", 1, vec!()),
648        t2_2: ("10_10_0", 2, vec!(2)),
649
650        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 1, vec!()),
651        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 2, vec!(2)),
652        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 3, vec!(3)),
653        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 4, vec!(4)),
654        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 5, vec!(5, 2)),
655        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 6, vec!(6, 4)),
656        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 7, vec!(7, 4)),
657        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 8, vec!(8, 4)),
658        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 9, vec!(9, 7, 4)),
659        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 10, vec!(10, 8, 4)),
660        t3_11: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 11, vec!(11, 8, 4)),
661    }
662}
663
664#[cfg(test)]
665mod child_to_ancestors_failure_tests {
666    use crate::{Louds, LoudsIndex};
667
668    macro_rules! parameterized_index_not_point_to_node_tests {
669        ($($name:ident: $value:expr,)*) => {
670        $(
671            #[test]
672            #[should_panic]
673            fn $name() {
674                let (in_s, index) = $value;
675                let louds = Louds::from(in_s);
676                let node = louds.index_to_node_num(LoudsIndex(index));
677                let _ = louds.child_to_ancestors(node);
678            }
679        )*
680        }
681    }
682
683    parameterized_index_not_point_to_node_tests! {
684        t1_1: ("10_0", 1),
685        t1_2: ("10_0", 3),
686
687        t2_1: ("10_10_0", 1),
688        t2_2: ("10_10_0", 3),
689        t2_3: ("10_10_0", 4),
690        t2_4: ("10_10_0", 5),
691
692        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 1),
693        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 5),
694        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 7),
695        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 8),
696        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 12),
697        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 13),
698        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 14),
699        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 16),
700        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 19),
701        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 20),
702        t3_11: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 21),
703        t3_12: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 22),
704        t3_13: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 23),
705        t3_14: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 24),
706    }
707
708    macro_rules! parameterized_root_not_have_parent_tests {
709        ($($name:ident: $value:expr,)*) => {
710        $(
711            #[test]
712            #[should_panic]
713            fn $name() {
714                let in_s = $value;
715                let louds = Louds::from(in_s);
716                let _ = louds.child_to_parent(LoudsIndex(0));
717            }
718        )*
719        }
720    }
721
722    parameterized_root_not_have_parent_tests! {
723        t1: "10_0",
724        t2: "10_10_0",
725        t3: "10_1110_10_0_1110_0_0_10_110_0_0_0",
726    }
727}
728
729#[cfg(test)]
730mod parent_to_children_indices_success_tests {
731    use crate::{Louds, LoudsIndex, LoudsNodeNum};
732
733    macro_rules! parameterized_tests {
734        ($($name:ident: $value:expr,)*) => {
735        $(
736            #[test]
737            fn $name() {
738                let (in_s, node_num, expected_children) = $value;
739                let louds = Louds::from(in_s);
740                let children: Vec<_> = louds.parent_to_children_indices(LoudsNodeNum(node_num)).collect();
741                assert_eq!(children, expected_children.iter().map(|c| LoudsIndex(*c)).collect::<Vec<LoudsIndex>>());
742            }
743        )*
744        }
745    }
746
747    parameterized_tests! {
748        t1_1: ("10_0", 1, vec!()),
749
750        t2_1: ("10_10_0", 1, vec!(2)),
751        t2_2: ("10_10_0", 2, vec!()),
752
753        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 1, vec!(2, 3, 4)),
754        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 2, vec!(6)),
755        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 3, vec!()),
756        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 4, vec!(9, 10, 11)),
757        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 5, vec!()),
758        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 6, vec!()),
759        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 7, vec!(15)),
760        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 8, vec!(17, 18)),
761        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 9, vec!()),
762        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 10, vec!()),
763        t3_11: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 11, vec!()),
764    }
765}
766
767#[cfg(test)]
768mod parent_to_children_indices_rev_success_tests {
769    use crate::{Louds, LoudsIndex, LoudsNodeNum};
770
771    macro_rules! parameterized_tests {
772        ($($name:ident: $value:expr,)*) => {
773        $(
774            #[test]
775            fn $name() {
776                let (in_s, node_num, expected_children) = $value;
777                let louds = Louds::from(in_s);
778                let children: Vec<_> = louds.parent_to_children_indices(LoudsNodeNum(node_num)).rev().collect();
779                assert_eq!(children, expected_children.iter().map(|c| LoudsIndex(*c)).collect::<Vec<LoudsIndex>>());
780            }
781        )*
782        }
783    }
784
785    parameterized_tests! {
786        t1_1: ("10_0", 1, vec!()),
787
788        t2_1: ("10_10_0", 1, vec!(2)),
789        t2_2: ("10_10_0", 2, vec!()),
790
791        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 1, vec!(4, 3, 2)),
792        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 2, vec!(6)),
793        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 3, vec!()),
794        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 4, vec!(11, 10, 9)),
795        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 5, vec!()),
796        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 6, vec!()),
797        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 7, vec!(15)),
798        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 8, vec!(18, 17)),
799        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 9, vec!()),
800        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 10, vec!()),
801        t3_11: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 11, vec!()),
802    }
803}
804
805#[cfg(test)]
806mod parent_to_children_indices_len_success_tests {
807    use crate::{Louds, LoudsNodeNum};
808
809    macro_rules! parameterized_tests {
810        ($($name:ident: $value:expr,)*) => {
811        $(
812            #[test]
813            fn $name() {
814                let (in_s, node_num, expected_size) = $value;
815                let louds = Louds::from(in_s);
816                let mut iter = louds.parent_to_children_indices(LoudsNodeNum(node_num));
817                assert_eq!(iter.len(), expected_size);
818            }
819        )*
820        }
821    }
822
823    parameterized_tests! {
824        t1_1: ("10_0", 1, 0),
825
826        t2_1: ("10_10_0", 1, 1),
827        t2_2: ("10_10_0", 2, 0),
828
829        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 1, 3),
830        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 2, 1),
831        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 3, 0),
832        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 4, 3),
833        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 5, 0),
834        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 6, 0),
835        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 7, 1),
836        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 8, 2),
837        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 9, 0),
838        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 10, 0),
839        t3_11: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 11, 0),
840    }
841}
842
843#[cfg(test)]
844mod parent_to_children_indices_next_back_success_tests {
845    use crate::{Louds, LoudsIndex, LoudsNodeNum};
846
847    macro_rules! parameterized_tests {
848        ($($name:ident: $value:expr,)*) => {
849        $(
850            #[test]
851            fn $name() {
852                let (in_s, node_num, expected_children) = $value;
853                let louds = Louds::from(in_s);
854                let mut front = Vec::new();
855                let mut back = Vec::new();
856                let mut iter = louds.parent_to_children_indices(LoudsNodeNum(node_num));
857                while let Some(x) = iter.next() {
858                    front.push(x);
859                    if let Some(y) = iter.next_back() {
860                        back.push(y);
861                    }
862                }
863                front.extend(back.into_iter().rev());
864                assert_eq!(front, expected_children.iter().map(|c| LoudsIndex(*c)).collect::<Vec<LoudsIndex>>());
865            }
866        )*
867        }
868    }
869
870    parameterized_tests! {
871        t1_1: ("10_0", 1, vec!()),
872
873        t2_1: ("10_10_0", 1, vec!(2)),
874        t2_2: ("10_10_0", 2, vec!()),
875
876        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 1, vec!(2, 3, 4)),
877        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 2, vec!(6)),
878        t3_3: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 3, vec!()),
879        t3_4: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 4, vec!(9, 10, 11)),
880        t3_5: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 5, vec!()),
881        t3_6: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 6, vec!()),
882        t3_7: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 7, vec!(15)),
883        t3_8: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 8, vec!(17, 18)),
884        t3_9: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 9, vec!()),
885        t3_10: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 10, vec!()),
886        t3_11: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 11, vec!()),
887    }
888}
889
890#[cfg(test)]
891mod parent_to_children_failure_tests {
892    use crate::{Louds, LoudsNodeNum};
893
894    macro_rules! parameterized_node_not_found_tests {
895        ($($name:ident: $value:expr,)*) => {
896        $(
897            #[test]
898            #[should_panic]
899            fn $name() {
900                let (in_s, node_num) = $value;
901                let louds = Louds::from(in_s);
902                let _: Vec<_> = louds.parent_to_children(LoudsNodeNum(node_num));
903            }
904        )*
905        }
906    }
907
908    parameterized_node_not_found_tests! {
909        t1_1: ("10_0", 0),
910        t1_2: ("10_0", 2),
911
912        t2_1: ("10_10_0", 0),
913        t2_2: ("10_10_0", 3),
914
915        t3_1: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 0),
916        t3_2: ("10_1110_10_0_1110_0_0_10_110_0_0_0", 12),
917    }
918}
louds_rs/louds/louds_impl.rs

louds_rs/louds/
louds_impl.rs
