Migrating Java TreeMap code to Scala?

Question

I am migrating my Java code base to pure Scala and I am stuck on this one piece of code. I have an implementation of an IntervalMap i.e. a data structures that let's you efficiently map ranges [from,to] to values where the set, delete and get operations are all O(log n) (slightly different from an IntervalTree or a SegmentTree).

This code uses Java's java.util.TreeMaps and while migrating to Scala, I ran into 2 big issues:

1. Scala has no mutable.TreeMap - I decided to go around it by using mutable.TreeSet (oddly Scala has mutable.TreeSet but no mutable.TreeMap) for storing the keys and storing the values in an auxiliary mutable.Map. This is an unpleasant hack but is there any better way?

2. Next problem is Scala's mutable.TreeSet has no equivalent of java.util.TreeSet's ceilingKey, floorEntry, pollFirst, pollLast which are all O(log n) operations in Java.

So, how can I best migrate my code to Scala? What are the best practices in these situations? I really do not want to write my own tree implementations. Is there a more idiomatic Scala way of writing IntervalMaps that I am not aware of? Or is there some reputable library out there? Or does Scala just plain suck here with its gimped TreeSet and non-existent TreeMaps. Ofcourse I can just use Java's TreeMap in Scala but that is ugly and I lose all the nice Scala collection features and I might as well use Java then.

Here is my current Java code: https://gist.github.com/pathikrit/5574521

Answer 1

The answer is, unfortunately, to just use the Java TreeMap class.

Scala doesn't have its own copy of everything, and this is one of the most notable exceptions. One of the reasons it's Java-compatible is so that you don't have to re-invent every wheel.

The reason you still want to use Scala is that not every bit of code you write is about this TreeMap. Your IntervalMap can be a Scala IntervalMap; you just use the Java TreeMap internally to implement it. Or you could use the immutable version in Scala, which now performs reasonably well for an immutable version.

Perhaps in 2.11 or 2.12 there will be a mutable TreeMap; it requires someone to write it, test it, optimize it, etc., but I don't think there's a philosophical objection to having it.

Answer 2

1) What's the problem with using an immutable TreeMap internally? It's more or less just as efficient as mutable tree map, does everything in O(log n).

2) In the Scala version, there is no ceilingKey and floorKey, but instead one has methods from and to that do essentially the same, but return a whole subtree instead of single entries.

Full 1:1 port of Java-code:

import scala.collection._
import scala.collection.immutable.TreeMap

case class Segment[T](start: Int, end: Int, value: T) {
  def contains(x: Int) = (start <= x) && (x < end)
  override def toString = "[%d,%d:%s]".format(start, end, value)
}

class IntervalMap[T] {
  private var segments = new TreeMap[Int, Segment[T]]
  private def add(s: Segment[T]): Unit = segments += (s.start -> s)
  private def destroy(s: Segment[T]): Unit = segments -= s.start
  def ceiling(x: Int): Option[Segment[T]] = {
    val from = segments.from(x)
    if (from.isEmpty) None
    else Some(segments(from.firstKey))
  }
  def floor(x: Int): Option[Segment[T]] = {
    val to = segments.to(x)
    if (to.isEmpty) None
    else Some(segments(to.lastKey))
  }
  def find(x: Int): Option[Segment[T]] = {
    floor(x).filter(_ contains x).orElse(ceiling(x))
  }

  // This is replacement of `set`, used as myMap(s,e) = v
  def update(x: Int, y: Int, value: T): Unit = {
    require(x < y)
    find(x) match {
      case None => add(Segment[T](x, y, value))
      case Some(s) => {
        if (x < s.start) {
          if (y <= s.start) {
            add(Segment[T](x, y, value))
          } else if (y < s.end) {
            destroy(s)
            add(Segment[T](x, y, value))
            add(Segment[T](y, s.end, s.value))
          } else {
            destroy(s)
            add(Segment[T](x, s.end, value))
            this(s.end, y) = value
          }
        } else if (x < s.end) {
          destroy(s)
          add(Segment[T](s.start, x, s.value))
          if (y < s.end) {
            add(Segment[T](x, y, value))
            add(Segment[T](y, s.end, s.value))
          } else {
            add(Segment[T](x, s.end, value))
            this(s.end, y) = value
          }
        } else {
          throw new IllegalStateException
        }
      }
    }
  }

  def get(x: Int): Option[T] = {
    for (seg <- floor(x); if (seg contains x)) yield seg.value
  }

  def apply(x: Int) = get(x).getOrElse{
    throw new NoSuchElementException(
      "No value set at index " + x
    )
  }

  override def toString = segments.mkString("{", ",", "}")
}

// little demo
val m = new IntervalMap[String]
println(m)
m(10, 20) = "FOOOOOOOOO"
m(18, 30) = "_bar_bar_bar_"
m(5, 12) = "bazzz"
println(m)

for (x <- 1 to 42) printf("%3d -> %s\n",x,m.get(x))

Result:

{}
{5 -> [5,12:bazzz],12 -> [12,18:FOOOOOOOOO],18 -> [18,20:_bar_bar_bar_],20 -> [20,30:_bar_bar_bar_]}
  1 -> None
  2 -> None
  3 -> None
  4 -> None
  5 -> Some(bazzz)
  6 -> Some(bazzz)
  7 -> Some(bazzz)
  8 -> Some(bazzz)
  9 -> Some(bazzz)
 10 -> Some(bazzz)
 11 -> Some(bazzz)
 12 -> Some(FOOOOOOOOO)
 13 -> Some(FOOOOOOOOO)
 14 -> Some(FOOOOOOOOO)
 15 -> Some(FOOOOOOOOO)
 16 -> Some(FOOOOOOOOO)
 17 -> Some(FOOOOOOOOO)
 18 -> Some(_bar_bar_bar_)
 19 -> Some(_bar_bar_bar_)
 20 -> Some(_bar_bar_bar_)
 21 -> Some(_bar_bar_bar_)
 22 -> Some(_bar_bar_bar_)
 23 -> Some(_bar_bar_bar_)
 24 -> Some(_bar_bar_bar_)
 25 -> Some(_bar_bar_bar_)
 26 -> Some(_bar_bar_bar_)
 27 -> Some(_bar_bar_bar_)
 28 -> Some(_bar_bar_bar_)
 29 -> Some(_bar_bar_bar_)
 30 -> None
 31 -> None
 32 -> None
 33 -> None
 34 -> None
 35 -> None

The Segment class should be set private[yourPackage], some documentation should be added.