[ceph.git] / ceph / src / boost / 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]
Commit	Line	Data
7c673cae FG	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
	46	All common equality and compare operators are defined for
	47	all objects of the icl. For all icl containers
	48	equality and compare operators implement lexicographical
	49	equality and lexicographical comparison, that depends on
	50	the equality of template parameter `Compare`.
	51	This includes the less ordering on intervals, that can be
	52	perceived as the sequence of elements between their lower and upper
	53	bound. This generalized lexicogrphical comparison in intervals
	54	can 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
69	Equality and compare operators are defined for all icl
70	objects but there are no overloads between different types.
71
72	Containers of different segmentation are different,
73	even if their elements are the same:
74	``
75	split_interval_set<time> w1, w2; //Pseudocode
76	w1 = {[Mon .. Sun)}; //split_interval_set containing a week
77	w2 = {[Mon .. Fri)[Sat .. Sun)}; //Same week split in work and week end parts.
78	w1 == w2; //false: Different segmentation
79	is_element_equal(w1,w2); //true: Same elements contained
80	``
81
82	[Complexity] is ['linear*] in the `iterative_size` of the shorter
83	container to compare.
84
85	[endsect][/ Lexicographical Ordering; Equivalences and Orderings]
86
87
88	[/ ----------------------------------------------------------------------------]
89
90	[section Sequential Element Ordering][/ Equivalences and Orderings]
91
92	The ['Sequential Element Ordering] abstracts from the way in which
93	elements of interval containers are clustered into intervals:
94	it's ['segmentation].
95
96	So these equality and compare operations can be applied within
97	interval container types. The admissible type combinations are summarized
98	in the next overload table.
99
100	``
101	// overload tables for
102	bool is_element_equal (const T&, const P&)
103	bool is_element_less (const T&, const P&)
104	bool is_element_greater(const T&, const P&)
105
106	element containers: interval containers:
107	T\P\| s m T\P\| S1 S2 S3 M1 M3
108	---+---- ---+---------------
109	s \| 1 S1 \| 1 1 1
110	m \| 1 S2 \| 1 1 1
111	S3 \| 1 1 1
112	M1 \| 1 1
113	M3 \| 1 1
114	``
115
116	For element containers lexicographical equality and
117	sequential element equality are identical.
118
119	The complexity of sequential element comparison functions
120	is ['linear] in the `iterative_size` of the larger
121	container.
122
123	[endsect]
124
125	[section Distinct Equality]
126
127	['Distinct Equality] is an equality predicate that is available
128	for __icl_maps__ and __itv_maps__. It yields true, if
129	two maps are sequential element equal except for value
130	pairs whose associated values are identity elements.
131
132	[*Complexity] is linear in the `iterative_size` of the
133	larger 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