How to use SortedArray with incomparable values? (tests included)

[sidazhang]

I am trying to sort values that are sometimes incomparable with each other. The data that I am sorting resembles a tree where

1. if a depends on b, then a should be sorted after b
2. if b depends on a, then b should be sorted after b
3. if neither a or b depend on each other then they are incomparable.

   Below is my example code:

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']))
})

This is the test output (with my annotation):

\\ -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

[Stuk]

https://github.com/montagejs/collections/issues/27 is probably relevant

[kriskowal]

I would very much like to solve this problem and have stable operations. This is a matter of cracking open the Algorithms book and translating the right pseudocode. If anyone has a moment to do this, many people would be grateful.

[sidazhang]

My apologies, I didn't realise that there has already been an issue on this particular problem.

Is there any plan to add support for incomparable values?

[sidazhang]

There seems to be not well maintained module that does this. Any chance to merge it in?

https://www.npmjs.org/package/toposort

[kriskowal]

The topological sort implementation might be insightful.

There are two answers to your question.

1. I do want to support incomparable values in SortedArray.
2. I do not plan to spend time on this issue, at least I do not plan to soon. I would however welcome this as a contribution.

[kriskowal]

Topo sort sounds like the right algorithm for your particular situation though. Topo sort is usually implemented with a depth first traversal of the graph, which if well-written can tolerate cycles.

[sidazhang]

If I were to try to make a pull request to add support for incomparable values. Where would you recommend me to start with (collections is a pretty big library, so would be good if you could point me to a good starting point where I can focus my time on)

[kriskowal]

@sidazhang Everything you need should be in sorted-array.js. The problem is probably in the binary search algorithms. Knowing how Object.compare and Object.equals will help and is in shim-object.js, but you won’t be surprised. Don’t forget to use npm test to verify work, but also, fixing tests may be the right solution.

[hthetiot]

https://github.com/montagejs/collections/pull/171