/*
  Partition.java
  
  Definition of the class Partition
  
  (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.*;
import java.text.*;

/**
 * Partition
 *
 * @version 	1.0
 * @author	Dana Cristofor
 */
public class Partition
{
  protected int classFitnessType;
  protected int[] v;  // array of integers
  protected int size; // no. of elements

  protected int maxNoClasses; // maximum no. of classes (distinct elements)
  protected Hashtable classCard; // classes cardinalities, key (integer):
			         // class id, value (integer) class
			         // cardinality
  protected Hashtable classCode; // classes encodings, key is a
				 // String representing the
				 // original value, mapped to an
				 // Integer representing the
				 // encoding
  protected Hashtable classFitness; // we remember the fitness for each
				    // class of the partition; key
				    // (Integer): class number, value
				    // (Double): fitness of the class
  protected boolean cfIsValid;

  protected double fitness; // fitness of the partition

  // class fitness types
  static public final int CF_SYM_DIFF  = 1; // symmetrical difference
  static public final int CF_PROD      = 2; // |Cj|imp(Cj)
  static public final int CF_DIV       = 3; // imp(Cj) / |Cj|
  static public final int CF_POW       = 4; // 2^imp(Cj) / |Cj| 

  Partition(int size)
  {
    this(size, 0, CF_SYM_DIFF);
  }

  Partition(int size, int maxNoClasses)
  {
    this(size, maxNoClasses, CF_SYM_DIFF);
  }

  Partition(int size, int maxNoClasses, int classFitnessType)
  {
    this.size = size;
    v = new int[size];
    for (int i = 0; i < size; i++)
      v[i] = 0;  // initial values 0, no class is set yet
    this.maxNoClasses = maxNoClasses;
    classCard = new Hashtable();
    classCode = new Hashtable();
    classFitness = new Hashtable();
    fitness = 0.0;
    this.classFitnessType = classFitnessType;
    cfIsValid = false;
  }

  /** sets <code>rowid</code> to belong to class <code>c</code>,
   * updates the class cardinality of the new and old class to whom
   * rowid belongs */
  public void set(int rowid, int c)
  {
    // if new class equal the old class return
    if (v[rowid] == c)
      return;
    
    // otherwise update classCard info!

    // if v[rowid] already had a class number
    Integer oldClassNo = new Integer(v[rowid]);
    if (v[rowid] != 0)
      if (classCard.containsKey(oldClassNo))
	{
	  // if v[rowid] is unique
	  int card = ((Integer)classCard.get(oldClassNo)).intValue();
	  if (card == 1)
	    // remove this class from the map
	    classCard.remove(oldClassNo);
	  else
	    // decrement cardinality of previous class v[rowid]
	    classCard.put(oldClassNo, new Integer(card - 1)); 
	}
    
    // set new value
    v[rowid] = c;
    
    // increment the cardinality of new class val
    Integer newClassNo = new Integer(c);

    int newClassCard = 1;
    if (classCard.containsKey(newClassNo))
      newClassCard = ((Integer)classCard.get(newClassNo)).intValue() + 1;
   
    classCard.put(newClassNo , new Integer(newClassCard));
    
    cfIsValid = false;
  }

  /** @return the class of <code>rowid</code> */
  public int get(int rowid)
  {
    if (Global.DEBUG == 1)
      if (rowid >= size)
	{
	  System.err.println("ERROR! Partition.get(): rowid too large");
	  System.exit(1);
	}

    return v[rowid];
  }

  /** @return true if the class <code>classOrig</code> has already a
   *  numeric code */
  public boolean hasClassCode(String classOrig)
  {
    return classCode.containsKey(classOrig);
  }

  /** @return an Integer encoding associated with the class
   * <code>classOrig</code>*/
  public Integer getClassCode(String classOrig)
  {
    return (Integer)(classCode.get(classOrig));
  }

  /** sets an Integer encoding <code>code</code> for the class
   * <code>classOrig</code>*/
  public void setClassCode(String classOrig, Integer code)
  {
    classCode.put(classOrig, code);
  }

  /** @return the maximum number of classes */
  public int getMaxNoClasses()
  {
    return maxNoClasses;
  }

  /** @return the actual number of classes */
  public int getNoClasses()
  {
    return classCard.size();
  }

  /** prints information about the classes of this Partition */
  public void printClassInfo()
  {
    for (Enumeration e = classCode.keys() ; e.hasMoreElements() ; ) 
      {
	String classOrig = (String)(e.nextElement());
	Integer encoding  = (Integer)classCode.get(classOrig);
	System.out.println(classOrig + " enc: " +  encoding 
			   + " card: " + classCard.get(encoding));
      }
  }

  /** returns a String containing a list of classes of this Partition
   * and their cardinalities */
  public String getClassesAndCardinalities()
  {
    StringBuffer output = new StringBuffer();
    for (Enumeration classes = classCard.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	output.append(currClass + " (" 
		      + classCard.get(currClass) + ") ");
      }
    return output.toString();
  }

  /** prints cardinalities of the classes of this Partition */
  public void printClassCardinalities()
  {
    for (Enumeration classes = classCard.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	System.out.print(currClass + " (" 
			 + classCard.get(currClass) + ") ");
      }
    System.out.println();
  }

  /** appends cardinalities of the classes of this Partition to the
   * <code>output</code> */
  public void printClassCardinalities(StringBuffer output)
  {
    for (Enumeration classes = classCard.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	output.append(currClass + " (" 
		      + classCard.get(currClass) + ") ");
      }
    output.append("\n");
  }

  /** prints the class fitness values */
  public void printClassFitness()
  {
    if (cfIsValid == false)
      {
	System.err.println("ERROR! Partition.getClassFitness(): cfIsValid = false");
	System.exit(1);
      }

    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(3);

    for (Enumeration classes = classFitness.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	System.out.print(currClass + " (" 
			 + nf.format(classFitness.get(currClass)) + ") ");
      }
    System.out.println();
  }


  /** @return the size of this Partition */
  public int getSize()
  {
    return size;
  }

  /** resets the size of this partition to a smaller value
   * <code>size</code>*/
  public void setSize(int size)
  {
    if (size <= this.size)
      this.size = size;
  }

  /** randomly initializes this Partition 
   *  @param rand random number generator
  */
  public void init(Random rand)
  {
    for (int j = 0; j < size; j++)
      // fill with a random number between 1 and getMaxNoClasses()
      set(j, rand.nextInt(getMaxNoClasses()) + 1); 
    
    // if we do not have exactly getMaxNoClasses() adjust the chromosome
    if (getNoClasses() != getMaxNoClasses())
      adjust(rand);
  }


  /** adjusts this Partition to have exactly
   * <code>getMaxNoClasses()</code> classes 
   * @param rand a random number generator object
  */
  public void adjust(Random rand)
  {
    //System.out.println("adjusting...");
    int noClasses = getNoClasses();
    int maxNoClasses = getMaxNoClasses();
    Hashtable[] am = new Hashtable[maxNoClasses];
    for (int i = 0; i < maxNoClasses; i++)
      am[i] = new Hashtable();

    getAM(am);
  
    // the empty classes will be between indices noClasses and
    // getMaxNoClasses()-1
    // populate the empty classes
    for (int k = noClasses; k < getMaxNoClasses(); k++)
      {
	// pick a random class between 0 and noClasses - 1
	int pos = rand.nextInt(noClasses);
      
	// if the selected class has less than 2 elements
	// choose again
	while (am[pos].size() < 2)
	  pos = rand.nextInt(noClasses);
      
	// pick one element in the selected class
	// between 0 and size-1
	int selClass = rand.nextInt(am[pos].size());
	
	// retrieve the class to move
	Integer classToMove = null;
	try
	  {
	    for (Enumeration keys = am[pos].keys(); selClass >= 0; selClass--)
	      classToMove = (Integer)keys.nextElement();
	  }
	catch(NoSuchElementException e)
	  {
	    System.err.println("InternalError: Partition.adjust()");
	    System.exit(1);
	  }

	// move the element
	am[k].put(classToMove, classToMove);
	am[pos].remove(classToMove);
      }
    
    // setAM(am, getMaxNoClasses());
    setAM(am);
  }

  /** fills an array of Hashtable objects, <code>am</code>, with the
   * array representation of the partition; in this array each class
   * corresponds to an index in the array; the contents of the array
   * at that index is a Hashtable with the rowids where the class
   * appears in the partition */
  public void getAM(Hashtable[] am)
  {
    // maps classes to the order in the array of maps
    Hashtable classToIndexMap = new Hashtable();

    int index = 0;
    for (int i = 0; i < size; i++)
      {
	// v[i] is the class, key in the map
	// classToIndexMap.get(v[i]) is the index in am where
	Integer currClassNo = new Integer(v[i]);
	
	// this class will be stored at classToIndexMap index in am
	// class v[i] was not mapped yet
	if (classToIndexMap.containsKey(currClassNo) == false)
	  classToIndexMap.put(currClassNo, 
			      new Integer(index++));

	// key and value are the same
	Integer currRowid = new Integer(i);
	am[((Integer)classToIndexMap.get(currClassNo)).intValue()].put(currRowid, currRowid);
      }
  }

