yat  0.18pre
Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
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 >:
theplu::yat::utility::SegmentTree< std::set< Segment< T, Compare >, SegmentCompare< T, Compare > >, Compare, Identity< const Segment< 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, iteratoroverlap_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:

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