Sorting Array To Make Parent Items Come Before Children

How can I order the list below to ensure children items are always preceded by their parent item? Some items in the list will be neither a child or parent item, and they should ju

Solution 1:

This solution works for any depth and use a tree for getting dependent items in right order.

var items = [{ _id: "Fizz" }, { _id: "Frogmorton", parent: "The Shire" }, { _id: "Hobbiton", parent: "The Shire" }, { _id: "Foobar", isParent: true }, { _id: "Foobar Xland", parent: "Foobar" }, { _id: "The Shire", isParent: true }],
    tree = function (data, root) {
        var r = [], o = {};
        data.forEach(function (t) {
            var a = { i: t._id, parent: t.p, data: t };
            a.children = o[a.i] && o[a.i].children;
            o[a.i] = a;
            if (a.p === root) {
                r.push(a);
            } else {
                o[a.p] = o[a.p] || {};
                o[a.p].children = o[a.p].children || [];
                o[a.p].children.push(a);
            }
        });
        return r;
    }(items.sort(function (a, b) { return a._id.localeCompare(b._id); }), undefined),
    ordered = tree.reduce(functionflat(r, o) {
        return r.concat(o.data, (o.children || []).reduce(flat, []));
    }, []);

console.log(ordered);

.as-console-wrapper { max-height: 100%!important; top: 0; }

Solution 2:

You could use this function, which can deal with grand-grand-grand-...-children, by converting it to a temporary tree and performing a depth-first iteration in it -- all in a functional way:

functiondepthFirst(items) {
    returnArray.from(items.reduce( (mp, o) =>
        (mp.get(o.parent).children.push(mp.get(o._id)), mp),
        newMap([{}].concat(items).map( (o) => [o._id, { children: [], orig: o }] ))
    ), ([_, o]) =>
        (o.children.sort((a, b) => a.orig._id.localeCompare(b.orig._id)), o)
    )[0].children.reduce(functioncollect(acc, o) {
        return acc.concat(o.orig, o.children.reduce(collect, []))
    }, []);
}
// Sample inputvar items = [{
    "_id": "Frogmorton",
    "parent": "The Shire"
}, {
    "_id": "Hobbiton",
    "parent": "The Shire"
}, {
    "_id": "Foobar",
}, {
    "_id": "Foobar Xland",
    "parent": "Foobar"
}, {
    "_id": "Fizz"
}, {
    "_id": "The Shire"
}, {
    "_id": "added grandchild",
    "parent": "Frogmorton"
}];

console.log(depthFirst(items));

Solution 3:

The following solutions works

var items = [
  
  {
    "_id": "Frogmorton",
    "parent": "The Shire"
  },
  {
    "_id": "Hobbiton",
    "parent": "The Shire"
  },
  {
    "_id": "Foobar",
    "isParent": true
  },
  {
    "_id": "Foobar Xland",
    "parent": "Foobar"
  },
  {
    "_id": "Fizz"
  },
  {
    "_id": "The Shire",
    "isParent": true
  }
]

const sortedArray = items
  .filter(item => item.isParent || !item.parent)
  .sort((a, b) => a._id.localeCompare(b._id))
  .map(parent => [parent].concat(
      items
        .filter(item => item.parent === parent._id)
        .sort((a, b) => a._id.localeCompare(b._id)))
    )
  .reduce((acc, item) => acc.concat(item), [])
  
console.log(sortedArray);

Solution 4:

You could use a closure with hashing to have a self-contained method.

const items = [ { _id: "Frogmorton", parent: "The Shire" }, { _id: "Hobbiton", parent: "The Shire" }, { _id: "Foobar", isParent: true }, { _id: "Foobar Xland", parent: "Foobar" },{ _id: "Fizz" }, { _id: "The Shire", isParent: true }],
result = Object.entries(items.slice().reduce((c =>(a, b) =>
    (c['val'] = b.parent || b._id, c['parent'] = b.parent, !a[c.val] ?
      a[c.val] = [b] :
      c.parent ? a[c.val].push(b) :
      a[c.val].unshift(b), a)
  )({}), ({}))).sort((a, b) =>
    a[0].localeCompare(b[0])).map(x =>
    x[1]).reduce((x, i) => x.concat(i), []);
    
console.log(result);

.as-console-wrapper { max-height: 100%!important; top: 0; }