How to sort Array by order of dependent each other

Question

I know the title is quite hard to understand.

I'll simply explain by simple code below.

var objA = {
    id: 1
}
var objB = {
    id: 2,
    children: [1,3] //<== this is ID of objA and objC
}
var objC = {
    id: 3,
    children: [1] //<== this is ID of objA
}

function myFunction(){
    const list = [objA, objB, objC];
    // Do something to sort to [objA, objC, objB]
    var listSorted = ...;
    for(var item in listSorted){
        //Do something else
    }
}

In the demo code above, the objA is independent of any other, so it should be run first, the objB depends on objA and objC so it should be run after objA and objC, and so on. So after sorting the list, it should be to [objA, objC, objB]

Answer 1

Try this:

    function canRun(obj, readyIds) {
        // Without childs... can run
        if (!obj.children || obj.children.lenght === 0)
            return true;

        // If some req is not added yet... can't run
        for (let i = 0; i < obj.children.length; i++) {
            if (!readyIds[obj.children[i]])
                return false;
        }

        return true;
    }

    function getSortedList(list) {
        let readyIds = [];
        let listSorted = [];
        let someChanged = true;

        while (list.length > 0 && someChanged) {
            someChanged = false;

            for (let i = list.length - 1; i >= 0; i--) {
                var item = list[i];

                if (canRun(item, readyIds)) {
                    list.splice(i, 1);
                    listSorted.push(item);
                    readyIds[item.id] = true;
                    someChanged = true;
                }
            }
        }

        return listSorted;
    }

canRun check when an item can be executed: it hasn't dependencies or all dependencies have been added before.

To sort the items, we iterate list removing the items that canRun and adding into listSorted. We need to do in a while because in each for we can add only the items without dependencies. someChanged is for security, in case some item can't be executed, to prevent infinite while. In a normal case, list become empty and listSorted have all items. If some item can't be executed, list have these items and listSorted, the items that can be executed.

Test code:

    var objA = {
        id: 1
    }
    var objB = {
        id: 2,
        children: [1, 3] //<== this is ID of objA and objC
    }
    var objC = {
        id: 3,
        children: [1] //<== this is ID of objA
    }

    let list = [objA, objB, objC];
    let listSorted = getSortedList(list);