Grcov report - tree.rs

1

// This file is part of hnefatafl-copenhagen.

2

//

3

// hnefatafl-copenhagen is free software: you can redistribute it and/or modify

4

// it under the terms of the GNU Affero General Public License as published by

5

// the Free Software Foundation, either version 3 of the License, or

6

// (at your option) any later version.

7

//

8

// hnefatafl-copenhagen is distributed in the hope that it will be useful,

9

// but WITHOUT ANY WARRANTY; without even the implied warranty of

10

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

11

// GNU Affero General Public License for more details.

12

//

13

// You should have received a copy of the GNU Affero General Public License

14

// along with this program.  If not, see <https://www.gnu.org/licenses/>.

15

16

use std::collections::VecDeque;

17

18

use crate::{

19

    board::{Board, BoardSize},

20

    game::PreviousBoards,

21

    play::Plays,

22

    role::Role,

23

};

24

25

#[derive(Clone, Debug)]

26

pub struct Tree {

27

    node: usize,

28

    pub next_child: usize,

29

    arena: Vec<Node>,

30

31

32

impl Tree {

33

    pub fn next_child(&mut self) {

34

        self.next_child += 1;

35

36

        if self.next_child >= self.arena[self.node].children.len() {

37

            self.next_child = 0;

38

39

40

41

    pub fn backward(&mut self) {

42

        if let Some(node) = self.arena[self.node].parent {

43

            self.node = node;

44

45

46

        self.next_child = 0;

47

48

49

    pub fn backward_all(&mut self) {

50

        let mut node = self.node;

51

52

        while let Some(node_index) = self.arena[node].parent {

53

            node = node_index;

54

55

56

        self.next_child = 0;

57

        self.node = node;

58

59

60

    pub fn forward(&mut self) {

61

        if !self.arena[self.node].children.is_empty() {

62

            self.node = self.arena[self.node].children[self.next_child];

63

64

65

        self.next_child = 0;

66

67

68

    #[must_use]

69

    pub fn forward_all(&mut self) -> usize {

70

        let mut node = self.node;

71

        let mut count = 0;

72

73

        while !self.arena[node].children.is_empty() {

74

            node = self.arena[node].children[self.next_child];

75

            count += 1;

76

77

78

        self.next_child = 0;

79

        self.node = node;

80

        count

81

82

83

    #[must_use]

84

    pub fn has_children(&self) -> bool {

85

        !self.arena[self.node].children.is_empty()

86

87

88

    pub fn insert(&mut self, board: &Board) {

89

        let index = self.arena.len();

90

        let node = &mut self.arena[self.node];

91

        self.node = index;

92

93

        let old_index = node.index;

94

        node.children.push(index);

95

        let turn = node.turn.opposite();

96

97

        self.arena.push(Node {

98

            index,

99

            board: board.clone(),

100

            turn,

101

            parent: Some(old_index),

102

            children: Vec::new(),

103

});

104

105

106

    #[must_use]

107

    pub fn here(&self) -> Node {

108

        self.arena[self.node].clone()

109

110

111

    #[must_use]

112

    pub fn here_board(&self) -> Board {

113

        self.arena[self.node].board.clone()

114

115

116

    #[must_use]

117

    pub fn new(board_size: BoardSize) -> Self {

118

        Self {

119

            node: 0,

120

            next_child: 0,

121

            arena: vec![Node {

122

                index: 0,

123

                board: Board::new(board_size),

124

                turn: Role::Attacker,

125

                parent: None,

126

                children: Vec::new(),

127

}],

128

129

130

131

    #[must_use]

132

    pub fn previous_boards(&self) -> (Plays, PreviousBoards) {

133

        let mut node = &self.here();

134

        let mut previous_boards = PreviousBoards::new(node.board.size());

135

        let mut boards = VecDeque::new();

136

        let mut plays = Vec::new();

137

138

        previous_boards.0.insert(node.board.clone());

139

        boards.push_front(node.board.clone());

140

141

        while let Some(parent) = node.parent {

142

            node = &self.arena[parent];

143

            previous_boards.0.insert(node.board.clone());

144

            boards.push_front(node.board.clone());

145

146

147

        let boards: Vec<_> = boards.iter().collect();

148

        for windows in boards.windows(2) {

149

            let board_1 = windows[0];

150

            let board_2 = windows[1];

151

152

            let play = board_1.difference(board_2);

153

            plays.push(play);

154

155

156

        let plays = Plays::PlayRecords(plays);

157

        (plays, previous_boards)

158

159

160

161

#[derive(Clone, Debug, PartialEq, Eq)]

162

pub struct Node {

163

    index: usize,

164

    pub board: Board,

165

    pub turn: Role,

166

    parent: Option<usize>,

167

    children: Vec<usize>,

168