/* ======================================================================
   David W. Aha
   NGE: training.c: Training/testing procedures for NGE
   ====================================================================== */

#include "nge.h"

/* ======================================================================
   Seeding, training, and testing.
   ====================================================================== */
void train_and_test()
{ 
  /*==== Subfunctions ====*/
  void seed_exemplar_base();
  int process_instance();
  extern void print_general_info(),               /*==== Printing ====*/
              print_classification_results(),     /*==== Printing ====*/
              print_feature_weights();

  /*==== Local Variables ====*/
  FILE  *output_file;
  register int num_processed=number_of_seeds, inst_num, attribute;

  /*==== 1. Setup ====*/
  output_file = fopen(outputfile,"w");
  print_general_info(output_file);
  seed_exemplar_base();
  for(attribute=0; attribute<number_of_attributes; attribute++)
    feature_weights[attribute] = 1.0;

  /*==== 2. Read and process the remaining training instances (1 pass) ====*/
  for(inst_num=0; inst_num<num_training_instances; inst_num++)
    { num_processed += process_instance(inst_num,output_file,num_processed);
      /* 
      printf("Feature weights after processing inst_num %d:\n",inst_num);
      print_feature_weights();
      */
    }

  /*==== 3. Finish up options. ====*/
  if (testlast &&
      ((num_processed % testrate) != 0))         /*==== Don't repeat ====*/
     print_classification_results(output_file,num_processed);
  fclose(output_file); 
}

/* ======================================================================
   Processes a given training instance.  Yields 1 if processed, 0 otherwise.
   ====================================================================== */
int process_instance(inst_num,output_file,num_processed_so_far)
  register int inst_num, num_processed_so_far;
  FILE *output_file;
{
  /*==== Subfunctions ====*/
  int compute_distances();
  void classify_and_update(),
       print_classification_results();

  /*==== 1. Nothing to do if included during seeding ====*/
  if (used_as_a_seed[inst_num] == TRUE)
    return(0);

  /*==== 2. Otherwise, do everything ====*/
  classify_and_update(inst_num,compute_distances(inst_num,TRAINING));
  
  /*==== 3. Check to see if we must test now ====*/
  if (((num_processed_so_far+1) % testrate) == 0)
     print_classification_results(output_file,num_processed_so_far+1);

  /*==== 4. Yes, it was processed now ====*/
  return(1);
}

/* ======================================================================
   Computes distances of all exemplars to this training instance.  Records
   closest exemplars in order in the nearest_neighbors[] array.  Returns
   the number of exemplars stored in the nearest_neighbors[] array.
   ====================================================================== */
int compute_distances(inst_num,mode)
  register int inst_num, mode;
{
   /*==== Subfunctions ====*/
   int insert();
   float square();  
   extern double sqrt();
   void print_instance(), print_exemplar_distance(), print_feature_weights();

   /*==== Local Variables ====*/
   register int e, num_stored=0, a;   /* e=exemplar_num, a=attribute_num */
   float sum, instance[MAX_NUMBER_OF_ATTRIBUTES];

   /*==== 0. Setup ====*/
   if (mode == TRAINING)
     for(a=0; a<number_of_attributes; a++)
       instance[a] = training_instances[inst_num][a];
   else
     for(a=0; a<number_of_attributes; a++)
       instance[a] = testing_instances[inst_num][a];

   /*==== 1. Dynamic determination of weighted distance ====*/
   for(e=0; e<number_of_exemplars; e++)
     { /*==== 1.1 Compute distance for this exemplar ====*/
       sum = 0.0; 
       for(a=0; a<number_of_attributes;a++)
         { if (attribute_type[a] == SYMBOLIC_TYPE)
             { /*==== Handle symbolic-valued attribute ====*/
               if (exemplars[e][a][(int)instance[a]] == INCLUDED)
               sum += square(feature_weights[a]);
             }
            else 
             { /*==== Handle numeric-valued attribute  ====*/
               if (instance[a] < exemplars[e][a][LOWER])
                 sum += square(feature_weights[a] *
                               (exemplars[e][a][LOWER]-instance[a]));
               else if (instance[a]>exemplars[e][a][UPPER])
                 sum += square(feature_weights[a] *
                               (instance[a]-exemplars[e][a][UPPER]));
             }
	 }
        distances[e] = ((float)number_of_uses[e]/(float)number_correct[e]) *
                       (float)sqrt((double)sum);
        /* 
        if (mode == TESTING)
          { printf("yes, sum is %4.2f\n",sum);
            print_feature_weights();
            print_instance(inst_num,TESTING);
            print_exemplar_distance(e);
            printf("Testing distances[%d] = %4.2f\n",e,distances[e]);
            printf("(Uses/Correct)*sqrt(Sum) is (%d/%d)/sqrt(%4.2f)\n",
                    number_of_uses[e],number_correct[e],
                    sum);
          }
        */

        /*==== 1.2 Insert into nearest_neighbors[] array if needed ====*/
        if ((num_stored == 0) || 
            (distances[e] < distances[nearest_neighbors[0]]))
          num_stored = insert(e,0,num_stored);
        else if ((num_stored == 1) ||
                 (distances[e] <= distances[nearest_neighbors[1]]))
          num_stored = insert(e,1,num_stored);
     }
  return(num_stored);
}

