The class Interval_skip_list<Interval> is a dynamic data structure 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.
|
| ||||
|
| |||
Inserts the iterator range [first, last) in the interval skip list, and returns
the number of inserted intervals.
| ||||
|
| inserts interval i in the interval skip list. | ||
|
| removes interval i from the interval skip list. Returns true iff removal was successful. | ||
|
| 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.
| ||||
|
| 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.
|
The insertion and deletion of a segment in the interval skip list takes expected time log, if the segment endpoints are chosen from a continuous distribution. A stabbing query takes expected time log, and finding all intervals that contain a point takes expected time log, where is the number of intervals.
The implementation is based on the code developed by Eric N. Hansen, which can be found at http://www-pub.cise.ufl.edu/~hanson/IS-lists/. Attention, this code has memory leaks.