function [tree,json] = partsTree(D)

tree.parent = []; % node = 0 is the root node
tree.nodewords = {};
%tree.counts = zeros(100*20,1);

% remove stop words
%   'crop',...
%D = removestopwords(D);

[names, namesCounts] = LMobjectnames(D);

% Identify whole objects first and that have more than N annotated examples
% only add as branches the ones that have as root a whole frequent object
% put the counts as part of the object name when building the tree. 
m=0;
for n = 1:length(D)
    n
    D(n).annotation = changeId(D(n).annotation);
    
    for j = 1:LMcountobject(D(n))
        hasparts = [];
        ispartof = [];
        if isfield(D(n).annotation.object(j), 'parts')
            if isfield(D(n).annotation.object(j).parts, 'hasparts')
                hasparts = str2num(D(n).annotation.object(j).parts.hasparts);
            end
            if isfield(D(n).annotation.object(j).parts, 'ispartof')
                ispartof = str2num(D(n).annotation.object(j).parts.ispartof);
            end
        end
        
        % only consider leaves:
        if isempty(hasparts) && ~isempty(ispartof)
            clear branch
            branch{1} = D(n).annotation.object(j).name;
            parent = str2num(D(n).annotation.object(j).parts.ispartof)+1;
            
            while ~isempty(parent)
                branch{end+1} = D(n).annotation.object(parent).name;
                if isfield(D(n).annotation.object(parent), 'parts') && isfield(D(n).annotation.object(parent).parts, 'ispartof')
                    parent = str2num(D(n).annotation.object(parent).parts.ispartof)+1;
                else
                    parent = [];
                end
            end
            
            br = sprintf('%s.',branch{end:-1:1}); br = br(1:end-1);

            m=m+1;
            branches{m} = br;
            
            %branch = branch(end:-1:1);
            %[tree, nodes] = addbranch(tree, branch);
            %for m = 1:length(nodes)
            %    tree.counts(nodes(m)) = tree.counts(nodes(m))+1;
            %end
        end
    end
end

[branches,~,h] = unique(branches);
threshold = 0;
counts = hist(h,1:max(h));
branches = branches(counts>threshold);
counts = counts(counts>threshold);

for m = 1:length(branches)
    branch = strsplit(branches{m},'.');
    
    branch = branch(end:-1:1);
    
    j = strmatch(branch{end}, names, 'exact');
    
    %branch{end} = sprintf('%s (%d)', branch{end}, namesCounts(j));
    %branch{1} = sprintf('%s (%d)', branch{1}, counts(m));
    
    [tree, nodes] = addbranch(tree, branch);
    tree.counts(nodes(1)) = counts(m);
    tree.counts(nodes(end)) = namesCounts(j);
end

for i = 1:length(tree.parent)
    if ~isempty(tree.counts(i)) && tree.counts(i)>0
        tree.nodewords{i} = sprintf('%s (%d)', tree.nodewords{i}, tree.counts(i));
    end
end

% add counts 
json = getStringBranch(tree,0);

function json = getStringBranch(tree, parent)

if parent == 0
    json = sprintf('{ "name": "SUN DATABASE"');
else
    json = sprintf('{ "name": "%s"', tree.nodewords{parent});
end

j = find(tree.parent == parent);
if ~isempty(j)
    json = [json sprintf(',\n"children": [\n')];
    for n = 1:length(j)
        json = [json getStringBranch(tree, j(n))];
    end
    json = json(1:end-2);
    json = [json sprintf('\n]\n')];
end

json = [json sprintf('},\n')];

if parent == 0
    json = json(1:end-2);
end

% Here is one example of a json string:
% {
%  "name": "SUN",
%  "children": [
%   {
%    "name": "kitchen",
%    "children": [
%     {
%      "name": "sink",
%      "children": [
%       {"name": "faucet", "size": 3938},
%       {"name": "sink", "size": 3812, "link": "http://www.test.edu"},
%       {"name": "HierarchicalCluster", "size": 6714},
%       {"name": "MergeEdge", "size": 743}
%      ]
%     },
%   ]
%  },
% }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [tree, nodes] = addbranch(tree, branch)
%
% Add a new branch to the tree

N = length(branch);
M = length(tree.parent);
parent = 0; %start on the root
for n = N:-1:1
    % two different nodes might have the same name!
    np = find(tree.parent==parent);
    node = strmatch(strtrim(branch{n}), tree.nodewords(np), 'exact');
    node = np(node);

    if isempty(node)
        % connect node to the root
        tree.parent(M+1) = parent;
        tree.nodewords{M+1} = strtrim(branch{n});
        nodes(n) = M+1;

        M = M+1;
        parent = M;
    else
        parent = node;
        nodes(n) = node;
    end
end


