Grcov report - strategy.rs

1

use std::collections::HashMap;

2

use std::fmt;

3

4

use crate::PG;

5

use crate::Player;

6

use crate::Set;

7

use crate::VertexIndex;

8

9

/// Keeps track of a strategy for a player in a parity game.

10

///

11

/// # Details

12

///

13

/// A strategy is a partial function from vertices owned by a player to one of

14

/// their successors.

15

pub struct Strategy {

16

    mapping: HashMap<VertexIndex, VertexIndex>,

17

18

19

impl Strategy {

20

    /// Creates a new, empty strategy.

21

2521

    pub fn new() -> Self {

22

2521

        Self {

23

2521

            mapping: HashMap::new(),

24

2521

25

2521

26

27

    /// Adds a mapping from `from` to `to` in the strategy.

28

13009

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

29

13009

        self.mapping.insert(from, to);

30

13009

31

32

    /// Gets the target vertex for the given source vertex, if it is defined.

33

145908

    pub fn get(&self, from: VertexIndex) -> Option<&VertexIndex> {

34

145908

        self.mapping.get(&from)

35

145908

36

37

    /// Computes the union of two strategies, assumes that they do not overlap.

38

1204

    pub fn union(mut self, other: Strategy) -> Strategy {

39

        // Add all mappings from the extension strategy to the base strategy

40

4818

        for (&from, &to) in other.iter() {

41

4818

            debug_assert!(!self.mapping.contains_key(&from), "Cannot combine strategies with overlapping domains");

42

4818

            self.set(from, to);

43

44

45

1204

        self

46

1204

47

48

    /// Extends the strategy with an arbitrary strategy for the given `player` on the given `vertices`.

49

913

    pub fn extend_arbitrary<G: PG>(mut self, pg: &G, vertices: &Set, subgame: &Set, player: Player) -> Strategy {

50

11917

        for vertex in vertices.iter_ones().map(VertexIndex::new) {

51

11917

            if pg.owner(vertex) == player && self.get(vertex).is_none() {

52

                // Add an arbitrary mapping for this vertex, we can just take the first outgoing edge.

53

2488

                if let Some(edge) = pg.outgoing_edges(vertex).find(|edge| subgame[*edge.to()]) {

54

2024

                    self.set(vertex, edge.to());

55

2024

56

9893

57

58

59

913

        self

60

913

61

62

    /// Returns an iterator over all (from, to) pairs in the strategy.

63

1204

    pub fn iter(&self) -> impl Iterator<Item = (&VertexIndex, &VertexIndex)> {

64

1204

        self.mapping.iter()

65

1204

66

67

    /// Checks that the strategy is only defined for the vertices owned by the

68

    /// given player. Furthermore, ensure that the strategy is defined for all

69

    /// vertices won in the solution for the given player

70

200

    pub fn check_consistent<G: PG>(&self, pg: &G, solution: &Set, player: Player) {

71

20000

        for vertex in pg.iter_vertices() {

72

20000

            if solution[*vertex] && pg.owner(vertex) == player && self.get(vertex).is_none() {

73

                panic!(

74

                    "Strategy is not defined for vertex {:?} owned by {:?}, but is in the winning set.",

75

                    vertex,

76

                    pg.owner(vertex),

77

);

78

20000

79

80

20000

            if self.get(vertex).is_some() && pg.owner(vertex) != player {

81

                panic!(

82

                    "Strategy is defined for vertex {:?} owned by {:?}, but it should be owned by {:?}.",

83

                    vertex,

84

                    pg.owner(vertex),

85

                    player

86

);

87

20000

88

89

200

90

91

92

impl Default for Strategy {

93

    fn default() -> Self {

94

        Self::new()

95

96

97

98

impl fmt::Debug for Strategy {

99

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

100

        writeln!(f, "Strategy {{")?;

101

        for (from, to) in &self.mapping {

102

            writeln!(f, "  v{} -> v{}", from, to)?;

103

104

        writeln!(f, "}}")

105

106