/* ======================================================================
   Inserts an exemplar index into the nearest_neighbors[] array.  Returns
   the number currently stored after the insertion.  Cares only about the
   ordering of the nearest 2 exemplars and those tied with it (wrt distance).
   ====================================================================== */
int insert(exemplar_num,insertion_location,num_stored)
  register int exemplar_num, insertion_location, num_stored;
{
  /*==== Local variables ====*/
  register int i;

  if (insertion_location == 0)
    { for(i=num_stored; i>0; i--)
        nearest_neighbors[i] = nearest_neighbors[i-1];
      nearest_neighbors[0] = exemplar_num;
      if ((num_stored >= 2) &&
          (distances[nearest_neighbors[1]] < distances[nearest_neighbors[2]]))
        return(2);
      else
        return(num_stored+1);
    }
  else /*==== insertion_location is 1 ====*/
    { if ((num_stored == 1) ||
          (distances[exemplar_num] < distances[nearest_neighbors[1]]))
        { nearest_neighbors[1] = exemplar_num;
          return(2);
        }
      else /*==== (num_stored > 1) and it's a tie ====*/
        { nearest_neighbors[num_stored] = exemplar_num;
          return(num_stored+1);
        }
    }
}

/* ======================================================================
   Classifies the given instance, using the info in distances[].  Updates
   hyperrectangles and weights appropriately.
   ====================================================================== */
void classify_and_update(inst_num,num_stored)
  register int inst_num, num_stored;
{
  /*==== Subfunctions ====*/
  void update(), insert_exemplar(), find_nearest_exemplar();
  void print_instance(), print_exemplars_distances();

  /*==== Local variables ====*/
  register int result;

  /*==== 0. Setup (temporary) ====*/
  /* printf("\n");
  print_instance(inst_num,TRAINING);
  print_exemplars_distances();
  */

  /*==== 1. Classify and update wrt nearest exemplar ====*/
  find_nearest_exemplar(0,num_stored);  /*==== In nearest_neighbors[0] ====*/
  if (class[nearest_neighbors[0]] ==
      (int)training_instances[inst_num][number_of_attributes])
    { /*==== 1.1 Correct classification ====*/
      update(nearest_neighbors[0],inst_num,CORRECT);
      result = CORRECT;
    }
  else
    { /*==== 1.2 Incorrect classification ====*/
      update(nearest_neighbors[0],inst_num,INCORRECT);
      result = INCORRECT;
    }

  /*==== 2. If not greedy, process also with 2nd nearest exemplar ====*/
  if (!greedy && (number_of_exemplars > 1))
    { find_nearest_exemplar(1,num_stored); 
      if (class[nearest_neighbors[1]] ==
	  (int)training_instances[inst_num][number_of_attributes])
	{ /*==== 1.1 Correct classification ====*/
	  update(nearest_neighbors[1],inst_num,CORRECT);
	  result = CORRECT;
	}
      else
	{ /*==== 1.2 Incorrect classification ====*/
	  update(nearest_neighbors[1],inst_num,INCORRECT);
	  result = INCORRECT;
	}
    }

  /*==== 3. If incorrect classification, then store it ====*/  
  if (result == INCORRECT) 
    insert_exemplar(inst_num);
}

