Navigation: Up, Table of Contents, Bibliography, Index, Title Page

## CGAL::Interval_skip_list<Interval>

### Definition

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>

### 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 succesful.
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(log2 n), if the segment endpoints are chosen from a continuous distribution. A stabbing query takes expected time O(logn), and finding all intervals that contain a point takes expected time O(logn + 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: Table of Contents, Bibliography, Index, Title Page

The CGAL Project . Tue, December 21, 2004 .