/************************************************************************
 *                                                                      *
 *  Program package         T O O L D I A G                             *
 *                                                                      *
 *  Version   1.5                                                       *
 *  Date:     Tue Feb  8 13:39:06 1994                                  *
 *                                                                      *
 *  NOTE: This program package is copyrighted in the sense that it      *
 *  may be used for scientific purposes. The package as a whole, or     *
 *  parts thereof, cannot be included or used in any commercial         *
 *  application without written permission granted by the author.       *
 *  No programs contained in this package may be copied for commercial  *
 *  distribution.                                                       *
 *                                                                      *
 *  All comments  concerning this program package may be sent to the    *
 *  e-mail address 'tr@fct.unl.pt'.                                     *
 *                                                                      *
 ************************************************************************/



#include <stdio.h>
#include <string.h>
#include <math.h>
#include "def.h"

extern universe *U;
extern bool verbose;
extern float Euclidian_Distance();

static bool interact = TRUE;
static bool first_prototype_random = FALSE;
static str80 buf, pfName, symbolicFeature;
static char wheel[] = "|/-\\";
static int nrFeat;


typedef struct ProType_ {
          FeatVector value;
          bool outlier;
          int nrFriends;
          int *friends;
        } ProType;

typedef struct ProtypeClass_ {
          str30 name;
          int numProtype;
          ProType *PT;
        } ProtypeClass,  *ProtypeClasses;

#define EPSILON (0.000000000000001)  /**/
#define UNDEFINED (-1)

static ProtypeClasses PTC = NULL;
static ProType *PurgedPT = NULL;
static ProType allPT = { NULL, FALSE, 0, NULL };
static FeatVector Samples = NULL;


#define UPDATE_MEAN 1
#define UPDATE_MARGINAL_MEDIAN 2
#define UPDATE_VECTOR_MEDIAN 3
static int update_method = UPDATE_MEAN;

static void init_qstar()
{
 /* Ask for the update method */
 printf("\n ---- Update rule for the prototype ----\n");
 printf("\n\tUpdate as the MEAN(1), MARGINAL MEDIAN(2) or VECTOR MEDIAN(3)\n");
 printf("\t of the correctly classified neighbors? %d\b", update_method );
 get_d_range( &update_method, UPDATE_MEAN,
	UPDATE_VECTOR_MEDIAN, LEFT_CLOSED__RIGHT_CLOSED );
 printf("\n\tInitialize first prototype of each class randomly (y/n)?n\b");
 gets( buf );
 if( buf[0] == 'y' )
   first_prototype_random = TRUE;
 if( ! first_prototype_random )
   printf(" Inializing first prototype conforming update rule.\n\n");
}


static void init_ProType( PT )
ProType *PT;
{
 PT->value = NULL;
 PT->outlier = TRUE;

 PT->nrFriends = 0;
 PT->friends = NULL;
}


static void free_ProType( PT )
ProType *PT;
{
 FREE( PT->value );
 PT->outlier = TRUE;

 PT->nrFriends = 0;
 FREE( PT->friends );
}


static void join_friend( friend, PT )
int friend;
ProType *PT;
{
 int i, *newFriends = NULL;

 newFriends = (int*) malloc( (1+PT->nrFriends) * sizeof(int) );
 CHKPTR( newFriends );
 for( i = 0; i < PT->nrFriends; i++ )
   newFriends[ i ] = PT->friends[i];
 newFriends[ PT->nrFriends ] = friend;
 (PT->nrFriends)++;
 FREE( PT->friends );
 PT->friends = newFriends;
}


static void show_friends( PT )
ProType *PT;
{
 int i;

 printf("\nPrototype has %d friends:\n\t( ", PT->nrFriends ); 
 for( i = 0; i < PT->nrFriends; i++ )
   printf("%d ", PT->friends[i] );
 printf(")\n\n");
}


static void copy_PT( PTsrc, PTdest, dim )
ProType *PTsrc, *PTdest;
int dim;
{
 int i;

 copy_FV( PTsrc->value, PTdest->value, dim ); 
 PTdest->outlier = PTsrc->outlier;

 PTdest->nrFriends = PTsrc->nrFriends;
 if( PTsrc->nrFriends > 0 )
 {
   PTdest->friends = (int*) malloc( PTdest->nrFriends * sizeof(int) );
   CHKPTR( PTdest->friends );
   for( i = 0; i < PTdest->nrFriends; i++ )
     PTdest->friends[i] = PTsrc->friends[i];
 }
} 


