/** File: Sort.java */

/**
 * Class Sort contains utility sort functions.
 * <PRE>
 * <B>List of Methods</B><BR>
 * ===================
 * quickSort(int[]) - quicksort a list of integers.
 * bubbleSort(String[]) - bubble sort a list of Strings.
 * bubbleSortIndex(String[]) - bubble sort a String[] and return sort index.
 * bubbleSortIndex(double[]) - bubble sort a double[] and return sort index.
 * bubbleSortIndex(float[]) - bubble sort a float[] and return sort index.
 * bubbleSortIndex(int[]) - bubble sort a int[] and return sort index.
 *</PRE>
 *<P> 
 * This code is available at the HTMLtools project on SourceForge at
 * <A HREF="http://htmltools.sourceforge.net/">http://htmltools.sourceforge.net/</A>
 * under the "Common Public License Version 1.0" 
 * <A HREF="http://www.opensource.org/licenses/cpl1.0.php">
 * http://www.opensource.org/licenses/cpl1.0.php</A>.<P></P>
 * <P>
 * It was derived and refactored from the open source
 * MAExplorer (http://maexplorer.sourceforge.net/), and
 * Open2Dprot (http://Open2Dprot.sourceforge.net/) Table modules.
 * <P>
 * $Date: 2009/067/03 11:45:56 $ $Revision: 1.28 $
 * <BR> 
 * Copyright 2008, 2009 by Peter Lemkin 
 * E-Mail: lemkin@users.sourceforge.net 
 * <A HREF="http://lemkingroup.com/">http://lemkingroup.com/</A>
 * <BR>
 */

public class Sort
{    
    
