
function [pst] = add_feature(data,pst)

N = data(:,end); % counts
m = length(pst);

prob = eval_pst_probs(data,pst);
H = sum(N.*binary_entropy(prob))/sum(N); % current conditional entropy

% find the best feature to add (try adding all leafs, even if duplicate)

best_fea.x = [];
best_fea.H = H; 

for i=1:m,
  best_fea = select_best(best_fea,data,prob,[pst{i}.x,0]); 
  best_fea = select_best(best_fea,data,prob,[pst{i}.x,1]); 
  best_fea = select_best(best_fea,data,prob,[pst{i}.x,2]); 
end;

if (length(best_fea.x)>0),
  pst{m+1} = best_fea;
end;

pst = sort_by_feature_size(pst); % keep shorter features earlier


% -----------------------------------------------------
function [best_fea] = select_best(best_fea,data,prob,x)

N = data(:,end); % counts

[fea,ind] = new_feature(data,x); 

if (length(ind)>0), % if any matches
  prob(ind) = fea.p; % update predictive pst probabilities 
  fea.H = sum(N.*binary_entropy(prob))/sum(N); 
  if (fea.H<best_fea.H-eps), best_fea = fea; end;
end;


% -----------------------------------------------------
function [pst_sorted] = sort_by_feature_size(pst)

m = length(pst);
nx= zeros(m,1);
for i=1:m, nx(i) = length(pst{i}.x); end;
[tmp,I] = sort(nx);

pst_sorted = cell(m,1);
for i=1:m, pst_sorted{i}=pst{I(i)}; end;
