Migrazione del codice TreeMap Java su Scala?

Question

Sto migrando il mio codice Java in puro Scala e sono bloccato on this one piece of code. Ho un'implementazione di un IntervalMap, ovvero una struttura dati che consente di mappare in modo efficiente gli intervalli da [from,to] a values dove le operazioni , delete e get sono tutte O(log n) (leggermente diverse da un intervallo o un segmento).

Questo codice utilizza Java di java.util.TreeMaps e durante la migrazione a Scala, mi sono imbattuto in 2 grandi temi:

1. Scala non ha mutable.TreeMap - ho deciso di andare intorno ad esso utilizzando mutable.TreeSet (stranamente Scala ha mutable.TreeSet ma non mutable.TreeMap) per la memorizzazione delle chiavi e la memorizzazione dei valori in un ausiliario mutable.Map. Questo è uno spiacevole trucco, ma c'è un modo migliore?

2. problema successivo è di Scala mutable.TreeSet non ha equivalenti di java.util.TreeSet s' ceilingKey, floorEntry, pollFirst, pollLast che sono tutte O(log n) operazioni in Java.

Quindi, come posso migrare al meglio il mio codice su Scala? Quali sono le migliori pratiche in queste situazioni? Non voglio davvero scrivere le mie implementazioni sugli alberi. C'è un modo più idiomatico di Scala di scrivere IntervalMaps di cui non sono a conoscenza? O c'è qualche biblioteca stimabile là fuori? O semplicemente Scala succhia qui con il suo TreeSet flessibile e TreeMaps inesistenti. Ovviamente posso usare Java TreeMap in Scala ma è brutto e perdo tutte le belle funzionalità della collezione Scala e quindi potrei usare Java.

Ecco il mio codice Java corrente: https://gist.github.com/pathikrit/5574521

Answer 1

Scala 2.12 ha mutable.TreeMap infine: https://github.com/scala/scala/pull/4504

Answer 2

La risposta è, purtroppo, di utilizzare solo la classe Java TreeMap.

Scala non ha una propria copia di tutto, e questo è una delle eccezioni più notevoli. Uno dei motivi per cui è compatibile con Java è che non devi re-inventare ogni ruota.

Il motivo per cui si desidera ancora utilizzare Scala è che non ogni bit di codice scritto riguarda questa TreeMap. Il tuo IntervalMap può essere un Scala IntervalMap; si usa semplicemente Java TreeMap internamente per implementarlo. Oppure potresti usare la versione immutabile in Scala, che ora funziona abbastanza bene per una versione immutabile.

Forse in 2.11 o 2.12 ci sarà un mutabile TreeMap; richiede a qualcuno di scriverlo, testarlo, ottimizzarlo, ecc., ma non penso ci sia un'obiezione filosofica ad averla.

Answer 3

Sembra che tu voglia usare le belle funzionalità delle collezioni Scala. Non penso che sia necessario reimplementare la tua classe.

Hai visto scala.collection.JavaConversions?

È possibile seguire un approccio simile con un wrapper e quindi implementare i metodi desiderati di conseguenza. Potrebbe essere necessario essere più creativi con il modo in cui definisci e quindi utilizzare metodi unici per il tuo tipo di mappa, ma non dovrebbe essere un grosso problema.

Spero che questo ti dia un'idea. Fammi sapere se hai bisogno di più indicazioni e potrei aiutarti (sembra che sia passato un po 'da quando hai chiesto).

Answer 4

1) Qual è il problema con l'utilizzo di una TreeMap immutabile internamente? È più o meno altrettanto efficiente della mappa ad albero mutevole, fa tutto in O (log n).

2) Nella versione Scala, non c'è ceilingKey e floorKey, ma invece si ha metodi from e to che fanno essenzialmente la stessa, ma restituire un'intera sottostruttura invece di singole voci.

completa 1: porta 1 del codice 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)) 

Risultato:

{} 
{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 classe Segment dovrebbe essere impostato private[yourPackage], deve essere aggiunto un po 'di documentazione.