\( \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.4 - Interval Skip List
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Interval_skip_list< Interval > Class Template 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
InputIteratormust 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
OutputIteratormust 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
InputIteratormust 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.