/************************************************************************
*
* Copyright 2006 by Sean Conner.  All Rights Reserved.
*
* 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*
* Comments, questions and criticisms can be sent to: sean@conman.org
*
*************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define ddt	assert

/******************************************************************/

void	 	 pres		(const int *,size_t,int,int);
int	 	 tpr_cmp	(int,int);
const int	*search		(int,size_t *,char *);

/*********************************************************************/

size_t    g_recnum;
const int g_rec[10] = { 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 };

/*********************************************************************/

int main(int argc,char *argv[])
{
  size_t     idx;
  const int *p;
  char       l;
  int        i;
  
  for (g_recnum = 0 ; g_recnum < 11 ; g_recnum++)
  {
    printf("g_recnum = %d\n",g_recnum);
    for (i = 0 ; i < 22 ; i++)
    {
      p = search(i,&idx,&l);
      pres(p,idx,i,l);
    }
    printf("\n");
  }
  return(EXIT_SUCCESS);
}

/********************************************************************/

void pres(const int *p,size_t i,int num,int l)
{
  if (p == NULL)
    printf("r=-- %c ",l);
  else
    printf("r=%2d %c ",*p,l);
  
  printf("%2d @ %2d a=",num,i);
  
  for (i = 0 ; i < g_recnum ; i++)
    printf("%2d:[%2d] ",i,g_rec[i]);
    
  printf("\n");
}

/********************************************************************/
  
int tpr_cmp(int key,int val)
{
  if (key < val)
    return(-1);
  else if (key > val)
    return( 1);
  else
    return(0);
}

/********************************************************************/

const int *search(int key,size_t *pidx,char *l)
{
  size_t low;
  size_t mid;
  int    q;
  
  low = 0;
  mid = g_recnum;
  
  while(mid)
  {
    mid /= 2;

    if (low + mid >= g_recnum)
    {
      low = g_recnum - 1;
      mid = 0;
    }
      
    q = tpr_cmp(key,g_rec[low + mid]);
    
    if (q > 0)
      low += mid + 1;
    else if (q == 0)
    {
      *pidx = low + mid;
      *l    = 'b';
      return(&g_rec[low + mid]);
    }
  }
  
  *pidx = low;
  *l    = 'c';
  return(NULL);
}

/************************************************************************/