/* ======================================================================
   Finds nearest or second-nearest exemplar (determined by given index).
   Assumes that there are at least "index+1" numbers of stored exemplars.
   ====================================================================== */
void find_nearest_exemplar(index,num_stored)
  register int index, num_stored;
{
  /*==== Subfunctions ====*/
  float area_of_exemplar();

  /*==== Local variables ====*/
  register int i, num_tied=1, original, selected;
  int tied_exemplar[MAX_NUMBER_OF_EXEMPLARS];
  float area_tied_exemplars, area;

  if ((num_stored >= (index+1)) &&
      (distances[nearest_neighbors[index]] < 
       distances[nearest_neighbors[index+1]]))
    /*==== 1. Nothing to do; no tie here ====*/
    return;
  else 
    { /*==== 2.1 Find set of tied exemplars ====*/
      tied_exemplar[0] = original = nearest_neighbors[index];
      area_tied_exemplars = area_of_exemplar(tied_exemplar[0]);
      for(i=index+1; i<num_stored; i++)
        { area = area_of_exemplar(nearest_neighbors[i]);
          if (area == area_tied_exemplars)
            { tied_exemplar[num_tied] = i;
              num_tied++;
            }
          else if (area < area_tied_exemplars)
	    { tied_exemplar[0] = i;
              num_tied = 1;
              area_tied_exemplars = area;
            }
	}

      /*==== 2.2 Select randomly from this tie and switch their ordering ====*/
      selected = tied_exemplar[random() % num_tied];
      nearest_neighbors[original] = selected;
      nearest_neighbors[selected] = original;
    }
}

/* ======================================================================
   Computes the area of the given exemplar.
   e=exemplar_num, a=attribute_num
   ====================================================================== */
float area_of_exemplar(e)
  register int e;
{
  /*==== Subfunctions ====*/
  float num_values_covered();  /*==== Note that this yields a float ====*/

  /*==== Local variables ====*/
  float area_so_far = 1.0;
  register int a;

  /*==== 1. Compute it ====*/
  for(a=0; a<number_of_attributes; a++)
    if (attribute_type[a] == SYMBOLIC_TYPE)
      area_so_far *= num_values_covered(e,a)/(float)num_values[a];
    else /*==== Numeric type ====*/
      area_so_far *= (exemplars[e][a][UPPER] - exemplars[e][a][LOWER]);

  /*==== 2. Return it ====*/
  return(area_so_far);
}

/* ======================================================================
   Computes number of symbolic values covered for this exemplar for this
   symbolic-valued attribute.
   ====================================================================== */
float num_values_covered(exemplar_num,attribute_num)
  register int exemplar_num, attribute_num;
{
  /*==== Local variables ====*/
  register int num_value, num_covered=0;

  /*==== 1. Compute the number covered ====*/
  for(num_value=0; num_value<num_values[attribute_num]; num_value++)
    if (exemplars[exemplar_num][attribute_num][num_value] == INCLUDED)
      num_covered++;
 
  /*==== 2. Return a float ====*/
  return((float)num_covered);
}

/* ======================================================================
   Updates the given exemplar's weights and, if needed, its hyperrectangle's
   size also.
   ====================================================================== */
void update(exemplar_num,inst_num,result)
  register int exemplar_num, inst_num, result;
{
  /*==== Subfunctions ====*/
  void update_attribute_weight(), update_hypperrectangle();
  int matches();
  
  /*==== Local variables ====*/
  register int attribute_num, match_result;

  /*==== 1. Update correctness counts for exemplar weight ====*/
  number_of_uses[exemplar_num]++;
  if (result == CORRECT)
    number_correct[exemplar_num]++;

  /*==== 2. Update attribute weights ====*/
  for(attribute_num=0; attribute_num<number_of_attributes; attribute_num++)
    { match_result = matches(exemplar_num,inst_num,attribute_num);
      update_attribute_weight(match_result,result,attribute_num);
    }
      
  /*==== 3. Update area of hyperrectangle ====*/
  if (result == CORRECT)
    for(attribute_num=0; attribute_num<number_of_attributes; attribute_num++)
      update_hypperrectangle(exemplar_num,inst_num,attribute_num);
}

