# An unrolled linked list
#
# A sequence implemented as a linked list of arrays.
#
# This data structure is similar to the `List` but it can benefit from
# better cache performance, lower data overhead for the nodes metadata and
# it spares the GC to allocate many small nodes.
class UnrolledList[E]
	super Sequence[E]

	# Desired capacity for each nodes
	#
	# By default at `32`, it can be increased for very large lists.
	#
	# It can be modified anytime, but newly created nodes may still be assigned
	# the same capacity of old nodes when created by `insert`.
	var nodes_length = 32 is writable

	private var head_node: UnrolledNode[E] = new UnrolledNode[E](nodes_length)

	private var tail_node: UnrolledNode[E] = head_node

	redef var length = 0

	redef fun clear
	do
		head_node = new UnrolledNode[E](nodes_length)
		tail_node = head_node
		length = 0
	end

	# Out parameter of `node_at`
	private var index_within_node = 0

	private fun node_at(index: Int): UnrolledNode[E]
	do
		assert index >= 0 and index < length

		var node = head_node
		while index >= node.length do
			index -= node.length
			node = node.next.as(not null)
		end

		index_within_node = index
		return node
	end

	private fun insert_node(node: UnrolledNode[E], prev, next: nullable UnrolledNode[E])
	do
		if prev != null then
			prev.next = node
		else head_node = node

		if next != null then
			next.prev = node
		else tail_node = node

		node.next = next
		node.prev = prev
	end

	redef fun [](index)
	do
		var node = node_at(index)
		index = index_within_node + node.head_index
		return node.items[index]
	end

	redef fun []=(index, value)
	do
		var node = node_at(index)
		index = index_within_node + node.head_index
		node.items[index] = value
	end

	redef fun push(item)
	do
		var node = tail_node
		if not node.full then
			if node.tail_index < node.capacity then
				# There's room at the tail
				node.tail_index += 1
			else
				# Move everything over by `d`
				assert node.head_index > 0
				var d = node.head_index / 2 + 1
				node.move_head(node.length, d)
				for i in d.times do node.items[node.tail_index - i] = null
				node.head_index -= d
				node.tail_index += -d+1
			end
			node.items[node.tail_index-1] = item
		else
			# New node!
			node = new UnrolledNode[E](nodes_length)
			insert_node(node, tail_node, null)
			node.tail_index = 1
			node.items[0] = item
		end
		length += 1
	end

	redef fun unshift(item)
	do
		var node = head_node
		if not node.full then
			if node.head_index > 0 then
				# There's room at the head
				node.head_index -= 1
			else
				# Move everything over by `d`
				assert node.tail_index < node.capacity
				var d = (node.capacity-node.tail_index) / 2 + 1
				node.move_tail(0, d)
				for i in d.times do node.items[node.head_index+i] = null
				node.head_index += d-1
				node.tail_index += d
			end
			node.items[node.head_index] = item
		else
			# New node!
			node = new UnrolledNode[E](nodes_length)
			insert_node(node, null, head_node)
			node.head_index = node.capacity-1
			node.tail_index = node.capacity
			node.items[node.capacity-1] = item
		end
		length += 1
	end

	redef fun pop
	do
		assert not_empty

		var node = tail_node
		while node.length == 0 do
			# Delete empty node
			var nullable_node = node.prev
			assert is_not_empty: nullable_node != null
			node = nullable_node
			node.next = null
			self.tail_node = node
		end

		var item = node.items[node.tail_index-1]
		node.tail_index -= 1
		length -= 1
		return item
	end

	redef fun shift
	do
		assert not_empty

		var node = head_node
		while node.length == 0 do
			# Delete empty node
			var nullable_node = node.next
			assert is_not_empty: nullable_node != null
			node = nullable_node
			node.prev = null
			self.head_node = node
		end

		var item = node.items[node.head_index]
		node.head_index += 1
		length -= 1
		return item
	end

	redef fun insert(item, index)
	do
		if index == length then
			push item
			return
		end

		var node = node_at(index)
		index = index_within_node
		if node.full then
			# Move half to a new node
			var new_node = new UnrolledNode[E](nodes_length.max(node.capacity))

			# Plug in the new node
			var next_node = node.next
			insert_node(new_node, node, next_node)

			# Move items at and after `index` to the new node
			var to_displace = node.length-index
			var offset = (new_node.capacity-to_displace)/2
			for i in [0..to_displace[ do
				new_node.items[offset+i] = node.items[index+i]
				node.items[index+i] = null
			end
			new_node.head_index = offset
			new_node.tail_index = offset + to_displace
			node.tail_index -= to_displace

			# Store `item`
			if index > node.capacity / 2 then
				new_node.items[offset-1] = item
				new_node.head_index -= 1
			else
				node.items[node.head_index+index] = item
				node.tail_index += 1
			end
		else
			if node.tail_index < node.capacity then
				# Move items towards the tail
				node.move_tail(index, 1)
				node.tail_index += 1
				node.items[node.head_index + index] = item
			else
				# Move items towards the head
				node.move_head(index, 1)
				node.items[node.head_index + index-1] = item
				node.head_index -= 1
			end
		end
		length += 1
	end

	redef fun remove_at(index)
	do
		var node = node_at(index)
		index = index_within_node + node.head_index

		# Shift left all the elements after `index`
		for i in [index+1 .. node.tail_index[ do
			node.items[i-1] = node.items[i]
		end
		node.tail_index -= 1
		node.items[node.tail_index] = null

		length -= 1

		var next_node = node.next
		var prev_node = node.prev
		if node.is_empty and (next_node != null or prev_node != null) then
			# Empty and non-head or tail node, delete
			if next_node != null then
				next_node.prev = node.prev
			else tail_node = prev_node.as(not null)

			if prev_node != null then
				prev_node.next = node.next
			else head_node = next_node.as(not null)
		end
	end

	redef fun iterator do return new UnrolledIterator[E](self)
end