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