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