/*
   Chromosome.java

   Definition of the class Chromosome

   (P)2002  Dana Cristofor

*/

/*

GAClust - Clustering categorical databases using genetic algorithms
Copyright (C) 2002  Dana Cristofor


This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or (at
your option) any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
USA

GAClust was written by Dana Cristofor (dana@cs.umb.edu).

*/

import java.util.*;

/**
 * Chromosome
 *
 * @version 	1.0
 * @author	Dana Cristofor
 */
public class Chromosome extends Partition
{
  protected int crossoverType;
  protected int mutationType;
  protected int distributionType;

  // crossover method types
  // random crossover
  static public final int CROSS_RAND              = 11;
  // exchanging two random classes
  static public final int CROSS_X_2RAND_CLASS     = 12;
  // exchanging best classes
  static public final int CROSS_AM_X_BEST_CLASS   = 13;
  // exchanging best worst classes
  static public final int CROSS_AM_X_BEST_WORST   = 14;
  // exchanging two random classes
  static public final int CROSS_AM_X_2RAND_CLASS  = 15;

  // mutation method types
  static public final int MUT_RAND      = 21;  // random mutation
  static public final int MUT_MOVE_ELEM = 22;  // move elements between classes
  static public final int MUT_SWAP_ELEM = 23;  // swap elements between classes

  // types of methods for distributing elements to classes
  static public final int DISTRIB_NONE    = 31;
  static public final int DISTRIB_RAND    = 32;
  static public final int DISTRIB_TO_EVEN = 33;  

  Chromosome(int size, int nc, int classFitnessType, 
	     int crossoverType, int mutationType, int distributionType)
  {
    super(size, nc, classFitnessType);
    this.crossoverType = crossoverType;
    this.mutationType = mutationType;
    this.distributionType = distributionType;
  }

  /** @return the crossover type */
  public int getCrossoverType()
  {
    return crossoverType;
  }

  /** @return the mutation type */
  public int getMutationType()
  {
    return mutationType;
  }

  /** @return the distribution type */
  public int getDistributionType()
  {
    return distributionType;
  }

  /** computes the fitness of the chromosome and the fitness of the
   * classes for chromosomes in the collection <code>c1</code>
   * relative to the partitions in the collection <code>c2</code>;
   * <code>N1</code> is the size of the collection <code>c1</code>;
   * <code>N2</code> represents the number of partitions in
   * <code>c2</code> **/
  static public void computeFitnessValues(Chromosome[] c1, int N1,
					  Partition[] c2, int N2, 
					  int entropyMeasure, 
					  int fitnessMeasure,
					  double[] weightDBTarget,
					  double[] weightTargetDB,
					  double[] weight)
  {
    for (int i = 0; i < N1; i++)
      c1[i].computeFitness(c2, N2, 
			   entropyMeasure, fitnessMeasure, 
			   weightDBTarget, weightTargetDB, weight);
  }

