package util.jgp.algorithm;

import util.jgp.interfaces.QuickSortable;
import util.jgp.interfaces.RandomAccessable;
import util.jgp.predicate.BinaryPredicate;

public class Sorter {
    
    public static void swap(QuickSortable v, int i, int j) {
	Object tmp = v.getElementAt(i);
	v.setElementAt(i, v.getElementAt(j));
	v.setElementAt(j, tmp);
    }
    
    public static void quickSort(QuickSortable v, BinaryPredicate lessThan, int first, int last) {
	if (first >= last)
	    return;
	
	int i = first;
	int j = last;
	Object mid = v.getElementAt(first);
	
	do 
	    {
		while (lessThan.execute(v.getElementAt(i), mid))
		    ++i;
		while (lessThan.execute(mid, v.getElementAt(j)))
		    --j;
		if (i <= j)
		    swap(v, i++, j--);
	    }
	while (i <= j);
	quickSort(v, lessThan, first, j);
	quickSort(v, lessThan, i, last);
    }
    
    public static void quickSort(QuickSortable v, BinaryPredicate lessThan) {
	quickSort(v, lessThan, 0, v.getSize() - 1);
    }
    
    public static void orderedInsertion(RandomAccessable v, BinaryPredicate lessThan, int first, int last, Object obj) {

	int i;

	for (i = first; i < last; ++i)
	    if (lessThan.execute(obj, v.getElementAt(i))) {
		
		int from = last - 1;
		int to   = last;
		while (to > i)
		    v.setElementAt(to--, v.getElementAt(from--));
		
		break;
	    }

	v.setElementAt(i, obj);
    }


    /*
       first              last 
       |                  |
      [....................]
                |
                i
                |
      [..........]  
       |        |
       first    last
      
     */

    public static void insertionSort(RandomAccessable v, BinaryPredicate lessThan, int first, int last) {
	for (int i = first; i <= last; ++i)
	    orderedInsertion(v, lessThan, first, i, v.getElementAt(i));
    }

    public static void insertionSort(RandomAccessable v, BinaryPredicate lessThan) {
	insertionSort(v, lessThan, 0, v.getSize() - 1);
    }
}