icl/concept/interval_set.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2010-2010: 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_CONCEPT_INTERVAL_SET_HPP_JOFA_100920
0009 #define BOOST_ICL_CONCEPT_INTERVAL_SET_HPP_JOFA_100920
0010
0011 #include <boost/icl/type_traits/is_combinable.hpp>
0012 #include <boost/icl/type_traits/interval_type_of.hpp>
0013 #include <boost/icl/detail/set_algo.hpp>
0014 #include <boost/icl/detail/interval_set_algo.hpp>
0015 #include <boost/icl/concept/interval.hpp>
0016
0017 namespace boost{ namespace icl
0018 {
0019
0020 //==============================================================================
0021 //= Containedness<IntervalSet>
0022 //==============================================================================
0023 //------------------------------------------------------------------------------
0024 //- bool contains(c T&, c P&) T:{S} P:{e i S} fragment_types
0025 //------------------------------------------------------------------------------
0026 template<class Type>
0027 typename enable_if<is_interval_set<Type>, bool>::type
0028 contains(const Type& super, const typename Type::element_type& element)
0029 {
0030     return !(icl::find(super, element) == super.end());
0031 }
0032
0033 template<class Type>
0034 typename enable_if<is_interval_set<Type>, bool>::type
0035 contains(const Type& super, const typename Type::segment_type& inter_val)
0036 {
0037     typedef typename Type::const_iterator const_iterator;
0038     if(icl::is_empty(inter_val))
0039         return true;
0040
0041     std::pair<const_iterator, const_iterator> exterior
0042         = super.equal_range(inter_val);
0043     if(exterior.first == exterior.second)
0044         return false;
0045
0046     const_iterator last_overlap = cyclic_prior(super, exterior.second);
0047
0048     return
0049         icl::contains(hull(*(exterior.first), *last_overlap), inter_val)
0050     &&  Interval_Set::is_joinable(super, exterior.first, last_overlap);
0051 }
0052
0053 template<class Type, class OperandT>
0054 typename enable_if<has_same_concept<is_interval_set, Type, OperandT>,
0055                    bool>::type
0056 contains(const Type& super, const OperandT& sub)
0057 {
0058     return Interval_Set::contains(super, sub);
0059 }
0060
0061 //==============================================================================
0062 //= Addition<IntervalSet>
0063 //==============================================================================
0064 //------------------------------------------------------------------------------
0065 //- T& add(T&, c P&) T:{S} P:{e i} fragment_types
0066 //------------------------------------------------------------------------------
0067 template<class Type>
0068 typename enable_if<is_interval_set<Type>, Type>::type&
0069 add(Type& object, const typename Type::segment_type& operand)
0070 {
0071     return object.add(operand);
0072 }
0073
0074 template<class Type>
0075 inline typename enable_if<is_interval_set<Type>, Type>::type&
0076 add(Type& object, const typename Type::element_type& operand)
0077 {
0078     typedef typename Type::segment_type segment_type;
0079     return icl::add(object, icl::singleton<segment_type>(operand));
0080 }
0081
0082 //------------------------------------------------------------------------------
0083 //- T& add(T&, J, c P&) T:{S} P:{i} interval_type
0084 //------------------------------------------------------------------------------
0085 template<class Type>
0086 inline typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
0087 add(Type& object, typename Type::iterator      prior,
0088             const typename Type::segment_type& operand)
0089 {
0090     return object.add(prior, operand);
0091 }
0092
0093 //==============================================================================
0094 //= Insertion<IntervalSet>
0095 //==============================================================================
0096 //------------------------------------------------------------------------------
0097 //- T& insert(T&, c P&) T:{S} P:{e i} fragment_types
0098 //------------------------------------------------------------------------------
0099 template<class Type>
0100 inline typename enable_if<is_interval_set<Type>, Type>::type&
0101 insert(Type& object, const typename Type::segment_type& operand)
0102 {
0103     return icl::add(object, operand);
0104 }
0105
0106 template<class Type>
0107 inline typename enable_if<is_interval_set<Type>, Type>::type&
0108 insert(Type& object, const typename Type::element_type& operand)
0109 {
0110     return icl::add(object, operand);
0111 }
0112
0113 //------------------------------------------------------------------------------
0114 //- T& insert(T&, J, c P&) T:{S} P:{i} with hint
0115 //------------------------------------------------------------------------------
0116 template<class Type>
0117 inline typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
0118 insert(Type& object, typename Type::iterator      prior,
0119                const typename Type::segment_type& operand)
0120 {
0121     return icl::add(object, prior, operand);
0122 }
0123
0124 //==============================================================================
0125 //= Subtraction<IntervalSet>
0126 //==============================================================================
0127 //------------------------------------------------------------------------------
0128 //- T& subtract(T&, c P&) T:{S} P:{e i} fragment_type
0129 //------------------------------------------------------------------------------
0130 template<class Type>
0131 typename enable_if<is_interval_set<Type>, Type>::type&
0132 subtract(Type& object, const typename Type::segment_type& operand)
0133 {
0134     return object.subtract(operand);
0135 }
0136
0137 template<class Type>
0138 inline typename enable_if<is_interval_set<Type>, Type>::type&
0139 subtract(Type& object, const typename Type::element_type& operand)
0140 {
0141     typedef typename Type::segment_type segment_type;
0142     return icl::subtract(object, icl::singleton<segment_type>(operand));
0143 }
0144
0145 //==============================================================================
0146 //= Erasure<IntervalSet>
0147 //==============================================================================
0148 //------------------------------------------------------------------------------
0149 //- T& erase(T&, c P&) T:{S} P:{e i} fragment_types
0150 //------------------------------------------------------------------------------
0151 template<class Type>
0152 typename enable_if<is_interval_set<Type>, Type>::type&
0153 erase(Type& object, const typename Type::segment_type& minuend)
0154 {
0155     return icl::subtract(object, minuend);
0156 }
0157
0158 template<class Type>
0159 typename enable_if<is_interval_set<Type>, Type>::type&
0160 erase(Type& object, const typename Type::element_type& minuend)
0161 {
0162     return icl::subtract(object, minuend);
0163 }
0164
0165 //==============================================================================
0166 //= Intersection
0167 //==============================================================================
0168 //------------------------------------------------------------------------------
0169 //- void add_intersection(T&, c T&, c P&) T:{S} P:{e i} fragment_types
0170 //------------------------------------------------------------------------------
0171 template<class Type>
0172 typename enable_if<is_interval_set<Type>, void>::type
0173 add_intersection(Type& section, const Type& object,
0174                  const typename Type::element_type& operand)
0175 {
0176     typedef typename Type::const_iterator const_iterator;
0177     const_iterator found = icl::find(object, operand);
0178     if(found != object.end())
0179         icl::add(section, operand);
0180 }
0181
0182
0183 template<class Type>
0184 typename enable_if<is_interval_set<Type>, void>::type
0185 add_intersection(Type& section, const Type& object,
0186                  const typename Type::segment_type& segment)
0187 {
0188     typedef typename Type::const_iterator const_iterator;
0189     typedef typename Type::iterator       iterator;
0190     typedef typename Type::interval_type  interval_type;
0191
0192     if(icl::is_empty(segment))
0193         return;
0194
0195     std::pair<const_iterator, const_iterator> exterior
0196         = object.equal_range(segment);
0197     if(exterior.first == exterior.second)
0198         return;
0199
0200     iterator prior_ = section.end();
0201     for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
0202     {
0203         interval_type common_interval = key_value<Type>(it_) & segment;
0204         if(!icl::is_empty(common_interval))
0205             prior_ = section.insert(prior_, common_interval);
0206     }
0207 }
0208
0209 //==============================================================================
0210 //= Symmetric difference<IntervalSet>
0211 //==============================================================================
0212 //------------------------------------------------------------------------------
0213 //- T& flip(T&, c P&) T:{S} P:{e i S'} fragment_types
0214 //------------------------------------------------------------------------------
0215 template<class Type>
0216 typename enable_if<is_interval_set<Type>, Type>::type&
0217 flip(Type& object, const typename Type::element_type& operand)
0218 {
0219     if(icl::contains(object, operand))
0220         return object -= operand;
0221     else
0222         return object += operand;
0223 }
0224
0225 template<class Type>
0226 typename enable_if<is_interval_set<Type>, Type>::type&
0227 flip(Type& object, const typename Type::segment_type& segment)
0228 {
0229     typedef typename Type::const_iterator const_iterator;
0230     typedef typename Type::interval_type  interval_type;
0231     // That which is common shall be subtracted
0232     // That which is not shall be added
0233     // So x has to be 'complementary added' or flipped
0234     interval_type span = segment;
0235     std::pair<const_iterator, const_iterator> exterior
0236         = object.equal_range(span);
0237
0238     const_iterator fst_ = exterior.first;
0239     const_iterator end_ = exterior.second;
0240
0241     interval_type covered, left_over;
0242     const_iterator it_ = fst_;
0243     while(it_ != end_)
0244     {
0245         covered = *it_++;
0246         //[a      ...  : span
0247         //     [b ...  : covered
0248         //[a  b)       : left_over
0249         left_over = right_subtract(span, covered);
0250         icl::subtract(object, span & covered); //That which is common shall be subtracted
0251         icl::add(object, left_over);           //That which is not shall be added
0252
0253         //...      d) : span
0254         //... c)      : covered
0255         //     [c  d) : span'
0256         span = left_subtract(span, covered);
0257     }
0258
0259     //If span is not empty here, it_ is not in the set so it_ shall be added
0260     icl::add(object, span);
0261     return object;
0262 }
0263
0264
0265 template<class Type, class OperandT>
0266 typename enable_if<is_concept_compatible<is_interval_set, Type, OperandT>, Type>::type&
0267 flip(Type& object, const OperandT& operand)
0268 {
0269     typedef typename OperandT::const_iterator const_iterator;
0270
0271     if(operand.empty())
0272         return object;
0273
0274     const_iterator common_lwb, common_upb;
0275
0276     if(!Set::common_range(common_lwb, common_upb, operand, object))
0277         return object += operand;
0278
0279     const_iterator it_ = operand.begin();
0280
0281     // All elements of operand left of the common range are added
0282     while(it_ != common_lwb)
0283         icl::add(object, *it_++);
0284     // All elements of operand in the common range are symmertrically subtracted
0285     while(it_ != common_upb)
0286         icl::flip(object, *it_++);
0287     // All elements of operand right of the common range are added
0288     while(it_ != operand.end())
0289         icl::add(object, *it_++);
0290
0291     return object;
0292 }
0293
0294 //==============================================================================
0295 //= Set selection
0296 //==============================================================================
0297 template<class Type>
0298 typename enable_if<is_interval_set<Type>, Type>::type&
0299 domain(Type& dom, const Type& object)
0300 {
0301     typedef typename Type::const_iterator const_iterator;
0302     typedef typename Type::iterator       iterator;
0303     dom.clear();
0304     const_iterator it_    = object.begin();
0305     iterator       prior_ = dom.end();
0306
0307     while(it_ != object.end())
0308         prior_ = icl::insert(dom, prior_, *it_++);
0309
0310     return dom;
0311 }
0312
0313 template<class Type>
0314 typename enable_if<is_interval_set<Type>, Type>::type&
0315 between(Type& in_between, const Type& object)
0316 {
0317     typedef typename Type::const_iterator const_iterator;
0318     typedef typename Type::iterator       iterator;
0319     in_between.clear();
0320     const_iterator it_ = object.begin(), pred_;
0321     iterator prior_ = in_between.end();
0322
0323     if(it_ != object.end())
0324         pred_ = it_++;
0325
0326     while(it_ != object.end())
0327         prior_ = icl::insert(in_between, prior_,
0328                              icl::between(*pred_++, *it_++));
0329
0330     return in_between;
0331 }
0332
0333
0334 //==============================================================================
0335 //= Streaming
0336 //==============================================================================
0337 template<class CharType, class CharTraits, class Type>
0338 typename enable_if<is_interval_set<Type>,
0339                    std::basic_ostream<CharType, CharTraits> >::type&
0340 operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
0341 {
0342     stream << "{";
0343     ICL_const_FORALL(typename Type, it_, object)
0344         stream << (*it_);
0345
0346     return stream << "}";
0347 }
0348
0349
0350 }} // namespace boost icl
0351
0352 #endif
0353
0354