function [tree, width, height] = bitstream2tree_v3(bitstream, max_deltas)
% -------------------------------------------------------------------------
% 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        : tree2bitstream_v3.m
% -------------------------------------------------------------------------
% Decode a tree of multiple levels of precision contours of multiple images
% from a binary bitstream. If the last level of precision has a max_delta
% between consecutive vertices of 1, the vertices must have been encoded 
% using Freeman chain code (3 bits per vertex with 8-connectivity 
% neighbourhood). The fields of each level (num. of vertices, num. of 
% segments, etc) must be constructed having a size multiple of the size 
% required for the vertices' deltas.
%
% [tree, width, height] = bitstream2tree_v3(bitstream, max_deltas)
%
% INPUT:
%  - bitstream    : Binary bitstream.
%  - max_deltas   : Maximum delta of consecutive vertices for each level of
%                   precision.
%
% OUTPUT:
%  - tree         : Tree containing the different images' contours.
%  - width        : Width of the original shape images.
%  - height       : Heigth of the original shape images.
%

b_idx = 1;

field_bits = 12;
width      = bin2dec(bitstream(b_idx:b_idx+field_bits-1), false);
b_idx      = b_idx + field_bits;
height     = bin2dec(bitstream(b_idx:b_idx+field_bits-1), false);
b_idx      = b_idx + field_bits;

field_bits    = 6;
num_of_layers = bin2dec(bitstream(b_idx:b_idx+field_bits-1), false);
b_idx         = b_idx + field_bits;

tree = cell(num_of_layers, 1);

max_depth = bin2dec(bitstream(b_idx:b_idx+field_bits-1));
b_idx     = b_idx + field_bits;

% Read first the first level of precision
for ith_layer = 1 : num_of_layers
    field_bits      = 6;
    num_of_contours = bin2dec(bitstream(b_idx:b_idx+field_bits-1), false);
    b_idx           = b_idx + field_bits;
    
    % Allocate the contours cells of this specific layer
    tree{ith_layer} = cell(1, num_of_contours);

    % The delta fields size depends on the maximum delta between vertices
    offset_bits = log2(max_deltas(1) + 1) + 1;
    if mod(8, offset_bits) > 0
        num_verts_bits = 8 + offset_bits - mod(8, offset_bits);
    else
        num_verts_bits = 8;
    end
    
    for ith_contour = 1 : num_of_contours
        % Allocate the different levels of this contour
        tree{ith_layer}{ith_contour} = cell(max_depth, 1);
        
        field_bits = num_verts_bits;
        seg_len    = bin2dec(bitstream(b_idx:b_idx+field_bits-1), false);
        b_idx      = b_idx + field_bits;
        
        % Allocate the firts level's vertices array
        verts = zeros(2, seg_len);
        
        field_bits = 12;
        verts(1,1) = bin2dec(bitstream(b_idx:b_idx+field_bits-1), false);
        b_idx      = b_idx + field_bits;
        verts(2,1) = bin2dec(bitstream(b_idx:b_idx+field_bits-1), false);
        b_idx      = b_idx + field_bits;
        
        field_bits = offset_bits;
        for ith_vert = 2 : seg_len
            verts(1,ith_vert) = verts(1,ith_vert-1) + bin2dec(bitstream(b_idx:b_idx+field_bits-1));
            b_idx             = b_idx + field_bits;
            verts(2,ith_vert) = verts(2,ith_vert-1) + bin2dec(bitstream(b_idx:b_idx+field_bits-1));
            b_idx             = b_idx + field_bits;
        end
        
        % Store the first level's verts
        tree{ith_layer}{ith_contour}{1} = verts;
    end
    
end


