|
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>
| typedef Interval::Value | Value; | the type of inf and sup of the interval. |
| Interval_skip_list<Interval>::const_iterator | |
|
An iterator over all intervals.
| |
| Interval_skip_list<Interval> isl; | |||
|
Default constructor.
| |||
| template < class InputIterator > | |||
| Interval_skip_list<Interval> isl ( InputIterator first, InputIterator last); | |||
Constructor that inserts the iterator range [first, last) in the interval skip list.
| |||
| template < class InputIterator > | ||||
| int | isl.insert ( InputIterator first, InputIterator last) | |||
Inserts the iterator range [first, last) in the interval skip list, and returns
the number of inserted intervals.
| ||||
| void | isl.insert ( Interval i) | inserts interval i in the interval skip list. | ||
| bool | isl.remove ( Interval i) | removes interval i from the interval skip list. Returns true iff removal was successful. | ||
| bool | isl.is_contained ( Value v) | Returns true iff there is an interval that contains v. | ||
| template < class OutputIterator > | ||||
| OutputIterator | isl.find_intervals ( Value v, OutputIterator out) | |||
Writes the intervals i with i.inf() ≤ v ≤ i.sup to the
output iterator out.
| ||||
| void | isl.clear () | Removes all intervals from the interval skip list. | ||
| const_iterator | isl.begin () const | Returns an iterator over all intervals. | ||
| const_iterator | isl.end () const | Returns the past the end iterator. | ||
| ostream& | ostream& os << isl |
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 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://www-pub.cise.ufl.edu/~hanson/IS-lists/. Attention, this code has memory leaks.