function [t, fail] = ndlinesch(x, f0, d, stepmax, pars)
%  A line search, suitable for nonsmooth functions, with the feature that 
%  instead of evaluating the objective function at candidate points as a 
%  conventional line search would, a routine is called to check the objective
%  function at candidate points against the previous objective function value.
%
%  If reduction is not obtained at initial point, bisect back
%  until it is satisfied.  If it is, quit.  (No doubling forward.)
%  There is no sufficient decrease requirement: it's too demanding, 
%  if the gradient discontinuities are sufficiently huge.
%
%  Input Parameters
%   x is initial point 
%   f0 is the function value at x
%   d is the search direction 
%   stepmax is max step along d (could be infinity)
%   pars is used to pass any necessary info to pars.fcomparename.
%   pars.fcomparename is the name of the m-file which checks whether the 
%    function at a candidate new point is reduced below the previous value, 
%    instead of computing the new value.  The idea is that in some cases,
%    including the pseudospectral abscissa, it's much cheaper to make this
%    check.  It expects parameters x (the candidate point), f0 (the
%    comparison value, and pars (any other info needed). It returns 1
%    if the function value at x is smaller than f0 and 0 otherwise.
%    It's invoked by: smaller = feval(pars.fcomparename, x, pars, f0).
%
%  Output parameters
%   t is the step computed 
%   fail is 0 (normal), 1 (failure to get reduction)
%
%  Written by M. Overton (overton@cs.nyu.edu), last revised March 2003

%  Formerly called ndlinesch2.m

fail = 0;
t = min(1, stepmax);   
smaller = feval(pars.fcomparename, x + d, f0, pars);

% bisect until get sufficient decrease
bisectmax = 50;
bisectsteps = 0;
while ~smaller & bisectsteps < bisectmax
   bisectsteps = bisectsteps + 1;
   t = t/2;
   smaller = feval(pars.fcomparename, x + t*d, f0, pars);
end
if bisectsteps == bisectmax
   %% fprintf('too many steps in line search\n')
   %% fprintf('function may be nonsmooth, but may not have picked up enough\n')
   %% fprintf('gradient info if tol is not sufficiently small\n')
   fail = 1;
   t = 0;
end
