function [vertices] = get_vertices_from_tree(tree, depth)
% -------------------------------------------------------------------------
% MSc Project - MSc in Communications and Signal Processing
% Department of Electrical and Electronic Engineering
% Imperial College London, 2011
%
% Supervisor  : Dr Pier Luigi Dragotti
% Contributor : Andriy Gelman
% Author      : Jon Onativia Bravo
%
% File        : tree2contour.m
% -------------------------------------------------------------------------
% Create a list of vertices from the top of the tree up to specified depth.
%
% [vertices] = get_vertices_from_tree(tree[, depth])
%
% INPUT:
%  - tree     : Tree of vertices.
%  - depth    : Optional argument. Depth of the tree up to where the 
%               vertices will be retrieved. 
%
% OUTPUT:
%  - vertices : List of vertices (2xN).
%


% Check input arguments
total_depth = length(tree);

if nargin == 1
    depth = total_depth;
else
    if depth > total_depth
        depth = total_depth;
    end
end


% Count the total number of vertices of this contour
num_of_verts = 0;
for l = 1 : depth
    if iscell(tree{l})
        num_of_verts = num_of_verts + size(cell2mat(tree{l}), 2);
    else
        num_of_verts = num_of_verts + size(tree{l}, 2);
    end
end

vertices = zeros(2, num_of_verts);


% Go through all the tree to retreive the vertices
i = 1;
for l = 1 : depth
    levels_verts = tree{l};
    
    if iscell(levels_verts)
        num_of_levels_cells = length(levels_verts);
        cells_verts         = levels_verts{1};
    else
        num_of_levels_cells = 1;
        cells_verts         = levels_verts;
    end
    
    j          = i;
    vert_count = 0;
    for ith_cell = 1 : num_of_levels_cells
        
        if ~isempty(cells_verts)
            
            vert_count = vert_count + 1;
            
            num_of_cells_verts  = size(cells_verts, 2);

            % Insert the first vertex of the level
            vertices(:,j) = cells_verts(:,1);
            j = j + 1;

            % Insert the following vertices of the cell
            for ith_lev_vert = 2 : num_of_cells_verts
                vert_count = vert_count + 1;

                num_of_sub_verts = count_sub_verts(tree, l, vert_count-1);
                j                = j + num_of_sub_verts;

                vertices(:,j) = cells_verts(:,ith_lev_vert);

                j = j + 1;
            end
            
            j = j + find(vertices(1,j:end) ~= 0, 1);
            j = j + find(vertices(1,j:end) == 0, 1) - 1;

        end
        
        if ith_cell < num_of_levels_cells
            cells_verts = levels_verts{ith_cell+1};
        end

    end
    
    i = i + find(vertices(1,i:end) == 0, 1) - 1;

end

end



function num_of_sub_verts = count_sub_verts(tree, level, node)

num_of_sub_verts = 0;

depth = length(tree);

if level == depth

    return

else
    
    % Cells that directly depend on the current node
    num_of_cur_verts  = size(tree{level+1}{node}, 2);
    
    num_of_sub_verts  = num_of_sub_verts + num_of_cur_verts;
    
    num_of_prev_verts = 0;
    % Count the cells of the previous nodes
    for prev_node = 1 : node-1
        num_of_prev_verts = num_of_prev_verts + size(tree{level+1}{prev_node}, 2);
    end
    
    % Count the verts of the subnodes
    for sub_node = num_of_prev_verts+1 : num_of_prev_verts+num_of_cur_verts
        num_of_sub_verts  = num_of_sub_verts + count_sub_verts(tree, level+1, sub_node);
    end
    
end % end of if/else statement

end % end of function 'count_sub_verts'

