MultiDict.add should return this if no changes are made

[bblfish]

trafficstars

The add method is defined as follows

  def add(key: K, value: V): MultiDict[K, V] =
    new MultiDict(elems.updatedWith(key) {
      case None     => Some(Set(value))
      case Some(vs) => Some(vs + value)
    })

but elms.updatedWith could easily return the same MultiDict if the value is already in the Set[V]. It would help if the signature made sure that the same object would be returned if nothing changed as that would allow one to reduce unnecessary object creation (both in the call, and also in the creation of objects in the calling object. Otherwise one ends up creating a lot of garbage.

Something like this seems better:

def add(key: K, value: V): MultiDict[K, V] =
   val newElems = elems.updatedWith(key) {
      case None     => Some(Set(value))
      case Some(vs) => Some(vs + value) // if vs + value == vs then this will return the original MD I believe
    }
    if newElems eq this.elems then this
    else new MultiDict(newElems)

That is how incl in the standard scala library for HashSet works.

[SethTisue]

@scala/collections ?

[bblfish]

yes, in scala collections for example IntMap line 390, but I had found another example in a more widely used collection yesterday.

[bblfish]

I have a mini implementation of MultiDict for my needs in org/w3/banana/quiver/util/MultiDict.scala with tests that pass and two implementations of Graph that use it whose tests also pass.