/*
 * WORK IN PROGRESS ALERT: Daniel Eisenbud <daniel@math.berkeley.edu>
 * is currently working on this code.  Contact him before working on it!
 */

/*
 * Copyright (C) 1996-8 Michael R. Elkins <me@cs.hmc.edu>
 *
 *     This program is free software; you can redistribute it and/or modify
 *     it under the terms of the GNU General Public License as published by
 *     the Free Software Foundation; either version 2 of the License, or
 *     (at your option) any later version.
 * 
 *     This program is distributed in the hope that it will be useful,
 *     but WITHOUT ANY WARRANTY; without even the implied warranty of
 *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *     GNU General Public License for more details.
 * 
 *     You should have received a copy of the GNU General Public License
 *     along with this program; if not, write to the Free Software
 *     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */ 

#include "mutt.h"
#include "sort.h"

#include <string.h>
#include <ctype.h>

/* returns 1 if `a' is a descendant (child) of thread `b' */
static int is_descendant (HEADER *a, HEADER *b)
{
  /* find the top parent of the thread */
  while (a->parent)
    a = a->parent;
  return (a == b);
}

/* This function makes use of the fact that Mutt stores message references in
 * reverse order (i.e., last to first).  This is optiminal since we would like
 * to find the most recent message to which "cur" refers itself.  
 */

static HEADER *find_reference (HEADER *cur, CONTEXT *ctx)
{
  LIST *refs = cur->env->references;
  HEADER *ptr;

  for (; refs; refs = refs->next)
  {
    /* ups, this message is in a reference loop. bad. */
    if (cur->env->message_id && !strcmp (cur->env->message_id, refs->data))
      continue;
    
    if ((ptr = hash_find (ctx->id_hash, refs->data)))
    {
      if (is_descendant (ptr, cur))
	continue;

      return ptr;
    }
  }
  
  return NULL;
}

/* Determines whether to display a message's subject. */
static int need_display_subject (CONTEXT *ctx, HEADER *tree)
{
  HEADER *tmp;

  /* if our subject is different from our parent's, display it */
  if (tree->subject_changed)
    return (1);

  /* if our subject is different from that of our closest previously displayed
   * sibling, display the subject */
  for (tmp = tree->prev; tmp; tmp = tmp->prev)
  {
    if (tmp->virtual >= 0 || (tmp->collapsed && (!ctx->pattern || tmp->limited)))
    {
      if (tmp->subject_changed)
	return (1);
      else
	break;
    }
  }
  
  /* if there is a parent-to-child subject change anywhere between us and our
   * closest displayed ancestor, display the subject */
  for (tmp = tree->parent; tmp; tmp = tmp->parent)
  {
    if (tmp->virtual >= 0 || (tmp->collapsed && (!ctx->pattern || tmp->limited)))
      return (0);
    else if (tmp->subject_changed)
      return (1);
  }
  
  /* if we have no visible parent or previous sibling, display the subject */
  return (1);
}

/* determines whether a later sibling or the child of a later 
 * sibling is displayed.  
 */

static int is_next_displayed (CONTEXT *ctx, HEADER *tree)
{
  int depth = 0;

  if ((tree = tree->next) == NULL)
    return (0);

  FOREVER
  {
    if (tree->virtual >= 0 || (tree->collapsed && (!ctx->pattern || tree->limited)))
      return (1);

    if (tree->child)
    {
      tree = tree->child;
      depth++;
    }
    else
    {
      while (!tree->next && depth > 0)
      {
	tree = tree->parent;
	depth--;
      }
      if ((tree = tree->next) == NULL)
	break;
    }
  }
  return (0);
}


/* Since the graphics characters have a value >255, I have to resort to
 * using escape sequences to pass the information to print_enriched_string().
 * These are the macros M_TREE_* defined in mutt.h.
 *
 * ncurses should automatically use the default ASCII characters instead of
 * graphics chars on terminals which don't support them (see the man page
 * for curs_addch).
 */
