The class Interval_skip_list<Interval> is a dynamic datastructure that allows to find all members of a set of intervals that overlap a point.
#include <CGAL/Interval_skip_list.h>
 
 the type of inf and sup of the interval. 
 
An iterator over all intervals.

 
Default constructor.
 
 
 
Constructor that inserts the iterator range [first, last) in the interval skip list. Precondition: The value_type of first and last is Interval.

 

 
Inserts the iterator range [first, last) in the interval skip list, and returns
the number of inserted intervals. Precondition: The value_type of first and last is Interval.  

 
inserts interval i in the interval skip list.  

 
removes interval i from the interval skip list. Returns true iff removal was succesful.  

 
Returns true iff there is an interval that contains v.  
 

 
Writes the intervals i with i.inf() $$ v $$ i.sup to the
output iterator out. Precondition: The value_type of out is Interval.  

 Removes all intervals from the interval skip list. 

 Returns an iterator over all intervals. 

 Returns the past the end iterator. 

 
Inserts the interval skip list isl into the stream os. Precondition: The output operator must be defined for Interval. 
The insertion and deletion of a segment in the interval skip list takes expected time $$O(log$$^{2} n), if the segment endpoints are chosen from a continuous distribution. A stabbing query takes expected time $$O(log$$n), and finding all intervals that contain a point takes expected time $$O(log$$n + k), where $$k is the number of intervals.
The implementation is based on the code developed by Eric N. Hansen, which can be found at http://wwwpub.cise.ufl.edu/~hanson/ISlists/. Attention, this code has memory leaks.