static void free_PTC()
{
 int i, p;

 if( PTC == NULL )
   return;
 for( i = 0; i < U->nrClass; i++ )
 {
   for( p = 0; p < PTC[i].numProtype; p++ )
     free_ProType( &(PTC[i].PT[p]) );
   PTC[i].numProtype = 0;
   FREE( PTC[i].PT );
 }
 FREE( PTC );
}


static void init_PTC()
{
 int i, class;

 if( PTC != NULL )
   free_PTC();
 PTC = (ProtypeClass*) malloc( U->nrClass * sizeof(struct ProtypeClass_) );
 for( i = 0; i < U->nrClass; i++ )
 {
   class = i;
   strcpy( PTC[i].name, U->C[class].name );
   PTC[i].numProtype = 0;
   PTC[i].PT = NULL;
 }
}


static void gen_selected_samples( verbose )
bool verbose;
{
 int i, j, k, s, class;
 int totSmp = 0, row, nrSmp;

 for( i = 0; i < U->nrClass; i++ )
 {
   class = i;
   totSmp += U->C[class].numSampl;
 }
 Samples= (FeatVector) malloc( totSmp * U->nrSelFeat * sizeof(FeatVector*) );
 CHKPTR( Samples );

 /* copy the global sample values to the local variable */

 row = 0;
 if( verbose )
   printf(" S A M P L E S:\n");
 for( i = 0; i < U->nrClass; i++ )
 {
   class = i;
   nrSmp = U->C[class].numSampl;
   if( verbose )
     printf("Class: %d = %s - Nr. Samples: %d\n",i+1,U->C[class].name,nrSmp);
   for( s = 0; s < nrSmp; s++ )
   {
     if( verbose )
       printf(" Nr. %3d", row );
     for( k = 0; k < U->nrSelFeat; k++ )
       Samples[ row*U->nrSelFeat+k ] =
             U->C[ class ].S[ U->nrFeat * s + U->FSV[k].rank ];
     if( verbose )
       showFV( U->nrSelFeat, &(Samples[ row*U->nrSelFeat ]) ); /**/
     row++;
   }
 }
}


/*
 *  Calulate the performance index of a clustering.
 *  It is based on the sum of the squared errors
*/
static float performance_index()
{
 int i, j, class, p, row;
 float dist, minDist, sumDist = 0.0;
 FeatVector Sample = NULL;

 /* for all samples of all classes calculate the distance to
    their optimal cluster center
 */
 row = 0;
 for( i = 0; i < U->nrClass; i++ )
 {
   class = i;
   for( j = 0; j < U->C[class].numSampl; j++ )
   {
     Sample = &(Samples[U->nrSelFeat*row]);
     minDist = INFINITY;
     for( p = 0; p < PTC[class].numProtype; p++ )
     {
       dist = Euclidian_Distance( PTC[i].PT[p].value, Sample, U->nrSelFeat );
       if( dist < minDist )
       {
         minDist = dist;
       }
     }
     sumDist += minDist;
     row++;
   }
 }
 return( sumDist );
}

 
static void show_PTC( showFriends )
bool showFriends;
{
 int i, p;

 printf("\n-------------- P R O T O T Y P E S  -------------------\n");
 for( i = 0; i < U->nrClass; i++ )
 {
   printf("%4d prototypes for class: %2d = %s\n",
                 PTC[i].numProtype, i+1, U->C[i].name );
   for( p = 0; p < PTC[i].numProtype; p++ )
   {
     printf(" Nr. %3d: ", p+1 );
     if( PTC[i].PT[p].outlier )
       printf("Outlier!");
     else
       printf("        ");
     showFV( U->nrSelFeat, PTC[i].PT[p].value );
     if( showFriends )
       show_friends( &(PTC[i].PT[p]) );
   }
 }
 printf(" Performance index =\t%20.10f\n", performance_index() );
 printf("-------------------------------------------------------\n");
}


