Grcov report - builder.rs

1

#![forbid(unsafe_code)]

2

3

use oxidd::BooleanFunction;

4

use oxidd::bdd::BDDFunction;

5

use oxidd::bdd::BDDManagerRef;

6

7

use crate::ParityGame;

8

use crate::Player;

9

use crate::Priority;

10

use crate::VariabilityParityGame;

11

use crate::VertexIndex;

12

13

/// A builder for parity games that accepts edges one by one and can remove

14

/// duplicates.

15

pub struct ParityGameBuilder {

16

    /// The edges of the parity game.

17

    edges: Vec<(VertexIndex, VertexIndex)>,

18

19

    /// The owner of each vertex, indexed by vertex index.

20

    owners: Vec<Player>,

21

22

    /// The priority of each vertex, indexed by vertex index.

23

    priorities: Vec<Priority>,

24

25

    /// The initial vertex of the game.

26

    initial_vertex: VertexIndex,

27

28

    /// The number of vertices discovered so far.

29

    num_of_vertices: usize,

30

31

32

impl ParityGameBuilder {

33

    /// Initializes a new empty builder with the given initial vertex.

34

1500

    pub fn new(initial_vertex: VertexIndex) -> Self {

35

1500

        Self::with_capacity(initial_vertex, 0)

36

1500

37

38

    /// Initializes the builder with pre-allocated capacity for edges.

39

1601

    pub fn with_capacity(initial_vertex: VertexIndex, num_of_edges: usize) -> Self {

40

1601

        let num_of_vertices = initial_vertex.value() + 1;

41

1601

        Self {

42

1601

            edges: Vec::with_capacity(num_of_edges),

43

1601

            owners: vec![Player::Even; num_of_vertices],

44

1601

            priorities: vec![Priority::new(0); num_of_vertices],

45

1601

            initial_vertex,

46

1601

            num_of_vertices,

47

1601

48

1601

49

50

    /// Adds a vertex to the builder with its owner and priority.

51

76103

    pub fn add_vertex(&mut self, vertex: VertexIndex, owner: Player, priority: Priority) {

52

76103

        let num_of_vertices = vertex.value() + 1;

53

76103

        self.ensure_vertex_capacity(num_of_vertices);

54

76103

        self.owners[vertex.value()] = owner;

55

76103

        self.priorities[vertex.value()] = priority;

56

76103

        self.num_of_vertices = self.num_of_vertices.max(num_of_vertices);

57

76103

58

59

    /// Adds an edge to the builder.

60

108154

    pub fn add_edge(&mut self, from: VertexIndex, to: VertexIndex) {

61

108154

        self.edges.push((from, to));

62

108154

        let num_of_vertices = self.num_of_vertices.max(from.value() + 1).max(to.value() + 1);

63

108154

        self.ensure_vertex_capacity(num_of_vertices);

64

108154

        self.num_of_vertices = num_of_vertices;

65

108154

66

67

    /// Returns the number of edges added to the builder.

68

    pub fn num_of_edges(&self) -> usize {

69

        self.edges.len()

70

71

72

    /// Returns the number of vertices that the builder currently found.

73

    pub fn num_of_vertices(&self) -> usize {

74

        self.num_of_vertices

75

76

77

    /// Finalizes the builder and returns the constructed parity game.

78

1601

    pub fn finish(mut self, make_total: bool, remove_duplicates: bool) -> ParityGame {

79

1601

        if remove_duplicates {

80

1601

            self.remove_duplicates();

81

1601

82

83

1601

        self.ensure_vertex_capacity(self.num_of_vertices);

84

85

        // Build the parity game using the from_edges method

86

1601

        let edges = self.edges.clone();

87

3202

        ParityGame::from_edges(self.initial_vertex, self.owners, self.priorities, make_total, || {

88

3202

            edges.iter().cloned()

89

3202

})

90

1601

91

92

    /// Ensures that the owners and priorities vectors have enough capacity for the given number of vertices.

93

185858

    fn ensure_vertex_capacity(&mut self, num_of_vertices: usize) {

94

185858

        if self.owners.len() < num_of_vertices {

95

66601

            self.owners.resize(num_of_vertices, Player::Even);

96

119257

97

185858

        if self.priorities.len() < num_of_vertices {

98

66601

            self.priorities.resize(num_of_vertices, Priority::new(0));

99

119257

100

185858

101

102

    /// Removes duplicated edges from the added edges.

103

1601

    fn remove_duplicates(&mut self) {

104

1601

        self.edges.sort();

105

1601

        self.edges.dedup();

106

1601

107

108

109

/// A builder for variability parity games that accepts edges with BDD configurations

110

/// one by one and can remove duplicates.

111

pub struct VariabilityParityGameBuilder {

112

    /// The edges of the variability parity game with their configurations.

113

    edges: Vec<(VertexIndex, oxidd::bdd::BDDFunction, VertexIndex)>,

114

115

    /// The owner of each vertex, indexed by vertex index.

116

    owners: Vec<Player>,

117

118

    /// The priority of each vertex, indexed by vertex index.

119

    priorities: Vec<Priority>,

120

121

    /// The initial vertex of the game.

122

    initial_vertex: VertexIndex,

123

124

    /// The number of vertices discovered so far.

125

    num_of_vertices: usize,

126

127

128

impl VariabilityParityGameBuilder {

129

    /// Initializes a new empty builder with the given initial vertex.

130

    pub fn new(initial_vertex: VertexIndex) -> Self {

131

        Self::with_capacity(initial_vertex, 0)

132

133

134

    /// Initializes the builder with pre-allocated capacity for edges.

135

302

    pub fn with_capacity(initial_vertex: VertexIndex, num_of_edges: usize) -> Self {

136

302

        let num_of_vertices = initial_vertex.value() + 1;

137

302

        Self {

138

302

            edges: Vec::with_capacity(num_of_edges),

139

302

            owners: vec![Player::Even; num_of_vertices],

140

302

            priorities: vec![Priority::new(0); num_of_vertices],

141

302

            initial_vertex,

142

302

            num_of_vertices,

143

302

144

302

145

146

    /// Adds a vertex to the builder with its owner and priority.

147

8627

    pub fn add_vertex(&mut self, vertex: VertexIndex, owner: Player, priority: Priority) {

148

8627

        let num_of_vertices = vertex.value() + 1;

149

8627

        self.ensure_vertex_capacity(num_of_vertices);

150

8627

        self.owners[vertex.value()] = owner;

151

8627

        self.priorities[vertex.value()] = priority;

152

8627

        self.num_of_vertices = self.num_of_vertices.max(num_of_vertices);

153

8627

154

155

    /// Adds an edge to the builder with its configuration.

156

16553

    pub fn add_edge(&mut self, from: VertexIndex, configuration: oxidd::bdd::BDDFunction, to: VertexIndex) {

157

16553

        self.edges.push((from, configuration, to));

158

16553

        let num_of_vertices = self.num_of_vertices.max(from.value() + 1).max(to.value() + 1);

159

16553

        self.ensure_vertex_capacity(num_of_vertices);

160

16553

        self.num_of_vertices = num_of_vertices;

161

16553

162

163

    /// Returns the number of edges added to the builder.

164

    pub fn num_of_edges(&self) -> usize {

165

        self.edges.len()

166

167

168

    /// Returns the number of vertices that the builder currently found.

169

601

    pub fn num_of_vertices(&self) -> usize {

170

601

        self.num_of_vertices

171

601

172

173

    /// Consumes the builder and returns the constructed variability parity game.

174

302

    pub fn finish(

175

302

        mut self,

176

302

        manager_ref: &BDDManagerRef,

177

302

        configuration: BDDFunction,

178

302

        variables: Vec<BDDFunction>,

179

302

        remove_duplicates: bool,

180

302

    ) -> VariabilityParityGame {

181

302

        if remove_duplicates {

182

1

            self.remove_duplicates();

183

301

184

185

302

        self.ensure_vertex_capacity(self.num_of_vertices);

186

187

        // Build the variability parity game using the from_edges method

188

302

        let edges = self.edges.clone();

189

302

        VariabilityParityGame::from_edges(

190

302

            manager_ref,

191

302

            self.initial_vertex,

192

302

            self.owners,

193

302

            self.priorities,

194

302

            configuration,

195

302

            variables,

196

604

            || edges.iter().cloned(),

197

198

302

199

200

    /// Ensures that the owners and priorities vectors have enough capacity for the given number of vertices.

201

25482

    fn ensure_vertex_capacity(&mut self, num_of_vertices: usize) {

202

25482

        if self.owners.len() < num_of_vertices {

203

5324

            self.owners.resize(num_of_vertices, Player::Even);

204

20158

205

25482

        if self.priorities.len() < num_of_vertices {

206

5324

            self.priorities.resize(num_of_vertices, Priority::new(0));

207

20158

208

25482

209

210

    /// Removes duplicated edges from the added edges.

211

1

    fn remove_duplicates(&mut self) {

212

77638

        self.edges.sort_by_key(|(from, _, to)| (*from, *to));

213

214

1

        let mut merged: Vec<(VertexIndex, BDDFunction, VertexIndex)> = Vec::with_capacity(self.edges.len());

215

4409

        for (from, configuration, to) in self.edges.drain(..) {

216

4409

            if let Some((last_from, last_configuration, last_to)) = merged.last_mut()

217

4408

                && *last_from == from

218

1407

                && *last_to == to

219

220

1

                *last_configuration = last_configuration

221

1

                    .or(&configuration)

222

1

                    .expect("Duplicate edges should have compatible BDD managers");

223

1

                continue;

224

4408

225

226

4408

            merged.push((from, configuration, to));

227

228

229

1

        self.edges = merged;

230

1

231