/* librock/procede/ibsearch.c
librock_CHISEL _summary Binary search primitive with losing caller-control

Copyright (c) 2001-2002, Forrest J. Cavalier III, doing business as
Mib Software, Saylorsburg Pennsylvania USA

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
    Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.

    Redistributions in binary form must reproduce the above copyright
    notice, this list of conditions and the following disclaimer in the
    documentation and/or other materials provided with the distribution.

    Neither the name of the author nor the names of its contributors
    may be used to endorse or promote products derived from this software
    without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifdef librock_NOTLIBROCK
/**************************************************************/
/*  ABOUT THIS FILE: GUIDE TO QUICK REUSE WITHOUT REWORK

This file uses many preprocessor conditional blocks and
features to publish http://www.mibsoftware.com/librock/
You can disable those features with little or no editing,
and reuse this file:

  1. At compile time, enable this conditional block by defining
     the preprocessor symbol librock_NOTLIBROCK, either with
     a compiler command line parameter, or as a #define in a
     source file which then #includes this source file.

  2. Define any preprocessor symbols in this block (if any)
     appropriately for your machine and compilation environment.

  3. Copy and use the declarations from this block in your
     source files as appropriate.

This file is originally from the librock library, which is
Free (libre), free (no cost), rock-stable API, and works on
gcc/MSVC/Windows/Linux/BSD/more.

Get originals, updates, license certificates, more, at
    http://www.mibsoftware.com/librock/

(Change log appears at end of this file.)

*/
#define librock_ISOLATED

#define librock_PTR
#define librock_CONST const
/**************************************************************/
#endif

#ifndef librock_ISOLATED
/**************************************************************/
#define librock_IMPLEMENT_ibsearch

#include <librock/target/types.c>
#include <librock/exec.h>
/**************************************************************/
#endif


#ifdef librock_IMPL_LIDESC
#ifndef librock_NOIMPL_LIDESC_ibsrch
/**************************************************************/
#include <librock/license/librock.lh> /* librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45 */
void *librock_LIDESC_ibsrch[] = {
    "\n" __FILE__ librock_LIDESC_librock "\n",
    0
};
/**************************************************************/
#endif
#endif

#ifndef librock_WRAP
/**************************************************************/
#define librock_body_ITERbinsearch librock_ITERbinsearch
/**************************************************************/
#endif


#ifndef librock_NOIMPL_ITERbinsearch
/**************************************************************/
int librock_body_ITERbinsearch(long librock_PTR *pLow,long librock_PTR *pHigh,long side)
{ /* Iterator for binary search */
/*<LICENSE>  Copyright 1998-2002 Forrest J. Cavalier III, http://www.mibsoftware.com
  Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block.
  License text in <librock/license/librock.txt> librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45
*/
#ifdef librock_MANUAL_ITERbinsearch
/*<NAME>
librock_ITERbinsearch - implement binary search of indexed, ordered list
*/
/*<SYNOPSIS>*/
#include <librock/procede.h>

int librock_ITERbinsearch(
        long *pLow, /* Low side */
        long *pHigh, /* High side */
        long side);

/*<DESCRIPTION>
This performs the manipulatation of indexes needed during
a binary search of an integer indexed, ordered list.  On each
call, it reduces the difference between a low and high index based
on the result of a comparison the caller made with (*pLow + *pHigh)/2.
One of the indexes is moved towards the other.

The item at (*pHigh on the initial call) will never be checked.
After the initial call, and until the return is 0, *pLow and
*pHigh should not be adjusted or used by the caller, except
to calculate (*pLow + *pHigh)/2.

If there are multiple entries of the same value, the first entry
in the list will be found.

Returns non-zero if more iterations are needed.

When finished, the result in *pHigh and *pLow are as follows:

    *pLow == *pHigh if the item was found exactly.  This will
            be the first item that matches if there are multiple
            identical matches.

    *pHigh = *pLow+1 if item was not found.  *pLow is before
            the item, *pHigh is after.  Note that *pHigh might be
            unchanged from the first call, so it may point off the
            end of the list.

    *pHigh == *pLow-1.  if the list is empty (i.e. no entries found)

Note that *pLow might be > *pHigh during iteration, but not when
return value is 0.  (This is part of how multiple identical
matches are handled.)

Typical Use:
*/
#ifdef librock_TYPICAL_USE_ITERbinsearch
    char *item[10] = {
        "a","b","c","d","e","find this","find this","h","i","j"
    };
    char *tolocate = "find this";
    long itest;
    long low = 0;
    long high = 10;
    int side;

    do {
            itest = (high+low)/2;
            side = strcmp(tolocate,item[itest]);
    } while(librock_ITERbinsearch(&low,&high,side));
    if (low == high) {
        printf("Found at %d\n",low);
    } else if (high == low+1) {
        printf("Not found.  Insert after %d.  Before %d\n",low,high);
    }
#endif

/*<USES>
    // [No external calls.]
*/
/*<LICENSE>  Copyright 1998-2002 Forrest J. Cavalier III, http://www.mibsoftware.com
  Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block.
  License text in <librock/license/librock.txt> librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45
*/
#endif /* MANUAL */

/*<IMPLEMENTATION>-------------------------------------------*/
long temp;
if (*pLow > *pHigh) {   /* A match was found exactly, we are searching
                           for the first occurrence
                         */
        if (!side) {
                *pLow = (*pLow + *pHigh)/2;
        } else { /* Must require moving low side up */
                *pHigh = (*pLow + *pHigh)/2 + 1;
        }
        if (*pLow == *pHigh) {
                return 0;       /* Found it. */
        }
        return 1;
}
if (!side) { /* Match was found exactly */
        /* We want to find the first occurence, so we
           keep searching.
         */
        /* We swap *pLow and *pHigh */
        temp = (*pLow + *pHigh)/2;      /* The new upper limit */
        *pHigh = *pLow;
        *pLow = temp;
        if (*pLow == *pHigh) {
                return 0;       /* Found it. */
        }
        return 1;
} else if (side < 0) {  /* Test was too high */
        *pHigh = (*pLow + *pHigh)/2;
        if (*pHigh == *pLow) {
                *pLow = *pHigh - 1;
                return 0;
        }
} else { /* Test was too low */
        *pLow = (*pLow + *pHigh)/2+1;
        if (*pLow == *pHigh) {
                *pLow -= 1;
                return 0;
        }
}
return 1;       /* Keep iterating */
} /* ITERbinsearch */
/**************************************************************/
#endif /* NOIMP */

/*
$Log: ibsrch.c,v $
Revision 1.7  2002/08/02 04:09:26  forrest@mibsoftware.com rights=#1
  Updated TYPICAL_USE section.
  Added NOTLIBROCK section.
  Moved CVS log to end.
  Changed LIDESC MD5 to HC.

Revision 1.6  2002/04/09 03:33:13  forrest@mibsoftware.com rights=#1
  Updated LICENSE in manual.

Revision 1.5  2002/04/06 04:21:43  forrest@mibsoftware.com rights=#1
  librock\procede.h is obsolete.

Revision 1.4  2002/02/10 03:43:49  Administrator
Fix LIDESC, fix log entry

Revision 1.3  2002/02/06 14:05:07  forrest@mibsoftware.com rights=#1
Standardized chg log

Revision 1.2  2002/01/30 16:07:50  forrest@mibsoftware.com rights=#1
   Renamed some .h files

Revision 1.1  2002/01/29 14:24:11  forrest@mibsoftware.com rights=#1
   moved

rights#1 Copyright (c) Forrest J Cavalier III d-b-a Mib Software
rights#1 License text in <librock/license/librock.txt> librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45
*/