From: Jean Privat Date: Wed, 14 Jan 2015 01:16:42 +0000 (-0500) Subject: Merge: Allow keys to be nullable in `Map` and `MapIterator` X-Git-Tag: v0.7.1~32 X-Git-Url: http://nitlanguage.org?hp=1698b759569be325f2c700f5a9793ad3554b0683 Merge: Allow keys to be nullable in `Map` and `MapIterator` I need at least the first commit since MapIterators can be used with non-maps. The second commit is more for consistency. Note that HashMap keys are still non-null. If this is of interest to you, I'll complete and publish my `NullableMap` in `more_collection`. Pull-Request: #1041 Reviewed-by: Alexandre Terrasa Reviewed-by: Jean Privat --- diff --git a/lib/more_collections.nit b/lib/more_collections.nit index 1bcc514..6396ec2 100644 --- a/lib/more_collections.nit +++ b/lib/more_collections.nit @@ -29,7 +29,7 @@ module more_collections # assert m.has_key("four") # assert m["four"] == ['i', 'i', 'i', 'i'] # assert m["zzz"] == new Array[Char] -class MultiHashMap[K: Object, V] +class MultiHashMap[K, V] super HashMap[K, Array[V]] # Add `v` to the array associated with `k`. @@ -59,7 +59,7 @@ end # assert hm2[1, "one"] == 1.0 # assert hm2[2, "not-two"] == null # ~~~~ -class HashMap2[K1: Object, K2: Object, V] +class HashMap2[K1, K2, V] private var level1 = new HashMap[K1, HashMap[K2, V]] # Return the value associated to the keys `k1` and `k2`. @@ -97,7 +97,7 @@ end # assert hm3[1, "one", 11] == 1.0 # assert hm3[2, "not-two", 22] == null # ~~~~ -class HashMap3[K1: Object, K2: Object, K3: Object, V] +class HashMap3[K1, K2, K3, V] private var level1 = new HashMap[K1, HashMap2[K2, K3, V]] # Return the value associated to the keys `k1`, `k2`, and `k3`. @@ -165,7 +165,7 @@ end # assert dma["b"] == [65, 66] # assert dma.default == [65] # ~~~~ -class DefaultMap[K: Object, V] +class DefaultMap[K, V] super HashMap[K, V] # The default value. diff --git a/lib/standard/collection/abstract_collection.nit b/lib/standard/collection/abstract_collection.nit index d5621a9..bb17064 100644 --- a/lib/standard/collection/abstract_collection.nit +++ b/lib/standard/collection/abstract_collection.nit @@ -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] @@ -492,7 +492,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 +552,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 +583,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 +594,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 +941,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 @@ -968,7 +968,7 @@ 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 diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit index 68f84e7..44ea5d3 100644 --- a/lib/standard/collection/array.nit +++ b/lib/standard/collection/array.nit @@ -536,7 +536,7 @@ end # Associative arrays implemented with an array of (key, value) pairs. -class ArrayMap[K: Object, E] +class ArrayMap[K, E] super CoupleMap[K, E] # O(n) @@ -618,7 +618,7 @@ class ArrayMap[K: Object, E] end end -private class ArrayMapKeys[K: Object, E] +private class ArrayMapKeys[K, E] super RemovableCollection[K] # The original map var map: ArrayMap[K, E] @@ -638,7 +638,7 @@ private class ArrayMapKeys[K: Object, E] redef fun remove_all(key) do self.remove(key) end -private class ArrayMapValues[K: Object, E] +private class ArrayMapValues[K, E] super RemovableCollection[E] # The original map var map: ArrayMap[K, E] diff --git a/lib/standard/collection/hash_collection.nit b/lib/standard/collection/hash_collection.nit index d389c5a..f3857293 100644 --- a/lib/standard/collection/hash_collection.nit +++ b/lib/standard/collection/hash_collection.nit @@ -10,13 +10,18 @@ # You are allowed to redistribute it and sell it, alone or is a part of # another product. -# Introduce Hashmap and Hashset. +# Introduce `HashMap` and `HashSet`. module hash_collection import array +redef class Map[K, V] + # Get a `HashMap[K, V]` as default implementation + new do return new HashMap[K, V] +end + # A HashCollection is an array of HashNode[K] indexed by the K hash value -private abstract class HashCollection[K: Object] +private abstract class HashCollection[K] type N: HashNode[K] var array: nullable NativeArray[nullable N] = null # Used to store items @@ -35,12 +40,14 @@ private abstract class HashCollection[K: Object] # Return the index of the key k fun index_at(k: K): Int do + if k == null then return 0 + var i = k.hash % _capacity if i < 0 then i = - i return i end - # Return the node assosiated with the key + # Return the node associated with the key fun node_at(k: K): nullable N do # cache: `is` is used instead of `==` because it is a faster filter (even if not exact) @@ -52,7 +59,7 @@ private abstract class HashCollection[K: Object] return res end - # Return the node assosiated with the key (but with the index already known) + # Return the node associated with the key (but with the index already known) fun node_at_idx(i: Int, k: K): nullable N do var c = _array[i] @@ -190,7 +197,7 @@ private abstract class HashCollection[K: Object] end end -private abstract class HashNode[K: Object] +private abstract class HashNode[K] var key: K type N: HashNode[K] var next_item: nullable N = null @@ -199,9 +206,20 @@ private abstract class HashNode[K: Object] var next_in_bucklet: nullable N = null end -# A map implemented with a hash table. -# Keys of such a map cannot be null and require a working `hash` method -class HashMap[K: Object, V] +# A `Map` implemented with a hash table. +# +# ~~~ +# var map = new HashMap[nullable String, Int] +# map[null] = 0 +# map["one"] = 1 +# map["two"] = 2 +# +# assert map[null] == 0 +# assert map["one"] == 1 +# assert map.keys.has("two") +# assert map.values.length == 3 +# ~~~ +class HashMap[K, V] super Map[K, V] super HashCollection[K] @@ -249,7 +267,7 @@ class HashMap[K: Object, V] end # View of the keys of a HashMap -private class HashMapKeys[K: Object, V] +private class HashMapKeys[K, V] super RemovableCollection[K] # The original map var map: HashMap[K, V] @@ -270,7 +288,7 @@ private class HashMapKeys[K: Object, V] end # View of the values of a Map -private class HashMapValues[K: Object, V] +private class HashMapValues[K, V] super RemovableCollection[V] # The original map var map: HashMap[K, V] @@ -340,14 +358,14 @@ private class HashMapValues[K: Object, V] end end -private class HashMapNode[K: Object, V] +private class HashMapNode[K, V] super HashNode[K] redef type N: HashMapNode[K, V] var value: V end # A `MapIterator` over a `HashMap`. -class HashMapIterator[K: Object, V] +class HashMapIterator[K, V] super MapIterator[K, V] redef fun is_ok do return _node != null diff --git a/lib/standard/string.nit b/lib/standard/string.nit index c4ae7b0..f1d3288 100644 --- a/lib/standard/string.nit +++ b/lib/standard/string.nit @@ -2174,7 +2174,7 @@ redef class Map[K,V] var i = iterator var k = i.key var e = i.item - s.append("{k}{couple_sep}{e or else ""}") + s.append("{k or else ""}{couple_sep}{e or else ""}") # Concat other items i.next @@ -2182,7 +2182,7 @@ redef class Map[K,V] s.append(sep) k = i.key e = i.item - s.append("{k}{couple_sep}{e or else ""}") + s.append("{k or else ""}{couple_sep}{e or else ""}") i.next end return s.to_s diff --git a/src/semantize/typing.nit b/src/semantize/typing.nit index ae697d4..8fb3852 100644 --- a/src/semantize/typing.nit +++ b/src/semantize/typing.nit @@ -975,7 +975,7 @@ redef class AForExpr is_col = true end - if mapit_cla != null and v.is_subtype(ittype, mapit_cla.get_mtype([objcla.mclass_type, objcla.mclass_type.as_nullable])) then + if mapit_cla != null and v.is_subtype(ittype, mapit_cla.get_mtype([objcla.mclass_type.as_nullable, objcla.mclass_type.as_nullable])) then # Map Iterator var coltype = ittype.supertype_to(v.mmodule, v.anchor, mapit_cla) var variables = self.variables