/*
  SelectionMethods.java

  Definition of the class SelectionMethods which implements 
  various selection methods
  
  (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.*;

/**
 * SelectionMethods
 *
 * @version 	1.0
 * @author	Dana Cristofor
 */
public class SelectionMethods
{
  /** places in the <code>sample</code> array, <code>sampleSize</code>
   * indices of the elements in <code>values</code> that contain the
   * best values corresponding to an ascending order if
   * <code>order</code> is 1 or to a descending order otherwise */
  static public void selectBest(double[] values, int valuesSize, int order, 
			 int[] sample, int sampleSize)
  {
    int[] sort = new int[valuesSize];
    
    for (int i = 0; i < valuesSize; i++)
      sort[i] = i;
    
    qsort(sort, 0, valuesSize - 1, values, order);
    
    for (int i = 0; i < sampleSize; i++)
      sample[i] = sort[i];
  }

  /** sorts the array <code>v</code> in ascending order of the
   * <code>values</code> if order is 1, descending order otherwise */
  static private void qsort(int[] v, int left, int right, 
		    double[] values, int order) 
  { 
    if (left >= right) return;

    int p = left;
    swap(v, left, (left + right)/2);
    for (int i = left + 1; i <= right; i++)
      {
	double diff = values[v[i]] - values[v[left]];
	if ((order == 1 ? diff < 0 : diff > 0))
	  swap(v, ++p, i);
      }
    swap(v, left, p);
    qsort(v, left, p - 1, values, order);
    qsort(v, p + 1, right, values, order);
  }

  
  /** swaps elements <code>i</code> and <code>j</code> in the array
   * <code>v</code> */
  static private void swap(int[]  v, int i, int j)
  {
    int t = v[i];
    v[i] = v[j];
    v[j] = t;
  }

  
  /** selects <code>n</code> integers with uniform probability,
   * between 0 and <code>N - 1</code> and places the selected values
   * in the field <code>sample</code> */
  static public void selectUnif(int N, int[] sample, int n, Random rand)
  {
    int t = 0; // how many we have seen
    int m = 0;  // how many we have selected
    int i = 0;
    while (true)
      {
	// [Generate U]
	double U = rand.nextDouble();

	// [Test]
	if ((N - t) * U >= n - m)
	  {
	    // [Skip]
	    t = t + 1;
	  }
	else
	  {
	    // [Select]
	    // we need values between 0 and N-1
	    
	    // in the original algorithm was sample[i++] = t+1
	    // we want sample[i] between 0 and N-1
	    sample[i++] = t;
	    m = m + 1;
	    t = t + 1;
	    
	    if (m < n)
	      ;
	    else // sample complete !
	      break;
	  }
      }
  }

  
  /** selects <code>n</code> integers between 0 and <code>N-1</code>
   * based on their probabilities; places the selected integers in
   * <code>sample</code>; probabilities should be cumulative
   * probabilities */
  static public void selectProb(int N, double[] probabilities, 
				int[] sample, int n, Random rand)
  {
    for (int j = 0; j < n; j++)
      { 
	double val = rand.nextDouble();
      
	// do a binary search for the location i such that
	// probabilities[i - 1] < val <= probabilities[i]
	int i = 0;
	int left = 0;
	int right = N - 1;
	while (right >= left)
	  {
	    int middle = (left + right) / 2;
	    if (val - probabilities[middle] < 0.0)
	      right = middle - 1;
	    else if (val - probabilities[middle] > 0.0)
	      left = middle + 1;
	    else
	      {
		i = middle;
		break;
	      }
	  }
	
	if (right < left)
	  i = left;
	
	// in the case there were neighboring 
	// items with probability 0
	while (i > 0 && probabilities[i - 1] == val)
	  i--;
	
	sample[j] = i;
      }
  }
}