static void purge_outliers()
{
 int i, p, smpClass, k, row, s, nrSmp;
 int numOutliers, *outlierInd = NULL, newPtr;
 float dist;

 printf(" --- Purging outliers ---\n");
 for( i = 0; i < U->nrClass; i++ )
 {
   printf(" %4d prototypes for class: %2d = %s\n",
                 PTC[i].numProtype, i+1, U->C[i].name );
   numOutliers = 0;
   outlierInd = (int*) malloc( PTC[i].numProtype * sizeof(int) );
   if( outlierInd == NULL )
     { printf("purge_outliers> No space! Exitus...\n"); exit(1); }
   for( p = 0; p < PTC[i].numProtype; p++ )
   {
     outlierInd[p] = FALSE;
     if( verbose )
     {
       printf("Prototype Nr. %3d: ", p+1 );
       showFV( U->nrSelFeat, PTC[i].PT[p].value );
     }
     if( PTC[i].PT[p].outlier )
     {
       outlierInd[p] = TRUE;
       numOutliers++;
     }
   }
   /* ouliers are found : purge them from the prototypes */
   /* purge only if the class has at least one prototypes that is no outlier */
   if( numOutliers > 0 && (PTC[i].numProtype > numOutliers) )
   {
     printf("\t*** Found %d outliers for class %d\n", numOutliers, i+1 );
     PurgedPT = (ProType*)
                     malloc((PTC[i].numProtype-numOutliers)*sizeof(ProType));
     if( PurgedPT == NULL )
       { printf("purge_outliers> No space for PurgedPT! Exitus...\n");exit(1); }
     newPtr = 0;
     for( p = 0; p < PTC[i].numProtype; p++ )
     {
       if( outlierInd[p] == FALSE )
       {
         /* no outlier: copy */
         init_ProType( &(PurgedPT[newPtr]) );
         PurgedPT[newPtr].value =
                       (FeatVector)malloc(U->nrSelFeat*sizeof(FeatVector*));
         copy_PT( &(PTC[i].PT[p]), &(PurgedPT[newPtr]), U->nrSelFeat );
         newPtr++;
       }
     }
     /* change and free the pointers */
     for( p = 0; p < PTC[i].numProtype; p++ )
       free_ProType( &(PTC[i].PT[p]) );
     FREE( PTC[i].PT );
     PTC[i].numProtype = PTC[i].numProtype-numOutliers;
     PTC[i].PT = PurgedPT;
     PurgedPT = NULL;
   }
   FREE( outlierInd );
 }
}


static void calc_mean( mean, PT )
FeatVector mean;
ProType *PT;
{
 int k, i;

 for( k = 0; k < nrFeat; k++ )
 {
   mean[k] = 0.0;
   for( i = 0; i < PT->nrFriends; i++ )
   {
     mean[k] += Samples[ nrFeat * PT->friends[i] + k ];
   }
   mean[k] /= PT->nrFriends;
 }
}


static int order_rule( real1, real2 )
float *real1, *real2;
{
 if( *real1 > *real2 ) return((int)1);
 if( *real1 < *real2 ) return((int)-1);
 return((int)0);
}


