123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152 |
- [/
- 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]
|