#include "geninc.h"            /* LONG, etc. */
/*****************************************************************************
*                                                                            *
*      COMMON OCEANOGRAPHIC DATA ACCESS SYSTEM (CODAS)                       *
*                                                                            *
*      WRITTEN BY:  RAMON CABRERA, ERIC FIRING, and JULIE RANADA             *
*                   JOINT INSTITUTE FOR MARINE AND ATMOSPHERIC RESEARCH      *
*                   1000 POPE ROAD  MSB 312                                  *
*                   HONOLULU, HI 96822                                       *
*                                                                            *
*      VERSION:     3.10                                                     *
*                                                                            *
*      DATE:        APRIL 1989, AUGUST 1995                                  *
*                                                                            *
*****************************************************************************/
/*

    FILE:  sort.c

           Sorting functions.

*/
/*-----------------------------------------------------------------------------

   FUNCTION:  DSRCHGE

      Given a key it returns the index to the first entry in the directory
      with key greater than or equal to the one given.

   PARAMETERS:  
   
      key = pointer to ULONG variable where the key to search for is stored

      key_base = pointer to the first key in the directory
                
      entry_length = pointer to variable containing the size in
                     BYTEs of directory entries
      
      nentries = pointer to variable containing the number of
                 entries in the directory

   RETURNS:  the index to the first entry found with key >= key
             0 if all entries in directory have keys > key
            -1 if all entries have keys < key

   CALLED FROM:  C, FORTRAN

   Modified 8/15/89 - J.R. to return -1 only if all entries have keys < key
   (rather than <=).  This allows calling function search_for_profile_by_time
   to distinguish between these two conditions and signal the difference.

*/
#if PROTOTYPE_ALLOWED
LONG DSRCHGE(ULONG *key, CHAR *key_base, int *entry_length, int *nentries)
#else
LONG DSRCHGE(key, key_base, entry_length, nentries)
ULONG *key;
CHAR *key_base;
int *entry_length, *nentries;
#endif
#define KEY(x) *( (ULONG *) (key_base + (x) * (*entry_length)) )
{
   int i1, i2, im, il;

   if (* (ULONG *) key_base >= *key) return(0);
   if (KEY(*nentries - 1) <  *key) return(-1);   /* jr- */
   if (KEY(*nentries - 1) == *key) return(*nentries - 1);     /* jr+ */
   i1 = il = 0;
   i2 = *nentries - 1;
   im = (i1 + i2) / 2;
   while (il != im)       /* binary search */
   {
      if (KEY(im) >= *key)
         if (KEY(im - 1) < *key) return(im);
         else im = ((i2 = il = im) + i1) / 2;   /* search top half */
      else im = ((i1 = il = im) + i2) / 2;      /* search bottom half */
   }
   return(i2);
}

/*-----------------------------------------------------------------------------

   FUNCTION:  dir_search_GE_file

      Given a key it returns the index to the first entry in the directory
      with key greater or equal than the one given.

      This function differs from DSRCHGE in that the directory is in a file,
      not in memory.

   PARAMETERS:

      fp = file pointer for directory file
          
      key = key to search for

      key_base = offset from beginning of file of first key in the directory

      entry_length = size in BYTEs of a directory entry

      nentries = number of entries in directory

   RETURNS:  the index to the first entry found with key >= key
             0 if all entries in directory have keys > key
             -1 if all entries have keys < key
             <-1 if an i/o error occurs

   CALLED FROM:  C, FORTRAN

   Modified 8/15/89 - J.R. to return -1 only if all entries have keys < key
   (rather than <=).  This allows calling function search_for_profile_by_time
   to distinguish between these two conditions and signal the difference.

*/
#if PROTOTYPE_ALLOWED
int dir_search_GE_file(FILE *fp, ULONG key, ULONG key_base, int entry_length,
                       int nentries, int from, int to)
#else
int dir_search_GE_file(fp, key, key_base, entry_length, nentries, from, to)
FILE *fp;
int entry_length, nentries, from, to;
ULONG key, key_base;
#endif
{
   int i1, i2, im, il;
   ULONG ofs;

   if (read_long(fp, key_base, from, to) >= key) return(0);
   i2 = nentries - 1;
   if (read_long(fp, key_base + i2 * entry_length, from, to) <  key) return(-1); /* jr- */
   if (read_long(fp, key_base + i2 * entry_length, from, to) == key) return(i2); /* jr+ */
   i1 = il = 0;
   im = (i1 + i2) / 2;
   while (il != im)
   {
      if (read_long(fp, (ofs = key_base + im * entry_length), from, to) >= key)
         if (read_long(fp, ofs - entry_length, from, to) < key) return(im);
         else im = ((i2 = il = im) + i1) / 2;
      else im = ((i1 = il = im) + i2) / 2;
   }
   return(i2);
}

