% $URL: svn+ssh://mrwhat@ssh.boim.com/home/mrwhat/svn/Walker/trunk/balanceList.m $
% $Id: balanceList.m 150 2013-08-12 14:04:10Z aaron $
%
% Given a list of vectors, cluster/balance them so that they
% are more likely to form a fairly balanced tree when loaded
function bl = balanceList(v)
global bal balIdx
   bal = zeros(size(v));
   balIdx = 0;

   splitListBal(v);
   bl = bal(1:balIdx,:);
   bal=0;
   return
end

function splitListBal(v)
global bal balIdx
   nv = size(v,1);
   if (nv<3)
      hi = balIdx+nv;
      %whos bal balIdx
      %balIdx
      bal(balIdx+1:hi,:) = v;
      balIdx = hi;
      return;
   end

   [lt,ge,center] = splitList(v);
   clear v
   balIdx = balIdx+1;
   bal(balIdx,:) = center;
   splitListBal(lt);
   splitListBal(ge);
end

function [lt,ge,center] = splitList(v)
   mu = mean(v);
   sd = std(v);
   [maxSD, iMax] = max(sd);
   % find closest entry to centroid
   d = v;
   for i=1:length(mu), d(:,i) = v(:,i) - mu(i); end
   d = d .* d;
   d = sum(d');
   [dLo, iCenter] = min(d);
   center = v(iCenter,:);
   vc = center(iMax);
   tlt = v(:,iMax) < vc;
   ilt = find(tlt);
   tlt(iCenter)=1; % spoof test to skip center item
   ige = find(tlt==0);
   lt = v(ilt,:);
   ge = v(ige,:);
end
