function [w,c,cluster]=c1d(x)
% Usage: [w,c,cluster]=c1d(x)
% 1-D clustering, will determine most likely cluster numbers
% copyright (C) 2000 by Yu Hen Hu
% created: 3/18/2000, modified 4/6/2001
% x: k by 1 input
% w: c by 1 cluster centers
% c: # of clusters
% cluster: cell array give actual elements of each cluster
n=length(x);
if n==1,
   w=x;
   return   
end
x=sort(x);
g=x(2:n)-x(1:n-1); % gap between adjacent x, length = n-1
mg=mean(g);
sig=std(g); % standard deviation of the gap
% the heuristics is that if there are gaps larger than 3*sig, then the
% current cluster needs to be split
idx0=find(abs(g-mg)>3*sig);
idx0=diag(diag(idx0))'; % make idx a row vector
if isempty(idx0), 
   w=mg;
   cluster{1}=x;
else % partition x's along g(idx)
   idx1=[0 idx0 n]; np=length(idx1)-1;
   csize=idx1(2:np+1)-idx1(1:np); % csize: np by 1 -- the size of each cluster
   % eliminate clusters that contains too few samples
   idx2=idx1(find(csize> 0.2*max(csize))+1); % new break point eliminating small clusters
   np2=length(idx2);
   if idx2(np2) < n, idx2(np2)=n; end % end point correction)
   idx=[0 idx2];
   w=[];
   for i=1:np2,
      cluster{i}=x(idx(i)+1:idx(i+1));
      w=[w;mean(cluster{i})];
   end
end
c=length(w);

%figure(1),plot(x,0,'.y',w,0,'hb')