| Home | Libraries | People | FAQ | More

### Required Concepts

There are uniform requirements for the template parameters across icl's class templates. The template parameters can be grouped with respect to those requirements.

| used in | Kind | Parameter | Instance | Description
--- | --- | --- | --- | --- | ---
Domain order | `Intervals, Sets, Maps` | `typename` | `DomainT` |  | For the type `DomainT` of key elements `...`
|  | `template` | `Compare` | `Compare<DomainT>` | `...` there is an order `Compare`
Interval type | `interval_sets/maps` | `typename` | `IntervalT` |  | `...` the `IntervalT` parameter has to use the same element type and order.
Codomain aggregation | `Maps` | `typename` | `CodomainT` |  | For the type `CodomainT` of associated values `...`
|  | `template` | `Combine` | `Combine<CodomainT>` | `...` there is a binary functor `Combine<CodomainT>()` to combine them
|  |  |  | `Inverse<Combine<CodomainT>>` | `...` and implicitly an `Inverse` functor to inversely combine them.
|  | `template` | `Section` | `Section<CodomainT>` | Intersection is propagated to CodomainT values via functor `Section<CodomainT>()`
Memory allocation | `Sets, Maps` | `template` | `Alloc` | `Alloc<`various`>` | An allocator can be chosen for memory allocation.

##### Requirements on DomainT

The next table gives an overview over the requirements for template parameter `DomainT`. Some requirements are dependent on conditions. Column operators shows the operators and functions that are expected for `DomainT`, if the default order `Compare = std::less` is used.

Parameter | Condition | Operators | Requirement
--- | --- | --- | ---
`DomainT` |  | `DomainT(), <` | `Regular<DomainT> && StrictWeakOrdering<DomainT,Compare>`
|  | `++, unit_element<CodomainT>::value()` | `&& (IsIncrementable<DomainT>||HasUnitElement<DomainT>)`
| `IsIntegral<DomainT>` | `++, --` | `IsIncrementable<DomainT> && IsDecrementable<DomainT>`

A domain type `DomainT` for intervals and interval containers has to satisfy the requirements of concept `Regular` which implies among other properties the existence of a copy and a default constructor. In addition `IsIncrementable` or `HasUnitElement` is required for `DomainT`. In the icl we represent an empty closed interval as interval `[b,a]` where `a < b` (here `<` represents `Compare<DomainT>()`). To construct one of these empty intervals as default constructor for any type `DomainT` we choose `[1,0]`, where `0` is a null-value or `identity_element` and `1` is a one-value or `unit_element`:

    interval() := [unit_element<DomainT>::value(), identity_element<DomainT>::value()] //pseudocode

`Identity_elements` are implemented via call of the default constructor of `DomainT`. A `unit_element<T>::value()` is implemented `by default` as a `identity_element`, that is incremented once.

    template <class Type>
    inline Type unit_element<Type>::value(){ return succ(identity_element<Type>::value()); };

So a type `DomainT` that is `incrementable` will also have an `unit_element`. If it does not, a `unit_element` can be provided. A `unit_element` can be any value, that is greater as the `identity_element` in the `Compare` order given. An example of a type, that has an `identity_element` but no increment operation is `string`. So for `std::string` a unit_element is implemented like this:

    // Smallest 'visible' string that is greater than the empty string.
    template <>
    inline std::string unit_element<std::string>::value(){ return std::string(" "); };

Just as for the key type of std::sets and maps template parameter `Compare` is required to be a strict weak ordering on `DomainT`.

Finally, if `DomainT` is an integral type, `DomainT` needs to be `incrementable` and `decrementable`. This 'bicrementability' needs to be implemented on the smallest possible unit of the integral type. This seems like being trivial but there are types like e.g. `boost::date_time::ptime`, that are integral in nature but do not provide the required in- and decrementation on the least incrementable unit. For `icl::intervals` incementation and decementation is used for computations between open to closed interval borders like e.g. `[2,43) == [2,42]`. Such computations always need only one in- or decrementation, if `DomainT` is an integral type.

###### Requirements on IntervalT

Requirements on the `IntervalT` parameter are closely related to the `DomainT` parameter. `IntervalT` has two associated types itself for an element type and a compare order that have to be consistent with the element and order parameters of their interval containers. `IntervalT` then has to implement an order called `exclusive_less`. Two intervals `x, y` are exclusive_less

    icl::exclusive_less(x, y)

if all `DomainT` elements of `x` are less than elements of `y` in the `Compare` order.

Parameter | Operators | Requirement
--- | --- | ---
`IntervalT` | `exclusive_less` | `IsExclusiveLessComparable<Interval<DomainT,Compare> >`

##### Requirements on CodomainT

Summarized in the next table are requirements for template parameter `CodomainT` of associated values for `Maps`. Again there are conditions for some of the requirements. Column operators contains the operators and functions required for `CodomainT`, if we are using the default combiner `Combine = icl::inplace_plus`.

Parameter | Condition | Operators | Requirement
--- | --- | --- | ---
`CodomainT` | `add`, `subtract`, `intersect` unused | `CodomainT(), ==` | `Regular<CodomainT>` which implies
|  |  | `DefaultConstructible<CodomainT> && EqualityComparable<CodomainT>`
| only `add` used | `+=` | `&& Combinable<CodomainT,Combine>`
| ... and also `subtract` used | `-=` | `&& Combinable<CodomainT,Inverse<Combine> >`
| `Section` used and `CodomainT` is a set | `&=` | `&& Intersectable<CodomainT,Section>`

The requirements on the type `CodomainT` of associated values for a `icl::map` or `interval_map` depend on the usage of their aggregation functionality. If aggregation on overlap is never used, that is to say that none of the addition, subtraction and intersection operations (`+, +=, add`, `-, -=, subtract`, &, &=, add_intersection) are used on the `interval_map`, then `CodomainT` only needs to be Regular.

Regular object semantics implies `DefaultConstructible` and `EqualityComparable` which means it has a default ctor `CodomainT()` and an `operator ==`.

Use `interval_maps` without aggregation, if the associated values are not addable but still are attached to intervals so you want to use `interval_maps` to handle them. As long as those values are added with `insert` and deleted with `erase` `interval_maps` will work fine with such values.

If only addition is used via `interval_map's` `+, +=` or `add` but no subtraction, then `CodomainT` need to be `Combinable` for functor template `Combine`. That means in most cases when the default implementation `inplace_plus` for `Combine` is used, that `CodomainT` has to implement `operator +=`.

For associated value types, that are addable but not subtractable like e.g. `std::string` it usually makes sense to use addition to combine values but the inverse combination is not desired.

    interval_map<int,std::string> cat_map;
    cat_map += make_pair(interval<int>::rightopen(1,5),std::string("Hello"));
    cat_map += make_pair(interval<int>::rightopen(3,7),std::string(" world"));
    cout << "cat_map: " << cat_map << endl;
    //cat_map: {([1,3)->Hello)([3,5)->Hello world)([5,7)-> world)}

For complete aggregation functionality an inverse aggregation functor on a `Map`'s `CodomainT` is needed. The icl provides a metafunction `inverse` for that purpose. Using the default `Combine = inplace_plus` that relies on the existence of `operator +=` on type `CodomainT` metafunction `inverse` will infer `inplace_minus` as inverse functor, that requires `operator -=` on type `CodomainT`.

In the icl's design we make the assumption, in particular for the default setting of parameters `Combine =` `inplace_plus`, that type `CodomainT` has a neutral element or `identity_element` with respect to the `Combine` functor.