############################################################################
#
#	Name:	 binsrch.icn
#
#	Title:	 general-purpose binary index search
#
#	Author:	 Richard L. Goerwitz
#
#	Version: 1.4
#
############################################################################
#
#  This file contains a single procedure, binary_index_search(str,
#  filename), which goes through a file called filename looking for a
#  line beginning with str.  Note well that binary_index_search()
#  assumes lines in filename will contain more than str.  Str must
#  occupy the first part of the line, separated from the remainder by
#  a tab.
#
############################################################################
#
#  Links: none
#
#  See also: retrieve.icn, makeind.icn
#
############################################################################


procedure binary_index_search(entry, index_filename)

    local in_index, bottom, top, loc, incr, firstpart, offset

    in_index := open(index_filename) |
	abort("binary_index_search","can't open "||index_filename,18)

    bottom := 1
    seek(in_index, 0)
    top := where(in_index)

    # If bottom gets bigger than top, there's no such entry.
    until bottom > top do {

	loc := (top+bottom) / 2
	seek(in_index, loc)

	# Move past next newline.  If at bottom, break.
	incr := 1
	until reads(in_index) == "\n" do
	    incr +:= 1
	if loc+incr = bottom then {
	    top := loc-1
	    next
	}

	# Check to see if the current line starts with entry (arg 1).
	read(in_index) ? {

	    # .IND file line format is entry\tbitmap-file-offset
	    if entry == (firstpart := tab(find("\t"))) then {
		# return offset
		return (move(1), tab(0))
	    }
	    # Ah, this is what all binary searches do.
	    else {
		if entry << firstpart
		then top := loc-1
		else bottom := loc + incr + *&subject
	    }
	}
    }

end