#define xxxPEEP_MED 10
/*
 * Calculate the Vector median
 * This seems to be a quite new approach from Tampere University.
 * The vector median of n multidimensional samples is the sample 
 * with the minimum sum of Euclidean distances to the other samples. 
 * So, for every sample one has to compute the sum of distances to 
 * the other samples and then to choose the minimum. 
*/
static void calc_VectorMedian( median, PT )
FeatVector median;
ProType *PT;
{
 int k, i, j, nrf, minFriend;
 FeatVector EuclidDistsSum = NULL;
 bool odd, even, found;
 float dist, minDist;

 nrf =  PT->nrFriends;

 /* Two special cases: Only one or two friends */
 if( nrf == 1 )
 {
   copy_FV( &(Samples[nrFeat*PT->friends[0]]), median, nrFeat );
#ifdef PEEP_MED
   printf("\n --- Only 1 friend: MEDIAN[%d] =", PT->friends[0] );
   showFV( nrFeat, median );
   printf("Friend:\n");
   showFV( nrFeat, &(Samples[nrFeat*PT->friends[0]]) ); DBG;
#endif
   return; 
 }
 /* Take the mean of the two friends */
 if( nrf == 2 )
 {
   for( k = 0; k < nrFeat; k++ )
     median[k] = ( Samples[nrFeat*PT->friends[0]+k] +
             Samples[nrFeat*PT->friends[1]+k] ) / 2.0;
#ifdef PEEP_MED
   printf("\n --- Only 2 friends: MEDIAN[%d,%d] =",
		 PT->friends[0], PT->friends[1] );
   showFV( nrFeat, median );
   printf("Friends:\n");
   showFV( nrFeat, &(Samples[nrFeat*PT->friends[0]]) );
   showFV( nrFeat, &(Samples[nrFeat*PT->friends[1]]) ); DBG;
#endif
   return; 
 }

 EuclidDistsSum = (FeatVector) malloc( nrf * sizeof( FeatVector* ) );
 CHKPTR( EuclidDistsSum );

 /* calculate the sum of all Euclidean distance for each friend from all
    other friends */
 for( i = 0; i < nrf; i++ )
 {
   EuclidDistsSum[ i ] = 0.0;
   for( j = 0; j < nrf; j++ )
   {
     if( i != j )
     {
       dist = Euclidian_Distance( &(Samples[nrFeat*PT->friends[i]]),
                                  &(Samples[nrFeat*PT->friends[j]]), nrFeat );
       /*printf("\tdist(%d,%d)=%f\n", PT->friends[i], PT->friends[j], dist);/**/
       EuclidDistsSum[ i ] += dist;
     }
   }
#ifdef PEEP_MED
   if( nrf < PEEP_MED )
   {
     printf("Distance=%f  Sample=%d  ", EuclidDistsSum[ i ], PT->friends[i] );
     showFV( nrFeat, &(Samples[nrFeat*PT->friends[i]]) ); /**/
   }
#endif
 }
 /* determine the minimum sum of distances */
 minDist = INFINITY;
 for( i = 0; i < nrf; i++ )
 {
   if( EuclidDistsSum[ i ] < minDist )
   {
     minDist = EuclidDistsSum[ i ];
     minFriend = i;
   }
 }
 copy_FV( &(Samples[nrFeat*PT->friends[minFriend]]), median, nrFeat );
#ifdef PEEP_MED
 if( nrf < PEEP_MED )
 {
   printf("VECTOR MEDIAN\n");
   showFV( nrFeat, &(Samples[nrFeat*PT->friends[minFriend]]) ); /**/
   printf("\n");
 }
#endif
 FREE( EuclidDistsSum );
}


/*
 * Calculate the marginal median, i. e. the vector of the univariate
 * medians for each individual feature
*/
static void calc_marginalMedian( median, PT )
FeatVector median;
ProType *PT;
{
 int k, i, nrf;
 FeatVector seq = NULL;
 bool odd, even;

 nrf =  PT->nrFriends;
 seq = (FeatVector) malloc( nrf * sizeof( FeatVector* ) );
 CHKPTR( seq );

 odd = nrf % 2 == 1;
 even = nrf % 2 == 0; 

 /* univariate vesion */
 for( k = 0; k < nrFeat; k++ )
 {
   for( i = 0; i < nrf; i++ )
     seq[ i ] = Samples[ nrFeat * PT->friends[i] + k ];
   /* showFV( nrf, seq ); /**/
   qsort( seq, nrf, sizeof(float), order_rule );
   /* showFV( nrf, seq ); DBG; /**/

   if( odd )
     median[ k ] = seq[ (nrf-1)/2 ];
   if( even )
     median[ k ] = (seq[ nrf/2 - 1 ] + seq[ nrf/2 ]) / 2.0;
   /* printf("median[%d] = %f", k, median[k] ); DBG; /**/
 }
 FREE( seq );
}


static bool update_friends( PT )
ProType *PT;
{
 FeatVector newPTvalue = NULL;
 int i, k;
 bool isEqual, change = FALSE;

 if( PT->nrFriends == 0 )
   return;


 newPTvalue = (FeatVector) malloc( nrFeat * sizeof( FeatVector* ) );
 CHKPTR( newPTvalue );

 if( PT->nrFriends > 1 )
   PT->outlier = FALSE;
 else
 {
   /* only reset the outlier predicate if the close sample
      it not the prototype itself
   */
   isEqual = TRUE;
   for( k = 0; k < nrFeat; k++ )
     isEqual = isEqual && Samples[nrFeat * PT->friends[0] + k] == PT->value[k];
   if( ! isEqual )
     PT->outlier = FALSE;
 }

 switch( update_method )
 {
   case UPDATE_MEAN : calc_mean( newPTvalue, PT ); break;
   case UPDATE_MARGINAL_MEDIAN : calc_marginalMedian( newPTvalue, PT );  break;
   case UPDATE_VECTOR_MEDIAN : calc_VectorMedian( newPTvalue, PT );  break;
   default : fprintf(stderr,"Trouble with update method - exit...\n"); exit(1);
 } 

 /* Check if there was a change */
 for( k = 0; k < nrFeat; k++ )
 {
   if( fabs( newPTvalue[k] - PT->value[k] ) > EPSILON )
     change = TRUE;
 }

 FREE( PT->value );
 PT->value = newPTvalue;

 PT->nrFriends = 0;
 FREE( PT->friends );
 return( change );
}


