/* @(#)tz9.c	17.1.1.1 (ES0-DMD) 01/25/02 17:36:46 */
/*===========================================================================
  Copyright (C) 1995 European Southern Observatory (ESO)
 
  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 Massachusetss Ave, Cambridge, 
  MA 02139, USA.
 
  Corresponding concerning ESO-MIDAS should be addressed as follows:
	Internet e-mail: midas@eso.org
	Postal address: European Southern Observatory
			Data Management Division 
			Karl-Schwarzschild-Strasse 2
			D 85748 Garching bei Muenchen 
			GERMANY
===========================================================================*/

/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.TYPE   	Module
.NAME    	tz9.c
.LANGUAGE 	C
.AUTHOR  	J.D.Ponz  IPG-ESO Garching
.CATEGORY 	table interface (Design 2.0) low level routines.
.COMMENTS  	This module contains the lower level routines handling tables.
		Search routines.

.VERSION 1.0 	25-Jan-1989   Definition JDP
.VERSION 3.0 	01-Jul-1990   New Version with Arrays / Elementary IO
.VERSION 4.0    10-Sep-1992   Correct bug in Binary search: looks now for
                              the first value and not the closest one MP
------------------------------------------------------------*/

#include <midas_def.h>		/* General MIDAS Symbols	*/
#include <tblsys.h>		/* Table System parameters	*/
#include <tbldef.h>		/* Symbols used for Tables	*/

#include <macrogen.h>		/* Classical macros		*/

/*=======================================================================*/

int TBL_SSI1(data, value, error, count, incr)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Sequential Search for a value with error, i*1 data.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
-------------------------------------------------------------*/
	char     *data          /* IN: data array  			*/;
	int     value          /* IN: value to look for		*/;
	int     error          /* IN: tolerance 			*/;
	int     count          /* IN: number of elements to test	*/;
	int     incr		/* IN: How to move to next value	*/;
{
	char	*p, *pe;
	int	rval;

  for (p = data, pe = p + count*incr; p<pe; p += incr) {
	rval = *p - value;
	if (rval < 0)	rval = -rval;
	if (rval <= error)	break;
  }
  return (p < pe ? (p-data)/incr : -1L);
}

int TBL_SSI2(data, value, error, count, incr)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Sequential Search for a value with error, i*2 data.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
-------------------------------------------------------------*/
	short	*data     	/* IN: data array  			*/;
	int     value          /* IN: value to look for		*/;
	int     error          /* IN: tolerance 			*/;
	int     count          /* IN: number of elements to test	*/;
	int     incr		/* IN: How to move to next value	*/;
{
	short	*p, *pe;
	int	rval;

  for (p = data, pe = p + count*incr; p<pe; p += incr) {
	rval = *p - value;
	if (rval < 0)	rval = -rval;
	if (rval <= error)	break;
  }
  return (p < pe ? (p-data)/incr : -1L);
}

int TBL_SSI4(data, value, error, count, incr)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Sequential Search for a value with error, i*4 data.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
-------------------------------------------------------------*/
	int	*data     	/* IN: data array  			*/;
	int     value          /* IN: value to look for		*/;
	int     error          /* IN: tolerance 			*/;
	int     count          /* IN: number of elements to test	*/;
	int     incr		/* IN: How to move to next value	*/;
{
	int	*p, *pe;
	int	rval;

  for (p = data, pe = p + count*incr; p<pe; p += incr) {
	rval = *p - value;
	if (rval < 0)	rval = -rval;
	if (rval <= error)	break;
  }
  return (p < pe ? (p-data)/incr : -1L);
}

int TBL_SSR(data, value, error, count, incr)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Sequential Search for a value with error, r*4 data.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
-------------------------------------------------------------*/
	float	*data     	/* IN: data array  			*/;
	double	 value 		/* IN: value to look for		*/;
	double	 error          /* IN: tolerance 			*/;
	int     count          /* IN: number of elements to test	*/;
	int     incr		/* IN: How to move to next value	*/;
{
	float	*p, *pe, rval;

  for (p = data, pe = p + count*incr; p<pe; p += incr) {
	rval = *p - value;
	if (rval < 0)	rval = -rval;
	if (rval <= error)	break;
  }
  return (p < pe ? (p-data)/incr : -1L);
}

