1[/ 2 Copyright (c) 2008-2010 Joachim Faulhaber 3 4 Distributed under the Boost Software License, Version 1.0. 5 (See accompanying file LICENSE_1_0.txt or copy at 6 http://www.boost.org/LICENSE_1_0.txt) 7] 8 9 10[/ //= Equivalences and Orderings ===================================================] 11[section Equivalences and Orderings] 12 13[section Synopsis][/ Equivalences and Orderings] 14 15[table 16[[['*Equivalences and Orderings*]][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]] 17[[['Segment Ordering]] [ ] [ ] [ ] [ ] [ ] ] 18[[`bool operator == (const T&, const T&)`] [1] [1] [1] [1] [1] ] 19[[`bool operator != (const T&, const T&)`] [1] [1] [1] [1] [1] ] 20[[`bool operator < (const T&, const T&)`] [1] [1] [1] [1] [1] ] 21[[`bool operator > (const T&, const T&)`] [1] [1] [1] [1] [1] ] 22[[`bool operator <= (const T&, const T&)`] [1] [1] [1] [1] [1] ] 23[[`bool operator >= (const T&, const T&)`] [1] [1] [1] [1] [1] ] 24[[['Element Ordering]] [ ] [ ] [ ] [ ] [ ] ] 25[[`bool is_element_equal(const T&, const P&)`] [ ] [__S] [__M] [1] [1] ] 26[[`bool is_element_less(const T&, const P&)`] [ ] [__S] [__M] [1] [1] ] 27[[`bool is_element_greater(const T&, const P&)`][ ] [__S] [__M] [1] [1] ] 28[[['Distinct Equality]] [ ] [ ] [ ] [ ] [ ] ] 29[[`bool is_distinct_equal(const T&, const P&)`][ ] [ ] [__M] [ ] [1] ] 30] 31 32 33[endsect][/ Synopsis Equivalences and Orderings] 34 35[section Less on Intervals] 36 37[table 38[[ ] [Types][]] 39[[`x < y`] [__i] [`x` begins before `y` or, for equal beginnings `x` ends before `y`]] 40] 41 42[endsect][/ Less on Intervals] 43 44[section Lexicographical Ordering][/ Equivalences and Orderings] 45 46All common equality and compare operators are defined for 47all objects of the *icl*. For all *icl* containers 48equality and compare operators implement lexicographical 49equality and lexicographical comparison, that depends on 50the equality of template parameter `Compare`. 51This includes the less ordering on intervals, that can be 52perceived as the sequence of elements between their lower and upper 53bound. This generalized lexicogrphical comparison in intervals 54can also be specified this way: 55 56[table 57[] 58[[`x < y`] [`:=`] [`x` begins before `y` or, for equal beginnings `x` ends before `y`.]] 59 60[[] [] [The other operators can be deduced in the usual way]] 61[[`x > y`] [`:=`] [`y < x`] ] 62[[`x <= y`] [`:=`] [`!(y < x)`] ] 63[[`x >= y`] [`:=`] [`!(x < y)`] ] 64[[`x == y`] [`:=`] [`!(x < y) && !(y < x)` induced equivalence] ] 65[[`x != y`] [`:=`] [`!(x == y)`] ] 66] 67 68 69Equality and compare operators are defined for all *icl* 70objects but there are no overloads between different types. 71 72Containers of different segmentation are different, 73even if their elements are the same: 74`` 75split_interval_set<time> w1, w2; //Pseudocode 76w1 = {[Mon .. Sun)}; //split_interval_set containing a week 77w2 = {[Mon .. Fri)[Sat .. Sun)}; //Same week split in work and week end parts. 78w1 == w2; //false: Different segmentation 79is_element_equal(w1,w2); //true: Same elements contained 80`` 81 82[*Complexity] is ['*linear*] in the `iterative_size` of the shorter 83container to compare. 84 85[endsect][/ Lexicographical Ordering; Equivalences and Orderings] 86 87 88[/ ----------------------------------------------------------------------------] 89 90[section Sequential Element Ordering][/ Equivalences and Orderings] 91 92The ['*Sequential Element Ordering*] abstracts from the way in which 93elements of interval containers are clustered into intervals: 94it's ['*segmentation*]. 95 96So these equality and compare operations can be applied within 97interval container types. The admissible type combinations are summarized 98in the next overload table. 99 100`` 101// overload tables for 102bool is_element_equal (const T&, const P&) 103bool is_element_less (const T&, const P&) 104bool is_element_greater(const T&, const P&) 105 106element containers: interval containers: 107T\P| s m T\P| S1 S2 S3 M1 M3 108---+---- ---+--------------- 109s | 1 S1 | 1 1 1 110m | 1 S2 | 1 1 1 111 S3 | 1 1 1 112 M1 | 1 1 113 M3 | 1 1 114`` 115 116For element containers lexicographical equality and 117sequential element equality are identical. 118 119The *complexity* of sequential element comparison functions 120is ['*linear*] in the `iterative_size` of the larger 121container. 122 123[endsect] 124 125[section Distinct Equality] 126 127['*Distinct Equality*] is an equality predicate that is available 128for __icl_maps__ and __itv_maps__. It yields true, if 129two maps are sequential element equal except for value 130pairs whose associated values are identity elements. 131 132[*Complexity] is linear in the `iterative_size` of the 133larger container to compare. 134 135[endsect] 136 137 138['*See also . . .*] 139[table 140[] 141[[[link boost_icl.semantics.orderings_and_equivalences ['*Semantics*]]]] 142] 143['*Back to section . . .*] 144[table 145[] 146[[[link function_synopsis_table ['*Function Synopsis*]]]] 147[[[link boost_icl.interface ['*Interface*]] ]] 148] 149 150[endsect][/ Equivalences and Orderings] 151 152 153