# Selects random items from a list, preferring least recently used ones closest to some criterion
#
# This is useful if there is a moderately-sized set of randomized options
# (like idle animations, footstep or breathing sounds) and you want to select
# one from the set and bias towards an option that was not used recently and
# is close to some criterion (i.e. anger, speed, exhaustion with the previous
# example cases).
#
# This class does not store the items themselves, but rather their rating
# on a user-defined scale. It returns indices for a user-kept item list.

# -------------------------------------------------------------------------------------------------

# Ratings of the items from which the selector should pick
var ratings = []

# Sorted indices for the items to match their closeness to the desired rating
# @remarks
#   Always sorted using a stable sort so indices pointing to items with the same
#   rating can be sub-sorted for least-recently-used ones
var indices = []

# -------------------------------------------------------------------------------------------------

# Adds an item (by its rating, the item itself isn't required by the selector)
# @param  rating   Rating of the item (user-defined scalar than can mean anything)
# @remarks
#   The random item picking method tries to avoid returning the same index
#   multiple times in a row, but this only works if multiple alternative items
#   with an identical rating exist. So it's a good idea to quantize ratings.
func Append(var rating):
	self.indices.append(self.indices.size())
	self.ratings.append(rating)

# -------------------------------------------------------------------------------------------------

# Appends multiple items to the selector
# @param  ratings  Array containing the ratings that will be appended
func AppendMultiple(var ratings):
	var count = ratings.size()
	var index = 0
	while index < count:
		Append(ratings[index])
		index += 1

# -------------------------------------------------------------------------------------------------

# Selects a random item with a high likelihood to have the desired rating
# @param  rating  Rating the picked item should preferably have
# @returns The index of the picked item
# @remarks
#   Has a high likelihood of picking items that have the same or close ratings
#   to the requested rating. Reduces likelihood of returning the same index
#   twice if multiple items with identical rating exist.
func Pick(var rating):
	sortIndicesByRating(rating)
	var randomIndicesIndex = biasedRandomInt(self.indices.size())
	moveBack(randomIndicesIndex)
	return self.indices[randomIndicesIndex]

# -------------------------------------------------------------------------------------------------

# Move an index in the indices list to the back of all indices for its rating
# @param  indicesIndex  Index of the index in the indices list
# @remarks
#   If there are multiple identical ratings, the specified index entry will be
#   moved down until it is the last index pointing to that rating. The effect
#   is that the specified entry is less likely to be selected if the selector
#   picks an entry for the same rating again.
func moveBack(var indicesIndex):
	var thisRating = self.ratings[self.indices[indicesIndex]]
	var count = self.indices.size()

	# Assumes that the indices are ordered by the ratings they point to
	# (which is always the case after sortIndicesByRating() has been called once)
	indicesIndex += 1
	while indicesIndex < count:
		if self.ratings[self.indices[indicesIndex]] == thisRating:
			var temp = self.indices[indicesIndex - 1]
			self.indices[indicesIndex - 1] = self.indices[indicesIndex]
			self.indices[indicesIndex] = temp
		
		indicesIndex += 1

# -------------------------------------------------------------------------------------------------

# Sorts the indices by the rating of the item they point at
# @param  rating  Rating that should be closest to the beginning
# @remarks
#   Uses a stable sort (bubble sort in this case) to shift items so they are in
#   order of distance from the desired rating
func sortIndicesByRating(var rating):
	var firstIndex = 0
	var lastIndex = self.indices.size() - 1
	var lastSwapIndex = 0

	# Move items that are further from the optimal rating to the end
	while firstIndex < lastIndex:
		var thisDistance = abs(rating - self.ratings[self.indices[firstIndex]])
		var nextDistance = abs(rating - self.ratings[self.indices[firstIndex + 1]])

		if thisDistance > nextDistance:
			var temp = self.indices[firstIndex]
			self.indices[firstIndex] = self.indices[firstIndex + 1]
			self.indices[firstIndex + 1] = temp
			lastSwapIndex = firstIndex

		firstIndex += 1
		if firstIndex >= lastIndex:
			lastIndex = lastSwapIndex
			lastSwapIndex = 0
			firstIndex = 0

# -------------------------------------------------------------------------------------------------

# Debug helper that prints the ratings in the order indicated by the index list
func debugPrintRatings():
	var index = 0
	var count = self.indices.size()
	while index < count:
		print("Index %d: %.3f" % [ index, self.ratings[self.indices[index]] ])
		index += 1

# -------------------------------------------------------------------------------------------------

# Returns a random integer up to (but not including) the specified maximum value
# @param  maxExclusive  Maximum value below which the returned random integer will be
# @returns A random integer that is less that the specified maximum value
# @remarks
#   Uses a custom selection curve where samples further from the optimum rating
#   are increasingly unlikely to be picked.
static func biasedRandomInt(var maxExclusive):
	var randomValue = pow(randf(), 2.0) * 0.667 # Bias towards 0.0
	return int(randomValue * maxExclusive)
	#return int(min(randomValue * maxExclusive, maxExclusive - 1))