  /** sets this Partition according to the groupings in the array of
   * Hashtables <code>am</code> that contains <code>am.length</code>
   * Hashtables */
  public void setAM(Hashtable[] am)
  {
    //    System.out.println("B setAM " + getNoClasses() + " " + am.length);
    int noClasses = am.length;

    // empty the classCard map
    classCard.clear();

    // reset partition to 0
    for (int i = 0; i < size; i++)
      v[i] = 0;

    // we can have at most noClasses classes
    for (int i = 0; i < noClasses; i++)
      for (Enumeration e = am[i].keys(); e.hasMoreElements(); )
	{
	  int currRowid = ((Integer)e.nextElement()).intValue();
	  set(currRowid, i+1);

	  /*
	  v[currRowid] = i+1; // classes will be encoded starting from 1
	  Integer currClass = new Integer(i+1);
	  int currCard = 0;
	  if (classCard.containsKey(currClass) == true)
	    currCard = ((Integer)classCard.get(currClass)).intValue();
	  
	  // increment class cardinality
	  classCard.put(currClass, new Integer(currCard + 1)); 
	  */
	}
    
    cfIsValid = false;

    //    System.out.println("A setAM " + getNoClasses() + " " + am.length);
  }

  /** prints this Partition as an array of integers */
  protected void print()
  {
    for (int i = 0; i < size; i++)
      System.out.print(v[i] + " ");
    
    System.out.println();
  }

  /** appends contents of this Partition as an array of integers to
   * <code>output</code>*/
  protected void print(StringBuffer output)
  {
    for (int i = 0; i < size; i++)
      output.append(v[i] + " ");
    
    output.append("\n");
  }

  /** prints this Partition as an array of a collection of rowids */
  public void printAM()
  {
    int noClasses = getNoClasses();
    Hashtable[] am = new Hashtable[noClasses];
    for (int i = 0; i < noClasses; i++)
      am[i] = new Hashtable();
    
    System.out.print("printAM noClasses = " + noClasses);
    print();

    getAM(am);
  
    System.out.print("[");
    for (int i = 0; i < noClasses; i++)
      {
	 System.out.print("[ ");

	 try
	   {
	     for (Enumeration keys = am[i].keys(); keys.hasMoreElements(); )
	       System.out.print(keys.nextElement() + " ");
	   }
	 catch(NoSuchElementException e)
	   {
	     System.err.println("InternalError:Partition.printAM()!");
	     System.exit(1);
	   }

	 System.out.print("]");
      }
    System.out.println("]");
  }
  
  /** @return the entropy of this partition computed with
   * <code>entropyMeasure</code> */
  public double entropy(int entropyMeasure)
  {
    double entropy = 0.0;
    for (Enumeration classCards = classCard.elements(); 
	 classCards.hasMoreElements(); )
      entropy += ImpurityMeasure.impurityMeasure(entropyMeasure,
						 ((Integer)classCards.nextElement()).intValue() / (double)size);
    return entropy;
  }

  /** @return true if this Partition is equal to the one received as
   * argument, false otherwise */
  public boolean isEqual(Partition p)
  {
    if (size != p.size)
      {
	if (Global.DEBUG == 1)
	  System.err.println("Warning! Partition.isEqual(): compared two partitions with different size");
	return false;
      }
    
    for (int i = 0; i < size; i++)
      if (v[i] != p.v[i])
	return false;
    
    return true;
  }

  /** sets the values of this Partition equal to the one from the
   * parameter */
  public void set(Partition p)
  {
    if (Global.DEBUG == 1)
      if (size != p.size)
	{
	  System.err.println("ERROR! Partition.set(): partitions have different size");
	  System.exit(1);
	}

    for (int rowid = 0 ; rowid < size; rowid++)
      set(rowid, p.v[rowid]);
    
    fitness = p.fitness;
    classFitness = new Hashtable(p.classFitness);
    cfIsValid = p.cfIsValid;
  }

  /** @return the cardinality of class <code>c</code> */
  public int getClassCard(int c)
  {
    Integer classNo = new Integer(c);
    if (classCard.containsKey(classNo) == true)
      return ((Integer)classCard.get(classNo)).intValue();
    else
      return 0;
  }

  /** @return the fitness of class <code>c</code> */
  public double getClassFitness(int c)
  {
    if (cfIsValid == false)
      {
	System.err.println("ERROR! Partition.getClassFitness(): cfIsValid = false");
	System.exit(1);
      }

    Integer classNo = new Integer(c);
    if (classFitness.containsKey(classNo))
      return ((Double)classFitness.get(classNo)).doubleValue();
    else
      {
	System.err.println("ERROR! Partition.getClassFitness(): invalid class no " + c);
	System.exit(1);
      }
    return 0.0;
  }

  /** sets the fitness of class <code>c</code> to <code>value</code> */
  public void setClassFitness(int c, double value)
  {
    classFitness.put(new Integer(c), new Double(value));
    cfIsValid = true;
  }

  /** @return fitness of this Partition */
  public double getFitness()
  {
    return fitness;
  }

  /** sets the fitness of this Partition to value <code>f</code> */
  public void setFitness(double f)
  {
    fitness = f;
  }

  /** @return the fitness type of the classes */
  public int getClassFitnessType()
  {
    return classFitnessType;
  }

  /** computes intersections between the classes of partitions in
      collection <code>c1</code> and classes of the partitions in
      collection <code>c2</code>
      @param NPART1 represents the number of partitions in c1
      @param NPART2 represents the number of partitions in c2
      @param intersectMap stores in intersectMap[i][j]: <class of
      c1[i], <class of c2[j], intersection count >>;
      intersectMap[i][j] is a map for intersections between partitions
      c1[i] and c2[j]; intersectMap[i][j]:key corresponds to each
      distinct value in c1[i](C_s); intersectMap[i][j]:value
      corresponds to a map with intersections between c2[j][t] and
      c1[i][s] (B_t x C_s); intersectMap[i][j] = <C_s, <B_t, B_t x C_s
      >> */
  static public void computeIntersections(Partition[] c1, int NPART1, 
				   Partition[] c2, int NPART2,
				   Hashtable[][] intersectMap)
  {
    int SIZE = c1[0].size; // partition size
    
    // create maps
    for (int rowid = 0; rowid < SIZE; rowid++)
      for (int i = 0; i < NPART1; i++)
	for (int j = 0; j < NPART2; j++)
	  {
	    Integer currClassC1 = new Integer(c1[i].v[rowid]);
	    Integer currClassC2 = new Integer(c2[j].v[rowid]);
	    
	    if (intersectMap[i][j].containsKey(currClassC1) == false)
	      {
		// currClassC1 has no hashtable associated yet
		// create a new table, with mapping (currClassC2, 1)
		Hashtable h = new Hashtable();
		h.put(currClassC2, new Integer(1));
		intersectMap[i][j].put(currClassC1, h);
	      }
	    else
	      {
		// currClassC1 has already a hashtable associated
		Hashtable h = (Hashtable)intersectMap[i][j].get(currClassC1);
		// does it contain an entry for currClassC2
		if (h.containsKey(currClassC2) == false)
		  h.put(currClassC2, new Integer(1));
		else
		  {
		    int oldCount = ((Integer)h.get(currClassC2)).intValue();
		    h.put(currClassC2, new Integer(oldCount+1));
		  }
	      }
	  }
  }
  
  /** computes intersections between the classes of partition
      <code>p</code> and classes of the partitions in collection
      <code>c</code>
      @param NPART represents the number of partitions in c
      @param intersectMap[i] stores: <class of p, <class of c[i],
      intersection count >>; intersectMap[i] is a map for
      intersections between partitions c[i] and p; intersectMap[i]:
      key corresponds to each distinct value in p (C_s);
      intersectMap[i]: value corresponds to a map with intersection
      between c[i][t] and p[s] (B_t x C_s); intersectMap[i] = <C_s,
      <B_t, B_t x C_s >> */
  static public void computeIntersections(Partition p, 
					  Partition[] c, int NPART,
					  Hashtable[] intersectMap)
  {
    int SIZE = p.size; // partition size
    
    // create maps
    for (int rowid = 0; rowid < SIZE; rowid++)
      for (int i = 0; i < NPART; i++)
	{
	  Integer currClass = new Integer(p.v[rowid]);
	  Integer currClassC = new Integer(c[i].v[rowid]);
	  
	  if (intersectMap[i].containsKey(currClass) == false)
	    {
	      // currClass has no hashtable associated yet
	      // create a new table, with mapping (currClassC, 1)
	      Hashtable h = new Hashtable();
	      h.put(currClassC, new Integer(1));
	      intersectMap[i].put(currClass, h);
	    }
	  else
	    {
	      // currClass has already a hashtable associated
	      Hashtable h = (Hashtable)intersectMap[i].get(currClass);
	      // does it contain an entry for currClassC
	      if (h.containsKey(currClassC) == false)
		h.put(currClassC, new Integer(1));
	      else
		{
		  int oldCount = ((Integer)h.get(currClassC)).intValue();
		  h.put(currClassC, new Integer(oldCount+1));
		}
	    }
	}
  }
  
