add patch and diff logic for recipes

2 files changed, 98 insertions, 0 deletions

diff --git a/recipe.go b/recipe.go
new file mode 100644
index 0000000..92385d9
--- /dev/null
+++ b/recipe.go
@@ -0,0 +1,74 @@
+package main
+
+import "reflect"
+
+type Recipe []Chunk
+
+type RecipeDel int
+
+type RecipeIns struct {
+	Idx   int
+	Value []Chunk
+}
+
+type RecipePatch struct {
+	Del []RecipeDel
+	Ins []RecipeIns
+}
+
+func patchRecipe(source Recipe, patch RecipePatch) (target Recipe) {
+	// apply Del part from patch to source into temp
+	size := len(source) - len(patch.Del)
+	temp := make(Recipe, size)
+	fill := 0
+	prev := 0
+	for _, del := range patch.Del {
+		di := int(del)
+		copy(temp[fill:], source[prev:di])
+		fill += di - prev
+		prev = di + 1
+	}
+	copy(temp[fill:], source[prev:])
+	// apply Ins part from patch to temp into target
+	for _, ins := range patch.Ins {
+		size += len(ins.Value)
+	}
+	target = make(Recipe, size)
+	fill = 0
+	prev = 0
+	tpos := 0
+	for _, ins := range patch.Ins {
+		offset := ins.Idx - prev
+		copy(target[fill:], temp[tpos:tpos+offset])
+		fill += offset
+		tpos += offset
+		copy(target[fill:], ins.Value)
+		fill += len(ins.Value)
+		prev = ins.Idx + len(ins.Value)
+	}
+	return
+}
+
+func diffRecipe(source Recipe, target Recipe) (patch RecipePatch) {
+	var si, ti int
+	var found bool
+	for ; si < len(source); si++ {
+		for i := ti; i < len(target); i++ {
+			found = reflect.DeepEqual(target[i], source[si])
+			if found {
+				if i != ti {
+					patch.Ins = append(patch.Ins, RecipeIns{ti, target[ti:i]})
+				}
+				ti = i + 1
+				break
+			}
+		}
+		if !found {
+			patch.Del = append(patch.Del, RecipeDel(si))
+		}
+	}
+	if ti < len(target) {
+		patch.Ins = append(patch.Ins, RecipeIns{ti, target[ti:]})
+	}
+	return
+}
diff --git a/recipe_test.go b/recipe_test.go
new file mode 100644
index 0000000..f5c9b29
--- /dev/null
+++ b/recipe_test.go
@@ -0,0 +1,24 @@
+package main
+
+import "testing"
+
+func TestRecipe(t *testing.T) {
+	c1 := &StoredChunk{Id: &ChunkId{0, 1}}
+	c2 := &StoredChunk{Id: &ChunkId{0, 2}}
+	c3 := &StoredChunk{Id: &ChunkId{0, 3}}
+	c4 := &StoredChunk{Id: &ChunkId{0, 4}}
+	c5 := &StoredChunk{Id: &ChunkId{0, 5}}
+	c6 := &StoredChunk{Id: &ChunkId{0, 6}}
+	c7 := &StoredChunk{Id: &ChunkId{0, 7}}
+	source := Recipe{c1, c2, c3, c4}
+	target := Recipe{c2, c5, c3, c6, c4, c7}
+	patch := diffRecipe(source, target)
+	assertSame(t, []RecipeDel{0}, patch.Del, "Patch del part")
+	assertSame(t, []RecipeIns{
+		{1, []Chunk{c5}},
+		{3, []Chunk{c6}},
+		{5, []Chunk{c7}},
+	}, patch.Ins, "Patch ins part")
+	actual := patchRecipe(source, patch)
+	assertSame(t, target, actual, "Target obtained from patch application")
+}