1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
[/
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)
]
[/ //= Containedness ===================================================================]
[section Containedness]
[table
[[['*Containedness*]] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__] ]
[[`bool T::empty()const`] [ ] [1] [1] [1] [1] ]
[[`bool is_empty(const T&)`] [1] [1] [1] [1] [1] ]
[[`bool contains(const T&, const P&)`\n
`bool within(const P&, const T&)`] [__ei] [__eiS][__eiS __bpM][__es] [__bm] ]
]
This group of functions refers to ['*contain*]edness which should
be fundamental to ['*contain*]ers. The function `contains`
is overloaded. It covers different kinds of containedness:
Containedness of elements, segments, and sub containers.
[table
[[['*Containedness*]] [ /O(...)/ ][Description ] ]
[[`bool T::empty()const`\n
`bool is_empty(const T&)`] [__O1__][Returns `true`, if the container is empty, `false` otherwise.] ]
[[`bool contains(const T&, const P&)`\n
`bool within(const P&, const T&)`] [[link complexities_contains ['see below]]]
[Returns `true`, if `super` container contains object `sub`.] ]
[[ ] [where] [ /n/` = iterative_size(sub)`] ]
[[ ] [ ] [ /m/` = iterative_size(super)`] ]
]
``
// overload tables for
bool contains(const T& super, const P& sub)
bool within(const P& sub, const T& super)
element containers: interval containers:
T\P| e b s m T\P| e i b p S M
--------+--- --------+-------
s | 1 1 S | 1 1 1
m | 1 1 1 1 M | 1 1 1 1 1 1
``
The overloads of `bool contains(const T& super, const P& sup)`
cover various kinds
of containedness. We can group them into a part (1) that checks
if an element, a segment or a container /of same kinds/ is contained in
an element or interval container
``
// (1) containedness of elements, segments or containers of same kind
T\P| e b s m T\P| e i b p S M
---+-------- ---+------------
s | 1 1 S | 1 1 1
m | 1 1 M | 1 1 1
``
and another part (2) that checks the containedness of
/key objects/, which can be /elements/ an /intervals/ or a /sets/.
``
// (2) containedness of key objects.
T\P| e b s m T\P| e i b p S M
---+-------- ---+------------
s | 1 1 S | 1 1 1
m | 1 1 M | 1 1 1
``
For type *m* = __icl_map__,
a key element (*m*`::domain_type`) and an __icl_set__
(*m*`::set_type`) can be a ['*key object*].
For an interval map type *M*,
a key element (*M*`::domain_type`),
an interval (*M*`::interval_type`) and an
['*interval set*], can be ['*key objects*].
[#complexities_contains] Complexity characteristics for function
`bool contains(const T& super, const P& sub)const`
are given by the next tables where
``
n = iterative_size(super);
m = iterative_size(sub); //if P is a container type
``
[table Time Complexity for function contains on element containers
[[`bool contains(const T& super, const P& sub)`\n
`bool within(const P& sub, const T& super)`][__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 functions contains and within on interval containers
[[`bool contains(const T& super, const P& sub)`\n
`bool within(const P& sub, const T& super)`][][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
[[interval_sets] [__itv_set__][__Olgn__] [__Olgn__] [] [] [__Omlgn__] [] ]
[[] [__sep_itv_set__\n__spl_itv_set__][__Olgn__] [__On__ ] [] [] [__Omlgn__] [] ]
[[interval_maps] [__itv_map__][__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Omlgn__] [__Omlgn__] ]
[[] [__spl_itv_map__][__Olgn__] [__On__ ] [__Olgn__] [__On__] [__Omlgn__] [__Omlgn__] ]
]
All overloads of containedness of containers in containers
``
bool contains(const T& super, const P& sub)
bool within(const P& sub, const T& super)
``
are of ['*loglinear*] time: __Omlgn__.
If both containers have same iterative_sizes so that /m = n/
we have the worst case ( __Onlgn__ ).
There is an alternative implementation that has a ['*linear*]
complexity of __Onpm__.
The loglinear implementation has been chosen,
because it can be faster, if the container argument is
small. In this case the loglinear implementation approaches
logarithmic behavior, whereas the linear implementation
stays linear.
['*Back to section . . .*]
[table
[]
[[[link function_synopsis_table ['*Function Synopsis*]]]]
[[[link boost_icl.interface ['*Interface*]] ]]
]
[endsect][/ Containedness]
|
