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

Dispassion

#4532356 – Ditchwater

That link does not really answer my question on how to actually migrate my code. What are the best practices/idioms etc? And, lastly, I still do not have an equivalent of floorEntry – Dispassion

Answer 1

Scala 2.12 has mutable.TreeMap finally: https://github.com/scala/scala/pull/4504

Dispassion

Answer 2

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.

Howe

Is there an implementation of mutable.TreeMap and/or IntervalMap itself in a reputable Scala library? – Dispassion

Answer 3

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.

Lecythus

Is from and to, O(log n) for TreeMaps?? If not, in your code, operations are not logarithmic... Btw, here is my implementation in Scala (it is O(n) and not O(log n) where n is number of segements: github.com/pathikrit/scalgos/blob/master/src/main/scala/com/… The Java one I linked above is O(log n). – Dispassion

Why shouldn't it be in O(log n)? It's more or less the same operation as ceil and floor, but instead of just walking down the tree to a leaf node, you walk down the tree, and store your path in a list of size O(log n), eventually pruning one of two children of the visited nodes. If you want, you can look at the implementation of the underlying RedBlackTree here: github.com/scala/scala/blob/v2.11.4/src/library/scala/… , especially at the doFrom method, which seems to be kind of 'recursive work-horse' for the actual from method. – Lecythus

Answer 4

It seems like you want to use the nice Scala collections features. I don't think you need to reimplement your class.

Have you seen scala.collection.JavaConversions?

You might follow a similar approach with a wrapper and then implement the methods you want accordingly. You might need to be more creative with how you define and then use methods unique to your kind of map, but shouldn't be a big deal.

I hope this gives you an idea. Let me know if you need more guidance and I could help you out (it looks like it's been a while since you asked).

Thin