/*
 *  update the prototypes of this class by attribute them the
 *  mean of all samples that belong to their domain.
*/
static bool update_Class( class, dim )
int class, dim;
{
 int p;
 bool proType_change = FALSE;

 /* update all prototypes for this class (exept last prototype which
     was just inserted without close samples
 */
 for( p = 0; p < PTC[class].numProtype; p++ )
 {
   if( PTC[class].PT[p].nrFriends > 0 )
     proType_change = update_friends( &(PTC[class].PT[p]) );
 }
 return( proType_change );
}


void discretize( Sample, symbolicFeature, nearestClass, nearestProt )
FeatVector Sample;
char *symbolicFeature;
int *nearestClass, *nearestProt;
{
 float dist, minDist;
 int p, a, minClass, minProt;

 minDist = INFINITY;
 /* look for the prototype which is closest to this sample */ 
 for( a = 0; a < U->nrClass; a++ )
 {
   for( p = 0; p < PTC[a].numProtype; p++ )
   {
     dist = Euclidian_Distance( PTC[a].PT[p].value, Sample, U->nrSelFeat );
     if( dist < minDist )
     {
       minDist = dist;
       minClass = a;
       minProt = p;
     }
   }
 }
 /* the nearest prototype is now found */
 sprintf( symbolicFeature, "%d-%d", minClass, minProt );
 *nearestClass = minClass; *nearestProt = minProt;
}


static void dropProtypesFile()
{
 FILE *pf = NULL;
 int i, j, p, k, class, row, nearestClass, nearestProt, errors = 0;
 float dist, minDist;
 bool protFile = TRUE, lvq_format = TRUE;
 FeatVector Sample = NULL;

 if( interact )
 {
   printf("\n Write all prototypes to a file (y/n)? y\b"); gets( buf );
   protFile = buf[0] != 'n' && buf[0] != 'N';
 }
 if( ! protFile ) return;

 if( interact )
 {
   printf(" Write file in LVQ format (y/n)? y\b"); gets( buf );
   lvq_format = buf[0] != 'n' && buf[0] != 'N';
   printf("Save prototypes to file: %s", DATA_DIR ); gets( buf );
   if( buf[0] == '\0' ) { printf("Nothing saved...\n"); return; }
   strcpy( pfName, DATA_DIR );
   strcat( pfName, buf );
 }
 else
 {
   strcpy( pfName, DATA_DIR );
   strcat( pfName, U->name );
   strncat( pfName, ".sym", 4 );
 }
 if( ( pf = fopen( pfName, f_open_text_w  )) == NULL )
 {
   fprintf( stderr, "Could not open %s for writing !!!\n", pfName );
   exit( 1 );
 }
 if( ! lvq_format )
 {
   fprintf( pf, "#\n# Prototype file for universe: %s\n#\n", U->name );
   fprintf( pf, "# Number of classes:\n%d\n", U->nrClass );
   fprintf( pf, "# Dimension of continuous feat. vector:\n");
 }
 fprintf( pf, "%d\n", U->nrSelFeat );
 if( ! lvq_format )
 {
   fprintf( pf, "# Number of prototypes for all classes:\n" );
   for( i = 0; i < U->nrClass; i++ )
     fprintf( pf, "%d\n", PTC[i].numProtype );
 }

 for( i = 0; i < U->nrClass; i++ )
 {
   class = i;
   if( ! lvq_format )
     fprintf( pf, "#\n# %s\n#\n", U->C[class].name );
   for( p = 0; p < PTC[i].numProtype; p++ )
   {
     for( k = 0; k < U->nrSelFeat; k++ )
       fprintf( pf, "%7.5f ", PTC[i].PT[p].value[k] );
     if( ! lvq_format )
     {
       fprintf( pf, "  %d-%d", class, p );
       if( PTC[i].PT[p].outlier )
         fprintf( pf, "    # outlier" );
     }
     else
       fprintf( pf, "  %s", U->C[class].name );
     fprintf( pf, "\n" );
   }
 }
 if( ! lvq_format )
 {
   /* now discretize all samples of all classes to the symbolic prototypes */
   fprintf( pf, "#\n# The discretized samples\n#\n" );
   fprintf( pf, "# ClassNr-PrototypeNr  ClassName\n#\n" );
   row = 0;
   for( i = 0; i < U->nrClass; i++ )
   {
     class = i;
     for( j = 0; j < U->C[class].numSampl; j++ )
     {
       Sample = &(Samples[U->nrSelFeat*row]);
       discretize( Sample, symbolicFeature, &nearestClass, &nearestProt );
       if( class != nearestClass )
         errors++;
       fprintf( pf, "%s %s\n", symbolicFeature, U->C[class].name );
       row++;
     }
   }
   fprintf( pf, "#\n# There were %d of %d = %6.3f%% samples misclassified\n#\n",
	errors, row, 100.0*(float)errors/(float)row );
 }
 fclose( pf );
}


