java_diff_utils_rs/algorithm/myers/
path_node.rs

1use std::fmt::{self, Display};
2
3// Point in the Myers edit graph.
4#[derive(Debug, Clone, Copy)]
5pub struct PathNode {
6    pub i: usize,
7    pub j: isize, // -1 reserved for bootstrap node
8    pub is_snake: bool,
9    pub is_bootstrap: bool,
10    pub prev: Option<usize>,
11}
12
13impl PathNode {
14    pub fn new(
15        i: usize,
16        j: isize,
17        is_snake: bool,
18        is_bootstrap: bool,
19        prev: Option<usize>,
20    ) -> Self {
21        Self {
22            i,
23            j,
24            is_snake,
25            is_bootstrap,
26            prev,
27        }
28    }
29
30    pub fn fmt_path(arena: &[PathNode], start_idx: usize) -> String {
31        format!("{}", PathFormatter { arena, start_idx })
32    }
33
34    /// Exact port of Java's `PathNode.previousSnake()`:
35    ///   if (isBootstrap()) return null;
36    ///   if (!isSnake() && prev != null) return prev.previousSnake();
37    ///   return this;
38    ///
39    /// Called on a node (by index) the same way Java calls `somePrev.previousSnake()`.
40    pub fn previous_snake(arena: &[PathNode], idx: usize) -> Option<usize> {
41        let node = arena[idx];
42        if node.is_bootstrap {
43            return None;
44        }
45        if !node.is_snake {
46            if let Some(p) = node.prev {
47                return PathNode::previous_snake(arena, p);
48            }
49        }
50        Some(idx)
51    }
52}
53
54pub struct PathFormatter<'a> {
55    arena: &'a [PathNode],
56    start_idx: usize,
57}
58
59impl Display for PathFormatter<'_> {
60    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
61        write!(f, "[")?;
62        let mut curr = Some(self.start_idx);
63        let mut first = true;
64
65        while let Some(idx) = curr {
66            let Some(node) = self.arena.get(idx) else {
67                break;
68            };
69
70            if !first {
71                write!(f, ", ")?;
72            }
73            write!(f, "({},{})", node.i, node.j)?;
74            first = false;
75
76            if node.is_bootstrap {
77                break;
78            }
79            curr = node.prev;
80        }
81
82        write!(f, "]")
83    }
84}
java_diff_utils_rs/algorithm/myers/path_node.rs

java_diff_utils_rs/algorithm/myers/
path_node.rs
