javascript - Sorting a threaded conversation -

not sure how frame one, here goes.

it's sorting algorithm question

tools have play postgressql , python (2.6) on server , javascript/jquery @ browser end

i need move data describes threaded conversation postgres db web page. data starts off in chronological order, want display in threads

record numbers small - should never more 100 messages returned

so, simple example, imagine table:

id     reply_to   text ===    ========   ============================= 1      0          hello world 2      0          make me sandwich 3      1          hello 4      2          no chance 5      1          you? 6      5          me of course 

the end point want reach is

• hello world
• hello back
• who you?
• me of course
• make me sandwich
• no chance

or, put way...

id     reply_to   text ===    ========   ============================= 1      0          hello world 3      1          hello 5      1          you? 6      5          me of course 2      0          make me sandwich 4      2          no chance 

i'm not after full solution here, ajax, json , formatting stuff i'm happy on with.

i'm having issues getting head around neatest way manage sort.

sql? python? javascript?

i'm playing array sorts in javascript (for no better reason fact python skills exceptionally weak)

edit @ moment i'm @ like:

function bythread(a,b) {   if (a.reply > b.id && a.reply != 0){     console.log("compared id=" + a.id + " id=" + b.id + " , returned -1 ")     return -1;   }   if (a.id > b.reply && b.reply != 0 ){     console.log("compared id=" + a.id + " id=" + b.id + " , returned 1 ")     return 1;   }   console.log("compared id=" + a.id + " id=" + b.id + " , returned 0 ")   return 0; } msg.sort(bythread); 

and it's frustratingly close

i've tried in pure sql, because think that's logic should belong. need find list of ids parent child, , order that. luckily, postgres has array types can ordered, can use recursive cte:

with recursive threaded(id, reply_to, message, order_path) (     select          parent.id,          parent.reply_to,          parent.message,          null::int[] || parent.id -- create 1-element array parent id     conversation parent     parent.reply_to null     union     select          reply.id,          reply.reply_to,          reply.message,          t.order_path || reply.id -- append reply id current path     threaded t     join conversation reply on t.id = reply.reply_to     reply.reply_to not null ) select * threaded order order_path; 

and results:

1    null    "hello world"          "{1}" 3    1       "hello back"           "{1,3}" 5    1       "who you?"         "{1,5}" 6    5       "me of course"         "{1,5,6}" 2    null    "make me sandwich"   "{2}" 4    2       "no chance"            "{2,4}" 

i'm not sure how perform though, should test , profile on real dataset make sure it's fine. if it's not, perhaps @ restructuring data, , investigating different ways of storing "tree" data in database. there library django called django-mptt can efficiently store , retrieve trees. concept applies databases in general, algorithms pulling out trees , making sure stay intact require changes application logic, better handled library.

edit:

i should mention using top-level id "order_path" single number. this answer led me using array of ids guarantee order way down.