  /** prints the intersection between classes of one partition and
   * other <code>nPart</code> partitions */
  static public void printIntersections(Hashtable[] intersectMap, int nPart)
  {
    for (int i = 0; i < nPart; i++)
      {
	System.out.println("Intersections with partition " + i);
	try
	  {

	    for (Enumeration classesC1 = intersectMap[i].keys(); 
		 classesC1.hasMoreElements();)
	      {
		Integer currClassC1 = (Integer)classesC1.nextElement();
		Hashtable intersect = (Hashtable)intersectMap[i].get(currClassC1);
		for (Enumeration classesC2 = intersect.keys(); 
		     classesC2.hasMoreElements();)
		  {
		    Integer currClassC2 = (Integer)classesC2.nextElement();
		    System.out.println(currClassC1 + " " + currClassC2 + " " 
				       + intersect.get(currClassC2));
		  }
	      }
	  }
	catch(NoSuchElementException e)
	  {
	    System.err.println("InternalError! Partition.printIntersections");
	    System.exit(1);
	  }
      }
  }

  /** @return entropy of the partition resulting from the
   * intersection of this Partition with the one received as argument,
   * computed with <code>entropyMeasure</code> */
  public double entropyIntersect(Partition p, int entropyMeasure)
  {
    // <Cs, <Bt, |Cs x Bt|> >
    Hashtable[] intersectMap = new Hashtable[1];
    intersectMap[0] = new Hashtable();
    Partition[] c = new Partition[1];
    c[0] = p;
    // create map with intersections
    computeIntersections(this, c, 1, intersectMap);

    double entropy = 0.0;
    // key: C_s, value: <B_t, B_t x C_s >
    for (Enumeration values = intersectMap[0].elements(); 
	 values.hasMoreElements(); )
      {
	Hashtable intersections = (Hashtable)values.nextElement();
	
	// key: B_t, value: |Bt x C_s|
	for (Enumeration counts = intersections.elements(); 
	     counts.hasMoreElements(); )
	  {
	    int count = ((Integer)counts.nextElement()).intValue(); // |B_t x C_s|
	    if (Global.DEBUG == 1)
	      if (count == 0)
		{
		  System.err.println("ERROR! Partition.entropyIntersect(): |B_t x C_s| = 0");
		  System.exit(1);
		}

	    entropy += ImpurityMeasure.impurityMeasure(entropyMeasure,
						       (double)count 
						       /(double)size);
	  }
      }
    
    return entropy;
  }


  /** fills the vector <code>v</code> with a Double representing the
   * value of the entropy of the partition determined by the
   * intersection of all <code>NPART</code> partitions in the
   * collection <code>c</code> and with an Integer representing the
   * number of classes of the intersection partition */
  static public void computeInfoIntersections(Partition[] c, int NPART, 
					      int entropyMeasure,
					      Vector v)
  {
    // the value in the partitions are integers so the key will be an
    // Integer; key:intersection class id, value: cardinality of the
    // class
    Hashtable intersections = new Hashtable();
    int SIZE = c[0].getSize(); // size of the partitions in c
    int key = 0;
    for (int rowid = 0; rowid < SIZE; rowid++)
      {
	for (int i = NPART-1; i >= 0; i--)
	  {
	    // accumulates the values in the columns to create a number; if
	    // the columns contain 1 2 3 4 5 for this rowid the key will
	    // be the number 12345
	    key = key*10 + c[i].v[rowid];
	  }
	
	Integer keyInt = new Integer(key);
	
	int count = 0;
	// is key already in the map, get old count
	if (intersections.containsKey(keyInt) == true)
	  count = ((Integer)intersections.get(keyInt)).intValue();
	
	intersections.put(keyInt, new Integer(count+1));
      }
    
    // compute entropy
    double entropy = 0.0;
    for (Enumeration values = intersections.elements(); 
	 values.hasMoreElements(); )
      entropy += ImpurityMeasure.impurityMeasure(entropyMeasure,
						 ((Integer)values.nextElement()).doubleValue() / (double)SIZE);

    v.insertElementAt(new Double(entropy), 0);

    v.insertElementAt(new Integer(intersections.size()), 1);
  }

  /** @return true if for the specified <code>fitnessMeasure</code>
   * we need to compute the entropy conditioned by the partition of
   * the argument */
  private boolean needsEntropyConditionedByThem(int fitnessMeasure)
  {
    return (fitnessMeasure == Global.FM_P_PA
	    || fitnessMeasure == Global.FM_BOTH
	    || fitnessMeasure == Global.FM_BOTH_SCALED
	    || fitnessMeasure == Global.FM_Q
	    || fitnessMeasure == Global.FM_L
	    || fitnessMeasure == Global.FM_Q_QR
	    || fitnessMeasure == Global.FM_ALTERNATE_HAVG
	    || fitnessMeasure == Global.FM_ALTERNATE
	    || fitnessMeasure == Global.FM_MOD
	    || fitnessMeasure == Global.FM_COS
	    || fitnessMeasure == Global.FM_NORM_W
	    || fitnessMeasure == Global.FM_WE
	    || fitnessMeasure == Global.FM_TEST);
  }

  /** @return true if for the specified <code>fitnessMeasure</code>
   * we need to compute the entropy conditioned by this partition */
  private boolean needsEntropyConditionedByUs(int fitnessMeasure)
  {
    return (fitnessMeasure == Global.FM_PA_P
	    || fitnessMeasure == Global.FM_BOTH
	    || fitnessMeasure == Global.FM_BOTH_SCALED
	    || fitnessMeasure == Global.FM_QR
	    || fitnessMeasure == Global.FM_LR
	    || fitnessMeasure == Global.FM_Q_QR
	    || fitnessMeasure == Global.FM_ALTERNATE_HAVG
	    || fitnessMeasure == Global.FM_ALTERNATE
	    || fitnessMeasure == Global.FM_MOD
	    || fitnessMeasure == Global.FM_COS
	    || fitnessMeasure == Global.FM_NORM_W
	    || fitnessMeasure == Global.FM_WE
	    || fitnessMeasure == Global.FM_TEST);
  }

  /** @return true if for the specified <code>fitnessMeasure</code>
   * we need to compute the entropy of intersections of all
   * partition */
  private boolean needsEntropyOfIntersection(int fitnessMeasure)
  {
    return (fitnessMeasure == Global.FM_L
	    || fitnessMeasure == Global.FM_LR);
  }

  /** @return true if for the specified <code>fitnessMeasure</code>
   * we need to compute weights */
  private boolean needsWeights(int fitnessMeasure)
  {
    return (fitnessMeasure == Global.FM_COS
	    || fitnessMeasure == Global.FM_NORM_W
	    || fitnessMeasure == Global.FM_WE);
  }

  /** if the argument is negative return 0, otherwise return the
   * argument */
  private double filterNegative(double value)
  {
    if (value < 0.0)
      return 0.0;
    else
      return value;
  }


