X-Git-Url: http://nitlanguage.org

diff --git a/lib/standard/collection/abstract_collection.nit b/lib/standard/collection/abstract_collection.nit
index 22a6563..16e4b1e 100644
--- a/lib/standard/collection/abstract_collection.nit
+++ b/lib/standard/collection/abstract_collection.nit
@@ -33,25 +33,29 @@ import kernel
 # Subclasses often provide a more efficient implementation.
 #
 # Because of the `iterator` method, Collections instances can use
-# the `for` control structure:
+# the `for` control structure.
 #
-#         var x: Collection[U]
-#         # ...
-#         for u in x do
-#             # u is a U
-#             # ...
-#         end
+# ~~~nitish
+# var x: Collection[U]
+# # ...
+# for u in x do
+#	# u is a U
+#	# ...
+# end
+# ~~~
 #
-# that is equivalent with
+# that is equivalent with the following:
 #
-#         var x: Collection[U]
-#         # ...
-#         var i = x.iterator
-#         while i.is_ok do
-#             var u = i.item # u is a U
-#             # ...
-#             i.next
-#         end
+# ~~~nitish
+# var x: Collection[U]
+# # ...
+# var i = x.iterator
+# while i.is_ok do
+#     var u = i.item # u is a U
+#     # ...
+#     i.next
+# end
+# ~~~
 interface Collection[E]
 	# Get a new iterator on the collection.
 	fun iterator: Iterator[E] is abstract
@@ -62,6 +66,14 @@ interface Collection[E]
 	#     assert [1..1[.is_empty   == true
 	fun is_empty: Bool do return length == 0
 
+	# Alias for `not is_empty`.
+	#
+	# Some people prefer to have conditions grammatically easier to read.
+	#
+	#     assert [1,2,3].not_empty  == true
+	#     assert [1..1[.not_empty   == false
+	fun not_empty: Bool do return not self.is_empty
+
 	# Number of items in the collection.
 	#
 	#     assert [10,20,30].length == 3
@@ -80,7 +92,7 @@ interface Collection[E]
 	#     assert [1,2,3].has(9)    == false
 	#     assert [1..5[.has(2)     == true
 	#     assert [1..5[.has(9)     == false
-	fun has(item: E): Bool
+	fun has(item: nullable Object): Bool
 	do
 		for i in self do if i == item then return true
 		return false
@@ -97,7 +109,7 @@ interface Collection[E]
 	#     assert [3..3[.has_only(1)          == true # empty collection
 	#
 	# ENSURE `is_empty implies result == true`
-	fun has_only(item: E): Bool
+	fun has_only(item: nullable Object): Bool
 	do
 		for i in self do if i != item then return false
 		return true
@@ -106,8 +118,8 @@ interface Collection[E]
 	# How many occurrences of `item` are in the collection?
 	# Comparisons are done with ==
 	#
-	#    assert [10,20,10].count(10)         == 2
-	fun count(item: E): Int
+	#     assert [10,20,10].count(10)         == 2
+	fun count(item: nullable Object): Int
 	do
 		var nb = 0
 		for i in self do if i == item then nb += 1
@@ -116,28 +128,60 @@ interface Collection[E]
 
 	# Return the first item of the collection
 	#
-	#    assert [1,2,3].first                == 1
+	#     assert [1,2,3].first                == 1
 	fun first: E
 	do
 		assert length > 0
 		return iterator.item
 	end
 
-	# Is the collection contains all the elements of `other`?
+	# Does the collection contain at least each element of `other`?
 	#
-	#    assert [1,1,1].has_all([1])         == true
-	#    assert [1,1,1].has_all([1,2])       == false
-	#    assert [1,3,4,2].has_all([1..2])    == true
-	#    assert [1,3,4,2].has_all([1..5])    == false
-	fun has_all(other: Collection[E]): Bool
+	#     assert [1,3,4,2].has_all([1..2])    == true
+	#     assert [1,3,4,2].has_all([1..5])    == false
+	#
+	# Repeated elements in the collections are not considered.
+	#
+	#     assert [1,1,1].has_all([1])         == true
+	#     assert [1..5].has_all([1,1,1])      == true
+	#
+	# Note that the default implementation is general and correct for any lawful Collections.
+	# It is memory-efficient but relies on `has` so may be CPU-inefficient for some kind of collections.
+	fun has_all(other: Collection[nullable Object]): Bool
 	do
 		for x in other do if not has(x) then return false
 		return true
 	end
