Java TreeMapコードをScalaに移行しますか？

Question

私はJavaコードベースを純粋なScalaに移行しており、私は詰まっていますon this one piece of codeです。私はIntervalMapの実装を持っています。[from,to]をset、delete、getの操作がすべてO(log n)（IntervalTreeやSegmentTreeとは少し異なります）に効率的にマップするデータ構造があります。

このコードは、Javaのjava.util.TreeMapsを使用し、スカラ座への移行ながら、私は2つの大きな問題に遭遇した：

1. Scalaは何mutable.TreeMapを持っていない - 私は（奇妙なScalaはmutable.TreeSetを持ってmutable.TreeSetを使用して、その周りに行くことにしましたがありませんmutable.TreeMap）を使用して、キーを格納し、その値を補助語mutable.Mapに格納する。これは不愉快なハックですが、より良い方法がありますか？

2. 次の問題は、Scalaのmutable.TreeSetは、JavaのすべてのO(log n)操作ですjava.util.TreeSetさんceilingKey、floorEntry、pollFirst、pollLastのない相当するものはないです。

コードをScalaに移行するにはどうすればよいですか？これらの状況におけるベストプラクティスは何ですか？私は自分のツリーの実装を書いていないのです。私が気づいていないIntervalMapsを書いている慣用的なScalaの方法がありますか？またはそこに評判の良い図書館がありますか？ Scalaは、幻想的なTreeSetと存在しないTreeMapsを使って、ここではまったく吸い取りません。もちろんScalaでJavaのTreeMapを使うことはできますが、それは醜いので、すてきなScalaコレクションの機能が失われてしまい、Javaを使うこともできます。 https://gist.github.com/pathikrit/5574521

Answer 1

Scalaの2.12は最終的にmutable.TreeMapがあります。https://github.com/scala/scala/pull/4504

Answer 2

答えは残念ながら、ちょうどJavaのTreeMapクラスを使用するには、次のとおりです。

は、ここに私の現在のJavaコードです。

Scalaにはすべてのコピーがありません。これは最も顕著な例外の1つです。 Javaと互換性がある理由の1つは、すべてのホイールを再作成する必要がないためです。

あなたがまだスカラを使用したい理由は、は、あなたが書き込むコードのすべてがこのTreeMapについてのものではないということです。 IntervalMapはScala IntervalMapとすることができます。 Java TreeMapを内部的に実装するだけです。あるいは、不変のバージョンをScalaで使うこともできます。これは不変のバージョンではうまくいきます。

おそらく2.11または2.12には、変更可能なTreeMapがあります。誰かにそれを書いたり、テストしたり、最適化したりする必要がありますが、私はそこに哲学的に異論はないと思います。

Answer 3

素晴らしいScalaコレクションの機能を使いたいと思うようです。あなたのクラスを再実装する必要はないと思います。

あなたはscala.collection.JavaConversionsを見ましたか？

同様の方法でラッパーを実行し、それに応じて必要なメソッドを実装することもできます。あなたは、あなたのマップの種類に固有のメソッドを定義し、使用する方法をより創造的にする必要があるかもしれませんが、大したことではありません。

私はこれがあなたにアイデアを与えることを望みます。あなたがもっとガイダンスを必要とするかどうかを教えてください。私はあなたに手伝ってもらえました。

Answer 4

1）不変なTreeMapを内部的に使用すると何が問題になりますか？多かれ少なかれ、変更可能なツリーマップと同じくらい効果的ですが、O（log n）内のすべてを行います。 Scalaのバージョンで

2）、ceilingKeyとfloorKeyないがないが、代わりに一方が実質的に同じ行う方法fromとtoを有するが、サブツリー全体の代わりに、単一のエントリを返します。

全1：Javaのコードの1ポート：

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

結果：

{} 
{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クラスはprivate[yourPackage]を設定する必要があり、いくつかのドキュメントを追加する必要があります。