123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134 |
- [/
- 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]
|