Vavr: LinkedHashMap.put should replace existing entry and maintain order

[thekaratekid05]

I noticed a difference between the java and javaslang 'put' implementations on LinkedHashMap

My assumption is that a 'put' should replace the existing entry and also maintain the original insertion order

@Test
  public void javaPutWithExistingKeyShouldReplaceExistingEntryAndMaintainOrder() {
    java.util.LinkedHashMap<Integer, String> javaMap = new java.util.LinkedHashMap<>();
    javaMap.put(1, "won");
    javaMap.put(2, "two");
    javaMap.put(1, "one");

    assertThat(javaMap).containsExactly(entry(1, "one"), entry(2, "two"));

  }

  @Test
  public void javaslangPutWithExistingKeyShouldReplaceExistingEntryAndMaintainOrder() {
    javaslang.collection.LinkedHashMap<Integer, String> javaslangMap =
          javaslang.collection.LinkedHashMap.<Integer, String>empty()
                .put(1, "won")
                .put(2, "two")
                .put(1, "one");

    // FAILS ASSERTION:
    assertThat(javaslangMap).containsExactly(Tuple.of(1, "one"), Tuple.of(2, "two"));
  }

[danieldietrich]

I remember that topic popped up a while ago. Before we change it I want to ensure that other immutable implementations act the same. When looking at Java and Scala, there are currently only immutable versions of LinkedHashMap.

[thekaratekid05]

alas it seems Scala behaves the same

scala> import collection.immutable.ListMap
import collection.immutable.ListMap

scala> val map = ListMap(1 -> 1, 2 -> 2, 3 -> 3)
map: scala.collection.immutable.ListMap[Int,Int] = ListMap(1 -> 1, 2 -> 2, 3 -> 3)

scala> val updated = map + (2 -> 20)
updated: scala.collection.immutable.ListMap[Int,Int] = ListMap(1 -> 1, 3 -> 3, 2 -> 20)

[danieldietrich]

We align to Scala. Changing the behavior is currently out of scope.

[yuriykulikov]

Hello everyone.
This is very unfortunate. Java LinkedHashMap retains insertion order in values() iterator.
Is there still any possibility the behavior of Vavr LinkedHashMap will be chagned?

[ruslansennov]

@danieldietrich , I agree with @yuriykulikov
Currently there is no way to keep order when existing key/value pair replaced. I believe LHM should do it, then both behavior will be possible

[yuriykulikov]

Would you prefer a pull request or to implement it yourselves? This is, in case you decide it makes sense:-)

Should be a small change in

@Override
    public LinkedHashMap<K, V> put(K key, V value) {
        Queue<Tuple2<K, V>> newList = list;
        HashMap<K, V> newMap = map;
        if (containsKey(key)) {
            //find the index of the element in the list, remove by index, insert using the same index
            //this will effectively retain the position in the list
            newList = newList.filter(t -> !Objects.equals(t._1, key));
            newMap = newMap.remove(key);
        }
        newList = newList.append(Tuple.of(key, value));
        newMap = newMap.put(key, value);
        return new LinkedHashMap<>(newList, newMap);
    }

[danieldietrich]

@yuriykulikov ok, we can do that. PR's welcome!

[danieldietrich]

I'm not sure we need to remove the entry if the key is already contained, see newMap = newMap.remove(key);. The put operation should overwrite the entry in the Map. Omitting the remove operation is faster. Right, @ruslansennov ?

[ruslansennov]

Yep

[ruslansennov]

~It seems we should do nothing except put new key/value pair into map~

[danieldietrich]

For example

    @Override
    public LinkedHashMap<K, V> put(K key, V value) {
        if (contains(key)) {
            return replaceValue(key, value);
        } else {
            final Queue<Tuple2<K, V>> newList = list.append(Tuple.of(key, value));
            final HashMap<K, V> newMap = map.put(key, value);
            return new LinkedHashMap<>(newList, newMap);
        }
    }

Update: replaceValue calls put 🙈=> StackOverflow

    @Override
    public LinkedHashMap<K, V> put(K key, V value) {
        final Queue<Tuple2<K, V>> newList;
        if (contains(key)) {
            newList = list.replace(list.find(t -> Objects.equals(t._1, key)).get(), Tuple.of(key, value));
        } else {
            newList = list.append(Tuple.of(key, value));
        }
        final HashMap<K, V> newMap = map.put(key, value);
        return new LinkedHashMap<>(newList, newMap);
    }

@yuriykulikov @ruslansennov I think we should overwrite an existing entry in each case, even if new value and old value are equal. The objects might be different, depending on the equals implementation!

[danieldietrich]

Idea: More Traversable.replace methods would be nice in order to simplify list.replace(list.find(...), ...):

• replaceIf(Predicate<? super T>, T) - replaces the first occurrence
• replaceAllIf(Predicate<? super T>, T) - replaces all occurrences

But that is another issue, I will create one... Mmh, maybe there are too many different use-cases. Also having a Function that transforms the old value to a new value and so on. I think we will leave this new functions away for now.

[yuriykulikov]

I see you have already implemented everything while I was forking/cloning :-)

[danieldietrich]

I have another optimization... please wait a minute

[danieldietrich]

We can fuse the get and the find operations (which are O(n)) by trading them with one Option instance:

    @Override
    public LinkedHashMap<K, V> put(K key, V value) {
        final Queue<Tuple2<K, V>> newList;
        final Option<Tuple2<K, V>> currentEntry = get(key);
        if (currentEntry.isDefined()) {
            newList = list.replace(currentEntry.get(), Tuple.of(key, value));
        } else {
            newList = list.append(Tuple.of(key, value));
        }
        final HashMap<K, V> newMap = map.put(key, value);
        return new LinkedHashMap<>(newList, newMap);
    }

[yuriykulikov]

One list traversal less, right?

[danieldietrich]

Yes

[ruslansennov]

get and the find operations (which are O(n))

No, both are O(1) because of underlying HashMap

[yuriykulikov]

you can use wrap(newList, newMap) instead of new LinkedHashMap<>(newList, newMap) while you are at it:-)

[danieldietrich]

@ruslansennov but we save a find on the Queue

[yuriykulikov]

list.replace is O(n) I believe, find() as well. My initial suggestion with index will also be O(n) since it is a linked list. It does not get faster than the last variant by Daniel.

[danieldietrich]

Yes

[anubliss]

Hi, can you please let me know how to achieve the opposite requirement of this?
I would like to reset the order when I remove and insert the same key with different values.

[nfekete]

@anubliss remove first and then add?