libs/icl/doc/html/boost_icl/semantics/quantifiers__maps_of_numbers.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   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.74.0">
   7 <link rel="home" href="../../index.html" title="Chapter&#160;1.&#160;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 boost_icl_semantics_quantifiers__maps_of_numbers" lang="en">
  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 <a name="boost_icl.semantics.quantifiers__maps_of_numbers.subtraction_on_quantifiers"></a><h6>
  31 <a name="id1128756"></a>
  32         <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:
  47 </span><span class="identifier">icl</span><span class="special">::</span><span class="identifier">map</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">,</span><span class="identifier">some_number</span><span class="special">&gt;</span> <span class="identifier">q</span> <span class="special">=</span> <span class="special">{(</span><span class="number">1</span><span class="special">-&gt;</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">-&gt;</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">&lt;</span><span class="keyword">int</span><span class="special">,</span><span class="identifier">some_number</span><span class="special">&gt;</span> <span class="identifier">q</span> <span class="special">=</span> <span class="special">{(</span><span class="number">1</span><span class="special">-&gt;</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">-&gt;</span><span class="number">1</span><span class="special">);</span>   <span class="comment">// key 2 is not in the map so
  56 </span><span class="identifier">q</span> <span class="special">==</span> <span class="special">{(</span><span class="number">1</span><span class="special">-&gt;</span><span class="number">1</span><span class="special">)};</span> <span class="comment">// q is unchanged by 'aggregate on collision'
  57 </span></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">&lt;</span><span class="keyword">int</span><span class="special">,</span><span class="identifier">some_number</span><span class="special">&gt;</span> <span class="identifier">q</span> <span class="special">=</span> <span class="special">{(</span><span class="number">1</span><span class="special">-&gt;</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">-&gt;</span><span class="number">1</span><span class="special">);</span>             <span class="comment">// subtracting works like
  64 </span><span class="identifier">q</span> <span class="special">==</span> <span class="special">{(</span><span class="number">1</span><span class="special">-&gt;</span><span class="number">1</span><span class="special">),</span> <span class="special">(</span><span class="number">2</span><span class="special">-&gt;</span> <span class="special">-</span><span class="number">1</span><span class="special">)};</span> <span class="comment">// adding the inverse element
  65 </span></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 <a name="boost_icl.semantics.quantifiers__maps_of_numbers.partial_and_total_quantifiers_and_infinite_vectors"></a><h5>
  72 <a name="id1129293"></a>
  73         <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 <a name="boost_icl.semantics.quantifiers__maps_of_numbers.intersection_on_quantifiers"></a><h6>
  97 <a name="id1129423"></a>
  98         <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">&amp;</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">&amp;</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">&amp;</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:
 123 </span><span class="identifier">interval_map</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">,</span><span class="keyword">int</span><span class="special">&gt;</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">)-&gt;</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">)-&gt;</span><span class="number">1</span><span class="special">};</span>
 126 <span class="identifier">p</span> <span class="special">&amp;</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">)-&gt;</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">&amp;</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:
 142 </span><span class="identifier">interval_map</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">,</span><span class="keyword">int</span><span class="special">&gt;</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">-&gt;</span><span class="number">0</span>      <span class="special">-&gt;</span><span class="number">1</span>         <span class="special">-&gt;</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">-&gt;</span><span class="number">0</span>         <span class="special">-&gt;</span><span class="number">1</span>       <span class="special">-&gt;</span><span class="number">0</span>
 147 <span class="identifier">p</span><span class="special">&amp;</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">-&gt;</span><span class="number">0</span>    <span class="special">-&gt;</span><span class="number">1</span>   <span class="special">-&gt;</span><span class="number">2</span>  <span class="special">-&gt;</span><span class="number">1</span>    <span class="special">-&gt;</span><span class="number">0</span>
 149 </pre>
 150 <p>
 151       </p>
 152 <a name="boost_icl.semantics.quantifiers__maps_of_numbers.laws_for_quantifiers_of_unsigned_numbers"></a><h5>
 153 <a name="id1132271"></a>
 154         <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">&lt;</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">&gt;</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">&lt;</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">&gt;</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">&lt;</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">&gt;</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
 172 </p>
 173 <pre class="programlisting"><span class="identifier">Associativity</span><span class="special">&lt;</span><span class="identifier">Q</span><span class="special">,+,==</span> <span class="special">&gt;:</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>
 174 <span class="identifier">Neutrality</span><span class="special">&lt;</span><span class="identifier">Q</span><span class="special">,+,==</span> <span class="special">&gt;</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>
 175 <span class="identifier">Commutativity</span><span class="special">&lt;</span><span class="identifier">Q</span><span class="special">,+,==</span> <span class="special">&gt;:</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>
 176
 177 <span class="identifier">Associativity</span><span class="special">&lt;</span><span class="identifier">Q</span><span class="special">,&amp;,==</span> <span class="special">&gt;:</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">&amp;(</span><span class="identifier">b</span><span class="special">&amp;</span><span class="identifier">c</span><span class="special">)</span> <span class="special">==(</span><span class="identifier">a</span><span class="special">&amp;</span><span class="identifier">b</span><span class="special">)&amp;</span><span class="identifier">c</span>
 178 <span class="identifier">Commutativity</span><span class="special">&lt;</span><span class="identifier">Q</span><span class="special">,&amp;,==</span> <span class="special">&gt;:</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">&amp;</span><span class="identifier">b</span> <span class="special">==</span> <span class="identifier">b</span><span class="special">&amp;</span><span class="identifier">a</span>
 179
 180 <span class="identifier">RightNeutrality</span><span class="special">&lt;</span><span class="identifier">Q</span><span class="special">,-,==</span> <span class="special">&gt;:</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>
 181 <span class="identifier">Inversion</span><span class="special">&lt;</span><span class="identifier">Q</span><span class="special">,-,=</span><span class="identifier">v</span><span class="special">=</span> <span class="special">&gt;</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>
 182 </pre>
 183 <p>
 184       </p>
 185 <p>
 186         For an <code class="computeroutput"><span class="keyword">unsigned</span> <span class="identifier">Quantifier</span></code>,
 187         an icl Map of <code class="computeroutput"><span class="keyword">unsigned</span> <span class="identifier">numbers</span></code>,
 188         the same basic laws apply that are valid for <code class="computeroutput"><span class="identifier">Collectors</span></code>:
 189       </p>
 190 <p>
 191
 192 </p>
 193 <pre class="programlisting">                               <span class="special">+</span>    <span class="special">&amp;</span>    <span class="special">-</span>
 194 <span class="identifier">Associativity</span>                  <span class="special">==</span>   <span class="special">==</span>
 195 <span class="identifier">Neutrality</span>                     <span class="special">==</span>        <span class="special">==</span>
 196 <span class="identifier">Commutativity</span>                  <span class="special">==</span>   <span class="special">==</span>
 197 <span class="identifier">Inversion</span> <span class="identifier">absorbs_identities</span>             <span class="special">==</span>
 198           <span class="identifier">enriches_identities</span>            <span class="special">=</span><span class="identifier">d</span><span class="special">=</span>
 199 </pre>
 200 <p>
 201       </p>
 202 <p>
 203         The subset of laws, that relates to <code class="computeroutput"><span class="keyword">operator</span>
 204         <span class="special">+</span></code> and the neutral element <code class="computeroutput"><span class="identifier">Q</span><span class="special">()</span></code> is
 205         that of a commutative monoid. This is the same concept, that applies for
 206         the <code class="computeroutput"><span class="identifier">CodomainT</span></code> type. This
 207         gives rise to the assumption that an icl <code class="computeroutput"><span class="identifier">Map</span></code>
 208         over a <code class="computeroutput"><span class="identifier">CommutativeModoid</span></code>
 209         is again a <code class="computeroutput"><span class="identifier">CommutativeModoid</span></code>.
 210       </p>
 211 <p>
 212         Other laws that were valid for <code class="computeroutput"><span class="identifier">Collectors</span></code>
 213         are not valid for an <code class="computeroutput"><span class="keyword">unsigned</span> <span class="identifier">Quantifier</span></code>.
 214       </p>
 215 <a name="boost_icl.semantics.quantifiers__maps_of_numbers.laws_for_quantifiers_of_signed_numbers"></a><h5>
 216 <a name="id1133206"></a>
 217         <a class="link" href="quantifiers__maps_of_numbers.html#boost_icl.semantics.quantifiers__maps_of_numbers.laws_for_quantifiers_of_signed_numbers">Laws
 218         for Quantifiers of signed Numbers</a>
 219       </h5>
 220 <p>
 221         For <code class="computeroutput"><span class="identifier">Quantifiers</span></code> of signed
 222         numbers, or <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">Quantifiers</span></code>,
 223         the pattern of valid laws is somewhat different:
 224 </p>
 225 <pre class="programlisting">                               <span class="special">+</span>    <span class="special">&amp;</span>    <span class="special">-</span>
 226 <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>
 227 <span class="identifier">Neutrality</span>                     <span class="special">==</span>        <span class="special">==</span>
 228 <span class="identifier">Commutativity</span>                  <span class="special">==</span>   <span class="special">==</span>
 229 <span class="identifier">Inversion</span> <span class="identifier">absorbs_identities</span>             <span class="special">==</span>
 230           <span class="identifier">enriches_identities</span>            <span class="special">=</span><span class="identifier">d</span><span class="special">=</span>
 231 </pre>
 232 <p>
 233       </p>
 234 <p>
 235         The differences are tagged as <code class="computeroutput"><span class="special">=</span><span class="identifier">v</span><span class="special">=</span></code> indicating,
 236         that the associativity law is not uniquely valid for a single equality relation
 237         <code class="computeroutput"><span class="special">==</span></code> as this was the case for
 238         <code class="computeroutput"><span class="identifier">Collector</span></code> and <code class="computeroutput"><span class="keyword">unsigned</span> <span class="identifier">Quntifier</span></code>
 239         maps.
 240       </p>
 241 <p>
 242         The differences are these:
 243 </p>
 244 <pre class="programlisting">                                   <span class="special">+</span>
 245 <span class="identifier">Associativity</span>         <span class="identifier">icl</span><span class="special">::</span><span class="identifier">map</span>     <span class="special">==</span>
 246                   <span class="identifier">interval_map</span>     <span class="special">==</span>
 247             <span class="identifier">split_interval_map</span>     <span class="special">=</span><span class="identifier">e</span><span class="special">=</span>
 248 </pre>
 249 <p>
 250         For <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+</span></code>
 251         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>
 252         is only valid with element equality <code class="computeroutput"><span class="special">=</span><span class="identifier">e</span><span class="special">=</span></code>, which
 253         is not a big constrained, because only element equality is required.
 254       </p>
 255 <p>
 256         For <code class="computeroutput"><span class="keyword">operator</span> <span class="special">&amp;</span></code>
 257         the associativity is broken for all maps that are partial absorbers. For
 258         total absorbers associativity is valid for element equality. All maps having
 259         the <span class="emphasis"><em>identity enricher</em></span> Trait are associative wrt. lexicographical
 260         equality <code class="computeroutput"><span class="special">==</span></code>.
 261 </p>
 262 <pre class="programlisting"><span class="identifier">Associativity</span>                        <span class="special">&amp;</span>
 263    <span class="identifier">absorbs_identities</span> <span class="special">&amp;&amp;</span> <span class="special">!</span><span class="identifier">is_total</span>   <span class="keyword">false</span>
 264    <span class="identifier">absorbs_identities</span> <span class="special">&amp;&amp;</span>  <span class="identifier">is_total</span>   <span class="special">=</span><span class="identifier">e</span><span class="special">=</span>
 265    <span class="identifier">enriches_identities</span>               <span class="special">==</span>
 266 </pre>
 267 <p>
 268       </p>
 269 <p>
 270         Note, that all laws that establish a commutative monoid for <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+</span></code>
 271         and identity element <code class="computeroutput"><span class="identifier">Q</span><span class="special">()</span></code>
 272         are valid for <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">Quantifiers</span></code>.
 273         In addition symmetric difference that does not hold for <code class="computeroutput"><span class="keyword">unsigned</span>
 274         <span class="identifier">Qunatifiers</span></code> is valid for <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">Qunatifiers</span></code>.
 275       </p>
 276 <p>
 277
 278 </p>
 279 <pre class="programlisting"><span class="identifier">SymmetricDifference</span><span class="special">&lt;</span><span class="identifier">Q</span><span class="special">,==</span> <span class="special">&gt;</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">&amp;</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>
 280 </pre>
 281 <p>
 282         For a <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">TotalQuantifier</span></code>
 283         <code class="computeroutput"><span class="identifier">Qt</span></code> symmetrical difference
 284         degenerates to a trivial form since <code class="computeroutput"><span class="keyword">operator</span>
 285         <span class="special">&amp;</span></code> and <code class="computeroutput"><span class="keyword">operator</span>
 286         <span class="special">+</span></code> become identical
 287 </p>
 288 <pre class="programlisting"><span class="identifier">SymmetricDifference</span><span class="special">&lt;</span><span class="identifier">Qt</span><span class="special">,==</span> <span class="special">&gt;</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>
 289 </pre>
 290 <p>
 291       </p>
 292 <a name="boost_icl.semantics.quantifiers__maps_of_numbers.existence_of_an_inverse"></a><h6>
 293 <a name="id1134028"></a>
 294         <a class="link" href="quantifiers__maps_of_numbers.html#boost_icl.semantics.quantifiers__maps_of_numbers.existence_of_an_inverse">Existence
 295         of an Inverse</a>
 296       </h6>
 297 <p>
 298         By now <code class="computeroutput"><span class="keyword">signed</span> <span class="identifier">Quantifiers</span></code>
 299         <code class="computeroutput"><span class="identifier">Q</span></code> are commutative monoids
 300         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>
 301         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>
 302         do, the <code class="computeroutput"><span class="identifier">CodomainT</span></code> type is
 303         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>
 304         that is also <span class="emphasis"><em><span class="bold"><strong>total</strong></span></em></span>
 305         has an <span class="emphasis"><em><span class="bold"><strong>inverse</strong></span></em></span> and
 306         the following law holds:
 307       </p>
 308 <p>
 309
 310 </p>
 311 <pre class="programlisting"><span class="identifier">InverseElement</span><span class="special">&lt;</span><span class="identifier">Qt</span><span class="special">,==</span> <span class="special">&gt;</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>
 312 </pre>
 313 <p>
 314       </p>
 315 <p>
 316         Which means that each <code class="computeroutput"><span class="identifier">TotalQuantifier</span></code>
 317         over an abelian group is an abelian group itself.
 318       </p>
 319 <p>
 320         This also implies that a <code class="computeroutput"><span class="identifier">Quantifier</span></code>
 321         of <code class="computeroutput"><span class="identifier">Quantifiers</span></code> is again a
 322         <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>
 323         is also a <code class="computeroutput"><span class="identifier">TotalQuantifier</span></code>.
 324       </p>
 325 <p>
 326         <code class="computeroutput"><span class="identifier">TotalQuantifiers</span></code> resemble
 327         the notion of a vector space partially. The concept could be completed to
 328         a vector space, if a scalar multiplication was added.
 329       </p>
 330 </div>
 331 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 332 <td align="left"></td>
 333 <td align="right"><div class="copyright-footer">Copyright &#169; 2007 -2010 Joachim Faulhaber<br>Copyright &#169; 1999 -2006 Cortex Software GmbH<p>
 334         Distributed under the Boost Software License, Version 1.0. (See accompanying
 335         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>)
 336       </p>
 337 </div></td>
 338 </tr></table>
 339 <hr>
 340 <div class="spirit-nav">
 341 <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>
 342 </div>
 343 </body>
 344 </html>