yat  0.8.3pre
Public Types | Public Member Functions | Protected Member Functions | Protected Attributes
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 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 &vt) 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
 similar to upper_bound in std::set and std::map

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 vt) 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 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 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

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

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

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

Generated on Thu Dec 20 2012 03:13:00 for yat by  doxygen 1.8.0-20120409