BatchSort.java

/*
 * Class:        BatchSort
 * Description:  performs a batch sort on the arrays
 * Environment:  Java
 * Software:     SSJ 
 * Copyright (C) 2001  Pierre L'Ecuyer and Universite de Montreal
 * Organization: DIRO, Universite de Montreal
 * @author       
 * @since
 
 * SSJ is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License (GPL) as published by the
 * Free Software Foundation, either version 3 of the License, or
 * any later version.
 
 * SSJ 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.
 
 * A copy of the GNU General Public License is available at
   <a href="http://www.gnu.org/licenses">GPL licence site</a>.
 */
package umontreal.ssj.util.multidimsort;
 
import java.util.Arrays;

 
public class BatchSort<T extends MultiDimComparable<? super T>> implements MultiDimSortComparable<T> {
 
   int dimension; // Number of coordinates.
   boolean useExponents; // True if we use proportion exponents.
   int[] batchNumbers; // Number of batches n_j for each dimension.
   double[] batchExponents; // The alpha_j.
   int batchProduct = 1; // Product p of numbers in batchNumbers.
   int nSaved = 0; // Number n of objects last time sort was called.

   public BatchSort(int[] batchNumbers) {
      if (batchNumbers == null)
         throw new NullPointerException("batchNumbers is null");
      useExponents = false;
      this.batchNumbers = batchNumbers;
      dimension = batchNumbers.length;
      batchProduct = 1;
      for (int i = 0; i < batchNumbers.length; ++i)
         batchProduct *= batchNumbers[i];
   }

   public BatchSort(double[] batchExponents) {
      if (batchExponents == null)
         throw new NullPointerException("batchExponents is null");
      this.batchExponents = batchExponents;
      useExponents = true;
      dimension = batchExponents.length;
      batchNumbers = new int[dimension];
      double sum = 0.0;
      for (int j = 0; j < dimension; ++j)
         sum += batchExponents[j];
      if (Math.abs(sum - 1) > 1.0e-10)
         throw new IllegalArgumentException("Sum of batchExponents not equal to 1");
   }

   public void setBatchNumbers(int n) {
      if (batchExponents == null)
         throw new NullPointerException("batchExponents is null");
      if (useExponents == false)
         throw new IllegalArgumentException("method allowed only when using proportion exponents");
      nSaved = n;
      batchProduct = 1; // Product of batch numbers.
      for (int dim = 0; dim < dimension; ++dim) {
         batchNumbers[dim] = (int) Math.ceil(Math.pow(n, batchExponents[dim])); // Round up.
         batchProduct *= batchNumbers[dim];
      }
   }

   public void setBatchExponents(double[] batchExponents) {
      if (batchExponents == null)
         throw new NullPointerException("batchExponents is null");
      if (batchExponents.length != dimension)
         throw new IllegalArgumentException("batchExponents has wrong dimension");
      nSaved = 0;
      useExponents = true;
      this.batchExponents = batchExponents;
      double sumExponents = 0.0; // Sum of exponents.
      for (int dim = 0; dim < dimension; ++dim) {
         sumExponents += batchExponents[dim];
      }
      if (Math.abs(sumExponents - 1.0) > 1.0e-10)
         throw new IllegalArgumentException("Sum of batchExponents not equal to 1");
   }

   public int[] getBatchNumbers() {
      return batchNumbers;
   }

   public int getBatchProduct() {
      return batchProduct;
   }

   public double[] getBatchExponents() {
      return batchExponents;
   }
 
   public int dimension() {
      return dimension;
   }

   public void sort(T[] a, int iMin, int iMax) {
      if (iMin + 1 == iMax)
         return;
      if (useExponents && (nSaved != iMax - iMin))
         setBatchNumbers(iMax - iMin);
      int i1, i2;
      int bsize = iMax - iMin; // Current batch size. At level 0: single batch.
      for (int j = 0; (j < dimension) && (bsize > 1); ++j) {
         MultiDimComparator<T> compar = new MultiDimComparator<T>(j);
         // Sort all the batches (entire array) according to coordinate j.
         if (batchNumbers[j] == 1)
            continue; // Can skip the sort for this dim j.
         // if (bsize <= 1) break;
         i1 = iMin;
         while (i1 < iMax) {
            i2 = i1 + bsize;
            if (i2 > iMax)
               i2 = iMax;
            Arrays.sort(a, i1, i2, compar);
            i1 += bsize;
         }
         bsize = (int) Math.ceil(bsize / batchNumbers[j]); // New batch size.
      }
   }

   public void sort(T[] a) {
      sort(a, 0, a.length);
   }

   public void sort(double[][] a, int iMin, int iMax) {
      if (iMin + 1 == iMax)
         return;
      if (useExponents && (nSaved != iMax - iMin))
         setBatchNumbers(iMax - iMin);
      int i1, i2;
      int bsize = iMax - iMin; // Current batch size. At level 0: single batch.
      for (int j = 0; (j < dimension) && (bsize > 1); ++j) {
         DoubleArrayComparator compar = new DoubleArrayComparator(j);
         // Sort all the batches (entire array) according to coordinate j.
         if (batchNumbers[j] == 1)
            continue; // Can skip the sort for this dim j.
         i1 = iMin;
         while (i1 < iMax) {
            i2 = i1 + bsize;
            if (i2 > iMax)
               i2 = iMax;
            Arrays.sort(a, i1, i2, compar);
            i1 += bsize;
         }
         bsize = (int) Math.ceil(bsize / batchNumbers[j]); // New batch size.
      }
   }

   public void sort(double[][] a) {
      sort(a, 0, a.length);
   }
 
}