I am trying to sort values that are sometimes incomparable with each other. The data that I am sorting resembles a tree where
var _ = require('underscore')
var SortedArray = require('collections/sorted-array');
// x has y as one of its dependencies
var x = {
uuid: 'x',
dependsOn: ['y', 'k']
}
// y should be go before x as x depends on y
var y = {
uuid: 'y',
dependsOn: ['k']
}
// z depends on k and so k must come before z
var z = {
uuid: 'z',
dependsOn: ['k']
}
// k depends on nothing
var k = {
uuid: 'k',
dependsOn: []
};
function equal(a, b) {
return (a.uuid === b.uuid)
}
function compare(a, b) {
// if they have the same uuid; then they are the same
if (a.uuid === b.uuid) {
return 0
}
// if a depends on b, then a should be after b
for (var i = 0, len = a.dependsOn.length; i < len; i++) {
var dependsOn = a.dependsOn[i];
if (dependsOn === b.uuid) {
return 1
}
}
// if b depends on a, then b should be after a
for (var i = 0, len = b.dependsOn.length; i < len; i++) {
var dependsOn = b.dependsOn[i];
if (dependsOn === a.uuid) {
return -1
}
}
// this is the edge case,
// if neither a or b depends on each other, then they don't have relative ranking
return 0
}
// this is every possible permutation - they should all sort to the same orders
// expected order k, z, y, x or k, y, z, x or k, y, x, z
// because:
// k -> z as z depends on k
// k -> y as y depends on k
// no relative ranking between z and y as they don't depend on each other
// x depends on both y and k so x will come after them
var perms = [
[x, y, z, k],
[x, y, k, z],
[x, z, y, k],
[x, z, k, y],
[x, k, y, z],
[x, k, z, y],
[y, x, z, k],
[y, x, k, z],
[y, z, x, k],
[y, z, k, x],
[y, k, x, z],
[y, k, z, x],
[z, x, y, k],
[z, x, k, y],
[z, y, x, k],
[z, y, k, x],
[z, k, x, y],
[z, k, y, x],
[k, x, y, z],
[k, x, z, y],
[k, y, x, z],
[k, y, z, x],
[k, z, x, y],
[k, z, y, x],
]
perms.forEach(function(perm) {
var s = SortedArray(perm, equal, compare)
var p = _.pluck(s.toArray(), 'uuid')
console.log(p, _.isEqual(p, ['k', 'z', 'y', 'x']) || _.isEqual(p, ['k', 'y', 'z', 'x']) || _.isEqual(p, ['k', 'y', 'x', 'z']))
})
\\ -sorted array- -test-
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'x', 'z', 'y' ] false \\ x depends on y, so it should come after y
[ 'k', 'x', 'z', 'y' ] false \\ x depends on y, so it should come after y
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'x', 'z', 'y' ] false \\ x depends on y, so it should come after y
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'x', 'z', 'y' ] false \\ x depends on y, so it should come after y
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true