CGAL 6.1 - Interval Skip List

Loading...
Searching...
No Matches
List of all members | Related Functions
CGAL::Interval_skip_list< Interval > Class Template Reference
Reference Manual

`#include <CGAL/Interval_skip_list.h>`

## Definition

template<typename Interval>
class CGAL::Interval_skip_list< Interval >

The class `Interval_skip_list` is a dynamic data structure that allows to find all members of a set of intervals that overlap a point.

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.

Examples
  Interval_skip_list/intervals.cpp, and Interval_skip_list/isl_terrain.cpp.

## Related Functions
(Note that these are not member functions.)
template<typenme Interval>
ostream & | operator<< (ostream &os, const Interval_skip_list< Interval > &isl)
| Inserts the interval skip list `isl` into the stream `os`.

## Types
typedef Interval::Value | Value
| the type of inf and sup of the interval.
typedef unspecified_type | const_iterator
| An iterator over all intervals.

## Creation
| Interval_skip_list ()
| Default constructor.
template<class InputIterator >
| Interval_skip_list (InputIterator first, InputIterator last)
| Constructor that inserts the iterator range `[first, last)` in the interval skip list.

## Operations
template<class InputIterator >
int | insert (InputIterator first, InputIterator last)
| Inserts the iterator range `[first, last)` in the interval skip list, and returns the number of inserted intervals.
void | insert (const Interval &i)
| Inserts interval `i` in the interval skip list.
bool | remove (const Interval &i)
| Removes interval `i` from the interval skip list.
bool | is_contained (const Value &v)
| Returns `true` iff there is an interval that contains `v`.
template<class OutputIterator >
OutputIterator | find_intervals (const Value &v, OutputIterator out)
| Writes the intervals `i` with `i.inf()` \( \leq\) `v` \( \leq\) `i.sup` to the output iterator `out`.
void | clear ()
| Removes all intervals from the interval skip list.
const_iterator | begin () const
| Returns an iterator over all intervals.
const_iterator | end () const
| Returns the past the end iterator.

## Constructor & Destructor Documentation

## ◆ Interval_skip_list()

template<typename Interval >
template<class InputIterator >

CGAL::Interval_skip_list< Interval >::Interval_skip_list | ( | InputIterator | first,
|  | InputIterator | last
| ) |  |

Constructor that inserts the iterator range `[first, last)` in the interval skip list.

Template Parameters

  InputIterator | must be an input iterator with value type `Interval`.

## Member Function Documentation

## ◆ find_intervals()

template<typename Interval >
template<class OutputIterator >

OutputIterator CGAL::Interval_skip_list< Interval >::find_intervals | ( | const Value & | v,
|  | OutputIterator | out
| ) |  |

Writes the intervals `i` with `i.inf()` \( \leq\) `v` \( \leq\) `i.sup` to the output iterator `out`.

Template Parameters

  OutputIterator | must be an output iterator with value type `Interval`.

## ◆ insert()

template<typename Interval >
template<class InputIterator >

int CGAL::Interval_skip_list< Interval >::insert | ( | InputIterator | first,
|  | InputIterator | last
| ) |  |

Inserts the iterator range `[first, last)` in the interval skip list, and returns the number of inserted intervals.

Template Parameters

  InputIterator | must be an input iterator with value type `Interval`.

## ◆ remove()

template<typename Interval >

bool CGAL::Interval_skip_list< Interval >::remove | ( | const Interval & | i | ) |

Removes interval `i` from the interval skip list.

Returns `true` iff removal was successful.

## Friends And Related Function Documentation

## ◆ operator<<()

template<typenme Interval>

ostream & operator<< | ( | ostream & | os,
|  | const Interval_skip_list< Interval > & | isl
| ) |  |
| related

Inserts the interval skip list `isl` into the stream `os`.

Precondition
  The output operator must be defined for `Interval`.