package com.dwave.util;

/*
 *  QuickSort
 *
 *   Copyright (C) 2001  D-Wave Systems Inc.
 *
 *   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
 */

/**
 *  @author Michael Coury
 *  @version 1.0, 05/16/2001
 */

public class QuickSort {
  private static final int DOUBLE = 0,
                           FLOAT = 1,
                           INT = 2,
                           LONG = 3;
  private static double[] doubleArray;
  private static float[] floatArray;
  private static int[] intArray;
  private static long[] longArray;
  private static int mode;
                                                             
  /**
   *
   */
  private QuickSort() {}
         
  /**
   *
   */
  public static synchronized void sortDouble(double[] theArray) {
    mode = DOUBLE;
    doubleArray = theArray;
    quickSort(0, doubleArray.length-1);
  }    
  /**
   *
   */
  public static synchronized void sortInt(int[] theArray) {
    mode = INT;
    intArray = theArray;
    quickSort(0, intArray.length-1);
  }
  /**
   *
   */
  public static synchronized void sortFloat(float[] theArray) {
    mode = FLOAT;
    floatArray = theArray;
    quickSort(0, floatArray.length-1);
  }       
  /**
   *
   */
  public static synchronized void sortLong(long[] theArray) {
    mode = LONG;
    longArray = theArray;
    quickSort(0, longArray.length-1);
  }

  /**
   *
   */
  private static synchronized void quickSort(int left, int right) {
    if(right-left <= 0)
      return;
    double pivot=-1;
    switch(mode) {
      case(DOUBLE):
        pivot = doubleArray[right];
       break;
      case(INT):
        pivot = (double)intArray[right];
       break;
      case(FLOAT):
        pivot = (double)floatArray[right];
       break;  
      case(LONG):
        pivot = (double)longArray[right];
       break;
    }
    int partition = findPartition(left, right, pivot);
    quickSort(left, partition-1);
    quickSort(partition+1, right);
  }
               
  /**
   *
   */
  private static synchronized int findPartition(int left, int right, double pivot) {
    int leftPtr = left-1;
    int rightPtr = right;
    switch(mode) {
      case(DOUBLE):
        while(true) {
          while(doubleArray[++leftPtr] < pivot);
          while(rightPtr > 0 && doubleArray[--rightPtr] > pivot);
          if(leftPtr >= rightPtr)
            break;
          else
            swap(leftPtr, rightPtr);
        }
        swap(leftPtr, right);
       return leftPtr;
      case(INT):
        while(true) {
          while(intArray[++leftPtr] < pivot);
          while(rightPtr > 0 && intArray[--rightPtr] > pivot);
          if(leftPtr >= rightPtr)
            break;
          swap(leftPtr, rightPtr);
        }   
        swap(leftPtr, right);
       return leftPtr;
      case(FLOAT):
        while(true) {
          while(floatArray[++leftPtr] < pivot);
          while(rightPtr > 0 && floatArray[--rightPtr] > pivot);
          if(leftPtr >= rightPtr)
            break;
          swap(leftPtr, rightPtr);
        }
        swap(leftPtr, right);
       return leftPtr;  
      case(LONG):
        while(true) {
          while(longArray[++leftPtr] < pivot);
          while(rightPtr > 0 && longArray[--rightPtr] > pivot);
          if(leftPtr >= rightPtr)
            break;
          swap(leftPtr, rightPtr);
        }
        swap(leftPtr, right);
       return leftPtr;
    }
    return -1;
  }
              
  /**
   *
   */
  private static synchronized void swap(int i1, int i2) {
    switch(mode) {
      case(DOUBLE):
        double dtemp = doubleArray[i1];
        doubleArray[i1] = doubleArray[i2];
        doubleArray[i2] = dtemp;
       break;
      case(INT):
        int itemp = intArray[i1];
        intArray[i1] = intArray[i2];
        intArray[i2] = itemp;
       break;
      case(FLOAT):
        float ftemp = floatArray[i1];
        floatArray[i1] = floatArray[i2];
        floatArray[i2] = ftemp;
       break;   
      case(LONG):
        long ltemp = longArray[i1];
        longArray[i1] = longArray[i2];
        longArray[i2] = ltemp;
       break;
    }
  }
}