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

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.