Chris@16: /*-----------------------------------------------------------------------------+    
Chris@16: Copyright (c) 2010-2010: Joachim Faulhaber
Chris@16: +------------------------------------------------------------------------------+
Chris@16:    Distributed under the Boost Software License, Version 1.0.
Chris@16:       (See accompanying file LICENCE.txt or copy at
Chris@16:            http://www.boost.org/LICENSE_1_0.txt)
Chris@16: +-----------------------------------------------------------------------------*/
Chris@16: #ifndef BOOST_ICL_CONCEPT_INTERVAL_SET_HPP_JOFA_100920
Chris@16: #define BOOST_ICL_CONCEPT_INTERVAL_SET_HPP_JOFA_100920
Chris@16: 
Chris@16: #include <boost/icl/type_traits/is_combinable.hpp>
Chris@16: #include <boost/icl/type_traits/interval_type_of.hpp>
Chris@16: #include <boost/icl/detail/set_algo.hpp>
Chris@16: #include <boost/icl/detail/interval_set_algo.hpp>
Chris@16: #include <boost/icl/concept/interval.hpp>
Chris@16: 
Chris@16: namespace boost{ namespace icl
Chris@16: {
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Containedness<IntervalSet>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- bool contains(c T&, c P&) T:{S} P:{e i S} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, bool>::type
Chris@16: contains(const Type& super, const typename Type::element_type& element)
Chris@16: {
Chris@16:     return !(icl::find(super, element) == super.end());
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, bool>::type
Chris@16: contains(const Type& super, const typename Type::segment_type& inter_val)
Chris@16: { 
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16:     if(icl::is_empty(inter_val)) 
Chris@16:         return true;
Chris@16: 
Chris@16:     std::pair<const_iterator, const_iterator> exterior 
Chris@16:         = super.equal_range(inter_val);
Chris@16:     if(exterior.first == exterior.second)
Chris@16:         return false;
Chris@16: 
Chris@16:     const_iterator last_overlap = cyclic_prior(super, exterior.second);
Chris@16: 
Chris@16:     return 
Chris@16:         icl::contains(hull(*(exterior.first), *last_overlap), inter_val)
Chris@16:     &&  Interval_Set::is_joinable(super, exterior.first, last_overlap);
Chris@16: }
Chris@16: 
Chris@16: template<class Type, class OperandT>
Chris@16: typename enable_if<has_same_concept<is_interval_set, Type, OperandT>, 
Chris@16:                    bool>::type 
Chris@16: contains(const Type& super, const OperandT& sub)
Chris@16: {
Chris@16:     return Interval_Set::contains(super, sub);
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Addition<IntervalSet>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& add(T&, c P&) T:{S} P:{e i} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: add(Type& object, const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return object.add(operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: add(Type& object, const typename Type::element_type& operand)
Chris@16: {
Chris@16:     typedef typename Type::segment_type segment_type;
Chris@16:     return icl::add(object, icl::singleton<segment_type>(operand));
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& add(T&, J, c P&) T:{S} P:{i} interval_type
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
Chris@16: add(Type& object, typename Type::iterator      prior, 
Chris@16:             const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return object.add(prior, operand);
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Insertion<IntervalSet>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& insert(T&, c P&) T:{S} P:{e i} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: insert(Type& object, const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return icl::add(object, operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: insert(Type& object, const typename Type::element_type& operand)
Chris@16: {
Chris@16:     return icl::add(object, operand);
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& insert(T&, J, c P&) T:{S} P:{i} with hint
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
Chris@16: insert(Type& object, typename Type::iterator      prior,
Chris@16:                const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return icl::add(object, prior, operand);
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Subtraction<IntervalSet>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& subtract(T&, c P&) T:{S} P:{e i} fragment_type
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: subtract(Type& object, const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return object.subtract(operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: subtract(Type& object, const typename Type::element_type& operand)
Chris@16: {
Chris@16:     typedef typename Type::segment_type segment_type;
Chris@16:     return icl::subtract(object, icl::singleton<segment_type>(operand));
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Erasure<IntervalSet>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& erase(T&, c P&) T:{S} P:{e i} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: erase(Type& object, const typename Type::segment_type& minuend)
Chris@16: {
Chris@16:     return icl::subtract(object, minuend);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: erase(Type& object, const typename Type::element_type& minuend)
Chris@16: {
Chris@16:     return icl::subtract(object, minuend);
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Intersection
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- void add_intersection(T&, c T&, c P&) T:{S} P:{e i} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, void>::type
Chris@16: add_intersection(Type& section, const Type& object, 
Chris@16:                  const typename Type::element_type& operand)
Chris@16: {
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16:     const_iterator found = icl::find(object, operand);
Chris@16:     if(found != object.end())
Chris@16:         icl::add(section, operand);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, void>::type
Chris@16: add_intersection(Type& section, const Type& object, 
Chris@16:                  const typename Type::segment_type& segment)
Chris@16: {
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16:     typedef typename Type::iterator       iterator;
Chris@16:     typedef typename Type::interval_type  interval_type;
Chris@16: 
Chris@16:     if(icl::is_empty(segment)) 
Chris@16:         return;
Chris@16: 
Chris@16:     std::pair<const_iterator, const_iterator> exterior 
Chris@16:         = object.equal_range(segment);
Chris@16:     if(exterior.first == exterior.second)
Chris@16:         return;
Chris@16: 
Chris@16:     iterator prior_ = section.end();
Chris@16:     for(const_iterator it_=exterior.first; it_ != exterior.second; it_++) 
Chris@16:     {
Chris@16:         interval_type common_interval = key_value<Type>(it_) & segment;
Chris@16:         if(!icl::is_empty(common_interval))
Chris@16:             prior_ = section.insert(prior_, common_interval);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Symmetric difference<IntervalSet>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& flip(T&, c P&) T:{S} P:{e i S'} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: flip(Type& object, const typename Type::element_type& operand)
Chris@16: {
Chris@16:     if(icl::contains(object, operand))
Chris@16:         return object -= operand;
Chris@16:     else
Chris@16:         return object += operand;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: flip(Type& object, const typename Type::segment_type& segment)
Chris@16: {
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16:     typedef typename Type::interval_type  interval_type;
Chris@16:     // That which is common shall be subtracted
Chris@16:     // That which is not shall be added
Chris@16:     // So x has to be 'complementary added' or flipped
Chris@16:     interval_type span = segment;
Chris@16:     std::pair<const_iterator, const_iterator> exterior 
Chris@16:         = object.equal_range(span);
Chris@16: 
Chris@16:     const_iterator fst_ = exterior.first;
Chris@16:     const_iterator end_ = exterior.second;
Chris@16: 
Chris@16:     interval_type covered, left_over;
Chris@16:     const_iterator it_ = fst_;
Chris@16:     while(it_ != end_) 
Chris@16:     {
Chris@16:         covered = *it_++; 
Chris@16:         //[a      ...  : span
Chris@16:         //     [b ...  : covered
Chris@16:         //[a  b)       : left_over
Chris@16:         left_over = right_subtract(span, covered);
Chris@16:         icl::subtract(object, span & covered); //That which is common shall be subtracted
Chris@16:         icl::add(object, left_over);           //That which is not shall be added
Chris@16: 
Chris@16:         //...      d) : span
Chris@16:         //... c)      : covered
Chris@16:         //     [c  d) : span'
Chris@16:         span = left_subtract(span, covered);
Chris@16:     }
Chris@16: 
Chris@16:     //If span is not empty here, it_ is not in the set so it_ shall be added
Chris@16:     icl::add(object, span);
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template<class Type, class OperandT>
Chris@16: typename enable_if<is_concept_compatible<is_interval_set, Type, OperandT>, Type>::type&
Chris@16: flip(Type& object, const OperandT& operand)
Chris@16: {
Chris@16:     typedef typename OperandT::const_iterator const_iterator;
Chris@16: 
Chris@16:     if(operand.empty())
Chris@16:         return object;
Chris@16: 
Chris@16:     const_iterator common_lwb, common_upb;
Chris@16: 
Chris@16:     if(!Set::common_range(common_lwb, common_upb, operand, object))
Chris@16:         return object += operand;
Chris@16: 
Chris@16:     const_iterator it_ = operand.begin();
Chris@16: 
Chris@16:     // All elements of operand left of the common range are added
Chris@16:     while(it_ != common_lwb)
Chris@16:         icl::add(object, *it_++);
Chris@16:     // All elements of operand in the common range are symmertrically subtracted
Chris@16:     while(it_ != common_upb)
Chris@16:         icl::flip(object, *it_++);
Chris@16:     // All elements of operand right of the common range are added
Chris@16:     while(it_ != operand.end())
Chris@16:         icl::add(object, *it_++);
Chris@16: 
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Set selection
Chris@16: //==============================================================================
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: domain(Type& dom, const Type& object)
Chris@16: {
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16:     typedef typename Type::iterator       iterator;
Chris@16:     dom.clear();
Chris@16:     const_iterator it_    = object.begin();
Chris@16:     iterator       prior_ = dom.end();
Chris@16: 
Chris@16:     while(it_ != object.end())
Chris@16:         prior_ = icl::insert(dom, prior_, *it_++);
Chris@16: 
Chris@16:     return dom;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_set<Type>, Type>::type&
Chris@16: between(Type& in_between, const Type& object)
Chris@16: {
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16:     typedef typename Type::iterator       iterator;
Chris@16:     in_between.clear();
Chris@16:     const_iterator it_ = object.begin(), pred_;
Chris@16:     iterator prior_ = in_between.end();
Chris@16: 
Chris@16:     if(it_ != object.end())
Chris@16:         pred_ = it_++;
Chris@16: 
Chris@16:     while(it_ != object.end())
Chris@16:         prior_ = icl::insert(in_between, prior_, 
Chris@16:                              icl::between(*pred_++, *it_++));
Chris@16: 
Chris@16:     return in_between;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Streaming
Chris@16: //==============================================================================
Chris@16: template<class CharType, class CharTraits, class Type>
Chris@16: typename enable_if<is_interval_set<Type>, 
Chris@16:                    std::basic_ostream<CharType, CharTraits> >::type& 
Chris@16: operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
Chris@16: {
Chris@16:     stream << "{";
Chris@16:     ICL_const_FORALL(typename Type, it_, object)
Chris@16:         stream << (*it_);
Chris@16: 
Chris@16:     return stream << "}";
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost icl
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: