ceph/src/boost/libs/icl/doc/functions_containedness.qbk

   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