git.sesse.net Git - casparcg/blob - dependencies/boost/boost/icl/detail/subset_comparer.hpp

   1 /*-----------------------------------------------------------------------------+
   2 Copyright (c) 2008-2009: Joachim Faulhaber
   3 +------------------------------------------------------------------------------+
   4    Distributed under the Boost Software License, Version 1.0.
   5       (See accompanying file LICENCE.txt or copy at
   6            http://www.boost.org/LICENSE_1_0.txt)
   7 +-----------------------------------------------------------------------------*/
   8 #ifndef BOOST_ICL_SUBSET_COMPARER_HPP_JOFA_090202
   9 #define BOOST_ICL_SUBSET_COMPARER_HPP_JOFA_090202
  10
  11 #include <boost/mpl/and.hpp>
  12 #include <boost/icl/type_traits/is_map.hpp>
  13 #include <boost/icl/detail/notate.hpp>
  14 #include <boost/icl/detail/relation_state.hpp>
  15 #include <boost/icl/type_traits/identity_element.hpp>
  16 #include <boost/icl/type_traits/codomain_type_of.hpp>
  17 #include <boost/icl/type_traits/is_concept_equivalent.hpp>
  18 #include <boost/icl/type_traits/is_element_container.hpp>
  19 #include <boost/icl/concept/interval_set_value.hpp>
  20 #include <boost/icl/concept/map_value.hpp>
  21
  22 namespace boost{namespace icl
  23 {
  24
  25 #ifdef BOOST_MSVC
  26 #pragma warning(push)
  27 #pragma warning(disable:4127) // conditional expression is constant
  28 #endif
  29
  30 namespace Set
  31 {
  32
  33 //------------------------------------------------------------------------------
  34 template<class LeftT, class RightT>
  35 struct settic_codomain_compare
  36 {
  37     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
  38     {
  39         return inclusion_compare( co_value<LeftT>(left_),
  40                                  co_value<RightT>(right_));
  41     }
  42 };
  43
  44 template<class LeftT, class RightT>
  45 struct atomic_codomain_compare
  46 {
  47     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
  48     {
  49         if(co_value<LeftT>(left_) == co_value<RightT>(right_))
  50             return inclusion::equal;
  51         else
  52             return inclusion::unrelated;
  53     }
  54 };
  55
  56 template<class LeftT, class RightT>
  57 struct empty_codomain_compare
  58 {
  59     static int apply(typename LeftT::const_iterator&, typename RightT::const_iterator&)
  60     {
  61         return inclusion::equal;
  62     }
  63 };
  64
  65 template<class LeftT, class RightT>
  66 struct map_codomain_compare
  67 {
  68     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
  69     {
  70         using namespace boost::mpl;
  71         typedef typename LeftT::codomain_type  LeftCodomainT;
  72         typedef typename RightT::codomain_type RightCodomainT;
  73
  74         return
  75             if_<
  76                 bool_<is_concept_equivalent<is_set,LeftCodomainT,
  77                                                    RightCodomainT>::value>,
  78                 settic_codomain_compare<LeftT,RightT>,
  79                 atomic_codomain_compare<LeftT,RightT>
  80             >
  81             ::type::apply(left_, right_);
  82     }
  83 };
  84
  85
  86 //------------------------------------------------------------------------------
  87 template<class LeftT, class RightT>
  88 class subset_comparer
  89 {
  90 private:
  91     subset_comparer& operator = (const subset_comparer&);
  92 public:
  93     typedef typename LeftT::const_iterator  LeftIterT;
  94     typedef typename RightT::const_iterator RightIterT;
  95
  96     BOOST_STATIC_CONSTANT(bool,
  97         _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value));
  98
  99     subset_comparer(const LeftT&      left,
 100                     const RightT&     right,
 101                     const LeftIterT&  left_end,
 102                     const RightIterT& right_end)
 103         : _left(left), _right(right),
 104           _left_end(left_end), _right_end(right_end), _result(equal)
 105     {}
 106
 107     enum{nextboth, stop};
 108
 109     enum
 110     {
 111         unrelated  = inclusion::unrelated,
 112         subset     = inclusion::subset,     // left is_subset_of   right
 113         superset   = inclusion::superset,   // left is_superset_of right
 114         equal      = inclusion::equal       // equal = subset | superset
 115     };
 116
 117     int result()const{ return _result; }
 118
 119     int co_compare(LeftIterT& left, RightIterT& right)
 120     {
 121         using namespace boost::mpl;
 122         typedef typename codomain_type_of<LeftT>::type  LeftCodomainT;
 123         typedef typename codomain_type_of<RightT>::type RightCodomainT;
 124
 125         return
 126             if_<
 127                 bool_<is_concept_equivalent<is_element_map,LeftT,RightT>::value>,
 128                 map_codomain_compare<LeftT,RightT>,
 129                 empty_codomain_compare<LeftT,RightT>
 130             >
 131             ::type::apply(left,right);
 132     }
 133
 134     int restrict_result(int state) { return _result &= state; }
 135
 136     int next_both(LeftIterT& left, RightIterT& right)
 137     {
 138         if(left == _left_end && right == _right_end)
 139             return stop;
 140         else if(left == _left_end)
 141         {
 142             restrict_result(subset);
 143             return stop;
 144         }
 145         else if(right == _right_end)
 146         {
 147             restrict_result(superset);
 148             return stop;
 149         }
 150         else if(typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(right)))
 151         {   // left:  *left . . *joint_     left could be superset
 152             // right:           *right ...  if joint_ exists
 153             restrict_result(superset);
 154             if(unrelated == _result)
 155                 return stop;
 156             else
 157             {
 158                 LeftIterT joint_ = _left.lower_bound(key_value<RightT>(right));
 159                 if(    joint_ == _left.end()
 160                     || typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(joint_)))
 161                 {
 162                     _result = unrelated;
 163                     return stop;
 164                 }
 165                 else
 166                     left = joint_;
 167             }
 168         }
 169         else if(typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(left)))
 170         {   // left:             *left   left could be subset
 171             // right:*right . . .*joint_ if *joint_ exists
 172             restrict_result(subset);
 173             if(unrelated == _result)
 174                 return stop;
 175             else
 176             {
 177                 RightIterT joint_ = _right.lower_bound(key_value<LeftT>(left));
 178                 if(    joint_ == _right.end()
 179                     || typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(joint_)))
 180                 {
 181                     _result = unrelated;
 182                     return stop;
 183                 }
 184                 else
 185                     right = joint_;
 186             }
 187         }
 188
 189         // left =key= right
 190         if(_compare_codomain)
 191             if(unrelated == restrict_result(co_compare(left,right)))
 192                 return stop;
 193
 194         ++left;
 195         ++right;
 196         return nextboth;
 197     }
 198
 199 private:
 200     const LeftT&  _left;
 201     const RightT& _right;
 202     LeftIterT     _left_end;
 203     RightIterT    _right_end;
 204     int           _result;
 205 };
 206
 207
 208
 209
 210
 211 //------------------------------------------------------------------------------
 212 // Subset/superset comparison on ranges of two interval container
 213 //------------------------------------------------------------------------------
 214 template<class LeftT, class RightT>
 215 int subset_compare
 216 (
 217     const LeftT& left,   //sub
 218     const RightT& right, //super
 219     typename LeftT::const_iterator  left_begin,
 220     typename LeftT::const_iterator  left_end,
 221     typename RightT::const_iterator right_begin,
 222     typename RightT::const_iterator right_end
 223 )
 224 {
 225     typedef subset_comparer<LeftT,RightT> Step;
 226     Step step(left, right, left_end, right_end);
 227
 228     typename LeftT::const_iterator  left_  = left_begin;
 229     typename RightT::const_iterator right_ = right_begin;
 230
 231     int state = Step::nextboth;
 232     while(state != Step::stop)
 233         state = step.next_both(left_, right_);
 234
 235     return step.result();
 236 }
 237
 238 template<class LeftT, class RightT>
 239 int subset_compare(const LeftT& left, const RightT& right)
 240 {
 241     return subset_compare
 242         (
 243             left, right,
 244             left.begin(), left.end(),
 245             right.begin(), right.end()
 246         );
 247 }
 248
 249
 250 } // namespace Set
 251
 252 #ifdef BOOST_MSVC
 253 #pragma warning(pop)
 254 #endif
 255
 256 }} // namespace icl boost
 257
 258 #endif
 259