Java TreeMap 코드를 스칼라로 마이그레이션 하시겠습니까?

Question

자바 코드 기반을 순수한 스칼라로 마이그레이션하고 있는데 on this one piece of code이 붙어 있습니다. IntervalMap의 구현 즉, 범위 [from,to]을 set, delete 및 get 연산이 모두 O(log n) (IntervalTree 또는 SegmentTree와 약간 다릅니다)으로 효율적으로 매핑 할 수있는 데이터 구조가 있습니다.

이 코드는 자바의 java.util.TreeMaps와 스칼라로 마이그레이션하는 동안, 나는이 큰 문제로 실행 사용

1. 스칼라 더 mutable.TreeMap이 없습니다 - 나는 mutable.TreeSet를 사용하여 주위에 가기로 결정 (이상한 스칼라없이 mutable.TreeSet 그러나이있다 mutable.TreeMap)를 사용하여 키를 저장하고 그 값을 보조 mutable.Map에 저장합니다. 이것은 불쾌한 해킹이지만 더 좋은 방법이 있습니까?

2. 다음 문제는 스칼라의 mutable.TreeSet이 java.util.TreeSet의 ceilingKey, floorEntry, pollFirst, 자바의 모든 O(log n) 작업입니다 pollLast의 동등한이 없습니다입니다.

그렇다면 코드를 스칼라로 가장 잘 마이그레이션하려면 어떻게해야합니까? 이러한 상황에서 가장 좋은 방법은 무엇입니까? 정말 내 자신의 트리 구현을 작성하고 싶지 않아요. 스칼라가 잘 모르는 IntervalMaps를 작성하는 관용적 인 방법이 있습니까? 아니면 밖에 평판 좋은 도서관이 있습니까? 또는 스칼라는 무시 무시한 TreeSet과 존재하지 않는 TreeMaps를 사용하여 여기에 빠져 있습니다. 물론 Scala에서는 Java의 TreeMap을 사용할 수 있지만보기에는 좋지 않은 Scala 컬렉션 기능이 모두 없어졌으며 Java를 사용할 수도 있습니다. https://gist.github.com/pathikrit/5574521

Answer 1

스칼라 2.12 마침내 mutable.TreeMap 있습니다 https://github.com/scala/scala/pull/4504

Answer 2

대답은 불행하게도, 그냥 자바 TreeMap 클래스를 사용한다 :

여기에 내 현재의 Java 코드입니다.

스칼라에는 모든 복사본이 없으며 이는 가장 주목할만한 예외 중 하나입니다. Java와 호환되는 이유 중 하나는 모든 바퀴를 다시 발명 할 필요가 없기 때문입니다.

그래도 스칼라를 사용하려는 이유는 입니다. 작성한 코드의 모든 비트가이 트리 맵에 관한 것이 아닙니다.. IntervalMap은 Scala가 될 수 있습니다 IntervalMap; Java TreeMap을 내부적으로 구현하면됩니다. 또는 스칼라에서 불변 버전을 사용할 수 있습니다. 스칼라 버전은 이제 불변 버전에 대해 상당히 잘 수행됩니다.

아마도 2.11 또는 2.12에서 변경 될 수 있습니다 TreeMap; 누군가 그것을 써야하고, 테스트하고, 최적화하는 것을 요구합니다. 그러나 그것을 가지고 있다는 철학적 반대가 있다고 생각하지 않습니다.

Answer 3

멋진 스칼라 컬렉션 기능을 사용하려는 것처럼 보입니다. 나는 당신이 당신의 수업을 다시 구현할 필요가 없다고 생각합니다.

scala.collection.JavaConversions을 보았습니까?

비슷한 방법으로 래퍼를 사용한 다음 원하는 방식으로 구현할 수 있습니다. 지도의 종류에 따라 고유 한 방법을 정의하고 사용하는 방법을보다 창의적으로 만들어야 할 수도 있지만 큰 문제는 아닙니다.

이 아이디어가 도움이되기를 바랍니다. 더 많은 안내가 필요하면 도움을받을 수 있음을 알려주십시오 (요청한 이후로 시간이 지났음).

Answer 4

1) 내부적으로 불변의 TreeMap을 사용할 때의 문제점은 무엇입니까? 그것은 대체로 변경 가능한 트리 맵만큼이나 효율적이며 O (log n)의 모든 것을 수행합니다. 스칼라 버전에서

2), 더 ceilingKey 및 floorKey 없다, 대신 하나는 본질적으로 동일 할 방법 from 및 to을 가지고 있지만 하나의 항목 대신 전체 하위 트리를 반환합니다.

전체 1 : 자바 코드의 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] 설정해야합니다 일부 문서는 추가해야합니다.