void mutt_linearize_tree (CONTEXT *ctx, int linearize)
{
  char *pfx = NULL, *mypfx = NULL, *arrow = NULL, *myarrow = NULL;
  char corner = Sort & SORT_REVERSE ? M_TREE_ULCORNER : M_TREE_LLCORNER;
  int depth = 0, start_depth = 0, max_depth = 0, max_width = 0;
  int nextdisp = 0;
  HEADER *tree = ctx->tree;
  HEADER **array = ctx->hdrs + (Sort & SORT_REVERSE ? ctx->msgcount - 1 : 0);

  /* A NULL tree should never be passed here, but may occur if there is
   * a cycle.  
   */
  if (!tree)
    return;

  FOREVER
  {
    if (tree->virtual >= 0 || (tree->collapsed && (!ctx->pattern || tree->limited)))
      tree->display_subject = need_display_subject (ctx, tree);

    if (depth >= max_depth)
      safe_realloc ((void **) &pfx,
		    (max_depth += 32) * 2 * sizeof (char));

    if (depth - start_depth >= max_width)
      safe_realloc ((void **) &arrow,
		    (max_width += 16) * 2 * sizeof (char));

    safe_free ((void **) &tree->tree);
    if (!depth)
    {
      if (tree->virtual >= 0 || (tree->collapsed && (!ctx->pattern || tree->limited)))
	tree->tree = safe_strdup ("");
    }
    else
    {
      myarrow = arrow + (depth - start_depth - (start_depth ? 0 : 1)) * 2;
      nextdisp = is_next_displayed (ctx, tree);
      
      if (depth && start_depth == depth)
	myarrow[0] = nextdisp ? M_TREE_LTEE : corner;
      else
	myarrow[0] = M_TREE_HIDDEN;
      myarrow[1] = tree->fake_thread ? M_TREE_STAR : M_TREE_HLINE;
      if (tree->virtual >= 0 || (tree->collapsed && (!ctx->pattern || tree->limited)))
      {
	myarrow[2] = M_TREE_RARROW;
	myarrow[3] = 0;
      }

      if (tree->virtual >= 0 || (tree->collapsed && (!ctx->pattern || tree->limited)))
      {
	tree->tree = safe_malloc ((2 + depth * 2) * sizeof (char));
	if (start_depth > 1)
	{
	  strncpy (tree->tree, pfx, (start_depth - 1) * 2);
	  strfcpy (tree->tree + (start_depth - 1) * 2,
		   arrow, (2 + depth - start_depth) * 2);
	}
	else
	  strfcpy (tree->tree, arrow, 2 + depth * 2);
      }
    }

    if (linearize)
    {
      *array = tree;
      array += Sort & SORT_REVERSE ? -1 : 1;
    }

    if (tree->child)
    {
      if (depth)
      {
	mypfx = pfx + (depth - 1) * 2;
	mypfx[0] = nextdisp ? M_TREE_VLINE : M_TREE_SPACE;
	mypfx[1] = M_TREE_SPACE;
      }
      depth++;
      if (tree->virtual >= 0 || (tree->collapsed && (!ctx->pattern || tree->limited)))
        start_depth = depth;
      tree = tree->child;
    }
    else
    {
      while (!tree->next && tree->parent)
      {
	if (tree->virtual >= 0 || (tree->collapsed && (!ctx->pattern || tree->limited)))
	  start_depth = depth;
	tree = tree->parent;
	if (start_depth == depth)
	  start_depth--;
	depth--;
      }
      if (tree->virtual >= 0 || (tree->collapsed && (!ctx->pattern || tree->limited)))
	start_depth = depth;
      if ((tree = tree->next) == NULL)
	break;
    }
  }

  safe_free ((void **) &pfx);
  safe_free ((void **) &arrow);
}

/* inserts `msg' into the list `tree' using an insertion sort.  this function
 * assumes that `tree' is the first element in the list, and not some
 * element in the middle of the list.
 */
