Sorting hierarchical data in Javascript (Adjacency List/Flat table)

Question

I am trying to sort the following data:

var data = [
    { path: '/a', order: 0 },
    { path: '/b', order: 1 },
    { path: '/a/d', order: 1 },
    { path: '/a/c', order: 0 }
];

Into:

var expected = [
    { path: '/a', order: 0 },
    { path: '/a/c', order: 0 },
    { path: '/a/d', order: 1 },
    { path: '/b', order: 1 }
];

I found a great post about hierarchical data:

What are the options for storing hierarchical data in a relational database?

From that question I think I am using a flat table:

A modification of the Adjacency List that adds a Level and Rank (e.g. ordering) column to each record.

The link in that SO question is down so I can't get more information from that.

I setup a JsFiddle to assert my sort function:

http://jsfiddle.net/U76ch/

I already tried a few approaches but none of them gave the correct result.

A completely different solution would be to add the order and sort alphabetically. But since the result will end up as urls it's kinda ugly to have www.example.com/01-products/01-snowboard.

Update

I created a more complex JSFiddle example to show what I am trying to do:

http://jsfiddle.net/YSd3d/

So I am trying to sort on path but the nodes should be sorted on order at their level. So like a file system when you sort alphabetically but the last child is sorted on order.

To your updated example: /cars and /bikes are nodes cars and bikes in the path /, both have to be at the beginning. — scessor
– scessor, Commented Jul 1, 2012 at 13:08
Isn't it possible to sort them the way I have in expected? I would like to have /parent, /parent/child, /parent, /parent/child depending on their order value. — Pickels
– Pickels, Commented Jul 1, 2012 at 13:15
Not with the sort function, because if you have two random elements, you have to say the first one is lower, higher or equal without using/knowing the other elements. But e.g. if you have the elements /bikes/some-brand and /cars/bmw the result depends on the elements /cars and /bikes. — scessor
– scessor, Commented Jul 1, 2012 at 13:34

Tomalak · Accepted Answer · 2012-07-01 12:47:12Z

4

var data = [
    { path: '/a', order: 0 },
    { path: '/b', order: 1 },
    { path: '/a/d', order: 1 },
    { path: '/a/c', order: 0 }
];

data.sort(function(a, b) {
  if (a.path === b.path) {
    return a.order < b.order ? -1 : 1;
  } else {
    return a.path < b.path ? -1 : 1;
  };
});

answered Jul 1, 2012 at 12:47

Tomalak

339k68 gold badges547 silver badges635 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

hookedonwinter · Accepted Answer · 2012-07-01 12:54:28Z

0

Can you just do a simple sort on it? I don't fully understand your concerns in the last paragraph.

var result = data.sort(function (a, b) {
  return a.path > b.path;
});

http://jsfiddle.net/sftdq/

Edit. I changed your test to show order > abc. Works in jsfiddle exmample

var data = [
    { path: '/a', order: 0 },
    { path: '/b', order: 1 },
    { path: '/a/a', order: 1 },
    { path: '/a/c', order: 0 }
];


var result = data.sort(function (a, b) {
    if( a.order === b.order ){
        return a.path > b.path;
    }
    else {
        return a.order > b.order;
    }
});


var expected = [
    { path: '/a', order: 0 },
    { path: '/a/c', order: 0 },
    { path: '/a/a', order: 1 },
    { path: '/b', order: 1 }
];


if (_.isEqual(result, expected)) {
    alert('Success');       
} else {
    alert('Failed');  
};

edited Jul 1, 2012 at 12:54

answered Jul 1, 2012 at 12:46

hookedonwinter

12.7k19 gold badges64 silver badges75 bronze badges

2 Comments

Pickels Over a year ago

If you have /products/a-snowboard and /products/b-snowboard and I might want to have b-snowboard come before a-snowboard.

hookedonwinter Over a year ago

Ah, so you want to sort by order first, then alphabetically? Your example is sorted alphabetically despite order, which is why I missed it I think.

Collectives™ on Stack Overflow

Sorting hierarchical data in Javascript (Adjacency List/Flat table)

2 Answers 2

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related