Fix bug in LinkedHashMap#ofEntries(): list of tuples in some case can contains more elements that contains map itself (#2226)

danieldietrich · danieldietrich · commit 562967a4dfa5 · 2019-01-06T23:44:47.000+01:00
* Fix bug in LinkedHashMap#ofEntries(): list of tuples in some case can contains more elements that contains map itself

* Fix construct of LinkedHashMap in case where initial sequence contains duplicate keys
diff --git a/vavr/src/main/java/io/vavr/collection/LinkedHashMap.java b/vavr/src/main/java/io/vavr/collection/LinkedHashMap.java
@@ -100,7 +100,7 @@ public static <K, V> LinkedHashMap<K, V> narrow(LinkedHashMap<? extends K, ? ext
     public static <K, V> LinkedHashMap<K, V> of(Tuple2<? extends K, ? extends V> entry) {
         final HashMap<K, V> map = HashMap.of(entry);
         final Queue<Tuple2<K, V>> list = Queue.of((Tuple2<K, V>) entry);
-        return new LinkedHashMap<>(list, map);
+        return wrap(list, map);
     }
 
     /**
@@ -164,7 +164,7 @@ public static <T, K, V> LinkedHashMap<K, V> ofAll(java.util.stream.Stream<? exte
     public static <K, V> LinkedHashMap<K, V> of(K key, V value) {
         final HashMap<K, V> map = HashMap.of(key, value);
         final Queue<Tuple2<K, V>> list = Queue.of(Tuple.of(key, value));
-        return new LinkedHashMap<>(list, map);
+        return wrap(list, map);
     }
 
     /**
@@ -181,7 +181,7 @@ public static <K, V> LinkedHashMap<K, V> of(K key, V value) {
     public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2) {
         final HashMap<K, V> map = HashMap.of(k1, v1, k2, v2);
         final Queue<Tuple2<K, V>> list = Queue.of(Tuple.of(k1, v1), Tuple.of(k2, v2));
-        return new LinkedHashMap<>(list, map);
+        return wrapNonUnique(list, map);
     }
 
     /**
@@ -200,7 +200,7 @@ public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2) {
     public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
         final HashMap<K, V> map = HashMap.of(k1, v1, k2, v2, k3, v3);
         final Queue<Tuple2<K, V>> list = Queue.of(Tuple.of(k1, v1), Tuple.of(k2, v2), Tuple.of(k3, v3));
-        return new LinkedHashMap<>(list, map);
+        return wrapNonUnique(list, map);
     }
 
     /**
@@ -221,7 +221,7 @@ public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3)
     public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
         final HashMap<K, V> map = HashMap.of(k1, v1, k2, v2, k3, v3, k4, v4);
         final Queue<Tuple2<K, V>> list = Queue.of(Tuple.of(k1, v1), Tuple.of(k2, v2), Tuple.of(k3, v3), Tuple.of(k4, v4));
-        return new LinkedHashMap<>(list, map);
+        return wrapNonUnique(list, map);
     }
 
     /**
@@ -244,7 +244,7 @@ public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3,
     public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
         final HashMap<K, V> map = HashMap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5);
         final Queue<Tuple2<K, V>> list = Queue.of(Tuple.of(k1, v1), Tuple.of(k2, v2), Tuple.of(k3, v3), Tuple.of(k4, v4), Tuple.of(k5, v5));
-        return new LinkedHashMap<>(list, map);
+        return wrapNonUnique(list, map);
     }
 
     /**
@@ -269,7 +269,7 @@ public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3,
     public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6) {
         final HashMap<K, V> map = HashMap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5, k6, v6);
         final Queue<Tuple2<K, V>> list = Queue.of(Tuple.of(k1, v1), Tuple.of(k2, v2), Tuple.of(k3, v3), Tuple.of(k4, v4), Tuple.of(k5, v5), Tuple.of(k6, v6));
-        return new LinkedHashMap<>(list, map);
+        return wrapNonUnique(list, map);
     }
 
     /**
@@ -296,7 +296,7 @@ public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3,
     public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7) {
         final HashMap<K, V> map = HashMap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5, k6, v6, k7, v7);
         final Queue<Tuple2<K, V>> list = Queue.of(Tuple.of(k1, v1), Tuple.of(k2, v2), Tuple.of(k3, v3), Tuple.of(k4, v4), Tuple.of(k5, v5), Tuple.of(k6, v6), Tuple.of(k7, v7));
-        return new LinkedHashMap<>(list, map);
+        return wrapNonUnique(list, map);
     }
 
     /**
@@ -325,7 +325,7 @@ public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3,
     public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7, K k8, V v8) {
         final HashMap<K, V> map = HashMap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5, k6, v6, k7, v7, k8, v8);
         final Queue<Tuple2<K, V>> list = Queue.of(Tuple.of(k1, v1), Tuple.of(k2, v2), Tuple.of(k3, v3), Tuple.of(k4, v4), Tuple.of(k5, v5), Tuple.of(k6, v6), Tuple.of(k7, v7), Tuple.of(k8, v8));
-        return new LinkedHashMap<>(list, map);
+        return wrapNonUnique(list, map);
     }
 
     /**
@@ -356,7 +356,7 @@ public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3,
     public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9) {
         final HashMap<K, V> map = HashMap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5, k6, v6, k7, v7, k8, v8, k9, v9);
         final Queue<Tuple2<K, V>> list = Queue.of(Tuple.of(k1, v1), Tuple.of(k2, v2), Tuple.of(k3, v3), Tuple.of(k4, v4), Tuple.of(k5, v5), Tuple.of(k6, v6), Tuple.of(k7, v7), Tuple.of(k8, v8), Tuple.of(k9, v9));
-        return new LinkedHashMap<>(list, map);
+        return wrapNonUnique(list, map);
     }
 
     /**
@@ -389,7 +389,7 @@ public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3,
     public static <K, V> LinkedHashMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9, K k10, V v10) {
         final HashMap<K, V> map = HashMap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5, k6, v6, k7, v7, k8, v8, k9, v9, k10, v10);
         final Queue<Tuple2<K, V>> list = Queue.of(Tuple.of(k1, v1), Tuple.of(k2, v2), Tuple.of(k3, v3), Tuple.of(k4, v4), Tuple.of(k5, v5), Tuple.of(k6, v6), Tuple.of(k7, v7), Tuple.of(k8, v8), Tuple.of(k9, v9), Tuple.of(k10, v10));
-        return new LinkedHashMap<>(list, map);
+        return wrapNonUnique(list, map);
     }
 
     /**
@@ -442,7 +442,7 @@ public static <K, V> LinkedHashMap<K, V> ofEntries(java.util.Map.Entry<? extends
             map = map.put(tuple);
             list = list.append(tuple);
         }
-        return wrap(list, map);
+        return wrapNonUnique(list, map);
     }
 
     /**
@@ -457,7 +457,7 @@ public static <K, V> LinkedHashMap<K, V> ofEntries(java.util.Map.Entry<? extends
     public static <K, V> LinkedHashMap<K, V> ofEntries(Tuple2<? extends K, ? extends V>... entries) {
         final HashMap<K, V> map = HashMap.ofEntries(entries);
         final Queue<Tuple2<K, V>> list = Queue.of((Tuple2<K, V>[]) entries);
-        return wrap(list, map);
+        return wrapNonUnique(list, map);
     }
 
     /**
@@ -480,7 +480,7 @@ public static <K, V> LinkedHashMap<K, V> ofEntries(Iterable<? extends Tuple2<? e
                 map = map.put(entry);
                 list = list.append((Tuple2<K, V>) entry);
             }
-            return wrap(list, map);
+            return wrapNonUnique(list, map);
         }
     }
 
@@ -738,7 +738,7 @@ public LinkedHashMap<K, V> put(K key, V value) {
             newList = list.append(Tuple.of(key, value));
         }
         final HashMap<K, V> newMap = map.put(key, value);
-        return new LinkedHashMap<>(newList, newMap);
+        return wrap(newList, newMap);
     }
 
     @Override
@@ -952,10 +952,32 @@ public String toString() {
         return mkString(stringPrefix() + "(", ", ", ")");
     }
 
+    /**
+     * Construct Map with given values and key order.
+     *
+     * @param list The list of key-value tuples with unique keys.
+     * @param map  The map of key-value tuples.
+     * @param <K>  The key type
+     * @param <V>  The value type
+     * @return A new Map containing the given map with given key order
+     */
     private static <K, V> LinkedHashMap<K, V> wrap(Queue<Tuple2<K, V>> list, HashMap<K, V> map) {
         return list.isEmpty() ? empty() : new LinkedHashMap<>(list, map);
     }
 
+    /**
+     * Construct Map with given values and key order.
+     *
+     * @param list The list of key-value tuples with non-unique keys.
+     * @param map  The map of key-value tuples.
+     * @param <K>  The key type
+     * @param <V>  The value type
+     * @return A new Map containing the given map with given key order
+     */
+    private static <K, V> LinkedHashMap<K, V> wrapNonUnique(Queue<Tuple2<K, V>> list, HashMap<K, V> map) {
+        return list.isEmpty() ? empty() : new LinkedHashMap<>(list.reverse().distinctBy(Tuple2::_1).reverse().toQueue(), map);
+    }
+
     // We need this method to narrow the argument of `ofEntries`.
     // If this method is static with type args <K, V>, the jdk fails to infer types at the call site.
     private LinkedHashMap<K, V> createFromEntries(Iterable<Tuple2<K, V>> tuples) {
diff --git a/vavr/src/test/java/io/vavr/collection/AbstractMapTest.java b/vavr/src/test/java/io/vavr/collection/AbstractMapTest.java
@@ -31,6 +31,7 @@
 import java.security.MessageDigest;
 import java.util.*;
 import java.util.Set;
+import java.util.concurrent.atomic.AtomicInteger;
 import java.util.function.BiConsumer;
 import java.util.function.BinaryOperator;
 import java.util.function.Function;
@@ -152,6 +153,8 @@ protected boolean emptyMapShouldBeSingleton() {
     @SuppressWarnings("unchecked")
     protected abstract <K extends Comparable<? super K>, V> Map<K, V> mapOfTuples(Tuple2<? extends K, ? extends V>... entries);
 
+    protected abstract <K extends Comparable<? super K>, V> Map<K, V> mapOfTuples(Iterable<? extends Tuple2<? extends K, ? extends V>> entries);
+
     @SuppressWarnings("unchecked")
     protected abstract <K extends Comparable<? super K>, V> Map<K, V> mapOfEntries(java.util.Map.Entry<? extends K, ? extends V>... entries);
 
@@ -308,13 +311,32 @@ public void shouldConstructFromJavaStream() {
         assertThat(map).isEqualTo(this.<String, Integer> emptyMap().put("1", 1).put("2", 2).put("3", 3));
     }
 
+    @Test
+    public void shouldConstructFromJavaStreamWithDuplicatedKeys() {
+        assertThat(mapOf(Stream.range(0, 4).toJavaStream()
+                , i -> Math.max(1, Math.min(i, 2))
+                , i -> String.valueOf(i + 1)
+        ))
+                .hasSize(2)
+                .isEqualTo(mapOf(1, "2", 2, "4"));
+    }
+
     @Test
     public void shouldConstructFromJavaStreamEntries() {
         final java.util.stream.Stream<Integer> javaStream = java.util.stream.Stream.of(1, 2, 3);
         final Map<String, Integer> map = mapOf(javaStream, i -> Tuple.of(String.valueOf(i), i));
         assertThat(map).isEqualTo(this.<String, Integer> emptyMap().put("1", 1).put("2", 2).put("3", 3));
     }
 
+    @Test
+    public void shouldConstructFromJavaStreamEntriesWithDuplicatedKeys() {
+        assertThat(mapOf(Stream.range(0, 4).toJavaStream(), i ->
+                Map.entry(Math.max(1, Math.min(i, 2)), String.valueOf(i + 1))
+        ))
+                .hasSize(2)
+                .isEqualTo(mapOf(1, "2", 2, "4"));
+    }
+
     @Test
     @SuppressWarnings("unchecked")
     public void shouldConstructFromUtilEntries() {
@@ -325,19 +347,99 @@ public void shouldConstructFromUtilEntries() {
 
     @Test
     @SuppressWarnings("unchecked")
-    public void shouldConstructFromEntries() {
+    public void shouldConstructFromUtilEntriesWithDuplicatedKeys() {
+        assertThat(mapOfEntries(
+                asJavaEntry(1, "1"), asJavaEntry(1, "2"),
+                asJavaEntry(2, "3"), asJavaEntry(2, "4")
+        ))
+                .hasSize(2)
+                .isEqualTo(mapOf(1, "2", 2, "4"));
+    }
+
+    @Test
+    @SuppressWarnings("unchecked")
+    public void shouldConstructFromEntriesVararg() {
         final Map<String, Integer> actual = mapOfTuples(Map.entry("1", 1), Map.entry("2", 2), Map.entry("3", 3));
         final Map<String, Integer> expected = this.<String, Integer>emptyMap().put("1", 1).put("2", 2).put("3", 3);
         assertThat(actual).isEqualTo(expected);
     }
 
+    @Test
+    @SuppressWarnings("unchecked")
+    public void shouldConstructFromEntriesVarargWithDuplicatedKeys() {
+        assertThat(mapOfTuples(
+                Map.entry(1, "1"), Map.entry(1, "2"),
+                Map.entry(2, "3"), Map.entry(2, "4")
+        ))
+                .hasSize(2)
+                .isEqualTo(mapOf(1, "2", 2, "4"));
+    }
+
+    @Test
+    public void shouldConstructFromEntriesIterable() {
+        final Map<String, Integer> actual = mapOfTuples(asList(Map.entry("1", 1), Map.entry("2", 2), Map.entry("3", 3)));
+        final Map<String, Integer> expected = this.<String, Integer>emptyMap().put("1", 1).put("2", 2).put("3", 3);
+        assertThat(actual).isEqualTo(expected);
+    }
+
+    @Test
+    public void shouldConstructFromEntriesIterableWithDuplicatedKeys() {
+        assertThat(mapOfTuples(asList(
+                Map.entry(1, "1"), Map.entry(1, "2"),
+                Map.entry(2, "3"), Map.entry(2, "4")
+        )))
+                .hasSize(2)
+                .isEqualTo(mapOf(1, "2", 2, "4"));
+    }
+
     @Test
     public void shouldConstructFromPairs() {
         final Map<String, Integer> actual = mapOf("1", 1, "2", 2, "3", 3);
         final Map<String, Integer> expected = this.<String, Integer>emptyMap().put("1", 1).put("2", 2).put("3", 3);
         assertThat(actual).isEqualTo(expected);
     }
 
+    @Test
+    public void shouldConstructFromPairsWithDuplicatedKeys() {
+        final Map<Integer, String> actual = mapOf(1, "1", 1, "2", 2, "3");
+        final Map<Integer, String> expected = this.<Integer, String>emptyMap().put(1, "2").put(2, "3");
+        assertThat(actual).isEqualTo(expected);
+    }
+
+    @Test
+    public void shouldConstructWithTabulate() {
+        final Map<String, Integer> actual = mapTabulate(4, i -> Tuple.of(i.toString(), i));
+        final Map<String, Integer> expected = this.<String, Integer>emptyMap().put("0", 0).put("1", 1).put("2", 2).put("3", 3);
+        assertThat(actual).isEqualTo(expected);
+    }
+
+    @Test
+    public void shouldConstructWithTabulateWithDuplicatedKeys() {
+        assertThat(mapTabulate(4, i ->
+                Tuple.of(Math.max(1, Math.min(i, 2)), String.valueOf(i + 1))
+        ))
+                .hasSize(2)
+                .isEqualTo(mapOf(1, "2", 2, "4"));
+    }
+
+    @Test
+    public void shouldConstructWithFill() {
+        AtomicInteger i = new AtomicInteger();
+        final Map<String, Integer> actual = mapFill(4, () -> Tuple.of(String.valueOf(i.get()), i.getAndIncrement()));
+        final Map<String, Integer> expected = this.<String, Integer>emptyMap().put("0", 0).put("1", 1).put("2", 2).put("3", 3);
+        assertThat(actual).isEqualTo(expected);
+    }
+
+    @Test
+    public void shouldConstructWithFillWithDuplicatedKeys() {
+        AtomicInteger i = new AtomicInteger();
+        assertThat(mapFill(4, () ->
+                Tuple.of(Math.max(1, Math.min(i.get(), 2)), String.valueOf(i.getAndIncrement() + 1))
+        ))
+                .hasSize(2)
+                .isEqualTo(mapOf(1, "2", 2, "4"));
+    }
+
     // -- equality
 
     @Test
diff --git a/vavr/src/test/java/io/vavr/collection/HashMapTest.java b/vavr/src/test/java/io/vavr/collection/HashMapTest.java
@@ -61,6 +61,11 @@ protected final <K extends Comparable<? super K>, V> HashMap<K, V> mapOfTuples(T
         return HashMap.ofEntries(entries);
     }
 
+    @Override
+    protected <K extends Comparable<? super K>, V> Map<K, V> mapOfTuples(Iterable<? extends Tuple2<? extends K, ? extends V>> entries) {
+        return HashMap.ofEntries(entries);
+    }
+
     @SuppressWarnings("varargs")
     @SafeVarargs
     @Override
diff --git a/vavr/src/test/java/io/vavr/collection/LinkedHashMapTest.java b/vavr/src/test/java/io/vavr/collection/LinkedHashMapTest.java
@@ -42,6 +42,11 @@ protected final <K extends Comparable<? super K>, V> LinkedHashMap<K, V> mapOfTu
         return LinkedHashMap.ofEntries(entries);
     }
 
+    @Override
+    protected <K extends Comparable<? super K>, V> Map<K, V> mapOfTuples(Iterable<? extends Tuple2<? extends K, ? extends V>> entries) {
+        return LinkedHashMap.ofEntries(entries);
+    }
+
     @SuppressWarnings("varargs")
     @SafeVarargs
     @Override
diff --git a/vavr/src/test/java/io/vavr/collection/TreeMapTest.java b/vavr/src/test/java/io/vavr/collection/TreeMapTest.java
@@ -78,6 +78,11 @@ protected final <K extends Comparable<? super K>, V> TreeMap<K, V> mapOfTuples(T
         return TreeMap.ofEntries(entries);
     }
 
+    @Override
+    protected <K extends Comparable<? super K>, V> Map<K, V> mapOfTuples(Iterable<? extends Tuple2<? extends K, ? extends V>> entries) {
+        return TreeMap.ofEntries(entries);
+    }
+
     @SuppressWarnings("varargs")
     @SafeVarargs
     @Override
