icl/detail/subset_comparer.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2008-2009: Joachim Faulhaber
0003 +------------------------------------------------------------------------------+
0004    Distributed under the Boost Software License, Version 1.0.
0005       (See accompanying file LICENCE.txt or copy at
0006            http://www.boost.org/LICENSE_1_0.txt)
0007 +-----------------------------------------------------------------------------*/
0008 #ifndef BOOST_ICL_SUBSET_COMPARER_HPP_JOFA_090202
0009 #define BOOST_ICL_SUBSET_COMPARER_HPP_JOFA_090202
0010
0011 #include <boost/mpl/and.hpp>
0012 #include <boost/icl/type_traits/is_map.hpp>
0013 #include <boost/icl/detail/notate.hpp>
0014 #include <boost/icl/detail/relation_state.hpp>
0015 #include <boost/icl/type_traits/identity_element.hpp>
0016 #include <boost/icl/type_traits/codomain_type_of.hpp>
0017 #include <boost/icl/type_traits/is_concept_equivalent.hpp>
0018 #include <boost/icl/type_traits/is_element_container.hpp>
0019 #include <boost/icl/concept/interval_set_value.hpp>
0020 #include <boost/icl/concept/map_value.hpp>
0021
0022 namespace boost{namespace icl
0023 {
0024
0025 #ifdef BOOST_MSVC
0026 #pragma warning(push)
0027 #pragma warning(disable:4127) // conditional expression is constant
0028 #endif
0029
0030 namespace Set
0031 {
0032
0033 //------------------------------------------------------------------------------
0034 template<class LeftT, class RightT>
0035 struct settic_codomain_compare
0036 {
0037     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
0038     {
0039         return inclusion_compare( co_value<LeftT>(left_),
0040                                  co_value<RightT>(right_));
0041     }
0042 };
0043
0044 template<class LeftT, class RightT>
0045 struct atomic_codomain_compare
0046 {
0047     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
0048     {
0049         if(co_value<LeftT>(left_) == co_value<RightT>(right_))
0050             return inclusion::equal;
0051         else
0052             return inclusion::unrelated;
0053     }
0054 };
0055
0056 template<class LeftT, class RightT>
0057 struct empty_codomain_compare
0058 {
0059     static int apply(typename LeftT::const_iterator&, typename RightT::const_iterator&)
0060     {
0061         return inclusion::equal;
0062     }
0063 };
0064
0065 template<class LeftT, class RightT>
0066 struct map_codomain_compare
0067 {
0068     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
0069     {
0070         using namespace boost::mpl;
0071         typedef typename LeftT::codomain_type  LeftCodomainT;
0072         typedef typename RightT::codomain_type RightCodomainT;
0073
0074         return
0075             if_<
0076                 bool_<is_concept_equivalent<is_set,LeftCodomainT,
0077                                                    RightCodomainT>::value>,
0078                 settic_codomain_compare<LeftT,RightT>,
0079                 atomic_codomain_compare<LeftT,RightT>
0080             >
0081             ::type::apply(left_, right_);
0082     }
0083 };
0084
0085
0086 //------------------------------------------------------------------------------
0087 template<class LeftT, class RightT>
0088 class subset_comparer
0089 {
0090 private:
0091     subset_comparer& operator = (const subset_comparer&);
0092 public:
0093     typedef typename LeftT::const_iterator  LeftIterT;
0094     typedef typename RightT::const_iterator RightIterT;
0095
0096     BOOST_STATIC_CONSTANT(bool,
0097         _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value));
0098
0099     subset_comparer(const LeftT&      left,
0100                     const RightT&     right,
0101                     const LeftIterT&  left_end,
0102                     const RightIterT& right_end)
0103         : _left(left), _right(right),
0104           _left_end(left_end), _right_end(right_end), _result(equal)
0105     {}
0106
0107     enum{nextboth, stop};
0108
0109     enum
0110     {
0111         unrelated  = inclusion::unrelated,
0112         subset     = inclusion::subset,     // left is_subset_of   right
0113         superset   = inclusion::superset,   // left is_superset_of right
0114         equal      = inclusion::equal       // equal = subset | superset
0115     };
0116
0117     int result()const{ return _result; }
0118
0119     int co_compare(LeftIterT& left, RightIterT& right)
0120     {
0121         using namespace boost::mpl;
0122         //CL typedef typename codomain_type_of<LeftT>::type  LeftCodomainT;
0123         //CL typedef typename codomain_type_of<RightT>::type RightCodomainT;
0124
0125         return
0126             if_<
0127                 bool_<is_concept_equivalent<is_element_map,LeftT,RightT>::value>,
0128                 map_codomain_compare<LeftT,RightT>,
0129                 empty_codomain_compare<LeftT,RightT>
0130             >
0131             ::type::apply(left,right);
0132     }
0133
0134     int restrict_result(int state) { return _result &= state; }
0135
0136     int next_both(LeftIterT& left, RightIterT& right)
0137     {
0138         if(left == _left_end && right == _right_end)
0139             return stop;
0140         else if(left == _left_end)
0141         {
0142             restrict_result(subset);
0143             return stop;
0144         }
0145         else if(right == _right_end)
0146         {
0147             restrict_result(superset);
0148             return stop;
0149         }
0150         else if(typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(right)))
0151         {   // left:  *left . . *joint_     left could be superset
0152             // right:           *right ...  if joint_ exists
0153             restrict_result(superset);
0154             if(unrelated == _result)
0155                 return stop;
0156             else
0157             {
0158                 LeftIterT joint_ = _left.lower_bound(key_value<RightT>(right));
0159                 if(    joint_ == _left.end()
0160                     || typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(joint_)))
0161                 {
0162                     _result = unrelated;
0163                     return stop;
0164                 }
0165                 else
0166                     left = joint_;
0167             }
0168         }
0169         else if(typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(left)))
0170         {   // left:             *left   left could be subset
0171             // right:*right . . .*joint_ if *joint_ exists
0172             restrict_result(subset);
0173             if(unrelated == _result)
0174                 return stop;
0175             else
0176             {
0177                 RightIterT joint_ = _right.lower_bound(key_value<LeftT>(left));
0178                 if(    joint_ == _right.end()
0179                     || typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(joint_)))
0180                 {
0181                     _result = unrelated;
0182                     return stop;
0183                 }
0184                 else
0185                     right = joint_;
0186             }
0187         }
0188
0189         // left =key= right
0190         if(_compare_codomain)
0191             if(unrelated == restrict_result(co_compare(left,right)))
0192                 return stop;
0193
0194         ++left;
0195         ++right;
0196         return nextboth;
0197     }
0198
0199 private:
0200     const LeftT&  _left;
0201     const RightT& _right;
0202     LeftIterT     _left_end;
0203     RightIterT    _right_end;
0204     int           _result;
0205 };
0206
0207
0208
0209
0210
0211 //------------------------------------------------------------------------------
0212 // Subset/superset comparison on ranges of two interval container
0213 //------------------------------------------------------------------------------
0214 template<class LeftT, class RightT>
0215 int subset_compare
0216 (
0217     const LeftT& left,   //sub
0218     const RightT& right, //super
0219     typename LeftT::const_iterator  left_begin,
0220     typename LeftT::const_iterator  left_end,
0221     typename RightT::const_iterator right_begin,
0222     typename RightT::const_iterator right_end
0223 )
0224 {
0225     typedef subset_comparer<LeftT,RightT> Step;
0226     Step step(left, right, left_end, right_end);
0227
0228     typename LeftT::const_iterator  left_  = left_begin;
0229     typename RightT::const_iterator right_ = right_begin;
0230
0231     int state = Step::nextboth;
0232     while(state != Step::stop)
0233         state = step.next_both(left_, right_);
0234
0235     return step.result();
0236 }
0237
0238 template<class LeftT, class RightT>
0239 int subset_compare(const LeftT& left, const RightT& right)
0240 {
0241     return subset_compare
0242         (
0243             left, right,
0244             left.begin(), left.end(),
0245             right.begin(), right.end()
0246         );
0247 }
0248
0249
0250 } // namespace Set
0251
0252 #ifdef BOOST_MSVC
0253 #pragma warning(pop)
0254 #endif
0255
0256 }} // namespace icl boost
0257
0258 #endif
0259