Equivalences and Orderings

| Home | Libraries | People | FAQ | More

### Equivalences and Orderings

#### Synopsis

Equivalences and Orderings | intervals | interval sets | interval maps | element sets | element maps
--- | --- | --- | --- | --- | ---
Segment Ordering |  |  |  |  |
`bool operator == (const T&, const T&)` | 1 | 1 | 1 | 1 | 1
`bool operator != (const T&, const T&)` | 1 | 1 | 1 | 1 | 1
`bool operator < (const T&, const T&)` | 1 | 1 | 1 | 1 | 1
`bool operator > (const T&, const T&)` | 1 | 1 | 1 | 1 | 1
`bool operator <= (const T&, const T&)` | 1 | 1 | 1 | 1 | 1
`bool operator >= (const T&, const T&)` | 1 | 1 | 1 | 1 | 1
Element Ordering |  |  |  |  |
`bool is_element_equal(const T&, const P&)` |  | S | M | 1 | 1
`bool is_element_less(const T&, const P&)` |  | S | M | 1 | 1
`bool is_element_greater(const T&, const P&)` |  | S | M | 1 | 1
Distinct Equality |  |  |  |  |
`bool is_distinct_equal(const T&, const P&)` |  |  | M |  | 1

#### Less on Intervals

| Types |
--- | --- | ---
`x < y` | i | `x` begins before `y` or, for equal beginnings `x` ends before `y`

#### Lexicographical Ordering

All common equality and compare operators are defined for all objects of the icl. For all icl containers equality and compare operators implement lexicographical equality and lexicographical comparison, that depends on the equality of template parameter `Compare`. This includes the less ordering on intervals, that can be perceived as the sequence of elements between their lower and upper bound. This generalized lexicogrphical comparison in intervals can also be specified this way:

`x < y` | `:=` | `x` begins before `y` or, for equal beginnings `x` ends before `y`.
|  | The other operators can be deduced in the usual way
`x > y` | `:=` | `y < x`
`x <= y` | `:=` | `!(y < x)`
`x >= y` | `:=` | `!(x < y)`
`x == y` | `:=` | `!(x < y) && !(y < x)` induced equivalence
`x != y` | `:=` | `!(x == y)`

Equality and compare operators are defined for all icl objects but there are no overloads between different types.

Containers of different segmentation are different, even if their elements are the same:

    split_interval_set<time> w1, w2; //Pseudocode
    w1 = {[Mon       ..       Sun)}; //split_interval_set containing a week
    w2 = {[Mon .. Fri)[Sat .. Sun)}; //Same week split in work and week end parts.
    w1 == w2;                        //false: Different segmentation
    is_element_equal(w1,w2);         //true:  Same elements contained

Complexity is linear in the `iterative_size` of the shorter container to compare.

#### Sequential Element Ordering

The Sequential Element Ordering abstracts from the way in which elements of interval containers are clustered into intervals: it's segmentation.

So these equality and compare operations can be applied within interval container types. The admissible type combinations are summarized in the next overload table.

    // overload tables for
    bool is_element_equal  (const T&, const P&)
    bool is_element_less   (const T&, const P&)
    bool is_element_greater(const T&, const P&)

    element containers:     interval containers:
    T\P| s m                T\P| S1 S2 S3 M1 M3
    ---+----                ---+---------------
    s  | 1                  S1 | 1  1  1
    m  |   1                S2 | 1  1  1
                            S3 | 1  1  1
                            M1 |          1  1
                            M3 |          1  1

For element containers lexicographical equality and sequential element equality are identical.

The complexity of sequential element comparison functions is linear in the `iterative_size` of the larger container.

#### Distinct Equality

Distinct Equality is an equality predicate that is available for `icl::maps` and `interval_maps`. It yields true, if two maps are sequential element equal except for value pairs whose associated values are identity elements.

Complexity is linear in the `iterative_size` of the larger container to compare.

See also . . .

Semantics

Back to section . . .

Function Synopsis
Interface