From: Jean Privat <jean@pryen.org>
Date: Thu, 20 Mar 2014 09:10:52 +0000 (-0400)
Subject: lib/coll: generalize `insert` in Sequence
X-Git-Tag: v0.6.5~19^2~3
X-Git-Url: http://nitlanguage.org

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
--- 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
--- 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
--- 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)