theplu::yat::utility::SegmentTree< Container, Compare, Value2Key > Class Template Reference

Base Class for SegmentSet and SegmentMap. More...

#include <yat/utility/SegmentTree.h>

List of all members.

Public Types
typedef Container::key_type	key_type
	key type
typedef Container::value_type	value_type
	value type
typedef key_type::value_type	element_type
	element type
typedef Container::key_compare	key_compare
	key compare
typedef Container::value_compare	value_compare
	calue compare
typedef Compare	element_compare
	element compare
typedef Container::pointer	pointer
	pointer
typedef Container::reference	reference
	reference
typedef Container::const_reference	const_reference
	const reference
typedef Container::size_type	size_type
	size_type
typedef Container::difference_type	difference_type
	difference_type
typedef Container::iterator	iterator
	iterator
typedef Container::const_iterator	const_iterator
	const_iterator
Public Member Functions
	SegmentTree (void)
	creates a container with no segments
virtual	~SegmentTree (void)
	Destructor.
const_iterator	begin (void) const
iterator	begin (void)
void	clear (void)
	erases all segments
size_type	count (const element_type &element) const
bool	empty (void) const
const_iterator	end (void) const
iterator	end (void)
const_iterator	find (const element_type &vt) const
std::pair< iterator, bool >	insert (const value_type &segment)
	insert value
key_compare	key_comp (void) const
iterator	lower_bound (const element_type &element)
const_iterator	lower_bound (const element_type &element) const
size_type	size (void) const
iterator	upper_bound (const element_type &element)
const_iterator	upper_bound (const element_type &element) const
value_compare	value_comp (void) const
Protected Member Functions
std::pair< iterator, iterator >	overlap_range (const key_type &segment)
Protected Attributes
Container	container_
	underlying container

---

Detailed Description

template<class Container, class Compare, class Value2Key>
class theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >

Base Class for SegmentSet and SegmentMap.

• Container: underlying container (set or map)
• Compare: functor comparing elements (same as in Segment)
• Value2Key: functor translating a const_reference to key_type (or const&)

---

Member Function Documentation

template<class Container, class Compare, class Value2Key>

iterator theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::begin

(

void

)

[inline]

Returns:

iterator to first Segment

template<class Container, class Compare, class Value2Key>

const_iterator theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::begin

(

void

)

const [inline]

Returns:

const iterator to first Segment

template<class Container , class Compare , class Value2Key >

SegmentTree< Container, Compare, Value2Key >::size_type theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::count

(

const element_type &

element

)

const [inline]

Returns:

1 if there is a set that overlaps with element

template<class Container, class Compare, class Value2Key>

bool theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::empty

(

void

)

const [inline]

Returns:

true

template<class Container, class Compare, class Value2Key>

iterator theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::end

(

void

)

[inline]

Returns:

end of set

template<class Container, class Compare, class Value2Key>

const_iterator theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::end

(

void

)

const [inline]

Returns:

end of set

template<class Container , class Compare , class Value2Key >

SegmentTree< Container, Compare, Value2Key >::const_iterator theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::find

(

const element_type &

vt

)

const [inline]

Returns:

an iterator pointing to the Segment that contains vt. If no Segment contains vt, end() is returned.

template<typename T , class Compare , class Value2Key >

std::pair< typename SegmentTree< T, Compare, Value2Key >::iterator, bool > theplu::yat::utility::SegmentTree< T, Compare, Value2Key >::insert

(

const value_type &

segment

)

[inline]

insert value

if segment does not overlap with any segment in set, insert segment; otherwise do nothing.

Returns:

a pair where pair.first points to the added segment or if segment was not added it points to a Segment in set that overlaps with segment; pair.second is true if segment was added.

template<class Container, class Compare, class Value2Key>

key_compare theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::key_comp

(

void

)

const [inline]

Returns:

Comparison functor to compare to segments

template<typename T , class Compare , class Value2Key >

SegmentTree< T, Compare, Value2Key >::const_iterator theplu::yat::utility::SegmentTree< T, Compare, Value2Key >::lower_bound

(

const element_type &

element

)

const [inline]

Returns:

iterator pointing to first segment that overlaps with element or is greater than element.

template<typename T , class Compare , class Value2Key >

SegmentTree< T, Compare, Value2Key >::iterator theplu::yat::utility::SegmentTree< T, Compare, Value2Key >::lower_bound

(

const element_type &

element

)

[inline]

Returns:

iterator pointing to first segment that overlaps with element or is greater than element.

template<class Container, class Compare, class Value2Key>

std::pair<iterator, iterator> theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::overlap_range

(

const key_type &

segment

)

[inline, protected]

pair.first first (smallest) segment that overlaps with segment and pair.second first (smallest) segment that does not overlap with segment.

template<class Container, class Compare, class Value2Key>

size_type theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::size

(

void

)

const [inline]

Returns:

number of segments in set

template<typename T , class Compare , class Value2Key >

SegmentTree< T, Compare, Value2Key >::const_iterator theplu::yat::utility::SegmentTree< T, Compare, Value2Key >::upper_bound

(

const element_type &

element

)

const [inline]

Returns:

iterator pointing to first segment that is greater than segment.

template<typename T , class Compare , class Value2Key >

SegmentTree< T, Compare, Value2Key >::iterator theplu::yat::utility::SegmentTree< T, Compare, Value2Key >::upper_bound

(

const element_type &

element

)

[inline]

Returns:

iterator pointing to first segment that is greater than segment.

template<class Container, class Compare, class Value2Key>

value_compare theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::value_comp

(

void

)

const [inline]

Returns:

Comparison functor to compare to segments

---

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

• yat/utility/SegmentTree.h