Di chuyển mã Java TreeMap sang Scala?

Question

Tôi đang di chuyển cơ sở mã Java của mình sang Scala thuần túy và tôi bị kẹt on this one piece of code. Tôi có triển khai IntervalMap tức là cấu trúc dữ liệu cho phép bạn lập bản đồ hiệu quả các dải [from,to] đến values trong đó các hoạt động set, delete và get là tất cả O(log n) (hơi khác với IntervalTree hoặc SegmentTree).

Mã này sử dụng Java của java.util.TreeMaps và trong khi chuyển sang Scala, tôi chạy vào 2 vấn đề lớn:

1. Scala không có mutable.TreeMap - Tôi quyết định đi xung quanh nó bằng cách sử dụng mutable.TreeSet (kỳ quặc Scala có mutable.TreeSet nhưng không có mutable.TreeMap) để lưu trữ khóa và lưu trữ các giá trị trong phụ trợ mutable.Map. Đây là một hack khó chịu nhưng có cách nào tốt hơn?

2. vấn đề tiếp theo là Scala của mutable.TreeSet không có tương đương với java.util.TreeSet 's ceilingKey, floorEntry, pollFirst, pollLast đó là tất cả O(log n) hoạt động trong Java.

Vì vậy, làm cách nào để di chuyển mã của tôi sang Scala tốt nhất? Các phương pháp hay nhất trong những tình huống này là gì? Tôi thực sự không muốn viết các triển khai cây của riêng mình. Có một cách Scala thành ngữ hơn bằng cách viết IntervalMaps mà tôi không biết? Hoặc là có một số thư viện có uy tín ngoài kia? Hoặc không Scala chỉ đơn giản là hút ở đây với TreeSet gimped của nó và TreeMaps không tồn tại. Ofcourse tôi chỉ có thể sử dụng Java TreeMap trong Scala nhưng đó là xấu xí và tôi mất tất cả các tính năng thu thập Scala đẹp và tôi cũng có thể sử dụng Java sau đó.

Đây là mã Java hiện tại của tôi: https://gist.github.com/pathikrit/5574521

Answer 1

Scala 2.12 có mutable.TreeMap cuối cùng: https://github.com/scala/scala/pull/4504

Answer 2

Câu trả lời là, không may, chỉ cần sử dụng lớp Java TreeMap.

Scala không có bản sao riêng của tất cả mọi thứ và đây là một trong những ngoại lệ đáng chú ý nhất. Một trong những lý do nó tương thích với Java là do đó bạn không phải phát minh lại mọi bánh xe.

Lý do bạn vẫn muốn sử dụng Scala là không phải mọi mã bạn viết là về TreeMap này. IntervalMap của bạn có thể là Scala IntervalMap; bạn chỉ cần sử dụng Java TreeMap nội bộ để triển khai nó. Hoặc bạn có thể sử dụng phiên bản bất biến trong Scala, hiện đang hoạt động khá tốt cho một phiên bản bất biến.

Có lẽ trong 2,11 hoặc 2,12 sẽ có một biến thể TreeMap; nó đòi hỏi ai đó viết nó, kiểm tra nó, tối ưu hóa nó, vv, nhưng tôi không nghĩ rằng có một phản đối triết học để có nó.

Answer 3

Dường như bạn muốn sử dụng các tính năng bộ sưu tập Scala đẹp. Tôi không nghĩ rằng bạn cần phải thực hiện lại lớp học của bạn.

Bạn đã xem scala.collection.JavaConversions chưa?

Bạn có thể làm theo một cách tiếp cận tương tự với trình bao bọc và sau đó triển khai các phương pháp bạn muốn cho phù hợp. Bạn có thể cần phải sáng tạo hơn với cách bạn xác định và sau đó sử dụng các phương pháp duy nhất cho loại bản đồ của bạn, nhưng không phải là một vấn đề lớn.

Tôi hy vọng điều này mang lại cho bạn ý tưởng. Hãy cho tôi biết nếu bạn cần thêm hướng dẫn và tôi có thể giúp bạn (có vẻ như đã lâu rồi bạn mới hỏi).

Answer 4

1) Có vấn đề gì với việc sử dụng TreeMap không thay đổi bên trong? Nó ít nhiều hiệu quả như bản đồ cây có thể thay đổi được, làm mọi thứ trong O (log n).

2) Trong phiên bản Scala, không có ceilingKey và floorKey, nhưng thay vào đó người ta có phương pháp from và to đó làm cơ bản là giống nhau, nhưng trở lại toàn bộ một cây con thay vì mục duy nhất.

Full 1: cổng 1 của Java-code:

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

Kết quả:

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

Lớp Segment nên được đặt private[yourPackage], một số tài liệu nên được bổ sung.