  /** computes the fitness of this Partition with respect to its
   * intersection to <code>NPART</code> partitions in <code>c</code>,
   * available in <code>intersectMap</code>, according to the entropy
   * measure and distance measure */
  public void computeFitness(Hashtable[] intersectMap,
			     Partition[] c, int NPART,
			     int entropyMeasure, int fitnessMeasure,
			     double[] wTargetCondOnDB, 
			     double[] wDBCondOnTarget,
			     double[] weight)
  {
    if (Global.DEBUG == 1)
      if (needsWeights(fitnessMeasure) && 
	  (weight == null || wTargetCondOnDB == null 
	   || wDBCondOnTarget == null))
	{
	  System.err.println("ERROR! Partition.computeFitness() invalid weight");
	  System.exit(1);
	}

    // average entropy of the NPART partitions
    double averageEntropy = 0.0;
    if (fitnessMeasure == Global.FM_ALTERNATE_HAVG)
      {
	// compute average entropy of attribute partitions
	for(int i = 0; i < NPART; i++)
	  averageEntropy += c[i].entropy(entropyMeasure);
	averageEntropy /= NPART;
      }

    // stores in intersectMap[i]: 
    // <class of our partition, <class of c[i], intersection count >>
    // intersectMap[i] is a map for intersections between
    // partitions c[i] and our partition
    // intersectMap[i]->first corresponds to each distinct 
    // value in our partition (C_s)
    // intersectMap[i]->second corresponds to a map with 
    // intersections between c[i][t] and v[s] (B_t x C_s)
    // intersectMap[i] = <C_s, <B_t, B_t x C_s >>

    // c[i]={B_t}, this={C_s}
    // stores in entropyCondThem[i] H(this|c[i])
    double[] entropyCondThem = null; // conditioned by c partitions
    // stores in entropyCondUs[i] H(c[i]|this)
    double[] entropyCondUs = null; // conditioned by our partition
    // stores in entropyIntersect H(this^c[i])
    double[] entropyIntersect = null;

    // memory allocation and initialization
    if (needsEntropyConditionedByThem(fitnessMeasure))
      {
	entropyCondThem = new double[NPART];
	for (int i = 0; i < NPART; i++)
	  entropyCondThem[i] = 0.0; 
      }

    if (needsEntropyConditionedByUs(fitnessMeasure))
      {
	entropyCondUs = new double[NPART];
	for (int i = 0; i < NPART; i++)
	  entropyCondUs[i] = 0.0;
      }
    
    if (needsEntropyOfIntersection(fitnessMeasure))
      {
	entropyIntersect = new double[NPART];
	for (int i = 0; i < NPART; i++)
	  entropyIntersect[i] = 0.0;
      }
    
    // clear old class_fitness maps
    classFitness.clear();
    Hashtable blockFitness = new Hashtable();

    // intersectMap[i] = <C_s, <B_t, B_t x C_s >>      
    // compute entropyCondThem, entropyCondUs
    for (int i = 0; i < NPART; i++)
      {
	// key: C_s, value: <B_t, B_t x C_s >
	for (Enumeration keys = intersectMap[i].keys(); 
	     keys.hasMoreElements(); )
	  {
	    Integer currClass = (Integer)keys.nextElement(); // |C_s|
	    Hashtable intersections = 
	      (Hashtable)intersectMap[i].get(currClass);
	  
	    int ourClassSize = getClassCard(currClass.intValue()); // |C_s|

	    if (Global.DEBUG == 1)
	      if (ourClassSize == 0)
		{
		  System.err.println("ERROR! Partition.computeFitness(): |C_s| = 0 for C_s = " + currClass);
		  print();
		  printClassCardinalities();
		  System.exit(1);
		}
	    
	    double sumCondThem = 0.0;
	    double sumCondUs = 0.0;
	    double sumIntersect = 0.0;

	    // key2: B_t, value2: |Bt x C_s|
	    for (Enumeration keys2 = intersections.keys(); 
		 keys2.hasMoreElements();)
	      {
		Integer currClass2 = (Integer)keys2.nextElement();
		int count = ((Integer)intersections.get(currClass2)).intValue(); // |B_t x C_s|

		if (Global.DEBUG == 1)
		  if (count == 0)
		    {
		      System.err.println("ERROR! Partition.computeFitness(): |B_t x C_s| = 0");
		      System.exit(1);
		    }
	      
		int hisClassSize = c[i].getClassCard(currClass2.intValue()); // |B_t|

		if (Global.DEBUG == 1)
		  if (hisClassSize == 0)
		    {
		      System.err.println("ERROR! Partition.computeFitness(): |B_t| = 0");
		      System.exit(1);
		    }

		if (needsEntropyConditionedByThem(fitnessMeasure))
		  sumCondThem += hisClassSize 
		    * ImpurityMeasure.impurityMeasure(entropyMeasure,
						      (double)count 
						      /(double)hisClassSize);

		if (needsEntropyConditionedByUs(fitnessMeasure))
		  sumCondUs += (double)ourClassSize 
		    * ImpurityMeasure.impurityMeasure(entropyMeasure,
						      (double)count 
						      /(double)ourClassSize);

		if (needsEntropyOfIntersection(fitnessMeasure))
		  sumIntersect += 
		    ImpurityMeasure.impurityMeasure(entropyMeasure,
						    (double)count 
						    /(double)size);

		// compute for classFitness a map 
		// that contains for each our class 
		// <class number, fitness of the class>
		switch(classFitnessType)
		  {
		  case CF_PROD:
		    // <Cs, |Cs| * sum_t |Bt ^ Cs|/|Cs|>
		    if (classFitness.containsKey(currClass) == false)
		      classFitness.put(currClass, 
				       new Double(ourClassSize * ImpurityMeasure.impurityMeasure(entropyMeasure,(double)count /(double)ourClassSize)));
		    else
		      {
			double oldValue = 
			  ((Double)classFitness.get(currClass)).doubleValue();
			classFitness.put(currClass, new Double(oldValue + ourClassSize * ImpurityMeasure.impurityMeasure(entropyMeasure, (double)count /(double)ourClassSize)));
		      }
		    break;

		  case CF_DIV:
		    // <Cs, 1/|Cs| * sum_t |Bt ^ Cs|/|Cs|>
		    if (classFitness.containsKey(currClass) == false)
		      classFitness.put(currClass, new Double((1.0/ourClassSize) * ImpurityMeasure.impurityMeasure(entropyMeasure, (double)count /(double)ourClassSize)));
		    else
		      {
			double oldValue = 
			  ((Double)classFitness.get(currClass)).doubleValue();
			classFitness.put(currClass, new Double(oldValue + (1.0/ourClassSize) * ImpurityMeasure.impurityMeasure(entropyMeasure, (double)count /(double)ourClassSize)));
		      }
		    break;

		  case CF_POW:
		    // <Cs, pow(2, sum_t |Bt ^ Cs|/|Cs|) / |Cs|>
		    // here we are computing pow(2, sum_t |Bt ^ Cs|/|Cs|)
		    // |Cs|/... is adjusted later
		    if (classFitness.containsKey(currClass) == false)
		      classFitness.put(currClass, new Double(Math.pow(2, ImpurityMeasure.impurityMeasure(entropyMeasure, (double)count / (double)ourClassSize))));
		    else
		      {
			double oldValue = 
			  ((Double)classFitness.get(currClass)).doubleValue();
			classFitness.put(currClass, new Double(oldValue * Math.pow(2, ImpurityMeasure.impurityMeasure(entropyMeasure, (double)count / (double)ourClassSize))));
		      }
		    break;

		    // if classFitness_type is 0
		    // use CF_SYM_DIFF
		  case 0:
		  case CF_SYM_DIFF:
		    // <Cs, <i, min (|Cs| + |Bt| - 2|Bt ^ Cs|)/(|Cs| + |Bt|)> >
		    {
		      double val =
			(double)(ourClassSize + hisClassSize - 2 * count)
			/ (double)(ourClassSize + hisClassSize);
		    
		      if (blockFitness.containsKey(currClass) == false)
			// if we see this block for first time
			{
			  Hashtable bf = new Hashtable();
			  bf.put(new Integer(i), new Double(val));
			  blockFitness.put(currClass, bf);
			}
		      else if (((Hashtable)blockFitness.get(currClass)).containsKey(new Integer(i)) == false)
			// if we see partition i for the first time
			{
			  ((Hashtable)blockFitness.get(currClass)).put(new Integer(i), new Double(val));
			}
		      else if (val < ((Double)((Hashtable)blockFitness.get(currClass)).get(new Integer(i))).doubleValue())
			{
			  ((Hashtable)blockFitness.get(currClass)).put(new Integer(i), new Double(val));
			}
		    }
		    break;
		    
		  default:
		    System.err.println("ERROR! Partition.computeFitness(): unknown class fitness measure");
		    System.exit(1);
		  }
	      } // end itr2 loop

	    if (needsEntropyConditionedByThem(fitnessMeasure))
	      entropyCondThem[i] += sumCondThem;
	    if (needsEntropyConditionedByUs(fitnessMeasure))
	      entropyCondUs[i] += sumCondUs;
	    if (needsEntropyOfIntersection(fitnessMeasure))
	      entropyIntersect[i] += sumIntersect;
	  } // end itr loop

	// scaling
	if (needsEntropyConditionedByThem(fitnessMeasure))
	  entropyCondThem[i] /= (double)size;
	if (needsEntropyConditionedByUs(fitnessMeasure))
	  entropyCondUs[i] /= (double)size;
      } // end i loop

    // for fitness class measure CF_POW and CF_SYM_DIFF we need 
    // to make some adjustments to the class fitness
    // we do the adjustment when we have everything computed
    switch(classFitnessType)
      {
      case CF_POW:
	for (int classNo = 1; classNo <= getNoClasses(); classNo++) 
	  {
	    Integer classNoInt = new Integer(classNo);
	    double oldFitness = 
	      ((Double)classFitness.get(classNoInt)).doubleValue();
	    
	    classFitness.put(classNoInt, 
			     new Double(oldFitness / getClassCard(classNo)));
	  }
	break;
	    
      case 0:
      case CF_SYM_DIFF:
	// <Cs, <j, min (|Cs| + |Bt| - 2|Bt ^ Cs|)/(|Cs| + |Bt|)> >
	for (Enumeration keys = blockFitness.keys(); 
	     keys.hasMoreElements(); )
	  {
	    double avg = 0.0;
	    Integer key1 = (Integer)keys.nextElement();
	    Hashtable value1 = 
	      (Hashtable)blockFitness.get(key1);
	    for(Enumeration values2 = value1.elements(); 
		values2.hasMoreElements(); )
	      avg += ((Double)values2.nextElement()).doubleValue();
	  
	    classFitness.put(key1, new Double(avg /(double)NPART));
	  }
	break;
      }

    cfIsValid = true;

    if (Global.ULTRA_VERBOSE == 1)
      printClassFitness();

    double sumEntropyCondUs  = 0.0;
    double sumEntropyCondThem = 0.0;
    double sumSquareEntropies = 0.0;
  
    // for these fitness measures we need to cumulate first
    // the two conditional entropies
    if (fitnessMeasure == Global.FM_NORM_W
	|| fitnessMeasure == Global.FM_ALTERNATE
	|| fitnessMeasure == Global.FM_MOD)
      {
	for (int i = 0; i < NPART; i++)
	  {
	    sumEntropyCondUs += entropyCondUs[i];
	    sumEntropyCondThem += entropyCondThem[i];
	  }
      }
    
    if (fitnessMeasure == Global.FM_MOD)
      fitness = Math.abs(sumEntropyCondUs + sumEntropyCondThem)
	+ Math.abs(sumEntropyCondUs - sumEntropyCondThem);
    else if (fitnessMeasure == Global.FM_ALTERNATE)
      {
	if (sumEntropyCondUs >= sumEntropyCondThem)
	  // minimization of PA_P
	  fitness = sumEntropyCondUs;
	else
	  // minimization of P_PA
	  fitness = sumEntropyCondThem;
      }
    else
      {
	fitness = 0.0;
	for (int i = 0; i < NPART; i++)
	  switch(fitnessMeasure)
	    {
	    case Global.FM_PA_P:
	      fitness += entropyCondUs[i];
	      break;

	    case Global.FM_P_PA:
	      fitness += entropyCondThem[i];
	      break;

	    case Global.FM_BOTH:
	      fitness += entropyCondThem[i] + entropyCondUs[i];
	      break;

	    case Global.FM_BOTH_SCALED:
	      fitness += 
		entropyCondUs[i]/(1 + c[i].entropy(entropyMeasure))
		+ entropyCondThem[i]/(1 + entropy(entropyMeasure));
	      break;

	    case Global.FM_Q:
	      fitness += 
		filterNegative(entropy(entropyMeasure) - entropyCondThem[i])
		/ (1 + c[i].entropy(entropyMeasure));
	      break;

	    case Global.FM_L:
	      fitness += 
		filterNegative(entropy(entropyMeasure) - entropyCondThem[i])
		/ (1 + entropyIntersect[i]);
	      break;

	    case Global.FM_QR:
	      fitness += 
		filterNegative(c[i].entropy(entropyMeasure) - entropyCondUs[i])
		/ (1 + entropy(entropyMeasure));
	      break;

	    case Global.FM_LR:
	      fitness += 
		filterNegative(c[i].entropy(entropyMeasure) - entropyCondUs[i])
		/ (1 + entropyIntersect[i]);
	      break;

	    case Global.FM_Q_QR:
	      fitness += 
		filterNegative(entropy(entropyMeasure) - entropyCondThem[i])
		/ (1 + c[i].entropy(entropyMeasure))
		+ filterNegative(c[i].entropy(entropyMeasure) - entropyCondUs[i])
		/ (1 + entropy(entropyMeasure));
	      break;

	    case Global.FM_ALTERNATE_HAVG:
	      if (entropy(entropyMeasure) <= averageEntropy)
		// minimization of PA_P
		fitness += entropyCondUs[i];
	      else
		// minimization of P_PA
		fitness += entropyCondThem[i];
	      break;

	    case Global.FM_COS:
	      fitness += weight[i] * 
		(entropyCondThem[i] + entropyCondUs[i]);
	      sumSquareEntropies += 
		Math.pow(entropyCondThem[i] + entropyCondUs[i], 2); 
	      break;
	
	    case Global.FM_NORM_W:
	      fitness += Math.abs(entropyCondThem[i] + entropyCondUs[i] 
			      - weight[i] 
			      * (sumEntropyCondUs + sumEntropyCondThem));
	      break;

	    case Global.FM_WE:
	      fitness += 
		Math.abs(wTargetCondOnDB[i] - entropyCondUs[i]) + 
		Math.abs(wDBCondOnTarget[i] - entropyCondThem[i]);
	      break;
	    
	    case Global.FM_TEST:
	      fitness += (entropyCondThem[i] + entropyCondUs[i])
		* weight[i];
	      break;
	    }
      }

    if (fitnessMeasure == Global.FM_COS)
      {
	double sum_square_weights = 0.0;
	for (int i = 0; i < NPART; i++)
	  sum_square_weights += Math.pow(weight[i], 2);
	fitness /= Math.sqrt(sumSquareEntropies)*Math.sqrt(sum_square_weights);
      }
  }

