DateTimeRange .NET

[MagMagals]

в работе так же сталкивался с необходимостью работать с временными интервалами. В частности в разработке/доработке парковочная система(так же на C#). В системе есть понятия тарифы которые действуют в определенные временные отрезки (ночной с 21:00-9:00, днейвной 09:00-21:00 и тд).

для этой задачи решил пойти по пути использования cron формата. библиотеки парсеры уже есть в дотнете.

единственный существенный минус, эт то что парсер выдает достаточно много лишних записей по времени между началом и концом тарифа. то есть, если кто-то простоял день, то парсер cron формата "09:00-21:00 (* 9-20 * * *)" выдаст записи 09:00,09:01,09:02 ...20:59.

[Dansoid]

Для справки, подобное существует уже около 10 лет, и оно очень серьёзно реализовано:
https://github.com/rsdn/CodeJam/tree/master/CodeJam.Main/Ranges

Поддерживаются бесконечные диапазоны, границы с/без включения, а также есть расширения для IQueryable, позволяющие накладывать ограничения прямо на выборку из базы данных.

[Naf2000]

Чему будет результат Intersections для набора (я дата-время заменил числами, т.к. принципиально это ничего не меняет):

[1,10],[2,4],[6,10],[7,8]

и для набора

[1,10],[2,4],[6,10],[3,7]

Как-то неочевидно это все

[resnyanskiy]

Результат на картинках. Самый близкий тест Overlapped_Ranges. В чем именно неочевидность? То есть, должен быть какой-то другой результат?

[1,10],[2,4],[6,10],[7,8] -> [2,4],[7,8]

[1,10],[2,4],[6,10],[3,7] -> [3,4],[6,7]

[Naf2000]

Вы можете словами сформулировать, что в итоге получается? 🤔

Потому что просто "все пересечения всех интервалов" это и просто попарные пересечения. Но вы же явно берете не все из них, а что-то другое

[resnyanskiy]

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

/*
012345678901
/----//----/
 /-------/
  /-----/
012345678901
 /+++/
  /+++++/
      /+/
012345678901
  /++//+/
012345678901
*/
[Fact]
public void Intersections_Of_Intersections()

[Naf2000]

Картинки и тесты безусловно помогают "увидеть" картину зачастую лучше сухого определения. С этим я согласен.

Но все же необходимо иметь четкое понимание исследуемого объекта, иначе можно говорить о разных вещах. Спасибо, что дали пояснение.

Тем не менее мотивация мне непонятна - для чего такое "пересечение", что оно показывает или как его можно применить?

Тем более похоже, что внутренней симметричной картины не получается. Если у нас есть три интервала A, B, C, то операция Intersections не удовлетворяет, например ассоциативности:

Intersections(Intersections(A, B), C) не равно Intersections(A, Intersections(B, C))

Хотя безусловно вещь интересная. Спасибо

[ptr128]

Лично для меня куда интересней был бы поиск наличия пересечений одного диапазона с одним из множества других. Скорее всего, оптимально это можно сделать с использованием R-Tree, но не исключаю и иные вариант.

[resnyanskiy]

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

var intervalTree = new IntervalTree(ranges);
var intersectingRanges = intervalTree.SearchIntersections(range);