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

1200

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

35

1200

        Self::with_capacity(initial_vertex, 0)

36

1200

37

38

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

39

1301

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

40

1301

        let num_of_vertices = initial_vertex.value() + 1;

41

1301

        Self {

42

1301

            edges: Vec::with_capacity(num_of_edges),

43

1301

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

44

1301

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

45

1301

            initial_vertex,

46

1301

            num_of_vertices,

47

1301

48

1301

49

50

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

51

56103

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

52

56103

        let num_of_vertices = vertex.value() + 1;

53

56103

        self.ensure_vertex_capacity(num_of_vertices);

54

56103

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

55

56103

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

56

56103

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

57

56103

58

59

    /// Adds an edge to the builder.

60

82319

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

61

82319

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

62

82319

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

63

82319

        self.ensure_vertex_capacity(num_of_vertices);

64

82319

        self.num_of_vertices = num_of_vertices;

65

82319

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

1301

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

79

1301

        if remove_duplicates {

80

1301

            self.remove_duplicates();

81

1301

82

83

1301

        self.ensure_vertex_capacity(self.num_of_vertices);

84

85

        // Build the parity game using the from_edges method

86

1301

        let edges = self.edges.clone();

87

1301

        ParityGame::from_edges(

88

1301

            self.initial_vertex,

89

1301

            self.owners,

90

1301

            self.priorities,

91

1301

            make_total,

92

2602

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

93

94

1301

95

96

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

97

139723

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

98

139723

        if self.owners.len() < num_of_vertices {

99

46901

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

100

92822

101

139723

        if self.priorities.len() < num_of_vertices {

102

46901

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

103

92822

104

139723

105

106

    /// Removes duplicated edges from the added edges.

107

1301

    fn remove_duplicates(&mut self) {

108

1301

        self.edges.sort();

109

1301

        self.edges.dedup();

110

1301

111

112

113

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

114

/// one by one and can remove duplicates.

115

pub struct VariabilityParityGameBuilder {

116

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

117

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

118

119

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

120

    owners: Vec<Player>,

121

122

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

123

    priorities: Vec<Priority>,

124

125

    /// The initial vertex of the game.

126

    initial_vertex: VertexIndex,

127

128

    /// The number of vertices discovered so far.

129

    num_of_vertices: usize,

130

131

132

impl VariabilityParityGameBuilder {

133

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

134

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

135

        Self::with_capacity(initial_vertex, 0)

136

137

138

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

139

302

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

140

302

        let num_of_vertices = initial_vertex.value() + 1;

141

302

        Self {

142

302

            edges: Vec::with_capacity(num_of_edges),

143

302

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

144

302

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

145

302

            initial_vertex,

146

302

            num_of_vertices,

147

302

148

302

149

150

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

151

8627

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

152

8627

        let num_of_vertices = vertex.value() + 1;

153

8627

        self.ensure_vertex_capacity(num_of_vertices);

154

8627

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

155

8627

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

156

8627

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

157

8627

158

159

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

160

16504

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

161

16504

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

162

16504

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

163

16504

        self.ensure_vertex_capacity(num_of_vertices);

164

16504

        self.num_of_vertices = num_of_vertices;

165

16504

166

167

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

168

    pub fn num_of_edges(&self) -> usize {

169

        self.edges.len()

170

171

172

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

173

601

    pub fn num_of_vertices(&self) -> usize {

174

601

        self.num_of_vertices

175

601

176

177

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

178

302

    pub fn finish(

179

302

        mut self,

180

302

        manager_ref: &BDDManagerRef,

181

302

        configuration: BDDFunction,

182

302

        variables: Vec<BDDFunction>,

183

302

        remove_duplicates: bool,

184

302

    ) -> VariabilityParityGame {

185

302

        if remove_duplicates {

186

1

            self.remove_duplicates();

187

301

188

189

302

        self.ensure_vertex_capacity(self.num_of_vertices);

190

191

        // Build the variability parity game using the from_edges method

192

302

        let edges = self.edges.clone();

193

302

        VariabilityParityGame::from_edges(

194

302

            manager_ref,

195

302

            self.initial_vertex,

196

302

            self.owners,

197

302

            self.priorities,

198

302

            configuration,

199

302

            variables,

200

604

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

201

202

302

203

204

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

205

25433

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

206

25433

        if self.owners.len() < num_of_vertices {

207

5324

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

208

20109

209

25433

        if self.priorities.len() < num_of_vertices {

210

5324

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

211

20109

212

25433

213

214

    /// Removes duplicated edges from the added edges.

215

1

    fn remove_duplicates(&mut self) {

216

77638

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

217

218

1

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

219

4409

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

220

4409

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

221

4408

                && *last_from == from

222

1407

                && *last_to == to

223

224

1

                *last_configuration = last_configuration

225

1

                    .or(&configuration)

226

1

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

227

1

                continue;

228

4408

229

230

4408

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

231

232

233

1

        self.edges = merged;

234

1

235