/***************************************************************************
 *                                                                         *
 *   BINSRCH.C                                                             *
 *                                                                         *
 *   Copyright (c) 1997      Galacticomm, Inc.      All Rights Reserved.   *
 *                                                                         *
 *   Generic binary search utility.                                        *
 *                                                                         *
 *                                            - J. Alvrus   5/29/97        *
 *                                                                         *
 ***************************************************************************/

#include "gcomm.h"

#define FILREV "$Revision: 2 $"

ULONG                              /*   index or numElems if not found     */
binSearch(                         /* generic binary search utility        */
const VOID *target,                /*   target object to find              */
const VOID *array,                 /*   array object                       */
ULONG numElems,                    /*   number of elements in array object */
binSearchComp compFunc)            /*   comparison function                */
{
     INT comp;
     LONG i;

     i=binFindNear(&comp,target,array,numElems,compFunc);
     if (comp == 0) {
          return(i);
     }
     return(numElems);
}

ULONG                              /*   index where element should be      */
binFindNear(                       /* generic binary find nearest utility  */
INT *lastComp,                     /*   result of last comparison          */
const VOID *target,                /*   target object                      */
const VOID *array,                 /*   array object                       */
ULONG numElems,                    /*   number of elements in array object */
binSearchComp compFunc)            /*   comparison function                */
{
     ULONG lo,md,hi;
     INT comp;

     comp=1;
     lo=md=0;
     if (numElems > 0) {
          hi=numElems-1;
          while (lo <= hi) {
               md=lo+(hi-lo)/2;
               if ((comp=(*compFunc)(target,array,md)) > 0) {
                    if (md == hi) {
                         ++md;
                         break;
                    }
                    lo=md+1;
               }
               else if (comp < 0) {
                    if (md == lo) {
                         break;
                    }
                    hi=md-1;
               }
               else {
                    break;
               }
          }
     }
     *lastComp=comp;
     return(md);
}