static void insert_message (HEADER **tree, HEADER *msg, sort_t *sortFunc)
{
  HEADER *tmp;

  /* NOTE: we do NOT clear the `msg->child' link here because when we do
   * the pseudo-threading, we want to preserve any sub-threads.  So we clear
   * the `msg->child' in the main routine where we know it is safe to do.
   */

  /* if there are no elements in the list, just add it and return */
  if (!*tree)
  {
    msg->prev = msg->next = NULL;
    *tree = msg;
    return;
  }

  /* check to see if this message belongs at the beginning of the list */
  if (!sortFunc || sortFunc ((void *) &msg, (void *) tree) < 0)
  {
    (*tree)->prev = msg;
    msg->next = *tree;
    msg->prev = NULL;
    *tree = msg;
    return;
  }
  
  /* search for the correct spot in the list to insert */
  for (tmp = *tree; tmp->next; tmp = tmp->next)
    if (sortFunc ((void *) &msg, (void *) &tmp->next) < 0)
    {
      msg->prev = tmp;
      msg->next = tmp->next;
      tmp->next->prev = msg;
      tmp->next = msg;
      return;
    }

  /* did not insert yet, so add this message to the end of the list */
  tmp->next = msg;
  msg->prev = tmp;
  msg->next = NULL;
}


/* find the best possible match for a parent mesage based upon subject.
 * if there are multiple matches, the one which was sent the latest, but
 * before the current message, is used. 
 */

static HEADER *find_subject (CONTEXT *ctx, HEADER *cur)
{
  struct hash_elem *ptr;
  HEADER *tmp, *last = NULL;
  ENVELOPE *env = cur->env;
  int hash;

  if (env->real_subj &&
      ((env->real_subj != env->subject) || (!option (OPTSORTRE))))
  {
    hash = hash_string ((unsigned char *) env->real_subj, ctx->subj_hash->nelem);
    for (ptr = ctx->subj_hash->table[hash]; ptr; ptr = ptr->next)
    {
      tmp = ptr->data;
      if (tmp != cur &&			/* don't match the same message */
	  !tmp->fake_thread &&		/* don't match pseudo threads */
	  tmp->subject_changed &&	/* only match interesting replies */
	  !is_descendant (tmp, cur) &&	/* don't match in the same thread */
	  cur->date_sent >= tmp->date_sent &&
	  (!last || (last->date_sent <= tmp->date_sent)) &&
	  tmp->env->real_subj &&
	  mutt_strcmp (env->real_subj, tmp->env->real_subj) == 0)
      {
	last = tmp; /* best match so far */
      }
    }
  }
  return last;
}

static void unlink_message (HEADER **top, HEADER *cur)
{
  if (cur->prev)
  {
    cur->prev->next = cur->next;

    if (cur->next)
      cur->next->prev = cur->prev;
  }
  else
  {
    if (cur->next)
      cur->next->prev = NULL;
    *top = cur->next;
  }
}

static void pseudo_threads (CONTEXT *ctx, sort_t *sortFunc)
{
  HEADER *tree = ctx->tree;
  HEADER *top = tree, *cur, *tmp, *curchild, *nextchild;

  while (tree)
  {
    cur = tree;
    tree = tree->next;
    if ((tmp = find_subject (ctx, cur)) != NULL)
    {
      /* detach this message from it's current location */
      unlink_message (&top, cur);

      cur->subject_changed = 0;
      cur->fake_thread = 1;
      cur->parent = tmp;
      insert_message (&tmp->child, cur, sortFunc);
      
      /* if the message we're attaching has pseudo-children, they
	 need to be attached to its parent, so move them up a level.  */
      for (curchild = cur->child; curchild; )
      {
	nextchild = curchild->next;
	if (curchild->fake_thread)
	{
	  /* detach this message from its current location */
	  unlink_message (&cur->child, curchild);
	  curchild->parent = tmp;
	  insert_message (&tmp->child, curchild, sortFunc);
	}
	curchild = nextchild;
      }
    }
  }
  ctx->tree = top;
}