  /** computes the fitness of this Partition with respect to the
   * partitions in collection c, according to the entropy measure and
   * distance measure */
  public void computeFitness(Partition[] c, int NPART, 
			     int entropyMeasure, int fitnessMeasure,
			     double[] wTargetCondOnDB, 
			     double[] wDBCondOnTarget,
			     double[] weight)
  {
    // stores in intersectMap[i]: 
    // <class of our partition, <class of c[i], intersection count >>
    // intersectMap[i] is a map for intersections between
    // partitions c[i] and our partition
    // intersectMap[i]:key corresponds to each distinct 
    // value in our partition (C_s)
    // intersectMap[i]:value corresponds to a map with 
    // intersections between c[i][t] and v[s] (B_t x C_s)
    // intersectMap[i] = <C_s, <B_t, B_t x C_s >>
    Hashtable[]  intersectMap =  new Hashtable[NPART];
    for (int i = 0; i < NPART; i++)
      intersectMap[i] = new Hashtable();

    // fills intersectMap
    computeIntersections(this, c, NPART, intersectMap);
    computeFitness(intersectMap, c, NPART, entropyMeasure, fitnessMeasure,
		   wTargetCondOnDB, wDBCondOnTarget, weight);
  }

  /** estimates the degree in which the other partitions in
   * <code>db</code> influences the target partition; the target
   * partition should be the last partition in <code>db</code>;
   * <code>sampleDBPct</code> specifies the percent of the database to
   * be sampled; sets <code>wTargetCondonDB[i]</code> to
   * H(db[i]|db[target]) and sets the <code>wDBCondOnTarget[i]</code>
   * to H(db[target]|db[i]); sets <code>weight[i]</code> to
   * wTargetCondOnDB[i]+wDBCondOnTarget[i] 
   @return the entropy of the partition sampled from the database */
  static public double estimateWeights(Partition[] db, int NPART,
				       double sampleDBPct,
				       int entropyMeasure, 
				       double[] wTargetCondOnDB,
				       double[] wDBCondOnTarget,
				       double[] weight, Random rand)
  {
    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(3);

    double targetEntr = 0;
    int SIZE = db[0].getSize();
  
    // reference partition in the sample database
    Partition sampleRefPart = null;
  
    // create a separate sample database
    int sampleDBSize = (int)(SIZE*sampleDBPct);
    // consider at least a sample db of size 2
    if (sampleDBSize < 2)
      sampleDBSize = 2;

    // rowids of the database that will belong to the sample
    int[] sampleRowids = new int[sampleDBSize];
    SelectionMethods.selectUnif(SIZE, sampleRowids, sampleDBSize, rand);
    
    Partition[] sampleDB = new Partition[NPART];
    for (int i = 0; i < NPART; i++)
      sampleDB[i] = new Partition(sampleDBSize, 
				  db[0].getMaxNoClasses(), 
				  db[0].getClassFitnessType());
  
    if (Global.VERBOSE == 1)
      {
	for (int i = 0; i < sampleDBSize; i++)
	  System.out.print(sampleRowids[i] + " ");
	System.out.println();
      }

    // extract the sample database from the original database
    int index = 0;
    for (int i = 0; i < sampleDBSize; i++, index++)
      for (int j = 0; j < NPART; j++)
	sampleDB[j].set(index, db[j].get(sampleRowids[i]));
  
  
    if (Global.VERBOSE == 1)
      for (int i = 0; i < NPART; i++)
	sampleDB[i].print();

    // the reference partition is the last column
    sampleRefPart = sampleDB[NPART - 1];
  
    // compute weights of all attributes with respect to the reference
    // partition using the sampleDB
    // the fitness of sampleDB[i] represents the weight
    // weight[i] = H(sampleDB[i]|ref_part) + H(ref_part|sampleDB[i])
    Partition[] c = new Partition[1];
    c[0] = sampleRefPart;
    for (int i = 0; i < NPART - 1; i++)
      {
	sampleDB[i].computeFitness(c, 1, entropyMeasure, Global.FM_P_PA, 
				     null, null, null);
	wDBCondOnTarget[i] = sampleDB[i].getFitness();

	sampleDB[i].computeFitness(c, 1, entropyMeasure, Global.FM_PA_P, 
				   null, null, null);
	wTargetCondOnDB[i] = sampleDB[i].getFitness();

	weight[i] = wTargetCondOnDB[i] + wDBCondOnTarget[i];
      }

    targetEntr = sampleRefPart.entropy(entropyMeasure);

    if (Global.VERBOSE == 1)
      {
	System.out.println("attr_no weight_target_cond_on_db" +
			 " weight_db_cond_on_target sum");

	for (int i = 0; i < NPART - 1; i++)
	  System.out.println(i + "  " + nf.format(wTargetCondOnDB[i]) + "  " 
			     + nf.format(wDBCondOnTarget[i]) 
			     + "  " + nf.format(weight[i]));
	
	System.out.println("H(target) = " + nf.format(targetEntr));
	System.out.println("H(target)-H(target|db)   H(db)-H(db|target)");

	double avgDBInfluence = 0.0;
	for (int i = 0; i < NPART - 1; i++)
	  {
	    System.out.println(i + "  " 
			       + nf.format(new Double(targetEntr - wTargetCondOnDB[i]))
			       + "  " + 
			       nf.format(new Double(sampleDB[i].entropy(entropyMeasure) 
					  - wDBCondOnTarget[i])));
	    avgDBInfluence += targetEntr - wTargetCondOnDB[i];
	  }

	System.out.println("avg H(target)-H(target|db) = " 
			   + nf.format(new Double(avgDBInfluence/(double)(NPART-1))));
      }

    return targetEntr;
  }


