/*---------------------------------------------------------------*/
/*   Copyright (c) 1992 Regents of the University of California  */
/*                 All Rights Reserved                           */
/*-------------------------- ------------------------------------*/
/*
      @(#)BufVarSorts.c	1.3  (UCLA, IGPP) 20 Apr 1994 
*/
/*---------------------------------------------------------------
  BufVarSortSublist(int start, int stop, char* columns[]) -
    Uses a mergesort, which is a sort that dones not require indexing
    of the buffer list items, which is a lot more memory freindly.  
    It is a N*log(N) operation, and nearly as fast a QuickSort, and
    better in some case.  
    The function sort on the first column, and does supplimental sorts 
    on the remaining columns.
    WARNING: this function is not fully tested.
 
  Return:
     
        
  Entry Requirements:
    int   start:     first record.
    int   stop:      last record.
    char* columns[]: list of columns name, terminaled by a NULL string.
 
  Development History:
    Began: 09/17/93 - Gilbert Hyatt.
    Edited:04/14/94 - Gilbert Hyatt 
      Now uses pipec.h as entry point into the library.
  ---------------------------------------------------------------*/
#include <malloc.h>
#include "pipec.h"

#define  MAXARGS     100

extern BUFFER_HEAD  _Rbuffer;
extern char         *Rbuffer;
extern DESC         Desc[];

char   *ColList[MAXARGS];
int    ColNumb[MAXARGS];
double buffgetcolval();

RECPTR *z;


/************** Comparison Function ***********/
compare(entry1, entry2)
RECPTR *entry1;
RECPTR *entry2;
{
  int         index;
  double      value1, value2;
  int         i, dnum;
 
  union pair {  
    int ival;
    float fval;
    double dval;
    char text[sizeof(double)];
  } pairs;

  for (index = 0; ColList[index] != NULL; index++) { 
    if (! exists(ColList[index]) )      continue;
    if (coltype(ColList[index]) == 'A') continue;
    dnum = ColNumb[index] -1;
    if (entry1 == NULL || entry1 == _Rbuffer.end || entry1 == z) return(1);
    if (entry2 == NULL || entry2 == _Rbuffer.end || entry1 == z) return(-1);

    Rbuffer = BufMapData(entry1);
    if (isflag(ColList[index])) return(1);
    value1 = buffgetcolval(Rbuffer, ColList[index]);

    Rbuffer = BufMapData(entry2);
    if (isflag(ColList[index])) return(-1);  
    value2 = buffgetcolval(Rbuffer, ColList[index]);
			   
    if (value1 > value2) return(1);
    if (value1 < value2) return(-1);
  }  /* end of for */
  return(0);
}  /* end of compare */


/********** Start of MergeSort ********************/
RECPTR* 
merge(a, b)
RECPTR *a;
RECPTR *b;
{
  RECPTR *c;
  
  c = z;
  do
    if (compare(b, a) >= 0) {c->next = a; c = a; a = a->next; }
    else                    {c->next = b; c = b; b = b->next; }
  while (c != z);
  c = z->next;
  z->next = z;
  return c;
}  /* end of merge */


/***********  Recursive Part *****************/
RECPTR* 
mergesort(c)
RECPTR *c;
{
  RECPTR *a, *b;
  if (c->next != z) {
    a = c; b = c->next->next->next;
    while (b != z) {c = c->next; b = b->next->next; }
    b = c->next; c->next = z;
    return merge(mergesort(a), mergesort(b));
  } /* end of if */
  return c;
}  /* end of mergesort (Recursive Version) */


/****************  Main Function of BufVarSort()  *****************/
BufVarSort(columns)
char *columns[];
{
  extern BUFFER_HEAD _Rbuffer;
  char    *TMP_Rbuffer;
  RECPTR  *oldlastnext, *ptr;
  int     index;

  _Rbuffer.num_current = _Rbuffer.num_last_req = _Rbuffer.num_lastVMrec = BufNoValue;

  for (index = 0; columns[index] != NULL; index++) {
    ColList[index] = columns[index];
    ColNumb[index] = colnum(columns[index]);
  }  /* ned of for */

  z = (RECPTR *) BufMalloc(sizeof(RECPTR));
  z->next = z;
  oldlastnext = _Rbuffer.last->next;
  _Rbuffer.last->next = z;

  TMP_Rbuffer = Rbuffer;
  _Rbuffer.first = mergesort(_Rbuffer.first);
  Rbuffer     = TMP_Rbuffer;

  for (ptr = _Rbuffer.first; ptr != z;  ptr = ptr->next) _Rbuffer.last = ptr;
  _Rbuffer.last->next = oldlastnext;
  _Rbuffer.end->next   = _Rbuffer.first;

  free(z);
  return(TRUE);
}  /* end of BufVarSort() */


/**************** Main Function of BufVarSortSublist ********************/
BufVarSortSublist(start, stop, columns)
int  start;
int  stop;
char *columns[];
{
  extern BUFFER_HEAD _Rbuffer;
  char    *TMP_Rbuffer;
  RECPTR  *before, *after, *last, *ptr;
  int     index;

  start = (start < 1)?1:start;
  stop  = (stop > _Rbuffer.nrecs)?_Rbuffer.nrecs:stop;
  if (start == stop) return(TRUE);
  if (start >  stop) return(FALSE);

  _Rbuffer.num_current = _Rbuffer.num_last_req = _Rbuffer.num_lastVMrec = BufNoValue;

  for (index = 0; columns[index] != NULL; index++) {
    ColList[index] = columns[index];
    ColNumb[index] = colnum(columns[index]);
  }  /* ned of for */


  z = (RECPTR *) BufMalloc(sizeof(RECPTR));
  z->next = z;

  before = _Rbuffer.end;
  for (index = 1; index < start; index++)    before = before->next;
  last = before;
  for (index = start; index <= stop; index++) last   = last->next;
  after = last->next;
  last->next = z;

  TMP_Rbuffer = Rbuffer;
  before->next = mergesort(before->next);
  Rbuffer     = TMP_Rbuffer;

  for (ptr = before->next; ptr != z;  ptr = ptr->next) last = ptr;
  last->next   = after;

  if (start == 1)              _Rbuffer.first     = before->next;
  if (stop  == _Rbuffer.nrecs) _Rbuffer.last      = last;
  
  free(z);
  return(TRUE);
}  /* end of BufVarSort() */
