function [recogRate, hitIndex, nearestIndex] = knnrLoo(DS, param, plotOpt)
%knnrLoo: Leave-one-out recognition rate of KNNR
%	Usage: [recogRate, hitIndex, nearestIndex] = knnrLoo(DS, param, plotOpt)
%		recogRate: recognition rate
%		hitIndex: Index of correctly classified points
%		nearestIndex: Nearest sample index of all data points
%		DS: Design set
%			DS.input: Input data (each column is a feature vector)
%			DS.output: Output class (ranging from 1 to N)
%		param: Classifier parameters
%			param.k: The "k" in k-nearest neighbor rule
%			param.smallSet = 0 for small data set (vectorized operation based), 1 for large data set (for-loop based)
%		plotOpt: 1 for ploting data (2D only)
%
%	Type "knnrLoo" to see an example.

%	Roger Jang, 19970628, 20040928

if nargin==0, selfdemo; return; end
if nargin<2, param.k=1;	param.smallSet=size(DS.input, 2)<=1000; end
if isempty(param), param.k=1;	param.smallSet=size(DS.input, 2)<=1000; end
if nargin<3, plotOpt=0; end
if isempty(param), param.k=1;	param.smallSet=size(DS.input, 2)<=1000; end

[dim, dataNum] = size(DS.input);
if param.smallSet			% Vectorized operation; suitable for small dataset
	classLabel = elementCount(DS.output);
	classNum = length(classLabel);
	distMat = pairwiseSqrDist(DS.input);
	distMat(1:(dataNum+1):dataNum^2) = inf;	% Set diagonal elements to inf

	% knnrMat(i,j) = class of i-th nearest point of j-th input vector
	[junk, nearestIndex] = sort(distMat, 1);
	knnrMat = DS.output(nearestIndex(1:param.k,:));
	% classCount(i,j) = count of class-i points within j-th input vector's neighborhood
	classCount = zeros(classNum, dataNum);
	for i = 1:dataNum,
		[sortedElement, count] = elementCount(knnrMat(:,i));
		classCount(sortedElement, i) = count;
	end
	[junk, computed] = max(classCount, [], 1);
else						% For-loop version; suitable for large dataset
	nearestIndex = zeros(1, dataNum);
	computed = zeros(size(DS.output));
	for i=1:dataNum
	%	if rem(i, 100)==0, fprintf('%d/%d\n', i, dataNum); end
		looData = DS;
		looData.input(:,i) = [];
		looData.output(:,i) = [];
		TS.input=DS.input(:,i);
		TS.output=DS.output(:,i);
		[computed(i), junk, tmp] = knnr(looData, TS, param.k);
		nearestIndex(i) = tmp(1);
		if nearestIndex(i)>=i,
			nearestIndex(i)=nearestIndex(i)+1;
		end
	end
end
hitIndex = find(DS.output==computed);
recogRate = length(hitIndex)/dataNum;

if plotOpt & dim==2
	dcprDataPlot(DS);
	axis image; box on
	missIndex=1:dataNum;
	missIndex(hitIndex)=[];
	% display these points
	for i=1:length(missIndex),
		line(DS.input(1,missIndex(i)), DS.input(2,missIndex(i)), 'marker', 'x', 'color', 'k');
	end
	titleString = sprintf('There are %d leave-one-out error points denoted by "x".', length(missIndex));
	title(titleString);
end

% ====== Self demo ======
function selfdemo
DS=prData('random2');
param.k = 1;
param.smallSet = 1;	% small dataset
plotOpt=1;
[recogRate, hitIndex, nearestIndex] = feval(mfilename, DS, param, plotOpt);