static void init_prototypes()
{
 int i, j, k, row, random_offset = 0;

 nrFeat = U->nrSelFeat;
 init_PTC();
 row = 0;
 /* init: for every class pick one aleatory sample as first prototype */
 for( i = 0; i < U->nrClass; i++ )
 {
   PTC[i].PT = (ProType*) malloc( sizeof(struct ProType_) );
   PTC[i].numProtype = 1;
   init_ProType( &(PTC[i].PT[0]) );
   PTC[i].PT[0].value = (FeatVector)malloc(nrFeat * sizeof(FeatVector*));

   if( first_prototype_random )
   {
     get_random( U->C[i].numSampl, &random_offset );	/**/
     /* printf("offset for class %d = %d", i, random_offset ); DBG; /**/
     /* check offset */
     if( random_offset < 0 || random_offset >= U->C[i].numSampl )
     {
       fprintf(stderr,"Warning: offset is %d\n", random_offset);
       fprintf(stderr,"Try changing the 'RANGE' in 'util.c'\n");
       fprintf(stderr,"init_prototypes> Setting to 0\n");
       random_offset = 0;
     }
     copy_FV( &(Samples[nrFeat*(row+random_offset)]),
		 PTC[i].PT[0].value, nrFeat );
   }
   else
   {
     allPT.nrFriends = U->C[i].numSampl;
     allPT.friends = (int*)malloc( allPT.nrFriends * sizeof(int) );
     CHKPTR( allPT.friends );
     for( j = 0; j < U->C[i].numSampl; j++ )
       allPT.friends[j] = row + j;

     switch( update_method )
     {
       case UPDATE_MEAN :
         for( k = 0; k < nrFeat; k++ )
           PTC[i].PT[0].value[k] = U->C[i].mean[ U->FSV[k].rank ]; break;
       case UPDATE_MARGINAL_MEDIAN :
         calc_marginalMedian( PTC[i].PT[0].value, &allPT );
         break;
       case UPDATE_VECTOR_MEDIAN :
         calc_VectorMedian( PTC[i].PT[0].value, &allPT );
         break;
       default : fprintf(stderr,"Trouble with update method - exit...\n");
		 exit(1);
     }
     FREE( allPT.friends );
   }
   row += U->C[i].numSampl;
 }
}


static void create_new_prototype( class, row )
int  class, row;
{
 int k, p, pInd; 
 ProType *PT_buf = NULL;

 PT_buf = (ProType*)
       malloc( (1+PTC[class].numProtype) * sizeof(struct ProType_) ); 
 for( p = 0; p <= PTC[class].numProtype; p++ )
 {
   init_ProType( &(PT_buf[p]) );
   PT_buf[p].value = (FeatVector) malloc(nrFeat * sizeof(FeatVector*));
 }
 for( p = 0; p < PTC[class].numProtype; p++ )
   copy_PT( &(PTC[class].PT[p]), &(PT_buf[p]), nrFeat );

 pInd = PTC[class].numProtype;

 copy_FV( &(Samples[nrFeat*row]), PT_buf[pInd].value, nrFeat );
 PT_buf[pInd].outlier = TRUE;
 PT_buf[pInd].nrFriends = 0;
 PT_buf[pInd].friends = NULL;

 /* copy buffer back and update all classes 0 ... class */
 for( p = 0; p < PTC[class].numProtype; p++ )
 {
   FREE( PTC[class].PT[p].value );
 }
 FREE( PTC[class].PT );
 /* increase the number of prototypes for class 'class' */
 PTC[class].numProtype++; 
 PTC[class].PT = PT_buf;
}


