Working with dates : complex problem

[Peter Otten]

Thibaut DIRLIK wrote:

> Hi,
> 
> I've a list of python objects with dates attributes. This list is ordered
> by one of these date. Elements mandatory follow each other :
> 
> Element #1                   Element #2           Element #3
> |-------------------------|--------------|--------------------------|
> 
> Now, I want to "insert" an element in this timeline. This imply that I
> will have to resize some elements :
> 
> Element #1                   Element #2           Element #3
> |-------------------------|--------------|--------------------------|
>                 New element
>           |----------------------|
> 
> And after resize :
> 
> Element #1      New element       Element #2       Element #3
> |---------|----------------------|---------|--------------------------|
> 
>           |----------------------|
> 
> My question is the following : how can I know (easily) which elements my
> "New element" is "over", which,
> in my example would have returned ['Element #1', 'Element #2'].
> 
> Elements objets are simple Python objects with dates :
> 
> obj.begin = datetime()
> obj.end = datetime()
> 
> I'm looking for the more Pythonic way to handle this problem, thanks !

Untested:

def insert(timeline, interval):
    keys = [item.begin for item in timeline]
    where = bisect.bisect(keys, interval.begin)
    if where > 0:
        # adjust previous interval to avoid a gap or an intersection
        timeline[where-1].end = interval.begin

    # remove intervals covered by the new interval
    while where < len(timeline) and timeline[where].end < interval.end:
        del timeline[where]

    if where < len(timeline):
        # adjust subsequent interval to avoid gap or intersection
        timeline[where].begin = interval.end

    timeline.insert(where, interval)

If you implement comparison for your interval type you won't need the 
intermediate keys list. The functools.total_ordering decorator may help you 
with that.