# Double linked lists.
class List[E]
	super Sequence[E]

# Access

	redef fun [](index) do return get_node(index).as(not null).item

	redef fun []=(index, item) do get_node(index).as(not null).item = item

	# O(1)
	redef fun first do return _head.as(not null).item

	# O(1)
	redef fun first=(e) do _head.as(not null).item = e

	# O(1)
	redef fun last do return _tail.as(not null).item

	# O(1)
	redef fun last=(e) do _tail.as(not null).item = e

# Queries

	# O(1)
	redef fun is_empty do return _head == null

	# O(1)
	redef var length = 0

	# O(n)
	redef fun has(e) do return search_node_after(e, _head) != null

	redef fun has_only(e)
	do
		var node = _head
		while node != null do
			if node.item != e then return false
			node = node.next
		end
		return true
	end

	redef fun count(e)
	do
		var nb = 0
		var node = _head
		while node != null do
			if node.item != e then nb += 1
			node = node.next
		end
		return nb
	end

	# Return a list of elements between 'from' and 'to'.
	fun slice(from: Int, to: Int): List[E] do
		assert from >= 0 and from < length
		assert to >= 0 and to < length and from <= to
		var list = new List[E]
		while from <= to do
			list.add(self[from])
			from += 1
		end
		return list
	end

# Add elements

	# O(1)
	redef fun push(e)
	do
		var node = new ListNode[E](e)
		var tail = _tail
		if tail == null then
			_head = node
		else
			tail.next = node
			node.prev = tail
		end
		_tail = node
		length += 1
	end

	# O(1)
	redef fun unshift(e)
	do
		var node = new ListNode[E](e)
		var head = _head
		if head == null then
			_tail = node
		else
			node.next = head
			head.prev = node
		end
		_head = node
		length += 1
	end

	# 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

	# Append `l` to `self` but clear `l`.
	#
	# O(1)
	fun link(l: List[E])
	do
		var tail = _tail
		if tail == null then
			_head = l._head
		else if l._head != null then
			tail.next = l._head
			tail.next.as(not null).prev = tail
		end
		_tail = l._tail
		length += l.length
		l.clear
	end

# Remove elements

	# O(1)
	redef fun pop
	do
		var node = _tail.as(not null)
		_tail = node.prev
		node.prev = null
		if _tail == null then
			_head = null
		else
			_tail.as(not null).next = null
		end
		length -= 1
		return node.item
	end

	# O(1)
	redef fun shift
	do
		var node = _head.as(not null)
		_head = node.next
		node.next = null
		if _head == null then
			_tail = null
		else
			_head.as(not null).prev = null
		end
		length -= 1
		return node.item
	end

	redef fun remove(e)
	do
		var node = search_node_after(e, _head)
		if node != null then remove_node(node)
	end

	redef fun remove_at(i)
	do
		var node = get_node(i)
		if node != null then remove_node(node)
	end

	redef fun clear
	do
		_head = null
		_tail = null
		length = 0
	end


	redef fun iterator: ListIterator[E] do return new ListIterator[E](self)
	redef fun reverse_iterator: ListIterator[E] do return new ListReverseIterator[E](self)

	# Build an empty list.
	init do end

	# Build a list filled with the items of `coll`.
	init from(coll: Collection[E]) do append(coll)

	# The first node of the list
	private var head: nullable ListNode[E] = null

	# The last node of the list
	private var tail: nullable ListNode[E] = null

	# Get the `i`th node. get `null` otherwise.
	private fun get_node(i: Int): nullable ListNode[E]
	do
		var n = _head
		if i < 0 then
			return null
		end
		while n != null and i > 0 do
			n = n.next
			i -= 1
		end
		return n
	end

	# get the first node that contains `e` after 'after', null otherwise
	private fun search_node_after(e: E, after: nullable ListNode[E]): nullable ListNode[E]
	do
		var n = after
		while n != null and n.item != e do n = n.next
		return n
	end

	# Remove the node (ie. atach prev and next)
	private fun remove_node(node: ListNode[E])
	do
		length -= 1
		if node.prev == null then
			_head = node.next
			if node.next == null then
				_tail = null
			else
				node.next.as(not null).prev = null
			end
		else if node.next == null then
			_tail = node.prev
			node.prev.as(not null).next = null
		else
			node.prev.as(not null).next = node.next
			node.next.as(not null).prev = node.prev
		end
	end

	private fun insert_before(element: E, node: ListNode[E])
	do
		length += 1
		var nnode = new ListNode[E](element)
		var prev = node.prev
		if prev == null then
			_head = nnode
		else
			prev.next = nnode
		end
		nnode.prev = prev
		nnode.next = node
		node.prev = nnode
	end
end