...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 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 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.