# Representation of sprite data on the GPU
#
# The main purpose of this class is to optimize the use of contiguous
# space in GPU memory. Each contiguous memory block can be drawn in a
# single call. The starts index of each block is kept by `starts,
# and the end + 1 by `ends`.
#
# The data can be compressed by a call to `defragment`.
#
# ~~~
# intrude import gamnit::flat
#
# var array = new GroupedArray[String]
# assert array.to_s == ""
#
# array.add "a"
# array.add "b"
# array.add "c"
# array.add "d"
# array.add "e"
# array.add "f"
# assert array.to_s == "[a,b,c,d,e,f]"
# assert array.capacity == 6
#
# array.remove "a"
# assert array.to_s == "[b,c,d,e,f]"
#
# array.remove "b"
# assert array.to_s == "[c,d,e,f]"
#
# array.remove "f"
# assert array.to_s == "[c,d,e]"
#
# array.remove "d"
# assert array.to_s == "[c][e]"
#
# array.add "A"
# assert array.to_s == "[A][c][e]"
#
# array.add "B"
# assert array.to_s == "[A,B,c][e]"
#
# array.remove "e"
# assert array.to_s == "[A,B,c]"
#
# array.add "D"
# assert array.to_s == "[A,B,c,D]"
#
# array.add "E"
# assert array.to_s == "[A,B,c,D,E]"
# assert array.capacity == 6
# assert array.length == 5
#
# array.remove "A"
# array.remove "B"
# array.remove "c"
# array.remove "D"
# array.remove "E"
# assert array.to_s == ""
#
# array.add "a"
# assert array.to_s == "[a]"
# ~~~
private class GroupedArray[E]

	# Memory with actual objects, and null in empty slots
	var items = new Array[nullable E]

	# Number of items in the array
	var length = 0

	# Number of item slots in the array
	fun capacity: Int do return items.length

	# List of available slots
	var available = new MinHeap[Int].default

	# Start index of filled chunks
	var starts = new List[Int]

	# Index of the spots after filled chunks
	var ends = new List[Int]

	# Add `item` to the first available slot and return its index
	fun add(item: E): Int
	do
		length += 1

		if available.not_empty then
			# starts & ends can't be empty

			var i = available.take
			items[i] = item

			if i == starts.first - 1 then
				# slot 0 free, 1 taken
				starts.first -= 1
			else if i == 0 then
				# slot 0 and more free
				starts.unshift 0
				ends.unshift 1
			else if starts.length >= 2 and ends.first + 1 == starts[1] then
				# merge 2 chunks
				ends.remove_at 0
				starts.remove_at 1
			else
				# at end of first chunk
				ends.first += 1
			end
			return i
		end

		items.add item
		if ends.is_empty then
			starts.add 0
			ends.add 1
		else ends.last += 1
		return ends.last - 1
	end

	# Remove the first instance of `item`
	fun remove(item: E)
	do
		var index = items.index_of(item)
		remove_at(item, index)
	end

	# Remove `item` at `index`
	fun remove_at(item: E, index: Int)
	do
		var i = index
		length -= 1
		items[i] = null

		var ii = 0
		for s in starts, e in ends do
			if s <= i and i < e then
				if s == e-1 then
					# single item chunk
					starts.remove_at ii
					ends.remove_at ii

					if starts.is_empty then
						items.clear
						available.clear
						return
					end
				else if e-1 == i then
					# last item of chunk
					ends[ii] -= 1

				else if s == i then
					# first item of chunk
					starts[ii] += 1
				else
					# break up chunk
					ends.insert(ends[ii], ii+1)
					ends[ii] = i
					starts.insert(i+1, ii+1)
				end

				available.add i
				return
			end
			ii += 1
		end

		abort
	end

	# Defragment and compress everything into a single chunks beginning at 0
	#
	# Returns the elements that moved as a list.
	#
	# ~~~
	# intrude import gamnit::flat
	#
	# var array = new GroupedArray[String]
	# array.add "a"
	# array.add "b"
	# array.add "c"
	# array.add "d"
	# array.remove "c"
	# array.remove "a"
	# assert array.to_s == "[b][d]"
	#
	# var moved = array.defragment
	# assert moved.to_s == "[d]"
	# assert array.to_s == "[d,b]"
	# assert array.length == 2
	# assert array.capacity == 2
	#
	# array.add "e"
	# array.add "f"
	# assert array.to_s == "[d,b,e,f]"
	# ~~~
	fun defragment(max: nullable Int): Array[E]
	do
		app.perf_clock_sprites.lapse
		max = max or else length

		var moved = new Array[E]
		while max > 0 and (starts.length > 1 or starts.first != 0) do
			var i = ends.last - 1
			var e = items[i]
			assert e != null
			remove e
			add e
			moved.add e
			max -= 1
		end

		if starts.length == 1 and starts.first == 0 then
			for i in [length..capacity[ do items.pop
			available.clear
		end

		sys.perfs["gamnit flat gpu defrag"].add app.perf_clock_sprites.lapse
		return moved
	end

	redef fun to_s
	do
		var ss = new Array[String]
		for s in starts, e in ends do
			ss.add "["
			for i in [s..e[ do
				var item: nullable Object = items[i]
				if item == null then item = "null"
				ss.add item.to_s
				if i != e-1 then ss.add ","
			end
			ss.add "]"
		end
		return ss.join
	end
end