comparison DEPENDENCIES/generic/include/boost/icl/detail/interval_map_algo.hpp @ 16:2665513ce2d3

Add boost headers

+/*-----------------------------------------------------------------------------+
+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 
+