  /**
   * Sort() - Constructor
   */
  public Sort()
  { /* Sort */
  } /* Sort */  
       
  
  /**
   * quickSort() - sort the int[] array.
   * Based on QuickSort method by James Gosling from Sun's SortDemo applet
   * @param a array of data to sort
   * @param lo0 lower bound of array
   * @param hi0 uppper bound of array
   */
  public static void quickSort(int a[], int lo0, int hi0)
  { /* quickSort */
    int
      lo= lo0,
      hi= hi0,
      mid,
      t;
    
    if (hi0 > lo0)
    {  /* need to sort */
      mid= a[(lo0 + hi0)/2];
      while(lo <= hi)
      { /* check if swap within range */
        while((lo < hi0) && (a[lo] < mid) )
          ++lo;
        while((hi > lo0) && (a[hi] > mid) )
          --hi;
        if(lo <= hi)
        {
          t= a[lo];
          a[lo]= a[hi];
          a[hi]= t;
          ++lo;
          --hi;
        }
      } /* check if swap within range */
      
      if(lo0 < hi)
        quickSort(a, lo0, hi);
      if(lo < hi0)
        quickSort(a, lo, hi0);
    } /* need to sort */
  } /* quickSort */
    
  
  /**
   * bubbleSort() - Sort String array via bubble sort w/len
   * @param data array of data to be sorted
   * @param len size of subarray array of data to be sorted [0:len-1]
   * @return the new sorted string[] array
   */
  public static String[] bubbleSort(String data[], int len)
  { /* bubbleSort */
    if(data==null || len==0)
      return(data);
    
    String
      dataUCJM1,
      dataUCJ,
      tempStr,
      dataUC[]= new String[len];
    int lenMinus1= len-1;
    
    /* convert temp array to upper case  */
    for (int i= 0; i < len; i++)
      dataUC[i]= data[i].toUpperCase();
    
    for(int i= 0; i < len; i++)
    {
      for(int j= lenMinus1; j > i; j--)
      {
        dataUCJM1= dataUC[j-1];
        dataUCJ= dataUC[j];
        
        if(dataUCJM1.compareTo(dataUCJ) > 0)
        { /* exchange */
          tempStr= data[j-1];  /* parallel sort the data */
          data[j-1]= data[j];
          data[j]= tempStr;
          
          dataUC[j-1]= dataUCJ;
          dataUC[j]= dataUCJM1;
        }
      }
    }
    
    return(data);
  } /* bubbleSort */ 
 
  
  /**
   * bubbleSortIndex() - sort copy of String[0:len-1] data with bubble sort,
   * return index[].
   * Do NOT actually sort the original data[].
   * @param data array of data to be sorted
   * @param len size of subarray array of data to be sorted [0:len-1]
   * @param ascending sort if true
   * @return the index[] of the sorted data
   */
  public static int[] bubbleSortIndex(String data[], int len,
                                      boolean ascending)
  { /* bubbleSortIndex */
    if(data==null || len==0)
      return(null);
    
    String
      dataUCJM1,
      dataUCJ,
      dataUC[]= new String[len];
    int
      oldJm1,
      index[]= new int[len],
      j,
      strCmp,
      lenMinus1= (len-1);
    
    /* convert temp array to upper case  */
    for (int i= 0; i < len; i++)
    {
      dataUC[i]= data[i].toUpperCase();
      index[i]= i;
    }
    
    /* Do the sort */
    for(int i= 0; i < len; i++)
    {
      for(j= lenMinus1; j > i; j--)
      {
        dataUCJM1= dataUC[j-1];
        dataUCJ= dataUC[j];
        strCmp= dataUCJM1.compareTo(dataUCJ);
        if((ascending && strCmp > 0) || (!ascending && strCmp < 0))
        { /* exchange */
          oldJm1= index[j-1];  /* parallel sort the index and dataUC */
          index[j-1]= index[j];
          index[j]= oldJm1;
          
          dataUC[j-1]= dataUCJ;
          dataUC[j]= dataUCJM1;
        }
      }
    }
    
    return(index);
  } /* bubbleSortIndex */

      
  /**
   * bubbleSortIndex() - sort copy of double[0:len-1] data with bubble sort,
   * return index[].
   * Do NOT actually sort the original data[].
   * @param data array of data to be sorted
   * @param len size of subarray array of data to be sorted [0:len-1]
   * @param ascending sort if true
   * @return the index[] of the sorted data
   */
  public static int[] bubbleSortIndex(double data[], int len,
                                      boolean ascending)
  { /* bubbleSortIndex */
    if(data==null || len==0)
      return(null);
    
    double
      dataJM1,
      dataJ,
      dataT[]= new double[len];
    int
      oldJm1,
      index[]= new int[len],
      j,
      lenMinus1= (len-1);
    
    /* copy data to local tmp array since will change the order */
    for (int i= 0; i < len; i++)
    {
      dataT[i]= data[i];
      index[i]= i;
    }
    
    /* Do the sort */
    for(int i= 0; i < len; i++)
    {
      for(j= lenMinus1; j > i; j--)
      {
        dataJM1= dataT[j-1];
        dataJ= dataT[j];
        if((ascending && dataJM1>dataJ) ||
           (!ascending && dataJM1<dataJ))
        { /* exchange */
          oldJm1= index[j-1];  /* parallel sort the index and dataUC */
          index[j-1]= index[j];
          index[j]= oldJm1;
          
          dataT[j-1]= dataJ;
          dataT[j]= dataJM1;
        }
      }
    }
    
    return(index);
  } /* bubbleSortIndex */ 

  
  /**
   * bubbleSortIndex() - sort copy of float[0:len-1] data with bubble sort,
   * return index[].
   * Do NOT actually sort the original data[].
   * @param data array of data to be sorted
   * @param len size of subarray array of data to be sorted [0:len-1]
   * @param ascending sort if true
   * @return the index[] of the sorted data
   */
  public static int[] bubbleSortIndex(float data[], int len,
                                      boolean ascending)
  { /* bubbleSortIndex */
    if(data==null || len==0)
      return(null);
    
    float
      dataJM1,
      dataJ,
      dataT[]= new float[len];
    int
      oldJm1,
      index[]= new int[len],
      j,
      lenMinus1= (len-1);
    
    /* copy data to local tmp array since will change the order */
    for (int i= 0; i < len; i++)
    {
      dataT[i]= data[i];
      index[i]= i;
    }
    
    /* Do the sort */
    for(int i= 0; i < len; i++)
    {
      for(j= lenMinus1; j > i; j--)
      {
        dataJM1= dataT[j-1];
        dataJ= dataT[j];
        if((ascending && dataJM1>dataJ) ||
           (!ascending && dataJM1<dataJ))
        { /* exchange */
          oldJm1= index[j-1];  /* parallel sort the index and dataUC */
          index[j-1]= index[j];
          index[j]= oldJm1;
          
          dataT[j-1]= dataJ;
          dataT[j]= dataJM1;
        }
      }
    }
    
    return(index);
  } /* bubbleSortIndex */
    
      
  /**
   * bubbleSortIndex() - sort copy of int[0:len-1] data with bubble sort,
   * return index[].
   * Do NOT actually sort the original data[].
   * @param data array of data to be sorted
   * @param len size of subarray array of data to be sorted [0:len-1]
   * @param ascending sort if true
   * @return the index[] of the sorted data
   */
  public static int[] bubbleSortIndex(int data[], int len,
                                      boolean ascending)
  { /* bubbleSortIndex */
    if(data==null || len==0)
      return(null);
    
    int
      dataJM1,
      dataJ,
      dataT[]= new int[len];
    int
      oldJm1,
      index[]= new int[len],
      j,
      lenMinus1= (len-1);
    
    /* copy data to local tmp array since will change the order */
    for (int i= 0; i < len; i++)
    {
      dataT[i]= data[i];
      index[i]= i;
    }
    
    /* Do the sort */
    for(int i= 0; i < len; i++)
    {
      for(j= lenMinus1; j > i; j--)
      {
        dataJM1= dataT[j-1];
        dataJ= dataT[j];
        if((ascending && dataJM1>dataJ) ||
           (!ascending && dataJM1<dataJ))
        { /* exchange */
          oldJm1= index[j-1];  /* parallel sort the index and dataUC */
          index[j-1]= index[j];
          index[j]= oldJm1;
          
          dataT[j-1]= dataJ;
          dataT[j]= dataJM1;
        }
      }
    }
    
    return(index);
  } /* bubbleSortIndex */
  
    
} /* end of class Sort */