Có phiên bản Scala của NavigableMap không?

Question

Trong Java 1.6, giao diện NavigableMap (và NavigableSet) đã được giới thiệu và TreeMap được cập nhật để triển khai giao diện mới. Trong số những thứ khác, NavigableMap hữu ích khi đặt câu hỏi như "Yếu tố nào trong bộ sưu tập gần nhất với X? (Xem this excellent blog post by François Sarradin để biết ví dụ và thảo luận).

Tôi đã hy vọng tìm được điều gì đó tương tự trong triển khai TreeMap của Scala 2.8 , nhưng than ôi, nó không xuất hiện như vậy (ít nhất, nó không phải là rõ ràng) Có một lớp Scala hoặc đặc điểm tương tự như NavigableMap của Java? Nếu không, có một số thành ngữ Scala đơn giản có thể được sử dụng để đạt được một cái gì đó tương tự?

tôi nhận ra tôi có thể sử dụng TreeMap Java, nhưng tôi muốn ở lại trong khuôn khổ bộ sưu tập Scala (nếu chỉ vì đơn giản).

Answer 1

Trên các bộ sưu tập không thay đổi, có tham chiếu ngược lại khiến không thể thực hiện việc thu thập liên tục. Vì vậy, thay vào đó, mọi người sử dụng zippers để điều hướng qua các cấu trúc như vậy. có một ví dụ điển hình về việc sử dụng các khóa kéo khi làm việc với XML.

Answer 2

Here's a thread on this topic

Có vẻ như SortedMapcó thể có thể giúp bạn tham gia, nhưng những gì tôi đã thử nghiệm cho đến nay tôi không chắc liệu đó có phải là O (log (n)) không. là:

def searchMap(m: SortedMap[Int,_], k: Int) = { 
    val left = m to(k) lastKey 
    val right = m from(k) take(2) lastKey 

    if (k - left < right - k) 
     left 
    else 
     right 
} 

dựa trên các định nghĩa của from và to về rangeImpl nó trông như thế này có thể là O (log (n)), nhưng dựa trên thực tế thời gian đó, nó xuất hiện để phát triển tuyến tính cho tất cả các chính đáng giá trị của n.

Vì vậy, tôi không chắc chắn.