+
+	# Does the collection contain exactly all the elements of `other`?
+	#
+	# The same elements must be present in both `self` and `other`,
+	# but the order of the elements in the collections are not considered.
+	#
+	#     assert [1..3].has_exactly([3,1,2]) == true  # the same elements
+	#     assert [1..3].has_exactly([3,1])   == false # 2 is not in the array
+	#     assert [1..2].has_exactly([3,1,2]) == false # 3 is not in the range
+	#
+	# Repeated elements must be present in both collections in the same amount.
+	# So basically it is a multi-set comparison.
+	#
+	#     assert [1,2,3,2].has_exactly([1,2,2,3]) == true  # the same elements
+	#     assert [1,2,3,2].has_exactly([1,2,3])   == false # more 2 in the first array
+	#     assert [1,2,3].has_exactly([1,2,2,3])   == false # more 2 in the second array
+	#
+	# Note that the default implementation is general and correct for any lawful Collections.
+	# It is memory-efficient but relies on `count` so may be CPU-inefficient for some kind of collections.
+	fun has_exactly(other: Collection[nullable Object]): Bool
+	do
+		if length != other.length then return false
+		for e in self do if self.count(e) != other.count(e) then return false
+		return true
+	end
 end
 
-# Instances of the Iterator class generates a series of elements, one at a time.
-# They are mainly used with collections.
+# Iterators generate a series of elements, one at a time.
+#
+# They are mainly used with collections and obtained from `Collection::iterator`.
 interface Iterator[E]
 	# The current item.
 	# Require `is_ok`.
@@ -147,6 +191,37 @@ interface Iterator[E]
 	# Require `is_ok`.
 	fun next is abstract
 
+	# Jump to the next item `step` times.
+	#
+	# ~~~
+	# var i = [11, 22, 33, 44].iterator
+	# assert i.item == 11
+	# i.next_by 2
+	# assert i.item == 33
+	# ~~~
+	#
+	# `next_by` should be used instead of looping on `next` because is takes care
+	# of stopping if the end of iteration is reached prematurely whereas a loop of
+	# `next` will abort because of the precondition on `is_ok`.
+	#
+	# ~~~
+	# i.next_by 100
+	# assert not i.is_ok
+	# ~~~
+	#
+	# If `step` is negative, this method aborts.
+	# But specific subclasses can change this and do something more meaningful instead.
+	#
+	# Require `is_ok`
+	fun next_by(step: Int)
+	do
+		assert step >= 0
+		while is_ok and step > 0 do
+			next
+			step -= 1
+		end
+	end
+
 	# Is there a current item ?
 	fun is_ok: Bool is abstract
 
@@ -162,13 +237,50 @@ interface Iterator[E]
 	#
 	# Do nothing by default.
 	fun finish do end
+
+	# A decorator around `self` that advance self a given number of steps instead of one.
+	#
+	# ~~~
+	# var i = [11, 22, 33, 44, 55].iterator
+	# var i2 = i.to_step(2)
+	#
+	# assert i2.item == 11
+	# i2.next
+	# assert i2.item == 33
+	#
+	# assert i.item == 33
+	# ~~~
+	fun to_step(step: Int): Iterator[E] do return new StepIterator[E](self, step)
+end
+
+# A basic helper class to specialize specific Iterator decorators
+abstract class IteratorDecorator[E]
+	super Iterator[E]
+
+	# The underling iterator
+	protected var real: Iterator[E]
+
+	redef fun is_ok do return real.is_ok
+	redef fun item do return real.item
+	redef fun finish do real.finish
+	redef fun next do real.next
+	redef fun next_by(step) do real.next_by(step)
+end
+
+# A decorator that advance a given number of steps
+private class StepIterator[E]
+	super IteratorDecorator[E]
+	var step: Int
+
+	redef fun next do real.next_by(step)
+	redef fun next_by(step) do real.next_by(step * self.step)
 end
 
 # A collection that contains only one item.
 #
 # Used to pass arguments by reference.
 #
-# Also used when one want to give asingle element when a full
+# Also used when one want to give a single element when a full
 # collection is expected
 class Container[E]
 	super Collection[E]
@@ -205,7 +317,7 @@ private class ContainerIterator[E]
 
 	redef fun next do is_ok = false
 
-	redef var is_ok: Bool = true
+	redef var is_ok = true
 
 	var container: Container[E]
 end
@@ -223,19 +335,19 @@ interface RemovableCollection[E]
 	# ENSURE `is_empty`
 	fun clear is abstract
 
-	# Remove an occucence of `item`
+	# Remove an occurrence of `item`
 	#
 	#     var a = [1,2,3,1,2,3]
 	#     a.remove 2
 	#     assert a == [1,3,1,2,3]
-	fun remove(item: E) is abstract
+	fun remove(item: nullable Object) is abstract
 
