Хранение изменяющихся диапазонов целых чисел

[baldr]

Есть задача хранить непересекающиеся диапазоны целых чисел. Причем могут добавляться новые значения.
Простой пример:
* Есть существующий диапазон: [3, 8], [11, 15], [19, 20]
* Добавляется новый диапазон [5, 16] - он должен объединить два первых в один.

Вопрос - есть ли какой-то существующий базовый механизм для работы с такими коллекциями?
SortedList не подходит по причине необходимости работы с предыдущими и последующими записями.
Возможно, будет решением использование LINQ, но я с ним почти не работал.

.NET Framework 3.0

[Dale]

HashSet<int>?

[Dimka]

SortedList не подходит по причине необходимости работы с предыдущими и последующими записями.

Вот этот пункт поподробнее. Что это значит? От некоего элемента получать доступ к предыдущему и следующему по порядку?

[baldr]

HashSet<int>?

Нежелательно:

.NET Framework 3.0

По MSDN, HashSet<> появился в 3.5

Добавлено через 2 минуты и 17 секунд:

Вот этот пункт поподробнее. Что это значит? От некоего элемента получать доступ к предыдущему и следующему по порядку?

Да. Если реализовывать это самостоятельно, то встанет вопрос перебора элементов, их удаления или изменения внутри коллекции.
Если, конечно, ключом для SortedList<> делать начальную позицию диапазона.

[RXL]

baldr, в БД есть такая вещь, как Nested Sets (вложенные множества). Это одна из возможных реализаций деревьев в реляционной базе. Я это рассказываю затем, что твоя задача имеет общие принципы с Nested Sets.
Каждый узел хранит границы начала и конца диапазона идентификаторов, входящих в множество. Причем начало - это его собственный идентификатор. Это можно описать так: struct set { int left; int right; /* ... */ };
Алгоритмы, используемые для работы с этими множествами могут тебе пригодиться.
Для ускорения используют left в качестве индекса. По этому тебе может подойти обычный Map.

[Dimka]

Я думаю, что ключевой проблемой здесь является решение следующей подзадачи.

Есть множество чисел, например, { 3, 11, 19 }. На вход подаётся число, например, 5. Нужно найти во множестве пару чисел, между которыми находится заданное (или пару одинаковых чисел, равных заданному, если заданное число присутствует во множестве) - в данном случае (3, 11).

С помощью чего такая задача решается оптимально?

На вскидку - это бинарный поиск (делением пополам) в упорядоченном множестве чисел. Реализуется он либо на массиве, либо на сбалансированном бинарном дереве.

И та, и другая структуры неоптимальны на вставку и удаление: массив нужно частично или полностью двигать, дерево - балансировать.

И та и другая структуры очень удобны для перебора всех следующих (предыдущих) чисел после (до) заданного.

[RXL]

Есть взять структуру new(left, right), поиск пересечения с существующими диапазонами:
1. Пересечение левой частью: left <= new.left && right >= new.left
2. Пересечение правой частью: left >= new.left && left <= new.right
3. Вхождение в существующий диапазон: утверждение_1 && right >= new.right
4. Вхождение существующего диапазона: утверждение_2 && right <= new.right

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

Дим, разве по дереву нельзя идти в обратном направлении?

[Dimka]

Дим, разве по дереву нельзя идти в обратном направлении?

Это просто так вопрос, или я что-то такое сказал, наводящее на эту мысль?

Во-первых, под "обратным" в дереве я понимаю "от листьев к корню". Во-вторых, конечно можно, если каждый дочерний узел хранит ссылку на родителя.


С помощью структуры "сбалансированное бинарное дерево" задача решается при помощи множества структур "Диапазон" и двух деревьев - одно для левых границ диапазона, другое - для правых. Каждый узел каждого дерева ссылается на соответствующий диапазон.

Тогда для [5, 16] нужно:
1) В дереве левых границ найти узел, ближайший и меньший 5 - это 3, и диапазон [3, 8].
2) В дереве правых границ найти узел, ближайший и больший 5 - это 8, и диапазон [3, 8].
3) Если найденные границы указывают на один и тот же диапазон, значит 5 попала в существующий диапазон - запомнить его как крайний левый. Если найденные границы указывают на разные диапазоны, значит 5 попала в "дыру" между существующими диапазонами - тогда от вершины, найденной в 1, нужно перейти к следующей в порядке обхода в глубину (либо это правый сын, либо, если его нет, родитель), и по этой вершине запомнить диапазон как крайний левый. Это [3, 8].

Аналогично с другого конца
4) В дереве левых границ найти узел, ближайший и меньший 16 - это 15.
5) В дереве правых границ найти узел, ближайший и больший 16 - это 20.
6) Если найденные границы указывают на один и тот же диапазон, значит 16 попало в существующий диапазон - запомнить его как крайний правый. Если найденные границы указывают на разные диапазоны, значит 16 попала в "дыру" между существующими диапазонами - тогда от вершины, найденной в 5, нужно перейти к предыдущей в порядке обхода в глубину (либо это левый сын, либо, если его нет, родитель), и по этой вершине запомнить диапазон как крайний правый. Это [11, 15].

7) По дереву левых (правых) вершин найти все диапазоны, у которых левая (правая) граница находится между левыми (правыми) границами найденных диапазонов (включительно). Это [3, 8], [11, 15]. Результатом может быть и пустое множество, если левая граница крайнего левого диапазона окажется больше левой границы крайнего правого диапазона. Тогда новый диапазон целиком умещается в "дыру". Может так быть, что нет крайнего левого или крайнего правого диапазонов - тогда вместо их левых (правых) границ взять, соответственно, наименьшее и наибольшее возможные значения границ для диапазонов.
8 ) Удалить все найденные диапазоны и их границы из деревьев.

9) Добавить новый диапазон [5, 16], добавить 5 в дерево левых границ, добавить 16 в дерево правых границ.
10) Сбалансировать деревья.

[Dale]

Диапазон значений ограничен, или допускаются любые целые?

[RXL]

Дим, извиняюсь - это я криво прочел. Вопрос отменяется.

[baldr]

Диапазон значений ограничен, или допускаются любые целые?

Если мы все еще говорим про мою задачу, то числа - это отрезки в файле. То есть это положительная ветка диапазона long. То есть числа довольно большие - это для RXL - к вопросу про 1 байт.

Все же изначально вопрос был такой - существуют ли в C# базовые возможности сделать это - какой-то готовый класс или паттерн.
За алгоритмы спасибо, но это был бы следующий шаг.

[Dimka]

Описанные мною деревья скорее всего реализованы при помощи SortedDictionary. Поскольку у него декларируется логарифмическая сложность по поиску. У него же есть метод Where, позволяющий организовывать поиск (как часть LINQ).