function [ finPtIndex, finVal ] = eLattice( xArray, func )
%
%------------------------------------------------------------------------
%
% SEARCHES FOR A MAXIMUM OF A 1D FUNCTION OVER A LATTICE OF POINTS.
%
%------------------------------------------------------------------------
%
% DESCRIPTION OF NOTATION:
%   xArray: An array of independent variables, the length
%           of which MUST be EXACTLY a Fibonacci number minus 1.
%
%   func: The input function to maximize.
% 
%------------------------------------------------------------------------
% Written by:
% -- 
% John L. Weatherwax                2007-04-22
% 
% email: wax@alum.mit.edu
% 
% Please send comments and especially bug reports to the
% above email address.
% 
%------------------------------------------------------------------------
  
% The FIBONACCI NUMBERS:
F_NUMBERS = [ 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 ...
	      1597 2584 4181 6765 10946 17711 28657 46368 75025 ...
	      121393 196418 317811 514229 832040 1346269 2178309 ...
	      3524578 5702887 9227465 14930352 ];
  
% Check input.
fIndex = find( F_NUMBERS == length( xArray )+1 );
if( isempty( fIndex ) )
  error( 'The length of the x array must be a Fibonacci number minus one.' );
end

lBIndex = 0;
hBIndex = F_NUMBERS( fIndex );

%------------------------------------------------------------------------
% EVALUATE STARTING TWO POINTS OF SEARCH ( "X1" and "X2" ):
%------------------------------------------------------------------------

testLBIndex = F_NUMBERS( fIndex-2 );
testLB      = xArray( testLBIndex );
lBVal       = feval( func, testLB );

testHBIndex = F_NUMBERS( fIndex-1 );
testHB      = xArray( testHBIndex );
hBVal       = feval( func, testHB );

%------------------------------------------------------------------------
% START LATTICE FIBONACCI SEARCH
%------------------------------------------------------------------------

for i = 1:fIndex-4,

  if( lBVal < hBVal )
    lBIndex = testLBIndex;
    lBound  = testLB;
    
    testIndex = lBIndex + (hBIndex - testHBIndex);
    testPt    = xArray( testIndex );
    if( testIndex < testHBIndex )
      testLBIndex = testIndex;
      testLB      = testPt;
      lBVal       = feval( func, testLB );
    else
      testLBIndex = testHBIndex;
      testLB      = testHB;
      lBVal       = hBVal;
      
      testHBIndex = testIndex;
      testHB      = testPt;
      hBVal       = feval( func, testHB );
    end
    
  else
    hBIndex = testHBIndex;
    hBound  = testHB;
    
    testIndex = hBIndex - (testLBIndex - lBIndex);
    testPt = xArray( testIndex );
    if( testIndex > testLBIndex ) 
      testHBIndex = testIndex;
      testHB      = testPt;
      hBVal       = feval( func, testHB );
    else
      testHBIndex = testLBIndex;
      testHB      = testLB;
      hBVal       = lBVal;
      
      testLBIndex = testIndex;
      testLB      = testPt;
      lBVal       = feval( func, testLB );
    end
  end
  
  if( lBVal < hBVal )
    finPtIndex = testHBIndex;
    % finPt  = testHB;
    finVal = hBVal;
  else
    finPtIndex = testLBIndex;
    % finPt  = testLB;
    finVal = lBVal;
  end
  
end

%------------------------------------------------------------------------
% END LATTICE FIBONACCI SEARCH
%------------------------------------------------------------------------