-	# Remove all occurences of `item`
+	# Remove all occurrences of `item`
 	#
 	#     var a = [1,2,3,1,2,3]
 	#     a.remove_all 2
 	#     assert a == [1,3,1,3]
-	fun remove_all(item: E) do while has(item) do remove(item)
+	fun remove_all(item: nullable Object) do while has(item) do remove(item)
 end
 
 # Items can be added to these collections.
@@ -270,7 +382,7 @@ end
 #      # ...
 #      s.add(a)
 #      assert s.has(b)      ==  true
-interface Set[E: Object]
+interface Set[E]
 	super SimpleCollection[E]
 
 	redef fun has_only(item)
@@ -301,7 +413,7 @@ interface Set[E: Object]
 	# Equality is defined on set and means that each set contains the same elements
 	redef fun ==(other)
 	do
-		if not other isa Set[Object] then return false
+		if not other isa Set[nullable Object] then return false
 		if other.length != length then return false
 		return has_all(other)
 	end
@@ -334,11 +446,15 @@ interface Set[E: Object]
 		return nhs
 	end
 
+	# Returns a new instance of `Set`.
+	#
+	# Depends on the subclass, mainly used for copy services
+	# like `union` or `intersection`.
 	protected fun new_set: Set[E] is abstract
 end
 
 # MapRead are abstract associative collections: `key` -> `item`.
-interface MapRead[K: Object, V]
+interface MapRead[K, V]
 	# Get the item at `key`
 	#
 	#     var x = new HashMap[String, Int]
@@ -348,7 +464,7 @@ interface MapRead[K: Object, V]
 	#
 	# If the key is not in the map, `provide_default_value` is called (that aborts by default)
 	# See `get_or_null` and `get_or_default` for safe variations.
-	fun [](key: K): V is abstract
+	fun [](key: nullable Object): V is abstract
 
 	# Get the item at `key` or null if `key` is not in the map.
 	#
@@ -358,7 +474,7 @@ interface MapRead[K: Object, V]
 	#     assert x.get_or_null("five") == null
 	#
 	# Note: use `has_key` and `[]` if you need the distinction between a key associated with null, and no key.
-	fun get_or_null(key: K): nullable V
+	fun get_or_null(key: nullable Object): nullable V
 	do
 		if has_key(key) then return self[key]
 		return null
@@ -371,14 +487,21 @@ interface MapRead[K: Object, V]
 	#     assert x.get_or_default("four", 40) == 4
 	#     assert x.get_or_default("five", 50) == 50
 	#
-	fun get_or_default(key: K, default: V): V
+	fun get_or_default(key: nullable Object, default: V): V
 	do
 		if has_key(key) then return self[key]
 		return default
 	end
 
-	# Alias for `keys.has`
-	fun has_key(key: K): Bool do return self.keys.has(key)
+	# Is there an item associated with `key`?
+	#
+	#     var x = new HashMap[String, Int]
+	#     x["four"] = 4
+	#     assert x.has_key("four") == true
+	#     assert x.has_key("five") == false
+	#
+	# By default it is a synonymous to `keys.has` but could be redefined with a direct implementation.
+	fun has_key(key: nullable Object): Bool do return self.keys.has(key)
 
 	# Get a new iterator on the map.
 	fun iterator: MapIterator[K, V] is abstract
@@ -426,7 +549,50 @@ interface MapRead[K: Object, V]
 	#
 	# Note: the value is returned *as is*, implementations may want to store the value in the map before returning it
 	# @toimplement
-	protected fun provide_default_value(key: K): V do abort
+	protected fun provide_default_value(key: nullable Object): V do abort
+
+	# Does `self` and `other` have the same keys associated with the same values?
+	#
+	# ~~~
+	# var a = new HashMap[String, Int]
+	# var b = new ArrayMap[Object, Numeric]
+	# assert a == b
+	# a["one"] = 1
+	# assert a != b
+	# b["one"] = 1
+	# assert a == b
+	# b["one"] = 2
+	# assert a != b
+	# ~~~
+	redef fun ==(other)
+	do
+		if not other isa MapRead[nullable Object, nullable Object] then return false
+		if other.length != self.length then return false
+		for k, v in self do
+			if not other.has_key(k) then return false
+			if other[k] != v then return false
+		end
+		return true
+	end
+
+	# A hashcode based on the hashcode of the keys and the values.
+	#
+	# ~~~
+	# var a = new HashMap[String, Int]
+	# var b = new ArrayMap[Object, Numeric]
+	# a["one"] = 1
+	# b["one"] = 1
+	# assert a.hash == b.hash
+	# ~~~
+	redef fun hash
+	do
+		var res = length
+		for k, v in self do
+			if k != null then res += k.hash * 7
+			if v != null then res += v.hash * 11
+		end
+		return res
+	end
 end
 
 # Maps are associative collections: `key` -> `item`.
