poset/
antichain_iterator.rs

1use crate::PartialOrderBehaviour;
2
3/// A struct representing an iterator over the antichains from a set of chains.
4pub struct AntichainIterator<'a, 'b, T, F>
5where
6    F: PartialOrderBehaviour<Element = T>,
7{
8    vectors: Vec<Vec<&'a T>>,
9    indices: Vec<Option<usize>>,
10    finished: bool,
11    p_ord: &'b F,
12}
13
14impl<'a, 'b, T, F> AntichainIterator<'a, 'b, T, F>
15where
16    T: Clone,
17    F: PartialOrderBehaviour<Element = T>,
18{
19    /// Construct a new `AntichainIterator`, given a list of chains and a partial order.
20    pub fn new(vectors: Vec<Vec<&'a T>>, p_ord: &'b F) -> Self {
21        AntichainIterator {
22            indices: vec![None; vectors.len()],
23            vectors,
24            finished: false,
25            p_ord,
26        }
27    }
28
29    fn is_incomparable(&self, combination: &[&T]) -> bool {
30        for (i, item1) in combination.iter().enumerate() {
31            for item2 in combination.iter().skip(i + 1) {
32                if self.p_ord.cp(item1, item2) {
33                    return false;
34                }
35            }
36        }
37        true
38    }
39
40    fn advance_indices(&mut self) -> bool {
41        for i in (0..self.indices.len()).rev() {
42            #[allow(clippy::match_on_vec_items)]
43            match self.indices[i] {
44                None => {
45                    if !self.vectors[i].is_empty() {
46                        self.indices[i] = Some(0);
47                        return true;
48                    }
49                }
50                Some(idx) if idx + 1 < self.vectors[i].len() => {
51                    self.indices[i] = Some(idx + 1);
52                    return true;
53                }
54                _ => {
55                    self.indices[i] = None;
56                }
57            }
58        }
59        false
60    }
61}
62
63impl<'a, 'b, T, F> Iterator for AntichainIterator<'a, 'b, T, F>
64where
65    T: Clone,
66    F: PartialOrderBehaviour<Element = T>,
67{
68    type Item = Vec<T>;
69
70    fn next(&mut self) -> Option<Self::Item> {
71        while !self.finished {
72            let combination: Vec<&T> = self
73                .indices
74                .iter()
75                .enumerate()
76                .filter_map(|(i, &idx)| idx.and_then(|idx| self.vectors[i].get(idx)))
77                .copied()
78                .collect();
79
80            if !self.advance_indices() {
81                self.finished = true;
82            }
83
84            if self.is_incomparable(&combination) {
85                return Some(combination.into_iter().cloned().collect());
86            }
87        }
88
89        None
90    }
91}
poset/antichain_iterator.rs

poset/
antichain_iterator.rs
