Ordering array of objects that have a BeforeID and AfterID on each object

Question

I am working with an API which returns an array of objects. Each object has an ID, and it also specifies which object comes before itself and after itself with a beforeId and afterId property. If it's the first object in the list, then the beforeId is null (since nothing is before it in the list) and if it's the last object in the list, then the afterId is null.

Example response from API:

var myUnorderedObjects = [
    { id: 896, beforeId: 392, afterId: 955 },
    { id: 955, beforeId: 896, afterId: null }
    { id: 451, beforeId: null, afterId: 392 },
    { id: 392, beforeId: 451, afterId: 896 },
]

Example of an ordered array:

var myOrderedObjects = [
    { id: 451, beforeId: null, afterId: 392 },
    { id: 392, beforeId: 451, afterId: 896 },
    { id: 896, beforeId: 392, afterId: 955 },
    { id: 955, beforeId: 896, afterId: null }
]

What is the best way to order these objects? Currently, my application implements its own ordering logic which is separate from the API's. I'd like to make them consistent. My general approach so far is to find the first object by identifying the one with null set on the beforeId, and then look up and find each one specified in the afterId, but that just seems a bit... rubbish.

My application uses Underscore.js, so I'm happy for any answers to make use of this library.

Edit

I did a quick performance test between the two answers. Nina Scholz's answer was the fastest, and also an approach I hadn't even considered. http://jsperf.com/order-objects-with-beforeid-and-afterid

@YuryTarabanko – Yes. Currently, my application implements its own ordering logic which is separate from the API's. I'd like to make them consistent. My general approach is to find the first object by identifying the one with `null` set on the `beforeId`, and then manually looking up and finding each one specified in the `afterId`, but that just seems a bit... rubbish. So I thought I'd ask here and see if there's a better way. Do you have any suggestions? — tjramage, Nov 27 '15 at 20:51
You better recheck accepted answer once again using more lengthy inputs. http://jsfiddle.net/zr8u15sv/ — Yury Tarabanko, Nov 30 '15 at 18:46

Nina Scholz · Accepted Answer · 2015-12-01T12:55:57.787

This solution works if all items are chained.

function strange(a, b) {
    if (
        a.beforeId === null ||
        b.afterId === null ||
        a.id === b.beforeId ||
        a.afterId === b.id
    ) {
        return -1;
    }
    if (
        b.beforeId === null ||
        a.afterId === null ||
        a.id === b.afterId ||
        a.beforeId === b.id
    ) {
        return 1;
    }
    return 0;
}

var unsorted1 = [
        { id: 896, beforeId: 392, afterId: 955 },
        { id: 955, beforeId: 896, afterId: null },
        { id: 451, beforeId: null, afterId: 392 },
        { id: 392, beforeId: 451, afterId: 893 },
    ],
    unsorted2 = [
        { id: 3, beforeId: 2, afterId: 4 },
        { id: 4, beforeId: 3, afterId: null },
        { id: 0, beforeId: null, afterId: 1 },
        { id: 2, beforeId: 1, afterId: 3 },
        { id: 1, beforeId: 0, afterId: 2 }
    ],
    sorted1 = unsorted1.slice().sort(strange),
    sorted2 = unsorted2.slice().sort(strange);

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

Update:

Yury Tarabanko pointed me to a problem with Chrome 46 and he is right, the former version does not sort well. So here an updated version which uses a hash table and a recursive call of the sort function.

function sort(array) {

    function s(a, b) {
        if (a.beforeId === null || b.afterId === null || a.id === b.beforeId || a.afterId === b.id) {
            return -1;
        }
        if (b.beforeId === null || a.afterId === null || a.id === b.afterId || a.beforeId === b.id) {
            return 1;
        }
        return s(o[a.beforeId], b) || s(a, o[b.afterId]) || 0;
    }

    var o = {};
    array = array.slice();
    array.forEach(function (a) {
        o[a.id] = a;
    });
    array.sort(s);
    return array;
}

