Merge: example: add 24 game task of Rosetta code

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

diff --git a/lib/standard/collection/list.nit b/lib/standard/collection/list.nit
index d032066..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
@@ -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,19 @@ 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
+               insert_before(e, node)
+       end
+
+       # Append `l` to `self` but clear `l`.
+       #
        # O(1)
        fun link(l: List[E])
        do
@@ -171,20 +194,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 +222,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 +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
@@ -255,22 +280,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 +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