int TBL_SSD(data, value, error, count, incr)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Sequential Search for a value with error, r*8 data.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
-------------------------------------------------------------*/
	double	*data     	/* IN: data array  			*/;
	double	 value          /* IN: value to look for		*/;
	double	 error          /* IN: tolerance 			*/;
	int     count          /* IN: number of elements to test	*/;
	int     incr		/* IN: How to move to next value	*/;
{
	double	*p, *pe, rval;

  for (p = data, pe = p + count*incr; p<pe; p += incr) {
	rval = *p - value;
	if (rval < 0)	rval = -rval;
	if (rval <= error)	break;
  }
  return (p < pe ? (p-data)/incr : -1L);
}

int TBL_SSC(data, value, start, ncomp, count, incr)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Sequential Search for a string.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
-------------------------------------------------------------*/
	char  	*data 	/* IN: data array  			*/;
	char	*value 	/* IN: string to look for		*/;
	int     start	/* IN: where in the char string		*/;
	int     ncomp	/* IN: how many bytes to compare	*/;
	int     count	/* IN: number of elements to test	*/;
	int     incr	/* IN: How to move to next value	*/;
{
	char	*p, *pe;

  for (p = data + (start-1), pe = p + count*incr; 
  	p<pe; p += incr) {
	if (oscomp(p, value, ncomp) == 0)	break;
  }
  return (p < pe ? (p-data)/incr : -1L);
}

/*  */

int TBL_BSI1(data, value, error, count, tonext)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Binary Search for a value with error, i*1 data.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
.REMARKS When tonext>0, the values are assumed to be in INCREASING sequence,
		and DECREASING sequence when tonext<0 .
-------------------------------------------------------------*/
	char     *data          /* IN: data array  			*/;
	int     value          /* IN: value to look for		*/;
	int     error          /* IN: tolerance 			*/;
	int     count          /* IN: number of elements to test	*/;
	int     tonext		/* IN: How to move to next LARGER value	*/;
{
	char	*low, *high, *mid, *p;
	int 	rval, rval1;
	int	i, incr;

  if (count <= 0)	return(-1L);
  incr = ABSOLUTE(tonext);

  low  = data;
  high = low + count*incr;
  
  while (low <= high) {
	i = (high-low)/(2*incr);
	mid   = low + i*incr;
	rval1 = value - *mid;
	rval  = ABSOLUTE(rval1);
	if (rval < 0) rval = -rval;
	if (rval <= error ) {	/* find value with minimum deviation */
		for (p= mid; p >= data; p -= 1) {
			rval1 = *p - value;
                        rval = ABSOLUTE(rval1) ;
			if (rval > error) break;
		}
		mid = p+1 ;
		break;
	}
	if (tonext*rval1 < 0)  	/* Have to move  <<====	*/
		high = mid - incr;
	else			/* Have to move  ====>>	*/
		low  = mid + incr;
  }
    
  return (low <= high ? (mid-data)/incr : -1L);  /* M.P 210291 */
}

int TBL_BSI2(data, value, error, count, tonext)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Binary Search for a value with error, i*2 data.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
.REMARKS When tonext>0, the values are assumed to be in INCREASING sequence,
		and DECREASING sequence when tonext<0 .
-------------------------------------------------------------*/
	short	*data 		/* IN: data array  			*/;
	int     value          /* IN: value to look for		*/;
	int     error          /* IN: tolerance 			*/;
	int     count          /* IN: number of elements to test	*/;
	int     tonext		/* IN: How to move to next LARGER value	*/;
{
	short	*low, *high, *mid, *p;
	int 	rval, rval1;
	int	i, incr;

  if (count <= 0)	return(-1L);
  incr = ABSOLUTE(tonext);

  low  = data;
  high = low + count*incr;

  while (low <= high) {
	i = (high-low)/(2*incr);
	mid   = low + i*incr;
	rval1 = value - *mid;
	rval  = ABSOLUTE(rval1);
	if (rval < 0) rval = -rval;
	if (rval <= error ) {	/* find value with minimum deviation */
		for (p= mid; p >= data; p -= 1) {
			rval1 = *p - value;
                        rval = ABSOLUTE(rval1) ;
			if (rval > error) break;
		}
		mid = p+1 ;
		break;
	}
	if (tonext*rval1 < 0)  	/* Have to move  <<====	*/
		high = mid - incr;
	else			/* Have to move  ====>>	*/
		low  = mid + incr;
  }
    
  return (low <= high ? (mid-data)/incr : -1L);  /* M.P 210291 */
  }
    

