"Fossies" - the Fresh Open Source Software Archive

Member "doc_html/Interval_skip_list/classCGAL_1_1Interval__skip__list.html" (8 Nov 2019, 29610 Bytes) of package /linux/misc/CGAL-4.14.2-doc_html.tar.xz:


Caution: In this restricted "Fossies" environment the current HTML page may not be correctly presentated and may have some non-functional links. You can here alternatively try to browse the pure source code or just view or download the uninterpreted raw source code. If the rendering is insufficient you may try to find and view the page on the CGAL-4.14.2-doc_html.tar.xz project site itself.

\( \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.14.2 - Interval Skip List
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

◆ 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
InputIteratormust 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
OutputIteratormust 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
InputIteratormust 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.