#include <sys/types.h>
#include <stdio.h>
#include <strings.h>
#include <dictionary.h>
#include <dict_errs.h>
#include <dicterrors.h>
#include <errno.h>

/*
 * I'm not using relative seeks here because I found a bug in the
 * stdio library that prevents me from doing so.
 */
     
static backUpToNewline(file, location)
FILE *file;
off_t *location;
{
     char buf[DICTIONARYLINELENGTH+SOUNDEX_LENGTH+2];
     char *ptr;
     int bytes;

     bytes = (*location > sizeof(buf)) ? sizeof(buf) : *location;
     
     if (fseek(file, *location - bytes, 0) == -1) {
	  dict_set_error(errno ? errno : -1);
	  return(dict_error_code);
     }

     if (! *location)
	  return(0);
     
     if (fread(buf, 1, bytes, file) == 0) {
	  dict_set_error(errno ? errno : -1);
	  return(dict_error_code);
     }

     ptr = buf + bytes - 1;
     while (ptr >= buf) {
	  if (*ptr == '\n')
	       break;
	  ptr--;
     }

     *location = *location - bytes + (ptr - buf) + 1;

     if (fseek(file, *location, 0) == -1) {
	  dict_set_error(errno ? errno : -1);
	  return(dict_error_code);
     }

     return(0);
}


	       
_dictBinarySearch(file, size, start, location)
FILE *file;
off_t size;
char *start;
off_t *location;
{
     off_t min_bound = 0, max_bound = size;
     off_t beginning_of_line, end_of_line, found = -1;
     int order, len, delta;
     char buf[DICTIONARYLINELENGTH+SOUNDEX_LENGTH+2];
     int retval;
     
     len = strlen(start);
     
     do {
	  delta = max_bound - min_bound;
	  beginning_of_line = min_bound + (max_bound - min_bound) / 2;
	  if (fseek(file, beginning_of_line, 0) == -1) {
	       dict_set_error(errno ? errno : -1);
	       return(dict_error_code);
	  }
	  retval = backUpToNewline(file, &beginning_of_line);
	  if (retval)
	       return(retval);
	  
	  if (fgets(buf, sizeof(buf), file) == NULL) {
	       dict_set_error(errno ? errno : -1);
	       return(dict_error_code);
	  }

	  end_of_line = beginning_of_line + strlen(buf);

	  order = strncmp(start, buf, len);

	  if (order < 0) {
	       max_bound = beginning_of_line;
	       continue;
	  }
	  else if (order > 0) {
	       min_bound = end_of_line;
	       continue;
	  }
	  else {
	       found = beginning_of_line;
	       max_bound = beginning_of_line;
	       continue;
	  }
     } while (delta != max_bound - min_bound);

     if (found == -1) {
	  dict_set_error(DICT_NOT_FOUND);
	  return(dict_error_code);
     }

     *location = found;
     
     return(0);
}