[ceph.git] / ceph / src / boost / libs / icl / doc / functions_intersection.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)
]

[/ //= Intersection ============================================================]
[section Intersection][/ Intersection]

[section Synopsis][/ Intersection]

[table
[[Intersection]                             [__ch_itv_t__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]

[[`void add_intersection(T&, const T&, const P&)`][ ]   [__eiS][__eiS __bpM][ ]     [ ]       ]
[[`T& operator &=(T&, const P&)`]                 [ ]   [__eiS][__eiS __bpM][__es]  [__bm]    ]
[[`T  operator & (T, const P&)`\n
  `T  operator & (const P&, T)`]                 [__i]  [__eiS][__eiS __bpM][__es]  [__bm]    ]
[[`bool intersects(const T&, const P&)`\n
  `bool disjoint(const T&, const P&)`]           [__i]  [__eiS][__eiS __bpM][__es]  [__bm]    ]
]

Functions and operators that are related to ['*intersection*] on *icl* objects
are given in the table above.


[table
[[]      [Description of Intersection]]
[[`Sets`][Intersection on Sets implements ['*set intersection*]]]
[[`Maps`][Intersection on Maps implements a ['*map intersection*] function similar to /set intersection/.
          If, on intersection, an element value pair `(k,v)` it's key `k` is in the map 
          already, the intersection function is propagated to the associated value,
          if it exists for the Map's codomain_type. 
          
          If the codomain_type has no intersection operation, associated 
          values are combined using addition. For partial map types this
          results in an addition on the intersection of the domains of
          the intersected sets. For total maps intersection and
          addition are identical in this case.
                  
          See also
          [link boost_icl.semantics.quantifiers__maps_of_numbers.intersection_on_quantifiers ['intersection on Maps of numbers]]. 
        
          A Map can be intersected with key types: an element 
          (an interval for interval_maps) and and a Set. This 
          results in the selection of a submap, and can be
          defined as a generalized selection function on Maps.
         ]]
]

[endsect][/ Synopsis Intersection]


[section Functions][/ Intersection]

The overloaded function 

`void add_intersection(T& result, const T& y, const P& x)`

allows to accumulate the intersection of `y` and `x` in the first argument `result`. 
`Result` might already contain data. In this case the intersection of `y` and `x` 
is `added` the the contents of `result`.
``
T s1 = f, s2 = f, y = g; P x = h; // The effect of 
add_intersection(s1, y, x);       // add_intersection 
s2 += (y & x);                    // and & followed by +=
assert(s1==s2);                   // is identical
``

This might be convenient, if intersection is used like a generalized selection function.
Using element or segment types for `P`, we can select small parts of a container
`y` and accumulate them in `section`.

The admissible combinations of types for function 
`void add_intersection(T&, const T&, const P&)` can be summarized in the 
['*overload table*] below. 
Compared to other overload tables, placements of function arguments are
different: Row headers denote type `T` of `*this` object.
Columns headers denote type `P` of the second function argument.
The table cells contain the arguments `T` of the intersections
`result`, which is the functions first argument.

``
/* overload table for */                                T\P| e i b p 
void T::add_intersection(T& result, const P&)const      ---+--------
                                                         s | s
                                                         m | m   m
                                                         S | S S     
                                                         M | M M M M 
``

The next table contains complexity characteristics for function `add_intersection`.

[table Time Complexity for function add_intersection on icl containers
[[`void add_intersection(T&, const T&, const P&)const`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
[[__icl_set__]                                   [__Olgn__]    []            []           []          ]
[[__icl_map__]                                   [__Olgn__]    []            [__Olgn__]   []          ]
[[__itv_sets__]                                  [__Olgn__]    [__On__]      []           []          ]
[[__itv_maps__]                                  [__Olgn__]    [__On__]      [__On__]     [__On__]    ]
]

[endsect][/ Function Intersection]


[section Inplace operators][/ Intersection]

The overload tables below are giving admissible
type combinations for the intersection `operator &=`.
As for the overload patterns of /subtraction/
intersections are possible within Sets and Maps
but also for Maps combined with /key objects/
which are /key elements, intervals/ and /Sets of keys/.

``
// overload tables for             element containers:     interval containers:
T& operator &= (T&, const P&)      &= | e b s m            &= | e i b p S M    
                                   ---+--------            ---+------------    
                                   s  | s   s              S  | S S     S      
                                   m  | m m m m            M  | M M M M M M    
``

While intersection on maps can be viewed as
a ['*generalisation of set intersection*]. The
combination on Maps and Sets can be interpreted as
a ['*generalized selection function*], because it
allows to select parts of a maps using
/key/ or /selection objects/.
So we have a ['*generalized intersection*] for
these overloads,

``
/* (Generalized) intersection */   &= | e b s m            &= | e i b p S M  
                                   ---+--------            ---+------------  
                                   s  | s   s              S  | S S     S    
                                   m  |   m   m            M  |     M M   M  
``

[*and] a ['*selection by key objects*] here:

``
/* Selection by key objects */     &= | e b s m            &= | e i b p S M 
                                   ---+--------            ---+------------ 
                                   s  | s   s              S  | S S     S   
                                   m  | m   m              M  | M M     M   
``

The differences for the different functionalities
of `operator &=` are on the Map-row of the
tables. Both functionalities fall together
for Sets in the function ['*set intersection*].

Complexity characteristics for inplace intersection operations are 
given by the next tables where 
``
n = iterative_size(y);
m = iterative_size(x); //if P is a container type
``

[table Time Complexity for inplace intersection on element containers
[[`T& operator &= (T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]]
[[__icl_set__]                    [__Olgn__]    []               [__Omlgn__]     []              ]
[[__icl_map__]                    [__Olgn__]    [__Olgn__]       [__Omlgn__]     [__Omlgn__]     ]
]

[table Time Complexity for inplace intersection on interval containers
[[`T& operator &= (T& y, const P& x)`][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
[[interval_sets]                  [__Olgn__]    [__On__]      []               []               [__Omlgnpm__]    []               ]
[[interval_maps]                  [__Olgn__]    [__On__]      [__Olgn__]       [__On__]         [__Omlgnpm__]    [__Omlgnpm__]    ]
]

[endsect][/ Inplace operators Intersection]

[section Infix operators][/ Intersection]

For the *icl's* infix intersection the
following overloads are available:

``
// overload tables for             element containers:     interval containers:
T operator & (T, const P&)         &  | e b s m            &  | e  i  b  p  S1 S2 S3 M1 M3
T operator & (const P&, T)         ---+--------            ---+---------------------------
                                   e  |     s m            e  |             S1 S2 S3 M1 M3
                                   b  |       m            i  |    i        S1 S2 S3 M1 M3
                                   s  | s   s m            b  |                      M1 M3
                                   m  | m m m m            p  |                      M1 M3
                                                           S1 | S1 S1       S1 S2 S3 M1 M3
                                                           S2 | S2 S2       S2 S2 S3 M1 M3
                                                           S3 | S3 S3       S3 S3 S3 M1 M3
                                                           M1 | M1 M1 M1 M1 M1 M1 M1 M1 M3
                                                           M3 | M3 M3 M3 M3 M3 M3 M3 M3 M3
``

To resolve ambiguities among interval containers
the ['*finer*] container type is chosen as result type.

Again, we can split up the overload tables of
`operator &` in a part describing
the ['*generalized intersection] on interval containers
and a second part defining the
['*selection by key object] functionality.

``
/* (Generalized) intersection */   &  | e b s m            &  | e  i  b  p  S1 S2 S3 M1 M3
                                   ---+--------            ---+---------------------------
                                   e  |     s              e  |             S1 S2 S3      
                                   b  |       m            i  |    i        S1 S2 S3      
                                   s  | s   s              b  |                      M1 M3
                                   m  |   m   m            p  |                      M1 M3
                                                           S1 | S1 S1       S1 S2 S3      
                                                           S2 | S2 S2       S2 S2 S3      
                                                           S3 | S3 S3       S3 S3 S3      
                                                           M1 |       M1 M1          M1 M3
                                                           M3 |       M3 M3          M3 M3
``

``
/* Selection by key objects */     &  | e b s m            &  | e  i  b  p  S1 S2 S3 M1 M3
                                   ---+--------            ---+---------------------------
                                   e  |     s m            e  |             S1 S2 S3 M1 M3
                                   b  |                    i  |    i        S1 S2 S3 M1 M3
                                   s  | s   s m            b  |                           
                                   m  | m   m              p  |                           
                                                           S1 | S1 S1       S1 S2 S3 M1 M3
                                                           S2 | S2 S2       S2 S2 S3 M1 M3
                                                           S3 | S3 S3       S3 S3 S3 M1 M3
                                                           M1 | M1 M1       M1 M1 M1      
                                                           M3 | M3 M3       M3 M3 M3      
``

[endsect][/ Inplace operator Intersection]

[section Intersection tester]

[table
[[Tester]                                          [Desctription]]
[[`bool intersects(const T& left, const P& right)`][Tests, if `left` and `right` intersect.]]
[[`bool disjoint(const T& left, const P& right)`]  [Tests, if `left` and `right` are disjoint.]]
[[]                                                [`intersects(x,y) == !disjoint(x,y)`]]
]

``
bool intersects(const T&, const P&)      T\P| e b s m      T\P| e i b p S M 
bool   disjoint(const T&, const P&)      ---+--------      ---+------------
                                          s | 1   1         S | 1 1     1  
                                          m | 1 1 1 1       M | 1 1 1 1 1 1
``

[endsect][/ Intersection tester]


['*See also . . .*]
[table
[]
[[[link boost_icl.function_reference.symmetric_difference ['*Symmetric difference*]] ]]
[[[link boost_icl.function_reference.subtraction  ['*Subtraction*]]  ]]
[[[link boost_icl.function_reference.addition     ['*Addition*]]     ]]
]
['*Back to section . . .*]
[table
[]
[[[link function_synopsis_table ['*Function Synopsis*]]    ]]
[[[link boost_icl.interface ['*Interface*]]                ]]
]


[endsect][/ Intersection]
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	[/ //= Intersection ============================================================]
	10	[section Intersection][/ Intersection]
	11
	12	[section Synopsis][/ Intersection]
	13
	14	[table
	15	[[Intersection] [__ch_itv_t__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
	16
	17	[[`void add_intersection(T&, const T&, const P&)`][ ] [__eiS][__eiS __bpM][ ] [ ] ]
	18	[[`T& operator &=(T&, const P&)`] [ ] [__eiS][__eiS __bpM][__es] [__bm] ]
	19	[[`T operator & (T, const P&)`\n
	20	`T operator & (const P&, T)`] [__i] [__eiS][__eiS __bpM][__es] [__bm] ]
	21	[[`bool intersects(const T&, const P&)`\n
	22	`bool disjoint(const T&, const P&)`] [__i] [__eiS][__eiS __bpM][__es] [__bm] ]
	23	]
	24
	25	Functions and operators that are related to ['intersection] on icl objects
	26	are given in the table above.
	27
	28
	29	[table
	30	[[] [Description of Intersection]]
	31	[[`Sets`][Intersection on Sets implements ['set intersection]]]
	32	[[`Maps`][Intersection on Maps implements a ['map intersection] function similar to /set intersection/.
	33	If, on intersection, an element value pair `(k,v)` it's key `k` is in the map
	34	already, the intersection function is propagated to the associated value,
	35	if it exists for the Map's codomain_type.
	36
	37	If the codomain_type has no intersection operation, associated
	38	values are combined using addition. For partial map types this
	39	results in an addition on the intersection of the domains of
	40	the intersected sets. For total maps intersection and
	41	addition are identical in this case.
	42
	43	See also
	44	[link boost_icl.semantics.quantifiers__maps_of_numbers.intersection_on_quantifiers ['intersection on Maps of numbers]].
	45
	46	A Map can be intersected with key types: an element
	47	(an interval for interval_maps) and and a Set. This
	48	results in the selection of a submap, and can be
	49	defined as a generalized selection function on Maps.
	50	]]
	51	]
	52
	53	[endsect][/ Synopsis Intersection]
	54
	55
	56	[section Functions][/ Intersection]
	57
	58	The overloaded function
	59
	60	`void add_intersection(T& result, const T& y, const P& x)`
	61
	62	allows to accumulate the intersection of `y` and `x` in the first argument `result`.
	63	`Result` might already contain data. In this case the intersection of `y` and `x`
	64	is `added` the the contents of `result`.
65	``
66	T s1 = f, s2 = f, y = g; P x = h; // The effect of
67	add_intersection(s1, y, x); // add_intersection
68	s2 += (y & x); // and & followed by +=
69	assert(s1==s2); // is identical
70	``
71
72	This might be convenient, if intersection is used like a generalized selection function.
73	Using element or segment types for `P`, we can select small parts of a container
74	`y` and accumulate them in `section`.
75
76	The admissible combinations of types for function
77	`void add_intersection(T&, const T&, const P&)` can be summarized in the
78	['overload table] below.
79	Compared to other overload tables, placements of function arguments are
80	different: Row headers denote type `T` of `*this` object.
81	Columns headers denote type `P` of the second function argument.
82	The table cells contain the arguments `T` of the intersections
83	`result`, which is the functions first argument.
84
85	``
86	/* overload table for */ T\P\| e i b p
87	void T::add_intersection(T& result, const P&)const ---+--------
88	s \| s
89	m \| m m
90	S \| S S
91	M \| M M M M
92	``
93
94	The next table contains complexity characteristics for function `add_intersection`.
95
96	[table Time Complexity for function add_intersection on icl containers
97	[[`void add_intersection(T&, const T&, const P&)const`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
98	[[__icl_set__] [__Olgn__] [] [] [] ]
99	[[__icl_map__] [__Olgn__] [] [__Olgn__] [] ]
100	[[__itv_sets__] [__Olgn__] [__On__] [] [] ]
101	[[__itv_maps__] [__Olgn__] [__On__] [__On__] [__On__] ]
102	]
103
104	[endsect][/ Function Intersection]
105
106
107	[section Inplace operators][/ Intersection]
108
109	The overload tables below are giving admissible
110	type combinations for the intersection `operator &=`.
111	As for the overload patterns of /subtraction/
112	intersections are possible within Sets and Maps
113	but also for Maps combined with /key objects/
114	which are /key elements, intervals/ and /Sets of keys/.
115
116	``
117	// overload tables for element containers: interval containers:
118	T& operator &= (T&, const P&) &= \| e b s m &= \| e i b p S M
119	---+-------- ---+------------
120	s \| s s S \| S S S
121	m \| m m m m M \| M M M M M M
122	``
123
124	While intersection on maps can be viewed as
125	a ['generalisation of set intersection]. The
126	combination on Maps and Sets can be interpreted as
127	a ['generalized selection function], because it
128	allows to select parts of a maps using
129	/key/ or /selection objects/.
130	So we have a ['generalized intersection] for
131	these overloads,
132
133	``
134	/* (Generalized) intersection */ &= \| e b s m &= \| e i b p S M
135	---+-------- ---+------------
136	s \| s s S \| S S S
137	m \| m m M \| M M M
138	``
139
140	[and] a ['selection by key objects*] here:
141
142	``
143	/* Selection by key objects */ &= \| e b s m &= \| e i b p S M
144	---+-------- ---+------------
145	s \| s s S \| S S S
146	m \| m m M \| M M M
147	``
148
149	The differences for the different functionalities
150	of `operator &=` are on the Map-row of the
151	tables. Both functionalities fall together
152	for Sets in the function ['set intersection].
153
154	Complexity characteristics for inplace intersection operations are
155	given by the next tables where
156	``
157	n = iterative_size(y);
158	m = iterative_size(x); //if P is a container type
159	``
160
161	[table Time Complexity for inplace intersection on element containers
162	[[`T& operator &= (T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]]
163	[[__icl_set__] [__Olgn__] [] [__Omlgn__] [] ]
164	[[__icl_map__] [__Olgn__] [__Olgn__] [__Omlgn__] [__Omlgn__] ]
165	]
166
167	[table Time Complexity for inplace intersection on interval containers
168	[[`T& operator &= (T& y, const P& x)`][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
169	[[interval_sets] [__Olgn__] [__On__] [] [] [__Omlgnpm__] [] ]
170	[[interval_maps] [__Olgn__] [__On__] [__Olgn__] [__On__] [__Omlgnpm__] [__Omlgnpm__] ]
171	]
172
173	[endsect][/ Inplace operators Intersection]
174
175	[section Infix operators][/ Intersection]
176
177	For the icl's infix intersection the
178	following overloads are available:
179
180	``
181	// overload tables for element containers: interval containers:
182	T operator & (T, const P&) & \| e b s m & \| e i b p S1 S2 S3 M1 M3
183	T operator & (const P&, T) ---+-------- ---+---------------------------
184	e \| s m e \| S1 S2 S3 M1 M3
185	b \| m i \| i S1 S2 S3 M1 M3
186	s \| s s m b \| M1 M3
187	m \| m m m m p \| M1 M3
188	S1 \| S1 S1 S1 S2 S3 M1 M3
189	S2 \| S2 S2 S2 S2 S3 M1 M3
190	S3 \| S3 S3 S3 S3 S3 M1 M3
191	M1 \| M1 M1 M1 M1 M1 M1 M1 M1 M3
192	M3 \| M3 M3 M3 M3 M3 M3 M3 M3 M3
193	``
194
195	To resolve ambiguities among interval containers
196	the ['finer] container type is chosen as result type.
197
198	Again, we can split up the overload tables of
199	`operator &` in a part describing
200	the ['*generalized intersection] on interval containers
201	and a second part defining the
202	['*selection by key object] functionality.
203
204	``
205	/* (Generalized) intersection */ & \| e b s m & \| e i b p S1 S2 S3 M1 M3
206	---+-------- ---+---------------------------
207	e \| s e \| S1 S2 S3
208	b \| m i \| i S1 S2 S3
209	s \| s s b \| M1 M3
210	m \| m m p \| M1 M3
211	S1 \| S1 S1 S1 S2 S3
212	S2 \| S2 S2 S2 S2 S3
213	S3 \| S3 S3 S3 S3 S3
214	M1 \| M1 M1 M1 M3
215	M3 \| M3 M3 M3 M3
216	``
217
218	``
219	/* Selection by key objects */ & \| e b s m & \| e i b p S1 S2 S3 M1 M3
220	---+-------- ---+---------------------------
221	e \| s m e \| S1 S2 S3 M1 M3
222	b \| i \| i S1 S2 S3 M1 M3
223	s \| s s m b \|
224	m \| m m p \|
225	S1 \| S1 S1 S1 S2 S3 M1 M3
226	S2 \| S2 S2 S2 S2 S3 M1 M3
227	S3 \| S3 S3 S3 S3 S3 M1 M3
228	M1 \| M1 M1 M1 M1 M1
229	M3 \| M3 M3 M3 M3 M3
230	``
231
232	[endsect][/ Inplace operator Intersection]
233
234	[section Intersection tester]
235
236	[table
237	[[Tester] [Desctription]]
238	[[`bool intersects(const T& left, const P& right)`][Tests, if `left` and `right` intersect.]]
239	[[`bool disjoint(const T& left, const P& right)`] [Tests, if `left` and `right` are disjoint.]]
240	[[] [`intersects(x,y) == !disjoint(x,y)`]]
241	]
242
243	``
244	bool intersects(const T&, const P&) T\P\| e b s m T\P\| e i b p S M
245	bool disjoint(const T&, const P&) ---+-------- ---+------------
246	s \| 1 1 S \| 1 1 1
247	m \| 1 1 1 1 M \| 1 1 1 1 1 1
248	``
249
250	[endsect][/ Intersection tester]
251
252
253	['See also . . .]
254	[table
255	[]
256	[[[link boost_icl.function_reference.symmetric_difference ['Symmetric difference]] ]]
257	[[[link boost_icl.function_reference.subtraction ['Subtraction]] ]]
258	[[[link boost_icl.function_reference.addition ['Addition]] ]]
259	]
260	['Back to section . . .]
261	[table
262	[]
263	[[[link function_synopsis_table ['Function Synopsis]] ]]
264	[[[link boost_icl.interface ['Interface]] ]]
265	]
266
267
268	[endsect][/ Intersection]
269
270
271