%EUSIPCO 2012
%Imperial College London 
%Andriy Gelman, Jon Onativia and Pier Luigi Dragotti 


function [output, state_counter] = partition_subband(input, number_of_decompositions, maximum_block_size)


%compute input size
input_size = size(input);

%combine blocks
row_nums_subband = compute_subband_size(input_size(1), number_of_decompositions);
col_nums_subband = compute_subband_size(input_size(2), number_of_decompositions);

%Extract first subband 
current_subband = input(1:row_nums_subband(1), 1:col_nums_subband(1));

%Initialize
total_block_counter=1;

[buffer, state_counter_buffer] = extract_first_subband(current_subband, maximum_block_size);

for i = 1:length(buffer)
    output{total_block_counter} = buffer{i};   
    state_counter(total_block_counter) = state_counter_buffer(i);
    total_block_counter = total_block_counter+1;
end


%output{total_block_counter} = input(1:row_nums_subband(1), 1:col_nums_subband(1));
%total_block_counter = total_block_counter+1;

for l = 1:number_of_decompositions
    %Extract a block
    %current block dimensions
    

    %N = current_decomposition_counter;
    current_block_dimensions = [sum(row_nums_subband(1:l+1)), sum(col_nums_subband(1:l+1))];

    smaller_block_dimension_rows = [sum(row_nums_subband(1:l)), row_nums_subband(l+1)];
    smaller_block_dimension_columns = [sum(col_nums_subband(1:l)), col_nums_subband(l+1)];


    %extract current block
    current_subband = input(1:current_block_dimensions(1), 1:current_block_dimensions(2));

   [buffer, state_counter_buffer] = extract_subbands(current_subband, smaller_block_dimension_rows, smaller_block_dimension_columns, maximum_block_size);
    
    %place buffer into current counter
    for i = 1:length(buffer)
        output{total_block_counter} = buffer{i};
        state_counter(total_block_counter) = state_counter_buffer(i);
        total_block_counter = total_block_counter+1;
    end
end



%{

%Iterate until all the subbands are smaller or equal to the maximum block
%size

%Decimate row subbands until all of them are smaller or equal to the maximum block size  
while 1
    index = find(output_row_nums_subband > maximum_block_size(1));
    if isempty(index)
        break;
    else
       %ensure only one value exists in the 
        index = index(1);
        output_row_nums_subband = insert_value_into_array(output_row_nums_subband, index);             
    end        
end


%Decimate row subbands until all of them are smaller or equal to the maximum block size  
while 1
    index = find(output_col_nums_subband > maximum_block_size(2));
    if isempty(index)
        break;
    else
       %ensure only one value exists in the 
        index = index(1);
        output_col_nums_subband = insert_value_into_array(output_col_nums_subband, index);             
    end        
end
%}
end


function output = compute_subband_size(input, number_of_decompositions)

output(1) = input;
for l = 1:number_of_decompositions
    
    buffer = output(l);
    output(l) = floor(buffer/2);
    output(l+1) = ceil(buffer/2);
    
end

    output = rot90(rot90(output));

end


function output = insert_value_into_array(input, index)
%function iserts value into an array

  output= zeros(1, length(input)+1);
       
  output(1:index-1) = input(1:index-1);
  output(index) = ceil(input(index)/2);      
  output(index+1) = floor(input(index)/2);
             
  output(index+2:end) = input(index+1:end);              
end

%{
function output = partition_into_blocks(input)

[r,c,k] = input;
output{1} = input(1:floor(end/2),1:floor(end/2));
output{2} = input(1:floor(end/2), floor(end/2)+1:end);
output{3} = input(floor(end/2)+1:end, 1:floor(end/2));
output{4} = input(floor(end/2)+1:end, floor(end/2)+1:end);

end
%}

function [output, state_counter] = extract_subbands(input, row_dims, col_dims, maximum_block_size)

%Extract the following blocks and check that they are smaller than the
%maximum block size, if they are larger, then partition the blocks into
%smaller blocks again.

%Only extract blocks 2,3,4  - 1 has allready been extracted
%___________________
%         |         |
%    1    |    2    |
%_________|________ |
%         |         |
%    3    |    4    |
%_________|_________|    
%

