135 lines
5.4 KiB
Plaintext
135 lines
5.4 KiB
Plaintext
[/
|
|
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]
|
|
|
|
|