Array diffing + DOM manipulation problem

problem.md

• We have two arrays of objects.
• Each object has an associated DOM element, .el.
• The two arrays are sharing some objects, but not all of them;
• The two arrays have different orders for the shared objects.
• The first array's associated DOM elements are already inserted in the DOM, reflecting the owner objects' order in the array.

Now we want to replace the first array with the second one, with the following requirements:

• Update the DOM so that the inserted elements reflect the order of objects in the second array.
• Reuse any existing objects and DOM elements.
• Incur the least amount of DOM manipulation possible.

solve.js

var arr1 = [{id:0}, {id:1}, {id:2}, {id:3}, {id:4}, {id:5}],
    arr2 = [arr1[0], arr1[1], {id:6}, arr1[2], {id:7}, arr1[3], {id:8}]

function move (oldArr, newArr) {
    
    var i, l, item,
        OLD_REUSED = [],
        NEW_REUSED = [],
        NEW_CREATED = []

    for (i = 0, l = newArr.length; i < l; i++) {
        newArr[i].$newFinalIndex = i
    }

    for (i = 0, l = oldArr.length; i < l; i++) {
        item = oldArr[i]
        if (item.$newFinalIndex != null) { // reused
            item.$oldReuseIndex = OLD_REUSED.length
            OLD_REUSED.push(item)
        } else {
            item.$destroyed = true
        }
    }

    for (i = 0, l = newArr.length; i < l; i++) {
        item = newArr[i]
        if (item.$oldReuseIndex != null) { // reused
            item.$newReuseIndex = NEW_REUSED.length
            NEW_REUSED.push(item)
        } else {
            NEW_CREATED.push(item)
        }
    }

    // console.log(OLD_REUSED.map(id))
    // console.log(NEW_REUSED.map(id))
    // console.log(NEW_CREATED.map(id))

    var oldNext, newNext, DOM = OLD_REUSED.slice(), moves = 0
    for (i = 0, l = OLD_REUSED.length; i < l; i++) {
        item = OLD_REUSED[i]
        oldNext = OLD_REUSED[i + 1]
        newNext = NEW_REUSED[item.$newReuseIndex + 1]
        if (newNext && oldNext !== newNext) {
            moves++
            if (!oldNext) {
                // I was the last one. move myself to before newNext
                insertBefore(item, newNext)
            } else {
                // move newNext to after me
                insertBefore(newNext, oldNext)
            }
        }
        strip(item)
        log(i)
    }

    for (i = 0, l = NEW_CREATED.length; i < l; i++) {
        item = NEW_CREATED[i]
        DOM.splice(item.$newFinalIndex, 0, item)
        strip(item)
    }

    log()
    console.log('total moves: ' + moves)

    function log (i) {
        if (i) {
            console.log('step ' + i)
        } else {
            console.log('final')
        }
        console.log(DOM)
        console.log()
    }

    // simulate DOM insertBefore
    // ignore the indexOf perf here
    function insertBefore (a, b) {
        DOM.splice(DOM.indexOf(a), 1)
        DOM.splice(DOM.indexOf(b), 0, a)
    }

}

move(arr1, arr2)

function strip (item) {
    delete item.$newFinalIndex
    delete item.$newReuseIndex
    delete item.$oldReuseIndex
}

function id (item) {
    return item.id
}