Короче, алгоритм добавления диапазона (begin, end) в двухсвязный список точек у меня такой:
Сначала ищем или создаём головную точку
Point head = null;
Point x = this.first;
while (begin > x.value)
{
x = x.next;
}
if (x.prev.type == PointType.Begin)
{
Попали в уже существующий диапазон, возвращаем его голову
head = x.prev;
}
else if ((x.prev.type == PointType.End) && ((x.prev.value == begin -1) || (x.prev.value == begin)))
{
Попали точно в конец существующего диапазона или в смежную с ним точку
head = x.prev.prev;
}
else if ((x.prev.type == PointType.Single) && ((x.prev.value == begin -1) || (x.prev.value == begin)))
{
Попали точно в существующую точку или в смежную с ней
head = x.prev;
}
else
{
Никуда не попали, создаём новую точку
head = new Point(begin);
head.next = x;
head.prev = x.prev;
head.next.prev = head;
head.prev.next = head;
}
Теперь ищем или создаём хвостовую точку
Point tail = null;
while (end > x.value)
{
x = x.next;
}
if (x.type == PointType.End)
{
Попали в уже существующий диапазон, возвращаем его хвост
tail = x;
}
else if ((x.type == PointType.Begin) && ((x.value == end + 1) || (x.value == end)))
{
Попали в самое начало существующего диапазона или непосредственно перед ним, возвращаем его хвост
tail = x.next;
}
else if ((x.type == PointType.Single) && ((x.value == end + 1) || (x.value == end)))
{
Попали в существующую одиночную точку или непосредственно перед ней
tail = x;
}
else
{
Никуда не попали, создаём новую точку
tail = new Point(end);
tail.prev = x.prev;
tail.next = x;
tail.next.prev = tail;
tail.prev.next = tail;
}
Коллапсируем всё что оказалось между головой и хвостом
if (head.value == tail.value)
{
Добавление одиночной точки, отбрасываем хвост
head.next = tail.next;
head.next.prev = head;
head.type = PointType.Single;
}
else
{
head.next = tail;
head.type = PointType.Begin;
tail.prev = head;
tail.type = PointType.End;
}
Точки бывают трёх сортов: Begin, End, Single. Для упрощения алгоритма в список помещены фэйковые граничные точки со значениями -2 и long.MaxValue. Да, тип номера сменил с UInt64 на Int64. Номерам разрешается быть >= 0 и < long.MaxValue - 1. Именно -2, а не -1 потому что -1 смежный с 0. Аналогично long.MaxValue-1.
После того как список точек построен по нему генерируется массив структур диапазонов. Но его менять уже нельзя. Далее используется только он. В частности, номера на массиве диапазонов ищутся бинарным поиском.