  /** @return the symmetrical difference between the classes of the
   * current partition and the one received as argument */
  public double distSymDiff(Partition c)
  {
    // get the unique representation into classes
    int noClasses1 = getNoClasses();
    Hashtable[] am1 = new Hashtable[noClasses1];
    for (int i = 0; i < noClasses1; i++)
      am1[i] = new Hashtable();

    getAM(am1);
  
    // get the unique representation into classes
    int noClasses2 = c.getNoClasses();
    Hashtable[] am2 = new Hashtable[noClasses2];
    for (int i = 0; i < noClasses2; i++)
      am2[i] = new Hashtable();

    c.getAM(am2);
    
    long symDiff = 0;
    for (int k2 = 0; k2 < noClasses2; k2++)
      symDiff += (am2[k2].size()*am2[k2].size());

    for (int k1 = 0; k1 < noClasses1; k1++)
      {
	symDiff += (am1[k1].size()*am1[k1].size());
	for (int k2 = 0; k2 < noClasses2; k2++)
	  {
	    long common = 0;
	    for (Enumeration keys1 = am1[k1].keys(); 
		 keys1.hasMoreElements(); )
	      if (am2[k2].containsKey((Integer)keys1.nextElement()) == true)
		common++;
	    symDiff -= (2*common*common);
	  }
      }

    return ((double)symDiff)/2;
  }

  /** @return Sum distSymDiff(p), for all p in the collection c */
  public double sumDistSymDiff(Partition[] c, int NPART)
  {
    double dist = 0.0;
    for (int i = 0; i < NPART; i++)
      dist += distSymDiff(c[i]);
    
    return dist;
  }

  /** @return the average Hamming distance between the row
   * <code>rowid</code> and all other rows from the class
   * <code>c</code>, according to the values of the <code>NPART</code>
   * partitions in <code>db</code> on these rows */
  private double avgHD(int rowid, Hashtable c, Partition[] db, int NPART)
  {
    long avgHD = 0;
    for (Enumeration keys = c.keys(); 
	 keys.hasMoreElements(); )
      {
	int currRowid = ((Integer)keys.nextElement()).intValue();
	if (currRowid != rowid)
	  {
	    long currHD = 0;
	    for (int j = 0; j < NPART; j++)
	      if (db[j].v[rowid] != db[j].v[currRowid])
		currHD++;
	    avgHD += currHD;
	  }
      }
  
    return ((double)avgHD)/((double)c.size());
  }

  
  /** fills the array <code>silhouettes</code> of dimension 'size'
   * with the silhoutte coefficients, computed with respect to the
   * classes in this Partition and with respect to the values of the
   * <code>NPART</code> partitions in collection <code>c</code>; this
   * Partition should have at least 2 classes; <code>neighbors</code>
   * will contain for each rowid the class number of the closest
   * class */
  public void computeSilhouettes(double[] silhouettes, 
				 int[] neighbors,
				 Partition[] c, int NPART)
  {
    // noClasses should be greater than 2
    int noClasses = getNoClasses();
    
    if (Global.DEBUG == 1)
      if (noClasses < 2)
	{
	  System.out.println("ERROR! Partition.computeSilhouettes():"
			     + "noClasses < 2");
	  System.exit(1);
	}

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

    getAM(am);
  
    for (int rowid = 0; rowid < size; rowid++)
      {
	// find to what class rowid belongs
	int classNo;
	for (classNo = 0; classNo < noClasses; classNo++)
	  if (am[classNo].containsKey(new Integer(rowid)) == true)
	    break;

	// rowid belongs to classNo
	double a = avgHD(rowid, am[classNo], c, NPART);

	// find average distances with respect to all other classes
	// (classNo, avgHD)
	Hashtable otherClassesHD = new Hashtable();

	for (int k = 0; k < noClasses; k++)
	  if (k != classNo)
	    otherClassesHD.put(new Integer(k), 
			       new Double(avgHD(rowid, am[k], c, NPART)));
      
	// find the class with smallest avgHD
	// we know that we have at least 2 classes at this point
	Enumeration keys = otherClassesHD.keys();
	Integer firstClass = (Integer)keys.nextElement();

	double b = ((Double)otherClassesHD.get(firstClass)).doubleValue();
	neighbors[rowid] = firstClass.intValue();

	for (Enumeration classes = otherClassesHD.keys();
	     classes.hasMoreElements(); )
	  {
	    Integer currClass = (Integer)classes.nextElement();
	    double currValue = 
	      ((Double)otherClassesHD.get(currClass)).doubleValue();
	    if (currValue < b)
	      {
		b = currValue;
		neighbors[rowid] = currClass.intValue();
	      }
	  }

	// if rowid is the only element is that class
	if (am[classNo].size() == 1)
	  silhouettes[rowid] = 0;
	else if (a < b)
	  silhouettes[rowid] = 1 - a/b;
	else if (a == b)
	  silhouettes[rowid] = 0;
	else
	  silhouettes[rowid] = b/a - 1;
      }
  }

  private class SilhInfo implements Comparable
  {
    public int rowid;
    public double silhouette;
    public int neighbor;

    SilhInfo(int rowid, double silhouette, int neighbor)
    {
      this.rowid      = rowid;
      this.silhouette = silhouette;
      this.neighbor   = neighbor;
    }

    public int compareTo(Object o)
    {
      if (!(o instanceof SilhInfo))
	throw new ClassCastException();

      if (silhouette < ((SilhInfo)o).silhouette)
	return -1;
      else 
	if (silhouette > ((SilhInfo)o).silhouette)
	  return 1;
	else
	    return 0;
    }
  }

  /** plots a graphical representation of the silhouettes; classes are
   * plotted in order and the elements in the classes are plotted in
   * decreasing order of their silhouette */
  public void plotSilhouettes(double[] silhouettes, int[] neighbors)
  {
    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(3);

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

    getAM(am);

    double avgSilh = 0;
    for (int rowid = 0; rowid < size; rowid++)
      avgSilh += silhouettes[rowid];
    
    System.out.println("Average silhouette " + nf.format(avgSilh/(double)size));

    for (int classNo = 0; classNo < noClasses; classNo++)
      {
	Heap silhToPrint = new Heap(noClasses);
	for (Enumeration rowids = am[classNo].keys();
	     rowids.hasMoreElements();)
	  {
	    int currRowid = ((Integer)rowids.nextElement()).intValue();
	    silhToPrint.insert(new SilhInfo(currRowid, silhouettes[currRowid],
					    neighbors[currRowid]));
	  }

	while (silhToPrint.size() != 0)
	  {
	    SilhInfo s = null;
	    try
	      {
		s = (SilhInfo)silhToPrint.remove();
	      }
	    catch(EmptyHeapException e)
	      {
		System.err.println("Internal Error: Partition.plotSilhouettes(): empty heap");
		System.exit(1);
	      }

	    double currSilh = s.silhouette;
	    System.out.print("c " + (classNo + 1) 
			       + " n " + (s.neighbor + 1) 
			       + " r " + s.rowid + "\t");
	    if (currSilh < 0)
	      {
		int i = 0;
		while(i++ < -30*currSilh)
		  System.out.print("-");
	      }
	    else
	      {
		int i = 0;
		while(i++ < 30*currSilh)
		  System.out.print("+");
	      }
	    System.out.println(" (" + currSilh + ")");
	  }
      }
  }

