Существует ли версия NavigableMap для Scala? - PullRequest
Новая
       15

Существует ли версия NavigableMap для Scala?

9 голосов
/ 29 августа 2011

В Java 1.6 были представлены интерфейсы NavigableMap (и NavigableSet ), и TreeMap был обновлен для реализации нового интерфейса. Помимо прочего, NavigableMap полезен для того, чтобы задавать вопросы типа «Какой элемент в коллекции ближе всего к X?» (См. этот отличный пост в блоге Франсуа Саррадина для примера и обсуждения).

Я надеялся найти что-то подобное в реализации TreeMap в Scala 2.8, но, увы, это не так (по крайней мере, это не очевидно). Есть ли другой класс или черта Scala, которые похожи на Java NavigableMap? Если нет, то есть ли несколько простых идиом Scala, которые можно использовать для достижения чего-то подобного?

Я понимаю, что могу использовать Java TreeMap, но я бы хотел остаться в рамках коллекции Scala (хотя бы для простоты).

Ответы [ 2 ]

2 голосов
/ 29 августа 2011

В неизменных коллекциях наличие обратных ссылок делает коллекцию постоянной. Поэтому вместо этого люди используют молнии для навигации по таким структурам. Anti-xml имеет хороший пример использования застежек-молний при работе с XML.

1 голос
/ 29 августа 2011

Вот тема на эту тему

Кажется, SortedMap может быть в состоянии помочь вам пройти часть пути, но то, что я проверилдо сих пор я не уверен, что это O (log (n)), каким должен быть поиск: 

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
}

На основе определений from и to в терминах rangeImpl похоже, что это может быть O (log (n)), но, основываясь на фактической синхронизации, оно кажется линейно растущим для всех вероятных значений n.

Так что я не уверен.

...