review needed: binary lookup

[Jaroslav Hajek]

hello,

I would like to implement a compiled binary search for Octave that
would replace the current lookup m-file implementation.
Dr. Eaton asked for an independent review of this code.

The new implementation is a dynamically loaded function
(src/DLD-FUNCTIONS). It uses repeated binary search with special
provisions to optimize for the most common case of downsampling a
table onto a denser one.
It also features options as a substitution for the (broken) hack used
in interpolation function - instead of
`lookup (table(2:end-1), y) + 1', one now writes `lookup (table, y,
'lr')'. If the new implementation is accepted, I'll make a patch
replacing the broken expressions in interpX functions with the safe
versions.
In addition to numeric arrays, the new implementation can also
binary-search cell arrays of strings (again with logarithmic
complexity per search). The core code is in liboctave/oct-lookup.h and
makes use of templates and STL algorithms.

Extracted inline help of the new implementation:

 -- Function File: IDX = lookup (TABLE, Y, OPT)
     Lookup values in a sorted table.  Usually used as a prelude to
     interpolation.

     If table is strictly increasing and `idx = lookup (table, y)', then
     `table(idx(i)) <= y(i) < table(idx(i+1))' for all `y(i)' within
     the table.  If `y(i)' is before the table, then `idx(i)' is 0. If
     `y(i)' is after the table then `idx(i)' is `table(n)'.

     If the table is strictly decreasing, then the tests are reversed.
     There are no guarantees for tables which are non-monotonic or are
     not strictly monotonic.

     TABLE and Y can also be a cell array of strings (or Y can be a
     single string). In this case, string lookup is performed using
     lexicographical comparison.  If OPTS is specified, it shall be a
     string with letters indicating additional options.

     For numeric lookup, 'l' in OPTS indicates that the leftmost
     subinterval shall be extended to infinity (i.e. all indices at
     least 1), and 'r' indicates that the rightmost subinterval shall be
     extended to infinity (i.e. all indices at most n-1).

     For string lookup, 'i' indicates case-insensitive comparison.


A changeset is attached.

regards,

-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz

binlookup.diff
Description: Text Data