# another product.
# This module handle double linked lists
-package list
+module list
import abstract_collection
# Double linked lists.
class List[E]
-special IndexedCollection[E]
+ super Sequence[E]
# Access
redef fun [](index) do return get_node(index).item
return nb
end
- redef fun has_key(index) do return get_node(index) != null
+ # 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
_head = node
end
- # Append `l' to `self' but clear `l'.
+ # O(n)
+ redef fun insert(e, i)
+ do
+ var node = get_node(i)
+ if node == null then
+ push(e)
+ return
+ end
+ var nnode = new ListNode[E](e)
+ var next = node.next
+ if next == null then
+ _tail = nnode
+ else
+ next.prev = nnode
+ end
+ nnode.prev = node
+ nnode.next = next
+ node.next = nnode
+ end
+
+ # Append `l` to `self` but clear `l`.
##
# O(1)
fun link(l: List[E])
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'.
+ # Build a list filled with the items of `coll`.
init from(coll: Collection[E]) do append(coll)
# The first node of the list
# The last node of the list
var _tail: nullable ListNode[E]
- # Get the `i'th node. get `null' otherwise.
+ # Get the `i`th node. get `null` otherwise.
private fun get_node(i: Int): nullable ListNode[E]
do
var n = _head
return n
end
- # get the first node that contains e after 'after', null otherwise
+ # 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
# This is the iterator class of List
class ListIterator[E]
-special IndexedIterator[E]
+ super IndexedIterator[E]
redef fun item do return _node.item
fun item=(e: E) do _node.item = e
_index += 1
end
- # Build a new iterator from `node'.
+ # Build a new iterator for `list`.
private init(list: List[E])
do
_list = list
var _node: nullable ListNode[E]
# The index of the current node
- redef readable var _index: Int
+ var _index: Int
+
+ redef fun index do return _index
# Remove the current item
fun delete
end
end
+private class ListReverseIterator[E]
+ super ListIterator[E]
+
+ redef fun next
+ do
+ _node = _node.prev
+ _index -= 1
+ end
+
+ private init(list: List[E])
+ do
+ _list = list
+ _node = list._tail
+ _index = list.length
+ end
+end
+
# Linked nodes that constitute a linked list.
private class ListNode[E]
-special Container[E]
+ super Container[E]
init(i: E)
do
item = i
end
# The next node.
- readable writable var _next: nullable ListNode[E]
+ var next: nullable ListNode[E]
# The previous node.
- readable writable var _prev: nullable ListNode[E]
+ var prev: nullable ListNode[E]
end