/********************************************************
 * algorithm.c
 *
 * These are the routines for a near neighbor algorithm.
 *
 * This particular implementation is for finding the exact
 * nearest neighbor to a query, and the algorithm is the
 * brute force search which uses no preprocessing and
 * compares a query to every point of the data set.
 *
 * Sixth Annual DIMACS Implementation Challenge
 * Author:  Michael Goldwasser (wass@cs.princeton.edu)
 * Created: Jan 16, 1998
 *******************************************************/
 
#include <stdio.h>
#include <stdlib.h>
#include <values.h>
#include "algorithm.h"
#include "oracle.h"




typedef struct TrueDS {
  /*-- data structure --*/
  int       num_points;

  /*-- accounting --*/
  int       cost_pre;
  int       cost_queries;
} TrueDS;




int CostPreprocess(
  AbstractDS* ads
)
{
  TrueDS*  ds;
  
  ds = (TrueDS*) ads;

  return(ds->cost_pre);
}



int CostQueries(
  AbstractDS* ads
)
{
  TrueDS*  ds;
  
  ds = (TrueDS*) ads;

  return(ds->cost_queries);
}




AbstractDS* Preprocess(
  Oracle  *ora
)
{
  TrueDS*  ds;

  ds = (TrueDS*) malloc(sizeof(TrueDS));
  ds->cost_pre = 0;
  ds->cost_queries = 0;

  ds->num_points = InqNumPoints(ora);

  return((AbstractDS*) ds);
}



void DestroyAbstractDS(
 AbstractDS* ads
)
{
  TrueDS*  ds;
  
  ds = (TrueDS*) ads;
  free(ds);
}


 

void FindNeighbor(
  Oracle*      ora,
  AbstractDS*  ads,
  int          query
)
{
  int      i,min;
  int      qindex;
  int      numfields;
  double   mindist;
  double   tempdist;
  char*    assoc;
  TrueDS*  ds;
  

  ds = (TrueDS*) ads;
  qindex = query + ds->num_points;


  min = -1;
  mindist = MAXDOUBLE;
  for (i=0; i<ds->num_points; i++) {
    tempdist = InqDist(ora,qindex,i);
    ds->cost_queries++;		/*-- account for distance query --*/
    if (tempdist < mindist) {
      min = i;
      mindist = tempdist;
    }

  }



  /*--- Report Results ---*/
  numfields = InqNumFields(ora,qindex);
  printf("Query Point %3d: ",query);
  for (i=0; i<numfields; i++) {
    assoc = InqField(ora,qindex,i);
    printf("%s ",assoc);
    free(assoc);
  }
  printf("\n");



  numfields = InqNumFields(ora,min);
  printf("Neighbor is point %3d: ",min);
  for (i=0; i<numfields; i++) {
    assoc = InqField(ora,min,i);
    printf("%s ",assoc);
    free(assoc);
  }
  printf("\n");



  printf("Distance is %lf\n",mindist);
  printf("\n");


}