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

// SPDX-License-Identifier: AGPL-3.0-or-later

17

// SPDX-FileCopyrightText: 2025 David Campbell <david@hnefatafl.org>

18

19

use std::collections::VecDeque;

20

21

use crate::{

22

    board::{Board, BoardSize},

23

    game::PreviousBoards,

24

    play::Plays,

25

    role::Role,

26

};

27

28

#[derive(Clone, Debug)]

29

pub struct Tree {

30

    node: usize,

31

    pub next_child: usize,

32

    arena: Vec<Node>,

33

34

35

impl Tree {

36

    pub fn next_child(&mut self) {

37

        self.next_child += 1;

38

39

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

40

            self.next_child = 0;

41

42

43

44

    pub fn backward(&mut self) {

45

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

46

            self.node = node;

47

48

49

        self.next_child = 0;

50

51

52

    pub fn backward_all(&mut self) {

53

        let mut node = self.node;

54

55

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

56

            node = node_index;

57

58

59

        self.next_child = 0;

60

        self.node = node;

61

62

63

    pub fn forward(&mut self) {

64

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

65

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

66

67

68

        self.next_child = 0;

69

70

71

    #[must_use]

72

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

73

        let mut node = self.node;

74

        let mut count = 0;

75

76

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

77

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

78

            count += 1;

79

80

81

        self.next_child = 0;

82

        self.node = node;

83

        count

84

85

86

    #[must_use]

87

    pub fn has_children(&self) -> bool {

88

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

89

90

91

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

92

        let index = self.arena.len();

93

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

94

        self.node = index;

95

96

        let old_index = node.index;

97

        node.children.push(index);

98

        let turn = node.turn.opposite();

99

100

        self.arena.push(Node {

101

            index,

102

            board: board.clone(),

103

            turn,

104

            parent: Some(old_index),

105

            children: Vec::new(),

106

});

107

108

109

    #[must_use]

110

    pub fn here(&self) -> Node {

111

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

112

113

114

    #[must_use]

115

    pub fn here_board(&self) -> Board {

116

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

117

118

119

    #[must_use]

120

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

121

        Self {

122

            node: 0,

123

            next_child: 0,

124

            arena: vec![Node {

125

                index: 0,

126

                board: Board::new(board_size),

127

                turn: Role::Attacker,

128

                parent: None,

129

                children: Vec::new(),

130

}],

131

132

133

134

    #[must_use]

135

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

136

        let mut node = &self.here();

137

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

138

        let mut boards = VecDeque::new();

139

140

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

141

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

142

143

        while let Some(parent) = node.parent {

144

            node = &self.arena[parent];

145

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

146

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

147

148

149

        let plays = boards

150

            .iter()

151

            .collect::<Vec<_>>()

152

            .as_slice()

153

            .array_windows()

154

            .map(|[board_1, board_2]| (*board_1).difference(board_2))

155

            .collect();

156

157

        let plays = Plays::PlayRecords(plays);

158

        (plays, previous_boards)

159

160

161

162

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

163

pub struct Node {

164

    index: usize,

165

    pub board: Board,

166

    pub turn: Role,

167

    parent: Option<usize>,

168

    children: Vec<usize>,

169