comparison DEPENDENCIES/generic/include/boost/icl/detail/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_SUBSET_COMPARER_HPP_JOFA_090202
+#define BOOST_ICL_SUBSET_COMPARER_HPP_JOFA_090202
+
+#include <boost/mpl/and.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/type_traits/codomain_type_of.hpp>
+#include <boost/icl/type_traits/is_concept_equivalent.hpp>
+#include <boost/icl/type_traits/is_element_container.hpp>
+#include <boost/icl/concept/interval_set_value.hpp>
+#include <boost/icl/concept/map_value.hpp>
+
+namespace boost{namespace icl
+{
+
+#ifdef BOOST_MSVC 
+#pragma warning(push)
+#pragma warning(disable:4127) // conditional expression is constant
+#endif                        
+
+namespace 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( co_value<LeftT>(left_), 
+                                 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(co_value<LeftT>(left_) == 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, 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;
+        typedef typename codomain_type_of<LeftT>::type  LeftCodomainT;
+        typedef typename codomain_type_of<RightT>::type RightCodomainT;
+
+        return  
+            if_<
+                bool_<is_concept_equivalent<is_element_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 next_both(LeftIterT& left, RightIterT& right)
+    {
+        if(left == _left_end && right == _right_end)
+            return stop;
+        else if(left == _left_end)
+        {
+            restrict_result(subset);
+            return stop;
+        }
+        else if(right == _right_end)
+        {
+            restrict_result(superset);
+            return stop;
+        }
+        else if(typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(right)))
+        {   // left:  *left . . *joint_     left could be superset
+            // right:           *right ...  if joint_ exists
+            restrict_result(superset);
+            if(unrelated == _result)
+                return stop;
+            else
+            {
+                LeftIterT joint_ = _left.lower_bound(key_value<RightT>(right));
+                if(    joint_ == _left.end() 
+                    || typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(joint_)))
+                {
+                    _result = unrelated;
+                    return stop;
+                }
+                else
+                    left = joint_;
+            }
+        }
+        else if(typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(left)))
+        {   // left:             *left   left could be subset
+            // right:*right . . .*joint_ if *joint_ exists 
+            restrict_result(subset);
+            if(unrelated == _result)
+                return stop;
+            else
+            {
+                RightIterT joint_ = _right.lower_bound(key_value<LeftT>(left));
+                if(    joint_ == _right.end()
+                    || typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(joint_)))
+                {
+                    _result = unrelated;
+                    return stop;
+                }
+                else
+                    right = joint_;
+            }
+        }
+
+        // left =key= right 
+        if(_compare_codomain)
+            if(unrelated == restrict_result(co_compare(left,right)))
+                return stop;
+
+        ++left;
+        ++right;
+        return nextboth;
+    }
+
+private:
+    const LeftT&  _left;
+    const RightT& _right;
+    LeftIterT     _left_end;
+    RightIterT    _right_end;
+    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)
+        state = step.next_both(left_, right_);
+
+    return step.result();
+}
+
+template<class LeftT, class RightT>
+int subset_compare(const LeftT& left, const RightT& right)
+{
+    return subset_compare
+        (
+            left, right,
+            left.begin(), left.end(),
+            right.begin(), right.end()
+        );
+}
+
+
+} // namespace Set
+    
+#ifdef BOOST_MSVC
+#pragma warning(pop)
+#endif
+
+}} // namespace icl boost
+
+#endif 
+