排序線程對話

Question

不知道如何框架這個，但在這裏。

這是一個排序算法問題

工具我有玩的服務器和JavaScript/jQuery的在瀏覽器端

我需要移動數據對PostgreSQL的和python（2.6）描述螺紋從postgres數據庫到網頁的對話。該數據按照時間順序開始了，我想在線程顯示

創紀錄的數字是小的 - 應該不會超過100條短信返回

所以，作爲一個簡單的例子，假設表：

ID  Reply_To Text 
=== ======== ============================= 
1  0   Hello World 
2  0   Make me a sandwich 
3  1   Hello back 
4  2   No chance 
5  1   Who are you? 
6  5   Me of course 

終點我想達到的

• 的Hello World
• 你好回
• 你是誰？
• 我當然
• 讓我一個三明治
• 沒有機會

或者，換一種方式......

ID  Reply_To Text 
=== ======== ============================= 
1  0   Hello World 
3  1   Hello back 
5  1   Who are you? 
6  5   Me of course 
2  0   Make me a sandwich 
4  2   No chance 

我並沒有在這裏找到完整的解決方案，所有ajax，json和格式化的東西，我很樂意繼續。

我只是遇到了問題，讓我的頭腦最好的方式來管理排序。

SQL？蟒蛇？ JavaScript的？

我目前正在與陣列各種打在Javascript（因爲沒有更好的原因，而不是事實，我的Python的技能是非常弱）

編輯 目前我在這樣的：

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

它很令人沮喪地關閉

Answer 1

我試過在純sql中這樣做，因爲我認爲這就是邏輯應該屬於的地方。你需要做的是找到從父母到孩子的ID列表，並按順序排列。幸運的是，Postgres的具有可有序陣列的類型，所以我們可以使用遞歸CTE：

with recursive threaded(id, reply_to, message, order_path) as (
    select 
     parent.id, 
     parent.reply_to, 
     parent.message, 
     NULL::int[] || parent.id -- create an 1-element array with the parent id 
    from conversation parent 
    where parent.reply_to is null 
    UNION ALL 
    select 
     reply.id, 
     reply.reply_to, 
     reply.message, 
     t.order_path || reply.id -- append the reply id to the current path 
    from threaded t 
    join conversation reply on t.id = reply.reply_to 
    where reply.reply_to is not null 
) 
select * from threaded order by order_path; 

而且結果：

1 NULL "Hello World"   "{1}" 
3 1  "Hello Back"   "{1,3}" 
5 1  "Who are you?"   "{1,5}" 
6 5  "Me of course"   "{1,5,6}" 
2 NULL "Make me a sandwich" "{2}" 
4 2  "No Chance"   "{2,4}" 

我不知道這將如何進行，雖然，所以你應該在你的真實數據集上進行測試和分析，以確保它沒問題。如果不是，也許你可以考慮重構你的數據，並研究在數據庫中存儲「樹」數據的不同方法。有一個django圖書館叫django-mptt，可以有效地存儲和檢索樹木。這個概念一般適用於數據庫，但是抽出樹並確保它們保持完好的算法需要對應用程序邏輯進行更改，更好地由庫處理。

編輯：

我要指出，我本來只用頂級ID爲「order_path」作爲一個單一的數字。 This answer讓我使用一個ID數組來保證順序一路下降。

Answer 2

你可以在JS方面嘗試這樣的事情。由於這裏面有答覆的答覆，它會很容易從convoSorted

var convo = [{id: 1, replyTo: 0, text: "hello world"}, 
      {id: 2, replyTo: 0, text: "Make me a sandwich"}, 
      {id: 3, replyTo: 1, text: "hello back"}, 
      {id: 4, replyTo: 2, text: "no chance"}, 
      {id: 5, replyTo: 1, text: "who are you?"}, 
      {id: 6, replyTo: 5, text: "me of course"}, 
      {id: 7, replyTo: 0, text: "new question"}, 
      {id: 8, replyTo: 7, text: "new answer"}]; 

var convoSorted = []; 

function addToReplies(obj, rply){ //recursive function to find the q. to reply to. 
    if (obj.id == rply.replyTo){ 
    obj.replies.push({id: rply.id, text: rply.text, replies: []}); //add to the replies array 
    } 
    else{ 
     for (k = 0; k < obj.replies.length; k++){ 
     addToReplies(obj.replies[k], rply); 
     } 
    } 
} 

function sortConvo(){ 

    for (i = 0; i < convo.length; i++){ 
    if (convo[i].replyTo == 0){ //if it's not a reply, add to sorted array 
     convoSorted.push({ id : convo[i].id, text: convo[i].text, replies: [] }); 
    } 
    else{ //it's a reply, find the question it's replying 
     for (j = 0; j < convoSorted.length; j++){ 
      addToReplies(convoSorted[j], convo[i]); 
     } 
    } 
    } 
} 

sortConvo(); 
console.log(convoSorted); 

Answer 3

我覺得白癡建立一個DOM - 我一直過於複雜這一點。

所有它需要的是一個有點橫向思維（此討論已與幫助）

msgs=[ 
    {id:1,reply:0,msg:'Hello World'}, 
    {id:2,reply:0,msg:'Make me a sandwich'}, 
    {id:3,reply:1,msg:'Hello back'}, 
    {id:4,reply:2,msg:'No chance'}, 
    {id:5,reply:1,msg:'Who are you?'}, 
    {id:6,reply:5,msg:'Me of course'} 
]; 
msgs.sort(function(a,b){ 
    return a.reply - b.reply; 
}); 

var conversation=$("<div id='threaded'>"); 
var list = $("<ul>") 
    .attr("id","thread_" + msgs[0].reply); 
var message = $("<li>") 
    .text(msgs[0].msg) 
    .attr("id","msg_" + msgs[0].id); 
$(list).append(message); 
$(conversation).append(list); 

for (i=1; i<msgs.length; i++){ 
    var message = $("<li>") 
    .text(msgs[i].msg) 
    .attr("id","msg_" + msgs[i].id); 
    if ($(conversation).find("#msg_" + msgs[i].reply).length == 0){ 
    $(conversation).find("ul:eq(0)").append(message); 
    } else { 
    var list = $("<ul>") 
     .attr("id","thread_" + msgs[i].id); 
    $(list).append(message); 
    $(conversation).find("#msg_" + msgs[i].reply).append(list); 
    } 
} 

有時我忘了剛剛的有力工具DOM是什麼