...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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 



For the type 






Interval type 





Codomain aggregation 



For the type 












Intersection is propagated to CodomainT values via functor 

Memory allocation 




An allocator can be chosen for memory allocation. 
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 











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 nullvalue or identity_element
and 1
is a onevalue 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 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 




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 







only 



... and also 






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.