Addability, Subtractability and Aggregate on Overlap

| Home | Libraries | People | FAQ | More

### Addability, Subtractability and Aggregate on Overlap

While addition and subtraction on `Sets` are implemented as set union and set difference, for `Maps` we want to implement aggregation on the associated values for the case of collision (of key elements) or overlap (of key intervals), which has been refered to as aggregate on overlap above. This kind of `Addability` and `Subtractability` allows to compute a lot of useful aggregation results on an `interval_map's` associated values, just by adding and subtracting value pairs. Various examples of aggregate on overlap are given in section examples. In addition, this concept of `Addability` and `Subtractability` contains the classical `Insertability` and `Erasability` of key value pairs as a special case so it provides a broader new semantics without loss of the classical one.

Aggregation is implemented for functions `add` and `subtract` by propagating a `Combiner` functor to combine associated values of type `CodomainT`. The standard `Combiner` is set as default template parameter `template<class>class Combine = inplace_plus`, which is again generically implemented by `operator +=` for all Addable types.

For `Combine` functors, the Icl provides an `inverse` functor.

`Combine<T>` | `inverse<Combine<T> >::type`
--- | ---
`inplace_plus``<T>` | `inplace_minus``<T>`
`inplace_et``<T>` | `inplace_caret``<T>`
`inplace_star``<T>` | `inplace_slash``<T>`
`inplace_max``<T>` | `inplace_min``<T>`
`inplace_identity``<T>` | `inplace_erasure``<T>`
`Functor` | `inplace_erasure``<T>`

The meta function `inverse` is mutually implemented for all but the default functor `Functor` such that e.g. `inverse<inplace_minus<T> >::type` yields `inplace_plus<T>`. Not in every case, e.g. `max/min`, does the `inverse` functor invert the effect of it's antetype. But for the default it does:

| `_add<Combine<CodomainT> >((k,x))` | `_subtract<inverse<Combine<CodomainT> >::type>((k,x))`
--- | --- | ---
Instance | `_add<inplace_plus<int> >((k,x))` | `_subtract<inplace_minus<int> >((k,x))`
Inversion | adds `x` on overlap. This inverts a preceding `subtract` of `x` on `k` | subtracts `x` on overlap. This inverts a preceding `add` of `x` on `k`

As already mentioned aggregating `Addability` and `Subtractability` on `Maps` contains the classical `Insertability` and `Erasability` of key value pairs as a special case:

aggregating function | equivalent classical function
--- | ---
`_add<inplace_identity<CodomainT> >(const value_type&)` | `insert(const value_type&)`
`_subtract<inplace_erasure<CodomainT> >(const value_type&)` | `erase(const value_type&)`

The aggregating member function templates `_add` and `_subtract` are not in the public interface of `interval_maps`, because the `Combine` functor is intended to be an invariant of `interval_map's` template instance to avoid, that clients spoil the aggregation by accidentally calling varying aggregation functors. But you could instantiate an `interval_map` to have `insert/erase` semantics this way:

    interval_map<int,int,partial_absorber,
                 std::less,
                 inplace_identity //Combine parameter specified
                > m;
    interval<int>::type itv = interval<int>::rightopen(2,7);
    m.add(make_pair(itv,42));      //same as insert
    m.subtract(make_pair(itv,42)); //same as erase

This is, of course, only a clarifying example. Member functions `insert` and `erase` are available in `interval_map's` interface so they can be called directly.