int TBL_BSI4(data, value, error, count, tonext)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Binary Search for a value with error, i*4 data.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
.REMARKS When tonext>0, the values are assumed to be in INCREASING sequence,
		and DECREASING sequence when tonext<0 .
-------------------------------------------------------------*/
	int	*data 		/* IN: data array  			*/;
	int     value          /* IN: value to look for		*/;
	int     error          /* IN: tolerance 			*/;
	int     count          /* IN: number of elements to test	*/;
	int     tonext		/* IN: How to move to next LARGER value	*/;
{
	int	*low, *high, *mid, *p;
	int 	rval, rval1;
	int	i, incr;

  if (count <= 0)	return(-1L);
  incr = ABSOLUTE(tonext);

  low  = data;
  high = low + count*incr;
  while (low <= high) {
	i = (high-low)/(2*incr);
	mid   = low + i*incr;
	rval1 = value - *mid;
	rval  = ABSOLUTE(rval1);
	if (rval < 0) rval = -rval;
	if (rval <= error ) {	/* find value with minimum deviation */
		for (p= mid; p >= data; p -= 1) {
			rval1 = *p - value;
                        rval = ABSOLUTE(rval1) ;
			if (rval > error) break;
		}
		mid = p+1 ;
		break;
	}
	if (tonext*rval1 < 0)  	/* Have to move  <<====	*/
		high = mid - incr;
	else			/* Have to move  ====>>	*/
		low  = mid + incr;
  }
    
  return (low <= high ? (mid-data)/incr : -1L);  /* M.P 210291 */
}

int TBL_BSR(data, value, error, count, tonext)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Binary Search for a value with error, r*4 data.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
.REMARKS When tonext>0, the values are assumed to be in INCREASING sequence,
		and DECREASING sequence when tonext<0 .
-------------------------------------------------------------*/
	float	*data 		/* IN: data array  			*/;
	double	 value          /* IN: value to look for		*/;
	double	 error          /* IN: tolerance 			*/;
	int     count          /* IN: number of elements to test	*/;
	int     tonext		/* IN: How to move to next LARGER value	*/;
{
	float	*low, *high, *mid, *p;
	float	rval, rval1;
	int	i, incr;

  if (count <= 0)	return(-1L);
  incr = ABSOLUTE(tonext);

  low  = data;
  high = low + (count-1)*incr;
  
  while (low <= high) {
	i = (high-low)/(2*incr);
	mid   = low + i*incr;
	rval1 = value - *mid;
	rval  = ABSOLUTE(rval1);
	if (rval < 0) rval = -rval;
	if (rval <= error ) {	/* find value with minimum deviation */
		for (p= mid; p >= data; p -= 1) {
			rval1 = *p - value;
                        rval = ABSOLUTE(rval1) ;
			if (rval > error) break;
		}
		mid = p+1 ;
		break;
	}
	if (tonext*rval1 < 0)  	/* Have to move  <<====	*/
		high = mid - incr;
	else			/* Have to move  ====>>	*/
		low  = mid + incr;
  }
    
  return (low <= high ? (mid-data)/incr : -1L);  /* M.P 210291 */
}

int TBL_BSD(data, value, error, count, tonext)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Binary Search for a value with error, r*8 data.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
.REMARKS When tonext>0, the values are assumed to be in INCREASING sequence,
		and DECREASING sequence when tonext<0 .
