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?

Сильно связанные вопросы:

Ответы

Ответ 1

Я бы, скорее всего, инкапсулировал Guava RangeMap. Все, что вам нужно, это класс трех методов, за которым вы можете скрыть несквалентную коллекцию.

Мне было любопытно, как тяжело было бы свернуть мое собственное решение на основе Java NavigableMap, и это довольно тривиально:

определить класс MyValue, содержащий (начало, конец, сохраненное значение)
используйте карту, сопоставляющую начальную точку с соответствующим MyValue

Только с 40 строк в Java с Lombok (и, вероятно, меньше в Scala), я бы не боялся никакого обслуживания. Я написал очень рудиментарный test.