CGAL 4.7 - Interval Skip List: CGAL::Interval_skip_list< Interval > Class Template Reference

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - Interval Skip List

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members | Related Functions
CGAL::Interval_skip_list< Interval > Class Template Reference
Interval Skip List Reference

`#include <CGAL/Interval_skip_list.h>`

## Definition

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`. More...

## 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. More...

## 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. More...
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. More...
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`. More...
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

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

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`.

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`.

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

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`.