package util.jgp.algorithm;

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

public class QuickSorter {

    static final int THRESHOLD = 50;

    private RandomAccessable vec      = null;
    private BinaryPredicate  lessThan = null;
    private InsertionSorter  sorter   = null;

    public QuickSorter(RandomAccessable v, BinaryPredicate less) {
	vec      = v;
	lessThan = less;
	sorter   = new InsertionSorter(v, less);
    }

    public void sort(int first, int last) {

	if (Math.abs(last - first) < THRESHOLD) {
	    sorter.sort(first, last);
	    return;
	}

	int i = first;
	int j = last;
	Object mid = vec.getElementAt(first);

	do 
	    {
		while (lessThan.execute(vec.getElementAt(i), mid))
		    ++i;
		while (lessThan.execute(mid, vec.getElementAt(j)))
		    --j;
		if (i <= j) {
		    Object tmp = vec.getElementAt(i);
		    vec.setElementAt(i, vec.getElementAt(j));
		    vec.setElementAt(j, tmp);
		    ++i;
		    --j;
		}
	    }
	while (i <= j);
	if (first < j)
	    sort(first, j);
	if (i < last) 
	    sort(i, last);

    }

    public void sort() {
	int last = vec.getSize() - 1;
	if (0 < last)
	    sort(0, last);
    }
}