Интеллектуальное слияние двух массивов (3-way-kindof)

Question

У меня есть два массива, каждый представляет список рассказов. Два пользователя могут одновременно изменять порядок, добавлять или удалять истории, и я хочу, чтобы эти изменения были объединены.

Пример должен прояснить ситуацию

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)

Результат вышеупомянутого должен быть

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

В случае конфликтов пользователь А должен всегда побеждать.

Я пришел довольно далеко с этим простым подходом. Сначала я удалил все, что сказал мой, что я должен удалить (эта часть кода не показана, это тривиально), затем я перебираю свои, вставляя и перемещая из них то, что нужно (mstories = mine, tstories = их):

     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, 'S moved by them, moffset--');
        }
     }
     result = tstories

Это близко, но это сбивает с толку, когда слишком много историй перемещаются вперед / назад с историями между ними, которых коснулся другой пользователь.

У меня есть расширенная версия, которая проверяет оригинал и умнее - держит 2 смещения и т. Д., - но я чувствую, что это проблема, которая должна иметь а) имя б) идеальное решение, и я не хочу заново его изобрести.

Answer 1

Вот функция, которая выполняет итерацию по предоставленным массивам и позволяет другой функции решить, как объединить с данным индексом. (см. Шаблон стратегии )

// 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;
}

А вот несколько примеров использования ... ваш:

// 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);

... и тот, который создает исключение при конфликте:

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);