##' Point Matching
##'
##' @param x,y  TSP instances
##'
##' @return matrix of point indices with shortest distance


eucl_distance <- function(x, y){
  sapply(1:nrow(y), function(i) { sqrt(crossprod(x - y[i,])) })
}


#### concept: search for minimal possible distance in an iterative manner

point_matching <- function(x,y) {

    # all distances to y_i's from each point in x    
    lists_dists <- lapply(1:nrow(x), function(i) eucl_distance(x[i,], y))
    
    len         <- length(lists_dists)
    
    # initialize index matrix
    ind         <- matrix(c(1:len,rep(0,len)),byrow=FALSE,ncol=2,nrow=len)
        
    for (i in c(1:len)){    
        
        # index of point in x for which the minimum distance to all points in y is smallest
        m  <- which.min(do.call(rbind,lapply(lists_dists,function(x) min(x, na.rm=TRUE))))
        #print(m)    
        
        # index of point in y with smallest distance 
        ind[m,2] <- which.min(lists_dists[[m]])
        
        # discard the selected point in y                 
        for (j in c(1:len)[-m]){
                if((is.na(lists_dists[[j]][1]) == TRUE) | (is.finite(lists_dists[[j]][1]))){
                    lists_dists[[j]][ind[m,2]] <- NA
                }
        }
        
        # set entry to Infinity to avoid repeated selection
        lists_dists[m] <- Inf
    }
    
    return(ind)
}
