function [ result ] = partitioning(X_l, Y_l, X_t, Y_t, X_eval, Y_eval , bandwiths_list)

number_bw=length(bandwiths_list);

errors=zeros(number_bw,1);
parfor i=1:number_bw
    
    Y_calc=partitioning_estimate_a(X_t,X_l,Y_l,bandwiths_list(i),mean(Y_l));
    errors(i)=sum((Y_calc-Y_t).^2);

end 

[~ , best_bw]=min(errors);


Y_calc=partitioning_estimate_a(X_eval,X_l,Y_l,bandwiths_list(best_bw),mean(Y_l));

result.mse=mean((Y_calc-Y_eval).^2);
result.res=Y_calc-Y_eval;
result.param=bandwiths_list(best_bw);

end

function [ part ] = part(x,h)
        
    % letzte Partition in [0,1]
    p = (1/h);

    % Partition errechnen. Jeweils der abgerundete Wert von x_i / h
    % ergibt die Partitionsnummer in der jeweiligen Dimension. Um die
    % "wahren" Partitionsnummern fuer Partition [0,h) bei 1 beginnen zu
    % lassen: +1
    %
    %  0 --[ 1 | 2 | ... |p-1| p ]-- p+1
    %    --|---|---| ... |---|---|--
    %      1   h  2h      (p-2)h ph
    part=1+floor(x/h);

    % Partition evtl korrigieren (Partitionsnummer <0 kommt in
    % Partition 0, Partition >p kommt in Partition p), X-Wert bei 1
    % kommt in Partition p+1.
    part(part<0)=0;
    %part(x==1)=p;
    part(part>p)=p+2;

end

function [Y_calc]=partitioning_estimate_a(X_t,X_l,Y_l,bw,const)
    
    [n,d] = size(X_t);
    
    X_t=part(X_t,bw);
    X_l=part(X_l,bw);
    
    [part_X part_Y]=partition(X_l,Y_l,d);
    
    Y_calc=zeros(n,1);
    
    [d b]=ismember(X_t,part_X,'rows');
    
    Y_calc(d)=part_Y(b(d));
    Y_calc(not(d))=const;
    
end


function [part_X,part_Y] = partition(X,Y,d)

%In the first step we sort the multidimesional datapoints, starting with
%the first dimension, then when 2 points have the same value use the second
%dimension etc.
[X,D]=sortrows(X,1:d);
%We apply the same changes on the values vector.
Y=Y(D);

%To save computing time we sort out the repetitions of the same cell in our
%data and compute the number of elements in this cell.

[part_X,B]=unique(X,'rows');%part_X returns a vector without repetitions, i.e. 
%the partition cell coordinates which are containing the datapoints from
%learning sample. B contains the last coordintes of this datapoints. 
c=length(B);
part_Y=zeros(c,1);
%The value of the first cell is the cumulative value of the points in the
%cell devided by their number.Which is B(1) because unique gives out the
%number of the last occurence of the first element.
part_Y(1)=sum(Y(1:B(1)))/B(1);

for i=1:c-1 %loop over the cells in our partition
    part_Y(i+1)=sum(Y((B(i)+1):B(i+1))/(B(i+1)-B(i)));
 %Recall that the array is sorted, so we can just sum all the values of our data with indices between ith
%and (i+1)th element of B, in order to gain the value of the partitioning
%cell.
end %for loop line 23


end %end of programm

