From 9d5bee3ba0b2ddba7cf15637923de3b4d1f5a19d Mon Sep 17 00:00:00 2001
From: Joshua Wise <jwise@andrew.cmu.edu>
Date: Tue, 22 Mar 2011 04:37:32 -0400
Subject: [PATCH] Sort list by a priority function in 'tdll'.

---
 list.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 tdl.h  |  1 +
 2 files changed, 65 insertions(+), 4 deletions(-)

diff --git a/list.c b/list.c
index a26a3c7..7c655bb 100644
--- a/list.c
+++ b/list.c
@@ -237,17 +237,77 @@ static void print_details(struct node *y, int indent, int summarise_kids, const
 
 }
 /*}}}*/
+/* 1 if x has lower priority than y. */
+static int node_lessthan(struct node *x, struct node *y)/*{{{*/
+{
+  if (x->priority < y->priority)
+    return 1;
+  if (x->priority > y->priority)
+    return 0;
+  if (x->required_by == 0 && y->required_by == 0)
+    return (x->idx > y->idx);
+  if (y->required_by == 0)
+    return 1;
+  if (x->required_by == 0)
+    return 0;
+  return x->required_by < y->required_by;
+}
+/*}}}*/
+static void sort_chain(struct links *x)/*{{{*/
+{
+  struct links new;
+  struct node *y, *ynext, *yprev;
+  int idx;
+  
+  new.next = NULL;
+  new.prev = NULL;
+  
+  /* Stupidsort. */
+  for (y = x->next, idx = 1; y != (struct node *) x; y = ynext, ++idx) {
+    /* y is now the current node; go insert it into its rightful place in
+     * the new chain.  */
+    struct node **nextp = &(new.next);
+    struct node *ins;
+    for (ins = new.next; ins && node_lessthan(ins, y); nextp = &(ins->chain.next), ins = ins->chain.next)
+      ;
+    y->chain.next->chain.prev = y->chain.prev;
+    y->chain.prev->chain.next = y->chain.next;
+    ynext = y->chain.next;
+    y->chain.next = *nextp;
+    *nextp = y;
+    y->idx = idx;
+  }
+  
+  /* Now clean up the new links. */
+  yprev = (struct node *)x;
+  for (y = new.next; y; yprev = y, y = y->chain.next) {
+    y->chain.prev = yprev;
+  }
+  yprev->chain.next = (struct node *)x;
+  new.prev = y;
+  
+  if (new.next == NULL) {
+    x->next = (struct node *)x;
+    x->prev = (struct node *)x;
+  } else {
+    x->next = new.next;
+    x->prev = new.prev;
+  }
+}
+/*}}}*/
 static void list_chain(struct links *x, int indent, int depth, const struct list_options *options, char *index_buffer, enum Priority prio, time_t now, unsigned char *hits)/*{{{*/
 {
   struct node *y;
-  int idx, is_done, is_deferred, is_postponed;
+  int is_done, is_deferred, is_postponed;
   int show_node;
   char component_buffer[8];
   char new_index_buffer[64];
   
-  for (y = x->next, idx = 1;
+  sort_chain(x);
+    
+  for (y = x->next;
        y != (struct node *) x;
-       y = y->chain.next, ++idx) {
+       y = y->chain.next) {
     
     is_done = (y->done > 0);
     is_postponed = (y->arrived == POSTPONED_TIME);
@@ -257,7 +317,7 @@ static void list_chain(struct links *x, int indent, int depth, const struct list
              || (!is_deferred && !is_postponed);
     if (!show_node) continue;
 
-    sprintf(component_buffer, "%d", idx);
+    sprintf(component_buffer, "%d", y->idx);
     strcpy(new_index_buffer, index_buffer);
     if (strlen(new_index_buffer) > 0) {
       strcat(new_index_buffer, ".");
diff --git a/tdl.h b/tdl.h
index 6faa193..14c25a5 100644
--- a/tdl.h
+++ b/tdl.h
@@ -60,6 +60,7 @@ struct node {
   long done;
   char *scratch; /* For functions to attach stuff to nodes */
   int iscratch;  /* More scratch space */
+  int idx; /* Keep your number, even after having been sorted. */
   char flag;
 };
 
-- 
2.39.2