date insertion algorithm

Question

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, which has its own start and end date. I want the elements in the list to update their start and end dates accordingly, when the new Foo object is inserted, and for the new Foo object to find its correct place in the List. i'll wait and see if this is enough info for someone to understand my problem, and see if i need to explain further...thanks

Answer 1

To find the insertion point you could use the interpolation search (treating each date an integer in msecs for example) and when the item is inserted it could fire off a method that updates its neighbors, who then update their neighbors upon receiving the request to update, on down the line.

I might be oversimplifying your problem, but from what I understand of your post, this should take on average a little more than O(n) time.

Answer 2

Your new Foo object needs to traverse the list and find where it needs to be inserted. But be careful, since there are a bunch of edge cases that can mess up 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.

It's possible I'm missing an edge case, but this is a model I used when I had to solve a very similar problem.

Answer 3

rtperson, u hit the nail on the head, u understand the issue. now my question is how to implement, pretty much straight forward if type stuff? also, i do not understand the sentinel thing, i saw a movie a while back with michael douglas and maybe keifer sutherland call the sentinel, but that's off track...what do u mean by it? thanks!