/*-----------------------------------------------------------------------------

   FUNCTION:  DSORTAS

      It sorts a directory into ascending order by time using the heapsort
      algorithm.

   PARAMETERS:
   
      dir_base = pointer to directory structure (not necessarily the same
                 as key_base)

      key_base = pointer to the first key in the directory

      entry_length = pointer to ULONG variable containing the size in BYTEs
                     of a directory entry

      nentries = pointer to ULONG variable containing the number of entries 
                 in the directory

   RETURNS:  VOID

   CALLED FROM:  C, FORTRAN

*/
#if PROTOTYPE_ALLOWED
void DSORTAS(CHAR *dir_base, CHAR *key_base, int *entry_length, int *nentries)
#else
void DSORTAS(dir_base, key_base, entry_length, nentries)
CHAR *dir_base, *key_base;
int *entry_length, *nentries;
#endif
{
   int i, i1, j, n, *ind;
   CHAR *e1, *e2, *temp_entry;

   if ((*nentries) < 2) return;
   ind = (int *) malloc( (*nentries) * sizeof(int));
   temp_entry = (CHAR *) malloc( (*entry_length) );
   sort_dir_index((*nentries), ind, key_base, (*entry_length) );
   n = 0;
   for (i1=0; i1<(*nentries); i1++)
   {
      j = ind[(i = i1)];
      if (j >= 0)
      {
         if (i != j)
         {
            while (ind[j] >= 0)
            {
               e1 = dir_base + i * (*entry_length);
               e2 = dir_base + j * (*entry_length);
               move_byte(e1, temp_entry,  (*entry_length) );
               move_byte(e2, e1,  (*entry_length) );
               move_byte(temp_entry, e2,  (*entry_length) );
               ind[i] = -1;
               i = j;
               j = ind[i];
               n++;
            }
            ind[i] = -1;
            n++;
         }
         if (n >= (*nentries))
         {
            free(ind);
            free(temp_entry);
            return;
         }
      }
   }
   free(ind);
   free(temp_entry);
   return;
}

/*-----------------------------------------------------------------------------

   FUNCTION:  sort_dir_index

      It is an auxiliary function to DSORTAS and does the actual sorting
      of the directory using the heapsort algorithm.  An index array is
      used to store the order in which the elements should be sorted.

      (c) 1986 Numerical Recipes Software
      Reproduced by permission, from the book Numerical Recipes:
      The Art of Scientific Computing, published by Cambridge
      University Press

      This routine is translated from the Pascal routine
      given in Numerical Recipes:

         PROCEDURE indexx(n: integer; arrin: glsarray; VAR indx: gliarray);
         (* Programs using routine INDEXX must define the types
         TYPE
            glsarray = ARRAY [1..np] OF real;
            gliarray = ARRAY [1..np] OF integer;
         in the main routine, with np >= n.   *)
            l,j,ir,indxt,i: integer;
            q: real;

      Translation by Eric Firing, Sept. 13, 1987.

      indexx() is based on the heapsort algorithm.
      The calling routine supplies pointers to the
      start of an array of numbers to be sorted, and
      to the start of an integer index array.  indexx()
      fills the index array, and then rearranges it so
      that it contains the indices, in order of the sorted
      elements in arrin.

      sort_dir_index() is a simple adaptation of indexx(),
      using the definition _key(i) in place of the key array.

   PARAMETERS:

      n = the number of entries in the directory

      indx = the index array in which the correct order of directory
             entries will be stored

      key_base = pointer to first key in the directory

      entry_length = size in bytes of a directory entry

*/
#if PROTOTYPE_ALLOWED
void sort_dir_index(int n, int *indx, CHAR *key_base, int entry_length)
#else
void sort_dir_index(n, indx, key_base, entry_length)
int n, *indx, entry_length;
CHAR *key_base;
#endif
#define _key(ii) ( *( (LONG *) (key_base+(entry_length)*(ii)) ) )
{
   int l,j,ir,indxt,i;
   LONG q;   /* ef: used to be float */

   for (j=0; j<n; j++) indx[j] = j;
   l = (n / 2) ;
   ir = n-1;
   while (1) 
   {
      if (l > 0)  
      {
         indxt = indx[--l];
         q = _key(indxt);
      } 
      else 
      {
         indxt = indx[ir];
         q = _key(indxt);
         indx[ir--] = indx[0];
         if (ir == 0)
         {
            indx[0] = indxt;
            return;                             /* This is the only exit. */
         }
      }
      i = l;
      j = l+l+1;
      while (j <= ir)  
      {
         if (j < ir)  
            if (_key(indx[j]) < _key(indx[j+1])) j++;
         if (q < _key(indx[j]))  
         {
            indx[i] = indx[j];
            i = j;
            j += j+1;
         } 
         else j = ir + 1;
      }
      indx[i] = indxt;
   }
}

/*-----------------------------------------------------------------------------

   FUNCTION:  read_long

      It returns a long integer read at a given offset into a file.

   PARAMETERS:

      fp = pointer to file to read from

      ofs = offset into file from which to start reading long integer

   RETURNS:  the long integer read, if successful
             SEEK_ERROR or READ_ERROR otherwise

   NOTE:  there is really no way that the calling function would be able
          to distinguish from the return value whether a SEEK or READ
          error has occurred--we could change this to read_ulong (since
          the calling f'n above dir_srch_GE_file really wants a ULONG)
          if a problem ever arises

   CALLED FROM:  C

*/
#if PROTOTYPE_ALLOWED
LONG read_long(FILE *fp, long ofs, int from, int to)
#else
LONG read_long(fp, ofs, from, to)
FILE *fp;
long ofs;
int from, to;
#endif
{
   LONG long_value;

   if (fseek(fp, ofs, 0)) return(SEEK_ERROR);
   if ((fread((char *)&long_value, 1, sizeof(LONG), fp)) != sizeof(LONG))
      return(READ_ERROR);
   if (from != to)
      convert_array_long((char *)&long_value, (char *)&long_value, from, to, 1);
   return(long_value);
}


