...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost::icl::interval_map — implements a map as a map of intervals - on insertion overlapping intervals are split and associated values are combined.
// In header: <boost/icl/interval_map.hpp>
template<typename DomainT, typename CodomainT,
typename Traits = icl::partial_absorber,
ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
ICL_COMBINE Combine = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
ICL_SECTION Section = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT),
ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
ICL_ALLOC Alloc = std::allocator>
class interval_map : public boost::icl::interval_base_map< boost::icl::interval_map< DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc >, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc >
{
public:
// types
typedef Traits traits; // Traits of an itl map.
typedef interval_map< DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > type;
typedef split_interval_map< DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > split_type;
typedef type overloadable_type; // Auxilliary type for overloadresolution.
typedef type joint_type;
typedef interval_base_map< type, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > base_type;
typedef base_type::iterator iterator; // iterator for iteration over intervals
typedef base_type::value_type value_type; // value type of the implementing container
typedef base_type::element_type element_type; // Conceptual is a map a set of elements of type element_type
.
typedef base_type::segment_type segment_type; // Type of an interval containers segment, that is spanned by an interval.
typedef base_type::domain_type domain_type; // Domain type (type of the keys) of the map.
typedef base_type::codomain_type codomain_type; // Domain type (type of the keys) of the map.
typedef base_type::domain_mapping_type domain_mapping_type; // Auxiliary type to help the compiler resolve ambiguities when using std::make_pair.
typedef base_type::interval_mapping_type interval_mapping_type; // Auxiliary type for overload resolution.
typedef base_type::ImplMapT ImplMapT; // Container type for the implementation.
typedef base_type::size_type size_type; // The size type of an interval which is mostly std::size_t.
typedef base_type::codomain_combine codomain_combine;
typedef interval_set< DomainT, Compare, Interval, Alloc > interval_set_type;
typedef interval_set_type set_type;
typedef set_type key_object_type;
// construct/copy/destruct
interval_map();
interval_map(const interval_map &);
template<typename SubType>
explicit interval_map(const interval_base_map< SubType, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > &);
explicit interval_map(domain_mapping_type &);
explicit interval_map(const value_type &);
interval_map(interval_map &&);
template<typename SubType>
interval_map&
operator=(const interval_base_map< SubType, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > &);
interval_map& operator=(interval_map &&);
// public member functions
typedef ICL_INTERVAL_TYPE(Interval, DomainT, Compare);
template<typename SubType>
void assign(const interval_base_map< SubType, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > &);
// private member functions
iterator handle_inserted(iterator);
void handle_inserted(iterator, iterator);
template<typename Combiner> void handle_left_combined(iterator);
template<typename Combiner> void handle_combined(iterator);
template<typename Combiner>
void handle_preceeded_combined(iterator, iterator &);
template<typename Combiner>
void handle_succeeded_combined(iterator, iterator);
void handle_reinserted(iterator);
template<typename Combiner>
void gap_insert_at(iterator &, iterator, const interval_type &,
const codomain_type &);
};
interval_map
public
construct/copy/destructinterval_map();Default constructor for the empty object.
interval_map(const interval_map & src);Copy constructor.
template<typename SubType> explicit interval_map(const interval_base_map< SubType, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > & src);Copy constructor for base_type.
explicit interval_map(domain_mapping_type & base_pair);
explicit interval_map(const value_type & value_pair);
interval_map(interval_map && src);Move constructor.
template<typename SubType> interval_map& operator=(const interval_base_map< SubType, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > & src);Assignment operator.
interval_map& operator=(interval_map && src);Move assignment operator.
interval_map
public member functionstypedef ICL_INTERVAL_TYPE(Interval, DomainT, Compare);The interval type of the
map
. template<typename SubType> void assign(const interval_base_map< SubType, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > & src);Assignment from a base
interval_map
. interval_map
private member functionsiterator handle_inserted(iterator it_);
void handle_inserted(iterator prior_, iterator it_);
template<typename Combiner> void handle_left_combined(iterator it_);
template<typename Combiner> void handle_combined(iterator it_);
template<typename Combiner> void handle_preceeded_combined(iterator prior_, iterator & it_);
template<typename Combiner> void handle_succeeded_combined(iterator it_, iterator next_);
void handle_reinserted(iterator insertion_);
template<typename Combiner> void gap_insert_at(iterator & it_, iterator prior_, const interval_type & end_gap, const codomain_type & co_val);