  /** appends to <code>output</code> a graphical representation of the
   * silhouettes; classes are plotted in order and the elements in the
   * classes are plotted in decreasing order of their silhouette */
  public void plotSilhouettes(double[] silhouettes, int[] neighbors, 
			      StringBuffer output)
  {
    int noClasses = getNoClasses();  
    Hashtable[] am = new Hashtable[noClasses];
    for (int i = 0; i < noClasses; i++)
      am[i] = new Hashtable();

    getAM(am);

    double avgSilh = 0;
    for (int rowid = 0; rowid < size; rowid++)
      avgSilh += silhouettes[rowid];
    
    output.append("Average silhouette " + avgSilh/(double)size + "\n");

    for (int classNo = 0; classNo < noClasses; classNo++)
      {
	Heap silhToPrint = new Heap(noClasses);
	for (Enumeration rowids = am[classNo].keys();
	     rowids.hasMoreElements();)
	  {
	    int currRowid = ((Integer)rowids.nextElement()).intValue();
	    silhToPrint.insert(new SilhInfo(currRowid, silhouettes[currRowid],
					    neighbors[currRowid]));
	  }

	while (silhToPrint.size() != 0)
	  {
	    SilhInfo s = null;
	    try
	      {
		s = (SilhInfo)silhToPrint.remove();
	      }
	    catch(EmptyHeapException e)
	      {
		System.err.println("Internal Error: Partition.plotSilhouettes(): empty heap");
		System.exit(1);
	      }

	    double currSilh = s.silhouette;
	    output.append("c " + (classNo + 1) 
			  + " n " + (s.neighbor + 1) 
			  + " r " + s.rowid + "\t");
	    if (currSilh < 0)
	      {
		int i = 0;
		while(i++ < -30*currSilh)
		  output.append("-");
	      }
	    else
	      {
		int i = 0;
		while(i++ < 30*currSilh)
		  output.append("+");
	      }
	    output.append(" (" + currSilh + ")\n");
	  }
      }
  }



  /** prints information about this Partition */
  public void printInfo(Partition[] db, int NPART, 
			double[] wTargetCondOnDB, 
			double[] wDBCondOnTarget, 
			double[] weight,
			int entropyMeasure, int fitnessMeasure,
			String s)
  {
    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(3);

    printClassCardinalities();
    System.out.println("entropy " + s + ": " 
		       + nf.format(entropy(entropyMeasure)));
    computeFitness(db, NPART, entropyMeasure, fitnessMeasure, 
		   wTargetCondOnDB, wDBCondOnTarget, weight);
    System.out.println("fitness " + s + ": " + nf.format(fitness));
    computeFitness(db, NPART, entropyMeasure, Global.FM_BOTH, 
		   wTargetCondOnDB, wDBCondOnTarget, weight);
    System.out.println("Sum H(piA|pi) + H(pi|piA) " + s + ": " 
		       + nf.format(fitness));

    if (Global.VERBOSE == 1)
      {
	System.out.println("Symmetrical difference equiv classes: "
			 + nf.format(sumDistSymDiff(db, NPART)));

	if (getNoClasses() > 1)
	  {
	    double[] silhouettes = new double[size];
	    int[] neighbors = new int[size];
	    computeSilhouettes(silhouettes, neighbors, db, NPART);
	    plotSilhouettes(silhouettes, neighbors);
	  }
      }
  }

  /** appends information about this Partition to
   * <code>output</code>*/
  public void printInfo(Partition[] db, int NPART, 
			double[] wTargetCondOnDB, 
			double[] wDBCondOnTarget, 
			double[] weight,
			int entropyMeasure, int fitnessMeasure,
			String s, StringBuffer output)
  {
    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(3);

    printClassCardinalities(output);
    output.append("entropy " + s + ": " 
		  + nf.format(entropy(entropyMeasure)) + "\n");
    computeFitness(db, NPART, entropyMeasure, fitnessMeasure, 
		   wTargetCondOnDB, wDBCondOnTarget, weight);
    output.append("fitness " + s + ": " 
		  + nf.format(fitness) + "\n");
    computeFitness(db, NPART, entropyMeasure, Global.FM_BOTH, 
		   wTargetCondOnDB, wDBCondOnTarget, weight);
    output.append("Sum H(piA|pi) + H(pi|piA) " + s + ": " 
		  + nf.format(fitness) + "\n");

    if (Global.VERBOSE == 1)
      {
	output.append("Symmetrical difference equiv classes: "
		      + nf.format(sumDistSymDiff(db, NPART)) + "\n");

	if (getNoClasses() > 1)
	  {
	    double[] silhouettes = new double[size];
	    int[] neighbors = new int[size];
	    computeSilhouettes(silhouettes, neighbors, db, NPART);
	    plotSilhouettes(silhouettes, neighbors, output);
	  }
      }
  }


  /** <code>mapIntersect</code> contains <B_t, |B_txC_s|>,
   * <code>excluding</code> is a map of B_t values that should not be
   * considered; the function returns the value B_t with the maximum
   * |B_txC_s| excluding the values specified; return 0 if no class
   * can be found */
  private int findAssocClass(Hashtable mapIntersect, 
			     Hashtable excluding)
  {
    int maxCount;
    int classId;
    if (excluding.size() == 0)
      {
	Enumeration keys = mapIntersect.keys();
	Integer currClass = null;
	try
	  {
	    currClass = (Integer)keys.nextElement();
	  }
	catch(NoSuchElementException e)
	  {
	    System.err.println("Internal Error: Partition.findAssocClass()");
		System.exit(1);	    
	  }
	
	maxCount = ((Integer)mapIntersect.get(currClass)).intValue();
	classId  = currClass.intValue();
      }
    else
      {
	maxCount = 0;
	classId = 0;
	// search for the first class that is not excluded
	for (Enumeration classes = mapIntersect.keys();
	     classes.hasMoreElements();)
	  {
	    Integer currClass = (Integer)classes.nextElement();
	    
	    if (excluding.containsKey(currClass) == false)
	      {
		maxCount = ((Integer)mapIntersect.get(currClass)).intValue();
		classId  = currClass.intValue();
		break;
	      }
	  }

	// all classes are excluded
	if (classId == 0)
	  return 0;
      }

    // search for the class B_t* with the maximum value |B_txC_s|
    // excluding the classes specified
    for (Enumeration classes = mapIntersect.keys();
	 classes.hasMoreElements();)
      {
	Integer currClass = (Integer)classes.nextElement();
	
	// if B_t should be excluded skip it
	if (excluding.size() != 0 && excluding.containsKey(currClass) == true)
	  continue;
      
	if (((Integer)mapIntersect.get(currClass)).intValue() > maxCount)
	  {
	    maxCount = ((Integer)mapIntersect.get(currClass)).intValue();
	    classId  = currClass.intValue();
	  }
      }
    
    return classId;
  }

  /** @return and ArrayList of ArrayList elements containing a string
   * representing the class of target and a String representing
   * intersections with the classes of this Partition */
  public ArrayList getClassIntersections(Partition target)
  {
    // target = (C_s), this = (B_t)
    // intersectMap = <C_s, <B_t, |B_t x C_s| >>
    Hashtable[] intersectMaps = new Hashtable[1];
    intersectMaps[0] = new Hashtable();
    Partition[] c = new Partition[1];
    c[0] = this;
    computeIntersections(target, c, 1, intersectMaps);
    Hashtable intersectMap = intersectMaps[0];

    int targetNoClasses = target.getNoClasses();
    ArrayList result = new ArrayList(targetNoClasses);

    // look for each C_s, at the map <B_t, |B_t x C_s| >
    for (Enumeration classes = intersectMap.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	ArrayList innerRes = new ArrayList(2);
	
	innerRes.add(currClass + "(" + 
		     + target.getClassCard(currClass.intValue())
		     + ")");
	// <B_t, |B_t x C_s| > to sum up all misclassifications
	Hashtable map = (Hashtable)intersectMap.get(currClass);
	StringBuffer value2 = new StringBuffer();
	for (Enumeration classes2 = map.keys(); 
	     classes2.hasMoreElements(); )
	  {
	    Integer currClass2 = (Integer)classes2.nextElement();
	    value2.append(currClass2 + "("
			 + getClassCard(currClass2.intValue())
			 + ")[" + map.get(currClass2) +"]  ");
	  }
	innerRes.add(value2.toString());
	result.add(innerRes);
      }

    return result;
  }

