Differences

This shows you the differences between two versions of the page.

--- projects:proof:populatedifftree [2023/02/27 15:50] – created Owen Mellema
+++ projects:proof:populatedifftree [2023/02/27 19:22] (current) – Owen Mellema
@@ Line 1: / Line 1: @@
-# Populate Diff Tree
+====== Populate Diff Tree ======
 This algorithm is the powerhouse of project proof, and is one of the most complicated and hairy things I've ever worked on.
@@ Line 5: / Line 5: @@
 The purpose of this algorithm is to add information to a tree about what will change in another tree. This includes information about creation and deletion of nodes, as well as movement.
-We are given two trees - an **original** tree and a **modified** tree. In the image below, the left tree is original, and the right tree is modified.
+We are given two trees - an **original** tree and a **modified** tree. The original tree will have the new information added. In the image below, the left tree is original, and the right tree is modified.
 {{:projects:proof:origin.png?400|}}
@@ Line 12: / Line 12: @@
 (Note that I haven't drawn the links between the trees, so as to prevent clutter. Instead, nodes with the same letter are considered to be linked.)
+===== Creation and Deletion - Level One=====
+We proceed level by level, then parent by parent, from the top of the tree.
+{{:projects:proof:level1.png?400|}}
+In this very simple example tree (no moving up or down levels!) we can ignore parent and root nodes, to make it a bit easier to tell what's going on. You might notice that there are links between nodes. This is because the children of a particular node are stored as a doubly linked list in memory, for reasons that will become relevant later.
+{{:projects:proof:just_level_1_better.png?400|}}
+==== Scanning for misalignments ====
+The first thing we do is **scan for misalignments**. A misalignment is when the order of matched nodes differs. For instance, suppose that in our original tree we had "A->x->B->y->C", and in our modified tree we had "A->w->k->B->s->C". In this instance, the order of matched nodes is "ABC" in both trees, so there is no misalignment. However, if the modified tree had "A->w->k->C->s->B", in the original we would have "ABC" and in the modified we'd have "ACB", so there would be a misalignment.
+Checking for a misalignment is easy. We start with a matched node in the original tree.
+{{:projects:proof:mac1a.png?400|}}
+Then, we scan forward to the next matched node.
+{{:projects:proof:mac1b.png?400|}}
+We repeat the process for the match of the starting node in the modified tree
+{{:projects:proof:mac1c.png?400|}}
+{{:projects:proof:mac1d.png?400|}}
+{{:projects:proof:mac1e.png?400|}}
+Finally, we check if these two nodes match. They do, so there is no mismatch here.
+{{:projects:proof:mac1f.png?400|}}
+We do this for each pair of matched nodes. On this level, there are no mismatched nodes, but there will be in the next level, under node F.
+==== Scanning for, and handling, creation ====
+Next, we check if we need to add new nodes. We start in the modified tree, scanning for any nodes that are unmatched.
+{{:projects:proof:creation1a.png?400|}}
+B2 matches with B1, so we are fine.
+{{:projects:proof:creation1b.png?400|}}
+C2 does not have a match!
+{{:projects:proof:creation1c.png?400|}}
+So, we create a new node, C1. But where to put it? Since this is a doubly linked list, we need a node before and a node after. This is pretty simple. We begin by scanning backwards from C2 to the previous matched node.
+{{:projects:proof:creation1d.png?400|}}
+{{:projects:proof:creation1e.png?400|}}
+We move to the node that matches this node, B1. This will be the previous node, before C1.
+{{:projects:proof:creation1f.png?400|}}
+To find the node that comes after, we just scan forward to the next node, which is D1.
+{{:projects:proof:creation1g.png?400|}}
+With that, we have all the information we need to add the new node to the original.
+{{:projects:proof:creation1h.png?400|}}
+There are no more unmatched nodes in the modified tree.
+==== Scanning for, and handling, deletion ====
+Handling deletions is really simple.
+We start at the first node in the original tree, and scan for unmatched nodes.
+{{:projects:proof:deletion1a.png?400|}}
+{{:projects:proof:deletion1b.png?400|}}
+{{:projects:proof:deletion1c.png?400|}}
+{{:projects:proof:deletion1d.png?400|}}
+When we find one, we mark it as deleted.
+{{:projects:proof:deletion1e.png?400|}}
+That's literally it - we don't need to actually delete any nodes, we just need a node telling us that we deleted a node.