yat  0.18pre
Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
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. More...
 
typedef Container::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 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) 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, iteratoroverlap_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.

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:

Generated on Sun Sep 27 2020 02:26:14 for yat by  doxygen 1.8.11