  /** @return the percent of rowids classified in the same way as in
   * the target partition */
  public double getClassifRate(Partition target)
  {
    // target = (C_s), this = (B_t)
    // intersectMap = <C_s, <B_t, |B_t x C_s| >>
    Hashtable[] intersectMaps = new Hashtable[1];
    intersectMaps[0] = new Hashtable();

    Partition[] c = new Partition[1];
    c[0] = this;

    computeIntersections(target, c, 1, intersectMaps);
    Hashtable intersectMap = intersectMaps[0];

    int targetNoClasses = target.getNoClasses();

    // class id c in target partition corresponds to class corrClass[c]
    // in this partition
    int[] corrClass = new int[targetNoClasses + 1]; // we do not use position 0

    // stores at position c the cardinality of the intersection of class
    // c and class corrClass[c]
    int[] cardIntersect = new int[targetNoClasses+1]; // we do not use
						      // position 0

    // we do not use position 0
    Hashtable[] excluding = new Hashtable[targetNoClasses + 1]; 
    for (int i = 0; i < targetNoClasses + 1; i++)
      excluding[i] = new Hashtable();

    // look for each C_s, at the map <B_t, |B_t x C_s| >
    for (Enumeration classes = intersectMap.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	// find the associated class not excluding any class
	int classId = findAssocClass((Hashtable)intersectMap.get(currClass), 
				     excluding[currClass.intValue()]);
      
	// classId was not previously assigned, assign it to C_s
	corrClass[currClass.intValue()] = classId;
	if (classId != 0)
	  cardIntersect[currClass.intValue()] = 
	    ((Integer)(((Hashtable)intersectMap.get(currClass)).get(new Integer(classId)))).intValue();
	else
	  cardIntersect[currClass.intValue()] = 0;
      }
    
    if (Global.VERBOSE == 1)
      {
	System.out.println("original mapping");
	for (int i = 1; i <= targetNoClasses; i++)
	  System.out.println("Ref Part class " + i + "(" 
			     + target.getClassCard(i)+ ") mapped to "
			     + corrClass[i] + " (" 
			     + getClassCard(corrClass[i]) + ") : " 
			     + cardIntersect[i]);
      }

    if (Global.VERBOSE == 1)
      {
	System.out.println("full mapping");
	// look for each C_s, at the map <B_t, |B_t x C_s| >
	for (Enumeration classes = intersectMap.keys(); 
	     classes.hasMoreElements(); )
	  {
	    Integer currClass = (Integer)classes.nextElement();
	    // <B_t, |B_t x C_s| > to sum up all misclassifications
	    Hashtable map = (Hashtable)intersectMap.get(currClass);
	    for (Enumeration classes2 = map.keys(); 
		 classes2.hasMoreElements(); )
	      {
		Integer currClass2 = (Integer)classes2.nextElement();
		System.out.println("target class " + currClass+ "("
				   + target.getClassCard(currClass.intValue()) 
				   + ") mapped to " +  currClass2 + " (" 
				   + getClassCard(currClass2.intValue())
				   + ") : " + map.get(currClass2));
	      }
	  }
      }
	
    // check if the mapping between classes of the target partition and
    // this partition are unique
    for (int i = 1; i <= targetNoClasses; i++)
      {
	// this class has no association
	if (corrClass[i] == 0)
	  continue;
      
	int j;
	for (j = i + 1; j <= targetNoClasses; j++)
	  if (corrClass[i] == corrClass[j])
	    {
	      // decide what class will be assigned to a different one
	      int change = 0;

	      if (cardIntersect[i] < cardIntersect[j])
		change = i;
	      else 
		if (cardIntersect[i] > cardIntersect[j])
		  change = j;
		else // cardIntersect[i] == cardIntersect[j]
		  if (getClassCard(i) < getClassCard(j))
		    change = j;
		  else
		    change = i;

	      // find another candidate associated with class i
	      excluding[change].put(new Integer(corrClass[change]),
				    new Integer(corrClass[change]));

	      corrClass[change] = 
		findAssocClass((Hashtable)intersectMap.get(new Integer(change)),
			       excluding[change]);
	      if (corrClass[change] != 0)
		cardIntersect[change] = 
		  ((Integer)((Hashtable)intersectMap.get(new Integer(change))).get(new Integer(corrClass[change]))).intValue();

	      // some change occur break the j loop
	      break;
	    } // end j loop
	
	// we break from the for above, we should start from the
	// beginning again
	if (j <= targetNoClasses)
	  i = 0;
      }
    

    if (Global.VERBOSE == 1)
      {
	System.out.println("unique mapping");
	// check if the mapping between classes of the target partition and
	// this partition are unique
	for (int i = 1; i <= targetNoClasses; i++)
	  System.out.println("target class " + i + "(" 
			     + target.getClassCard(i) + ") mapped to " 
			     + corrClass[i] + " (" 
			     + getClassCard(corrClass[i]) 
			     + ") : " + cardIntersect[i]);
	
	System.out.println("Elements classified as in target");
	// check if the mapping between classes of the target partition and
	// this partition are unique
	for (int i = 1; i <= targetNoClasses; i++)
	  if (corrClass[i] != 0)
	    System.out.println(cardIntersect[i] + " out of " 
			       + target.getClassCard(i));
      }
    
    int classifCorrect = 0;
    for (int i = 1; i <= targetNoClasses; i++)
      if (corrClass[i] != 0)
	classifCorrect += cardIntersect[i];
    
    if (Global.VERBOSE == 1)
      System.out.println(classifCorrect + " rowids out of " + size 
			 + " have been classified as in target parition");

    return (double)classifCorrect/(double)size;
  }


  static public void main(String[] args)
  {
    int nRows = 5;
    int nCols = 5;
    int nMaxNoClasses = 3;
    Partition[] db = new Partition[nCols];
    for (int i = 0; i < nCols; i++)
      db[i] = new Partition(nRows, nMaxNoClasses);

    Random rand = new Random(1000);

    for (int i = 0; i < nCols; i++)
      {
	db[i].init(rand);
	db[i].print();
	db[i].printAM();      
	System.out.println(db[i].entropy(ImpurityMeasure.GINI));
      }

    System.out.println(db[0].isEqual(db[0]));
    System.out.println(db[0].isEqual(db[1]));
    System.out.println(db[0].getSize());

    db[nCols-1].print();
    db[nCols-2].print();
    db[nCols-1].set(db[nCols-2]);
    db[nCols-1].print();
    db[nCols-2].print();

    for (int i = 0; i < nRows; i++)
      System.out.print(db[0].get(i) + " ");

    System.out.println();
    System.out.println(db[0].getClassCard(1));
    db[0].setClassFitness(1, 0.5);
    System.out.println(db[0].getClassFitness(1));

    db[0].printClassFitness();
    db[0].setFitness(0.56);
    System.out.println(db[0].getFitness());

    for (int i = 0; i < nCols; i++)
      db[i].print();
    Hashtable[] intersectMap = new Hashtable[nCols];
    for (int i = 0; i < nCols; i++)
      intersectMap[i] = new Hashtable();
    computeIntersections(db[0], db, nCols, intersectMap);
    printIntersections(intersectMap, nCols);

    Hashtable[][] intersectMap1 = new Hashtable[nCols][nCols];
    for (int i = 0; i < nCols; i++)
      for (int j = 0; j < nCols; j++)
	intersectMap1[i][j] = new Hashtable();

    computeIntersections(db, nCols, db, nCols, intersectMap1);
    for (int i = 0; i < nCols; i++)
      {
	System.out.println("Column " + i + " with rest of the columns");
	printIntersections(intersectMap1[i], nCols);
      }

    System.out.println("H(db[0]^db[1]) = " + db[0].entropyIntersect(db[1], 
								    ImpurityMeasure.GINI));

    Vector v = new Vector(2);
    computeInfoIntersections(db, nCols, ImpurityMeasure.GINI, v);
    System.out.println("Entropy of all columns intersected = " 
		       + (Double)v.get(0) + " number of classes " 
		       + (Integer)v.get(1));

    double[] wTargetCondOnDB = new double[nCols];
    double[] wDBCondOnTarget = new double[nCols];
    double[] weight = new double[nCols];

    double targetEntr = estimateWeights(db, nCols, 0.4,
					ImpurityMeasure.GINI,
					wTargetCondOnDB, wDBCondOnTarget,
					weight, rand);

    db[0].computeFitness(intersectMap, db, nCols, ImpurityMeasure.GINI,
			 Global.FM_NORM_W, wTargetCondOnDB, wDBCondOnTarget,
			 weight);

    for (int i = 0; i < nCols; i++)
      System.out.println(i + " " + wTargetCondOnDB[i] + " " 
			 + wDBCondOnTarget[i] + " " + weight[i]);

    System.out.println(db[0].getFitness());
    db[0].printClassFitness();

    db[0].computeFitness(db, nCols, ImpurityMeasure.GINI, Global.FM_NORM_W,
			 wTargetCondOnDB, wDBCondOnTarget, weight);
    
    System.out.println(db[0].getFitness());
    db[0].printClassFitness();

    db[0].printClassCardinalities();

    System.out.println("Sym diff db[0] db[0] = " + db[0].distSymDiff(db[0]));
    System.out.println("Sym diff db[0] db[1] = " + db[0].distSymDiff(db[1]));
    System.out.println("Sym diff db[0] all other db = " 
		       + db[0].sumDistSymDiff(db, nCols));
		       
    double[] silhouettes = new double[nCols];
    int[] neighbors = new int[nCols];
    db[0].computeSilhouettes(silhouettes, neighbors, db, nCols);

    for (int i = 0; i < nCols; i++)
      System.out.println(silhouettes[i] + " " + neighbors[i]);

    db[0].plotSilhouettes(silhouettes, neighbors);

    db[0].printInfo(db, nCols, wTargetCondOnDB, wDBCondOnTarget, weight,
		    ImpurityMeasure.GINI, Global.FM_NORM_W,
		    "Test Partition");

    db[0].printAM();
    db[1].printAM();
    db[0].print();
    db[1].print();
    db[0].getClassifRate(db[1]);
  }
}