package pattern.strategy.sort;

/**
 * 策略模式:Strategy Pattern
 *
 * 排序算法策略
 *
 * @version 2009-05-22
 * @author Winty (wintys@gmail.com) http://www.blogjava.net/wintys
 *
 */
public class SortStrategyTest {
    public static void main(String[] args) {
        Sorter<?> sorter;
            
        Integer[] data = new Integer[]{548,85,984,3,2,44,99};
        sorter = new Sorter<Integer>(data , "QuickSort");
        sorter.printArray();
        sorter.sort();
        sorter.printArray();
        
        String[] strs = new String[]{"B","C","D","A","X","F","E"};
        sorter = new Sorter<String>(strs , "InsertionSort");
        sorter.printArray();
        sorter.sort();
        sorter.printArray();        
    }
}

class Sorter<T extends Comparable<T>>{
    private T[] data;
    private SortStrategy<T> strategy;
    
    @SuppressWarnings("unchecked")
    public Sorter(T[] data , String sortStrategy){
        this.data = data;
        
        //利用反射动态加载策略类
        String pack = this.getClass().getPackage().getName();
        pack += ".";
        try {

            Class<?> cl = Class.forName(pack + sortStrategy);
            strategy = (SortStrategy<T>) cl.newInstance();//unchecked
        } catch (InstantiationException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }
    }
    
    public void sort(){
        strategy.sort(data);
    }
    
    public void printArray(){
        for(int i=0;i<data.length;i++){
            System.out.print(""+data[i]+" ");
        }
        System.out.println("");
    }
}

/**
 * 抽象排序算法类
 * @author Winty
 *
 * @param <T> 实现了Comparable<T>接口的类
 */
abstract class SortStrategy<T extends Comparable<T>>{
    public abstract void sort(T[] data);
}

/**
 * 插入排序
 * @author Winty
 */
class InsertionSort<T extends Comparable<T>> extends SortStrategy<T>{

    @Override
    public void sort(T[] data) {
        int len;
        T temp;
        len=data.length;

        for(int i=1;i<len;i++){
            int k;
            k=0;
            temp=data[i];
            for(int j=i-1;j>=0;j--){
                k=i;
                if(data[j].compareTo(temp) > 0){
                    data[j+1]=data[j];
                    k=j;
                }
                else if(data[j].compareTo(temp) < 0){
                    k=j+1;
                    break;
                }
            }
            data[k]=temp;
        }    
    }    
}

/**
 * 快速排序
 * @author Winty
 */
class QuickSort<T extends Comparable<T>> extends SortStrategy<T>{

    @Override
    public void sort(T[] data) {
        quick(data , 0 , data.length - 1);        
    }

    private void quick(T[] data , int p , int r){
        int q;

        if (p < r){
            q = partition(data , p , r);
            quick(data , p , q - 1);
            quick(data , q + 1 , r);
        }
    }

    private int partition(T[] data , int p ,int r){
        int i;
        T pivot , temp;
        
        i = p - 1;
        pivot = data[r];

        for(int j = p; j <= r - 1;j++){
            if(data[j].compareTo(pivot) < 0){
                i++;
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        temp = data[i + 1];
        data[i + 1] = data[r];
        data[r] = temp;

        return i + 1;
    }
}