У меня почти такой же вопрос, как упоминалось в структурах данных, которые могут отображать диапазон ключей в значение, но для Scala.
То есть, я хотел бы иметь изменяемую систему неперекрывающихся диапазонов 1D [a [i], b [i]), которые отображались бы на какое-то значение v [i]. Стандартная базовая структура данных для выполнения этой работы - это красно-черное дерево.
Операции, которые я хотел бы иметь, желательно, чтобы все они имели сложность O (log n):
- Запросить и получить заданный диапазон (начало, конец, сохраненное значение) или его отсутствие, указав любую точку внутри него
- Вставьте новый диапазон в эту структуру
- Удалить диапазон из структуры
Итак, я предполагаю, что до сих пор я вижу следующие варианты, все из которых имеют свои минусы:
- Roll-your-own-container поверх Java TreeMap - быстрый и грязный, но, вероятно, плохой в долгосрочной перспективе из-за отсутствия надлежащее обслуживание
- Использовать Guava RangeMap - возможно, но будет довольно неудобно в мире коллекций Scala
- Попытайтесь использовать Scala красно-черные реализации дерева и попробуйте выполнить roll-your-own, однако, я думаю, это было бы довольно сложно, учитывая, что Scala TreeMap является неизменяемым и пропускает простые методы поиска, такие как Java TreeMap
floorEntry
Я что-то упустил? Существуют ли в Гуаве хорошо сохранившиеся библиотеки расширений коллекций, использующие Scala -центрические API, которые расширяют основные коллекции Scala?
Сильно связанные вопросы:
- Перенос кода Java TreeMap в Scala? - упоминает "просто использовать Java TreeMap" и забыть о чем-нибудь еще
- Java-версии этой проблемы:
