Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

Required Concepts

There are uniform requirements for the template parameters across icl's class templates. The template parameters can be grouped with respect to those requirements.

used in

Kind

Parameter

Instance

Description

Domain order

Intervals, Sets, Maps

typename

DomainT

For the type DomainT of key elements ...

template

Compare

Compare<DomainT>

... there is an order Compare

Interval type

interval_sets/maps

typename

IntervalT

... the IntervalT parameter has to use the same element type and order.

Codomain aggregation

Maps

typename

CodomainT

For the type CodomainT of associated values ...

template

Combine

Combine<CodomainT>

... there is a binary functor Combine<CodomainT>() to combine them

Inverse<Combine<CodomainT>>

... and implicitly an Inverse functor to inversely combine them.

template

Section

Section<CodomainT>

Intersection is propagated to CodomainT values via functor Section<CodomainT>()

Memory allocation

Sets, Maps

template

Alloc

Alloc<various>

An allocator can be chosen for memory allocation.

Requirements on DomainT

The next table gives an overview over the requirements for template parameter DomainT. Some requirements are dependent on conditions. Column operators shows the operators and functions that are expected for DomainT, if the default order Compare = std::less is used.

Parameter

Condition

Operators

Requirement

DomainT

DomainT(), <

Regular<DomainT> && StrictWeakOrdering<DomainT,Compare>

++, unit_element<CodomainT>::value()

&& (IsIncrementable<DomainT>||HasUnitElement<DomainT>)

IsIntegral<DomainT>

++, --

IsIncrementable<DomainT> && IsDecrementable<DomainT>

A domain type DomainT for intervals and interval containers has to satisfy the requirements of concept Regular which implies among other properties the existence of a copy and a default constructor. In addition IsIncrementable or HasUnitElement is required for DomainT. In the icl we represent an empty closed interval as interval [b,a] where a < b (here < represents Compare<DomainT>()). To construct one of these empty intervals as default constructor for any type DomainT we choose [1,0], where 0 is a null-value or identity_element and 1 is a one-value or unit_element:

interval() := [unit_element<DomainT>::value(), identity_element<DomainT>::value()] //pseudocode

Identity_elements are implemented via call of the default constructor of DomainT. A unit_element<T>::value() is implemented by default as a identity_element, that is incremented once.

template <class Type> 
inline Type unit_element<Type>::value(){ return succ(identity_element<Type>::value()); };

So a type DomainT that is incrementable will also have an unit_element. If it does not, a unit_element can be provided. A unit_element can be any value, that is greater as the identity_element in the Compare order given. An example of a type, that has an identity_element but no increment operation is string. So for std::string a unit_element is implemented like this:

// Smallest 'visible' string that is greater than the empty string.
template <>    
inline std::string unit_element<std::string>::value(){ return std::string(" "); };

Just as for the key type of std::sets and maps template parameter Compare is required to be a strict weak ordering on DomainT.

Finally, if DomainT is an integral type, DomainT needs to be incrementable and decrementable. This 'bicrementability' needs to be implemented on the smallest possible unit of the integral type. This seems like being trivial but there are types like e.g. boost::date_time::ptime, that are integral in nature but do not provide the required in- and decrementation on the least incrementable unit. For icl::intervals incementation and decementation is used for computations between open to closed interval borders like e.g. [2,43) == [2,42]. Such computations always need only one in- or decrementation, if DomainT is an integral type.

Requirements on IntervalT

Requirements on the IntervalT parameter are closely related to the DomainT parameter. IntervalT has two associated types itself for an element type and a compare order that have to be consistent with the element and order parameters of their interval containers. IntervalT then has to implement an order called exclusive_less. Two intervals x, y are exclusive_less

icl::exclusive_less(x, y)

if all DomainT elements of x are less than elements of y in the Compare order.

Parameter

Operators

Requirement

IntervalT

exclusive_less

IsExclusiveLessComparable<Interval<DomainT,Compare> >

Requirements on CodomainT

Summarized in the next table are requirements for template parameter CodomainT of associated values for Maps. Again there are conditions for some of the requirements. Column operators contains the operators and functions required for CodomainT, if we are using the default combiner Combine = icl::inplace_plus.

Parameter

Condition

Operators

Requirement

CodomainT

add, subtract, intersect unused

CodomainT(), ==

Regular<CodomainT> which implies

DefaultConstructible<CodomainT> && EqualityComparable<CodomainT>

only add used

+=

&& Combinable<CodomainT,Combine>

... and also subtract used

-=

&& Combinable<CodomainT,Inverse<Combine> >

Section used and CodomainT is a set

&=

&& Intersectable<CodomainT,Section>

The requirements on the type CodomainT of associated values for a icl::map or interval_map depend on the usage of their aggregation functionality. If aggregation on overlap is never used, that is to say that none of the addition, subtraction and intersection operations (+, +=, add, -, -=, subtract, &, &=, add_intersection) are used on the interval_map, then CodomainT only needs to be Regular. Regular object semantics implies DefaultConstructible and EqualityComparable which means it has a default ctor CodomainT() and an operator ==.

Use interval_maps without aggregation, if the associated values are not addable but still are attached to intervals so you want to use interval_maps to handle them. As long as those values are added with insert and deleted with erase interval_maps will work fine with such values.

If only addition is used via interval_map's +, += or add but no subtraction, then CodomainT need to be Combinable for functor template Combine. That means in most cases when the default implementation inplace_plus for Combine is used, that CodomainT has to implement operator +=.

For associated value types, that are addable but not subtractable like e.g. std::string it usually makes sense to use addition to combine values but the inverse combination is not desired.

interval_map<int,std::string> cat_map;
cat_map += make_pair(interval<int>::rightopen(1,5),std::string("Hello"));
cat_map += make_pair(interval<int>::rightopen(3,7),std::string(" world"));
cout << "cat_map: " << cat_map << endl;
//cat_map: {([1,3)->Hello)([3,5)->Hello world)([5,7)-> world)}

For complete aggregation functionality an inverse aggregation functor on a Map's CodomainT is needed. The icl provides a metafunction inverse for that purpose. Using the default Combine = inplace_plus that relies on the existence of operator += on type CodomainT metafunction inverse will infer inplace_minus as inverse functor, that requires operator -= on type CodomainT.

In the icl's design we make the assumption, in particular for the default setting of parameters Combine = inplace_plus, that type CodomainT has a neutral element or identity_element with respect to the Combine functor.


PrevUpHomeNext