function [H] = breadth_first(N)
%% BREADTH_FIRST  Visit the graph of hypotheses using the breadth-first algorithm
%%
%%    [H] = breadth_first(N)
%%    H - list of all hypotheses
%%    N - vector of numbers of features found
%%
%% (c) P. Perona, California Institute of Technology
%% May 5, 2000

F = length(N); %% Number of parts in model
W = [fliplr(cumprod(fliplr(N)+1)) 1];  %% Set of weights for index computation
Nh = prod(N+1); %% Total n. of hypotheses

H = zeros(Nh,F); %% Array containing hypotheses
X = ones(Nh); %% Array containing 1 for non-queued hyps and 0 otherwise

Q = [1]; %% The first item in the queue is the all-zero hyp
X(1) = 0;


%%% In the future should implement queue with array
%%% rather than stack in order to make it more efficient...
while length(Q)>0,
  h_i = Q(1); Q=Q(2:length(Q)); %% Pop the first element from the queue
  H(h_i,:) = hypothesis(h_i,N); %% Add hyp to the output list
    %% HERE THERE SHOULD BE CODE TO CHECK WHETHER THE BEST-CASE SCENARIO
    %% FOR THIS HYP LOOKS PROMISING. THE CHILDREN SHOULD BE ADDED TO THE
    %% QUEUE ONLY IN THIS CASE. OTHERWISE THE CHILDREN ARE ONLY MARKED
    %% BY SETTING THEIR BIT IN X TO 1 BUT NOT ADDED TO THE QUEUE.
  cc = children(h_i,N,W); %% compute the children of the current hyp.
  if length(cc)>0,
    xx = X(cc); %% compute which children have not been added to the queue already
    Q = [Q cc(find(xx))]; %% Add to the queue the children of the current hyp
    X(cc(find(xx))) = 1;
  end;
end;
  

  
%%% Given the hyp calculate
%%% the position of the hyp in the lexicographic
%%% list ( [000],[001], ...)
%%% Unfortunately N is stored `backwards' so we need
%%% to reverse the order before and after cumprod
function h_i = h_index(hyp,W)
h_i= 1 + W * [0 hyp]';

%%% Given the position of the hyp in the lex. list
%%% calculate the hypothesis
%%%
function hyp = hypothesis(h_i,N)
F = length(N);
hh = h_i-1;
for f=F:-1:2,
  nn = N(f)+1;
  tmp = floor(hh/nn);
  hyp(f) = hh - tmp*nn; %% mod(hh,nn);
  hh = tmp;
end;
hyp(1)=hh;


%%%
%%% Given a hypothesis, generate its children
%%%
function  cc = children(h_i,N,W)


F = length(N);
hyp = hypothesis(h_i,N);
ff = find(hyp==0);
cc = zeros(1,sum(N(ff)));

i=1;
for f=ff,
  for n=1:N(f),
    hyp_c = hyp; hyp_c(f)=n;
    cc(i) = h_index(hyp_c,W);
    i=i+1;
  end;
end;