Home | Libraries | People | FAQ | More |
Itl maps differ in their behavior dependent on how they handle neutral elements of the associated type
CodomainT
. This section became
kind of nuclear at least in wording. But rest assured
itl::Maps
won't contaminate your software.
In the itl we call neutral elements
neutrons
and all values that
are not neutrons
we call protons
.
In the pseudo code snippets below 0
will be used to denote neutrons
,
which can be different objects like const
double 0.0
,
empty sets, empty strings, null-vectors etc. dependent of the instance type
for parameter CodomainT
.
The existence of a neutral element
wrt. an operator+=
is a requirement for template type CodomainT
.
Note, that a neutron is defined in relation to a combiner operation.
type |
operation |
neutron |
---|---|---|
|
addition |
|
|
concatenation |
|
|
union |
|
In these cases the neutron
value is delivered by the default constructor of the maps CodomainT
type. But there are well known exceptions like e.g. numeric multiplication:
type |
operation |
neutron |
---|---|---|
|
multiplication |
|
Therefore itl functors, that serve as Combiner
parameters of itl Maps implement a static function neutron()
to make sure that the correct neutron()
is used in the implementation of aggregate on overlap.
inplace_times<int>::neutron() == 1 // or more general inplace_times<T>::neutron() == unon<T>::value()
There are two properties or traits
of itl maps that can be chosen by a template parameter Traits
.
The first trait relates
to the definedness
of the map. Itl maps can be partial or
total on the set of values given by domain
type DomainT
.
The second trait is
related to the representation of neutrons
in the map. An itl map can be a neutron absorber
or a neutron enricher.
(k,0)
that carry neutrons.
(k,0)
.
For the template parameter Traits
of itl Maps we have the following four values.
|
neutron absorber |
neutron enricher |
---|---|---|
partial |
partial_absorber (default) |
partial_enricher |
total |
total_absorber |
total_enricher |
Map traits are a late extension to the itl. Interval maps have been used for a couple of years in a variety of applications at Cortex Software GmbH with an implementation that resembled the default trait. Only the deeper analysis of the itl's aggregating Map's concept in the course of preparation of the library for boost led to the introduction of map Traits.
Constitutional for the absorber/enricher propery is a little antinomy.
We can insert value pairs to the map by adding
them to the map via operations add, +=
or +
:
{} + {(k,1)} == {(k,1)} // addition
Further addition on common keys triggers aggregation:
{(k,1)} + {(k,1)} == {(k,2)} // aggregation for common key k
A subtraction of existing pairs
{(k,2)} - {(k,2)} == {(k,0)} // aggregation for common key k
yields value pairs that are associated with 0-values or neutrons
.
So once a value pair is created for a key k
it can not be removed from the map via subtraction (subtract, -=
or -
).
The very basic fact on sets, that we can remove what we have previously added
x - x = {}
does not apply.
This is the motivation for the neutron absorber Trait. A neutron absorber map handles value pairs that carry neutrons as non-existent, which saves the law:
x - x = {}
Yet this introduces a new problem: With such a neutron absorber
we are by definition unable to store a value (k,0)
in the map.
This may be unfavorable because it is not inline with the behavior of stl::maps
and this is not necessarily expected by clients of the library.
The solution to the problem is the introduction of the neutron enricher Trait, so the user can choose a map variant according to her needs.
The idea of a neutron absorbing map is, that an associated
neutron value of a pair (k,0)
codes non-existence
for it's key k
. So the pair
(k,0)
immediately tunnels from a map where it may emerge into the realm of non
existence.
{(k,0)} == {}
If neutrons do not code non-existence
but existence with null quantification,
we can also think of a map that has an associated neutron value for every key k
that has no associated value different from 0. So in contrast to modelling
all neutronic value pairs (k,0)
as being
non-existent we can
model all neutronic value pairs (k,0)
as being
implicitly existent.
A map that is modelled in this way, is one large vector with a value v
for every key k
of it's domain type DomainT
.
But only protonic value are actually stored. This is the motivation for the
definedness-Trait on itl Maps
.
A partial map models the intuitive view that only value pairs are existent, that are stored in the map. A total map exploits the possibility that all value pairs that are not stored can be considered as being existent and quantified with the neutron value.
From a pragmatic perspective value pairs that carry neutrons
as mapped values can often be ignored. If we count, for instance, the number
of overlaps of inserted intervals in an interval_map
(see example overlap counter),
most of the time, we are not interested in whether an overlap has been counted
0
times or has not been counted
at all. A neutron enricher map is only needed, if we want to distinct between
non-existence and 0-quantification.
The following distinction can not be made
for a partial_absorber
map but it can be made for an partial_enricher
map:
(k,v) does not exist in the map: Pair (k,v) has NOT been dealt with (k,0) key k carries 0 : Pair (k,v) has been dealt with resulting in v=0
Sometimes this subtle distinction is needed. Then a partial_enricher
is the right choice. Also, If we want to give two itl::Maps
a common set of keys in order to, say, iterate synchronously over both maps,
we need enrichers.