# Optimized organization of `Bucketable` instances
class Buckets[G: Game]
	super Turnable[G]

	# Bucket type used in this implementation.
	type BUCKET: HashSet[Bucketable[G]]

	private var next_bucket: nullable BUCKET = null
	private var current_bucket_key = -1

	# Number of `buckets`, default at 100
	#
	# Must be set prior to using any other methods of this class.
	var n_buckets = 100

	private var buckets: Array[BUCKET] =
		[for b in n_buckets.times do new HashSet[Bucketable[G]]] is lazy

	# Stats on delays asked when adding an event with `act_in` and `act_next`
	private var delays = new Counter[Int]

	# Add the Bucketable event `e` at `at_tick`.
	fun add_at(e: Bucketable[G], at_tick: Int)
	do
		var at_key = key_for_tick(at_tick)

		if at_key == current_bucket_key then
			next_bucket.as(not null).add(e)
		else
			buckets[at_key].add(e)
		end

		e.act_at = at_tick
	end

	private fun key_for_tick(at_tick: Int): Int
	do
		return at_tick % buckets.length
	end

	redef fun do_turn(turn: GameTurn[G])
	do
		current_bucket_key = key_for_tick(turn.tick)
		var current_bucket = buckets[current_bucket_key]

		var next_bucket = new HashSet[Bucketable[G]]
		buckets[current_bucket_key] = next_bucket
		self.next_bucket = next_bucket

		for e in current_bucket do
			var act_at = e.act_at
			if act_at != null then
				if turn.tick == act_at then
					e.do_turn(turn)
				else if act_at > turn.tick and
					key_for_tick(act_at) == current_bucket_key
				then
					next_bucket.add(e)
				end
			end
		end
	end

	# Get some statistics on both the current held events and historic expired events
	fun stats: String
	do
		var entries = 0
		var instances = new HashSet[Bucketable[G]]
		var max = 0
		var min = 100000
		for bucket in buckets do
			var len = bucket.length
			entries += len
			instances.add_all bucket
			min = min.min(len)
			max = max.max(len)
		end
		var avg = entries.to_f / buckets.length.to_f

		return "{buckets.length} buckets; uniq/tot:{instances.length}/{entries}, avg:{avg.to_precision(1)}, min:{min}, max:{max}\n" +
			"history:{delays.sum}, avg:{delays.avg}, min:{delays[delays.min.as(not null)]}, max:{delays[delays.max.as(not null)]}"
	end
end