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

Base Class for SegmentSet and SegmentMap. More...

#include <yat/utility/SegmentTree.h>

Public Types
typedef Container::key_type	key_type
	key type is same as Container 's key_type.
typedef Container::value_type	value_type
	value type is same as Container 's value_type.
typedef key_type::value_type	element_type
	element type is same as key_type 's value_type.
typedef Container::key_compare	key_compare
	key compare
typedef Container::value_compare	value_compare
	value 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 SegmentTree with no segments
virtual	~SegmentTree (void)
	Destructor.
const_iterator	begin (void) const
iterator	begin (void)
void	clear (void)
	erases all values
size_type	count (const element_type &element) const
bool	empty (void) const
const_iterator	end (void) const
iterator	end (void)
void	erase (iterator first, iterator last)
	erase values in range [first, last)
void	erase (iterator pos)
iterator	find (const element_type &element)
const_iterator	find (const element_type &element) const
std::pair< iterator, bool >	insert (const value_type &value)
	insert value
key_compare	key_comp (void) const
iterator	lower_bound (const element_type &element)
	similar to lower_bound in std::set and std::map
const_iterator	lower_bound (const element_type &element) const
	similar to lower_bound in std::set and std::map
size_type	size (void) const
iterator	upper_bound (const element_type &element)
const_iterator	upper_bound (const element_type &element) const
	similar to upper_bound in std::set and std::map
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 Typedef Documentation

template<class Container, class Compare, class Value2Key>

typedef key_type::value_type theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::element_type

element type is same as key_type 's value_type.

If the key held is Segment<T>, value_type is T.

template<class Container, class Compare, class Value2Key>

typedef Container::key_type theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::key_type

key type is same as Container 's key_type.

Typically Segment<element_type>.

template<class Container, class Compare, class Value2Key>

typedef Container::value_type theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::value_type

value type is same as Container 's value_type.

Typically a Segment<element_type> or pair<const Segment<element_type>, Data>.

Member Function Documentation

template<class Container, class Compare, class Value2Key>

const_iterator theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::begin ( void  ) const

inline

Returns

const iterator pointing to beginning of container

template<class Container, class Compare, class Value2Key>

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

inline

Returns

iterator pointing to beginning of container

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

Returns

1 if there is a Segment 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 if size is zero

template<class Container, class Compare, class Value2Key>

const_iterator theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::end ( void  ) const

inline

Returns

a const_iterator pointing to the end of container

template<class Container, class Compare, class Value2Key>

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

inline

Returns

end of container

template<class Container, class Compare, class Value2Key>

void theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::erase ( iterator  first, iterator  last  )

inline

erase values in range [first, last)

Since

New in yat 0.8

template<class Container, class Compare, class Value2Key>

void theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::erase ( iterator  pos )

inline

erase value pointed to by pos

Since

New in yat 0.8

template<class Container , class Compare , class Value2Key >

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

(

const element_type &

element

)

Returns

iterator pointing to value containing element

If no value contains element, end() is returned.

template<class Container , class Compare , class Value2Key >

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

(

const element_type &

element

)

const

Returns

const iterator pointing to value containing element

If no value contains element, end() is returned.

Returns

an iterator pointing to the Segment that contains element. If no Segment contains element, 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 &

value

)

insert value

if value does not overlap with container, insert segment; otherwise do nothing.

Returns

a pair where pair.first points to the inserted value or if value was not inserted it points to a value in container that overlaps with value; pair.second is true if value was inserted.

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 two keys (Segment)

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

)

similar to lower_bound in std::set and std::map

Returns

iterator pointing to first value whose key overlaps with element or is greater than element.

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

similar to lower_bound in std::set and std::map

Returns

const iterator pointing to first value whose key 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 )

inlineprotected

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 values in container

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

)

Returns

iterator pointing to first segment that is greater than segment.

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

similar to upper_bound in std::set and std::map

Returns

iterator pointing to first value whose key is greater than element.

template<class Container, class Compare, class Value2Key>

value_compare theplu::yat::utility::SegmentTree< Container, Compare, Value2Key >::value_comp ( void  ) const

inline

Returns

the value_compare object used by the class to sort values

---

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

• yat/utility/SegmentTree.h