rangemap< _recordtype > Class Template Reference

An interval map container. More...

#include <rangemap.hh>

Classes
class	PartIterator
	An iterator into the interval map container. More...

Public Types
typedef _recordtype::linetype	linetype
	Integer data-type defining the linear domain.
typedef _recordtype::subsorttype	subsorttype
	The data-type used for subsorting.
typedef _recordtype::inittype	inittype
	The data-type containing initialization data for records.
typedef PartIterator	const_iterator
	The main sub-range iterator data-type.

Public Member Functions
bool	empty (void) const
	Return true if the container is empty.
void	clear (void)
	Clear all records from the container.
std::list< _recordtype >::const_iterator	begin_list (void) const
	Beginning of records.
std::list< _recordtype >::const_iterator	end_list (void) const
	End of records.
std::list< _recordtype >::iterator	begin_list (void)
	Beginning of records.
std::list< _recordtype >::iterator	end_list (void)
	End of records.
const_iterator	begin (void) const
	Beginning of sub-ranges.
const_iterator	end (void) const
	Ending of sub-ranges.
std::pair< const_iterator, const_iterator >	find (linetype a) const
	Find sub-ranges intersecting the given boundary point. More...
std::pair< const_iterator, const_iterator >	find (linetype a, const subsorttype &subsort1, const subsorttype &subsort2) const
	Find sub-ranges intersecting given boundary point, and between given subsorts. More...
const_iterator	find_begin (linetype point) const
	Find beginning of sub-ranges that contain the given boundary point. More...
const_iterator	find_end (linetype point) const
	Find ending of sub-ranges that contain the given boundary point. More...
const_iterator	find_overlap (linetype point, linetype end) const
	Find first record overlapping given interval. More...
std::list< _recordtype >::iterator	insert (const inittype &data, linetype a, linetype b)
	Insert a new record into the container. More...
void	erase (typename std::list< _recordtype >::iterator v)
	Erase a given record from the container. More...
void	erase (const_iterator iter)
	Erase a record given an iterator.

Detailed Description

template<typename _recordtype>
class rangemap< _recordtype >

An interval map container.

A container for records occupying (possibly overlapping) intervals. I.e. a map from a linear ordered domain to (multiple) records. The recordtype is the main object in the container, it must support:

• recordtype() a constructor taking no parameters
• getFirst() beginning of range
• getLast() end of range (inclusive)
• getSubsort() retrieve the subsorttype object (see below)
• initialize(inittype,linetype,linetype) an initializer routine

The recordtype must define data-types:

• linetype
• subsorttype
• inittype

linetype is the data-type of elements in the linear domain. It must support:

• <,<= Comparisons
• ==,!= Equality
• + <constant> Addition of integers
• - <constant> Subtraction of integers

subsorttype describes how overlapping intervals can be sub-sorted. It must support:

• <
• subsorttype(false) constructor with false produces a minimal value
• subsorttype(true) constructor with true produces a maximal value
• copy constructor

inittype is extra initialization data for the recordtype

The main interval map is implemented as a multiset of disjoint sub-ranges mapping to the recordtype objects. After deduping the sub-ranges form the common refinement of all the possibly overlapping recordtype ranges. A sub-range is duplicated for each distinct recordtype that overlaps that sub-range. The sub-range multiset is updated with every insertion or deletion of recordtype objects into the container, which may insert new or delete existing boundary points separating the disjoint subranges.

Member Function Documentation

erase()

template<typename _recordtype>

void rangemap< _recordtype >::erase

(

typename std::list< _recordtype >::iterator

v

)

Erase a given record from the container.

Parameters

v	is the iterator to the record to be erased

find() [1/2]

template<typename _recordtype >

std::pair< typename rangemap< _recordtype >::const_iterator, typename rangemap< _recordtype >::const_iterator > rangemap< _recordtype >::find

(

linetype

point

)

const

Find sub-ranges intersecting the given boundary point.

Parameters

point

is the given boundary point

Returns

begin/end iterators over all intersecting sub-ranges

find() [2/2]

template<typename _recordtype >

std::pair< typename rangemap< _recordtype >::const_iterator, typename rangemap< _recordtype >::const_iterator > rangemap< _recordtype >::find	(	linetype	point,
		const subsorttype &	sub1,
		const subsorttype &	sub2
	)		const

Find sub-ranges intersecting given boundary point, and between given subsorts.

Parameters

point	is the given boundary point
sub1	is the starting subsort
sub2	is the ending subsort

Returns

begin/end iterators over all intersecting and bounded sub-ranges

find_begin()

template<typename _recordtype >

rangemap< _recordtype >::const_iterator rangemap< _recordtype >::find_begin

(

linetype

point

)

const

Find beginning of sub-ranges that contain the given boundary point.

Parameters

point

is the given boundary point

Returns

iterator to first sub-range of intersects the boundary point

find_end()

template<typename _recordtype >

rangemap< _recordtype >::const_iterator rangemap< _recordtype >::find_end

(

linetype

point

)

const

Find ending of sub-ranges that contain the given boundary point.

Parameters

point

is the given boundary point

Returns

iterator to first sub-range after that does not intersect the boundary point

find_overlap()

template<typename _recordtype >

rangemap< _recordtype >::const_iterator rangemap< _recordtype >::find_overlap	(	linetype	point,
		linetype	end
	)		const

Find first record overlapping given interval.

Parameters

point	is the start of interval to test
end	is the end of the interval to test

Returns

iterator to first sub-range of an intersecting record (or end)

insert()

template<typename _recordtype >

std::list< _recordtype >::iterator rangemap< _recordtype >::insert	(	const inittype &	data,
		linetype	a,
		linetype	b
	)

Insert a new record into the container.

Parameters

data	is other initialization data for the new record
a	is the start of the range occupied by the new record
b	is the (inclusive) end of the range

Returns

an iterator to the new record

---

The documentation for this class was generated from the following file:

• rangemap.hh