/* ======================================================================
   Yields TRUE iff the instance's attribute's value matches the exemplar's
   attribute's values.  e=exemplar_num and a=attribute_num.
   ====================================================================== */
int matches(e, inst_num, a)
  register int e, inst_num, a;
{
  if (attribute_type[a] == SYMBOLIC_TYPE)
    { if (exemplars[e][a][(int)training_instances[inst_num][a]] == INCLUDED)
        return(TRUE);
      else
        return(FALSE);
    }
  else /*==== Numeric-valued attribute ====*/
    if ((exemplars[e][a][LOWER] <= training_instances[inst_num][a]) &&
        (exemplars[e][a][UPPER] >= training_instances[inst_num][a]))
      return(TRUE);
    else
      return(FALSE);
}

/* ======================================================================
   Updates an attribute weight
   ====================================================================== */
void update_attribute_weight(match_result,classification_result,attribute_num)
  register int match_result, classification_result, attribute_num;
{
  if (((classification_result == CORRECT) && (match_result == TRUE)) ||
      ((classification_result == INCORRECT) && (match_result == FALSE)))
    feature_weights[attribute_num] *= (1.0 + feature_adjustment_rate);
  else
    feature_weights[attribute_num] *= (1.0 - feature_adjustment_rate);
}

/* ======================================================================
   Updates the size of the exemplar's hyperrectangle after a correct 
   classification guess.  1 attribute at a time.  e=exemplar_num and
   a=attribute_num.
   ====================================================================== */
void update_hypperrectangle(e,inst_num,a)
  register int e,inst_num,a;
{
  if (attribute_type[a] == SYMBOLIC_TYPE)
    exemplars[e][a][(int)training_instances[inst_num][a]] = INCLUDED;
  else /*==== Numeric-valued attribute ====*/
    { if (exemplars[e][a][LOWER] > training_instances[inst_num][a])
        exemplars[e][a][LOWER] = training_instances[inst_num][a];
      if (exemplars[e][a][UPPER] < training_instances[inst_num][a])
        exemplars[e][a][UPPER] = training_instances[inst_num][a];
    }
}

/* ======================================================================
   Selects the seeds to use to initialize the exemplar base.
   ====================================================================== */
void seed_exemplar_base()
{
  /*==== Subfunctions ====*/
  void insert_exemplar();

  /*==== Local variables ====*/
  register int i, seed;

  /*==== Select the seeds ====*/
  for(i=0; i<number_of_seeds; i++)
    { seed = ((int)random() % num_training_instances);
      if (used_as_a_seed[seed] == FALSE)
        { used_as_a_seed[seed] = TRUE;
          insert_exemplar(seed);
        }
      else /*==== Try again ====*/
        i--;
    }
}

/* ======================================================================
   Adds a training instance inst_num to the exemplar base.  
   ====================================================================== */
void insert_exemplar(inst_num)
  register int inst_num;
{
  /*==== Local variables ====*/
  register int attribute_num, i, index;

  /*==== 1. Insert the given training instance ====*/
  for(attribute_num=0; attribute_num<number_of_attributes; attribute_num++)
    if (attribute_type[attribute_num] == NUMERIC_TYPE)
      exemplars[number_of_exemplars][attribute_num][LOWER] = 
       exemplars[number_of_exemplars][attribute_num][UPPER] = 
         training_instances[inst_num][attribute_num];
    else /*==== Symbolic value; only one included so far ====*/
      { for(i=0; i<MAX_NUMBER_OF_SYMBOLIC_VALUES_PER_ATTRIBUTE; i++)
          exemplars[number_of_exemplars][attribute_num][i] = NOT_INCLUDED;
        index = (int)training_instances[inst_num][attribute_num];
        exemplars[number_of_exemplars][attribute_num][index] = INCLUDED;
      }

  /*==== 2. Insert its class ====*/  
  class[number_of_exemplars] = 
    (int)training_instances[inst_num][number_of_attributes];

  /*==== 3. Initialize its exemplar weight information ====*/
  number_correct[number_of_exemplars] = 1;
  number_of_uses[number_of_exemplars] = 1;

  /*==== 4. Note that we've added another ====*/
  number_of_exemplars++;
}

/* ======================================================================
   Square for floats
   ====================================================================== */
float square(x)
  float x;
{
  return(x*x);
}