var unsorted1 = [
        { id: 896, beforeId: 392, afterId: 955 },
        { id: 955, beforeId: 896, afterId: null },
        { id: 451, beforeId: null, afterId: 392 },
        { id: 392, beforeId: 451, afterId: 896 },
    ],
    unsorted2 = [
        { id: 3, beforeId: 2, afterId: 4 },
        { id: 4, beforeId: 3, afterId: null },
        { id: 0, beforeId: null, afterId: 1 },
        { id: 2, beforeId: 1, afterId: 3 },
        { id: 1, beforeId: 0, afterId: 2 }
    ],
    unsorted3 = [
        { 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(sort(unsorted1), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(sort(unsorted2), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(sort(unsorted3), 0, 4) + '</pre>');

Update 2:

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

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 unsorted1 = [
        { id: 896, beforeId: 392, afterId: 955 },
        { id: 955, beforeId: 896, afterId: null },
        { id: 451, beforeId: null, afterId: 392 },
        { id: 392, beforeId: 451, afterId: 896 },
    ],
    unsorted2 = [
        { id: 3, beforeId: 2, afterId: 4 },
        { id: 4, beforeId: 3, afterId: null },
        { id: 0, beforeId: null, afterId: 1 },
        { id: 2, beforeId: 1, afterId: 3 },
        { id: 1, beforeId: 0, afterId: 2 }
    ],
    unsorted3 = [
        { 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(unsorted1), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(chain(unsorted2), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(chain(unsorted3), 0, 4) + '</pre>');

Awesome. Not sure why I didn't even think about passing an actual compare function to `Array.sort()`... Your approach is also a lot faster: http://jsperf.com/order-objects-with-beforeid-and-afterid — tjramage, Nov 28 '15 at 10:46
This simply can't work in general case. http://jsfiddle.net/zr8u15sv/ Your function does not compare 2 arbitrary items. By returning 0 you are saying them to be equal thought you just failed to actually compare them. — Yury Tarabanko, Nov 30 '15 at 18:44
@YuryTarabanko, i added your example, but it works as it should. — Nina Scholz, Nov 30 '15 at 22:16
@NinaScholz Which browser? That's what I get in chrome 46 `[ { "id": 0, "beforeId": null, "afterId": 1 }, { "id": 2, "beforeId": 1, "afterId": 3 }, { "id": 3, "beforeId": 2, "afterId": 4 }, { "id": 1, "beforeId": 0, "afterId": 2 }, { "id": 4, "beforeId": 3, "afterId": null } ]` — Yury Tarabanko, Nov 30 '15 at 22:47
I've added `isSorted` function http://jsfiddle.net/zr8u15sv/1/ Check your results plz. — Yury Tarabanko, Nov 30 '15 at 23:12
@YuryTarabanko, thank you for pointing me to the problem. pease see edit. i think the IE has a different sort engine an iterates until no `0` is returning. the Chrome does not care about that. — Nina Scholz, Dec 01 '15 at 08:13
@NinaScholz It would be interesting to measure the performance of your solution. But the main reason I've downvoted your answer is that you don't need sorting at all. Even if you comparator function was `O(1)` which is not in case as far as I can see overall sorting would be `O(n log n)` time (`O(n^2 log n)` in your case). But this can be done in `O(n)` using 2 loops: cache and construct. Whenever you have indexed entire list by id you could simply construct entire list using the cache using the fact that hash lookup is `O(1)`. — Yury Tarabanko, Dec 01 '15 at 09:35
@YuryTarabanko, i know the problem with big o, but it was more or less an attempt to use it in combination with `Array.prototype.sort`. so performance was not my (main) target. in a production code i woud not use the above solution. — Nina Scholz, Dec 01 '15 at 09:41
@NinaScholz "in a production code i woud not use the above solution." you'd better highlight this in your answer then :) — Yury Tarabanko, Dec 01 '15 at 09:43

score 0 · Answer 2 · answered Nov 27 '15 at 20:58

Since the ids are just arbitrary numbers you cannot generate any kind of object index from them that might be used for sorting. Starting with beforeId null and following the afterId fields is a reasonable solution. If this is how you get the data from the API, there is nothing wrong with your approach of ordering the objects.

Jon · Answer 3 · 2015-11-28T11:08:36.033

0

This would do it:

function findElementWithPropertyValue (array, property, value) {
  var index = array.map(function (element) {
    return element[property];
  }).indexOf(value);

  return array[index];
}

function reorderResults (unsorted) {
  var sorted = [];

  sorted.push(findElementWithPropertyValue(unsorted, 'beforeId', null));

  while (sorted.length < unsorted.length) {
    sorted.push(findElementWithPropertyValue(unsorted, 'beforeId', sorted[sorted.length - 1].id));
  }

  return sorted
}

var myUnorderedObjects = [
      { id: 896, beforeId: 392, afterId: 955 },
      { id: 955, beforeId: 896, afterId: null },
      { id: 451, beforeId: null, afterId: 392 },
      { id: 392, beforeId: 451, afterId: 893 }
    ],
    myOrderedObjects = reorderResults(myUnorderedObjects);

console.log(myOrderedObjects);

edited Nov 28 '15 at 11:08

answered Nov 27 '15 at 20:59

Jon

10,678
2
36
48

Apologies if you thought I was saying your approach was "rubbish"! This is basically the same solution as mine – I just felt like there should have been a better way to do it. Nina Scholz's answer is indeed an `Array.sort()` compare function which works well and is pretty fast! – tjramage Nov 28 '15 at 10:56
Nina's answer is a great solution. I'd be interested in seeing what the performance differences are between them. I'll take my comment back about the sort function too ;) – Jon Nov 28 '15 at 11:08
Ha! :) Jon – I posted a jsperf link on the answer. – tjramage Nov 28 '15 at 11:09
Wow, quite a difference. Totally bookmarking that website too :) – Jon Nov 28 '15 at 11:11

score 0 · Answer 4 · answered Dec 01 '15 at 08:04

As I have written in comment @Nina's answer is just wrong. Given function fails to compare 2 non-sibling items and returning 0 is not an option here.

First incorrect result comes for arrays of length 5.

var shuffled = [
    {"id":3,"beforeId":2,"afterId":4},
    {"id":4,"beforeId":3,"afterId":null},
    {"id":0,"beforeId":null,"afterId":1},
    {"id":2,"beforeId":1,"afterId":3},
    {"id":1,"beforeId":0,"afterId":2}
];

was sorted to

[
    {"id": 0, "beforeId": null, "afterId": 1},
    {"id": 2, "beforeId": 1, "afterId": 3},
    {"id": 3, "beforeId": 2, "afterId": 4},
    {"id": 1, "beforeId": 0, "afterId": 2},
    {"id": 4, "beforeId": 3,"afterId": null}
]

Actually @Jon's solution was right. His naive implementation might be optimized to be O(n) instead of O(n^2). Which is a micro optimization you should not worry about unless you have hundreds of items in your list. Perf.

/**
 * Using for loops for *micro* optimization and explicit O(n) estimates.
 * http://jsperf.com/order-objects-with-beforeid-and-afterid/2
 */
function linkSort(array) {
    var head, 
        cache = {},
        i,
        len = array.length,
        linked = new Array(len),
        item;

    //indexing
    for(i = 0; i < len; i++) { //O(n) index and find head
        item = array[i];

        if(item.beforeId === null) { //is head
            head = item;
        }
        else { //index by id
            cache[item.id] = item;            
        }
    }

    //linking
    linked[0] = head; 

    for(i = 1; i < len; i++) { //O(n) construct linked list
        linked[i] = head = cache[head.afterId]; //Lookup is O(1) unlike map+indexOf
    }

    return linked;
}

Ordering array of objects that have a BeforeID and AfterID on each object

4 Answers4

Linked