X-Git-Url: http://nitlanguage.org?ds=sidebyside

diff --git a/lib/standard/collection/list.nit b/lib/standard/collection/list.nit
index d032066..66ef4af 100644
--- a/lib/standard/collection/list.nit
+++ b/lib/standard/collection/list.nit
@@ -11,14 +11,16 @@
 # another product.
 
 # This module handle double linked lists
-package list
+module list
 
 import abstract_collection
 
 # Double linked lists.
 class List[E]
 	super Sequence[E]
+
 # Access
+
 	redef fun [](index) do return get_node(index).item
 
 	redef fun []=(index, item) do get_node(index).item = item
@@ -76,7 +78,17 @@ class List[E]
 		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
 
@@ -106,8 +118,28 @@ class List[E]
 		_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])
 	do
@@ -171,20 +203,21 @@ class 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
-	var _head: nullable ListNode[E]
+	private var head: nullable ListNode[E] = null
 
 	# The last node of the list
-	var _tail: nullable ListNode[E]
+	private var tail: nullable ListNode[E] = null
 
-	# 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
@@ -198,7 +231,7 @@ class List[E]
 		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
@@ -245,6 +278,7 @@ class ListIterator[E]
 	super IndexedIterator[E]
 	redef fun item do return _node.item
 
+	# Set item `e` at self `index`.
 	fun item=(e: E) do _node.item = e
 
 	redef fun is_ok do return not _node == null
@@ -255,22 +289,20 @@ class ListIterator[E]
 		_index += 1
 	end
 
-	# Build a new iterator from `node'.
-	private init(list: List[E])
+	# Build a new iterator for `list`.
+	init
 	do
-		_list = list
-		_node = list._head
-		_index = 0
+		_node = _list._head
 	end
 
 	# The current list
-	var _list: List[E]
+	private var list: List[E]
 
 	# The current node of the list
-	var _node: nullable ListNode[E]
+	private var node: nullable ListNode[E] = null
 
 	# The index of the current node
-	redef readable var _index: Int
+	redef var index = 0
 
 	# Remove the current item
 	fun delete
@@ -285,17 +317,30 @@ class ListIterator[E]
 	end
 end
 
+private class ListReverseIterator[E]
+	super ListIterator[E]
+
+	redef fun next
+	do
+		_node = _node.prev
+		_index -= 1
+	end
+
+	init
+	do
+		var list = _list
+		_node = list._tail
+		_index = list.length
+	end
+end
+
 # Linked nodes that constitute a linked list.
 private class ListNode[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] = null
 
 	# The previous node.
-	readable writable var _prev: nullable ListNode[E]
+	var prev: nullable ListNode[E] = null
 end