ceph/src/boost/libs/icl/include/boost/icl/concept/interval_associator_base.hpp

   1 /*-----------------------------------------------------------------------------+
   2 Copyright (c) 2011-2011: 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_CONCEPT_INTERVAL_ASSOCIATOR_BASE_HPP_JOFA_110301
   9 #define BOOST_ICL_CONCEPT_INTERVAL_ASSOCIATOR_BASE_HPP_JOFA_110301
  10
  11 #include <boost/icl/type_traits/domain_type_of.hpp>
  12 #include <boost/icl/type_traits/interval_type_of.hpp>
  13 #include <boost/icl/type_traits/is_combinable.hpp>
  14 #include <boost/icl/concept/set_value.hpp>
  15 #include <boost/icl/concept/map_value.hpp>
  16 #include <boost/icl/concept/interval.hpp>
  17
  18 namespace boost{ namespace icl
  19 {
  20
  21 //==============================================================================
  22 //= Selection<IntervalSet|IntervalMap>
  23 //==============================================================================
  24 template<class Type> inline
  25 typename enable_if<mpl::and_< is_interval_container<Type>
  26                             , is_discrete<typename domain_type_of<Type>::type>
  27                             >
  28                    , typename Type::const_iterator>::type
  29 find(const Type& object, const typename domain_type_of<Type>::type& key_val)
  30 {
  31     //CL typedef typename Type::const_iterator const_iterator;
  32     typedef typename Type::interval_type  interval_type;
  33     return object.find(icl::detail::unit_trail<interval_type>(key_val));
  34 }
  35
  36 template<class Type> inline
  37 typename enable_if<mpl::and_< is_interval_container<Type>
  38                             , is_continuous<typename domain_type_of<Type>::type>
  39                             , has_dynamic_bounds<typename interval_type_of<Type>::type>
  40                             >
  41                    , typename Type::const_iterator>::type
  42 find(const Type& object, const typename domain_type_of<Type>::type& key_val)
  43 {
  44     //CL typedef typename Type::const_iterator const_iterator;
  45     typedef typename Type::interval_type  interval_type;
  46     return object.find(icl::singleton<interval_type>(key_val));
  47 }
  48
  49 template<class Type> inline
  50 typename enable_if<mpl::and_< is_interval_container<Type>
  51                             , is_continuous<typename domain_type_of<Type>::type>
  52                             , is_static_right_open<typename interval_type_of<Type>::type>
  53                             , boost::detail::is_incrementable<typename domain_type_of<Type>::type>
  54                             >
  55                    , typename Type::const_iterator>::type
  56 find(const Type& object, const typename domain_type_of<Type>::type& key_val)
  57 {
  58     typedef typename Type::const_iterator const_iterator;
  59     typedef typename Type::interval_type  interval_type;
  60     const_iterator first_collision = object.lower_bound(icl::detail::unit_trail<interval_type>(key_val));
  61     // A part of the unit_trail(key_value)-interval may be found in the container, that
  62     // does not contain key_value. Therefore we have to check for its existence:
  63     return (  first_collision == object.end()
  64            || icl::contains(key_value<Type>(first_collision), key_val) )
  65             ? first_collision
  66             : object.end();
  67 }
  68
  69 template<class Type> inline
  70 typename enable_if<mpl::and_< is_interval_container<Type>
  71                             , is_continuous<typename domain_type_of<Type>::type>
  72                             , is_static_left_open<typename interval_type_of<Type>::type>
  73                             , boost::detail::is_incrementable<typename domain_type_of<Type>::type>
  74                             >
  75                    , typename Type::const_iterator>::type
  76 find(const Type& object, const typename domain_type_of<Type>::type& key_val)
  77 {
  78     typedef typename Type::const_iterator const_iterator;
  79     typedef typename Type::interval_type  interval_type;
  80     const_iterator last_collision = object.upper_bound(icl::detail::unit_trail<interval_type>(key_val));
  81     if(last_collision != object.begin())
  82         --last_collision;
  83     // A part of the unit_trail(key_value)-interval may be found in the container, that
  84     // does not contain key_value. Therefore we have to check for its existence:
  85     return (  last_collision == object.end()
  86            || icl::contains(key_value<Type>(last_collision), key_val) )
  87             ? last_collision
  88             : object.end();
  89 }
  90
  91 // NOTE: find(object, key) won't compile if key is of continuous type that does
  92 // not implement in(de)crementation (e.g. std::string).
  93
  94 template<class Type> inline
  95 typename enable_if< is_interval_container<Type>
  96                   , typename Type::const_iterator>::type
  97 find(const Type& object, const typename interval_type_of<Type>::type& inter_val)
  98 {
  99     return object.find(inter_val);
 100 }
 101
 102 //==============================================================================
 103 //= Morphisms
 104 //==============================================================================
 105 template<class Type>
 106 typename enable_if<is_interval_container<Type>, Type>::type&
 107 join(Type& object)
 108 {
 109     typedef typename Type::interval_type interval_type;
 110     typedef typename Type::iterator      iterator;
 111
 112     iterator it_ = object.begin();
 113     if(it_ == object.end())
 114         return object;
 115
 116     iterator next_ = it_; next_++;
 117
 118     while(next_ != object.end())
 119     {
 120         if( segmental::is_joinable<Type>(it_, next_) )
 121         {
 122             iterator fst_mem = it_;  // hold the first member
 123
 124             // Go on while touching members are found
 125             it_++; next_++;
 126             while(     next_ != object.end()
 127                     && segmental::is_joinable<Type>(it_, next_) )
 128             { it_++; next_++; }
 129
 130             // finally we arrive at the end of a sequence of joinable intervals
 131             // and it points to the last member of that sequence
 132             const_cast<interval_type&>(key_value<Type>(it_))
 133                 = hull(key_value<Type>(it_), key_value<Type>(fst_mem));
 134             object.erase(fst_mem, it_);
 135
 136             it_++; next_=it_;
 137             if(next_!=object.end())
 138                 next_++;
 139         }
 140         else { it_++; next_++; }
 141     }
 142     return object;
 143 }
 144
 145 }} // namespace boost icl
 146
 147 #endif
 148
 149