| /*-----------------------------------------------------------------------------+ |
| Copyright (c) 2008-2010: Joachim Faulhaber |
| +------------------------------------------------------------------------------+ |
| Distributed under the Boost Software License, Version 1.0. |
| (See accompanying file LICENCE.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| +-----------------------------------------------------------------------------*/ |
| #ifndef BOOST_ICL_INTERVAL_MAP_ALGO_HPP_JOFA_100730 |
| #define BOOST_ICL_INTERVAL_MAP_ALGO_HPP_JOFA_100730 |
| |
| #include <boost/utility/enable_if.hpp> |
| #include <boost/mpl/not.hpp> |
| |
| #include <boost/icl/type_traits/is_total.hpp> |
| #include <boost/icl/type_traits/is_map.hpp> |
| #include <boost/icl/detail/notate.hpp> |
| #include <boost/icl/detail/relation_state.hpp> |
| #include <boost/icl/type_traits/identity_element.hpp> |
| #include <boost/icl/interval_combining_style.hpp> |
| #include <boost/icl/detail/element_comparer.hpp> |
| #include <boost/icl/detail/interval_subset_comparer.hpp> |
| |
| namespace boost{namespace icl |
| { |
| |
| |
| namespace Interval_Map |
| { |
| using namespace segmental; |
| |
| template<class IntervalMapT> |
| bool is_joinable(const IntervalMapT& container, |
| typename IntervalMapT::const_iterator first, |
| typename IntervalMapT::const_iterator past) |
| { |
| if(first == container.end()) |
| return true; |
| |
| typename IntervalMapT::const_iterator it_ = first, next_ = first; |
| ++next_; |
| |
| const typename IntervalMapT::codomain_type& co_value |
| = icl::co_value<IntervalMapT>(first); |
| while(it_ != past) |
| { |
| if(icl::co_value<IntervalMapT>(next_) != co_value) |
| return false; |
| if(!icl::touches(key_value<IntervalMapT>(it_++), |
| key_value<IntervalMapT>(next_++))) |
| return false; |
| } |
| |
| return true; |
| } |
| |
| //------------------------------------------------------------------------------ |
| //- Containedness of key objects |
| //------------------------------------------------------------------------------ |
| |
| //- domain_type ---------------------------------------------------------------- |
| template<class IntervalMapT> |
| typename enable_if<mpl::not_<is_total<IntervalMapT> >, bool>::type |
| contains(const IntervalMapT& container, |
| const typename IntervalMapT::domain_type& key) |
| { |
| return container.find(key) != container.end(); |
| } |
| |
| template<class IntervalMapT> |
| typename enable_if<is_total<IntervalMapT>, bool>::type |
| contains(const IntervalMapT&, |
| const typename IntervalMapT::domain_type&) |
| { |
| return true; |
| } |
| |
| //- interval_type -------------------------------------------------------------- |
| template<class IntervalMapT> |
| typename enable_if<mpl::not_<is_total<IntervalMapT> >, bool>::type |
| contains(const IntervalMapT& container, |
| const typename IntervalMapT::interval_type& sub_interval) |
| { |
| typedef typename IntervalMapT::const_iterator const_iterator; |
| if(icl::is_empty(sub_interval)) |
| return true; |
| |
| std::pair<const_iterator, const_iterator> exterior = container.equal_range(sub_interval); |
| if(exterior.first == exterior.second) |
| return false; |
| |
| const_iterator last_overlap = prior(exterior.second); |
| |
| return |
| icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval) |
| && Interval_Set::is_joinable(container, exterior.first, last_overlap); |
| } |
| |
| template<class IntervalMapT> |
| typename enable_if<is_total<IntervalMapT>, bool>::type |
| contains(const IntervalMapT&, |
| const typename IntervalMapT::interval_type&) |
| { |
| return true; |
| } |
| |
| //- set_type ------------------------------------------------------------------- |
| template<class IntervalMapT, class IntervalSetT> |
| typename enable_if<mpl::and_<mpl::not_<is_total<IntervalMapT> > |
| ,is_interval_set<IntervalSetT> >, bool>::type |
| contains(const IntervalMapT& super_map, const IntervalSetT& sub_set) |
| { |
| return Interval_Set::within(sub_set, super_map); |
| } |
| |
| template<class IntervalMapT, class IntervalSetT> |
| typename enable_if<mpl::and_<is_total<IntervalMapT> |
| ,is_interval_set<IntervalSetT> >, bool>::type |
| contains(const IntervalMapT&, const IntervalSetT&) |
| { |
| return true; |
| } |
| |
| |
| //------------------------------------------------------------------------------ |
| //- Containedness of sub objects |
| //------------------------------------------------------------------------------ |
| |
| template<class IntervalMapT> |
| bool contains(const IntervalMapT& container, |
| const typename IntervalMapT::element_type& key_value_pair) |
| { |
| typename IntervalMapT::const_iterator it_ = container.find(key_value_pair.key); |
| return it_ != container.end() && (*it_).second == key_value_pair.data; |
| } |
| |
| template<class IntervalMapT> |
| bool contains(const IntervalMapT& container, |
| const typename IntervalMapT::segment_type sub_segment) |
| { |
| typedef typename IntervalMapT::const_iterator const_iterator; |
| typename IntervalMapT::interval_type sub_interval = sub_segment.first; |
| if(icl::is_empty(sub_interval)) |
| return true; |
| |
| std::pair<const_iterator, const_iterator> exterior = container.equal_range(sub_interval); |
| if(exterior.first == exterior.second) |
| return false; |
| |
| const_iterator last_overlap = prior(exterior.second); |
| |
| if(!(sub_segment.second == exterior.first->second) ) |
| return false; |
| |
| return |
| icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval) |
| && Interval_Map::is_joinable(container, exterior.first, last_overlap); |
| } |
| |
| |
| template<class IntervalMapT> |
| bool contains(const IntervalMapT& super, const IntervalMapT& sub) |
| { |
| return Interval_Set::within(sub, super); |
| } |
| |
| } // namespace Interval_Map |
| |
| }} // namespace icl boost |
| |
| #endif |
| |