static void cluster_qstar()
{
 bool changes = TRUE, mis_classed, dummy, verbose = FALSE, purge = TRUE;
 int i, j, k, c, p, row, minClass, class, minProType, a, b, w = 0, runs = 1;
 float minDist, dist;

 if( interact )
 {
   printf("CLUSTER:\n Verbose (y/n)? n\b"); gets( buf );
   verbose = buf[0] == 'y' || buf[0] == 'Y';
 }
 gen_selected_samples( verbose );
 init_prototypes();
 if( verbose )
 {
   show_PTC( FALSE );
   printf("*** Ignore ouliers because of initialization ***\n");
 }

 /* main loop of cluster */
 /* while the prototypes do change */
 do
 {
   if( ! verbose )
   {
     printf("Learning prototypes...  %c\r", wheel[(w++) % strlen(wheel)] );
     fflush( stdout );
   }
   i = 0; mis_classed = FALSE;
   row = 0;
   while( (i < U->nrClass) && ! mis_classed )
   {
     class = i;
     for( j = 0; j < U->C[class].numSampl; j++ )
     {
       minDist = INFINITY; minClass = UNDEFINED;
       for( c = 0; c < U->nrClass; c++ )
       {
         for( p = 0; p < PTC[c].numProtype; p++ )
         {
           dist = Euclidian_Distance( PTC[c].PT[p].value,
                                      &(Samples[nrFeat*row]), nrFeat );
           if( dist <= minDist )
           {
             if( dist == minDist && c != class && minClass == class )
             {
               ; /* do nothing: keep the minimum the own class */
             }
             else /* dist < minDist */
             {
               minDist = dist;
               minClass = c;
               minProType = p;
             }
           }
         }
       } 
       /* look if the sample was correctly classified */
       if( minClass == class )
       {
         /* join the correctly classified pattern to the friends */
         join_friend( row, &(PTC[minClass].PT[minProType]) );
       }
       else
       {
       /* printf("mis_classed class=%d minClass=%d  row=%d! -> New prototype\n",
                     class, minClass, row); DBG; /**/
         mis_classed = TRUE;
         create_new_prototype( class, row );
         for( a = 0; a <= class; a++ )
         {
           dummy = update_Class( a, nrFeat );
         }
       }
       row++;
     }/* for every sample */
     i++; /* for every class */
   }/* while */
   /* if no misclassifications occured update prototypes for all classes */
   if( ! mis_classed )
     for( i = 0; i < U->nrClass; i++ )
       changes = update_Class( i, nrFeat ) && changes;
   if( verbose )
   {
     printf("\n\t\t +++++ END OF RUN  %d  +++++", runs );
     show_PTC( TRUE ); /**/
   }
   if( changes )
     runs++;
 } 
 while( changes );

 if( verbose )
 {
   printf("\n --- F I N A L  R E S U L T  after %d runs: ---\n", runs );
   show_PTC( FALSE );
 }
 else
   printf("\n\n --- Sucessfully clustered in %d runs ---\n", runs );

 /* Purge all prototypes which were generated by only one sample
  *  These prototypes are outliers
 */
 if( interact )
 {
   printf("CLUSTER:\n Purge all single sample prototypes (y/n)? y\b");
   gets( buf );
   purge = buf[0] != 'n' && buf[0] != 'N';
 }
 if( purge )
   purge_outliers();
 if( verbose )
 {
   printf("\n --- R E S U L T  A F T E R  P U R G E: ---");
   show_PTC( FALSE );
 }
}


void learnQ()
{

 if( U->nrSelFeat == 0 )
   { printf("Select features first..."); gets( buf ); return; }
 init_qstar();
 cluster_qstar();
 dropProtypesFile();
 FREE( Samples );
}