mvc - ¿Está migrando código Java TreeMap a Scala?

spring java tutorial

Question

Estoy migrando mi base de código Java a Scala puro y estoy atascado en esta pieza de código . Tengo una implementación de un IntervalMap, es decir, una estructura de datos que le permite mapear de manera eficiente los rangos [from,to] a los values donde las operaciones de set , delete y get son todas O(log n) (ligeramente diferentes de un IntervalTree o un SegmentTree).

Este código utiliza java.util.TreeMaps de Java y, al migrar a Scala, me topé con 2 grandes problemas:

1. Scala no tiene mutable.TreeMap - Decidí darle una vuelta utilizando mutable.TreeSet (curiosamente Scala tiene mutable.TreeSet pero no mutable.TreeMap ) para almacenar las claves y almacenar los valores en un mutable.Map auxiliar. mutable.Map . Este es un truco desagradable pero ¿hay alguna manera mejor?

2. El siguiente problema es el mutable.TreeSet de Scala no tiene equivalente de ceilingKey , floorEntry , pollFirst , pollLast que son todas las operaciones O(log n) en Java.

Entonces, ¿cómo puedo migrar mejor mi código a Scala? ¿Cuáles son las mejores prácticas en estas situaciones? Realmente no quiero escribir mis propias implementaciones de árbol. ¿Hay alguna forma Scala más idiomática de escribir IntervalMaps de la que no tenga conocimiento? ¿O hay alguna biblioteca de buena reputación por ahí? ¿O es que Scala simplemente apesta aquí con su TreeSet simplificado y sus TreeMaps inexistentes? Por supuesto, solo puedo usar el TreeMap de Java en Scala, pero eso es feo y pierdo todas las buenas características de la colección de Scala y podría usar Java en ese momento.

Aquí está mi código Java actual: https://gist.github.com/pathikrit/5574521

Answer 1

1) ¿Cuál es el problema con el uso de un TreeMap inmutable internamente? Es más o menos tan eficiente como el mapa de árbol mutable, hace todo en O (log n).

2) En la versión de Scala, no hay ceilingKey ni floorKey , pero en cambio uno tiene métodos from y to eso hacen lo mismo, pero devuelven un subárbol completo en lugar de entradas individuales.

Puerto 1: 1 completo de código Java:

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))

Resultado:

{}
{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

La clase de Segment debe establecerse como private[yourPackage] , se debe agregar alguna documentación.

Answer 2

La respuesta es, desafortunadamente, simplemente usar la clase Java TreeMap .

Scala no tiene su propia copia de todo, y esta es una de las excepciones más notables. Una de las razones por las que es compatible con Java es para que no tenga que reinventar cada rueda.

La razón por la que aún desea utilizar Scala es que no todos los bits de código que escribe son sobre este TreeMap . Su IntervalMap puede ser un IntervalMap Scala; solo usas Java TreeMap internamente para implementarlo. O podría usar la versión inmutable en Scala, que ahora funciona razonablemente bien para una versión inmutable.

Tal vez en 2.11 o 2.12 habrá un TreeMap mutable; requiere que alguien lo escriba, lo pruebe, lo optimice, etc., pero no creo que haya una objeción filosófica para tenerlo.

Answer 3

Parece que quieres usar las bonitas características de las colecciones de Scala. No creo que necesites reimplementar tu clase.

¿Has visto scala.collection.JavaConversions ?

Puede seguir un enfoque similar con un envoltorio y luego implementar los métodos que desee en consecuencia. Es posible que deba ser más creativo con la forma en que define y luego utilice métodos exclusivos para su tipo de mapa, pero no debería ser un gran problema.

Espero que esto te dé una idea. Déjame saber si necesitas más orientación y puedo ayudarte (parece que ha pasado un tiempo desde que lo pediste).

Answer 4

Scala 2.12 tiene mutable.TreeMap finalmente: https://github.com/scala/scala/pull/4504