Datastructure for a collection of intervals

Question

I am looking for a Java based data structure which manages a collection time/date based intervals (preferably Joda Time) such that for every interval which is added to the collection, the data structure returns the subintervals(s) of the added interval, which are not yet in the data strucuture and consolidates the intervals.

Now in terms of set theory this would be easy, i.e. the return value would be "to be added" \ "existing" and the resulting structure would be "existing" union "to be added". Now of course I could emulate the date/time intervals using sets of discrete points but this seems not really effective.

So I am looking for an existing datastructure which already provides these set operations out of the box using intervals.

Just for clarification, here is an illustration of what I am looking for.

• existing: a collection of time intervals
• to be added: interval which should be added to the collection
• return value: the subintervals(s) of the interval which should be added which are not yet in the datastructure
• result: the collection of intervals including the one which has just been added

//       case 0
//       existing         *********************************************
//       to be added                      ********
//       return value                     --empty--  
//       result           *********************************************
//       
//       case 1
//       existing             *****************************************
//       to be added      ************
//       return value     ****
//       result           *********************************************
//       
//       case 2
//       existing               ***************************************
//       to be added      ****
//       return value     ****
//       result           ****  ***************************************
//       
//       case 3
//       existing         *****************************************
//       to be added                                       ************
//       return value                                              ****
//       result           *********************************************
//       
//       case 4
//       existing         ***************************************
//       to be added                                               ****
//       return value                                              ****
//       result           ***************************************  ****
//       
//       case 5
//       existing         *****************             ***************
//       to be added                           ****
//       return value                          ****
//       result           *****************    ****     ***************
//       
//       case 6
//       existing         *****************             ***************
//       to be added                    ********
//       return value                      *****
//       result           **********************        ***************
//       
//       case 7
//       existing         *****************             ***************
//       to be added                               ********
//       return value                              *****
//       result           *****************        ********************
//       
//       case 8
//       existing         *****************    ****     ***************
//       to be added                     *****************
//       return value                      ****    *****
//       result           *********************************************
//       
//       ......
//