How can I sort an array based on "before" and "after" conditions in JavaScript?

Question

I want to sort an array based on "before" and "after" conditions.

Example:

• C should be before B: Example: {key: 'C', condition: {$before: 'B'}
• B should be after A: Example: {key: 'B', condition: {$after: 'A'}
• A: Example {key: 'A'}.

The resulting sorted list would be: A, C, B.

I need this so I can sort a list of middleware in a pipeline. Each middleware has a condition and I should come up with an order in which all conditions from all middleware are met. This is similar to what MS Project does to organize tasks in a Gantt given what are the requirements for a task.

Question: What is the easiest way to achieve it? Even by using external libraries like underscore? Bonus: Does this kind of sorting have a name better than "conditional sorting"? That would help on my Google searches.

EDIT: The input should be an array of items with their conditions. I can't hardcode the sort method.

EDIT 2: As @Berdi stated. This is called typological sorting. Yes, depending on the items and conditions, there might be no combination that meet all the conditions and my algorithm should trigger an exception.

EDIT 3: The way I'm thinking of implementing this is calculating all the possible combinations and then look for the first one that meet all the conditions. This may not be terribly slow for me because, in my case, I can do this just once when the app starts and I'm not going to have more than 50 items in the array. But anyway, for the science, it would be good to know a more optimized solution.

EDIT 4: I would accept a solution that works with after conditions only. Like MS Project.

Answer 1

Bonus: Does this kind of sorting have a name better than "conditional sorting"?

It's called topological sort. And depending on your exact input format and content, it might not even be well-defined.

Answer 2

I would use: a hash table, a pointer for the start and then reassembling the array.

(This answer is part of my answer from this question: Ordering array of objects that have a BeforeID and AfterID on each object)

function chain(array) {
    var o = {}, pointer;
    array.forEach(function (a) {
        o[a.id] = a;
        if (a.beforeId === null) {
            pointer = a.id;
        }
    });
    array = [];
    do {
        array.push(o[pointer]);
        pointer = o[pointer].afterId;
    } while (pointer !== null);
    return array;
}

var unsorted = [{ id: 7, beforeId: 6, afterId: 8 }, { id: 11, beforeId: 10, afterId: null }, { id: 0, beforeId: null, afterId: 1 }, { id: 1, beforeId: 0, afterId: 2 }, { id: 4, beforeId: 3, afterId: 5 }, { id: 8, beforeId: 7, afterId: 9 }, { id: 2, beforeId: 1, afterId: 3 }, { id: 9, beforeId: 8, afterId: 10 }, { id: 10, beforeId: 9, afterId: 11 }, { id: 3, beforeId: 2, afterId: 4 }, { id: 5, beforeId: 4, afterId: 6 }, { id: 6, beforeId: 5, afterId: 7 }];
document.write('<pre>' + JSON.stringify(chain(unsorted), 0, 4) + '</pre>');

A Solution for EDIT 4, after conditions only.

function chain(array) {
    var n = {}, o = {}, pointer;
    array.forEach(function (a) {
        o[a.id] = a;
        n[a.after] = a.id;
        if (a.after === null) {
            pointer = a.id;
        }
    });
    // rewind pointer.
    // i took push for the array. otherwise the array could be mounted
    // from the other end with unshift but push is more efficient.
    do {
        pointer = n[pointer];
    } while (pointer in n);
    array = [];
    do {
        array.push(o[pointer]);
        pointer = o[pointer].after;
    } while (pointer !== null);
    return array;
}

var unsorted = [{ id: 7, after: 8 }, { id: 11, after: null }, { id: 0, after: 1 }, { id: 1, after: 2 }, { id: 4, after: 5 }, { id: 8, after: 9 }, { id: 2, after: 3 }, { id: 9, after: 10 }, { id: 10, after: 11 }, { id: 3, after: 4 }, { id: 5, after: 6 }, { id: 6, after: 7 }, ];
document.write('<pre>' + JSON.stringify(chain(unsorted), 0, 4) + '</pre>');

Edit - with sparse before/after

function chain(array) {
    var after = {}, before = {}, o = {}, pointer = array[0].id;
    array.forEach(function (a) {
        o[a.id] = a;
        if (a.after !== null) {
            after[a.id] = a.after;
            before[a.after] = a.id;
        }
        if (a.before !== null) {
            before[a.id] = a.before;
            after[a.before] = a.id;
        }
    });

    document.write('<pre>before ' + JSON.stringify(before, 0, 4) + '</pre>');
    document.write('<pre>after ' + JSON.stringify(after, 0, 4) + '</pre>');

    do {
        document.write('pointer: ' + pointer + '<br>');
        pointer = before[pointer];
    } while (pointer in before);
    document.write('pointer: ' + pointer + '<br>');
    array = [];
    do {
        array.push(o[pointer]);
        pointer = after[pointer];
    } while (pointer !== undefined);
    return array;
}

var unsorted = [{ id: 'C', before: 'B', after: null }, { id: 'B', before: null, after: null }, { id: 'A', before: null, after: 'B' }];
document.write('<pre>' + JSON.stringify(chain(unsorted), 0, 4) + '</pre>');

Answer 3

This may be of use.

function sortByRules(rules, arr) {
    var rulesEvaluated = [];

    rules.forEach(rule => {
      applyRule(rule, arr);
      rulesEvaluated.push(rule);

      if (conflicts(rulesEvaluated, arr)){
        throw new Error('rule conflict');
      }
    });

    return arr;
}

function conflicts(rules, arr) {
    return rules.some(r => r.condition.before ?
      arr.indexOf(r.key)>arr.indexOf(r.condition.before) :
      arr.indexOf(r.key)<arr.indexOf(r.condition.after));
}

function applyRule(rule, arr) {
    var increment = rule.condition.before ? -1 : 1;
    var item = arr.splice(arr.indexOf(rule.key), 1)[0];
    var target = rule.condition.before || rule.condition.after;
    arr.splice(Math.max(0, arr.indexOf(target) + increment), 0, item);
}


var toSort = ['b', 'd', 'c', 'a'];    
var rules = [ { key: 'b', condition: { before: 'c' } }, 
              { key: 'd', condition: { after: 'c' } }, 
              { key: 'a', condition: { before: 'b' } } ];
document.write(sortByRules(rules, toSort)); // ['a', 'b',  'c', 'd']

Answer 4

Create an object storing the order you need, then use [].sort() as usual:

var sorter = {
  'A': 1,
  'B': 3,
  'C': 2
}

var input = ['A', 'B', 'C'];

input = input.sort(function sort(a, b) {
  return sorter[a] > sorter[b];
});

console.log(input);
document.write("<pre>" + input + "</pre>");

Now, you can sort any array containing any combination of A, B and C. A, B, C can be anything, a property, its length, the first letter of a value...