package webutility

type QSortDirection int

const (
	QSortAscending  = 0
	QSortDescending = 1
)

// QuickSortable is an interface for quicksorting slices.
type QuickSortable interface {
	Swap(i, j int)
	Compare(i, j int) int
	Len() int
}

// Quicksort quicksorts que.
func Quicksort(que QuickSortable, low, high int, dir QSortDirection) {
	if low >= high {
		return
	}

	if dir != QSortAscending && dir != QSortDescending {
		return
	}

	index := partition(que, low, high, dir)
	Quicksort(que, low, index-1, dir)
	Quicksort(que, index+1, high, dir)
}

func partition(que QuickSortable, low, high int, dir QSortDirection) int {
	i := low - 1
	for j := low; j <= high-1; j++ {
		if dir == QSortAscending {
			if que.Compare(j, high) == -1 {
				i++
				que.Swap(i, j)
			}
		} else if dir == QSortDescending {
			if que.Compare(j, high) == 1 {
				i++
				que.Swap(i, j)
			}
		}
	}
	que.Swap(i+1, high)
	return i + 1
}