darklua_core/process/utils/
permutator.rs

1#[derive(Debug)]
2pub struct Permutator<I> {
3    original_producer: I,
4    current_producers: Vec<I>,
5    root: String,
6}
7
8impl<I: Iterator + Clone> Permutator<I> {
9    pub fn new(producer: I) -> Self {
10        Self {
11            original_producer: producer.clone(),
12            current_producers: vec![producer],
13            root: String::new(),
14        }
15    }
16
17    fn new_producer(&self) -> I {
18        self.original_producer.clone()
19    }
20}
21
22impl<I: Iterator<Item = char> + Clone> Iterator for Permutator<I> {
23    type Item = String;
24
25    fn next(&mut self) -> Option<String> {
26        let next_char = self
27            .current_producers
28            .last_mut()
29            .and_then(|producer| producer.next());
30
31        if let Some(value) = next_char {
32            let mut string = self.root.clone();
33            string.push(value);
34            Some(string)
35        } else {
36            let mut count_pop = 1;
37            self.current_producers.pop();
38
39            while let Some(previous_producer) = self.current_producers.last_mut() {
40                self.root.pop();
41                if let Some(next_root_char) = previous_producer.next() {
42                    self.root.push(next_root_char);
43                    count_pop -= 1;
44                    break;
45                } else {
46                    self.current_producers.pop();
47                    count_pop += 1;
48                }
49            }
50
51            for _ in 0..count_pop {
52                let mut new_producer = self.new_producer();
53                self.root.push(new_producer.next().unwrap());
54                self.current_producers.push(new_producer);
55            }
56
57            self.current_producers.push(self.original_producer.clone());
58
59            self.next()
60        }
61    }
62}
63
64#[cfg(test)]
65mod test {
66    use super::*;
67    use std::convert::TryInto;
68
69    #[test]
70    fn produce_all_permutations_with_single_char() {
71        let mut permutate = Permutator::new("ab".chars());
72
73        assert_eq!(permutate.next().unwrap(), "a");
74        assert_eq!(permutate.next().unwrap(), "b");
75    }
76
77    #[test]
78    fn produce_all_permutations_with_two_chars() {
79        let mut permutate = Permutator::new("ab".chars());
80
81        assert_eq!(permutate.next().unwrap(), "a");
82        assert_eq!(permutate.next().unwrap(), "b");
83        assert_eq!(permutate.next().unwrap(), "aa");
84        assert_eq!(permutate.next().unwrap(), "ab");
85        assert_eq!(permutate.next().unwrap(), "ba");
86        assert_eq!(permutate.next().unwrap(), "bb");
87    }
88
89    #[test]
90    fn produce_all_permutations_with_three_chars() {
91        let mut permutate = Permutator::new("ab".chars());
92
93        for _ in 0..(2 + 2) ^ 2 {
94            permutate.next();
95        }
96
97        assert_eq!(permutate.next().unwrap(), "aaa");
98        assert_eq!(permutate.next().unwrap(), "aab");
99        assert_eq!(permutate.next().unwrap(), "aba");
100        assert_eq!(permutate.next().unwrap(), "abb");
101        assert_eq!(permutate.next().unwrap(), "baa");
102        assert_eq!(permutate.next().unwrap(), "bab");
103        assert_eq!(permutate.next().unwrap(), "bba");
104        assert_eq!(permutate.next().unwrap(), "bbb");
105    }
106
107    #[test]
108    fn produce_only_first_char_permutations() {
109        let char_set = "01";
110        let set_length = char_set.len();
111
112        let mut permutate = Permutator::new(char_set.chars());
113
114        for length in 1..9 {
115            assert_eq!(permutate.next().unwrap(), char_set[0..1].repeat(length));
116
117            for _ in 0..set_length.pow(length.try_into().unwrap()) - 1 {
118                assert!(permutate.next().is_some());
119            }
120        }
121    }
122}
darklua_core/process/utils/permutator.rs

darklua_core/process/utils/
permutator.rs
