bls<-function(x0,x,y){
   x = cbind(x,1)
   b = (solve(t(x)%*%x)%*%t(x))%*%y
   y0 = t(b)%*%t(cbind(x0,1))
   return(y0)
}
knn<-function(x0,x,y,k){
   estimate = 0
   for(i in 1:k){
	 minDist = sum((x[1,]-x0)^2)
         minIndex = 1
         tmpEstimate = y[1]
	 for(j in 2:length(y)){
             tmpDist = sum((x[j,]-x0)^2)
	     if(tmpDist < minDist){
	        minDist = tmpDist
                tmpEstimate = y[j]
                minIndex = j
	     }              
	 }
         x<-x[-minIndex,]
	 y<-y[-minIndex]
	 estimate = estimate + tmpEstimate
   }
   estimate = estimate/k
   return(estimate)
}
BLS_Flag=FALSE  ##Change to FALSE for k-NN
######
## sin(x) Regression Example
######
set.seed(100)
x=runif(100,0,2*pi)
y=sin(x)+rnorm(100,,0.1)

xgrid=seq(0,2*pi,length=500)
n=length(xgrid)
ygrid=vector(length=n)
k=10
for(i in 1:n){
	if(BLS_Flag){
		ygrid[i]=bls(xgrid[i],x,y)
	}else{
		ygrid[i]=knn(xgrid[i],x,y,k)
	}
}
plot(x,y,pch=16)
lines(xgrid,ygrid,col=c("red"))
lines(xgrid,sin(xgrid),col=c("blue"))

######
## Simulated Example
######
x<-read.table("dat_3.txt",F)
y<-x[,3]
x<-x[,-3]
x=as.matrix(x)

xgrid1<-seq(min(x[,1]),max(x[,1]),length=100)
xgrid2<-seq(min(x[,2]),max(x[,2]),length=100)
n=length(xgrid1)
zgrid=matrix(0,n,n)
k=1
for(i in 1:n){
  for(j in 1:n){
	  if(BLS_Flag){
		  zgrid[i,j]=bls( cbind(xgrid1[i],xgrid2[j]),x,y)
	  }else{
		  zgrid[i,j]=knn( cbind(xgrid1[i],xgrid2[j]),x,y,k)
	  }
  }
}
plot(x,col=c("orange","blue")[y+1],pch=16,xlab="x1",ylab="x2")
for(i in 1:n){
	val<-as.numeric(zgrid[,i]>=0.5)+1
	points(xgrid1,rep(xgrid2[i],n),pch=".",col=c("orange","blue")[val])
}      
contour(xgrid1,xgrid2,zgrid,levels=0.5,add=TRUE,drawlabels=FALSE)