/***             analog 4.13             http://www.analog.cx/             ***/
/*** This program is copyright (c) Stephen R. E. Turner 1995 - 2000 except as
 *** stated otherwise. Distribution, usage and modification of this program is
 *** subject to the conditions of the Licence which you should have received
 *** with it. This program comes with no warranty, expressed or implied.   ***/
/*** sort.c; sort a hashindex tree into a list by some criterion ***/
#include "anlghea3.h"
#define FINDNAME(p) ((rep >= 0)?(maketreename(partname, (p), newpn, space, need, rep, FALSE)):((p)->name))
void my_sort(Hashindex **gooditems, Hashindex **baditems, Strlist *partname,
	     Strlist **newpn, Strlist *space, size_t need, choice rep,
	     Floor *floor, choice sortby, logical alphaback, Include *wanthead,
	     choice requests, choice date, unsigned long totr,
	     unsigned long totp, double totb, unsigned long maxr,
	     unsigned long maxp, double maxb) {
  Hashindex *ans, *ans2, *p, *nextp, *q, *lastq = NULL;
  unsigned long min = 0;
  double mind;
  choice filterby;
  logical goods;
  unsigned long count;
  /* we do a different sort depending whether the floor is +ve or -ve */
  mind = floor->min;
  filterby = floor->floorby;
  if (filterby == REQUESTS) {
    filterby = requests;
    if (floor->qual == '%')
      mind *= (double)totr / 100.0;  /* NB mind < 0 => qual == '\0' */
    else if (floor->qual == ':')
      mind *= (double)maxr / 100.0;
    min = (unsigned long)(mind + 1 - EPSILON);
  }
  else if (filterby == PAGES) {
    if (floor->qual == '%')
      mind *= (double)totp / 100.0;
    else if (floor->qual == ':')
      mind *= (double)maxp / 100.0;
    min = (unsigned long)(mind + 1 - EPSILON);
  }
  else if (filterby == BYTES) {
    if (floor->qual == '%')
      mind *= totb / 100.0;
    else if (floor->qual == ':')
      mind *= maxb / 100.0;
    else if (floor->qual == 'k')
      mind *= 1024.0;
    else if (floor->qual == 'M')
      mind *= 1024.0 * 1024.0;
    else if (floor->qual == 'G') {
      mind *= 1024.0 * 1024.0;
      mind *= 1024.0;
    }    
    else if (floor->qual == 'T') {
      mind *= 1024.0 * 1024.0;
      mind *= 1024.0 * 1024.0;
    }
  }
  else { /* filterby == DATESORT */
    filterby = date;
    min = (unsigned long)(mind + 1 - EPSILON);
  }
  ans = NULL;
  ans2 = NULL;
  if (mind < 0) {   /* insertion sort, small end first for speed */
    count = (unsigned long)(-mind + EPSILON);
    if (*gooditems != NULL) {
      p = *gooditems;
      goods = TRUE;
    }
    else {
      p = *baditems;
      goods = FALSE;
    }
    for ( ; p != NULL; p = nextp) {
      nextp = p->next;  /* need this because will overwrite p->next */
      if (nextp == NULL && goods) {
	nextp = *baditems;
	goods = FALSE;
      }
      /* The 2nd - 5th lines of the following expression are not strictly
	 needed. But by making one extra comparison now we can often save
	 the work in testing whether the name is included(). */
      /* NB If count == 0, ans != NULL */
      if (p->own == NULL || p->own->data[requests] == 0 ||
	  (count == 0 &&
	   ((filterby != BYTES && p->own->data[filterby] <=
	     ans->own->data[filterby]) ||
	    (filterby == BYTES && p->own->bytes <= ans->own->bytes)))
	  || !included(FINDNAME(p), p->own->ispage, wanthead)) {
	/* not wanted */
	p->next = ans2;
	ans2 = p;
      }
      else {
	if (filterby == BYTES) {
	  for (q = ans; q != NULL && p->own->bytes > q->own->bytes;
	       TO_NEXT(q))
	    lastq = q;   /* run to right place in emerging list */
	}
	else {
	  for (q = ans; q != NULL &&
	       p->own->data[filterby] > q->own->data[filterby];
	       TO_NEXT(q))
	    lastq = q;
	}
	if (q == ans) {  /* at beginning of list */
	  if (count > 0) {     /* list still not big enough */
	    p->next = ans;
	    ans = p;
	    count--;
	  }
	  else {
	    p->next = ans2;
	    ans2 = p;
	  }
	}
	else {
	  p->next = lastq->next;
	  lastq->next = p;
	  if (count == 0) {
	    lastq = ans; /* temporarily re-using lastq for old ans */
	    ans = ans->next;
	    lastq->next = ans2;
	    ans2 = lastq;
	  }
	  else
	    count--;
	}
      }
    }
    if (sortby == floor->floorby || sortby == RANDOM) {
      /* swap the list round so that the largest item is first */
      q = NULL;  /* q is last p */
      for (p = ans; p != NULL; p = nextp) {
	nextp = p->next;
	p->next = q;
	q = p;
      }
      ans = q;
    }
    else {
      count = 0;
      for (p = ans; p != NULL; TO_NEXT(p))
	count++;
      if (count > 0) {
	if (sortby == BYTES)
	  ans = my_mergesort(ans, count, sortby, &mergeb);
	else if (sortby == ALPHABETICAL) {
	  if (alphaback)
	    reversenames(ans);
	  ans = my_mergesort(ans, count, sortby, &mergea);
	}
	else if (sortby == REQUESTS)
	  ans = my_mergesort(ans, count, requests, &merge);
	else if (sortby == PAGES)
	  ans = my_mergesort(ans, count, PAGES, &merge);
	else /* sortby == DATESORT */
	  ans = my_mergesort(ans, count, date, &merge);
	/* it's possible that the list has acquired some trailing junk which
	   we have to lop off */
	for (p = ans; count > 1; TO_NEXT(p))
	  count--;
	p->next = NULL;
	if (alphaback && sortby == ALPHABETICAL)
	  reversenames(ans);
      }
    }
  }
  else {   /* mind >= 0; use mergesort */
    /* string the wanted ones into a list */
    count = 0;
    if (mind <= 0.5) {
      filterby = requests;
      min = 1;  /* so as to include exactly those items with any requests */
    }
    if (*gooditems != NULL) {
      p = *gooditems;
      goods = TRUE;
    }
    else {
      p = *baditems;
      goods = FALSE;
    }
    for ( ; p != NULL; p = nextp) {
      nextp = p->next;
      if (nextp == NULL && goods) {
	nextp = *baditems;
	goods = FALSE;
      }
      if ((p->own != NULL) &&
	  ((filterby != BYTES && p->own->data[filterby] >= min) ||
	   (filterby == BYTES && p->own->bytes >= mind)) &&
	  (included(FINDNAME(p), p->own->ispage, wanthead))) {
	p->next = ans;
	ans = p;
	count++;
      }
      else {
	p->next = ans2;
	ans2 = p;
      }
    }
    if (sortby == RANDOM)
      ;  /* do nothing: we're done */
    else if (count > 0) {
      if (sortby == BYTES)
	ans = my_mergesort(ans, count, sortby, &mergeb);
      else if (sortby == ALPHABETICAL) {
	if (alphaback)
	  reversenames(ans);
	ans = my_mergesort(ans, count, sortby, &mergea);
      }
      else if (sortby == REQUESTS)
	ans = my_mergesort(ans, count, requests, &merge);
      else if (sortby == PAGES)
	ans = my_mergesort(ans, count, PAGES, &merge);
      else /* sortby == DATESORT */
	ans = my_mergesort(ans, count, date, &merge);
      /* it's possible that the list has acquired some trailing junk which
	 we have to lop off */
      for (p = ans; count > 1; TO_NEXT(p))
	count--;
      p->next = NULL;
      if (alphaback && sortby == ALPHABETICAL)
	reversenames(ans);
    }
    else
      ans = NULL;
  }
  *gooditems = ans;
  *baditems = ans2;
}
Hashindex *my_mergesort(Hashindex *list, unsigned long length, choice sortby,
			mergefnp mergefn) {
  Hashindex *ans, *p, *p1, *p2;
  unsigned long a, count;
  if (length <= 1)
    return(list);
  a = length / 2;
  count = a;
  for (p = list; count > 0; TO_NEXT(p))
    count--;    /* find the halfway point of the list */
  p1 = my_mergesort(list, a, sortby, mergefn);
  p2 = my_mergesort(p, length - a, sortby, mergefn);
  ans = mergefn(p1, p2, a, length - a, sortby);
  return(ans);
  /* NB may have trailing junk, but we can lop that off when we've returned,
     so as not to do it for each sub-sort */
}
Hashindex *merge(Hashindex *list1, Hashindex *list2, unsigned long length1,
		 unsigned long length2, choice sortby) {
  Hashindex *ans, *p1, *p2, *p3;
  if (list1->own->data[sortby] > list2->own->data[sortby]) {
    ans = list1;
    p1 = list1->next;
    p2 = list2;
    length1--;
  }
  else {
    ans = list2;
    p2 = list2->next;
    p1 = list1;
    length2--;
  }
  p3 = ans;
  while (length1 > 0 && length2 > 0) {
    if (p1->own->data[sortby] > p2->own->data[sortby]) {
      p3->next = p1;
      TO_NEXT(p3);
      TO_NEXT(p1);
      length1--;
    }
    else {
      p3->next = p2;
      TO_NEXT(p3);
      TO_NEXT(p2);
      length2--;
    }
  }
  if (length1 > 0)
    p3->next = p1;
  else
    p3->next = p2;
  return(ans);
}
Hashindex *mergea(Hashindex *list1, Hashindex *list2, unsigned long length1,
		  unsigned long length2, choice sortby) {
  Hashindex *ans, *p1, *p2, *p3;
  if (strcmp(list1->name, list2->name) < 0) {
    ans = list1;
    p1 = list1->next;
    p2 = list2;
    length1--;
  }
  else {
    ans = list2;
    p2 = list2->next;
    p1 = list1;
    length2--;
  }
  p3 = ans;
  while (length1 > 0 && length2 > 0) {
    if (strcmp(p1->name, p2->name) < 0) {
      p3->next = p1;
      TO_NEXT(p3);
      TO_NEXT(p1);
      length1--;
    }
    else {
      p3->next = p2;
      TO_NEXT(p3);
      TO_NEXT(p2);
      length2--;
    }
  }
  if (length1 > 0)
    p3->next = p1;
  else
    p3->next = p2;
  return(ans);
}
Hashindex *mergeb(Hashindex *list1, Hashindex *list2, unsigned long length1,
		  unsigned long length2, choice sortby) {
  Hashindex *ans, *p1, *p2, *p3;
  if (list1->own->bytes > list2->own->bytes) {
    ans = list1;
    p1 = list1->next;
    p2 = list2;
    length1--;
  }
  else {
    ans = list2;
    p2 = list2->next;
    p1 = list1;
    length2--;
  }
  p3 = ans;
  while (length1 > 0 && length2 > 0) {
    if (p1->own->bytes > p2->own->bytes) {
      p3->next = p1;
      TO_NEXT(p3);
      TO_NEXT(p1);
      length1--;
    }
    else {
      p3->next = p2;
      TO_NEXT(p3);
      TO_NEXT(p2);
      length2--;
    }
  }
  if (length1 > 0)
    p3->next = p1;
  else
    p3->next = p2;
  return(ans);
}