lib/coll: generalize `insert` in Sequence

Signed-off-by: Jean Privat <jean@pryen.org>

diff --git a/lib/standard/collection/abstract_collection.nit b/lib/standard/collection/abstract_collection.nit
index d08560b..39fe9bb 100644 (file)
--- a/lib/standard/collection/abstract_collection.nit
+++ b/lib/standard/collection/abstract_collection.nit
@@ -762,6 +762,16 @@ interface Sequence[E]
        # REQUIRE `index >= 0 and index <= length`
        fun []=(index: Int, item: E) is abstract
 
+       # Insert an element at a given position, following elements are shifted.
+       #
+       #     var a = [10, 20, 30, 40]
+       #     a.insert(100, 2)
+       #     assert a      ==  [10, 20, 100, 30, 40]
+       #
+       # REQUIRE `index >= 0 and index < length`
+       # ENSURE `self[index] == item`
+       fun insert(item: E, index: Int) is abstract
+
        # Remove the item at `index` and shift all following elements
        #
        #     var a = [10,20,30]

diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit
index e8e814c..d242966 100644 (file)
--- a/lib/standard/collection/array.nit
+++ b/lib/standard/collection/array.nit
@@ -177,12 +177,7 @@ abstract class AbstractArray[E]
                self[0] = item
        end
 
-       # Insert an element at a given position, following elements are shifted.
-       #
-       #     var a= [10, 20, 30, 40]
-       #     a.insert(100, 2)
-       #     assert a      ==  [10, 20, 100, 30, 40]
-       fun insert(item: E, pos: Int)
+       redef fun insert(item: E, pos: Int)
        do
                enlarge(length + 1)
                copy_to(pos, length-pos, self, pos + 1)

diff --git a/lib/standard/collection/list.nit b/lib/standard/collection/list.nit
index 3a59a49..c9a7155 100644 (file)
--- a/lib/standard/collection/list.nit
+++ b/lib/standard/collection/list.nit
@@ -116,6 +116,26 @@ 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
+               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)