%initialize
current_counter = 1;

inc = 1;
%extract block and check whether it is smaller larger then maximum block
%size

block2 = input(1:row_dims(1), col_dims(1)+1:end);

[r,c] = size(block2);

switch ((r*c)<= maximum_block_size(1)*maximum_block_size(2)) 
    case 1
       output{current_counter} =  block2;
       current_counter = current_counter + 1; 
       state_counter(inc) = 2;
       inc = inc+1;
    case 0       
        block2 = partition_block_subband([row_dims(1), col_dims(1)], block2, maximum_block_size);
        
        %place partitioned blocks into output
        for l = 1:length(block2)
            output{current_counter} = block2{l};
            current_counter = current_counter+1;
            state_counter(inc) = 2;
            inc = inc+1;
        end
end
    

block3 = input(row_dims(1)+1:end, 1:col_dims(1));

[r,c] = size(block3);

switch ((r*c)<= maximum_block_size(1)*maximum_block_size(2)) 
    case 1
       output{current_counter} =  block3;
       current_counter = current_counter + 1; 
       state_counter(inc) = 3;
       inc = inc+1;
    case 0       
        block3 = partition_block_subband([row_dims(1), col_dims(1)], block3, maximum_block_size);
        
        %place partitioned blocks into output
        for l = 1:length(block3)
            output{current_counter} = block3{l};
            current_counter = current_counter+1;
            state_counter(inc) = 3;
            inc = inc+1;
        end
end


block4 = input(row_dims(1)+1:end, col_dims(1)+1:end);

[r,c] = size(block4);

switch ((r*c)<= maximum_block_size(1)*maximum_block_size(2)) 
    case 1
       output{current_counter} =  block4;
       current_counter = current_counter + 1; 
       state_counter(inc) = 4;
       inc = inc+1;
    case 0       
        block4 = partition_block_subband([row_dims(1), col_dims(1)], block4, maximum_block_size);
        
        %place partitioned blocks into output
        for l = 1:length(block4)
            output{current_counter} = block4{l};
            current_counter = current_counter+1;
            state_counter(inc) = 4;
            inc = inc+1;
        end
end


end


function [output, current_counter] = partition_block_subband(low_dims, output, maximum_block_size)


[r,c] = size(output);

r_test = low_dims(1);
c_test = low_dims(2);

r_max = maximum_block_size(1);
c_max = maximum_block_size(1);

%calculate the number of times the current block size is larger than the
%maximum block size
%calculate the number of current data parti

partitions = floor(log((r_test*c_test)/(r_max*c_max))/log(4));
if partitions > 0
    new_r = divide_et_impera(r, partitions);
    new_c = divide_et_impera(c, partitions);

    output = mat2cell(output, new_r, new_c);

    output = reshape(output, [1, length(new_r)*length(new_c)]);
else
    buffer{1} = output;
    output = buffer;
end
end

function output = divide_et_impera(input, iterations)
output = input;
for i = 1:iterations
    
    for ii = 1:length(output)
        buffer((ii-1)*2+1:ii*2) = [ceil(output(ii)/2), floor(output(ii)/2)];
    end
    output = buffer;

end
end



function [output, state_counter] = extract_first_subband(input, maximum_block_size)

%Extract the following blocks and check that they are smaller than the
%maximum block size, if they are larger, then partition the blocks into
%smaller blocks again.

%Only extract blocks 1
%___________________
%         |         |
%    1    |    2    |
%_________|________ |
%         |         |
%    3    |    4    |
%_________|_________|    
%

%initialize
current_counter = 1;
state_counter = 1;
%extract block and check whether it is smaller larger then maximum block
%size
inc = 1;
block1 = input;

[r,c] = size(block1);

switch ((r*c)<= maximum_block_size(1)*maximum_block_size(2)) 
    case 1
       output{current_counter} =  block1;
       current_counter = current_counter + 1; 
    case 0       
        block1 = partition_block_subband(size(block1), block1, maximum_block_size);
        
        %place partitioned blocks into output
        for l = 1:length(block1)
            output{current_counter} = block1{l};
            current_counter = current_counter+1;
            
            state_counter(inc) = 1;
            inc = inc+1;
        end
end
    



end

