% Copyright (C) 2016 by Deanna Needell, Rayan Saab, and Tina Woolf

% This file is part of ''Weighted L1-Minimization for Sparse Recovery under
%                        Arbitrary Prior Information''

% This program is free software: you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation, either version 3 of the License, or
% (at your option) any later version.

% This program is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details.

% You should have received a copy of the GNU General Public License
% along with this program.  If not, see <http://www.gnu.org/licenses/>.

% genSignal.m

function a = genSignal(n, k, values)

[f,~] = log2(abs(n));
if f ~= 0.5
    error('n must be a power of two');
end

if nargin < 3
    values = randn(k, 1);
end

a = zeros(1,n);
parent = [0 1 2 2 floor((2:n-3)/2)+2];    % binary tree

a(1) = values(1);
for ii = 2:k
    I = find( a(2:end) == 0 & a( parent(2:end) ) ~= 0 ) + 1;
    jj = I(randi(end));
    a(jj) = values(ii);
    % fprintf('ii: %d, from %s, choose %d\n', ...
    %     ii, num2str(I), jj);
end

