Не имеет ли кто на примете контейнера, способного хранить интервалы и эффективно делать по ним запросы?

К примеру, есть интервал временных отрезков и надо найти, какие интервалы находятся ближе всего к заданному интервалу.

NavigableMap — близко, но не подходит, так как:
1) Не multimap (ну ладно, исправимо)
2) Не позволяет эффективно искать ближайший к точке интервал.

Здравствуйте, Cyberax, Вы писали:

C>Не имеет ли кто на примете контейнера, способного хранить интервалы и эффективно делать по ним запросы?

C>К примеру, есть интервал временных отрезков и надо найти, какие интервалы находятся ближе всего к заданному интервалу.

C>NavigableMap — близко, но не подходит, так как:
C>1) Не multimap (ну ладно, исправимо)
C>2) Не позволяет эффективно искать ближайший к точке интервал.

Не видел, чтобы прямо вот такой контейнер. Но как-то приглядывался к задаче, где
неплохо подходило R-Tree. На сайте есть исходники http://www.rtreeportal.org/

Здравствуйте, Cyberax, Вы писали:

C>Не имеет ли кто на примете контейнера, способного хранить интервалы и эффективно делать по ним запросы?

C>К примеру, есть интервал временных отрезков и надо найти, какие интервалы находятся ближе всего к заданному интервалу.

C>NavigableMap — близко, но не подходит, так как:
C>1) Не multimap (ну ладно, исправимо)
C>2) Не позволяет эффективно искать ближайший к точке интервал.

Чем NavigableMap не подходит? Точнее, если надо хранить только интервалы, и они уникальны, используйте NavigableSet. Метод Itarable.compareTo пусть анализрует близость значения к заданному интервалу.
Если нужна multimap, используйте Multimap из Guava.
Что значит — непозволяет эффективно искать ближайший к точке интервал? Реализация NavigableMap — TreeMap, оптимизировано для отсортированных мапов.
Если у вас, операция — поиск ближайшей к точке интервала доминирует, используйте очереди. Не блокирующая очередь с сортировкой — PriorityQueue. в основе тоже дерево, но оптимизировано для доступа к вершине дерева.

Здравствуйте, Аноним, Вы писали:

C>>NavigableMap — близко, но не подходит, так как:
C>>1) Не multimap (ну ладно, исправимо)
C>>2) Не позволяет эффективно искать ближайший к точке интервал.
А>Чем NavigableMap не подходит? Точнее, если надо хранить только интервалы, и они уникальны, используйте NavigableSet. Метод Itarable.compareTo пусть анализрует близость значения к заданному интервалу.
Нельзя эффективно искать интервалы по близости к данной точке. Для этого нужно хранить индексы по началу и концу интервала, индексы по одному параметру пллохо подходят.

А>Если нужна multimap, используйте Multimap из Guava.
Нет Navigable.

А>Что значит — непозволяет эффективно искать ближайший к точке интервал? Реализация NavigableMap — TreeMap, оптимизировано для отсортированных мапов.
А>Если у вас, операция — поиск ближайшей к точке интервала доминирует, используйте очереди. Не блокирующая очередь с сортировкой — PriorityQueue. в основе тоже дерево, но оптимизировано для доступа к вершине дерева.
Не поможет, мне нужно именно делать запросы по произвольной точке.

Здравствуйте, Cyberax, Вы писали:

C>Здравствуйте, Аноним, Вы писали:

C>>>NavigableMap — близко, но не подходит, так как:
C>>>1) Не multimap (ну ладно, исправимо)
C>>>2) Не позволяет эффективно искать ближайший к точке интервал.
А>>Чем NavigableMap не подходит? Точнее, если надо хранить только интервалы, и они уникальны, используйте NavigableSet. Метод Itarable.compareTo пусть анализрует близость значения к заданному интервалу.
C>Нельзя эффективно искать интервалы по близости к данной точке. Для этого нужно хранить индексы по началу и концу интервала, индексы по одному параметру пллохо подходят.

