package median

import (
	"bytes"
	"math/rand"
)

func RandomSelectb(A [][]byte, p, r, i int) []byte {
	if p == r {
		return A[p]
	}

	q := RandPartitionb(A, p, r)
	k := q - p + 1

	if k == i {
		return A[q]
	}

	if i < k {
		return RandomSelectb(A, p, q-1, i)
	}

	return RandomSelectb(A, q+1, r, i-k)
}

func RandPartitionb(A [][]byte, p, r int) int {
	i := rand.Intn(r - p + 1)
	A[p+i], A[p] = A[p], A[p+i]

	x := A[p]
	i = p

	for j := p + 1; j <= r; j++ {
		if bytes.Compare(A[j], x) < 1 {
			i++
			A[i], A[j] = A[j], A[i]
		}
	}

	A[i], A[p] = A[p], A[i]

	return i
}

func RandomSelect(A []int, p, r, i int) int {
	if p == r {
		return A[p]
	}

	q := RandPartition(A, p, r)
	k := q - p + 1

	if k == i {
		return A[q]
	}

	if i < k {
		return RandomSelect(A, p, q-1, i)
	}

	return RandomSelect(A, q+1, r, i-k)
}

func RandPartition(A []int, p, r int) int {
	i := rand.Intn(r - p + 1)
	A[p+i], A[p] = A[p], A[p+i]

	x := A[p]
	i = p

	for j := p + 1; j <= r; j++ {
		if A[j] <= x {
			i++
			A[i], A[j] = A[j], A[i]
		}
	}

	A[i], A[p] = A[p], A[i]

	return i
}