1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Quantifiers: Maps of Numbers</title> 5<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../index.html" title="Chapter 1. Boost.Icl"> 8<link rel="up" href="../semantics.html" title="Semantics"> 9<link rel="prev" href="collectors__maps_of_sets.html" title="Collectors: Maps of Sets"> 10<link rel="next" href="concept_induction.html" title="Concept Induction"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="collectors__maps_of_sets.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../semantics.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="concept_induction.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h3 class="title"> 27<a name="boost_icl.semantics.quantifiers__maps_of_numbers"></a><a class="link" href="quantifiers__maps_of_numbers.html" title="Quantifiers: Maps of Numbers">Quantifiers: 28 Maps of Numbers</a> 29</h3></div></div></div> 30<h6> 31<a name="boost_icl.semantics.quantifiers__maps_of_numbers.h0"></a> 32 <span class="phrase"><a name="boost_icl.semantics.quantifiers__maps_of_numbers.subtraction_on_quantifiers"></a></span><a class="link" href="quantifiers__maps_of_numbers.html#boost_icl.semantics.quantifiers__maps_of_numbers.subtraction_on_quantifiers">Subtraction 33 on Quantifiers</a> 34 </h6> 35<p> 36 With <code class="computeroutput"><span class="identifier">Sets</span></code> and <code class="computeroutput"><span class="identifier">Collectors</span></code> the semantics of <code class="computeroutput"><span class="keyword">operator</span> <span class="special">-</span></code> 37 is that of <span class="emphasis"><em>set difference</em></span> which means, that you can 38 only subtract what has been put into the container before. With <code class="computeroutput"><span class="identifier">Quantifiers</span></code> that <span class="emphasis"><em><span class="bold"><strong>count</strong></span></em></span> 39 or <span class="emphasis"><em><span class="bold"><strong>quantify</strong></span></em></span> their key 40 values in some way, the semantics of <code class="computeroutput"><span class="keyword">operator</span> 41 <span class="special">-</span></code> may be different. 42 </p> 43<p> 44 The question is how subtraction should be defined here? 45</p> 46<pre class="programlisting"><span class="comment">//Pseudocode:</span> 47<span class="identifier">icl</span><span class="special">::</span><span class="identifier">map</span><span class="special"><</span><span class="keyword">int</span><span class="special">,</span><span class="identifier">some_number</span><span class="special">></span> <span class="identifier">q</span> <span class="special">=</span> <span class="special">{(</span><span class="number">1</span><span class="special">-></span><span class="number">1</span><span class="special">)};</span> 48<span class="identifier">q</span> <span class="special">-=</span> <span class="special">(</span><span class="number">2</span><span class="special">-></span><span class="number">1</span><span class="special">);</span> 49</pre> 50<p> 51 If type <code class="computeroutput"><span class="identifier">some_number</span></code> is <code class="computeroutput"><span class="keyword">unsigned</span></code> a <span class="emphasis"><em>set difference</em></span> 52 kind of subtraction make sense 53</p> 54<pre class="programlisting"><span class="identifier">icl</span><span class="special">::</span><span class="identifier">map</span><span class="special"><</span><span class="keyword">int</span><span class="special">,</span><span class="identifier">some_number</span><span class="special">></span> <span class="identifier">q</span> <span class="special">=</span> <span class="special">{(</span><span class="number">1</span><span class="special">-></span><span class="number">1</span><span class="special">)};</span> 55<span class="identifier">q</span> <span class="special">-=</span> <span class="special">(</span><span class="number">2</span><span class="special">-></span><span class="number">1</span><span class="special">);</span> <span class="comment">// key 2 is not in the map so </span> 56<span class="identifier">q</span> <span class="special">==</span> <span class="special">{(</span><span class="number">1</span><span class="special">-></span><span class="number">1</span><span class="special">)};</span> <span class="comment">// q is unchanged by 'aggregate on collision'</span> 57</pre> 58<p> 59 If <code class="computeroutput"><span class="identifier">some_number</span></code> is a <code class="computeroutput"><span class="keyword">signed</span></code> numerical type the result can also 60 be this 61</p> 62<pre class="programlisting"><span class="identifier">icl</span><span class="special">::</span><span class="identifier">map</span><span class="special"><</span><span class="keyword">int</span><span class="special">,</span><span class="identifier">some_number</span><span class="special">></span> <span class="identifier">q</span> <span class="special">=</span> <span class="special">{(</span><span class="number">1</span><span class="special">-></span><span class="number">1</span><span class="special">)};</span> 63<span class="identifier">q</span> <span class="special">-=</span> <span class="special">(</span><span class="number">2</span><span class="special">-></span><span class="number">1</span><span class="special">);</span> <span class="comment">// subtracting works like </span> 64<span class="identifier">q</span> <span class="special">==</span> <span class="special">{(</span><span class="number">1</span><span class="special">-></span><span class="number">1</span><span class="special">),</span> <span class="special">(</span><span class="number">2</span><span class="special">-></span> <span class="special">-</span><span class="number">1</span><span class="special">)};</span> <span class="comment">// adding the inverse element</span> 65</pre> 66<p> 67 As commented in the example, subtraction of a key value pair <code class="computeroutput"><span class="special">(</span><span class="identifier">k</span><span class="special">,</span><span class="identifier">v</span><span class="special">)</span></code> can 68 obviously be defined as adding the <span class="emphasis"><em><span class="bold"><strong>inverse 69 element</strong></span></em></span> for that key <code class="computeroutput"><span class="special">(</span><span class="identifier">k</span><span class="special">,-</span><span class="identifier">v</span><span class="special">)</span></code>, if the key is not yet stored in the map. 70 </p> 71<h5> 72<a name="boost_icl.semantics.quantifiers__maps_of_numbers.h1"></a> 73 <span class="phrase"><a name="boost_icl.semantics.quantifiers__maps_of_numbers.partial_and_total_quantifiers_and_infinite_vectors"></a></span><a class="link" href="quantifiers__maps_of_numbers.html#boost_icl.semantics.quantifiers__maps_of_numbers.partial_and_total_quantifiers_and_infinite_vectors">Partial 74 and Total Quantifiers and Infinite Vectors</a> 75 </h5> 76<p> 77 Another concept, that we can think of, is that in a <code class="computeroutput"><span class="identifier">Quantifier</span></code> 78 every <code class="computeroutput"><span class="identifier">key_value</span></code> is initially 79 quantified <code class="computeroutput"><span class="number">0</span></code>-times, where <code class="computeroutput"><span class="number">0</span></code> stands for the neutral element of the numeric 80 <code class="computeroutput"><span class="identifier">CodomainT</span></code> type. Such a <code class="computeroutput"><span class="identifier">Quantifier</span></code> would be totally defined on 81 all values of it's <code class="computeroutput"><span class="identifier">DomainT</span></code> 82 type and can be conceived as an <code class="computeroutput"><span class="identifier">InfiniteVector</span></code>. 83 </p> 84<p> 85 To create an infinite vector that is totally defined on it's domain we can 86 set the map's <code class="computeroutput"><span class="identifier">Trait</span></code> parameter 87 to the value <code class="computeroutput"><a class="link" href="../../boost/icl/total_absorber.html" title="Struct total_absorber">total_absorber</a></code>. 88 The <code class="computeroutput"><a class="link" href="../../boost/icl/total_absorber.html" title="Struct total_absorber">total_absorber</a></code> 89 trait fits specifically well with a <code class="computeroutput"><span class="identifier">Quantifier</span></code> 90 if it's <code class="computeroutput"><span class="identifier">CodomainT</span></code> has an 91 inverse element, like all signed numerical type have. As we can see later 92 in this section this kind of a total <code class="computeroutput"><span class="identifier">Quantifier</span></code> 93 has the basic properties that elements of a <a href="http://en.wikipedia.org/wiki/Vector_space" target="_top">vector 94 space</a> do provide. 95 </p> 96<h6> 97<a name="boost_icl.semantics.quantifiers__maps_of_numbers.h2"></a> 98 <span class="phrase"><a name="boost_icl.semantics.quantifiers__maps_of_numbers.intersection_on_quantifiers"></a></span><a class="link" href="quantifiers__maps_of_numbers.html#boost_icl.semantics.quantifiers__maps_of_numbers.intersection_on_quantifiers">Intersection 99 on Quantifiers</a> 100 </h6> 101<p> 102 Another difference between <code class="computeroutput"><span class="identifier">Collectors</span></code> 103 and <code class="computeroutput"><span class="identifier">Quantifiers</span></code> is the semantics 104 of <code class="computeroutput"><span class="keyword">operator</span> <span class="special">&</span></code>, 105 that has the meaning of set intersection for <code class="computeroutput"><span class="identifier">Collectors</span></code>. 106 </p> 107<p> 108 For the <span class="emphasis"><em>aggregate on overlap principle</em></span> the operation 109 <code class="computeroutput"><span class="special">&</span></code> has to be passed to combine 110 associated values on overlap of intervals or collision of keys. This can 111 not be done for <code class="computeroutput"><span class="identifier">Quantifiers</span></code>, 112 since numeric types do not implement intersection. 113 </p> 114<p> 115 For <code class="computeroutput"><span class="identifier">CodomainT</span></code> types that 116 are not models of <code class="computeroutput"><span class="identifier">Sets</span></code> <code class="computeroutput"><span class="keyword">operator</span> <span class="special">&</span> </code> 117 is defined as <span class="emphasis"><em>aggregation on the intersection of the domains</em></span>. 118 Instead of the <code class="computeroutput"><span class="identifier">codomain_intersect</span></code> 119 functor <code class="computeroutput"><span class="identifier">codomain_combine</span></code> 120 is used as aggregation operation: 121</p> 122<pre class="programlisting"><span class="comment">//Pseudocode example for partial Quantifiers p, q:</span> 123<span class="identifier">interval_map</span><span class="special"><</span><span class="keyword">int</span><span class="special">,</span><span class="keyword">int</span><span class="special">></span> <span class="identifier">p</span><span class="special">,</span> <span class="identifier">q</span><span class="special">;</span> 124<span class="identifier">p</span> <span class="special">=</span> <span class="special">{[</span><span class="number">1</span> <span class="number">3</span><span class="special">)-></span><span class="number">1</span> <span class="special">};</span> 125<span class="identifier">q</span> <span class="special">=</span> <span class="special">{</span> <span class="special">([</span><span class="number">2</span> <span class="number">4</span><span class="special">)-></span><span class="number">1</span><span class="special">};</span> 126<span class="identifier">p</span> <span class="special">&</span> <span class="identifier">q</span> <span class="special">=={</span> <span class="special">[</span><span class="number">2</span> <span class="number">3</span><span class="special">)-></span><span class="number">2</span> <span class="special">};</span> 127</pre> 128<p> 129 So an addition or aggregation of associated values is done like for <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+</span></code> 130 but value pairs that have no common keys are not added to the result. 131 </p> 132<p> 133 For a <code class="computeroutput"><span class="identifier">Quantifier</span></code> that is 134 a model of an <code class="computeroutput"><span class="identifier">InfiniteVector</span></code> 135 and which is therefore defined for every key value of the <code class="computeroutput"><span class="identifier">DomainT</span></code> 136 type, this definition of <code class="computeroutput"><span class="keyword">operator</span> 137 <span class="special">&</span></code> degenerates to the same sematics 138 that <code class="computeroutput"><span class="identifier">operaotor</span> <span class="special">+</span></code> 139 implements: 140</p> 141<pre class="programlisting"><span class="comment">//Pseudocode example for total Quantifiers p, q:</span> 142<span class="identifier">interval_map</span><span class="special"><</span><span class="keyword">int</span><span class="special">,</span><span class="keyword">int</span><span class="special">></span> <span class="identifier">p</span><span class="special">,</span> <span class="identifier">q</span><span class="special">;</span> 143<span class="identifier">p</span> <span class="special">=</span> <span class="special">{[</span><span class="identifier">min</span> <span class="number">1</span><span class="special">)[</span><span class="number">1</span> <span class="number">3</span><span class="special">)[</span><span class="number">3</span> <span class="identifier">max</span><span class="special">]};</span> 144 <span class="special">-></span><span class="number">0</span> <span class="special">-></span><span class="number">1</span> <span class="special">-></span><span class="number">0</span> 145<span class="identifier">q</span> <span class="special">=</span> <span class="special">{[</span><span class="identifier">min</span> <span class="number">2</span><span class="special">)[</span><span class="number">2</span> <span class="number">4</span><span class="special">)[</span><span class="number">4</span> <span class="identifier">max</span><span class="special">]};</span> 146 <span class="special">-></span><span class="number">0</span> <span class="special">-></span><span class="number">1</span> <span class="special">-></span><span class="number">0</span> 147<span class="identifier">p</span><span class="special">&</span><span class="identifier">q</span> <span class="special">=={[</span><span class="identifier">min</span> <span class="number">1</span><span class="special">)[</span><span class="number">1</span> <span class="number">2</span><span class="special">)[</span><span class="number">2</span> <span class="number">3</span><span class="special">)[</span><span class="number">3</span> <span class="number">4</span><span class="special">)[</span><span class="number">4</span> <span class="identifier">max</span><span class="special">]};</span> 148 <span class="special">-></span><span class="number">0</span> <span class="special">-></span><span class="number">1</span> <span class="special">-></span><span class="number">2</span> <span class="special">-></span><span class="number">1</span> <span class="special">-></span><span class="number">0</span> 149</pre> 150<p> 151 </p> 152<h5> 153<a name="boost_icl.semantics.quantifiers__maps_of_numbers.h3"></a> 154 <span class="phrase"><a name="boost_icl.semantics.quantifiers__maps_of_numbers.laws_for_quantifiers_of_unsigned_numbers"></a></span><a class="link" href="quantifiers__maps_of_numbers.html#boost_icl.semantics.quantifiers__maps_of_numbers.laws_for_quantifiers_of_unsigned_numbers">Laws 155 for Quantifiers of unsigned Numbers</a> 156 </h5> 157<p> 158 The semantics of icl Maps of Numbers is different for unsigned or signed 159 numbers. So the sets of laws that are valid for Quantifiers will be different 160 depending on the instantiation of an unsigned or a signed number type as 161 <code class="computeroutput"><span class="identifier">CodomainT</span></code> parameter. 162 </p> 163<p> 164 Again, we are presenting the investigated sets of laws, this time for <code class="computeroutput"><span class="identifier">Quantifier</span></code> types <code class="computeroutput"><span class="identifier">Q</span></code> 165 which are <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code><code class="computeroutput"><span class="special"><</span><span class="identifier">D</span><span class="special">,</span><span class="identifier">N</span><span class="special">,</span><span class="identifier">T</span><span class="special">></span></code>, <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code><code class="computeroutput"><span class="special"><</span><span class="identifier">D</span><span class="special">,</span><span class="identifier">N</span><span class="special">,</span><span class="identifier">T</span><span class="special">></span></code> and <code class="computeroutput"><a class="link" href="../../boost/icl/split_interval_map.html" title="Class template split_interval_map">split_interval_map</a></code><code class="computeroutput"><span class="special"><</span><span class="identifier">D</span><span class="special">,</span><span class="identifier">N</span><span class="special">,</span><span class="identifier">T</span><span class="special">></span></code> where <code class="computeroutput"><span class="identifier">CodomainT</span></code> 166 type <code class="computeroutput"><span class="identifier">N</span></code> is a <code class="computeroutput"><span class="identifier">Number</span></code> and <code class="computeroutput"><span class="identifier">Trait</span></code> 167 type <code class="computeroutput"><span class="identifier">T</span></code> is one of the icl's 168 map traits. 169 </p> 170<p> 171</p> 172<pre class="programlisting"><span class="identifier">Associativity</span><span class="special"><</span><span class="identifier">Q</span><span class="special">,+,==</span> <span class="special">>:</span> <span class="identifier">Q</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="identifier">a</span><span class="special">+(</span><span class="identifier">b</span><span class="special">+</span><span class="identifier">c</span><span class="special">)</span> <span class="special">==</span> <span class="special">(</span><span class="identifier">a</span><span class="special">+</span><span class="identifier">b</span><span class="special">)+</span><span class="identifier">c</span> 173<span class="identifier">Neutrality</span><span class="special"><</span><span class="identifier">Q</span><span class="special">,+,==</span> <span class="special">></span> <span class="special">:</span> <span class="identifier">Q</span> <span class="identifier">a</span><span class="special">;</span> <span class="identifier">a</span><span class="special">+</span><span class="identifier">Q</span><span class="special">()</span> <span class="special">==</span> <span class="identifier">a</span> 174<span class="identifier">Commutativity</span><span class="special"><</span><span class="identifier">Q</span><span class="special">,+,==</span> <span class="special">>:</span> <span class="identifier">Q</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">;</span> <span class="identifier">a</span><span class="special">+</span><span class="identifier">b</span> <span class="special">==</span> <span class="identifier">b</span><span class="special">+</span><span class="identifier">a</span> 175 176<span class="identifier">Associativity</span><span class="special"><</span><span class="identifier">Q</span><span class="special">,&,==</span> <span class="special">>:</span> <span class="identifier">Q</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="identifier">a</span><span class="special">&(</span><span class="identifier">b</span><span class="special">&</span><span class="identifier">c</span><span class="special">)</span> <span class="special">==(</span><span class="identifier">a</span><span class="special">&</span><span class="identifier">b</span><span class="special">)&</span><span class="identifier">c</span> 177<span class="identifier">Commutativity</span><span class="special"><</span><span class="identifier">Q</span><span class="special">,&,==</span> <span class="special">>:</span> <span class="identifier">Q</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">;</span> <span class="identifier">a</span><span class="special">&</span><span class="identifier">b</span> <span class="special">==</span> <span class="identifier">b</span><span class="special">&</span><span class="identifier">a</span> 178 179<span class="identifier">RightNeutrality</span><span class="special"><</span><span class="identifier">Q</span><span class="special">,-,==</span> <span class="special">>:</span> <span class="identifier">Q</span> <span class="identifier">a</span><span class="special">;</span> <span class="identifier">a</span><span class="special">-</span><span class="identifier">Q</span><span class="special">()</span> <span class="special">==</span> <span class="identifier">a</span> 180<span class="identifier">Inversion</span><span class="special"><</span><span class="identifier">Q</span><span class="special">,-,=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">></span> <span class="special">:</span> <span class="identifier">Q</span> <span class="identifier">a</span><span class="special">;</span> <span class="identifier">a</span> <span class="special">-</span> <span class="identifier">a</span> <span class="special">=</span><span class="identifier">v</span><span class="special">=</span> <span class="identifier">Q</span><span class="special">()</span> 181</pre> 182<p> 183 </p> 184<p> 185 For an <code class="computeroutput"><span class="keyword">unsigned</span> <span class="identifier">Quantifier</span></code>, 186 an icl Map of <code class="computeroutput"><span class="keyword">unsigned</span> <span class="identifier">numbers</span></code>, 187 the same basic laws apply that are valid for <code class="computeroutput"><span class="identifier">Collectors</span></code>: 188 </p> 189<p> 190</p> 191<pre class="programlisting"> <span class="special">+</span> <span class="special">&</span> <span class="special">-</span> 192<span class="identifier">Associativity</span> <span class="special">==</span> <span class="special">==</span> 193<span class="identifier">Neutrality</span> <span class="special">==</span> <span class="special">==</span> 194<span class="identifier">Commutativity</span> <span class="special">==</span> <span class="special">==</span> 195<span class="identifier">Inversion</span> <span class="identifier">absorbs_identities</span> <span class="special">==</span> 196 <span class="identifier">enriches_identities</span> <span class="special">=</span><span class="identifier">d</span><span class="special">=</span> 197</pre> 198<p> 199 </p> 200<p> 201 The subset of laws, that relates to <code class="computeroutput"><span class="keyword">operator</span> 202 <span class="special">+</span></code> and the neutral element <code class="computeroutput"><span class="identifier">Q</span><span class="special">()</span></code> is 203 that of a commutative monoid. This is the same concept, that applies for 204 the <code class="computeroutput"><span class="identifier">CodomainT</span></code> type. This 205 gives rise to the assumption that an icl <code class="computeroutput"><span class="identifier">Map</span></code> 206 over a <code class="computeroutput"><span class="identifier">CommutativeModoid</span></code> 207 is again a <code class="computeroutput"><span class="identifier">CommutativeModoid</span></code>. 208 </p> 209<p> 210 Other laws that were valid for <code class="computeroutput"><span class="identifier">Collectors</span></code> 211 are not valid for an <code class="computeroutput"><span class="keyword">unsigned</span> <span class="identifier">Quantifier</span></code>. 212 </p> 213<h5> 214<a name="boost_icl.semantics.quantifiers__maps_of_numbers.h4"></a> 215 <span class="phrase"><a name="boost_icl.semantics.quantifiers__maps_of_numbers.laws_for_quantifiers_of_signed_numbers"></a></span><a class="link" href="quantifiers__maps_of_numbers.html#boost_icl.semantics.quantifiers__maps_of_numbers.laws_for_quantifiers_of_signed_numbers">Laws 216 for Quantifiers of signed Numbers</a> 217 </h5> 218<p> 219 For <code class="computeroutput"><span class="identifier">Quantifiers</span></code> of signed 220 numbers, or <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">Quantifiers</span></code>, 221 the pattern of valid laws is somewhat different: 222</p> 223<pre class="programlisting"> <span class="special">+</span> <span class="special">&</span> <span class="special">-</span> 224<span class="identifier">Associativity</span> <span class="special">=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">=</span><span class="identifier">v</span><span class="special">=</span> 225<span class="identifier">Neutrality</span> <span class="special">==</span> <span class="special">==</span> 226<span class="identifier">Commutativity</span> <span class="special">==</span> <span class="special">==</span> 227<span class="identifier">Inversion</span> <span class="identifier">absorbs_identities</span> <span class="special">==</span> 228 <span class="identifier">enriches_identities</span> <span class="special">=</span><span class="identifier">d</span><span class="special">=</span> 229</pre> 230<p> 231 </p> 232<p> 233 The differences are tagged as <code class="computeroutput"><span class="special">=</span><span class="identifier">v</span><span class="special">=</span></code> indicating, 234 that the associativity law is not uniquely valid for a single equality relation 235 <code class="computeroutput"><span class="special">==</span></code> as this was the case for 236 <code class="computeroutput"><span class="identifier">Collector</span></code> and <code class="computeroutput"><span class="keyword">unsigned</span> <span class="identifier">Quntifier</span></code> 237 maps. 238 </p> 239<p> 240 The differences are these: 241</p> 242<pre class="programlisting"> <span class="special">+</span> 243<span class="identifier">Associativity</span> <span class="identifier">icl</span><span class="special">::</span><span class="identifier">map</span> <span class="special">==</span> 244 <span class="identifier">interval_map</span> <span class="special">==</span> 245 <span class="identifier">split_interval_map</span> <span class="special">=</span><span class="identifier">e</span><span class="special">=</span> 246</pre> 247<p> 248 For <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+</span></code> 249 the associativity on <code class="computeroutput"><a class="link" href="../../boost/icl/split_interval_map.html" title="Class template split_interval_map">split_interval_maps</a></code> 250 is only valid with element equality <code class="computeroutput"><span class="special">=</span><span class="identifier">e</span><span class="special">=</span></code>, which 251 is not a big constrained, because only element equality is required. 252 </p> 253<p> 254 For <code class="computeroutput"><span class="keyword">operator</span> <span class="special">&</span></code> 255 the associativity is broken for all maps that are partial absorbers. For 256 total absorbers associativity is valid for element equality. All maps having 257 the <span class="emphasis"><em>identity enricher</em></span> Trait are associative wrt. lexicographical 258 equality <code class="computeroutput"><span class="special">==</span></code>. 259</p> 260<pre class="programlisting"><span class="identifier">Associativity</span> <span class="special">&</span> 261 <span class="identifier">absorbs_identities</span> <span class="special">&&</span> <span class="special">!</span><span class="identifier">is_total</span> <span class="keyword">false</span> 262 <span class="identifier">absorbs_identities</span> <span class="special">&&</span> <span class="identifier">is_total</span> <span class="special">=</span><span class="identifier">e</span><span class="special">=</span> 263 <span class="identifier">enriches_identities</span> <span class="special">==</span> 264</pre> 265<p> 266 </p> 267<p> 268 Note, that all laws that establish a commutative monoid for <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+</span></code> 269 and identity element <code class="computeroutput"><span class="identifier">Q</span><span class="special">()</span></code> 270 are valid for <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">Quantifiers</span></code>. 271 In addition symmetric difference that does not hold for <code class="computeroutput"><span class="keyword">unsigned</span> 272 <span class="identifier">Qunatifiers</span></code> is valid for <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">Qunatifiers</span></code>. 273 </p> 274<p> 275</p> 276<pre class="programlisting"><span class="identifier">SymmetricDifference</span><span class="special"><</span><span class="identifier">Q</span><span class="special">,==</span> <span class="special">></span> <span class="special">:</span> <span class="identifier">Q</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">+</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">-</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">&</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">==</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">-</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">+</span> <span class="special">(</span><span class="identifier">b</span> <span class="special">-</span> <span class="identifier">a</span><span class="special">)</span> 277</pre> 278<p> 279 For a <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">TotalQuantifier</span></code> 280 <code class="computeroutput"><span class="identifier">Qt</span></code> symmetrical difference 281 degenerates to a trivial form since <code class="computeroutput"><span class="keyword">operator</span> 282 <span class="special">&</span></code> and <code class="computeroutput"><span class="keyword">operator</span> 283 <span class="special">+</span></code> become identical 284</p> 285<pre class="programlisting"><span class="identifier">SymmetricDifference</span><span class="special"><</span><span class="identifier">Qt</span><span class="special">,==</span> <span class="special">></span> <span class="special">:</span> <span class="identifier">Qt</span> <span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">,</span><span class="identifier">c</span><span class="special">;</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">+</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">-</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">+</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">==</span> <span class="special">(</span><span class="identifier">a</span> <span class="special">-</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">+</span> <span class="special">(</span><span class="identifier">b</span> <span class="special">-</span> <span class="identifier">a</span><span class="special">)</span> <span class="special">==</span> <span class="identifier">Qt</span><span class="special">()</span> 286</pre> 287<p> 288 </p> 289<h6> 290<a name="boost_icl.semantics.quantifiers__maps_of_numbers.h5"></a> 291 <span class="phrase"><a name="boost_icl.semantics.quantifiers__maps_of_numbers.existence_of_an_inverse"></a></span><a class="link" href="quantifiers__maps_of_numbers.html#boost_icl.semantics.quantifiers__maps_of_numbers.existence_of_an_inverse">Existence 292 of an Inverse</a> 293 </h6> 294<p> 295 By now <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">Quantifiers</span></code> 296 <code class="computeroutput"><span class="identifier">Q</span></code> are commutative monoids 297 with respect to the <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+</span></code> and the neutral element <code class="computeroutput"><span class="identifier">Q</span><span class="special">()</span></code>. If the Quantifier's <code class="computeroutput"><span class="identifier">CodomainT</span></code> 298 type has an <span class="emphasis"><em>inverse element</em></span> like e.g. <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">numbers</span></code> 299 do, the <code class="computeroutput"><span class="identifier">CodomainT</span></code> type is 300 a <span class="emphasis"><em><span class="bold"><strong>commutative</strong></span></em></span> or <span class="emphasis"><em><span class="bold"><strong>abelian group</strong></span></em></span>. In this case a <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">Quantifier</span></code> 301 that is also <span class="emphasis"><em><span class="bold"><strong>total</strong></span></em></span> 302 has an <span class="emphasis"><em><span class="bold"><strong>inverse</strong></span></em></span> and 303 the following law holds: 304 </p> 305<p> 306</p> 307<pre class="programlisting"><span class="identifier">InverseElement</span><span class="special"><</span><span class="identifier">Qt</span><span class="special">,==</span> <span class="special">></span> <span class="special">:</span> <span class="identifier">Qt</span> <span class="identifier">a</span><span class="special">;</span> <span class="special">(</span><span class="number">0</span> <span class="special">-</span> <span class="identifier">a</span><span class="special">)</span> <span class="special">+</span> <span class="identifier">a</span> <span class="special">==</span> <span class="number">0</span> 308</pre> 309<p> 310 </p> 311<p> 312 Which means that each <code class="computeroutput"><span class="identifier">TotalQuantifier</span></code> 313 over an abelian group is an abelian group itself. 314 </p> 315<p> 316 This also implies that a <code class="computeroutput"><span class="identifier">Quantifier</span></code> 317 of <code class="computeroutput"><span class="identifier">Quantifiers</span></code> is again a 318 <code class="computeroutput"><span class="identifier">Quantifiers</span></code> and a <code class="computeroutput"><span class="identifier">TotalQuantifier</span></code> of <code class="computeroutput"><span class="identifier">TotalQuantifiers</span></code> 319 is also a <code class="computeroutput"><span class="identifier">TotalQuantifier</span></code>. 320 </p> 321<p> 322 <code class="computeroutput"><span class="identifier">TotalQuantifiers</span></code> resemble 323 the notion of a vector space partially. The concept could be completed to 324 a vector space, if a scalar multiplication was added. 325 </p> 326</div> 327<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 328<td align="left"></td> 329<td align="right"><div class="copyright-footer">Copyright © 2007-2010 Joachim 330 Faulhaber<br>Copyright © 1999-2006 Cortex Software 331 GmbH<p> 332 Distributed under the Boost Software License, Version 1.0. (See accompanying 333 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 334 </p> 335</div></td> 336</tr></table> 337<hr> 338<div class="spirit-nav"> 339<a accesskey="p" href="collectors__maps_of_sets.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../semantics.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="concept_induction.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 340</div> 341</body> 342</html> 343
