# O(n)
	redef fun insert(e, i)
	do
		var node = get_node(i)
		if node == null then
			push(e)
			return
		end
		insert_before(e, node)
	end

	redef fun insert(item, index)
	do
		# Special insertion at the end (is push)
		if index >= length then
			assert index == length
			push(item)
			return
		end
		assert index >= 0

		var new_len = length + 1

		# TODO be more efficient:
		# Here, we just allocate a new native and copy everything.

		# Allocate a new native array
		var c = native.length
		while c < new_len do c *= 2
		var new_native = new NativeArray[E](c)

		# Copy everything
		var i = 0
		while i < index do
			new_native[i] = self[i]
			i += 1
		end
		new_native[index] = item
		var l = length
		while i < l do
			new_native[i+1] = self[i]
			i += 1
		end

		# Use the new native array
		length = new_len
		head = 0
		tail = new_len - 1
		native = new_native
	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 insert(it, index) do
		entities.insert(it, index)
		it.set_parent owner
	end

	redef fun insert(item, pos) do
		enlarge(length + 1)
		copy_to(pos, length-pos, self, pos + 1)
		self[pos] = item
	end

	redef fun insert(e, i)
	do
		mutex.lock
		real_collection.insert(e, i)
		mutex.unlock
	end