Good data structure for finding date intervals including a given date

[Jean-Daniel]

Hello,

I have a long list of n date intervals that gets added or suppressed
intervals regularly. I am looking for a fast way to find the intervals
containing a given date, without having to check all intervals (less
than O(n)).

Do you know the best way to do this in Python with the stdlib?

A variant of the red black trees can do the job quickly [1], is this a
good enough use case to discuss the inclusion of a red black tree
implementation in the stdlib?

This has been discussed here: http://bugs.python.org/issue1324770 ,
and lack of good use case was the reason the bug was closed. A dict
implemented with red black trees is slower (but not too slow) at
inserting, searching and deleting but the dict is always kept ordered.
Bigger projects have their own implementation of ordered dict so such
datastructures in the standard library would help the porting of the
project to other platforms. Take the example of the zodb and the
C-only implementation of the btree: btree in the stdlib in Python
would help the porting to GAE or pypy [2].

Cheers,

[1] in the "Cormen" book:
http://en.wikipedia.org/wiki/Introduction_to_Algorithms
[2] https://blueprints.launchpad.net/zodb/+spec/remove-btree-dependency