static HEADER *sort_last (HEADER *top)
{
  HEADER *tree;
  HEADER *tmp;
  HEADER *first;
  HEADER *last;
  HEADER *nextsearch;
  sort_t *usefunc;
  
  usefunc = mutt_get_sort_func (Sort);
  
  tree = top;
  FOREVER
  {
    if (tree->child)
      tree = tree->child;
    else
    {
      while (!tree->next)
      {
	first = last = tree;
	nextsearch = tree->prev;
	first->prev = NULL;
	last->next = NULL;
	while ((tree = nextsearch) != NULL)
	{
          tmp = last;
          nextsearch = nextsearch->prev;
	  while (tmp && (*usefunc) ((void *) &tree->last_sort, 
				    (void *) &tmp->last_sort) < 0)
	    tmp = tmp->prev;
	  if (tmp)
	  {
	    if ((tree->next = tmp->next) != NULL)
	      tmp->next->prev = tree;
	    else
	      last = tree;
	    tmp->next = tree;
	    tree->prev = tmp;
	  }
	  else
	  {
	    tree->next = first;
	    first->prev = tree;
	    first = tree;
	    tree->prev = NULL;
	  }
	}
	if (first->parent)
	{
	  first->parent->child = first;
	  tree = first->parent;
	  if (Sort & SORT_REVERSE)
	  {
	    if ((*usefunc) ((void *) &tree->last_sort,
			    (void *) &first->last_sort) > 0)
	      tree->last_sort = first->last_sort;
	  }
	  else
	  {
	    if ((*usefunc) ((void *) &tree->last_sort,
			    (void *) &last->last_sort) < 0)
	      tree->last_sort = last->last_sort;
	  }
	}
	else
	{
	  top = first;
	  tree = last;
	  break;
	}
      }
      if ((tree = tree->next) == NULL)
	break;
    }
  }
  return top;
}

static void move_descendants (HEADER **tree, HEADER *cur, sort_t *usefunc)
{
  HEADER *ptr, *tmp = *tree;

  while (tmp)
  {
    /* only need to look at the last reference */
    if (tmp->env->references &&
	mutt_strcmp (tmp->env->references->data, cur->env->message_id) == 0)
    {
      /* remove message from current location */
      unlink_message (tree, tmp);

      tmp->parent = cur;
      if (cur->env->real_subj && tmp->env->real_subj)
	tmp->subject_changed = mutt_strcmp (tmp->env->real_subj, cur->env->real_subj) ? 1 : 0;
      else
	tmp->subject_changed = (cur->env->real_subj || tmp->env->real_subj) ? 1 : 0;
      tmp->fake_thread = 0; /* real reference */

      ptr = tmp;
      tmp = tmp->next;
      insert_message (&cur->child, ptr, usefunc);
    }
    else
      tmp = tmp->next;
  }
}

void mutt_clear_threads (CONTEXT *ctx)
{
  int i;

  for (i = 0; i < ctx->msgcount; i++)
  {
    ctx->hdrs[i]->parent = NULL;
    ctx->hdrs[i]->next = NULL;
    ctx->hdrs[i]->prev = NULL;
    ctx->hdrs[i]->child = NULL;
    ctx->hdrs[i]->threaded = 0;
    ctx->hdrs[i]->fake_thread = 0;
  }
  ctx->tree = NULL;
}

HEADER *mutt_sort_subthreads (HEADER *hdr, sort_t *func)
{
  HEADER *top = NULL;
  HEADER *t;
  
  while (hdr)
  {
    t = hdr;
    hdr = hdr->next;
    insert_message (&top, t, func);
    if (t->child)
      t->child = mutt_sort_subthreads (t->child, func);
  }
  return top;
}

