theplu::yat::utility::SegmentSet< T, Compare > Class Template Reference

a set of Segments More...

#include <yat/utility/SegmentSet.h>

Inheritance diagram for theplu::yat::utility::SegmentSet< T, Compare >:

Public Types
typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >::key_type	key_type
	key type is same as Container 's key_type. More...
typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >::value_type	value_type
	value type is same as Container 's value_type. More...
typedef key_type::value_type	element_type
	element type is same as key_type 's value_type. More...
typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >::key_compare	key_compare
	key compare
typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >::value_compare	value_compare
	value compare
typedef Compare	element_compare
	element compare
typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >::pointer	pointer
	pointer
typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >::reference	reference
	reference
typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >::const_reference	const_reference
	const reference
typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >::size_type	size_type
	size_type
typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >::difference_type	difference_type
	difference_type
typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >::iterator	iterator
	iterator
typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >::const_iterator	const_iterator
	const_iterator

Public Member Functions
	SegmentSet (void)
	creates a set with no segments
me::const_iterator	insert_merge (const typename me::value_type &segment)
me::iterator	insert_merge (typename me::iterator hint, const typename me::value_type &segment)
	insert with a hint More...
template<typename Iterator >
void	insert_merge (Iterator first, Iterator last)
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) More...
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 More...
key_compare	key_comp (void) const
iterator	lower_bound (const element_type &element)
	similar to lower_bound in std::set and std::map More...
const_iterator	lower_bound (const element_type &element) const
	similar to lower_bound in std::set and std::map More...
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 More...
value_compare	value_comp (void) const

Protected Member Functions
std::pair< iterator, iterator >	overlap_range (const key_type &segment)

Protected Attributes
std::set< Segment< T, Compare > , SegmentCompare< T, Compare > >	container_
	underlying container

Detailed Description

template<typename T, class Compare = std::less<T>>
class theplu::yat::utility::SegmentSet< T, Compare >

a set of Segments

A container that holds a set of Segment. The Segments cannot overlap.

Since

new in yat 0.7

Member Typedef Documentation

typedef key_type::value_type theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::element_type

inherited

element type is same as key_type 's value_type.

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

typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > ::key_type theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::key_type

inherited

key type is same as Container 's key_type.

Typically Segment<element_type>.

typedef std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > ::value_type theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::value_type

inherited

value type is same as Container 's value_type.

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

Member Function Documentation

const_iterator theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::begin ( void  ) const

inlineinherited

Returns

const iterator pointing to beginning of container

iterator theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::begin ( void  )

inlineinherited

Returns

iterator pointing to beginning of container

size_type theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::count ( const element_type &  element ) const

inherited

Returns

1 if there is a Segment that overlaps with element

bool theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::empty ( void  ) const

inlineinherited

Returns

true if size is zero

const_iterator theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::end ( void  ) const

inlineinherited

Returns

a const_iterator pointing to the end of container

iterator theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::end ( void  )

inlineinherited

Returns

end of container

void theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::erase ( iterator  first, iterator  last  )

inlineinherited

erase values in range [first, last)

Since

New in yat 0.8

void theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::erase ( iterator  pos )

inlineinherited

erase value pointed to by pos

Since

New in yat 0.8

iterator theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::find ( const element_type &  element )

inherited

Returns

iterator pointing to value containing element

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

const_iterator theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::find ( const element_type &  element ) const

inherited

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.

std::pair<iterator, bool> theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::insert ( const value_type &  value )

inherited

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<typename T , class Compare = std::less<T>>

me::const_iterator theplu::yat::utility::SegmentSet< T, Compare >::insert_merge ( const typename me::value_type &  segment )

inline

insert segment into set. If there is no gap between segment and neighboring segments the segments are merged.

template<typename T , class Compare = std::less<T>>

me::iterator theplu::yat::utility::SegmentSet< T, Compare >::insert_merge ( typename me::iterator  hint, const typename me::value_type &  segment  )

inline

insert with a hint

Similar to insert_merge(1) but hint help to find where to insert segment. For the hint to be useful, segment should not be greater than element hint points to and not smaller than element –hint points to.

Since

New in yat 0.13

template<typename T , class Compare = std::less<T>>

template<typename Iterator >

void theplu::yat::utility::SegmentSet< T, Compare >::insert_merge ( Iterator  first, Iterator  last  )

inline

Insert range [first, last). Same result as inserting them individually, but inserting a range is potentially faster, especially if range is sorted and set is sparse compared to range.

Since

new in yat 0.13

key_compare theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::key_comp ( void  ) const

inlineinherited

Returns

Comparison functor to compare two keys (Segment)

iterator theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::lower_bound ( const element_type &  element )

inherited

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.

const_iterator theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::lower_bound ( const element_type &  element ) const

inherited

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.

std::pair<iterator, iterator> theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::overlap_range ( const key_type &  segment )

inlineprotectedinherited

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

size_type theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::size ( void  ) const

inlineinherited

Returns

number of values in container

iterator theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::upper_bound ( const element_type &  element )

inherited

Returns

iterator pointing to first segment that is greater than segment.

const_iterator theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::upper_bound ( const element_type &  element ) const

inherited

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

Returns

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

value_compare theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > > , Compare, Identity< const Segment< T, Compare > & > >::value_comp ( void  ) const

inlineinherited

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/SegmentSet.h