1use std::{collections::BTreeSet, error::Error, fmt};
2
3use shakmaty::{Chess, Move};
4
5use crate::domain::Annotation;
6
7#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
9pub struct NodeId(usize);
10
11impl NodeId {
12 #[must_use]
13 pub const fn index(self) -> usize {
14 self.0
15 }
16}
17
18#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
20pub struct CommentFragment(String);
21
22impl CommentFragment {
23 pub fn new(text: impl Into<String>) -> Self {
24 Self(text.into())
25 }
26
27 #[must_use]
28 pub fn as_str(&self) -> &str {
29 &self.0
30 }
31
32 pub fn into_string(self) -> String {
33 self.0
34 }
35}
36
37impl<T: Into<String>> From<T> for CommentFragment {
38 fn from(text: T) -> Self {
39 Self::new(text)
40 }
41}
42
43#[derive(Clone, Debug, Eq, PartialEq)]
45pub struct Node {
46 parent: Option<NodeId>,
47 chess_move: Option<Move>,
48 children: Vec<NodeId>,
49 comments: Vec<CommentFragment>,
50 annotations: BTreeSet<Annotation>,
51}
52
53impl Node {
54 fn root() -> Self {
55 Self {
56 parent: None,
57 chess_move: None,
58 children: Vec::new(),
59 comments: Vec::new(),
60 annotations: BTreeSet::new(),
61 }
62 }
63
64 fn child(parent: NodeId, chess_move: Move) -> Self {
65 Self {
66 parent: Some(parent),
67 chess_move: Some(chess_move),
68 children: Vec::new(),
69 comments: Vec::new(),
70 annotations: BTreeSet::new(),
71 }
72 }
73
74 #[must_use]
75 pub const fn parent(&self) -> Option<NodeId> {
76 self.parent
77 }
78
79 #[must_use]
80 pub const fn chess_move(&self) -> Option<Move> {
81 self.chess_move
82 }
83
84 #[must_use]
85 pub fn children(&self) -> &[NodeId] {
86 &self.children
87 }
88
89 #[must_use]
90 pub fn comments(&self) -> &[CommentFragment] {
91 &self.comments
92 }
93
94 #[must_use]
95 pub const fn annotations(&self) -> &BTreeSet<Annotation> {
96 &self.annotations
97 }
98
99 pub fn add_comment(&mut self, comment: impl Into<CommentFragment>) -> bool {
100 let comment = comment.into();
101 if self.comments.contains(&comment) {
102 false
103 } else {
104 self.comments.push(comment);
105 true
106 }
107 }
108
109 pub fn add_annotation(&mut self, annotation: Annotation) -> bool {
110 self.annotations.insert(annotation)
111 }
112}
113
114#[derive(Clone, Debug, Eq, PartialEq)]
116pub struct MoveTree {
117 starting_position: Chess,
118 nodes: Vec<Node>,
119 root: NodeId,
120}
121
122impl Default for MoveTree {
123 fn default() -> Self {
124 Self::new()
125 }
126}
127
128impl MoveTree {
129 #[must_use]
130 pub fn new() -> Self {
131 Self::from_position(Chess::default())
132 }
133
134 #[must_use]
135 pub fn from_position(starting_position: Chess) -> Self {
136 Self {
137 starting_position,
138 nodes: vec![Node::root()],
139 root: NodeId(0),
140 }
141 }
142
143 #[must_use]
144 pub const fn starting_position(&self) -> &Chess {
145 &self.starting_position
146 }
147
148 #[must_use]
149 pub const fn root(&self) -> NodeId {
150 self.root
151 }
152
153 #[must_use]
154 pub const fn len(&self) -> usize {
155 self.nodes.len()
156 }
157
158 #[must_use]
159 pub const fn is_empty(&self) -> bool {
160 false
161 }
162
163 #[must_use]
164 pub fn node(&self, id: NodeId) -> Option<&Node> {
165 self.nodes.get(id.0)
166 }
167
168 pub fn node_mut(&mut self, id: NodeId) -> Option<&mut Node> {
169 self.nodes.get_mut(id.0)
170 }
171
172 pub fn add_child(&mut self, parent: NodeId, chess_move: Move) -> Result<NodeId, TreeError> {
173 if self.node(parent).is_none() {
174 return Err(TreeError::UnknownNode(parent));
175 }
176
177 let child = NodeId(self.nodes.len());
178 self.nodes.push(Node::child(parent, chess_move));
179 self.nodes[parent.0].children.push(child);
180 Ok(child)
181 }
182
183 pub fn promote_child(&mut self, parent: NodeId, child: NodeId) -> Result<(), TreeError> {
185 let node = self
186 .nodes
187 .get_mut(parent.0)
188 .ok_or(TreeError::UnknownNode(parent))?;
189 let index = node
190 .children
191 .iter()
192 .position(|candidate| *candidate == child)
193 .ok_or(TreeError::NotAChild { parent, child })?;
194 node.children[..=index].rotate_right(1);
195 Ok(())
196 }
197
198 pub fn traverse(&self) -> impl Iterator<Item = NodeId> + '_ {
200 let mut stack = vec![self.root];
201 std::iter::from_fn(move || {
202 let id = stack.pop()?;
203 stack.extend(self.nodes[id.0].children.iter().rev().copied());
204 Some(id)
205 })
206 }
207
208 pub fn validate(&self) -> Result<(), TreeError> {
210 let root = self
211 .nodes
212 .get(self.root.0)
213 .ok_or(TreeError::UnknownNode(self.root))?;
214 if root.parent.is_some() || root.chess_move.is_some() {
215 return Err(TreeError::InvalidRoot);
216 }
217
218 let mut seen = vec![false; self.nodes.len()];
219 let mut stack = vec![self.root];
220 while let Some(parent) = stack.pop() {
221 if seen[parent.0] {
222 return Err(TreeError::DuplicateOrCyclicNode(parent));
223 }
224 seen[parent.0] = true;
225
226 for &child in &self.nodes[parent.0].children {
227 let child_node = self
228 .nodes
229 .get(child.0)
230 .ok_or(TreeError::UnknownNode(child))?;
231 if child_node.parent != Some(parent) {
232 return Err(TreeError::ParentMismatch {
233 child,
234 expected: parent,
235 actual: child_node.parent,
236 });
237 }
238 if child_node.chess_move.is_none() {
239 return Err(TreeError::MissingMove(child));
240 }
241 stack.push(child);
242 }
243 }
244
245 if let Some(index) = seen.iter().position(|visited| !visited) {
246 return Err(TreeError::UnreachableNode(NodeId(index)));
247 }
248 Ok(())
249 }
250}
251
252#[derive(Clone, Debug, Eq, PartialEq)]
253pub enum TreeError {
254 UnknownNode(NodeId),
255 NotAChild {
256 parent: NodeId,
257 child: NodeId,
258 },
259 InvalidRoot,
260 DuplicateOrCyclicNode(NodeId),
261 ParentMismatch {
262 child: NodeId,
263 expected: NodeId,
264 actual: Option<NodeId>,
265 },
266 MissingMove(NodeId),
267 UnreachableNode(NodeId),
268 PlyCommentOutOfBounds {
269 line_number: usize,
270 ply: u32,
271 available_plies: u32,
272 },
273}
274
275impl fmt::Display for TreeError {
276 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
277 match self {
278 Self::UnknownNode(node) => write!(formatter, "unknown node {}", node.index()),
279 Self::NotAChild { parent, child } => write!(
280 formatter,
281 "node {} is not a child of node {}",
282 child.index(),
283 parent.index()
284 ),
285 Self::InvalidRoot => formatter.write_str("root node has a parent or move"),
286 Self::DuplicateOrCyclicNode(node) => write!(
287 formatter,
288 "node {} is referenced more than once or forms a cycle",
289 node.index()
290 ),
291 Self::ParentMismatch {
292 child,
293 expected,
294 actual,
295 } => write!(
296 formatter,
297 "node {} has parent {actual:?}, expected node {}",
298 child.index(),
299 expected.index()
300 ),
301 Self::MissingMove(node) => {
302 write!(formatter, "non-root node {} has no move", node.index())
303 }
304 Self::UnreachableNode(node) => {
305 write!(formatter, "node {} is unreachable", node.index())
306 }
307 Self::PlyCommentOutOfBounds {
308 line_number,
309 ply,
310 available_plies,
311 } => write!(
312 formatter,
313 "line {line_number} targets ply {ply}, but the mainline has {available_plies} plies"
314 ),
315 }
316 }
317}
318
319impl Error for TreeError {}
320
321#[cfg(test)]
322mod tests {
323 use shakmaty::{Chess, Move, Position, Role, Square};
324
325 use crate::domain::Annotation;
326
327 use super::{CommentFragment, MoveTree, NodeId, TreeError};
328
329 fn normal(from: Square, to: Square, role: Role) -> Move {
330 Move::Normal {
331 role,
332 from,
333 capture: None,
334 to,
335 promotion: None,
336 }
337 }
338
339 #[test]
340 fn tree_retains_its_explicit_starting_position() {
341 let after_e4 = Chess::default()
342 .play(normal(Square::E2, Square::E4, Role::Pawn))
343 .unwrap();
344 let tree = MoveTree::from_position(after_e4.clone());
345
346 assert_eq!(tree.starting_position(), &after_e4);
347 }
348
349 #[test]
350 fn insertion_and_traversal_are_deterministic() {
351 let mut tree = MoveTree::new();
352 let root = tree.root();
353 let e4 = tree
354 .add_child(root, normal(Square::E2, Square::E4, Role::Pawn))
355 .unwrap();
356 let d4 = tree
357 .add_child(root, normal(Square::D2, Square::D4, Role::Pawn))
358 .unwrap();
359 let e5 = tree
360 .add_child(e4, normal(Square::E7, Square::E5, Role::Pawn))
361 .unwrap();
362
363 assert_eq!(tree.traverse().collect::<Vec<_>>(), [root, e4, e5, d4]);
364 assert_eq!(tree.node(e5).unwrap().parent(), Some(e4));
365 assert_eq!(tree.validate(), Ok(()));
366 }
367
368 #[test]
369 fn promotion_changes_only_explicit_child_order() {
370 let mut tree = MoveTree::new();
371 let root = tree.root();
372 let e4 = tree
373 .add_child(root, normal(Square::E2, Square::E4, Role::Pawn))
374 .unwrap();
375 let d4 = tree
376 .add_child(root, normal(Square::D2, Square::D4, Role::Pawn))
377 .unwrap();
378
379 tree.promote_child(root, d4).unwrap();
380 assert_eq!(tree.node(root).unwrap().children(), [d4, e4]);
381 assert_eq!(tree.validate(), Ok(()));
382 }
383
384 #[test]
385 fn promotion_rejects_non_children() {
386 let mut tree = MoveTree::new();
387 let root = tree.root();
388 let e4 = tree
389 .add_child(root, normal(Square::E2, Square::E4, Role::Pawn))
390 .unwrap();
391 let e5 = tree
392 .add_child(e4, normal(Square::E7, Square::E5, Role::Pawn))
393 .unwrap();
394
395 assert_eq!(
396 tree.promote_child(root, e5),
397 Err(TreeError::NotAChild {
398 parent: root,
399 child: e5
400 })
401 );
402 }
403
404 #[test]
405 fn comments_deduplicate_without_losing_order() {
406 let mut tree = MoveTree::new();
407 let root = tree.root();
408 let node = tree.node_mut(root).unwrap();
409
410 assert!(node.add_comment("first"));
411 assert!(node.add_comment("second"));
412 assert!(!node.add_comment("first"));
413 assert_eq!(
414 node.comments(),
415 [
416 CommentFragment::new("first"),
417 CommentFragment::new("second")
418 ]
419 );
420 }
421
422 #[test]
423 fn annotations_are_typed_and_sorted() {
424 let mut tree = MoveTree::new();
425 let node = tree.node_mut(tree.root()).unwrap();
426 node.add_annotation(Annotation::Dubious);
427 node.add_annotation(Annotation::Good);
428 node.add_annotation(Annotation::Good);
429
430 assert_eq!(
431 node.annotations().iter().copied().collect::<Vec<_>>(),
432 [Annotation::Good, Annotation::Dubious]
433 );
434 }
435
436 #[test]
437 fn unknown_parent_is_rejected_without_mutating_the_arena() {
438 let mut tree = MoveTree::new();
439 let result = tree.add_child(NodeId(99), normal(Square::E2, Square::E4, Role::Pawn));
440
441 assert_eq!(result, Err(TreeError::UnknownNode(NodeId(99))));
442 assert_eq!(tree.len(), 1);
443 assert_eq!(tree.validate(), Ok(()));
444 }
445
446 #[test]
447 fn validation_detects_a_broken_parent_link() {
448 let mut tree = MoveTree::new();
449 let root = tree.root();
450 let child = tree
451 .add_child(root, normal(Square::E2, Square::E4, Role::Pawn))
452 .unwrap();
453 tree.nodes[child.index()].parent = Some(child);
454
455 assert_eq!(
456 tree.validate(),
457 Err(TreeError::ParentMismatch {
458 child,
459 expected: root,
460 actual: Some(child),
461 })
462 );
463 }
464}