function index=linear_time_resampling(W)
clear index;

% requires: sum(W_i)=1
N=length(W);
Q=cumsum(W);
t=-log(rand(N+1,1));
T=cumsum(t);
TN=T/T(N+1);
i=1;
j=1;

while(i<=N)
   if TN(i)<Q(j)
      index(i)=j;
      i=i+1;
   else
      j=j+1;
   end
end