lib/map: document `Map.has_key` and implement it efficienlty

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

diff --git a/lib/standard/collection/abstract_collection.nit b/lib/standard/collection/abstract_collection.nit
index d5621a9..d38e001 100644 (file)
--- a/lib/standard/collection/abstract_collection.nit
+++ b/lib/standard/collection/abstract_collection.nit
@@ -305,7 +305,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)
@@ -377,7 +377,7 @@ interface Set[E: Object]
 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]
@@ -416,7 +416,14 @@ interface MapRead[K: Object, V]
                return default
        end
 
-       # Alias for `keys.has`
+       # 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: K): Bool do return self.keys.has(key)
 
        # Get a new iterator on the map.
@@ -466,6 +473,30 @@ 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
+
+       # 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
 end
 
 # Maps are associative collections: `key` -> `item`.
@@ -492,7 +523,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`.
@@ -552,7 +583,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
@@ -583,7 +614,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]
@@ -594,7 +625,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]
@@ -941,7 +972,7 @@ 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
@@ -963,12 +994,14 @@ 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