Don't store node in predecessorsedge_only_predecessors

3 files changed, 97 insertions, 6 deletions

diff --git a/src/dijkstra.rs b/src/dijkstra.rs
index 20660e6cc..ffa994dfa 100644
--- a/src/dijkstra.rs
+++ b/src/dijkstra.rs
@@ -4,7 +4,7 @@
 use std::cmp::{Ordering, Reverse};
 
 use crate::{
-    graph::{mark_route, neighbours, Edge, Vertex},
+    graph::{mark_route, neighbours, prev_vertex, Edge, Vertex},
     syntax::Syntax,
 };
 use radix_heap::RadixHeapMap;
@@ -49,7 +49,7 @@ impl<'a> PartialEq for OrdVertex<'a> {
 }
 impl<'a> Eq for OrdVertex<'a> {}
 
-type PredecessorInfo<'a> = (u64, Vertex<'a>, Edge);
+type PredecessorInfo<'a> = (u64, Edge);
 
 fn shortest_path(start: Vertex) -> Vec<(Edge, Vertex)> {
     // We want to visit nodes with the shortest distance first, but
@@ -57,7 +57,7 @@ fn shortest_path(start: Vertex) -> Vec<(Edge, Vertex)> {
     // to flip comparisons.
     let mut heap: RadixHeapMap<Reverse<_>, Vertex> = RadixHeapMap::new();
 
-    heap.push(Reverse(0), start);
+    heap.push(Reverse(0), start.clone());
 
     // TODO: this grows very big. Consider using IDA* to reduce memory
     // usage.
@@ -75,13 +75,13 @@ fn shortest_path(start: Vertex) -> Vec<(Edge, Vertex)> {
                 for (edge, next) in neighbour_buf.iter().flatten() {
                     let distance_to_next = distance + edge.cost();
                     let found_shorter_route = match predecessors.get(next) {
-                        Some((prev_shortest, _, _)) => distance_to_next < *prev_shortest,
+                        Some((prev_shortest, _)) => distance_to_next < *prev_shortest,
                         _ => true,
                     };
 
                     if found_shorter_route {
                         predecessors
-                            .insert(next.clone(), (distance_to_next, current.clone(), *edge));
+                            .insert(next.clone(), (distance_to_next, *edge));
 
                         heap.push(Reverse(distance_to_next), next.clone());
                     }
@@ -102,7 +102,8 @@ fn shortest_path(start: Vertex) -> Vec<(Edge, Vertex)> {
 
     let mut route: Vec<(Edge, Vertex)> = vec![];
     let mut cost = 0;
-    while let Some((_, node, edge)) = predecessors.remove(&current) {
+    while let Some((_, edge)) = predecessors.remove(&current) {
+        let node = prev_vertex(&start, &current, &edge);
         route.push((edge, node.clone()));
         cost += edge.cost();
 
diff --git a/src/graph.rs b/src/graph.rs
index a2e801540..afe3b9e36 100644
--- a/src/graph.rs
+++ b/src/graph.rs
@@ -363,6 +363,88 @@ pub fn neighbours<'a>(v: &Vertex<'a>, buf: &mut [Option<(Edge, Vertex<'a>)>]) {
     }
 }
 
+pub fn prev_vertex<'a>(start: &Vertex<'a>, v: &Vertex<'a>, e: &Edge) -> Vertex<'a> {
+    let lhs_prev = match v.lhs_syntax {
+        Some(lhs_syntax) => lhs_syntax.prev(),
+        None => {
+            // We've reached the end, so find the last syntax node.
+            let mut current = start.lhs_syntax.unwrap();
+            while let Some(node) = current.next() {
+                current = node;
+            }
+            Some(current)
+        }
+    };
+    let rhs_prev = match v.rhs_syntax {
+        Some(rhs_syntax) => rhs_syntax.prev(),
+        None => {
+            // We've reached the end, so find the last syntax node.
+            let mut current = start.rhs_syntax.unwrap();
+            while let Some(node) = current.next() {
+                current = node;
+            }
+            Some(current)
+        }
+    };
+
+    match e {
+        UnchangedNode { .. } => Vertex {
+            lhs_syntax: lhs_prev,
+            rhs_syntax: rhs_prev,
+            lhs_prev_is_novel: false,
+            rhs_prev_is_novel: false,
+        },
+        UnchangedDelimiter { .. } => Vertex {
+            lhs_syntax: v.lhs_syntax.unwrap().parent(),
+            rhs_syntax: v.rhs_syntax.unwrap().parent(),
+            lhs_prev_is_novel: false,
+            rhs_prev_is_novel: false,
+        },
+        ReplacedComment { .. } => Vertex {
+            lhs_syntax: lhs_prev,
+            rhs_syntax: rhs_prev,
+            lhs_prev_is_novel: false,
+            rhs_prev_is_novel: false,
+        },
+        NovelAtomLHS { .. } => Vertex {
+            lhs_syntax: lhs_prev,
+            rhs_syntax: v.rhs_syntax,
+            lhs_prev_is_novel: false,
+            rhs_prev_is_novel: false,
+        },
+        NovelAtomRHS { .. } => Vertex {
+            lhs_syntax: v.lhs_syntax,
+            rhs_syntax: rhs_prev,
+            lhs_prev_is_novel: false,
+            rhs_prev_is_novel: false,
+        },
+        NovelDelimiterLHS { .. } => Vertex {
+            lhs_syntax: v.lhs_syntax.unwrap().parent(),
+            rhs_syntax: v.rhs_syntax,
+            lhs_prev_is_novel: false,
+            rhs_prev_is_novel: false,
+        },
+        NovelDelimiterRHS { .. } => Vertex {
+            lhs_syntax: v.lhs_syntax,
+            rhs_syntax: v.rhs_syntax.unwrap().parent(),
+            lhs_prev_is_novel: false,
+            rhs_prev_is_novel: false,
+        },
+        NovelTreeLHS { .. } => Vertex {
+            lhs_syntax: lhs_prev,
+            rhs_syntax: v.rhs_syntax,
+            lhs_prev_is_novel: false,
+            rhs_prev_is_novel: false,
+        },
+        NovelTreeRHS { .. } => Vertex {
+            lhs_syntax: v.lhs_syntax,
+            rhs_syntax: rhs_prev,
+            lhs_prev_is_novel: false,
+            rhs_prev_is_novel: false,
+        },
+    }
+}
+
 pub fn mark_route(route: &[(Edge, Vertex)]) {
     for (e, v) in route {
         match e {
diff --git a/src/syntax.rs b/src/syntax.rs
index b821f9b4d..96d9dbf41 100644
--- a/src/syntax.rs
+++ b/src/syntax.rs
@@ -234,6 +234,14 @@ impl<'a> Syntax<'a> {
         self.info().next.get()
     }
 
+    pub fn prev(&self) -> Option<&'a Syntax<'a>> {
+        self.info().prev.get()
+    }
+
+    pub fn parent(&self) -> Option<&'a Syntax<'a>> {
+        self.info().parent.get()
+    }
+
     pub fn prev_is_contiguous(&self) -> bool {
         self.info().prev_is_contiguous.get()
     }