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

Add boost headers

+/*-----------------------------------------------------------------------------+
+Copyright (c) 2008-2009: 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_SUBSET_COMPARER_HPP_JOFA_090827
+#define BOOST_ICL_INTERVAL_SUBSET_COMPARER_HPP_JOFA_090827
+
+#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/type_traits/is_concept_equivalent.hpp>
+#include <boost/icl/type_traits/is_interval_container.hpp>
+#include <boost/icl/type_traits/is_set.hpp>
+#include <boost/icl/concept/interval_set_value.hpp>
+
+namespace boost{namespace icl
+{
+
+#ifdef BOOST_MSVC 
+#pragma warning(push)
+#pragma warning(disable:4127) // conditional expression is constant
+#endif                        
+
+namespace Interval_Set
+{
+
+//------------------------------------------------------------------------------
+template<class LeftT, class RightT>
+struct settic_codomain_compare
+{
+    static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
+    {
+        return inclusion_compare( icl::co_value<LeftT>(left_), 
+                                 icl::co_value<RightT>(right_));
+    }
+};
+
+template<class LeftT, class RightT>
+struct atomic_codomain_compare
+{
+    static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
+    {
+        if(icl::co_value<LeftT>(left_) == icl::co_value<RightT>(right_))
+            return inclusion::equal;
+        else
+            return inclusion::unrelated;
+    }
+};
+
+template<class LeftT, class RightT>
+struct empty_codomain_compare
+{
+    static int apply(typename LeftT::const_iterator&, typename RightT::const_iterator)
+    {
+        return inclusion::equal;
+    }
+};
+
+template<class LeftT, class RightT>
+struct map_codomain_compare
+{
+    static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
+    {
+        using namespace boost::mpl;
+        typedef typename LeftT::codomain_type  LeftCodomainT;
+        typedef typename RightT::codomain_type RightCodomainT;
+
+        return
+            if_<
+                bool_<is_concept_equivalent<is_set,LeftCodomainT,
+                                                   RightCodomainT>::value>,
+                settic_codomain_compare<LeftT,RightT>,
+                atomic_codomain_compare<LeftT,RightT>
+            >
+            ::type::apply(left_, right_);
+    }
+};
+
+
+//------------------------------------------------------------------------------
+template<class LeftT, class RightT>
+class subset_comparer
+{
+private:
+    subset_comparer& operator = (const subset_comparer&);
+public:
+    typedef typename LeftT::const_iterator  LeftIterT;
+    typedef typename RightT::const_iterator RightIterT;
+
+    BOOST_STATIC_CONSTANT(bool, 
+        _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value)); 
+
+
+    subset_comparer(const LeftT&      left,
+                    const RightT&     right,
+                    const LeftIterT&  left_end,
+                    const RightIterT& right_end)
+        : _left(left), _right(right),
+          _left_end(left_end), _right_end(right_end), _result(equal)
+    {}
+
+    enum{nextboth, nextleft, nextright, stop};
+
+    enum
+    {
+        unrelated  = inclusion::unrelated, 
+        subset     = inclusion::subset,     // left is_subset_of   right 
+        superset   = inclusion::superset,   // left is_superset_of right
+        equal      = inclusion::equal       // equal = subset | superset
+    };
+
+    int result()const{ return _result; }
+
+
+    int co_compare(LeftIterT& left, RightIterT& right)
+    {
+        using namespace boost::mpl;
+
+        return  
+            if_<
+                bool_<is_concept_equivalent<is_interval_map,LeftT,RightT>::value>,
+                map_codomain_compare<LeftT,RightT>,
+                empty_codomain_compare<LeftT,RightT>
+            >
+            ::type::apply(left,right);
+    }
+
+    int restrict_result(int state) { return _result &= state; }
+
+    int proceed(LeftIterT& left, RightIterT& right)
+    {
+        if(upper_less(key_value<LeftT>(left), key_value<RightT>(right)))
+        {   // left  ..)  
+            // right .....)
+            _prior_left = left;
+            ++left;
+            return nextleft;
+        }
+        else if(upper_less(key_value<RightT>(right), key_value<LeftT>(left)))
+        {   // left  .....)
+            // right ..)
+            _prior_right = right;
+            ++right;
+            return nextright;
+        }
+        else//key_value<LeftT>(left).upper_equal(key_value<RightT>(right))
+        {   // left  ..)
+            // right ..)
+            ++left; 
+            ++right;    
+            return nextboth;
+        }
+    }
+
+    int next_both(LeftIterT& left, RightIterT& right)
+    {
+        if(left == _left_end && right == _right_end)
+            return stop;
+        else if(left == _left_end)
+        {   // left: ....end    left could be subset
+            // right:....[..
+            restrict_result(subset);
+            return stop;
+        }
+        else if(right == _right_end)
+        {   // left: ....[..    left could be superset
+            // right:....end
+            restrict_result(superset);
+            return stop;
+        }
+        else if(exclusive_less(key_value<LeftT>(left), key_value<RightT>(right)))
+        {   // left: [..) . . .[---)      left could be superset
+            // right:           [..)....  if [---) exists
+            restrict_result(superset);
+            if(unrelated == _result)
+                return stop;
+            else
+            {
+                LeftIterT joint_ = _left.lower_bound(key_value<RightT>(right));
+                if(joint_ == _left.end())
+                {
+                    _result = unrelated;
+                    return stop;
+                }
+                else
+                {
+                    left = joint_;
+                    return nextboth;
+                }
+            }
+        }
+        else if(exclusive_less(key_value<RightT>(right), key_value<LeftT>(left)))
+        {   // left:             [..  left could be subset
+            // right:....) . . .[---) if [---) exists 
+            restrict_result(subset);
+            if(unrelated == _result)
+                return stop;
+            else
+            {
+                RightIterT joint_ = _right.lower_bound(key_value<LeftT>(left));
+                if(joint_ == _right.end())
+                {
+                    _result = unrelated;
+                    return stop;
+                }
+                else
+                {
+                    right = joint_;
+                    return nextboth;
+                }
+            }
+        }
+
+        // left and right have intervals with nonempty intersection:
+        if(_compare_codomain)
+            if(unrelated == restrict_result(co_compare(left,right)))
+                return stop;
+
+        // examine left borders only. Right borders are checked in proceed
+        if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
+        {   // left: ....[...     left could be superset
+            // right:....   [..
+            if(unrelated == restrict_result(superset))
+                return stop;
+        }
+        else if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
+        {   // left: ....   [..   left can be subset
+            // right:....[...
+            if(unrelated == restrict_result(subset))
+                return stop;
+        }
+        //else key_value<LeftT>(right).lower_equal(key_value<RightT>(left))
+            // left: ....[..   both can be equal
+            // right:....[..
+            // nothing to do: proceed
+
+        return proceed(left, right);
+    }
+
+    int next_left(LeftIterT& left, RightIterT& right)
+    {
+        if(left == _left_end)
+        {   // left: ..)end    left could be subset
+            // right:......)
+            restrict_result(subset);
+            return stop;            
+        }
+        else if(!touches(key_value<LeftT>(_prior_left), key_value<LeftT>(left)))
+        {   // left: ..)   [..
+            // right:.........)
+            if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
+            {   //   ..)   [..   left could be subset
+                //   ..........)
+                if(unrelated == restrict_result(subset))
+                    return stop;            
+            }
+            //else   ..)   [...
+            //          [..
+            if(_compare_codomain && intersects(key_value<LeftT>(left),key_value<RightT>(right)) )
+                if(unrelated == restrict_result(co_compare(left,right)))
+                    return stop;
+        }
+        else
+        {   // left: ..)[..  left could be subset
+            // right:.......)
+            if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
+                if(unrelated == restrict_result(co_compare(left,right)))
+                    return stop;
+        }
+
+        return proceed(left, right);
+    }
+
+
+    int next_right(LeftIterT& left, RightIterT& right)
+    {
+        if(right == _right_end)
+        {   // left: ......)    left could be superset
+            // right:..)end
+            restrict_result(superset);
+            return stop;            
+        }
+        else if(!touches(key_value<RightT>(_prior_right), key_value<RightT>(right)))
+        {   // left: .........)
+            // right:..)   [..
+            if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
+            {   //       [....)  left could be superset
+                //   ..)   [..
+                if(unrelated == restrict_result(superset))
+                    return stop;            
+            }
+            //else       [....)
+            //   ..)   [..
+            if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
+                if(unrelated == restrict_result(co_compare(left,right)))
+                    return stop;
+        }
+        else
+        {
+            if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
+                if(unrelated == restrict_result(co_compare(left,right)))
+                    return stop;
+        }
+
+        return proceed(left, right);
+    }
+
+private:
+    const LeftT&  _left;
+    const RightT& _right;
+    LeftIterT     _left_end;
+    RightIterT    _right_end;
+    LeftIterT     _prior_left;
+    RightIterT    _prior_right;
+    int           _result;
+};
+
+
+
+
+
+//------------------------------------------------------------------------------
+// Subset/superset comparison on ranges of two interval container 
+//------------------------------------------------------------------------------
+template<class LeftT, class RightT>
+int subset_compare
+(
+    const LeftT& left,   //sub
+    const RightT& right, //super
+    typename LeftT::const_iterator  left_begin,   
+    typename LeftT::const_iterator  left_end,
+    typename RightT::const_iterator right_begin, 
+    typename RightT::const_iterator right_end
+)
+{
+    typedef subset_comparer<LeftT,RightT> Step;
+    Step step(left, right, left_end, right_end);
+
+    typename LeftT::const_iterator  left_  = left_begin;
+    typename RightT::const_iterator right_ = right_begin;
+
+    int state = Step::nextboth;
+    while(state != Step::stop)
+    {
+        switch(state){
+        case Step::nextboth:    state = step.next_both(left_, right_);  break;
+        case Step::nextleft:    state = step.next_left(left_, right_);  break;
+        case Step::nextright:   state = step.next_right(left_, right_); break;
+        }
+    }
+    return step.result();
+}
+
+
+} // namespace Interval_Set
+    
+#ifdef BOOST_MSVC
+#pragma warning(pop)
+#endif
+
+}} // namespace icl boost
+
+#endif 
+