Java TreeMap kodunu Scala'ya mı taşıyorsunuz?

Question

Java kod tabanımı saf Scala'ya taşıyorum ve on this one piece of code takılıyorum. IntervalMap'in bir uygulamasına sahibim, yani [from,to] aralıklarını values ile set, delete ve get işlemlerinin tümü O(log n) (IntervalTree veya SegmentTree'den biraz farklı) olarak verimli bir şekilde eşleştirmenizi sağlayan bir veri yapıları.

Bu kod, Java en java.util.TreeMaps ve Scala göç ederken, ben 2 büyük sorunlar koştu kullanır:

1. Scala hiçbir mutable.TreeMap var - Ben mutable.TreeSet kullanarak etrafında gitmeye karar (garip bir şekilde Scala hiçbir mutable.TreeSet ama vardır mutable.TreeMap) anahtarların saklanması ve değerlerin bir yardımcı mutable.Map içinde saklanması. Bu hoş olmayan bir hack ama daha iyi bir yolu var mı?

2. Sonraki sorun Scala'nın mutable.TreeSetjava.util.TreeSet 'ın ceilingKey, floorEntry, pollFirst, Java tüm O(log n) operasyonlardır pollLast hiçbir eşdeğer sahiptir.

Kodumu en iyi Scala'ya nasıl taşıyabilirim? Bu durumlarda en iyi uygulamalar nelerdir? Kendi ağaç uygulamalarını yazmak istemiyorum. Farkında olmadığım IntervalMaps yazmanın daha deyimsel bir Scala yolu var mı? Yoksa orada saygın bir kütüphane var mı? Ya da Scala, gimped TreeSet ve varolmayan TreeMaps'ları ile sadece burada emilir. Tabii ki sadece Java'nın TreeMap'u Scala'da kullanabilirim ama bu çirkin ve tüm güzel Scala koleksiyonu özelliklerini kaybediyorum ve ben de Java'yı kullanabiliyorum. https://gist.github.com/pathikrit/5574521

Answer 1

Scala 2.12 nihayet mutable.TreeMap sahiptir: https://github.com/scala/scala/pull/4504

Answer 2

cevap maalesef sadece Java TreeMap sınıfını kullanmak, geçerli:

İşte benim şimdiki Java kodudur.

Scala'nın her şeyin bir kopyası yok ve bu en dikkate değer istisnalardan biri. Java uyumlu olmasının nedenlerinden biri, böylece her tekerleği yeniden icat etmeniz gerekmez.

Scala'yı kullanmak için hala kullanmanızın nedeni, numaralı telefonun, bu TreeMap hakkında yazdığınız her bir kodun olmamasıdır. Sizin IntervalMap, bir Scala IntervalMap olabilir; Bunu uygulamak için sadece Java TreeMap'u kullanıyorsunuz. Ya da şimdi değişmez bir versiyon için makul derecede iyi performans gösteren Scala'daki immutable versiyonu kullanabilirsiniz.

Belki de 2.11 veya 2.12'de mutant TreeMap; Birilerinin bunu yazmasını, test etmesini, optimize etmesini vb. gerektirir, ancak buna sahip olmanın felsefi bir itiraz olduğunu düşünmüyorum.

Answer 3

Güzel Scala koleksiyonlarını kullanmak istediğiniz gibi görünüyor. Sınıfınızı yeniden geliştirmeniz gerektiğini düşünmüyorum.

scala.collection.JavaConversions'u gördünüz mü?

Sarıcıyla benzer bir yaklaşım izleyebilir ve ardından istediğiniz yöntemleri uygulayabilirsiniz. Nasıl tanımladığınıza ve daha sonra haritanıza özgü olan yöntemleri kullandığınıza göre daha yaratıcı olmanız gerekebilir, ancak büyük bir anlaşma olmamalıdır.

Umarım bu size bir fikir verir. Daha fazla rehberliğe ihtiyacınız varsa ve size yardımcı olabilirim (bana sorduğunuzdan beri bir süre olmuş gibi görünüyor).

Answer 4

1) İçinde immutable bir TreeMap kullanılmasıyla ilgili sorun nedir? Değişken ağaç haritası kadar az ya da çok, O (log n) içindeki her şeyi yapar. Scala versiyonda

2), hiçbir ceilingKey ve floorKey yoktur, bunun yerine bir temelde aynı şeyi yöntemleri from ve to vardır, ama tek girişlerin yerine bütün bir alt ağacı döner.

Tam 1: Java kod 1 port:

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

Sonuç:

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

Segment sınıf private[yourPackage] ayarlanmalıdır, bazı belgeler eklenmelidir.