HilbertCurveSort.java

/*
 * Class:        HilbertCurveSort
 * Description:  Sorts d-dimensional points in [0,1)^d based on Hilbert curve.
 * Environment:  Java
 * Software:     SSJ 
 * Copyright (C) 2014  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>.
 */
 
/* IMPORTANT NOTE:
* Much of this code has been taken (with adaptations) from  
*     the hilbert.c  code  
* Author:   Spencer W. Thomas
*       EECS Dept.
*       University of Michigan
* Date: Thu Feb  7 1991
* Copyright (c) 1991, University of Michigan
*/
package umontreal.ssj.util.multidimsort;
 
import java.util.Comparator;
import java.util.Arrays;

public class HilbertCurveSort implements MultiDimSort01<MultiDim01> {
 
   int dimension; // Dimension d of the points used for the sort.
   long[][] indexForSort; // This is the index computed by the last Hilbert sort,
   // sorted by the second coordinate. The order of the first coordinates
   // gives the permutation made by that sort.
   // This index is recomputed each time we sort.
   HilbertCurveMap hcMap; // The map used for sorting

   public HilbertCurveSort(int d, int m) {
      dimension = d;
      hcMap = new HilbertCurveMap(d, m);
   }

   public HilbertCurveSort(HilbertCurveMap map) {
      this.hcMap = map;
      this.dimension = map.dimension();
   }

   public void sort(MultiDim01[] a, int iMin, int iMax) {
      // Copy the (0,1)^d transformations of the states in array b.
      double b[][] = new double[iMax][dimension];
      for (int i = iMin; i < iMax; ++i)
         b[i] = a[i].getPoint();
      // Sort this array b by Hilbert sort. The index
      // indexForSort will contain the permutation made by that sort.
      sort(b, iMin, iMax);
      // Now use indexForSort to sort a.
      // We do not want to clone all the objects in a,
      // but only the array of pointers.
      MultiDim01[] aclone = a.clone(); // new Object[iMax];
      for (int i = iMin; i < iMax; ++i)
         a[i] = aclone[(int) indexForSort[i][0]];
   }

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

   public void sort(double[][] a, int iMin, int iMax) {
      if (iMin + 1 == iMax)
         return;
      indexForSort = new long[iMax][2]; // Index used for sort.
      int[] icoord = new int[dimension]; // To store integer coordinates.
      for (int i = 0; i < a.length; ++i) {
         // Transform to integer coordinates.
         hcMap.pointToCoordinates(a[i], icoord);
         indexForSort[i][0] = i;
         indexForSort[i][1] = hcMap.coordinatesToIndex(icoord); // Hilbert index of this point.
      }
      // Sort the index based on the positions on the Hilbert curve
      sortIndexOfLong2(indexForSort, iMin, iMax);
      // Now use the sorted index to sort a.
      double[][] aclone = a.clone(); // Save copy of a before the sort.
      for (int i = iMin; i < iMax; ++i) {
         a[i] = aclone[(int) indexForSort[i][0]];
      }
   }
 
   public void sort(double[][] a) {
      sort(a, 0, a.length);
   }

   public long[][] getIndexAfterSort() {
      return indexForSort;
   }

   public int dimension() {
      return dimension;
   }

   public HilbertCurveMap getHilbertCurveMap() {
      return hcMap;
   }
 
   // Compares two arrays of long according to their second coordinate.
   // This is used to sort an index of type long[][2] by the second coordinate.
   // The permutation can be recovered in the first coordinate.

   public static class LongIndexComparator2 implements Comparator<long[]> {
      public int compare(long[] p1, long[] p2) {
         if (p1[1] > p2[1])
            return 1;
         else if (p1[1] < p2[1])
            return -1;
         else
            return 0;
      }
   }

   public static void sortIndexOfLong2(long[][] index, int iMin, int iMax) {
      // if (iMin==(iMax-1)) return;
      Arrays.sort(index, iMin, iMax, new LongIndexComparator2());
   }
 
}