-------------------------------------------------------------*/
	double	*data 		/* IN: data array  			*/;
	double	 value          /* IN: value to look for		*/;
	double	 error          /* IN: tolerance 			*/;
	int     count          /* IN: number of elements to test	*/;
	int     tonext		/* IN: How to move to next LARGER value	*/;
{
	double	*low, *high, *mid, *p;
	double	rval, rval1;
	int	i, incr;

  if (count <= 0)	return(-1L);
  incr = ABSOLUTE(tonext);

  low  = data;
  high = low + (count-1)*incr;
  
  while (low <= high) {
	i = (high-low)/(2*incr);
	mid   = low + i*incr;
	rval1 = value - *mid;
	rval  = ABSOLUTE(rval1);
	if (rval < 0) rval = -rval;
	if (rval <= error ) {	/* find value with minimum deviation */
		for (p= mid; p >= data; p -= 1) {
			rval1 = *p - value;
                        rval = ABSOLUTE(rval1) ;
			if (rval > error) break;
		}
		mid = p+1 ;
		break;
	}
	if (tonext*rval1 < 0)  	/* Have to move  <<====	*/
		high = mid - incr;
	else			/* Have to move  ====>>	*/
		low  = mid + incr;
  }
    
  return (low <= high ? (mid-data)/incr : -1L);  /* M.P 210291 */
}
/*  */

int TBL_BSC(data, value, start, ncomp, count, tonext)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE Binary Search for a string.
.RETURNS Sequence number of the first value found (from 0),
                -1 if not found. 
.REMARKS When tonext>0, the values are assumed to be in INCREASING sequence,
		and DECREASING sequence when tonext<0 .
-------------------------------------------------------------*/
	char  	*data 	/* IN: data array  			*/;
	char	*value 	/* IN: string to look for		*/;
	int     start	/* IN: where in the char string		*/;
	int     ncomp	/* IN: how many bytes to compare	*/;
	int     count	/* IN: number of elements to test	*/;
	int     tonext	/* IN: How to move to next LARGER value	*/;
{
	char	*low, *high, *mid;
	int	diff, incr;

  if (count <= 0)	return(-1L);
  incr = ABSOLUTE(tonext);

  low  = data + (start-1);
  high = low + count*incr;
  
  while (low < high) {
	diff = (high-low)/(2*incr);
	mid  = low + diff*incr;
	diff = oscomp (value, mid, ncomp);
	if (diff == 0)	break;
	if (tonext*diff < 0)  	/* Have to move  <<====	*/
		high = mid - incr;
	else			/* Have to move  ====>>	*/
		low  = mid + incr;
  }

  return (low < high ? (mid-data)/incr : -1L);
}

int TBL_BSCTA(data,value,start,ncomp, count, nb)
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE
		Search for a value with error
.ALGORITHM	
                Binary search with error margin, 
                Data sorted in ascending sequence.
                Character data, transposed file organization.

.RETURNS
		sequence number of the first value found,
                -1 if not found. 
-------------------------------------------------------------*/
char    *data           /* data array  */;
char    *value          /* value to be found */;
int     start          /* first field element */;
int     ncomp          /* nuber of bytes to be compared */;
int     count          /* number of elements */;
int     nb             /* nuber of bytes in the column */;

{
  int low, high, mid, iseq;

  low  = 0;
  high = low + count;
  
  while (low < high)
     {mid  = (low+high)/2;
      iseq = oscomp(value, data + mid*nb + start, ncomp);
      if      (iseq < 0) high = mid-1;
      else if (iseq > 0) low = mid+1;
      else    return  (mid);
     }
    
  return (-1);
}

int TBL_BSCTD(data,value,start,ncomp,count,nb)
/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.PURPOSE
		Search for a value with error
.ALGORITHM	
                Binary search with error margin, 
                Data sorted in descending sequence.
                Character data, transposed file organization.

.RETURNS
		sequence number of the first value found,
                -1 if not found. 
-------------------------------------------------------------*/
char    *data           /* data array  */;
char    *value          /* value to be found */;
int     start          /* first field element */;
int     ncomp          /* nuber of bytes to be compared */;
int     count          /* number of elements */;
int     nb             /* nuber of bytes in the column */;


{ int low, high, mid, iseq;

  low  = 0;
  high =  low + count;
  
  while (low < high)
     {mid  = (low+high)/2;
      iseq = oscomp(value, data + mid*nb + start, ncomp);
      if      (iseq > 0) high = mid-1;
      else if (iseq < 0) low = mid+1;
      else    return  (mid);

     }
    
  return (-1);
}