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