ceph/src/boost/libs/icl/include/boost/icl/interval_map.hpp

   1 /*-----------------------------------------------------------------------------+
   2 Copyright (c) 2008-2012: 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_HPP_JOFA_080705
   9 #define BOOST_ICL_INTERVAL_MAP_HPP_JOFA_080705
  10
  11 #include <boost/assert.hpp>
  12 #include <boost/icl/type_traits/is_map.hpp>
  13 #include <boost/icl/interval_set.hpp>
  14 #include <boost/icl/interval_base_map.hpp>
  15
  16 namespace boost{namespace icl
  17 {
  18
  19 template<class DomainT, class CodomainT, class Traits,
  20          ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section,
  21          ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
  22 class split_interval_map;
  23
  24 /** \brief implements a map as a map of intervals - on insertion
  25     overlapping intervals are split and associated values are combined.*/
  26 template
  27 <
  28     typename DomainT,
  29     typename CodomainT,
  30     class Traits = icl::partial_absorber,
  31     ICL_COMPARE Compare  = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
  32     ICL_COMBINE Combine  = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
  33     ICL_SECTION Section  = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT),
  34     ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
  35     ICL_ALLOC   Alloc    = std::allocator
  36 >
  37 class interval_map:
  38
  39     public interval_base_map<interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>,
  40                              DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
  41 {
  42 public:
  43     typedef Traits traits;
  44     typedef       interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> type;
  45     typedef split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> split_type;
  46     typedef type overloadable_type;
  47     typedef type joint_type;
  48     typedef interval_base_map<type,
  49                               DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> base_type;
  50
  51     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
  52     typedef typename base_type::iterator      iterator;
  53     typedef typename base_type::value_type    value_type;
  54     typedef typename base_type::element_type  element_type;
  55     typedef typename base_type::segment_type  segment_type;
  56     typedef typename base_type::domain_type   domain_type;
  57     typedef typename base_type::codomain_type codomain_type;
  58     typedef typename base_type::domain_mapping_type domain_mapping_type;
  59     typedef typename base_type::interval_mapping_type interval_mapping_type;
  60     typedef typename base_type::ImplMapT ImplMapT;
  61
  62     typedef typename base_type::size_type     size_type;
  63     typedef typename base_type::codomain_combine codomain_combine;
  64
  65     typedef interval_set<DomainT,Compare,Interval,Alloc> interval_set_type;
  66     typedef interval_set_type set_type;
  67     typedef set_type          key_object_type;
  68
  69     enum { fineness = 1 };
  70
  71 public:
  72     //==========================================================================
  73     //= Construct, copy, destruct
  74     //==========================================================================
  75
  76     /// Default constructor for the empty object
  77     interval_map(): base_type() {}
  78
  79     /// Copy constructor
  80     interval_map(const interval_map& src): base_type(src) {}
  81
  82     /// Copy constructor for base_type
  83     template<class SubType>
  84     explicit interval_map
  85         (const interval_base_map<SubType,DomainT,CodomainT,
  86                                  Traits,Compare,Combine,Section,Interval,Alloc>& src)
  87     { this->assign(src); }
  88
  89     explicit interval_map(const domain_mapping_type& base_pair): base_type()
  90     { this->add(base_pair); }
  91
  92     explicit interval_map(const value_type& value_pair): base_type()
  93     { this->add(value_pair); }
  94
  95
  96     /// Assignment from a base interval_map.
  97     template<class SubType>
  98     void assign(const interval_base_map<SubType,DomainT,CodomainT,
  99                                         Traits,Compare,Combine,Section,Interval,Alloc>& src)
 100     {
 101         typedef interval_base_map<SubType,DomainT,CodomainT,
 102                                   Traits,Compare,Combine,Section,Interval,Alloc> base_map_type;
 103         this->clear();
 104         iterator prior_ = this->_map.end();
 105         ICL_const_FORALL(typename base_map_type, it_, src)
 106             prior_ = this->add(prior_, *it_);
 107     }
 108
 109     /// Assignment operator for base type
 110     template<class SubType>
 111     interval_map& operator =
 112         (const interval_base_map<SubType,DomainT,CodomainT,
 113                                  Traits,Compare,Combine,Section,Interval,Alloc>& src)
 114     {
 115         this->assign(src);
 116         return *this;
 117     }
 118
 119 #   ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 120     //==========================================================================
 121     //= Move semantics
 122     //==========================================================================
 123
 124     /// Move constructor
 125     interval_map(interval_map&& src)
 126         : base_type(boost::move(src))
 127     {}
 128
 129     /// Move assignment operator
 130     interval_map& operator = (interval_map src)
 131     {
 132         base_type::operator=(boost::move(src));
 133         return *this;
 134     }
 135
 136     //==========================================================================
 137 #   else
 138
 139     /// Assignment operator
 140     interval_map& operator = (const interval_map& src)
 141     {
 142         base_type::operator=(src);
 143         return *this;
 144     }
 145
 146 #   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 147
 148 private:
 149     // Private functions that shall be accessible by the baseclass:
 150     friend class
 151         interval_base_map <interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>,
 152                                         DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>;
 153
 154     iterator handle_inserted(iterator it_)
 155     {
 156         return segmental::join_neighbours(*this, it_);
 157     }
 158
 159     void handle_inserted(iterator prior_, iterator it_)
 160     {
 161         if(prior_ != this->_map.end() && segmental::joinable(*this, prior_, it_))
 162             segmental::join_on_right(*this, prior_, it_);
 163     }
 164
 165     template<class Combiner>
 166     void handle_left_combined(iterator it_)
 167     {
 168         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
 169             this->_map.erase(it_);
 170         else
 171             segmental::join_left(*this, it_);
 172     }
 173
 174     template<class Combiner>
 175     void handle_combined(iterator it_)
 176     {
 177         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
 178             this->_map.erase(it_);
 179         else
 180             segmental::join_neighbours(*this, it_);
 181     }
 182
 183     template<class Combiner>
 184     void handle_preceeded_combined(iterator prior_, iterator& it_)
 185     {
 186         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
 187         {
 188             this->_map.erase(it_);
 189             it_ = prior_;
 190         }
 191         else // After a new combination (e.g. combiner=max) joining neighbours may be possible
 192             segmental::join_neighbours(*this, it_);
 193     }
 194
 195     template<class Combiner>
 196     void handle_succeeded_combined(iterator it_, iterator next_)
 197     {
 198         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
 199         {
 200             this->_map.erase(it_);
 201             segmental::join_right(*this, next_);
 202         }
 203         else
 204         {
 205             segmental::join_left(*this, it_);
 206             segmental::join_neighbours(*this, next_);
 207         }
 208     }
 209
 210
 211
 212     void handle_reinserted(iterator insertion_)
 213     {
 214         segmental::join_right(*this, insertion_);
 215     }
 216
 217
 218     template<class Combiner>
 219     void gap_insert_at(iterator& it_, iterator prior_,
 220                        const interval_type& end_gap, const codomain_type& co_val)
 221     {
 222         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
 223         {
 224             this->_map.erase(it_);
 225             it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val);
 226             segmental::join_right(*this, it_);
 227         }
 228         else
 229         {
 230             segmental::join_left(*this, it_);
 231             iterator inserted_ = this->template gap_insert<Combiner>(it_, end_gap, co_val);
 232             it_ = segmental::join_neighbours(*this, inserted_);
 233         }
 234     }
 235
 236 } ;
 237
 238
 239 //-----------------------------------------------------------------------------
 240 // type traits
 241 //-----------------------------------------------------------------------------
 242 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
 243 struct is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
 244 {
 245     typedef is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
 246     BOOST_STATIC_CONSTANT(bool, value = true);
 247 };
 248
 249 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
 250 struct has_inverse<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
 251 {
 252     typedef has_inverse<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
 253     BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value));
 254 };
 255
 256
 257 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
 258 struct is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
 259 {
 260     typedef is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
 261     BOOST_STATIC_CONSTANT(bool, value = true);
 262 };
 263
 264 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
 265 struct absorbs_identities<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
 266 {
 267     typedef absorbs_identities<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
 268     BOOST_STATIC_CONSTANT(bool, value = (Traits::absorbs_identities));
 269 };
 270
 271 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
 272 struct is_total<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
 273 {
 274     typedef is_total<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
 275     BOOST_STATIC_CONSTANT(bool, value = (Traits::is_total));
 276 };
 277
 278
 279 //-----------------------------------------------------------------------------
 280 // type representation
 281 //-----------------------------------------------------------------------------
 282 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
 283 struct type_to_string<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
 284 {
 285     static std::string apply()
 286     {
 287         return "itv_map<"+ type_to_string<DomainT>::apply()   + ","
 288                          + type_to_string<CodomainT>::apply() + ","
 289                          + type_to_string<Traits>::apply()    + ">";
 290     }
 291 };
 292
 293 }} // namespace icl boost
 294
 295 #endif
 296
 297