void mutt_sort_threads (CONTEXT *ctx, int init)
{
  sort_t *usefunc = NULL;
  HEADER *tmp, *CUR;
  int i, oldsort;
  
  /* set Sort to the secondary method to support the set sort_aux=reverse-*
   * settings.  The sorting functions just look at the value of
   * SORT_REVERSE
   */
  oldsort = Sort;
  Sort = SortAux;
  
  /* get secondary sorting method.  we can't have threads, so use the date
   * if the user specified it
   */
  if ((Sort & SORT_MASK) == SORT_THREADS)
    Sort = (Sort & ~SORT_MASK) | SORT_DATE;
  
  /* if the SORT_LAST bit is set, we save sorting for later */
  if (!(Sort & SORT_LAST))
    usefunc = mutt_get_sort_func (Sort);

  for (i = 0; i < ctx->msgcount; i++)
  {
    CUR = ctx->hdrs[i];

    if (CUR->fake_thread)
    {
      /* Move pseudo threads back to the top level thread so that they can
       * can be moved later if they are descendants of messages that were
       * just delivered.
       */
      CUR->fake_thread = 0;
      CUR->subject_changed = 1;
      unlink_message (&CUR->parent->child, CUR);
      CUR->parent = NULL;
      insert_message (&ctx->tree, CUR, usefunc);
    }
    else if (!CUR->threaded)
    {
      if ((tmp = find_reference (CUR, ctx)) != NULL)
      {
	CUR->parent = tmp;
	if (CUR->env->real_subj && tmp->env->real_subj)
	  CUR->subject_changed = mutt_strcmp (tmp->env->real_subj, CUR->env->real_subj) ? 1 : 0;
	else
	  CUR->subject_changed = (CUR->env->real_subj || tmp->env->real_subj) ? 1 : 0;
      }
      else
	CUR->subject_changed = 1;

      if (!init)
      {
	/* Search the children of `tmp' for decendants of `cur'.  This is only
	 * done when the mailbox has already been threaded since we don't have
	 * to worry about the tree being threaded wrong (because of a missing
	 * parent) during the initial threading.
	 */
	if (CUR->env->message_id)
	  move_descendants (tmp ? &tmp->child : &ctx->tree, CUR, usefunc);
      }
      insert_message (tmp ? &tmp->child : &ctx->tree, CUR, usefunc);
      CUR->threaded = 1;
    }
  }

  if (!option (OPTSTRICTTHREADS))
    pseudo_threads (ctx, usefunc);

  /* now that the whole tree is put together, we can sort by last-* */
  if (Sort & SORT_LAST)
  {
    for (i = 0; i < ctx->msgcount; i++)
      ctx->hdrs[i]->last_sort = ctx->hdrs[i];
    ctx->tree = sort_last (ctx->tree);
  }
  
  /* restore the oldsort order. */
  Sort = oldsort;

  /* Put the list into an array.  If we are reverse sorting, give the
   * offset of the last message, and work backwards (tested for and
   * done inside the function), so that the threads go backwards. 
   * This, of course, means the auxillary sort has to go forwards
   * because we map it backwards here.
   */
  mutt_linearize_tree (ctx, 1);
}

static HEADER *find_virtual (HEADER *cur)
{
  HEADER *top;

  if (cur->virtual >= 0)
      return (cur);

  top = cur;
  if ((cur = cur->child) == NULL)
    return (NULL);

  FOREVER
  {
    if (cur->virtual >= 0)
      return (cur);

    if (cur->child)
      cur = cur->child;
    else if (cur->next)
      cur = cur->next;
    else
    {
      while (!cur->next)
      {
	cur = cur->parent;
	if (cur == top)
	  return (NULL);
      }
      cur = cur->next;
    }
    /* not reached */
  }
}

int _mutt_aside_thread (HEADER *hdr, short dir, short subthreads)
{
  HEADER *tmp;

  if ((Sort & SORT_MASK) != SORT_THREADS)
  {
    mutt_error ("Threading is not enabled.");
    return (hdr->virtual);
  }

  if (!subthreads)
  {
    while (hdr->parent)
      hdr = hdr->parent;
  }
  else
  {
    if ((dir != 0) ^ ((Sort & SORT_REVERSE) != 0))
    {
      while (!hdr->next && hdr->parent)
	hdr = hdr->parent;
    }
    else
    {
      while (!hdr->prev && hdr->parent)
	hdr = hdr->parent;
    }
  }

  if ((dir != 0) ^ ((Sort & SORT_REVERSE) != 0))
  {
    do
    { 
	hdr = hdr->next;
	if (!hdr)
	  return (-1);
	tmp = find_virtual (hdr);
    } while (!tmp);
  }
  else
  {
    do
    { 
	hdr = hdr->prev;
	if (!hdr)
	  return (-1);
	tmp = find_virtual (hdr);
    } while (!tmp);
  }

  return (tmp->virtual);
}

void mutt_set_virtual (CONTEXT *ctx)
{
  int i;

  ctx->vcount = 0;
  ctx->vsize = 0;

#define THIS_BODY cur->content
  for (i = 0; i < ctx->msgcount; i++)
  {
    HEADER *cur = ctx->hdrs[i];
    if (cur->virtual != -1)
    {
      cur->virtual = ctx->vcount;
      ctx->v2r[ctx->vcount] = i;
      ctx->vcount++;
      ctx->vsize += THIS_BODY->length + THIS_BODY->offset - THIS_BODY->hdr_offset;
      cur->num_hidden = mutt_get_hidden (ctx, cur);
    }
  }
#undef THIS_BODY
}