А>>Если нужна multimap, используйте Multimap из Guava.
C>Нет Navigable.

А>>Что значит — непозволяет эффективно искать ближайший к точке интервал? Реализация NavigableMap — TreeMap, оптимизировано для отсортированных мапов.
А>>Если у вас, операция — поиск ближайшей к точке интервала доминирует, используйте очереди. Не блокирующая очередь с сортировкой — PriorityQueue. в основе тоже дерево, но оптимизировано для доступа к вершине дерева.
C>Не поможет, мне нужно именно делать запросы по произвольной точке.

Не могли бы вы подробнее описать, тип элемента коллекции, какие поля он содержит.
И что понимается под операцией: эффективно искать ближайший к точке интервал?
Какая операции доминируют?

Здравствуйте, Cyberax, Вы писали:

А>>Чем NavigableMap не подходит? Точнее, если надо хранить только интервалы, и они уникальны, используйте NavigableSet. Метод Itarable.compareTo пусть анализрует близость значения к заданному интервалу.
C>Нельзя эффективно искать интервалы по близости к данной точке. Для этого нужно хранить индексы по началу и концу интервала, индексы по одному параметру пллохо подходят.

А что если просто складывать точки-концы в NavigableMap? Каждая такая точка может, в свою очередь, ссылаться на свой интервал, содержать дополнительную информацию, например, начало это или конец интервала...

Здравствуйте, investigator, Вы писали:

C>>Нельзя эффективно искать интервалы по близости к данной точке. Для этого нужно хранить индексы по началу и концу интервала, индексы по одному параметру пллохо подходят.
I>А что если просто складывать точки-концы в NavigableMap? Каждая такая точка может, в свою очередь, ссылаться на свой интервал, содержать дополнительную информацию, например, начало это или конец интервала...
Проблема в том, что нужно искать не только по одной точке.

К примеру, такой случай:

====[-------]===[--x---------------------------]===========

Если искать по концевой точке, то ближайшим интервалом к точке "x" будет первый интервал. Что в корне неверно, так как точка лежит во втором.

Я пока соорудил монстра из двух NavigableMap, но это мне активно не нравится.

Здравствуйте, Аноним, Вы писали:

А>Не могли бы вы подробнее описать, тип элемента коллекции, какие поля он содержит.
А>И что понимается под операцией: эффективно искать ближайший к точке интервал?
А>Какая операции доминируют?
На самом деле, нужны разные типы запросов: выбор интервалов в определённом порядке, поиск пересечений и т.п.

В C++ я бы сделал на boost.multiindex.

Здравствуйте, Cyberax, Вы писали:

C>Здравствуйте, investigator, Вы писали:

C>>>Нельзя эффективно искать интервалы по близости к данной точке. Для этого нужно хранить индексы по началу и концу интервала, индексы по одному параметру пллохо подходят.
I>>А что если просто складывать точки-концы в NavigableMap? Каждая такая точка может, в свою очередь, ссылаться на свой интервал, содержать дополнительную информацию, например, начало это или конец интервала...
C>Проблема в том, что нужно искать не только по одной точке.

C>К примеру, такой случай:
C>

C>====[-------]===[--x---------------------------]===========
C>

C>Если искать по концевой точке, то ближайшим интервалом к точке "x" будет первый интервал. Что в корне неверно, так как точка лежит во втором.

Почему первый?

Имеем:

====A1-------A2===B1--x---------------------------B2===========

Все точки — A1, A2, B1 и B2 лежат в мапе. Далее по x выдергиваем ближайщую слева или справа. В нашем случае будет B1. Получаем второй интервал.

C>Я пока соорудил монстра из двух NavigableMap, но это мне активно не нравится.

По-моему, если их объединить, то как раз получится мой вариант (если я правильно догадываюсь об их смысле). Концептуально, правда, это ничего не поменяет.