/**
 *  @(#) SortStrategy.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

/**
 *  @(#) SortStrategyConst.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

public interface SortStrategyConst {
	public static final String HEAPSORT = "HeapSort";
	public static final String BUBBLESORT = "BubbleSort";
	public static final String INSERTSORT = "InsertSort";
	public static final String MERGESORT = "MergeSort";
	public static final String QUICKSORT = "QuickSort";
	public static final String SELECTSORT = "SelectSort";
	public static final String SHELLSORT = "ShellSort";
	
} 

/**
 *  @(#) SortStrategy.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

public interface SortStrategy extends SortStrategyConst {
   public String getStrategyName();
   public void sort( double[] data );
}

/**
 *  @(#) AbstractSortStrategy.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

public abstract class AbstractSortStrategy 
implements SortStrategy {
   
   protected String strategyName = null;
   
   public AbstractSortStrategy( String strategyName ) {
       this.strategyName = strategyName;
   }
   
   public String getStrategyName( ) {
       return strategyName;
   }
} 

/**
 *  @(#) NullSort.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

public class NullSort extends AbstractSortStrategy
implements SortStrategy {
	public NullSort() {
		super( NullSort.class.getName());
	}
	
	public void sort( double[] data ) {
		// do nothing
	}
} 

/**
 *  @(#) SortHelper.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

public class SortHelper {
   private SortHelper() {
   }
   
   public static void swap( double[] data, 
                            int i, int j ) {
      if ( i < 0 || j < 0 
        || i >= data.length 
        || j >= data.length ) {
           return;
      }
      double temp = data[i];
      data[i] = data[j];
      data[j] = temp;  
   }
   
   public static final double EPSILON = 1e-5;
   public static boolean isSmaller( double db1, 
                                    double db2 ) {
      return ( db2 - db1 > EPSILON); 
   }
   
   public static boolean isGreater( double db1, 
                                    double db2 ) {
      return ( db1 - db2 > EPSILON );
   }
   
   public static boolean isEqual( double db1, 
                                  double db2 ) {
      return ( db1 - db2 < EPSILON && db2 - db1 < EPSILON );
   }
   
   public static boolean isNotEqual( double db1, 
                                     double db2 ) {
      return ( db1 - db2 > EPSILON || db2 - db1 > EPSILON );
   }
   
   public static boolean isSmallerOrEqual( double db1, 
                                           double db2 ) {
      return ( db1 - db2 < EPSILON );
   }
   
   public static boolean isGreaterOrEqual( double db1, 
                                           double db2 ) {
      return ( db2 - db1 < EPSILON );
   }
   
}

/**
 *  @(#)SelectSort.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

public class SelectSort extends AbstractSortStrategy
implements SortStrategy {
	public SelectSort() {
	  super( SelectSort.class.getName());
	}
	
	public void sort( double[] data ) {
	  for ( int i = 0; i < data.length; i++) {
	    int minIndex = i;
	    for ( int j = data.length - 1; j > i; j-- ) {
	      if ( SortHelper.isSmaller( data[j], data[minIndex] )) {
	         minIndex = i;
	      }
	    }
	    SortHelper.swap( data, i, minIndex );
	  }
	}
} 

/**
 *  @(#) InsertSort.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

public class InsertSort extends AbstractSortStrategy
implements SortStrategy {
   public InsertSort() {
      super( InsertSort.class.getName());
   }
   
   public void sort( double[] data ) {
      for ( int i = 0; i < data.length; i++) {
         for ( int j = i; 
               j > 0 && SortHelper.isSmaller( data[j], data[j-1] );
               j--) {
           SortHelper.swap( data, j, j-1 );
        } 
      }
   }
} 

/**
 *  @(#)MergeSort.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

public class MergeSort extends AbstractSortStrategy
implements SortStrategy {
    public MergeSort() {
      super( MergeSort.class.getName());
    }
    
    public void sort( double[] data ) {
      mergesort( data, 0, data.length-1);   
    }
    
    private void mergesort( double[] data, int left, int right ) {
      if ( left < right ) {
        int mid = ( left + right ) / 2;
        mergesort( data, left, mid );
        mergesort( data, mid + 1, right );
        merge( data, left, mid, right );
      }
    }
    
    private void merge(double[] data, int left, int mid, int right ) {
    	int i = left;
    	int j = mid + 1;
    	int k = left;
    	double[] temp = new double[data.length];
    	while ( i <= mid && j <= right ) {
    	   if ( SortHelper.isSmallerOrEqual( data[i], data[j] )) {
    	      temp[k] = data[i];
    	      i++;
    	      k++;
    	   } else {
    	      temp[k] = data[j];
    	      j++;
    	      k++;
    	   }
    	}
    	while ( i <= mid ) {
    	      temp[k] = data[i];
    	      i++;
    	      k++;
    	}
    	while ( j <= right ) {
    	      temp[k] = data[j];
    	      j++;
    	      k++;
    	}
    	for ( i = left; i <= right; i++ ){
    	      data[i] = temp[i];
    	}
    }
} 

/**
 *  @(#) BubbleSort.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

public class BubbleSort extends AbstractSortStrategy
implements SortStrategy {
   public BubbleSort() {
     super( BubbleSort.class.getName());
   }
   
   public void sort( double[] data ) {
     for ( int i = 0; i < data.length; i++){
        for ( int j = data.length-1; j > i; j-- ) {
          if ( SortHelper.isSmaller( data[j], data[j-1] ) ) {
            SortHelper.swap( data, j, j-1 );
          }
        }
     }
   }
} 

/**
 * @(#) HeapSort.java
 * @author quickpoint At HUST
 * @version 1.0 2006-05-24
 */