@@ -453,7 +619,7 @@ end
 #     assert map.values.has(1)      ==  true
 #     assert map.values.has(3)      ==  false
 #
-interface Map[K: Object, V]
+interface Map[K, V]
 	super MapRead[K, V]
 
 	# Set the `value` at `key`.
@@ -513,7 +679,7 @@ interface Map[K: Object, V]
 end
 
 # Iterators for Map.
-interface MapIterator[K: Object, V]
+interface MapIterator[K, V]
 	# The current item.
 	# Require `is_ok`.
 	fun item: V is abstract
@@ -544,7 +710,7 @@ interface MapIterator[K: Object, V]
 end
 
 # Iterator on a 'keys' point of view of a map
-class MapKeysIterator[K: Object, V]
+class MapKeysIterator[K, V]
 	super Iterator[K]
 	# The original iterator
 	var original_iterator: MapIterator[K, V]
@@ -555,7 +721,7 @@ class MapKeysIterator[K: Object, V]
 end
 
 # Iterator on a 'values' point of view of a map
-class MapValuesIterator[K: Object, V]
+class MapValuesIterator[K, V]
 	super Iterator[V]
 	# The original iterator
 	var original_iterator: MapIterator[K, V]
@@ -618,7 +784,7 @@ interface SequenceRead[E]
 	#     var a = [10,20,30,10,20,30]
 	#     assert a.index_of(20)   == 1
 	#     assert a.index_of(40)   == -1
-	fun index_of(item: E): Int do return index_of_from(item, 0)
+	fun index_of(item: nullable Object): Int do return index_of_from(item, 0)
 
 	# The index of the last occurrence of `item`.
 	# Return -1 if `item` is not found.
@@ -627,7 +793,7 @@ interface SequenceRead[E]
 	#     var a = [10,20,30,10,20,30]
 	#     assert a.last_index_of(20)   == 4
 	#     assert a.last_index_of(40)   == -1
-	fun last_index_of(item: E): Int do return last_index_of_from(item, length-1)
+	fun last_index_of(item: nullable Object): Int do return last_index_of_from(item, length-1)
 
 	# The index of the first occurrence of `item`, starting from pos.
 	# Return -1 if `item` is not found.
@@ -637,7 +803,7 @@ interface SequenceRead[E]
 	#     assert a.index_of_from(20, 3)   == 4
 	#     assert a.index_of_from(20, 4)   == 4
 	#     assert a.index_of_from(20, 5)   == -1
-	fun index_of_from(item: E, pos: Int): Int
+	fun index_of_from(item: nullable Object, pos: Int): Int
 	do
 		var p = 0
 		var i = iterator
@@ -657,7 +823,7 @@ interface SequenceRead[E]
 	#     assert a.last_index_of_from(20, 2)   == 1
 	#     assert a.last_index_of_from(20, 1)   == 1
 	#     assert a.last_index_of_from(20, 0)   == -1
-	fun last_index_of_from(item: E, pos: Int): Int
+	fun last_index_of_from(item: nullable Object, pos: Int): Int
 	do
 		var res = -1
 		var p = 0
@@ -902,12 +1068,12 @@ end
 
 # Associative arrays that internally uses couples to represent each (key, value) pairs.
 # This is an helper class that some specific implementation of Map may implements.
-interface CoupleMap[K: Object, V]
+interface CoupleMap[K, V]
 	super Map[K, V]
 
 	# Return the couple of the corresponding key
 	# Return null if the key is no associated element
-	protected fun couple_at(key: K): nullable Couple[K, V] is abstract
+	protected fun couple_at(key: nullable Object): nullable Couple[K, V] is abstract
 
 	# Return a new iteralot on all couples
 	# Used to provide `iterator` and others
@@ -924,15 +1090,17 @@ interface CoupleMap[K: Object, V]
 			return c.second
 		end
 	end
+
+	redef fun has_key(key) do return couple_at(key) != null
 end
 
 # Iterator on CoupleMap
 #
 # Actually it is a wrapper around an iterator of the internal array of the map.
-private class CoupleMapIterator[K: Object, V]
+private class CoupleMapIterator[K, V]
 	super MapIterator[K, V]
 	redef fun item do return _iter.item.second
-	
+
 	#redef fun item=(e) do _iter.item.second = e
 
 	redef fun key do return _iter.item.first