package webutility

type QSortDirection int

const (
	QSortAscending QSortDirection = iota
	QSortDescending
)

// 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 {
	swap := 0
	// -1 -> i > j
	//  1 -> i < j
	if dir == QSortDescending {
		swap = -1
	} else {
		swap = 1
	}

	i := low - 1
	for j := low; j <= high-1; j++ {
		if que.Compare(j, high) == swap {
			i++
			que.Swap(i, j)
		}
		continue
	}
	que.Swap(i+1, high)
	return i + 1
}