%recovers message using iterative (graph-peeling) erasure decoding
%recieved_codeword - result of sending message through bec, bits erased marked with -1
function recovered_codeword = recover_lost_bits(recieved_codeword, parity_matrix)
    recovered_codeword = recieved_codeword;
    valid_checks = boolean(zeros(size(recieved_codeword)));
    can_recover = true; %if number of valid checks is not growing it means we have too many erased bits
    while ~is_fully_recovered(recovered_codeword) && can_recover
        [new_valid_checks, recovered_codeword] = recover_all_possible_bits(recovered_codeword, parity_matrix, valid_checks);
        can_recover = can_recover_more_bits(valid_checks, new_valid_checks);

        valid_checks = new_valid_checks;
    end

    if ~is_fully_recovered(recovered_codeword) && ~can_recover
        disp('RECOVERY FAILED, TOO MANY ERASED BITS!');
    end
end

%all bits are restored
function is_fully_recovered = is_fully_recovered(codeword)
    is_fully_recovered = all(codeword >= 0);
end

%if number of valid checks is not growing it means we have too many erased bits
function can_recover = can_recover_more_bits(valid_checks, new_valid_checks)
    can_recover = sum(new_valid_checks - valid_checks) > 0;
end

%one iteration over parity_check matrix
function [new_valid_checks, recovered_codeword] = recover_all_possible_bits(codeword, parity_matrix, valid_checks)
    new_valid_checks = valid_checks;
    recovered_codeword = codeword;
    for parity_check = 1 : size(parity_matrix, 1)
        if(~valid_checks(parity_check)) % don't jump in if parity check satisfied
            [recovered_codeword, is_check_valid]  = try_recovering_bits_from_parity_check_row(codeword, parity_matrix(parity_check,:));
            if is_check_valid
                new_valid_checks(parity_check) = true;
            end
        end
        codeword = recovered_codeword;
    end
end

function [recovered_codeword, is_check_valid] = try_recovering_bits_from_parity_check_row(codeword, parity_check)
    is_check_valid = true;
    recovered_codeword = codeword;
    bit_positions = find(parity_check);
    bit_values = codeword(bit_positions);

    if ~is_fully_recovered(bit_values)  %all ok, do nothing
        [recovered_codeword, is_check_valid] = try_recovering_bit(bit_values, bit_positions, codeword);
    end
end

function [recovered_codeword, is_check_valid] = try_recovering_bit(bit_values, bit_positions, codeword)
    is_check_valid = true;
    recovered_codeword = codeword;

    unknown_positions = find(bit_values == -1);
    number_of_unknowns = numel(unknown_positions);

    if number_of_unknowns == 1 % we can fix one unknown!
        known_values = bit_values(bit_values > -1);
        position_of_bit_to_recover = bit_positions(unknown_positions(1));
        recovered_codeword(position_of_bit_to_recover) = mod(sum(known_values), 2); %to satisfy parity check sum of all elems must be 0
    else
        is_check_valid = false; %check not valid, we need to wait for next iteration
    end
end