libs/icl/doc/functions_equivs_orderings.qbk

[/
    Copyright (c) 2008-2010 Joachim Faulhaber

    Distributed under the Boost Software License, Version 1.0.
    (See accompanying file LICENSE_1_0.txt or copy at
    http://www.boost.org/LICENSE_1_0.txt)
]


[/ //= Equivalences and Orderings ===================================================]
[section Equivalences and Orderings]

[section Synopsis][/ Equivalences and Orderings]

[table
[[['*Equivalences and Orderings*]][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_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]   ]
]


[endsect][/ Synopsis Equivalences and Orderings]

[section Less on Intervals]

[table
[[ ]    [Types][]]
[[`x < y`]   [__i]   [`x` begins before `y` or, for equal beginnings `x` ends before `y`]]
]

[endsect][/ Less on Intervals]

[section Lexicographical Ordering][/ Equivalences and Orderings]

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:

[table
[]
[[`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.

[endsect][/ Lexicographical Ordering; Equivalences and Orderings]


[/ ----------------------------------------------------------------------------]

[section Sequential Element Ordering][/ Equivalences and Orderings]

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.

[endsect]

[section Distinct Equality]

['*Distinct Equality*] is an equality predicate that is available
for __icl_maps__ and __itv_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.

[endsect]


['*See also . . .*]
[table
[]
[[[link boost_icl.semantics.orderings_and_equivalences ['*Semantics*]]]]
]
['*Back to section . . .*]
[table
[]
[[[link function_synopsis_table ['*Function Synopsis*]]]]
[[[link boost_icl.interface ['*Interface*]]                          ]]
]

[endsect][/ Equivalences and Orderings]