% Fill the other levels
for depth = 2 : max_depth
    
    for ith_layer = 1 : num_of_layers
        num_of_contours = length(tree{ith_layer});
            
        for ith_contour = 1 : num_of_contours
            
            prev_verts = tree{ith_layer}{ith_contour}{depth-1};
            if iscell(prev_verts)
                prev_verts    = cell2mat(prev_verts);
            end
            num_of_prev_verts = size(prev_verts, 2);
            
            % The number of the previous levels' vertices it's the number
            % of current's level segments
            tree{ith_layer}{ith_contour}{depth} = cell(1, num_of_prev_verts);
            
            if max_deltas(depth) > 1
                % The delta fields size depends on the maximum delta between vertices
                offset_bits = log2(max_deltas(depth) + 1) + 1;
                if mod(8, offset_bits) > 0
                    num_verts_bits = 8 + offset_bits - mod(8, offset_bits);
                else
                    num_verts_bits = 8;
                end
                
                for ith_seg = 1 : num_of_prev_verts
                    % Read the current's segment length from the bitstream
                    field_bits = num_verts_bits;
                    seg_len    = bin2dec(bitstream(b_idx:b_idx+field_bits-1), false) + 1;
                    b_idx      = b_idx + field_bits;

                    % Allocate segment's vertices array
                    verts = zeros(2, seg_len);

                    % The first vertex correspond to the previous level's
                    % vertex
                    verts(1,1) = prev_verts(1,ith_seg);
                    verts(2,1) = prev_verts(2,ith_seg);

                    field_bits = offset_bits;
                    % The following vertices are retrieved from the bitstream
                    for ith_vert = 2 : seg_len
                        verts(1,ith_vert) = verts(1,ith_vert-1) + bin2dec(bitstream(b_idx:b_idx+field_bits-1));
                        b_idx             = b_idx + field_bits;
                        verts(2,ith_vert) = verts(2,ith_vert-1) + bin2dec(bitstream(b_idx:b_idx+field_bits-1));
                        b_idx             = b_idx + field_bits;
                    end

                    % Store the vertices array in the tree
                    tree{ith_layer}{ith_contour}{depth}{ith_seg} = verts;
                end
            else
                % The delta fields have a size of 3 bits (Freeman encoding)
                offset_bits = 3;
                if mod(8, offset_bits) > 0
                    num_verts_bits = 8 + offset_bits - mod(8, offset_bits);
                else
                    num_verts_bits = 8;
                end
                
                % Retrieve Freeman encoded segments
                for ith_seg = 1 : num_of_prev_verts
                    
                    % Read the current's segment length from the bitstream
                    field_bits = num_verts_bits;
                    seg_len    = bin2dec(bitstream(b_idx:b_idx+field_bits-1), false) + 1;
                    b_idx      = b_idx + field_bits;
                    
                    % Allocate segment's vertices array
                    verts = zeros(2, seg_len);
                    
                    % The first vertex correspond to the previous level's
                    % vertex
                    verts(1,1) = prev_verts(1,ith_seg);
                    verts(2,1) = prev_verts(2,ith_seg);
                    
                    field_bits = offset_bits;
                    
                    for ith_vert = 2 : seg_len
                        freeman_code = bin2dec(bitstream(b_idx:b_idx+field_bits-1), false);
                        b_idx        = b_idx + field_bits;
                        
                        if freeman_code == 0
                            dx = 1;
                            dy = 0;
                        elseif freeman_code == 1
                            dx = 1;
                            dy = 1;
                        elseif freeman_code == 2
                            dx = 0;
                            dy = 1;
                        elseif freeman_code == 3
                            dx = -1;
                            dy = 1;
                        elseif freeman_code == 4
                            dx = -1;
                            dy = 0;
                        elseif freeman_code == 5
                            dx = -1;
                            dy = -1;
                        elseif freeman_code == 6
                            dx = 0;
                            dy = -1;
                        elseif freeman_code == 7
                            dx = 1;
                            dy = -1;
                        end
                        
                        verts(:,ith_vert) = verts(:,ith_vert-1) + [dx; dy];
                    end

                    % Store the vertices array in the tree
                    tree{ith_layer}{ith_contour}{depth}{ith_seg} = verts;
                end
            end
        end
        
    end
end


end