int _mutt_traverse_thread (CONTEXT *ctx, HEADER *cur, int flag)
{
  HEADER *roothdr = NULL, *top;
  int final, reverse = (Sort & SORT_REVERSE), minmsgno;
  int num_hidden = 0, new = 0, old = 0;
  int min_unread_msgno = INT_MAX, min_unread = cur->virtual;
#define CHECK_LIMIT (!ctx->pattern || cur->limited)

  if ((Sort & SORT_MASK) != SORT_THREADS && !(flag & M_THREAD_GET_HIDDEN))
  {
    mutt_error ("Threading is not enabled.");
    return (cur->virtual);
  }

  final = cur->virtual;
  while (cur->parent) 
     cur = cur->parent;
  top = cur;
  minmsgno = cur->msgno;
  

  if (!cur->read && CHECK_LIMIT)
  {
    if (cur->old)
      old = 2;
    else
      new = 1;
    if (cur->msgno < min_unread_msgno)
    {
      min_unread = cur->virtual;
      min_unread_msgno = cur->msgno;
    }
  }

  if (cur->virtual == -1 && CHECK_LIMIT)
    num_hidden++;

  if (flag & (M_THREAD_COLLAPSE | M_THREAD_UNCOLLAPSE))
  {
    cur->pair = 0; /* force index entry's color to be re-evaluated */
    cur->collapsed = flag & M_THREAD_COLLAPSE;
    if (cur->virtual != -1)
    {
      roothdr = cur;
      if (flag & M_THREAD_COLLAPSE)
	final = roothdr->virtual;
    }
  }

  if ((cur = cur->child) == NULL)
  {
    /* return value depends on action requested */
    if (flag & (M_THREAD_COLLAPSE | M_THREAD_UNCOLLAPSE))
      return (final);
    else if (flag & M_THREAD_UNREAD)
      return ((old && new) ? new : (old ? old : new));
    else if (flag & M_THREAD_GET_HIDDEN)
      return (num_hidden);
    else if (flag & M_THREAD_NEXT_UNREAD)
      return (min_unread);
  }
  
  FOREVER
  {
    if (flag & (M_THREAD_COLLAPSE | M_THREAD_UNCOLLAPSE))
    {
      cur->pair = 0; /* force index entry's color to be re-evaluated */
      cur->collapsed = flag & M_THREAD_COLLAPSE;
      if (!roothdr && CHECK_LIMIT)
      {
	roothdr = cur;
	if (flag & M_THREAD_COLLAPSE)
	  final = roothdr->virtual;
      }

      if (reverse && (flag & M_THREAD_COLLAPSE) && (cur->msgno < minmsgno) && CHECK_LIMIT)
      {
	minmsgno = cur->msgno;
	final = cur->virtual;
      }

      if (flag & M_THREAD_COLLAPSE)
      {
	if (cur != roothdr)
	  cur->virtual = -1;
      }
      else 
      {
	if (CHECK_LIMIT)
	  cur->virtual = cur->msgno;
      }
    }


    if (!cur->read && CHECK_LIMIT)
    {
      if (cur->old)
	old = 2;
      else
	new = 1;
      if (cur->msgno < min_unread_msgno)
      {
	min_unread = cur->virtual;
	min_unread_msgno = cur->msgno;
      }
    }

    if (cur->virtual == -1 && CHECK_LIMIT)
      num_hidden++;

    if (cur->child)
      cur = cur->child;
    else if (cur->next)
      cur = cur->next;
    else
    {
      int done = 0;
      while (!cur->next)
      {
	cur = cur->parent;
	if (cur == top)
	{
	  done = 1;
	  break;
	}
      }
      if (done)
	break;
      cur = cur->next;
    }
  }

  /* return value depends on action requested */
  if (flag & (M_THREAD_COLLAPSE | M_THREAD_UNCOLLAPSE))
    return (final);
  else if (flag & M_THREAD_UNREAD)
    return ((old && new) ? new : (old ? old : new));
  else if (flag & M_THREAD_GET_HIDDEN)
    return (num_hidden+1);
  else if (flag & M_THREAD_NEXT_UNREAD)
    return (min_unread);

  return (0);
#undef CHECK_LIMIT
}