sgf_parser/tree.rs
1use crate::{GameNode, SgfError, SgfErrorKind, SgfToken};
2
3/// A game tree, containing it's nodes and possible variations following the last node
4#[derive(Debug, Clone, PartialEq)]
5pub struct GameTree {
6 pub nodes: Vec<GameNode>,
7 pub variations: Vec<GameTree>,
8}
9
10impl Default for GameTree {
11 /// Creates an empty GameTree
12 fn default() -> Self {
13 GameTree {
14 nodes: vec![],
15 variations: vec![],
16 }
17 }
18}
19
20impl GameTree {
21 /// Counts number of nodes in the longest variation
22 pub fn count_max_nodes(&self) -> usize {
23 let count = self.nodes.len();
24 let variation_count = self
25 .variations
26 .iter()
27 .map(|v| v.count_max_nodes())
28 .max()
29 .unwrap_or(0);
30
31 count + variation_count
32 }
33
34 /// Gets a vector of all nodes that contain a `SgfToken::Unknown` token
35 ///
36 /// ```rust
37 /// use sgf_parser::*;
38 ///
39 /// let tree: GameTree = parse("(;B[dc];W[ef]TMP[foobar](;B[aa])(;B[cc];W[ee]))").unwrap();
40 ///
41 /// let unknown_nodes = tree.get_unknown_nodes();
42 /// unknown_nodes.iter().for_each(|node| {
43 /// let unknown_tokens = node.get_unknown_tokens();
44 /// assert_eq!(unknown_tokens.len(), 1);
45 /// if let SgfToken::Unknown((identifier, value)) = unknown_tokens[0] {
46 /// assert_eq!(identifier, "TMP");
47 /// assert_eq!(value, "foobar");
48 /// }
49 /// });
50 ///
51 /// ```
52 pub fn get_unknown_nodes(&self) -> Vec<&GameNode> {
53 let mut unknowns = self
54 .nodes
55 .iter()
56 .filter(|node| {
57 node.tokens
58 .iter()
59 .any(|t| matches!(t, SgfToken::Unknown(_)))
60 })
61 .collect::<Vec<_>>();
62 self.variations.iter().for_each(|variation| {
63 let tmp = variation.get_unknown_nodes();
64 unknowns.extend(tmp);
65 });
66 unknowns
67 }
68
69 /// Gets a vector of all nodes that contain a `SgfToken::Invalid` token
70 ///
71 /// ```rust
72 /// use sgf_parser::*;
73 ///
74 /// let tree: GameTree = parse("(;B[dc];W[foobar];B[aa])(;B[cc];W[ee]))").unwrap();
75 ///
76 /// let invalid_nodes = tree.get_invalid_nodes();
77 /// invalid_nodes.iter().for_each(|node| {
78 /// let invalid_tokens = node.get_invalid_tokens();
79 /// if let SgfToken::Invalid((identifier, value)) = invalid_tokens[0] {
80 /// assert_eq!(identifier, "W");
81 /// assert_eq!(value, "foobar");
82 /// }
83 /// });
84 ///
85 /// ```
86 pub fn get_invalid_nodes(&self) -> Vec<&GameNode> {
87 let mut invalids = self
88 .nodes
89 .iter()
90 .filter(|node| {
91 node.tokens
92 .iter()
93 .any(|t| matches!(t, SgfToken::Invalid(_)))
94 })
95 .collect::<Vec<_>>();
96 self.variations.iter().for_each(|variation| {
97 let tmp = variation.get_invalid_nodes();
98 invalids.extend(tmp);
99 });
100 invalids
101 }
102
103 /// Checks if this GameTree has any variations
104 pub fn has_variations(&self) -> bool {
105 !self.variations.is_empty()
106 }
107
108 /// Counts number of variations in the GameTree
109 pub fn count_variations(&self) -> usize {
110 self.variations.len()
111 }
112
113 /// Get max length of a variation
114 ///
115 /// ```rust
116 /// use sgf_parser::*;
117 ///
118 /// let tree: GameTree = parse("(;B[dc];W[ef](;B[aa])(;B[cc];W[ee]))").unwrap();
119 ///
120 /// assert_eq!(tree.get_varation_length(0).unwrap(), 1);
121 /// assert_eq!(tree.get_varation_length(1).unwrap(), 2);
122 /// ```
123 pub fn get_varation_length(&self, variation: usize) -> Result<usize, SgfError> {
124 if let Some(variation) = self.variations.get(variation) {
125 Ok(variation.count_max_nodes())
126 } else {
127 Err(SgfErrorKind::VariationNotFound.into())
128 }
129 }
130
131 /// Gets an iterator for the GameTree
132 ///
133 /// ```rust
134 /// use sgf_parser::*;
135 ///
136 /// let tree: GameTree = parse("(;B[dc];W[ef](;B[aa])(;B[cc];W[ee]))").unwrap();
137 ///
138 /// let mut iter = tree.iter();
139 ///
140 /// assert_eq!(iter.count_variations(), 2);
141 /// assert!(iter.pick_variation(1).is_ok());
142 ///
143 /// let mut count = 0;
144 /// iter.for_each(|node| {
145 /// assert!(!node.tokens.is_empty());
146 /// count += 1;
147 /// });
148 ///
149 /// assert_eq!(count, tree.count_max_nodes());
150 /// ```
151 pub fn iter(&self) -> GameTreeIterator<'_> {
152 GameTreeIterator::new(self)
153 }
154
155 /// Checks if the tree is valid. `self` is assumed to be a root tree, so it can contain
156 /// root tokens in it's first node.
157 ///
158 /// The only way to invalidate a GameTree is to have a root token in a non-root node.
159 /// The provided `parse` function will not generate invalid a `GameTree`, but manual creation
160 /// or modification of a game tree can create an invalid state
161 ///
162 /// `SgfToken::Invalid` and `SgfToken::Unknown` does not invalidate the tree
163 ///
164 /// ```rust
165 /// use sgf_parser::*;
166 ///
167 /// let valid_tree: GameTree = parse("(;SZ[19]B[dc];W[ef](;B[aa])(;B[cc];W[ee]))").unwrap();
168 /// assert!(valid_tree.is_valid());
169 ///
170 /// let mut invalid_tree: GameTree = valid_tree.clone();
171 /// invalid_tree.variations[1].nodes[0].tokens.push(SgfToken::from_pair("SZ", "19"));
172 ///
173 /// assert!(!invalid_tree.is_valid());
174 /// ```
175 pub fn is_valid(&self) -> bool {
176 let validate_nodes = |nodes: &[GameNode]| {
177 nodes
178 .iter()
179 .all(|node| node.tokens.iter().all(|t| !t.is_root_token()))
180 };
181 if !validate_nodes(&self.nodes[1..]) {
182 return false;
183 }
184
185 let mut trees: Vec<&GameTree> = vec![];
186 trees.extend(self.variations.iter());
187 while let Some(tree) = trees.pop() {
188 if !validate_nodes(&tree.nodes) {
189 return false;
190 }
191 trees.extend(tree.variations.iter());
192 }
193 true
194 }
195}
196
197impl Into<String> for &GameTree {
198 fn into(self) -> String {
199 let nodes = self
200 .nodes
201 .iter()
202 .map(|n| -> String { n.into() })
203 .collect::<String>();
204 let variations = self
205 .variations
206 .iter()
207 .map(|n| -> String { n.into() })
208 .collect::<String>();
209 format!("({}{})", nodes, variations)
210 }
211}
212
213impl Into<String> for GameTree {
214 fn into(self) -> String {
215 (&self).into()
216 }
217}
218
219pub struct GameTreeIterator<'a> {
220 tree: &'a GameTree,
221 index: usize,
222 variation: usize,
223}
224
225impl<'a> GameTreeIterator<'a> {
226 fn new(game_tree: &'a GameTree) -> Self {
227 GameTreeIterator {
228 tree: game_tree,
229 index: 0,
230 variation: 0,
231 }
232 }
233
234 /// Checks if the current `GameTree` has any variations
235 pub fn has_variations(&self) -> bool {
236 self.tree.has_variations()
237 }
238
239 /// Counts number of variations in the current `GameTree`
240 pub fn count_variations(&self) -> usize {
241 self.tree.count_variations()
242 }
243
244 /// Picks a varation in the current `GameTree` to continue with, once the nodes haves been exhausted
245 pub fn pick_variation(&mut self, variation: usize) -> Result<usize, SgfError> {
246 if variation < self.tree.variations.len() {
247 self.variation = variation;
248 Ok(self.variation)
249 } else {
250 Err(SgfErrorKind::VariationNotFound.into())
251 }
252 }
253}
254
255impl<'a> Iterator for GameTreeIterator<'a> {
256 type Item = &'a GameNode;
257
258 fn next(&mut self) -> Option<&'a GameNode> {
259 match self.tree.nodes.get(self.index) {
260 Some(node) => {
261 self.index += 1;
262 Some(&node)
263 }
264 None => {
265 if !self.tree.variations.is_empty() {
266 self.tree = &self.tree.variations[self.variation];
267 self.index = 0;
268 self.variation = 0;
269 self.next()
270 } else {
271 None
272 }
273 }
274 }
275 }
276}