tree_automata/
utils.rs

1pub struct Combinations<'a, T, F, I, E: Clone> where F: Fn(&'a T) -> I, I: 'a + Iterator<Item=E> {
2    sources: &'a [T],
3    f: F,
4    iterators: Vec<I>,
5    elements: Vec<E>,
6    visited: bool
7}
8
9impl<'a, T, F, I, E: Clone> Combinations<'a, T, F, I, E> where F: Fn(&'a T) -> I, I: 'a + Iterator<Item=E> {
10    pub fn new(sources: &'a [T], f: F) -> Combinations<'a, T, F, I, E> {
11        let iterators = if sources.is_empty() {
12            Vec::new()
13        } else {
14            vec![(f)(&sources[0])]
15        };
16        Combinations {
17            sources: sources,
18            f: f,
19            iterators: iterators,
20            elements: Vec::new(),
21            visited: false
22        }
23    }
24}
25
26impl<'a, T, F, I, E: Clone> Iterator for Combinations<'a, T, F, I, E> where F: Fn(&'a T) -> I, I: 'a + Iterator<Item=E> {
27    type Item = Vec<E>;
28
29    fn next(&mut self) -> Option<Self::Item> {
30        if self.sources.is_empty() {
31            if self.visited {
32                None
33            } else {
34                self.visited = true;
35                Some(Vec::new())
36            }
37        } else {
38            while self.elements.len() < self.sources.len() {
39                // let i = self.elements.len();
40                // if i <= self.iterators.len() {
41                //     self.iterators.push((self.f)(&self.sources[i]))
42                // }
43
44                match self.iterators.last_mut().unwrap().next() {
45                    Some(e) => {
46                        self.elements.push(e);
47                        let j = self.elements.len();
48                        if j < self.sources.len() {
49                            self.iterators.push((self.f)(&self.sources[j]))
50                        }
51                    },
52                    None => {
53                        match self.elements.pop() {
54                            Some(_) => {
55                                self.iterators.pop();
56                            },
57                            None => return None
58                        }
59                    }
60                }
61            }
62
63            let item = self.elements.clone();
64            self.elements.pop();
65            Some(item)
66        }
67    }
68}
69
70pub fn combinations<'a, T, F, I, E: Clone>(sources: &'a [T], f: F) -> Combinations<'a, T, F, I, E> where F: Fn(&'a T) -> I, I: 'a + Iterator<Item=E> {
71    Combinations::new(sources, f)
72}
73
74pub struct CombinationsOption<'a, T, F, I, E: Clone> where F: Fn(&'a T) -> I, I: 'a + Iterator<Item=E> {
75    sources: &'a [T],
76    f: F,
77    iterators: Vec<(I, bool)>,
78    elements: Vec<Option<E>>,
79    visited: bool,
80    weak: bool
81}
82
83impl<'a, T, F, I, E: Clone> CombinationsOption<'a, T, F, I, E> where F: Fn(&'a T) -> I, I: 'a + Iterator<Item=E> {
84    pub fn new(sources: &'a [T], f: F, weak: bool) -> CombinationsOption<'a, T, F, I, E> {
85        let iterators = if sources.is_empty() {
86            Vec::new()
87        } else {
88            vec![((f)(&sources[0]), false)]
89        };
90        CombinationsOption {
91            sources: sources,
92            f: f,
93            iterators: iterators,
94            elements: Vec::new(),
95            visited: false,
96            weak: weak
97        }
98    }
99}
100
101impl<'a, T, F, I, E: Clone> Iterator for CombinationsOption<'a, T, F, I, E> where F: Fn(&'a T) -> I, I: 'a + Iterator<Item=E> {
102    type Item = Vec<Option<E>>;
103
104    fn next(&mut self) -> Option<Self::Item> {
105        if self.sources.is_empty() {
106            if self.visited {
107                None
108            } else {
109                self.visited = true;
110                Some(Vec::new())
111            }
112        } else {
113            while self.elements.len() < self.sources.len() {
114                // assert!(self.iterators.len() <= self.sources.len());
115                // for (_, visited) in self.iterators.iter() {
116                //     print!("{}, ", visited);
117                // }
118                // print!(" for {} elements/ {}\n", self.elements.len(), self.sources.len());
119
120                // let i = self.elements.len();
121                // if self.iterators.len() <= i {
122                //     println!("push iterator");
123                //     self.iterators.push(((self.f)(&self.sources[i]), false))
124                // }
125
126                match self.iterators.last_mut() {
127                    Some((ref mut it, ref mut visited)) => {
128                        match it.next() {
129                            Some(e) => {
130                                self.elements.push(Some(e));
131                                if !self.weak {
132                                    *visited = true;
133                                }
134                                let j = self.elements.len();
135                                if j < self.sources.len() {
136                                    self.iterators.push(((self.f)(&self.sources[j]), false))
137                                }
138                            },
139                            None => {
140                                if *visited {
141                                    // println!("visited");
142                                    match self.elements.pop() {
143                                        Some(_) => {
144                                            self.iterators.pop();
145                                        },
146                                        None => {
147                                            // println!("NONE");
148                                            return None
149                                        }
150                                    }
151                                } else {
152                                    // println!("marked");
153                                    self.elements.push(None);
154                                    *visited = true;
155                                    let j = self.elements.len();
156                                    if j < self.sources.len() {
157                                        self.iterators.push(((self.f)(&self.sources[j]), false))
158                                    }
159                                }
160                            }
161                        };
162                    },
163                    None => unreachable!()
164                }
165            }
166
167            let item = self.elements.clone();
168            self.elements.pop();
169            Some(item)
170        }
171    }
172}
173
174pub fn combinations_option<'a, T, F, I, E: Clone>(sources: &'a [T], f: F) -> CombinationsOption<'a, T, F, I, E> where F: Fn(&'a T) -> I, I: 'a + Iterator<Item=E> {
175    CombinationsOption::new(sources, f, false)
176}
177
178pub fn combinations_weak_option<'a, T, F, I, E: Clone>(sources: &'a [T], f: F) -> CombinationsOption<'a, T, F, I, E> where F: Fn(&'a T) -> I, I: 'a + Iterator<Item=E> {
179    CombinationsOption::new(sources, f, true)
180}
181
182/// A multiplexer iterator that thats iterates on multiple iterators, alternating between iterators
183/// at each iteration.
184pub struct Mux<T: Iterator> {
185    /// The iterators to iterate on.
186    iterators: Vec<T>,
187
188    /// The index of the next iterator to call `next` on.
189    index: usize
190}
191
192impl<T: Iterator> Mux<T> {
193    pub fn new(iterators: Vec<T>) -> Mux<T> {
194        Mux {
195            iterators: iterators,
196            index: 0
197        }
198    }
199}
200
201impl<T: Iterator> Iterator for Mux<T> {
202    type Item = T::Item;
203
204    fn next(&mut self) -> Option<T::Item> {
205        if self.iterators.is_empty() {
206            None
207        } else {
208            let mut i = self.index;
209            loop {
210                if let Some(item) = self.iterators[i].next() {
211                    self.index = (i + 1)%self.iterators.len();
212                    return Some(item)
213                } else {
214                    i = (i + 1)%self.iterators.len();
215                    if i == self.index {
216                        // we rounded back on the same index without finding any item.
217                        return None
218                    }
219                }
220            }
221        }
222    }
223}
tree_automata/utils.rs

tree_automata/
utils.rs
