Date input algorithm
I have a List, it has Foo objects, and each Foo has a start date and an end date. I want to insert a new Foo object that has its own start and end date.
I want the items in the list to update the start and end dates accordingly when a new Foo object was inserted and that the new Foo object finds its correct place in the list. I'll wait and see if there is enough information for someone to understand my problem and see if I need to explain further.
source to share
Your new Foo object should traverse the list and find where it should be inserted. But be careful, as there are tons of edge things to do that can ruin your list. Your logic should work in the following situations:
1) The new interval fits into an existing interval -- do nothing
2) The new interval begins and ends before the first interval --
insert it at the front of the list
3) The new interval stretches the existing start, end,
or both without cutting across adjacent intervals --
replace the start or end date on existing Foo.
4) The new interval begins after the end of the previous interval, but
ends after the beginning of the next interval --
walk the list with a sentinel until you find a Foo that begins before
the end of your new Foo. Delete the Foos that fall in
between the current Foo and the sentinel, adjusting the
end time if necessary.
5) The new interval begins after the end of the last interval --
insert it at the end of the list.
I may be missing an edge, but this is the model I used when I had to solve a very similar problem.
source to share
To find the insertion point, you can use an interpolation lookup (for example, every day has an integer in mss), and when an item it can disable a method that updates its neighbors, which then update their neighbors after receiving an update request, down the line.
I could simplify your problem, but from what I understand from your post, this should average slightly more O (n) time.
source to share