///////////////////////////////////////////////////////////////////////////
/*
  Copyright 2001 Ronald S. Burkey

  This file is part of GutenMark.

  GutenMark 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.

  GutenMark 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 GutenMark; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

  Filename:	SearchWordlist.c
  Purpose:	Binary search of an in-memory wordlist structure.
  Mods:		11/18/01 RSB	Began.
*/

///////////////////////////////////////////////////////////////////////////

#include "libGutenSpell.h"

//------------------------------------------------------------------------
// Binary search of the wordlist for a given normalized+full word.
// Returns the index of the word record (if found), or of the record 
// before which the word should be inserted.  This may, of course, be
// one record past the end of the file.  Additionally, 
// the Matched parameter, on output, indicates
// whether the word was matched or not.

int
SearchWordlist (Wordlist * Words, char *Normalized, char *Full, int *Matched)
{
  int Start, End, Now, i, j = 0;
  *Matched = 0;

  // We work in successively smaller regions.  Start is the index
  // of the first word in the region.  End is the index of the word
  // AFTER the last word in the region.  Now is the index of the word
  // we're currently looking at within the region.
  Start = 0;
  End = Words->NumWords;
  for (;;)
    {
      Now = (Start + End) / 2;
      if (Now >= End)
	return (End);
      i = strcmp (Normalized, Words->Words[Now].Normalized);
      if (i == 0)
	j = strcmp (Full, Words->Words[Now].Full);
      if (i < 0 || (i == 0 && j < 0))
	End = Now;
      else if (i > 0 || (i == 0 && j > 0))
	Start = Now + 1;
      else
	{

	  // It may be a little hard to see, but we've gotten
	  // here only if i==0 && j==0.  So it's a match!
	  *Matched = 1;
	  return (Now);
	}
    }
}