From 2887d66a939b3b8d7e84d9c71c0a86d5132b5e54 Mon Sep 17 00:00:00 2001 From: n-peugnet Date: Tue, 21 Sep 2021 16:29:44 +0200 Subject: change recipe into a generic slice patch/diff package --- slice/slice.go | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++++ slice/slice_test.go | 21 +++++++++++++++ 2 files changed, 95 insertions(+) create mode 100644 slice/slice.go create mode 100644 slice/slice_test.go (limited to 'slice') diff --git a/slice/slice.go b/slice/slice.go new file mode 100644 index 0000000..15be5dd --- /dev/null +++ b/slice/slice.go @@ -0,0 +1,74 @@ +package slice + +import "reflect" + +type Slice []interface{} + +type SliceDel int + +type SliceIns struct { + Idx int + Value []interface{} +} + +type SlicePatch struct { + Del []SliceDel + Ins []SliceIns +} + +func PatchSlice(source Slice, patch SlicePatch) (target Slice) { + // apply Del part from patch to source into temp + size := len(source) - len(patch.Del) + temp := make(Slice, 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(Slice, 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 DiffSlice(source Slice, target Slice) (patch SlicePatch) { + 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, SliceIns{ti, target[ti:i]}) + } + ti = i + 1 + break + } + } + if !found { + patch.Del = append(patch.Del, SliceDel(si)) + } + } + if ti < len(target) { + patch.Ins = append(patch.Ins, SliceIns{ti, target[ti:]}) + } + return +} diff --git a/slice/slice_test.go b/slice/slice_test.go new file mode 100644 index 0000000..b73946e --- /dev/null +++ b/slice/slice_test.go @@ -0,0 +1,21 @@ +package slice + +import ( + "testing" + + "github.com/n-peugnet/dna-backup/testutils" +) + +func TestPatch(t *testing.T) { + source := Slice{1, 2, 3, 4} + target := Slice{2, 5, 3, 6, 4, 7, 8} + patch := DiffSlice(source, target) + testutils.AssertSame(t, []SliceDel{0}, patch.Del, "Patch del part") + testutils.AssertSame(t, []SliceIns{ + {1, Slice{5}}, + {3, Slice{6}}, + {5, Slice{7, 8}}, + }, patch.Ins, "Patch ins part") + actual := PatchSlice(source, patch) + testutils.AssertSame(t, target, actual, "Target obtained from patch application") +} -- cgit v1.2.3