Intelligent combining of two arrays (3-way-kindof)

Question

I have two arrays, each of which represents a list of Stories. Two users can simultaneously reorder, add or remove Stories, and I want these changes to be merged.

An example should make this clearer.

Original 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 above should be

 Merge (result) 3,1,2,5,4 

In case of conflict, UserA should always win.

I came quite far with this simple approach. First I deleted everything that says I should delete (this part of the code is not shown, it is trivial), then I iterate over mine, inserting and moving from them what is needed (mstories = mine, tstories = theirs):

  for (var idx=0;idx<mstories.length;idx++) { var storyId = mstories[idx]; // new story by theirs if (tstories[idx] !== undefined && mstories.indexOf(tstories[idx]) == -1) { mstories.splice(idx+1, 0, tstories[idx]); idx--; continue; } // new story by mine if (tstories.indexOf(storyId) == -1 && ostories.indexOf(storyId) == -1) { tstories.splice(idx+offset, 0, storyId); offset += 1; // story moved by me } else if ((tstories.indexOf(storyId) != idx + offset) && ostories.indexOf(storyId) != idx) { tstories.splice(tstories.indexOf(storyId), 1); tstories.splice(idx+offset, 0, storyId); // story moved by them } else if (tstories.indexOf(storyId) != idx + offset) { mstories.splice(mstories.indexOf(storyId), 1); mstories.splice(idx+offset, 0, storyId); mdebug(storyId, moved by them, moffset--'); } } result = tstories 

It closes, but it gets confused when too many Stories move front / back with Stories between them that another user has touched.

I have an extended version that checks the original and smarter - holds 2 offsets, etc., but I feel that this is a problem that should have a) the name b) the perfect solution, and I do not want to reinvent it.

Answer 1

Here's a function that iterates over the provided arrays and allows another function to decide how to join at a given index. (see Strategy Template )

 // params: // original, a, b: equally dimensioned arrays // mergeStrategy : function with params _original, _a, _b that // accept the values inhabiting the arrays // original, a, and b resp. // // - Is called for each array index. // - Should return one of the arguments passed. // - May throw "conflict" exception. // returns merged array function merge(original, a, b, mergeStrategy){ var result=[]; for ( var i =0; i< a.length; i++ ) { try { result.push( mergeStrategy( original[i], a[i], b[i] )); } catch (e if e=="conflict") { throw ("conflict at index "+i); } } return result; } 

And here are some usage examples ... yours:

 // example: always choose a over b function aWins( original, a, b ) { return ( original == a ) ? b : a; } // returns [3,1,2,5,4] merge( [1,2,3,4,5], [3,1,2,4,5], [1,2,3,5,4], aWins); 

... and one that throws an exception in a conflict:

 function complain( original, a, b ) { if (original == a ) return b; if (original == b ) return a; if ( a == b ) return a; throw ("conflict"); } // throws "conflict at index 3" merge( [1,2,3,4,5], [3,1,2,1,5], [1,2,3,5,4], complain);