function [clabel, err_rate] = NN_euclidean(gdata, glabel, tdata, tlabel, nchunk)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 
% EU_NN.m
% Written by Wei Liu, Lexing Xie
% Nearest neighbor classification with Euclidean distance
% gdata (dXgn): the training data
% glabel (1Xgn): the label of the training set
% tdata (dXtn): the testing data
% tlabel (1Xtn): the label of the testing set
% element: the number of examples to process in each chunk, e.g. 2500
% error: the error rate
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if nargin<5, nchunk = 200; end
[d1, n1] = size(gdata);
[d2, n2] = size(tdata);
if exist('assert', 'builtin')
	assert(d1==d2, 'training and testing data should have the same dimension');
	assert(n1==length(glabel) && n2==length(tlabel), 'the number of labels must equal the number of samples') ;
end 

t0 = clock;
% compute the norm of the training vectors
try 
    g2 = sum(gdata.^2, 1)';
catch % break gdata into chunks if running into memory errors
    g2 = zeros(n1, 1);
    for i = 1 : nchunk*10 : n1
        j = min(n1, i+nchunk*10-1);
        ind = i: j ; 
        g2(ind) = sum(gdata(:,ind).^2, 1)';
    end
end
fprintf(1, ' done computing norms, %.3f sec\n', etime(clock,t0));

clabel = zeros(n2, 1); 
for i = 1 : nchunk : n2
    j = min(n2, i+nchunk-1);
    ind = i: j ; 
    % for each testing data sample
    % d(x, y) = (x-y)'(x-y) = x'x - 2x'y + y'y  
    % ... it suffices to compare - 2x'y + y'y
    dxy = -2*(tdata(:, ind)'*gdata)' + g2*ones(1,length(ind)) ;
    % find the nearest neighbor
    [md, mi] = min(dxy, [], 1);
    % copy the label
    clabel(ind) = glabel(mi); 
    
    if j==n2 || mod(j, 1000)==0
        fprintf(1, ' done classifying %5d examples, %.3f sec \n', j, etime(clock,t0));
    end
end

err_rate = sum(clabel(:)~=tlabel(:))/n2;