package edu.hust.sort;

public class HeapSort extends AbstractSortStrategy
implements SortStrategy {
    public HeapSort() {
      super( HeapSort.class.getName());
    }
    
    public void sort( double[] data ) {
      for (int i = (data.length-1) / 2; i > 0; i-- ) {
        adjustHeap( data, i, data.length-1 );
      }
      SortHelper.swap( data, 0, data.length - 1 );
      for (int i = data.length - 1; i > 0; i-- ) {
          adjustHeap( data, 0, i );
          SortHelper.swap( data, 0, i );
        }
     }
     
     private void adjustHeap( double[] data, int left, int right ) {
       double temp = data[left];
       for ( int j = 2 * left; j <= right; j *= 2 ) {
          if ( j < right && SortHelper.isSmaller( data[j], data[j+1] )) j++;

          if ( SortHelper.isGreaterOrEqual( temp, data[j] )) break;
          data[left] = data[j];
          left = j;
       }
       data[left] = temp;
     }   
} 

/**
 *  @(#)QuickSort.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

public class QuickSort extends AbstractSortStrategy 
implements SortStrategy {
    public QuickSort() {
      super( QuickSort.class.getName());
    }
    
    public void sort( double[] data ) {
       quicksort( data, 0, data.length - 1 ); 
    }
    
    public void quicksort( double[] data, int left, int right ) {
       int i = left;
       int j = right;
       double pivot = data[left];
       while ( i < j ) {
          while ( i < j && SortHelper.isSmaller( pivot, data[j] )) j--;
          if ( i < j ) data[i++] = data[j];
          while ( i < j &&SortHelper.isGreater( pivot, data[i])) i++;
          if ( i < j ) data[j--] = data[i];
       }
       data[i] = pivot;
       if ( i - left > 1 ) quicksort( data, left, i - 1 );
       if ( right - j > 1 ) quicksort( data, j+1, right );
    }
    
} 

/**
 *  @(#)ShellSort.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;
 
public class ShellSort extends AbstractSortStrategy
implements SortStrategy {	
	
  public ShellSort() {
     super( ShellSort.class.getName());
  }
  public void sort( double[] data ) {
     for ( int i = data.length / 2; i > 2; i /= 2 ) {
         for (int j = 0; j < i; j++ ) {
           insertSort( data, j, i );
         }
      }
     insertSort( data, 0, 1 );
  }
  private void insertSort( double[] data, int start, int inc ) {
    for ( int i = start + inc; i < data.length; i += inc ) {
      for ( int j = i; j >= inc && SortHelper.isSmaller( data[j], data[j-inc])
;
            j -= inc ) {
         SortHelper.swap( data, j, j - inc );
      }
    }
  }
} 

/**
 *  @(#) SortStrategyFactory.java
 *  @author quickpoint At HUST
 *  @version 1.0 2006-05-24
 */
package edu.hust.sort;

public class SortStrategyFactory {
	private static SortStrategyFactory instance = new SortStrategyFactory();
	
	public static final String PREFIX = "edu.hust.sort.";
	
	public static SortStrategyFactory getInstance() {
		return instance;
	}
	
	private SortStrategyFactory() {
	}
	
	public SortStrategy renderSortStrategyByName( String name ) {
		if ( null == name ) {
			return new NullSort();
		}
		
		if ( !name.startsWith(PREFIX)) {
			name = PREFIX + name;
		}
		
		try {
		  return 
			( SortStrategy ) ( Class.forName( name ).newInstance());
		} catch ( ClassNotFoundException ex ) {
			ex.printStackTrace();
			return new NullSort();
		} catch ( Exception ex ) {
			ex.printStackTrace();
			return new NullSort();
		}
	}
} 


/**
 * @(#) SortMain.java
 * @author quickpoint At HUST
 * @version 1.0 2006-05-24 
 */
package edu.hust.sort;
 
public class SortMain {
  public static void main( String[] args ) {
     double[] data = { 15.0, 23.3, 25.1, 25.3, 22.1, 35.3};
     SortStrategy strategy = SortStrategyFactory.getInstance()
                          .renderSortStrategyByName( SortStrategy.HEAPSORT );

     strategy.sort( data );
     System.out.println( strategy.getStrategyName());
     for ( int i = 0; i < data.length; i++){
        System.out.println( data[i] );
     }   
  }
}