ceph/src/boost/libs/icl/include/boost/icl/detail/interval_map_algo.hpp

   1 /*-----------------------------------------------------------------------------+
   2 Copyright (c) 2008-2010: Joachim Faulhaber
   3 +------------------------------------------------------------------------------+
   4    Distributed under the Boost Software License, Version 1.0.
   5       (See accompanying file LICENCE.txt or copy at
   6            http://www.boost.org/LICENSE_1_0.txt)
   7 +-----------------------------------------------------------------------------*/
   8 #ifndef BOOST_ICL_INTERVAL_MAP_ALGO_HPP_JOFA_100730
   9 #define BOOST_ICL_INTERVAL_MAP_ALGO_HPP_JOFA_100730
  10
  11 #include <boost/utility/enable_if.hpp>
  12 #include <boost/mpl/not.hpp>
  13
  14 #include <boost/icl/type_traits/is_total.hpp>
  15 #include <boost/icl/type_traits/is_map.hpp>
  16 #include <boost/icl/detail/notate.hpp>
  17 #include <boost/icl/detail/relation_state.hpp>
  18 #include <boost/icl/type_traits/identity_element.hpp>
  19 #include <boost/icl/interval_combining_style.hpp>
  20 #include <boost/icl/detail/element_comparer.hpp>
  21 #include <boost/icl/detail/interval_subset_comparer.hpp>
  22
  23 namespace boost{namespace icl
  24 {
  25
  26
  27 namespace Interval_Map
  28 {
  29 using namespace segmental;
  30
  31 template<class IntervalMapT>
  32 bool is_joinable(const IntervalMapT& container,
  33                  typename IntervalMapT::const_iterator first,
  34                  typename IntervalMapT::const_iterator past)
  35 {
  36     if(first == container.end())
  37         return true;
  38
  39     typename IntervalMapT::const_iterator it_ = first, next_ = first;
  40     ++next_;
  41
  42     const typename IntervalMapT::codomain_type& co_value
  43         = icl::co_value<IntervalMapT>(first);
  44     while(it_ != past)
  45     {
  46         if(icl::co_value<IntervalMapT>(next_) != co_value)
  47             return false;
  48         if(!icl::touches(key_value<IntervalMapT>(it_++),
  49                          key_value<IntervalMapT>(next_++)))
  50             return false;
  51     }
  52
  53     return true;
  54 }
  55
  56 //------------------------------------------------------------------------------
  57 //- Containedness of key objects
  58 //------------------------------------------------------------------------------
  59
  60 //- domain_type ----------------------------------------------------------------
  61 template<class IntervalMapT>
  62 typename enable_if<mpl::not_<is_total<IntervalMapT> >, bool>::type
  63 contains(const IntervalMapT& container,
  64          const typename IntervalMapT::domain_type& key)
  65 {
  66     return container.find(key) != container.end();
  67 }
  68
  69 template<class IntervalMapT>
  70 typename enable_if<is_total<IntervalMapT>, bool>::type
  71 contains(const IntervalMapT&,
  72          const typename IntervalMapT::domain_type&)
  73 {
  74     return true;
  75 }
  76
  77 //- interval_type --------------------------------------------------------------
  78 template<class IntervalMapT>
  79 typename enable_if<mpl::not_<is_total<IntervalMapT> >, bool>::type
  80 contains(const IntervalMapT& container,
  81          const typename IntervalMapT::interval_type& sub_interval)
  82 {
  83     typedef typename IntervalMapT::const_iterator const_iterator;
  84     if(icl::is_empty(sub_interval))
  85         return true;
  86
  87     std::pair<const_iterator, const_iterator> exterior = container.equal_range(sub_interval);
  88     if(exterior.first == exterior.second)
  89         return false;
  90
  91     const_iterator last_overlap = prior(exterior.second);
  92
  93     return
  94           icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
  95       &&  Interval_Set::is_joinable(container, exterior.first, last_overlap);
  96 }
  97
  98 template<class IntervalMapT>
  99 typename enable_if<is_total<IntervalMapT>, bool>::type
 100 contains(const IntervalMapT&,
 101          const typename IntervalMapT::interval_type&)
 102 {
 103     return true;
 104 }
 105
 106 //- set_type -------------------------------------------------------------------
 107 template<class IntervalMapT, class IntervalSetT>
 108 typename enable_if<mpl::and_<mpl::not_<is_total<IntervalMapT> >
 109                             ,is_interval_set<IntervalSetT> >, bool>::type
 110 contains(const IntervalMapT& super_map, const IntervalSetT& sub_set)
 111 {
 112     return Interval_Set::within(sub_set, super_map);
 113 }
 114
 115 template<class IntervalMapT, class IntervalSetT>
 116 typename enable_if<mpl::and_<is_total<IntervalMapT>
 117                             ,is_interval_set<IntervalSetT> >, bool>::type
 118 contains(const IntervalMapT&, const IntervalSetT&)
 119 {
 120     return true;
 121 }
 122
 123
 124 //------------------------------------------------------------------------------
 125 //- Containedness of sub objects
 126 //------------------------------------------------------------------------------
 127
 128 template<class IntervalMapT>
 129 bool contains(const IntervalMapT& container,
 130               const typename IntervalMapT::element_type& key_value_pair)
 131 {
 132     typename IntervalMapT::const_iterator it_ = container.find(key_value_pair.key);
 133     return it_ != container.end() && (*it_).second == key_value_pair.data;
 134 }
 135
 136 template<class IntervalMapT>
 137 bool contains(const IntervalMapT& container,
 138               const typename IntervalMapT::segment_type sub_segment)
 139 {
 140     typedef typename IntervalMapT::const_iterator const_iterator;
 141     typename IntervalMapT::interval_type sub_interval = sub_segment.first;
 142     if(icl::is_empty(sub_interval))
 143         return true;
 144
 145     std::pair<const_iterator, const_iterator> exterior = container.equal_range(sub_interval);
 146     if(exterior.first == exterior.second)
 147         return false;
 148
 149     const_iterator last_overlap = prior(exterior.second);
 150
 151     if(!(sub_segment.second == exterior.first->second) )
 152         return false;
 153
 154     return
 155           icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
 156       &&  Interval_Map::is_joinable(container, exterior.first, last_overlap);
 157 }
 158
 159
 160 template<class IntervalMapT>
 161 bool contains(const IntervalMapT& super, const IntervalMapT& sub)
 162 {
 163     return Interval_Set::within(sub, super);
 164 }
 165
 166 } // namespace Interval_Map
 167
 168 }} // namespace icl boost
 169
 170 #endif
 171