Scala: build a map from the list of tuples, but crash if there are conflicting entries

Question

I think it could be a general operation. So maybe this is inside the API, but I cannot find it. I am also interested in an efficient functional / simple solution, if not.

Given the sequence of tuples ("a" -> 1, "b" ->2, "c" -> 3) , I want to turn it into a map. It is easy to use TraversableOnce.toMap . But I want to fail this construction if the final map “contains a contradiction”, that is, different values ​​assigned to the same key. As in the sequence ("a" -> 1, "a" -> 2) . But duplicates must be allowed.

I currently have this (very imperative) code:

 def buildMap[A,B](in: TraversableOnce[(A,B)]): Option[Map[A,B]] = { val map = new HashMap[A,B] val it = in.toIterator var fail = false while(it.hasNext){ val next = it.next() val old = map.put(next._1, next._2) fail = old.isDefined && old.get != next._2 } if(fail) None else Some(map.toMap) } 

Side question

Is the latest toMap necessary? I get a type error when it is absent, but I think this should work. The toMap implementation creates a new map that I want to avoid.

Answer 1

As always when working with Seq[A] optimal solution depends on the specific type of collection. A general, but not very effective solution is to add:

 def optMap[A,B](in: Iterable[(A,B)]): Option[Map[A,B]] = in.iterator.foldLeft(Option(Map[A,B]())) { case (Some(m),e @ (k,v)) if m.getOrElse(k, v) == v => Some(m + e) case _ => None } 

If you limit yourself to using List[A,B] , the optimized version will be:

 @tailrec def rmap[A,B](in: List[(A,B)], out: Map[A,B] = Map[A,B]()): Option[Map[A,B]] = in match { case (e @ (k,v)) :: tail if out.getOrElse(k,v) == v => rmap(tail, out + e) case Nil => Some(out) case _ => None } 

In addition, a less idiomatic version using changeable maps can be implemented:

 def mmap[A,B](in: Iterable[(A,B)]): Option[Map[A,B]] = { val dest = collection.mutable.Map[A,B]() for (e @ (k,v) <- in) { if (dest.getOrElse(k, v) != v) return None dest += e } Some(dest.toMap) } 

Answer 2

Here is a bad solution (if you create the whole card and then discard it in order):

 def uniqueMap[A,B](s: Seq[(A,B)]) = { val m = s.toMap if (m.size == s.length) Some(s) else None } 

Here is a mutable failover solution (as soon as an error is detected), follow these steps:

 def uniqueMap[A,B](s: Seq[(A,B)]) = { val h = new collection.mutable.HashMap[A,B] val i = s.iterator.takeWhile(x => !(h contains x._1)).foreach(h += _) if (h.size == s.length) Some(h) else None } 

And here is an indisputable fault tolerant solution:

 def uniqueMap[A,B](s: Seq[(A,B)]) = { def mapUniquely(i: Iterator[(A,B)], m: Map[A,B]): Option[Map[A,B]] = { if (i.hasNext) { val j = i.next if (m contains j._1) None else mapUniquely(i, m + j) } else Some(m) } mapUniquely(s.iterator, Map[A,B]()) } 

---

Edit: and here is a solution using put for speed (hopefully):

 def uniqueMap[A,B](s: Seq[(A,B)]) = { val h = new collection.mutable.HashMap[A,B] val okay = s.iterator.forall(x => { val y = (h put (x._1,x._2)) y.isEmpty || y.get == x._2 }) if (okay) Some(h) else None } 

Edit: now checked, and this is ~ 2x as fast at the input, which works (returns true) than Moritz 'or my direct solution.

Answer 3

Scala 2.9 is close, so why not use the combination method (based on Moritz’s answer):

 def optMap[A,B](in: List[(A,B)]) = { if (in.combinations(2).exists { case List((a,b),(c,d)) => a == c && b != d case _ => false }) None else Some(in.toMap) } scala> val in = List(1->1,2->3,3->4,4->5,2->3) in: List[(Int, Int)] = List((1,1), (2,3), (3,4), (4,5), (2,3)) scala> optMap(in) res29: Option[scala.collection.immutable.Map[Int,Int]] = Some(Map(1 -> 1, 2 -> 3, 3 -> 4, 4 -> 5)) scala> val in = List(1->1,2->3,3->4,4->5,2->3,1->2) in: List[(Int, Int)] = List((1,1), (2,3), (3,4), (4,5), (2,3), (1,2)) scala> optMap(in) res30: Option[scala.collection.immutable.Map[Int,Int]] = None 

Answer 4

You can also use gourpBy as follows:

  val pList = List(1 -> "a", 1 -> "b", 2 -> "c", 3 -> "d") def optMap[A,B](in: Iterable[(A,B)]): Option[Map[A,B]] = { Option(in.groupBy(_._1).map{case(_, list) => if(list.size > 1) return None else list.head}) } println(optMap(pList)) 

Efficiency competes with the above solutions. In fact, if you study the implementation of gourpBy, you will see that it is very similar to some of the proposed solutions.