Merge: More keep going

[nit.git] / lib / standard / collection / list.nit

diff --git a/lib/standard/collection/list.nit b/lib/standard/collection/list.nit
index 804c629..2cdc431 100644 (file)
--- 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
@@ -116,8 +118,19 @@ class List[E]
                _head = node
        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
@@ -181,6 +194,7 @@ 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
@@ -189,10 +203,10 @@ class List[E]
        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.
        private fun get_node(i: Int): nullable ListNode[E]
@@ -255,6 +269,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
@@ -266,21 +281,19 @@ class ListIterator[E]
        end
 
        # Build a new iterator for `list`.
-       private init(list: List[E])
+       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
@@ -295,17 +308,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