Grcov report - cube_iter

1

use oxidd::ldd::LDDFunction;

2

use oxidd::ldd::Value;

3

use streaming_iterator::StreamingIterator;

4

5

/// Owned `(value, down, right)` triple of an LDD node.

6

pub struct Data(pub Value, pub LDDFunction, pub LDDFunction);

7

8

// Returns an iterator over all right siblings of the given LDD.

9

pub fn iter_right(ldd: &LDDFunction) -> IterRight {

10

    IterRight { current: ldd.clone() }

11

12

13

// Returns an iterator over all vectors contained in the given LDD.

14

136713

pub fn iter(ldd: &LDDFunction) -> Iter {

15

136713

    if ldd.node().is_none() {

16

        // Either the empty set or the empty vector, both contain no

17

        // non-trivial vectors to iterate.

18

        Iter {

19

            vector: Vec::new(),

20

            current: Vec::new(),

21

            stack: Vec::new(),

22

            finished: false,

23

24

    } else {

25

136713

        Iter {

26

136713

            vector: Vec::new(),

27

136713

            current: Vec::new(),

28

136713

            stack: vec![ldd.clone()],

29

136713

            finished: false,

30

136713

31

32

136713

33

34

// Returns an iterator over all nodes in the given LDD. Visits each node only if the predicate holds.

35

2002

pub fn iter_nodes<P>(ldd: &LDDFunction, filter: P) -> IterNode<P>

36

2002

where

37

2002

    P: Fn(&LDDFunction) -> bool,

38

39

2002

    let mut stack = Vec::new();

40

41

    // Skip terminals (empty set / empty vector); they have no node data.

42

2002

    if ldd.node().is_some() {

43

2000

        stack.push((ldd.clone(), false));

44

2000

45

46

2002

    IterNode {

47

2002

        stack,

48

2002

        predicate: filter,

49

2002

50

2002

51

52

pub struct IterNode<P>

53

where

54

    P: Fn(&LDDFunction) -> bool,

55

56

    stack: Vec<(LDDFunction, bool)>,

57

    predicate: P,

58

59

60

impl<P> Iterator for IterNode<P>

61

where

62

    P: Fn(&LDDFunction) -> bool,

63

64

    type Item = (LDDFunction, Data);

65

66

451230

    fn next(&mut self) -> Option<Self::Item> {

67

900458

        while let Some((current, visited)) = self.stack.pop() {

68

898456

            let (value, down, right) = current.node().expect("only inner nodes are pushed onto the stack");

69

70

898456

            if visited {

71

449228

                return Some((current, Data(value, down, right)));

72

449228

73

74

            // Next time we can actually process the current node.

75

449228

            self.stack.push((current.clone(), true));

76

77

            // Add unvisited children to stack (skip terminals: empty set / empty vector)

78

449228

            if down.node().is_some() && (self.predicate)(&down) {

79

385228

                self.stack.push((down, false));

80

385228

81

82

449228

            if right.node().is_some() && (self.predicate)(&right) {

83

62000

                self.stack.push((right, false));

84

387228

85

86

87

2002

        None

88

451230

89

90

91

pub struct IterRight {

92

    current: LDDFunction,

93

94

95

impl Iterator for IterRight {

96

    type Item = Data;

97

98

    fn next(&mut self) -> Option<Self::Item> {

99

        match self.current.node() {

100

            // Reached the empty set (or empty vector), so iteration stops.

101

            None => None,

102

            Some((value, down, right)) => {

103

                // Progress to the right LDD.

104

                self.current = right.clone();

105

                Some(Data(value, down, right))

106

107

108

109

110

111

pub struct Iter {

112

    /// Stores the values of the returned vector.

113

    vector: Vec<Value>,

114

    /// Stores the current path in the LDD.

115

    current: Vec<Value>,

116

    /// Stores the stack for the depth-first search (only non 'true' or 'false' nodes)

117

    stack: Vec<LDDFunction>,

118

    /// Indicates whether the iteration is finished.

119

    finished: bool,

120

121

122

impl StreamingIterator for Iter {

123

    type Item = Vec<Value>;

124

125

1547718

    fn advance(&mut self) {

126

        // Find the next vector by going down the chain.

127

        loop {

128

10526655

            if let Some(current) = self.stack.last() {

129

10390143

                let (value, down, _) = current.node().expect("only inner nodes are pushed onto the stack");

130

10390143

                self.vector.push(value);

131

10390143

                if down.is_empty_vector() {

132

1411206

                    self.current.clear();

133

1411206

                    self.current.extend_from_slice(&self.vector);

134

1411206

                    break; // Stop iteration.

135

8978937

                } else {

136

8978937

                    self.stack.push(down);

137

8978937

138

            } else {

139

                // No more elements to iterate.

140

136512

                self.finished = true;

141

136512

                return;

142

143

144

145

        // Go up the chain to find the next right sibling that is not 'false'.

146

10526856

        while let Some(current) = self.stack.pop() {

147

10390143

            self.vector.pop();

148

10390143

            let (_, _, right) = current.node().expect("only inner nodes are pushed onto the stack");

149

150

10390143

            if !right.is_empty() {

151

1274493

                self.stack.push(right); // This is the first right sibling.

152

1274493

                break;

153

9115650

154

155

1547718

156

157

1547718

    fn get(&self) -> Option<&Self::Item> {

158

1547718

        if self.finished { None } else { Some(&self.current) }

159

1547718

160

161

162

#[cfg(test)]

163

mod tests {

164

165

    use super::*;

166

167

    use merc_utilities::random_test;

168

169

    use crate::from_iter;

170

    use crate::random_vector_set;

171

172

    // Test the iterator implementation.

173

    #[test]

174

    #[cfg_attr(miri, ignore)]

175

1

    fn test_random_iter() {

176

100

        random_test(100, |rng| {

177

100

            let manager = oxidd::ldd::new_manager(2048, 1024, 1);

178

179

100

            let set = random_vector_set(rng, 32, 10, 10);

180

100

            let ldd = from_iter(&manager, set.iter());

181

182

100

            assert!(

183

100

                iter(&ldd).count() == set.len(),

184

                "Number of iterations does not match the number of elements in the set."

185

);

186

187

100

            let mut results: Vec<Vec<Value>> = Vec::new();

188

100

            let mut it = iter(&ldd);

189

3300

            while let Some(vector) = it.next() {

190

3200

                assert!(set.contains(vector), "Found element not in the set.");

191

3200

                results.push(vector.to_vec());

192

193

194

100

            results.sort();

195

100

            let original_len = results.len();

196

100

            results.dedup();

197

100

            assert_eq!(original_len, results.len(), "iter returned duplicate vectors.");

198

100

})

199

1

200