Intelligent Merge of two Arrays (3-way-kindof)
- by simon.oberhammer
I have to Arrays, each represents a list of Stories. Two users can concurrently modify the order, add or remove Stories, and I want those changes merged.
An example should make this clearer
Orignial 1,2,3,4,5
UserA (mine) 3,1,2,4,5 (moved story 3 to start)
UserB (theirs) 1,2,3,5,4 (moved story 5 forward)
The result of the above should be
Merge (result) 3,1,2,5,4
In case of conflicts, UserA should always win.
I came pretty far with this simple approach. First i deleted whatever mine says i should deleted (that part of the code is not shown, it's trivial), then I iterate of mine, inserting and moving from theirs what is needed (mstories = mine, tstories = theirs):
var offset = 0;
for (var idx=0;idx<mstories.length;idx++) {
var storyId = mstories[idx];
// new story in theirs
if (mstories.indexOf(tstories[idx]) == -1) {
mstories.splice(idx+1, 0, tstories[idx]);
idx--;
continue;
}
// new story in mine?
if (tstories.indexOf(storyId) == -1) {
tstories.splice(idx+offset, 0, storyId);
offset += 1;
// story moved
} else if (tstories.indexOf(storyId) != idx + offset) {
tstories.splice(tstories.indexOf(storyId), 1);
tstories.splice(idx+offset, 0, storyId);
}
}
It's close, but it gets confused when too many Stories are moved to the front / back with Stories in between, which the other User touched.
I have an extended version which does checks on the original and is smarter - holding 2 offsets, etc - , but I feel like this is a problem that must have a) a name b) a perfect solution and i don't want to re-invent it.
