Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL

CGAL::Interval_skip_list<Interval>

Definition

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>

Types

typedef Interval::Value Value; the type of inf and sup of the interval.

Interval_skip_list<Interval>::const_iterator
An iterator over all intervals.

Creation

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.
Precondition: The value_type of first and last is Interval.

Operations

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.
Precondition: The value_type of first and last is Interval.

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.
Precondition: The value_type of out is Interval.

void isl.clear () Removes all intervals from the interval skip list.

const_iterator isl.begin () Returns an iterator over all intervals.

const_iterator isl.end () Returns the past the end iterator.

I/O

ostream& ostream& os << isl Inserts the interval skip list isl into the stream os.
Precondition: The output operator must be defined for Interval.

Implementation

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.

Next: Interval
Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL
CGAL Open Source Project. Release 3.7. 14 October 2010.