  /** computes fitness value of chromosomes in collection
   * <code>c1</code> based on the fitness value of chromosome
   * <code>chrom1</code> and on the intersection between
   * <code>chrom1</code> and the collection of <code>N</code>
   * partitions in <code>db</code> */
  static public void computeFitnessValues(Chromosome chrom1, 
					  Hashtable[] intersectMap,
					  Partition[] db, int N, 
					  Chromosome[] c1, int N1,
					  int entropyMeasure, 
					  int fitnessMeasure,
					  double[] weightDBTarget,
					  double[] weightTargetDB,
					  double[] weight)
  {
    for (int i = 0; i < N1; i++)
      {
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.println("working on chromosome " + i);
	    System.out.println("best chrom fitness " + chrom1.getFitness());
	  }

	computeFitnessValue(chrom1, intersectMap,
			    db, N, c1[i],
			    entropyMeasure, fitnessMeasure, 
			    weightDBTarget, weightTargetDB, weight);
	
	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println("chromosome " + i + " fitness: " 
			     + c1[i].getFitness());
      }
  }


  /** compute fitness value of chromosome <code>chrom2</code> based on
   * the fitness value of chromosome <code>chrom1</code> and on the
   * intersection between <code>chrom1</code> and the collection of
   * <code>N</code> partitions in <code>db</code> */
  static public void computeFitnessValue(Chromosome chrom1, 
					 Hashtable[] intersectMap,
					 Partition[] db, int N, 
					 Chromosome chrom2,
					 int entropyMeasure, 
					 int fitnessMeasure,
					 double[] weightDBTarget,
					 double[] weightTargetDB,
					 double[] weight)
  {
    if (Global.DEBUG == 1)
      if (chrom1.getSize() != chrom2.getSize())
	{
	  System.err.println("ERROR! Chromosome.computeFitnessValue():"
			     + "chromosomes have different size.");
	  System.exit(1);
	}

    int SIZE = chrom1.getSize();
    // <int, <int, int>>
    Hashtable[] localIntersectMap = new Hashtable[N];
    for (int i = 0; i < N; i++)
      {
	localIntersectMap[i] = new Hashtable();
	for (Enumeration classes = intersectMap[i].keys();
	     classes.hasMoreElements();)
	  {
	    Integer currClass = (Integer)classes.nextElement();
	    Hashtable map = (Hashtable)intersectMap[i].get(currClass);
	    localIntersectMap[i].put(currClass, new Hashtable(map));
	  }
      }

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println("chrom1 intersections with db");
	for (int i = 0; i < N; i++)
	  {
	    System.out.println("attr " + i);
	    for (Enumeration classes1 = localIntersectMap[i].keys();
		 classes1.hasMoreElements();)
	      {
		Integer currClass1 = (Integer)classes1.nextElement();
		System.out.print(currClass1 + " | ");
		Hashtable value1 = 
		  (Hashtable)localIntersectMap[i].get(currClass1);
		for (Enumeration classes2 = value1.keys(); 
		     classes2.hasMoreElements(); )
		  {
		    Integer currClass2 = (Integer)classes2.nextElement();
		    System.out.print(currClass2 + "(" 
				       + (Integer)value1.get(currClass2) 
				       + ") ");
		  }
		System.out.println();
	      }
	  }
      }
  
    int numModif = 0;

    // loop on all partitions from collection c
    for (int i = 0; i < N; i++)
      // loop on all rowids
      for (int rowid = 0; rowid < SIZE; rowid++)
	// if we have different values on position rowid
	if (chrom1.get(rowid) != chrom2.get(rowid))
	  {
	    numModif++;
	    // for class Cs1 = chrom1[rowid] modify
	    // class Bt = db[i] 
	    // if Cs1 x Bt is 1 delete Bt from the map
	    Integer Cs1 = new Integer(chrom1.get(rowid));
	    Integer Bt = new Integer(db[i].get(rowid));
	    Hashtable map = (Hashtable)localIntersectMap[i].get(Cs1);

	    int count = ((Integer)map.get(Bt)).intValue();
	    if (count == 1)
	      {
		map.remove(Bt);
		// if the map associated with Cs1 becomes empty, remove Cs1
		// from localIntersectMap[i]
		if (map.size() == 0)
		  localIntersectMap[i].remove(Cs1);
	      }
	    else
	      // decrementing Cs1 x Bt
	      map.put(Bt, new Integer(count - 1));
	    
	    // for class Cs2 = chrom2[rowid] modify
	    // class Bt = db[j] by incrementing Cs2 x Bt
	    Integer Cs2 = new Integer(chrom2.get(rowid));
	   
	    if (localIntersectMap[i].containsKey(Cs2))
	      {
		// if localIntersectMap[i] contains the key Cs2 get
		// the count of Bt and increment it
		map = (Hashtable)localIntersectMap[i].get(Cs2); 
		count = 0;
		if (map.containsKey(Bt) == true)
		  count = ((Integer)map.get(Bt)).intValue();
		map.put(Bt, new Integer(count + 1));
	      }
	    else
	      {
		// create a new map with <Bt, 1> and add the map <Cs2,
		// <Bt, 1>> to localIntersectMap[i]
		map = new Hashtable();
		map.put(Bt, new Integer(1));
		localIntersectMap[i].put(Cs2, map);
	      }
	  }
    
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println("final intersections");
	for (int i = 0; i < N; i++)
	  {
	    System.out.println("attr " + i);
	    for (Enumeration classes1 = localIntersectMap[i].keys();
		 classes1.hasMoreElements();)
	      {
		Integer currClass1 = (Integer)classes1.nextElement();
		System.out.print(currClass1 + " | ");
		Hashtable value1 = 
		  (Hashtable)localIntersectMap[i].get(currClass1);
		for (Enumeration classes2 = value1.keys(); 
		     classes2.hasMoreElements(); )
		  {
		    Integer currClass2 = (Integer)classes2.nextElement();
		    System.out.println(currClass2 + "(" 
				       + (Integer)value1.get(currClass2) 
				       + ") ");
		  }
		System.out.println();
	      }
	  }
    
	if (numModif > 0)
	  System.out.println("intersectMap has been modified " + numModif);
      }
  
    if (numModif > 0)
      // now in localIntersectMap we have the intersections between
      // chrom2 and the partitions in db
      // based on these intersections compute the fitness of chrom2
      chrom2.computeFitness(localIntersectMap,
			    db, N, 
			    entropyMeasure, fitnessMeasure, 
			    weightDBTarget, weightTargetDB, weight);
    else
      // chrom1 is identical with chrom2
      chrom2.set(chrom1);
  }

  ///////////////// CROSSOVER METHODS //////////////////////

  /** performs the crossover between this chromosome and the one
   * received as argument according to crossoverType */
  public void crossover(Chromosome c, Random rand)
  {
    // if the two partitions are equal return immediately
    if (isEqual(c))
      return;

    if (Global.VERBOSE == 1)
      System.out.print("C ");
    
    switch(crossoverType)
      {
      case CROSS_RAND:
	crossoverR(c, rand);
	break;
  
      case CROSS_X_2RAND_CLASS:
	crossoverXC(c, rand);
	break;
	
      case CROSS_AM_X_2RAND_CLASS:
      case CROSS_AM_X_BEST_CLASS:
      case CROSS_AM_X_BEST_WORST:
	crossoverAM(c, rand);
	break;
	
      default:
	System.err.println("ERROR! Chromosome.crossover():"
			   + "invalid crossover type " + crossoverType);
	System.exit(1);
      }
  }

  /** crosses over this chromosome with the chromosome received as
   * argument by randomly selecting a single cut point and exchanging
   * the last portion starting from the cut point between the two
   * chromosomes */
  private void crossoverR(Chromosome  c, Random rand)
  {
    if (Global.ULTRA_VERBOSE == 1)
      System.out.print("Crossover RANDOM ");
  
    // randomly select a position to cut the chromosomes
    // we will switch positions k to size-1
    // between the two parents
    // k can be a number between 1 and size-1
    int k = 1 + rand.nextInt(size-1);
    // save tail of v in a temp array
    int[] temp = new int[size - k];

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println(" first chromosome: ");
	for (int j = 0; j < size; j++)
	  System.out.print(v[j] + " ");
	System.out.println();

	System.out.println( " second chromosome: ");
	for (int j = 0; j < c.size; j++)
	  System.out.print(c.v[j] + " ");
	System.out.println();
  
	System.out.println("crossed over at position " + k);      
      }
    
    for (int i = k; i < size; i++)
      temp[i-k] = v[i];

    // copy tail of c.v instead
    for (int i = k; i < size; i++)
      set(i, c.v[i]);

    // copy temp over tail of c
    for (int i = k; i < size; i++)
      c.set(i, temp[i-k]);

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println(" first chromosome:");
	for (int j = 0; j < size; j++)
	  System.out.print(v[j] + " ");
	System.out.println();

	System.out.println(" second chromosome:");
	for (int j = 0; j < c.size; j++)
	  System.out.print(c.v[j] + " ");
	System.out.println();
      }
  }

  /** crosses over this chromosome with the one received as argument;
   * selects a random class and exchanges this class between the two
   * parent chromosomes */
  private void crossoverXC(Chromosome c, Random rand)
  {
    if (Global.ULTRA_VERBOSE == 1)
      System.out.print("Crossover XC ");

    if (getNoClasses() == 1 || c.getNoClasses() == 1)
      return;
  
    // randomly select a class to exchange between the chromosomes
    // k should be a number between 1 and the number of classes
    int noClasses = getNoClasses();
    int k = 1 + rand.nextInt(noClasses);

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println(" first chromosome:");
	for (int j = 0; j < size; j++)
	  System.out.print(v[j] + " ");
	System.out.println();

	System.out.println(" second chromosome:");
	for (int j = 0; j < c.size; j++)
	  System.out.print(c.v[j] + " ");
	System.out.println();
  
	System.out.println("exchanging the class " + k);      
      }

    // save partition c in a temp array
    int[] temp = new int[c.size];
    for (int j = 0; j < c.size; j++)
      temp[j] = c.v[j];

    // copy the class k from this chromosome into c
    // the old elements from c that belong to class k
    // are moved to other classes
    for (int j = 0; j < size; j++)
      {
	if (v[j] == k)
	  c.set(j, k);
	else if (c.v[j] == k)
	  {
	    // move old elements to other distinct classes
	    int new_k = 1 + rand.nextInt(noClasses);
	    while (new_k == k)
	      new_k = 1 + rand.nextInt(noClasses);
	    
	    c.set(j, new_k); 
	  }    
      }
  
    // copy the class k from temp into this chromosome
    // the old elements from v that belonged to class k
    // are moved to other classes
    for (int j = 0; j < size; j++)
      {
	if (temp[j] == k)
	  set(j, k);
	else if (v[j] == k)
	  {
	    // move old elements to other classes
	    int new_k = 1 + rand.nextInt(noClasses);
	    while (new_k == k)
	      new_k = 1 + rand.nextInt(noClasses);
	    
	    set(j, new_k); 
	  }
      }
  
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println(" first chromosome:");
	for (int j = 0; j < size; j++)
	  System.out.print(v[j] + " ");
	System.out.println();
  
	System.out.println(" second chromosome:");
	for (int j = 0; j < c.size; j++)
	  System.out.print(c.v[j] + " ");
	System.out.println();
      }
  }

  /** crosses over this chromosome with the one received as argument;
   * implementation with array of maps */
  private void crossoverAM(Chromosome c, Random rand)
  {
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.print(" Crossover AM ");
	System.out.println("first chromosome before crossover");
	printAM();
	System.out.println("second chromosome before crossover");
	c.printAM();
      }
    
    // create array of maps for first chromosome
    int noClasses1 = getMaxNoClasses();
    Hashtable[] am1 = new Hashtable[noClasses1];
    for (int i = 0; i < noClasses1; i++)
      am1[i] = new Hashtable();
    getAM(am1);

    // create array of maps for second chromosome
    int noClasses2 = c.getMaxNoClasses();
    Hashtable[] am2 = new Hashtable[noClasses2];
    for (int i = 0; i < noClasses2; i++)
      am2[i] = new Hashtable();
    c.getAM(am2);

    if (Global.DEBUG == 1)
      if (noClasses1 != getMaxNoClasses() 
	  || noClasses2 != c.getMaxNoClasses())
	{
	  System.out.println("ERROR! Chromosome.crossoverAM():"
			     + " invalid number of classes");
	  System.exit(1);
	}
    
    Vector v = selectCrossoverClasses(c, rand);
    // class with best fitness
    int from1AMIndex = ((Integer)v.elementAt(0)).intValue();
    // class with worst fitness
    int to2AMIndex = ((Integer)v.elementAt(1)).intValue();
    // class with best fitness
    int from2AMIndex = ((Integer)v.elementAt(2)).intValue();
    // class with worst fitness
    int to1AMIndex  = ((Integer)v.elementAt(3)).intValue();

    // save class to2AMIndex from am2 into a toReplace map
    Hashtable toReplace = new Hashtable(am2[to2AMIndex]);
    // save the original from2AMIndex from am2
    Hashtable from2bak = new Hashtable(am2[from2AMIndex]); 
    
    // put class from1AMIndex in am2 instead of class to2AMIndex
    am2[to2AMIndex] = new Hashtable(am1[from1AMIndex]);
    
    // remove the elements of class from1AMIndex that appear in other
    // classes of am2
    // remove the elements in toReplace that are also in from1AMIndex
    // since they should not be distributed to other classes
    cleanUpAndDistributeAM(am2, toReplace, to2AMIndex, rand, c);
    //    c.setAM(am2, noClasses2);
    c.setAM(am2);

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.print("AM2 map sizes = ");
	for (int i = 0; i < am2.length; i++)
	  System.out.print(am2[i].size() + " ");
	System.out.println();
      }
    /////////////// Second part //////////////
    
    // save class to1AMIndex from am1 in a toReplace map
    toReplace = new Hashtable(am1[to1AMIndex]);
    
    // put class from2bak (the original from2AMIndex) in am1 instead of
    // class to1AMIndex
    am1[to1AMIndex] = new Hashtable(from2bak);
    
    // remove the elements of class from2AMIndex that appear in other
    // classes of am2
    // remove the elements in toReplace that are also in to1AMIndex
    // since they should not be distributed to other classes
    cleanUpAndDistributeAM(am1, toReplace, to1AMIndex, rand, this);
    //    setAM(am1, noClasses1);
    setAM(am1);
    
    if (Global.ULTRA_VERBOSE == 1)
      {    
	System.out.print("AM1 map sizes = ");
	for (int i = 0; i < am1.length; i++)
	  System.out.print(am1[i].size() + " ");
	System.out.println();
      }

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println(" first chromosome after crossover");
	printAM();
	
	System.out.println(" second chromosome after crossover");
	c.printAM();
      }
  }
  
  //////////////////// MISCELLANEOUS METHODS //////////////////////

  private void cleanUpAndDistributeAM(Hashtable[] am, Hashtable temp, int k,
				      Random rand, Partition p)
  {
    // indices of classes that become empty
    Hashtable emptyClasses = new Hashtable();

    cleanUpAM(am, temp, k, emptyClasses, p);

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println("there are " + temp.size() 
			   + " elements to distribute");
	System.out.println("there are " + emptyClasses.size() 
			   + " empty classes");
      }
    
    int nElemDistribute = temp.size();
    int nEmptyClasses = emptyClasses.size();
  
    if (nEmptyClasses == 0)
      {
	// we have no empty classes
	  
	// if temp is empty nothing is done 
	// otherwise we distribute elem of temp 
	// according to distribution_type
	distribute(temp, am, rand); 
      }
    else // we have empty classes
      {
	if (nElemDistribute <= nEmptyClasses)
	  {
	    // we have less elements to distribute
	    // than empty classes
	    // insert one element in each empty class
	    distributeToEmptyClasses(temp, am, emptyClasses, 1, rand);
	  }
	else
	  {
	    // we have more elements to distribute than empty classes
	    int quota = nElemDistribute/nEmptyClasses;
	    
	    // distribute nElemDistribute/nEmptyClasses 
	    // to each empty class
	    distributeToEmptyClasses(temp, am, emptyClasses, quota, rand);
	  }
      }
  }
  
  /** cleans up the classes of <code>am</code> such that the elements
   * of class <code>am[k]</code> do not appear in other classes of
   * <code>am</code> (different than <code>k</code>) also removes the
   * elements of <code>temp</code> that are in <code>am[k]</code>
   * since they should not be distributed to other classes;
   * <code>emptyClasses</code> gets filled with the ids of the classes
   * that got empty */
  private void cleanUpAM(Hashtable[] am, Hashtable temp, int k, 
			 Hashtable emptyClasses, Partition p)
  {
    int noClasses = p.getNoClasses();
    for (Enumeration classes = am[k].keys(); classes.hasMoreElements();)
      {
	Integer currClass = (Integer)classes.nextElement();
	// if currClass is in map temp
	// delete this value from the map
	if (temp.containsKey(currClass) == true)
	  temp.remove(currClass);

	for (int i = 0; i < noClasses; i++)	
	  if (i != k)
	    {
	      // if currClass is in map am[i]
	      if (am[i].containsKey(currClass) == true)
		{
		  // delete this value from the map
		  am[i].remove(currClass);
		  
		  // if this class becomes empty remember its index
		  if (am[i].size() == 0)
		    emptyClasses.put(new Integer(i), new Integer(i));

		  break;
		}
	    }
      }
    
    // from noClasses to getMaxNoClasses() - 1 we have empty classes
    for (int i = noClasses; i < p.getMaxNoClasses(); i++)
      {
	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println("Found " + i + " as empty class");
	emptyClasses.put(new Integer(i), new Integer(i));
      }
  }

  /** selects the best class according to the class fitness and
   * returns its index in <code>am</code> representation */
  private int selectBestClass()
  {
    int amIndex = -1;
    if (Global.ULTRA_VERBOSE == 1)
      System.out.println("select best class ");

    int noClasses = getNoClasses();
    Hashtable[] am = new Hashtable[noClasses];
    for (int i = 0; i < noClasses; i++)
      am[i] = new Hashtable();
    getAM(am);

    Enumeration classes = classFitness.keys();
    Integer currClass = (Integer)classes.nextElement();
    int classNo = currClass.intValue();
    double bestFit = ((Double)classFitness.get(currClass)).doubleValue();
    for (Enumeration classes1 = classFitness.keys();
	 classes1.hasMoreElements();)
      {
	Integer currClass1 = (Integer)classes1.nextElement();
	double value = ((Double)classFitness.get(currClass1)).doubleValue();
	if (value < bestFit)
	  {
	    classNo = currClass1.intValue();
	    bestFit = value;
	  }
      }


    // classNo is the class integer that has the smallest fitness
    // see to what class it corresponds in am
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.println("AM contents start " + noClasses);
	for (int k = 0; k < noClasses; k++)
	  {
	    System.out.print("am[" + k + "]:");
	    printMap(am[k]);
	  }
	System.out.println("AM contents end");
      }

    int k;
    for (k = 0; k < noClasses; k++)
      {
	Enumeration keys = am[k].keys();
	Integer key = (Integer)keys.nextElement();
	if (v[key.intValue()] == classNo)
	  {
	    amIndex = k;
	    break;
	  }
      }


    if (Global.DEBUG == 1)
      if (k == noClasses)
	{
	  // this should never happen
	  System.err.println("ERROR! Chromosome.selectBestClass():"
			     + "classNo corresponds to no class: " + classNo);
	  System.exit(1);
	}

    return amIndex;
  }

  /** selects the best and worst classes according to the class
   * fitness and returns a vector containing two Integer objects, the
   * first one is the best class index in am representation and the
   * second one is the worst class index in am representation */
  private Vector selectBestWorstClasses()
  {
    int bAMIndex = -1;
    int wAMIndex = -1;
    if (Global.ULTRA_VERBOSE == 1)
      System.out.println("select best worst class ");

    int noClasses = getNoClasses();
    Hashtable[] am = new Hashtable[noClasses];
    for (int i = 0; i < noClasses; i++)
      am[i] = new Hashtable();
    getAM(am);

    if (Global.DEBUG == 1)
      if (classFitness.size() == 0)
	{
	  System.err.println("ERROR! Chromosome.selectBestWorstClasses():"
			     + " classFitness is empty");
	  System.exit(1);
	}
    
    Enumeration classes = classFitness.keys();
    Integer currClass = (Integer)classes.nextElement();
    int bClassNo = currClass.intValue();
    double minFit = ((Double)classFitness.get(currClass)).doubleValue();
    int wClassNo = bClassNo;
    double maxFit = minFit;

    for (Enumeration classes1 = classFitness.keys();
	 classes1.hasMoreElements();)
      {
	Integer currClass1 = (Integer)classes1.nextElement();
	double value = ((Double)classFitness.get(currClass1)).doubleValue();
	if (value < minFit)
	  {
	    bClassNo = currClass1.intValue();
	    minFit = value;
	  }
	else if (value > maxFit)
	  {
	    wClassNo = currClass1.intValue();
	    maxFit = value;
	  }
      }
  
    if (Global.ULTRA_VERBOSE == 1)
      System.out.println("bClassNo " + bClassNo + " wClassNo " + wClassNo);

    // bClassNo is the class integer that has the smallest fitness
    // wClassNo is the class integer that has the largest fitness
    // see to what classes correspond in am
    int k;
    boolean foundBest = false;
    boolean foundWorst = false;
    for (k = 0; k < noClasses; k++)
      {
	Enumeration keys = am[k].keys();
	Integer key = (Integer)keys.nextElement();

	if (!foundBest && v[key.intValue()] == bClassNo)
	  {
	    bAMIndex = k;
	    foundBest = true;
	  }
	
	if (!foundWorst && v[key.intValue()] == wClassNo)
	  {
	    wAMIndex = k;
	    foundWorst = true;
	  }
	
	if (foundBest && foundWorst)
	  break;
      }
    
    if (Global.DEBUG == 1)  
      if (k == noClasses)
	{
	  // this should never happen
	  System.err.println("ERROR! selectBestWorstClasses(): invalid class"
			     + " number -> bClassNo =? " + bClassNo 
			     + " wClassNo =? " + wClassNo);
	  System.exit(1);
	}

    Vector v = new Vector(2);
    v.insertElementAt(new Integer(bAMIndex), 0);
    v.insertElementAt(new Integer(wAMIndex), 1);

    return v;
  }

  /** selects the classes to crossover between this chromosome and c
   * and returns a vector containing from1AMIndex, to2AMIndex,
   * from2AMIndex, and to1AMIndex*/
  private Vector selectCrossoverClasses(Chromosome c, Random rand)
  {
    int from1AMIndex = -1;
    int to2AMIndex = -1;
    int from2AMIndex = -1;
    int to1AMIndex = -1;

    if (Global.ULTRA_VERBOSE == 1)
      System.out.println("select crossover classes ...");

    switch(crossoverType)
      {
      case CROSS_AM_X_2RAND_CLASS:
	from1AMIndex = to1AMIndex = rand.nextInt(getNoClasses());
	from2AMIndex = to2AMIndex = rand.nextInt(c.getNoClasses());
	break;

      case CROSS_AM_X_BEST_CLASS:
	from1AMIndex = selectBestClass();
	to1AMIndex = from1AMIndex;
	from2AMIndex = c.selectBestClass();
	to2AMIndex = from2AMIndex;
	break;

      case CROSS_AM_X_BEST_WORST:
	Vector v = selectBestWorstClasses();
	from1AMIndex = ((Integer)v.elementAt(0)).intValue();
	to1AMIndex = ((Integer)v.elementAt(1)).intValue();
	v = c.selectBestWorstClasses();
	from2AMIndex = ((Integer)v.elementAt(0)).intValue();
	to2AMIndex = ((Integer)v.elementAt(1)).intValue();
	break;

      default:
	System.err.println("ERROR! Chromosome.selectCrossoverClasses():"
			   + " invalid crossoverType");
	System.exit(1);
      }
    
    if (Global.ULTRA_VERBOSE == 1)
      System.out.println("from1 " + from1AMIndex + " to1 " + to1AMIndex
			 + " from2 " + from2AMIndex + " to2 " + to2AMIndex);
  
    Vector ret = new Vector(4);
    ret.insertElementAt(new Integer(from1AMIndex), 0);
    ret.insertElementAt(new Integer(to2AMIndex), 1);
    ret.insertElementAt(new Integer(from2AMIndex), 2);
    ret.insertElementAt(new Integer(to1AMIndex), 3);
    return ret;
  }

  private void distribute(Hashtable temp, Hashtable[] am, Random rand)
  {
    switch (distributionType)
      {
      case DISTRIB_RAND:
	distributeRandomly(temp, am, rand);
	break;
	
      case DISTRIB_TO_EVEN:
	distributeToEven(temp, am, rand);
	break;
	
      case DISTRIB_NONE:
      default:
	System.err.println("ERROR! Chromosome.distribute(): invalid"
			   + " distributionType");
	System.exit(1);
      }
  }

  /** distributes the elements of the map <code>temp</code> to other
   * classes in <code>am</code>; classes are selected randomly*/
  private void distributeRandomly(Hashtable temp, Hashtable[] am, Random rand) 
  {
    if (Global.VERBOSE == 1)
      System.out.print("distributeRandomly ");

    int nElemDistribute = temp.size();
    if (nElemDistribute == 0)
      return; //no elements to distribute

    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.print("temp ");
	printMap(temp);
      }
  
    // distribute the elements in temp to randomly selected classes 
    for (Enumeration classes = temp.keys(); classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	// select at random a class to distribute
	// the element from temp
	// pos should be a number between 0 and getMaxNoClasses()-1
	// here in am we have maximum number of classes
	int pos = rand.nextInt(getMaxNoClasses());
	
	// insert the element from temp
	am[pos].put(currClass, currClass); 
	
	if (Global.ULTRA_VERBOSE == 1)
	  {	
	    System.out.println("distribute " + currClass + " to am[" 
			       + pos + "] ");
	    printMap(am[pos]);
	  }
      }
  }

  /** selects <code>n</code> classes from <code>am</code>, based on
   * their sizes (smaller have greater probability of being picked
   * up); the selection is placed in the array
   * <code>sampleClasses</code> */
  private void selectSmallClassesProb(Hashtable[] am, int n,
				      int[] sampleClasses, Random rand)
  {
    double overallProb = 0.0;
    double[] prob = new double[getMaxNoClasses()];

    // initial prob are the classes sizes
    for (int i = 0; i < getMaxNoClasses(); i++)
      {
	if (am[i].size() == 0)
	  {
	    System.err.println("ERROR! Chromosome.selectSmallClassesProb():"
			       + " empty class found");
	    System.exit(1);
	  }

	// am[i] with smallest size will have the greatest probability
	prob[i] = ((double)size) / ((double)am[i].size());
	overallProb += prob[i];
      }

    // normalize the probabilities
    for (int i = 0; i < getMaxNoClasses(); i++)
      prob[i] /= overallProb;
    
    // cumulate probabilities
    for (int i = 1; i < getMaxNoClasses() - 1; i++)
      prob[i] += prob[i - 1];
    prob[getMaxNoClasses() - 1] = 1.0;
    
    if (Global.ULTRA_VERBOSE == 1)
      {
	for (int i = 0; i < getMaxNoClasses(); i++)
	  System.out.print(prob[i] + " ");
	System.out.println();
      }

    SelectionMethods.selectProb(getMaxNoClasses(), prob,
				 sampleClasses, n, rand);
  
    if (Global.ULTRA_VERBOSE == 1)
      for (int j = 0; j < n; j++)
	{
	  System.out.println("class " + sampleClasses[j] + " having size "
			     + am[sampleClasses[j]].size());
	}
  }

  /** distributes the elements of the map <code>temp</code> to other
   * classes in <code>am</code>; classes with smaller sizes having a
   * greater chance to receive the new elements */
  private void distributeToEven(Hashtable temp, Hashtable[] am,
				Random rand)
  {
    if (Global.VERBOSE == 1)
      System.out.print("distributeToEven ");

    int nElemDistribute = temp.size();
    if (nElemDistribute == 0)
      return; // no elements to distribute
  
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.print("temp ");
	printMap(temp);
      }
  
    int[] sampleClasses = new int[nElemDistribute];
    // select probabilistic nElemDistribute classes
    selectSmallClassesProb(am, nElemDistribute, sampleClasses, rand);

    // distribute the elements in temp to these classes
    int t = 0;
    for (Enumeration classes = temp.keys(); classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	// insert the element from temp
	am[sampleClasses[t]].put(currClass, currClass); 
	      
	if (Global.ULTRA_VERBOSE == 1)
	  {	
	    System.out.print("distribute " + currClass
			     + " to am[" + sampleClasses[t] + "] ");
	    printMap(am[sampleClasses[t]]);
	  }
      }
  }

  /** distributes the elements of <code>temp</code> into the
   * <code>emptyClasses</code> of <code>am</code>; puts
   * <code>quota</code> elements from <code>temp</code> into each
   * empty class; remaining elements are distributed according to
   * distributionType */
  private void distributeToEmptyClasses(Hashtable temp,
					Hashtable[] am, 
					Hashtable emptyClasses, 
					int quota,
					Random rand)
  {
    if (Global.VERBOSE == 1)
      System.out.print("distributeToEmptyClasses ");

    Enumeration classesTemp = temp.keys();
    Enumeration classesEmpty = emptyClasses.keys();

    Integer currClassEmpty = null;
    Integer currClassTemp = null;

    int t = -1; // number of elements inserted in the current empty
		// class

    while (classesTemp.hasMoreElements())
      {
	if (classesEmpty.hasMoreElements() == false)
	  break;
	
	currClassTemp = (Integer)classesTemp.nextElement();

	// if we already inserted the quota
	// of elements into this class
	if (t == -1 || ++t == quota)
	  {
	    t = 0;
	    // advance to next class
	    currClassEmpty = (Integer)classesEmpty.nextElement();
	  }
	
	// insert the element from temp
	// into an empty class
	am[currClassEmpty.intValue()].put(currClassTemp, currClassTemp); 
	
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("distributing " + currClassTemp + " to am["
			     + currClassEmpty + "] ");
	    printMap(am[currClassEmpty.intValue()]);
	  }
      }

    // if we still have empty classes
    while (classesEmpty.hasMoreElements())
      {
	currClassEmpty = (Integer)classesEmpty.nextElement();

	// pick at random a position from where
	// to start the search for the first class
	// having size at least 2
	// to take one element from it
	// pos is between 0 and getMaxNoClasses()-1
	int pos = rand.nextInt(getMaxNoClasses());
	
	for (; am[pos].size() < 2; )
	  pos = (pos + 1 >= getMaxNoClasses() ? 0 : pos + 1);
	
	// we take a random element
	// between 0 and am[pos].size() - 1 
	int e = rand.nextInt(am[pos].size());
	Enumeration keys = am[pos].keys();
	// position class3 on the right element on class
	// am[pos]
	Integer class3 = null;
	while(e-- >= 0)
	  class3 = (Integer)keys.nextElement();
	
	// add element to am[itr2->first]
	am[currClassEmpty.intValue()].put(class3, class3);
	// erase element from am[pos]
	am[pos].remove(class3);
	
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("transfering " + class3 + " from class " + pos
			     + " to am[" + currClassEmpty + "] ");
	    printMap(am[currClassEmpty.intValue()]);
	  }
      }
    
    // if we still have elements to distribute
    Hashtable rest = new Hashtable();
    while (classesTemp.hasMoreElements())
      {
	currClassTemp = (Integer)classesTemp.nextElement();
	rest.put(currClassTemp, currClassTemp);
      }

    if (rest.size() > 0)
      distribute(rest, am, rand);
  }

  /** prints the content of the map received as argument */
  static private void printMap(Hashtable m)
  {
    for (Enumeration classes = m.keys(); classes.hasMoreElements(); )
      System.out.print(classes.nextElement() + " ");
    System.out.println();
  }

  //////////////// MUTATION METHODS ////////////////////

  /** performes the mutation according to mutation type */
  public void mutate( Random rand)
  {
    if (Global.VERBOSE == 1)
      System.out.print("M ");

    switch(mutationType)
      {
      case MUT_RAND:
	// do the mutation
	// by randomly changing some cells in the array of values
	mutateR(rand);
	break;

      case MUT_SWAP_ELEM:
	// do the mutation
	// by swapping elements between classes
	mutateAM_SW(rand);
	break;

      case MUT_MOVE_ELEM:
	// do the mutation
	// by moving elements from one class to the other
	mutateAM_ME(rand);
	break;
	
      default:
	System.err.println("ERROR! Chromosome.mutate(): wrong choice"
			   + " of mutation type");
	System.exit(1);
      }
  }

  
  /** randomly mutates 10% elements */
  private void mutateR(Random rand)
  {
    int nMutations = (int)(0.1*size);
    // make at least one mutation
    if (nMutations == 0)
      nMutations = 1;
    
    int temp;
    for (int j = 0; j < nMutations; j++)
      {
	// randomly select the element to mutate
	// k should be a number between 0 and size-1
	int k = rand.nextInt(size);

	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println("element " + k + " in class " + v[k]);

	// randomly select a new class (between 1 and getMaxNoClasses())
	// for element k, different than the old class 
	temp = 1 + rand.nextInt(getMaxNoClasses());
	while (temp == v[k])
	  temp = 1 + rand.nextInt(getMaxNoClasses());
      
	// set the new class
	set(k, temp);
	
	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println(" mutated to " + temp);
      }
  }

  /** moves 10% elements between randomly selected classes */
  private void mutateAM_ME(Random rand)
  {
    int nMoves = (int)(0.1*size);
    // move at least one element
    if (nMoves == 0)
      nMoves = 1;

    int noClasses = getNoClasses(); // actual number of classes  
    Hashtable[] am = new Hashtable[getMaxNoClasses()];
    for (int i = 0; i < getMaxNoClasses(); i++)
      am[i] = new Hashtable();
    getAM(am);
  
    for (int k = 0; k < nMoves; k++)
      {
	// randomly select two distinct classes among which we will transfer
	// one element, k1, k2 are between 0 and noClasses-1
	int k1 = rand.nextInt(noClasses);

	// we do nothing if the first selected class
	// has only one element
	if (am[k1].size() == 1)
	  continue;

	// select destination class
	int k2 = rand.nextInt(getMaxNoClasses());
	while (k2 == k1)
	  k2 = rand.nextInt(noClasses);
	
	// if we picked an empty class, make it be the first empty class
	// if it's not already
	if (k2 > noClasses)
	  k2 = noClasses;

	// increment noClasses if we're going to add to an empty class
	if (k2 == noClasses)
	  noClasses++;
	
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("initial class am[" + k1 + "] ");
	    printMap(am[k1]);
	    System.out.println("initial class am[" + k2 + "] ");
	    printMap(am[k2]);
	  }
	  
	// select randomly the element that will be moved
	// e is between 0 and card_k1 - 1
	int e = rand.nextInt(am[k1].size());
	
	Enumeration keys = am[k1].keys();
	// position the iterator on the right element
	// in class k1
	Integer currClass = null;
	while (e-- >= 0)
	  currClass = (Integer)keys.nextElement();
	
	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println("moving element " + currClass + " from class "
			     + k1 + " to class " + k2);
	am[k1].remove(currClass);
	am[k2].put(currClass, currClass);

	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("final class am[" + k1 + "] ");
	    printMap(am[k1]);
	    System.out.print("final class am[" + k2 + "] ");
	    printMap(am[k2]);
	  }
      }

    //    setAM(am, noClasses);
    setAM(am);
  }


  /** swaps 10% elements between randomly selected classes */
  private void mutateAM_SW(Random rand)
  {
    if (getNoClasses() == 1)
      return;
    
    int nSwaps = (int)(0.1*size);
    // swap at least one element
    if (nSwaps == 0)
      nSwaps = 1;
    
    int noClasses = getNoClasses();
    Hashtable[] am = new Hashtable[noClasses];
    for (int i = 0; i < noClasses; i++)
      am[i] = new Hashtable();
    getAM(am);
 
    int k1, k2, e1, e2;
    for (int k = 0; k < nSwaps; k++)
      {
	// randomly select two distinct classes among which we will swap
	// one element, k1, k2 are between 0 and noClasses-1
	k1 = rand.nextInt(noClasses);
	k2 = rand.nextInt(noClasses);
	while (k2 == k1)
	  k2 = rand.nextInt(noClasses);
      
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("initial class am[" + k1 + "] ");
	    printMap(am[k1]);
	    System.out.print("initial class am[" + k2 + "] ");
	    printMap(am[k2]);
	  }
	  
	// randomly select the elements that will be swap 
	// e1 is between 0 and card_k1 - 1
	// e2 is between 0 and card_k2 - 1
	e1 = rand.nextInt(am[k1].size());
	e2 = rand.nextInt(am[k2].size());
	
	Enumeration classes1 = am[k1].keys();
	Enumeration classes2 = am[k2].keys();
	Integer currClass1 = null;
	Integer currClass2 = null;

	// position the iterator on the right element
	// in class k1
	while (e1-- >= 0)
	  currClass1 = (Integer)classes1.nextElement();

	// position the iterator on the right element
	// in class k2
	while (e2-- >= 0)
	  currClass2 = (Integer)classes2.nextElement();
	
	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println("Swapping elements " + currClass1 + " from class "
			     + k1 + " with element " + currClass2 
			     + " from class "  + k2);
	// swap the elements
	Integer temp = currClass2;
	am[k2].remove(currClass2);
	am[k2].put(currClass1, currClass1);

	am[k1].remove(currClass1);
	am[k1].put(temp, temp);
	  
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("final class am[" + k1 + "] ");
	    printMap(am[k1]);
	    System.out.print("final class am[" + k2 + "] ");
	    printMap(am[k2]);
	  }
      }
    //    setAM(am, noClasses);
    setAM(am);
  }

  static public void main(String[] args)
  {
    int nRows = 10;
    int nCols = 10;
    int nMaxNoClasses = 3;
    Chromosome[] db = new Chromosome[nCols];
    for (int i = 0; i < nCols; i+=2)
      {
	db[i] = new Chromosome(nRows, nMaxNoClasses, Partition.CF_SYM_DIFF,
			       CROSS_RAND + i, MUT_RAND, DISTRIB_RAND);
	db[i+1] = new Chromosome(nRows, nMaxNoClasses, Partition.CF_SYM_DIFF,
			       CROSS_RAND + i, MUT_RAND, DISTRIB_RAND);
      }

    Random rand = new Random(1000);
    
    for (int i = 0; i < nCols; i++)
      db[i].init(rand);

    computeFitnessValues(db, nCols, db, nCols, ImpurityMeasure.GINI,
			 Global.FM_BOTH, null, null, null);

    for (int i = 0; i < nCols/2; i++)
      {
	System.out.println("CROSSOVER " + (CROSS_RAND+i));
	System.out.print(i + ": ");
	db[i].print();
	System.out.print((i+1) + ": ");
	db[i+1].print();
	System.out.println("Crossing over ...");
	db[i].crossover(db[i+1], rand);
	System.out.print(i + ": ");
	db[i].print();
	System.out.print((i+1) + ": ");
	db[i+1].print();
      }

    for (int i = 0; i < 3; i++)
      db[i] = new Chromosome(nRows, nMaxNoClasses, Partition.CF_SYM_DIFF,
			     CROSS_RAND + i, MUT_RAND+i, DISTRIB_RAND);
    for (int i = 0; i < 3; i++)
      db[i].init(rand);

    computeFitnessValues(db, 3, db, 3, ImpurityMeasure.GINI,
			 Global.FM_BOTH, null, null, null);

    for (int i = 0; i < 3; i++)
      {
	System.out.println("MUTATION " + (MUT_RAND+i));
	System.out.print(i + ": ");
	db[i].print();
	db[i].mutate(rand);
	System.out.print(i + ": ");
	db[i].print();
      }
  }
}