Home | Libraries | People | FAQ | More |
Itl Collectors
, behave like
Sets
. This can be understood
easily, if we consider, that every map of sets can be transformed to an equivalent
set of pairs. For instance in the pseudocode below map m
itl::map<int,set<int> > m = {(1->{1,2}), (2->{1})};
is equivalent to set s
itl::set<pair<int,int> > s = {(1,1),(1,2), //representing 1->{1,2} (2,1) }; //representing 2->{1}
Also the results of add, subtract and other operations on map
m
and set
s
preserves the equivalence of
the containers almost
perfectly:
m += (1,3); m == {(1->{1,2,3}), (2->{1})}; //aggregated on collision of key value 1 s += (1,3); s == {(1,1),(1,2),(1,3), //representing 1->{1,2,3} (2,1) }; //representing 2->{1}
The equivalence of m
and
s
is only violated if an
empty set occurres in m
by
subtraction of a value pair:
m -= (2,1); m == {(1->{1,2,3}), (2->{})}; //aggregated on collision of key value 2 s -= (2,1); s == {(1,1),(1,2),(1,3) //representing 1->{1,2,3} }; //2->{} is not represented in s
This problem can be dealt with in two ways.
neutron
.
neutron
value.
Solution (1) led to the introduction of map traits, particularly trait partial_absorber, which is the default setting in all itl's map templates.
Solution (2), is applied to check the semantics of itl::Maps for the partial_enricher
trait that does not delete value pairs that carry neutrons. Protonic equality
is implemented by a non member function called is_protonic_equal
.
Throughout this chapter protonic equality in pseudocode and law denotations
is denoted as =p=
operator.
The validity of the sets of laws that make up Set
semantics should now be quite evident. So the following text shows the laws
that are validated for all Collector
types C
. Which are itl::map
<D,S,T>
,
interval_map
<D,S,T>
and split_interval_map
<D,S,T>
where CodomainT
type S
is a model of Set
and Trait
type T
is either partial_absorber
or partial_enricher
.
Associativity<C,+,== >: C a,b,c; a+(b+c) == (a+b)+c Neutrality<C,+,== > : C a; a+C() == a Commutativity<C,+,== >: C a,b; a+b == b+a Associativity<C,&,== >: C a,b,c; a&(b&c) ==(a&b)&c Commutativity<C,&,== >: C a,b; a&b == b&a RightNeutrality<C,-,== >: C a; a-C() == a Inversion<C,-,=v= > : C a; a - a =v= C()
All the fundamental laws could be validated for all itl Maps in their instantiation
as Maps of Sets or Collectors. As expected Inversion only holds for protonic
equality, if the map is not a partial_absorber
.
+ & - Associativity == == Neutrality == == Commutativity == == Inversion partial_absorber == partial_enricher =p=
Distributivity<C,+,&,=v= > : C a,b,c; a + (b & c) =v= (a + b) & (a + c) Distributivity<C,&,+,=v= > : C a,b,c; a & (b + c) =v= (a & b) + (a & c) RightDistributivity<C,+,-,=v= > : C a,b,c; (a + b) - c =v= (a - c) + (b - c) RightDistributivity<C,&,-,=v= > : C a,b,c; (a & b) - c =v= (a - c) & (b - c)
Results for the distributivity laws are almost identical to the validation
of sets except that for a partial_enricher
map
the law (a & b) -
c ==
(a - c)
& (b - c)
holds for lexicographical equality.
+,& &,+ Distributivity joining == == splitting partial_absorber =e= =e= partial_enricher =e= == +,- &,- RightDistributivity joining == == splitting =e= ==
DeMorgan<C,+,&,=v= > : C a,b,c; a - (b + c) =v= (a - b) & (a - c) DeMorgan<C,&,+,=v= > : C a,b,c; a - (b & c) =v= (a - b) + (a - c)
+,& &,+ DeMorgan joining == == splitting == =e=
SymmetricDifference<C,== > : C a,b,c; (a + b) - (a * b) == (a - b) + (b - a)
Reviewing the validity tables above shows, that the sets of valid laws for
itl Sets
and itl Maps
of Sets
that are neutron absorbing are exactly the same. As
expected, only for Maps of Sets that represent empty sets as associated values,
called neutron enrichers, there are marginal semantical
differences.