icl/detail/interval_map_algo.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2008-2010: Joachim Faulhaber
0003 +------------------------------------------------------------------------------+
0004    Distributed under the Boost Software License, Version 1.0.
0005       (See accompanying file LICENCE.txt or copy at
0006            http://www.boost.org/LICENSE_1_0.txt)
0007 +-----------------------------------------------------------------------------*/
0008 #ifndef BOOST_ICL_INTERVAL_MAP_ALGO_HPP_JOFA_100730
0009 #define BOOST_ICL_INTERVAL_MAP_ALGO_HPP_JOFA_100730
0010
0011 #include <boost/utility/enable_if.hpp>
0012 #include <boost/mpl/not.hpp>
0013
0014 #include <boost/icl/type_traits/is_total.hpp>
0015 #include <boost/icl/type_traits/is_map.hpp>
0016 #include <boost/icl/detail/notate.hpp>
0017 #include <boost/icl/detail/relation_state.hpp>
0018 #include <boost/icl/type_traits/identity_element.hpp>
0019 #include <boost/icl/interval_combining_style.hpp>
0020 #include <boost/icl/detail/element_comparer.hpp>
0021 #include <boost/icl/detail/interval_subset_comparer.hpp>
0022
0023 namespace boost{namespace icl
0024 {
0025
0026
0027 namespace Interval_Map
0028 {
0029 using namespace segmental;
0030
0031 template<class IntervalMapT>
0032 bool is_joinable(const IntervalMapT& container,
0033                  typename IntervalMapT::const_iterator first,
0034                  typename IntervalMapT::const_iterator past)
0035 {
0036     if(first == container.end())
0037         return true;
0038
0039     typename IntervalMapT::const_iterator it_ = first, next_ = first;
0040     ++next_;
0041
0042     const typename IntervalMapT::codomain_type& co_value
0043         = icl::co_value<IntervalMapT>(first);
0044     while(it_ != past)
0045     {
0046         if(icl::co_value<IntervalMapT>(next_) != co_value)
0047             return false;
0048         if(!icl::touches(key_value<IntervalMapT>(it_++),
0049                          key_value<IntervalMapT>(next_++)))
0050             return false;
0051     }
0052
0053     return true;
0054 }
0055
0056 //------------------------------------------------------------------------------
0057 //- Containedness of key objects
0058 //------------------------------------------------------------------------------
0059
0060 //- domain_type ----------------------------------------------------------------
0061 template<class IntervalMapT>
0062 typename enable_if<mpl::not_<is_total<IntervalMapT> >, bool>::type
0063 contains(const IntervalMapT& container,
0064          const typename IntervalMapT::domain_type& key)
0065 {
0066     return container.find(key) != container.end();
0067 }
0068
0069 template<class IntervalMapT>
0070 typename enable_if<is_total<IntervalMapT>, bool>::type
0071 contains(const IntervalMapT&,
0072          const typename IntervalMapT::domain_type&)
0073 {
0074     return true;
0075 }
0076
0077 //- interval_type --------------------------------------------------------------
0078 template<class IntervalMapT>
0079 typename enable_if<mpl::not_<is_total<IntervalMapT> >, bool>::type
0080 contains(const IntervalMapT& container,
0081          const typename IntervalMapT::interval_type& sub_interval)
0082 {
0083     typedef typename IntervalMapT::const_iterator const_iterator;
0084     if(icl::is_empty(sub_interval))
0085         return true;
0086
0087     std::pair<const_iterator, const_iterator> exterior = container.equal_range(sub_interval);
0088     if(exterior.first == exterior.second)
0089         return false;
0090
0091     const_iterator last_overlap = prior(exterior.second);
0092
0093     return
0094           icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
0095       &&  Interval_Set::is_joinable(container, exterior.first, last_overlap);
0096 }
0097
0098 template<class IntervalMapT>
0099 typename enable_if<is_total<IntervalMapT>, bool>::type
0100 contains(const IntervalMapT&,
0101          const typename IntervalMapT::interval_type&)
0102 {
0103     return true;
0104 }
0105
0106 //- set_type -------------------------------------------------------------------
0107 template<class IntervalMapT, class IntervalSetT>
0108 typename enable_if<mpl::and_<mpl::not_<is_total<IntervalMapT> >
0109                             ,is_interval_set<IntervalSetT> >, bool>::type
0110 contains(const IntervalMapT& super_map, const IntervalSetT& sub_set)
0111 {
0112     return Interval_Set::within(sub_set, super_map);
0113 }
0114
0115 template<class IntervalMapT, class IntervalSetT>
0116 typename enable_if<mpl::and_<is_total<IntervalMapT>
0117                             ,is_interval_set<IntervalSetT> >, bool>::type
0118 contains(const IntervalMapT&, const IntervalSetT&)
0119 {
0120     return true;
0121 }
0122
0123
0124 //------------------------------------------------------------------------------
0125 //- Containedness of sub objects
0126 //------------------------------------------------------------------------------
0127
0128 template<class IntervalMapT>
0129 bool contains(const IntervalMapT& container,
0130               const typename IntervalMapT::element_type& key_value_pair)
0131 {
0132     typename IntervalMapT::const_iterator it_ = container.find(key_value_pair.key);
0133     return it_ != container.end() && (*it_).second == key_value_pair.data;
0134 }
0135
0136 template<class IntervalMapT>
0137 bool contains(const IntervalMapT& container,
0138               const typename IntervalMapT::segment_type sub_segment)
0139 {
0140     typedef typename IntervalMapT::const_iterator const_iterator;
0141     typename IntervalMapT::interval_type sub_interval = sub_segment.first;
0142     if(icl::is_empty(sub_interval))
0143         return true;
0144
0145     std::pair<const_iterator, const_iterator> exterior = container.equal_range(sub_interval);
0146     if(exterior.first == exterior.second)
0147         return false;
0148
0149     const_iterator last_overlap = prior(exterior.second);
0150
0151     if(!(sub_segment.second == exterior.first->second) )
0152         return false;
0153
0154     return
0155           icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
0156       &&  Interval_Map::is_joinable(container, exterior.first, last_overlap);
0157 }
0158
0159
0160 template<class IntervalMapT>
0161 bool contains(const IntervalMapT& super, const IntervalMapT& sub)
0162 {
0163     return Interval_Set::within(sub, super);
0164 }
0165
0166 } // namespace Interval_Map
0167
0168 }} // namespace icl boost
0169
0170 #endif
0171