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
21This group of functions refers to ['*contain*]edness which should
22be fundamental to ['*contain*]ers. The function `contains`
23is overloaded. It covers different kinds of containedness:
24Containedness 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
39bool contains(const T& super, const P& sub)
40bool   within(const P& sub, const T& super)
41
42element containers:   interval containers:
43T\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
49The overloads of `bool contains(const T& super, const P& sup)`
50cover various kinds
51of containedness. We can group them into a part (1) that checks
52if an element, a segment or a container /of same kinds/ is contained in
53an element or interval container
54
55``
56// (1) containedness of elements, segments or containers of same kind
57T\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
63and 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.
68T\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
74For type *m* = __icl_map__,
75a key element (*m*`::domain_type`) and an __icl_set__
76(*m*`::set_type`) can be a ['*key object*].
77
78For an interval map type *M*,
79a key element (*M*`::domain_type`),
80an 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`
85are given by the next tables where
86``
87n = iterative_size(super);
88m = 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
108All overloads of containedness of containers in containers
109``
110bool contains(const T& super, const P& sub)
111bool   within(const P& sub, const T& super)
112``
113are of ['*loglinear*] time: __Omlgn__.
114If both containers have same iterative_sizes so that /m = n/
115we have the worst case ( __Onlgn__ ).
116There is an alternative implementation that has a ['*linear*]
117complexity of __Onpm__.
118The loglinear implementation has been chosen,
119because it can be faster, if the container argument is
120small. In this case the loglinear implementation approaches
121logarithmic behavior, whereas the linear implementation
122stays 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
135