fast array diff

array_diff.js

var tests = [
    [[], [1, 2, 3], [1, 2, 3], [], 0, 0],
    [[1, 2, 3], [], [], [1, 2, 3], 0, 0],
    [[1, 2, 3], [1, 2, 3], [], [], 3, 0],
    [[1, 2, 3, 4], [1, 2, 3], [], [4], 3, 0],
    [[1, 2, 3], [1, 2, 3, 4], [4], [], 3, 0],
    [[1, 2, 3], [1, 3], [], [2], 3, 1],
    [[1, 3], [1, 2, 3], [2], [], 3, 0],
    [[1, 2, 3], [3, 2, 1], [], [], 6, 0],
    [[1, 2, 3], [3, 2], [], [1], 5, 2],
    [[1, 2], [3, 2, 1], [3], [], 5, 0],
    [[3, 2, 1], [1, 2], [], [3], 5, 2],
    [[1, 2, 3], [1, 3, 2], [], [], 4, 0],
    [[1, 2], [1, 3, 2], [3], [], 3, 0],
    [[1, 2, 3], [1, 3], [], [2], 3, 1],
    [[1, 2, 3, 4, 5, 6, 7, 8, 9], [9], [], [1, 2, 3, 4, 5, 6, 7, 8], 9, 8],
    [[1, 2, 3, 4, 5, 6, 7, 8, 9], [9,1], [], [2, 3, 4, 5, 6, 7, 8], 10, 7],
]

function diff(a, b) {
    var found, deleteCount = 0, checkedCount = 0, aLen = a.length, bLen = b.length, i, j, bCount = 0, aCount = 0, st = 0, added = [], removed = [];
    for (i = 0; i < bLen; i++) {
        found = false;
        for (j = st; j < aLen; j++) {
            bCount++;
            if (b[i] === a[j]) {
                if (st == j) {
                    st = j + 1;
                }
                checkedCount++;
                found = true;
                break;
            }
        }
        if (!found) {
            added.push(b[i]);
        }
    }
    if (checkedCount < aLen) {
        for (i = st; i < aLen; i++) {
            found = false;
            for (j = st; j < bLen; j++) {
                aCount++;
                if (b[j] === a[i]) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                deleteCount++;
                removed.push(a[i]);
                if (deleteCount == aLen - checkedCount) {
                    break;
                }
            }
        }
    }
    return {added: added, removed: removed, aCount: aCount, bCount: bCount}
}

function add(p){

}
function remove(p){

}
function fdiff(a, b) {
    var found, deleteCount, checkedCount = 0, aLen = a.length, bLen = b.length, i, j, st = 0;
    for (i = 0; i < bLen; i++) {
        found = false;
        for (j = st; j < aLen; j++) {
            if (b[i] === a[j]) {
                if (st == j) {
                    st = j + 1;
                }
                checkedCount++;
                found = true;
                break;
            }
        }
        if (!found) {
            add(b[i]);
        }
    }
    if (checkedCount < aLen) {
        deleteCount = 0;
        for (i = st; i < aLen; i++) {
            found = false;
            for (j = st; j < bLen; j++) {
                if (b[j] === a[i]) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                deleteCount++;
                remove(a[i]);
                if (deleteCount == aLen - checkedCount) {
                    break;
                }
            }
        }
    }
}

function fill(a) {
    var arr = [];
    for (var i = 0; i < a.length; i++) {
        for (var j = 0; j < 10; j++) {
            arr[i * 10 + j] = a[i] * 10 + j;
        }
    }
    // console.log(arr);
    return a;
}

function runTests() {
    var wrongTests = 0;
    for (var i = 0; i < tests.length; i++) {
        var test = tests[i];

        var result = diff(fill(test[0]), fill(test[1]));
        // console.log(i, result.bCount, result.aCount);
        if (JSON.stringify(result.added) !== JSON.stringify(test[2])) {
            console.info(i, test, 'added', result);
            wrongTests++;
        }
        if (JSON.stringify(result.removed) !== JSON.stringify(test[3])) {
            console.info(i, test, 'removed', result);
            wrongTests++;
        }
        if (result.bCount != test[4]) {
            console.info(i, 'bCount', test[4], result.bCount, test);
            wrongTests++;
        }
        if (result.aCount != test[5]) {
            console.info(i, 'aCount', test[5], result.aCount, test);
            wrongTests++;
        }
        // console.log(i, result.aCount + result.bCount, result.added.length, result.removed.length);
    }
    console.log('wrongTests', wrongTests);
}
runTests();