function [ i, seed ] = walker_sampler ( n, y, a, seed, i )

%*****************************************************************************80
%
%% WALKER_SAMPLER returns a random sample i=1..N with prob X(i).
%
%  Discussion:
%
%    Implementation of algorithm for sampling from a discrete
%    probability N-vector X(1), X(2), ..., X(N).  (N>=1.)
%    Runs on O(1) worst case time per sample,
%    and uses one integer and one real N-element array for storage.
%    Preprocessing consumes O(N) time and temporarily uses one 
%    additional integer array (B(0..N+1)) for bookkeeping. 
%    X(0) and X(N+1) are also used as sentinels in the Build() algorithm.
%
%  Licensing:
%
%    This code is distributed under the GNU LGPL license. 
%
%  Modified:
%
%    21 February 2016
%
%  Author:
%
%    Original C version by Warren Smith.
%    This MATLAB version by John Burkardt.
%
%  Reference:
%
%    Warren Smith,
%    How to sample from a probability distribution,
%    April 18, 2002.
%
%  Parameters:
%
%    Input, integer N, indicates the size of X.
%
%    Input, real Y(0:N+1), the Walker threshold vector.
%
%    Input, integer A(0:N+1), the Walker index vector.
%
%    Input/output, integer SEED, a seed for the random 
%    number generator.
%
%    Output, integer I, a sample value between 1 and N,
%    selected according to the probability vector X.
%

% 
%  Let i = random uniform integer from {1,2,...N}  
%
  [ i, seed ] = i4_uniform_ab ( 1, n, seed );

  [ r, seed ] = r8_uniform_01 ( seed );

  if ( y(i+1) < r )
    i = a(i+1);
  end

  return
end

