/*-----------------------------------------------------------------------------+ | |
Copyright (c) 2008-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_INTERVAL_SET_ALGO_HPP_JOFA_081005 | |
#define BOOST_ICL_INTERVAL_SET_ALGO_HPP_JOFA_081005 | |
#include <boost/next_prior.hpp> | |
#include <boost/icl/detail/notate.hpp> | |
#include <boost/icl/detail/relation_state.hpp> | |
#include <boost/icl/type_traits/identity_element.hpp> | |
#include <boost/icl/type_traits/is_map.hpp> | |
#include <boost/icl/type_traits/is_total.hpp> | |
#include <boost/icl/type_traits/is_combinable.hpp> | |
#include <boost/icl/concept/set_value.hpp> | |
#include <boost/icl/concept/map_value.hpp> | |
#include <boost/icl/interval_combining_style.hpp> | |
#include <boost/icl/detail/element_comparer.hpp> | |
#include <boost/icl/detail/interval_subset_comparer.hpp> | |
#include <boost/icl/detail/associated_value.hpp> | |
namespace boost{namespace icl | |
{ | |
namespace Interval_Set | |
{ | |
//------------------------------------------------------------------------------ | |
// Lexicographical comparison on ranges of two interval container | |
//------------------------------------------------------------------------------ | |
template<class LeftT, class RightT> | |
bool is_element_equal(const LeftT& left, const RightT& right) | |
{ | |
return subset_compare | |
( | |
left, right, | |
left.begin(), left.end(), | |
right.begin(), right.end() | |
) == inclusion::equal; | |
} | |
template<class LeftT, class RightT> | |
bool is_element_less(const LeftT& left, const RightT& right) | |
{ | |
return element_compare | |
( | |
left, right, | |
left.begin(), left.end(), | |
right.begin(), right.end() | |
) == comparison::less; | |
} | |
template<class LeftT, class RightT> | |
bool is_element_greater(const LeftT& left, const RightT& right) | |
{ | |
return element_compare | |
( | |
left, right, | |
left.begin(), left.end(), | |
right.begin(), right.end() | |
) == comparison::greater; | |
} | |
//------------------------------------------------------------------------------ | |
// Subset/superset compare on ranges of two interval container | |
//------------------------------------------------------------------------------ | |
template<class IntervalContainerT> | |
bool is_joinable(const IntervalContainerT& container, | |
typename IntervalContainerT::const_iterator first, | |
typename IntervalContainerT::const_iterator past) | |
{ | |
if(first == container.end()) | |
return true; | |
typename IntervalContainerT::const_iterator it_ = first, next_ = first; | |
++next_; | |
while(next_ != container.end() && it_ != past) | |
if(!icl::touches(key_value<IntervalContainerT>(it_++), | |
key_value<IntervalContainerT>(next_++))) | |
return false; | |
return true; | |
} | |
template<class LeftT, class RightT> | |
bool is_inclusion_equal(const LeftT& left, const RightT& right) | |
{ | |
return subset_compare | |
( | |
left, right, | |
left.begin(), left.end(), | |
right.begin(), right.end() | |
) == inclusion::equal; | |
} | |
template<class LeftT, class RightT> | |
typename enable_if<mpl::and_<is_concept_combinable<is_interval_set, is_interval_map, LeftT, RightT>, | |
is_total<RightT> >, | |
bool>::type | |
within(const LeftT&, const RightT&) | |
{ | |
return true; | |
} | |
template<class LeftT, class RightT> | |
typename enable_if<mpl::and_<is_concept_combinable<is_interval_set, is_interval_map, LeftT, RightT>, | |
mpl::not_<is_total<RightT> > >, | |
bool>::type | |
within(const LeftT& sub, const RightT& super) | |
{ | |
int result = | |
subset_compare | |
( | |
sub, super, | |
sub.begin(), sub.end(), | |
super.begin(), super.end() | |
); | |
return result == inclusion::subset || result == inclusion::equal; | |
} | |
template<class LeftT, class RightT> | |
typename enable_if<is_concept_combinable<is_interval_map, is_interval_map, LeftT, RightT>, | |
bool>::type | |
within(const LeftT& sub, const RightT& super) | |
{ | |
int result = | |
subset_compare | |
( | |
sub, super, | |
sub.begin(), sub.end(), | |
super.begin(), super.end() | |
); | |
return result == inclusion::subset || result == inclusion::equal; | |
} | |
template<class LeftT, class RightT> | |
typename enable_if<is_concept_combinable<is_interval_set, is_interval_set, LeftT, RightT>, | |
bool>::type | |
within(const LeftT& sub, const RightT& super) | |
{ | |
int result = | |
subset_compare | |
( | |
sub, super, | |
sub.begin(), sub.end(), | |
super.begin(), super.end() | |
); | |
return result == inclusion::subset || result == inclusion::equal; | |
} | |
template<class LeftT, class RightT> | |
typename enable_if<mpl::and_<is_concept_combinable<is_interval_map, is_interval_set, LeftT, RightT>, | |
is_total<LeftT> >, | |
bool>::type | |
contains(const LeftT&, const RightT&) | |
{ | |
return true; | |
} | |
template<class LeftT, class RightT> | |
typename enable_if<mpl::and_<is_concept_combinable<is_interval_map, is_interval_set, LeftT, RightT>, | |
mpl::not_<is_total<LeftT> > >, | |
bool>::type | |
contains(const LeftT& super, const RightT& sub) | |
{ | |
int result = | |
subset_compare | |
( | |
super, sub, | |
super.begin(), super.end(), | |
sub.begin(), sub.end() | |
); | |
return result == inclusion::superset || result == inclusion::equal; | |
} | |
template<class LeftT, class RightT> | |
typename enable_if<is_concept_combinable<is_interval_set, is_interval_set, LeftT, RightT>, | |
bool>::type | |
contains(const LeftT& super, const RightT& sub) | |
{ | |
int result = | |
subset_compare | |
( | |
super, sub, | |
super.begin(), super.end(), | |
sub.begin(), sub.end() | |
); | |
return result == inclusion::superset || result == inclusion::equal; | |
} | |
template<class IntervalContainerT> | |
bool is_dense(const IntervalContainerT& container, | |
typename IntervalContainerT::const_iterator first, | |
typename IntervalContainerT::const_iterator past) | |
{ | |
if(first == container.end()) | |
return true; | |
typename IntervalContainerT::const_iterator it_ = first, next_ = first; | |
++next_; | |
while(next_ != container.end() && it_ != past) | |
if(!icl::touches(key_value<IntervalContainerT>(it_++), | |
key_value<IntervalContainerT>(next_++))) | |
return false; | |
return true; | |
} | |
} // namespace Interval_Set | |
namespace segmental | |
{ | |
template<class Type> | |
inline bool joinable(const Type& _Type, typename Type::iterator& some, typename Type::iterator& next) | |
{ | |
// assert: next != end && some++ == next | |
return touches(key_value<Type>(some), key_value<Type>(next)) | |
&& co_equal(some, next, &_Type, &_Type); | |
} | |
template<class Type> | |
inline void join_nodes(Type& object, typename Type::iterator& left_, | |
typename Type::iterator& right_) | |
{ | |
typedef typename Type::interval_type interval_type; | |
interval_type right_interval = key_value<Type>(right_); | |
object.erase(right_); | |
const_cast<interval_type&>(key_value<Type>(left_)) | |
= hull(key_value<Type>(left_), right_interval); | |
} | |
template<class Type> | |
inline typename Type::iterator | |
join_on_left(Type& object, typename Type::iterator& left_, | |
typename Type::iterator& right_) | |
{ | |
typedef typename Type::interval_type interval_type; | |
// both left and right are in the set and they are neighbours | |
BOOST_ASSERT(exclusive_less(key_value<Type>(left_), key_value<Type>(right_))); | |
BOOST_ASSERT(joinable(object, left_, right_)); | |
join_nodes(object, left_, right_); | |
return left_; | |
} | |
template<class Type> | |
inline typename Type::iterator | |
join_on_right(Type& object, typename Type::iterator& left_, | |
typename Type::iterator& right_) | |
{ | |
typedef typename Type::interval_type interval_type; | |
// both left and right are in the map and they are neighbours | |
BOOST_ASSERT(exclusive_less(key_value<Type>(left_), key_value<Type>(right_))); | |
BOOST_ASSERT(joinable(object, left_, right_)); | |
join_nodes(object, left_, right_); | |
right_ = left_; | |
return right_; | |
} | |
template<class Type> | |
typename Type::iterator join_left(Type& object, typename Type::iterator& it_) | |
{ | |
typedef typename Type::iterator iterator; | |
if(it_ == object.begin()) | |
return it_; | |
// there is a predecessor | |
iterator pred_ = it_; | |
if(joinable(object, --pred_, it_)) | |
return join_on_right(object, pred_, it_); | |
return it_; | |
} | |
template<class Type> | |
typename Type::iterator join_right(Type& object, typename Type::iterator& it_) | |
{ | |
typedef typename Type::iterator iterator; | |
if(it_ == object.end()) | |
return it_; | |
// there is a successor | |
iterator succ_ = it_; | |
if(++succ_ != object.end() && joinable(object, it_, succ_)) | |
return join_on_left(object, it_, succ_); | |
return it_; | |
} | |
template<class Type> | |
typename Type::iterator join_neighbours(Type& object, typename Type::iterator& it_) | |
{ | |
join_left (object, it_); | |
return join_right(object, it_); | |
} | |
template<class Type> | |
inline typename Type::iterator | |
join_under(Type& object, const typename Type::value_type& addend) | |
{ | |
//ASSERT: There is at least one interval in object that overlaps with addend | |
typedef typename Type::iterator iterator; | |
typedef typename Type::interval_type interval_type; | |
typedef typename Type::value_type value_type; | |
std::pair<iterator,iterator> overlap = object.equal_range(addend); | |
iterator first_ = overlap.first, | |
end_ = overlap.second, | |
last_ = end_; --last_; | |
iterator second_= first_; ++second_; | |
interval_type left_resid = right_subtract(key_value<Type>(first_), addend); | |
interval_type right_resid = left_subtract(key_value<Type>(last_) , addend); | |
object.erase(second_, end_); | |
const_cast<value_type&>(key_value<Type>(first_)) | |
= hull(hull(left_resid, addend), right_resid); | |
return first_; | |
} | |
template<class Type> | |
inline typename Type::iterator | |
join_under(Type& object, const typename Type::value_type& addend, | |
typename Type::iterator last_) | |
{ | |
//ASSERT: There is at least one interval in object that overlaps with addend | |
typedef typename Type::iterator iterator; | |
typedef typename Type::interval_type interval_type; | |
typedef typename Type::value_type value_type; | |
iterator first_ = object.lower_bound(addend); | |
//BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val)); | |
iterator second_= boost::next(first_), end_ = boost::next(last_); | |
interval_type left_resid = right_subtract(key_value<Type>(first_), addend); | |
interval_type right_resid = left_subtract(key_value<Type>(last_) , addend); | |
object.erase(second_, end_); | |
const_cast<value_type&>(key_value<Type>(first_)) | |
= hull(hull(left_resid, addend), right_resid); | |
return first_; | |
} | |
} // namespace segmental | |
namespace Interval_Set | |
{ | |
using namespace segmental; | |
template<class Type, int combining_style> | |
struct on_style; | |
template<class Type> | |
struct on_style<Type, interval_combine::joining> | |
{ | |
typedef on_style type; | |
typedef typename Type::interval_type interval_type; | |
typedef typename Type::iterator iterator; | |
inline static iterator handle_inserted(Type& object, iterator inserted_) | |
{ return join_neighbours(object, inserted_); } | |
inline static iterator add_over | |
(Type& object, const interval_type& addend, iterator last_) | |
{ | |
iterator joined_ = join_under(object, addend, last_); | |
return join_neighbours(object, joined_); | |
} | |
inline static iterator add_over | |
(Type& object, const interval_type& addend) | |
{ | |
iterator joined_ = join_under(object, addend); | |
return join_neighbours(object, joined_); | |
} | |
}; | |
template<class Type> | |
struct on_style<Type, interval_combine::separating> | |
{ | |
typedef on_style type; | |
typedef typename Type::interval_type interval_type; | |
typedef typename Type::iterator iterator; | |
inline static iterator handle_inserted(Type&, iterator inserted_) | |
{ return inserted_; } | |
inline static iterator add_over | |
(Type& object, const interval_type& addend, iterator last_) | |
{ | |
return join_under(object, addend, last_); | |
} | |
inline static iterator add_over | |
(Type& object, const interval_type& addend) | |
{ | |
return join_under(object, addend); | |
} | |
}; | |
template<class Type> | |
struct on_style<Type, interval_combine::splitting> | |
{ | |
typedef on_style type; | |
typedef typename Type::interval_type interval_type; | |
typedef typename Type::iterator iterator; | |
inline static iterator handle_inserted(Type&, iterator inserted_) | |
{ return inserted_; } | |
inline static iterator add_over | |
(Type& object, const interval_type& addend, iterator last_) | |
{ | |
iterator first_ = object.lower_bound(addend); | |
//BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val)); | |
iterator it_ = first_; | |
interval_type rest_interval = addend; | |
add_front(object, rest_interval, it_); | |
add_main (object, rest_interval, it_, last_); | |
add_rear (object, rest_interval, it_); | |
return it_; | |
} | |
inline static iterator add_over | |
(Type& object, const interval_type& addend) | |
{ | |
std::pair<iterator,iterator> overlap = object.equal_range(addend); | |
iterator first_ = overlap.first, | |
end_ = overlap.second, | |
last_ = end_; --last_; | |
iterator it_ = first_; | |
interval_type rest_interval = addend; | |
add_front(object, rest_interval, it_); | |
add_main (object, rest_interval, it_, last_); | |
add_rear (object, rest_interval, it_); | |
return it_; | |
} | |
}; | |
template<class Type> | |
void add_front(Type& object, const typename Type::interval_type& inter_val, | |
typename Type::iterator& first_) | |
{ | |
typedef typename Type::interval_type interval_type; | |
typedef typename Type::iterator iterator; | |
// If the collision sequence has a left residual 'left_resid' it will | |
// be split, to provide a standardized start of algorithms: | |
// The addend interval 'inter_val' covers the beginning of the collision sequence. | |
// only for the first there can be a left_resid: a part of *first_ left of inter_val | |
interval_type left_resid = right_subtract(key_value<Type>(first_), inter_val); | |
if(!icl::is_empty(left_resid)) | |
{ // [------------ . . . | |
// [left_resid---first_ --- . . . | |
iterator prior_ = cyclic_prior(object, first_); | |
const_cast<interval_type&>(key_value<Type>(first_)) | |
= left_subtract(key_value<Type>(first_), left_resid); | |
//NOTE: Only splitting | |
object._insert(prior_, icl::make_value<Type>(left_resid, co_value<Type>(first_))); | |
} | |
//POST: | |
// [----- inter_val ---- . . . | |
// ...[-- first_ --... | |
} | |
template<class Type> | |
void add_segment(Type& object, const typename Type::interval_type& inter_val, | |
typename Type::iterator& it_ ) | |
{ | |
typedef typename Type::interval_type interval_type; | |
interval_type lead_gap = right_subtract(inter_val, *it_); | |
if(!icl::is_empty(lead_gap)) | |
// [lead_gap--- . . . | |
// [prior_) [-- it_ ... | |
object._insert(prior(it_), lead_gap); | |
// . . . --------- . . . addend interval | |
// [-- it_ --) has a common part with the first overval | |
++it_; | |
} | |
template<class Type> | |
void add_main(Type& object, typename Type::interval_type& rest_interval, | |
typename Type::iterator& it_, | |
const typename Type::iterator& last_) | |
{ | |
typedef typename Type::interval_type interval_type; | |
interval_type cur_interval; | |
while(it_ != last_) | |
{ | |
cur_interval = *it_ ; | |
add_segment(object, rest_interval, it_); | |
// shrink interval | |
rest_interval = left_subtract(rest_interval, cur_interval); | |
} | |
} | |
template<class Type> | |
void add_rear(Type& object, const typename Type::interval_type& inter_val, | |
typename Type::iterator& it_ ) | |
{ | |
typedef typename Type::interval_type interval_type; | |
typedef typename Type::iterator iterator; | |
iterator prior_ = cyclic_prior(object, it_); | |
interval_type cur_itv = *it_; | |
interval_type lead_gap = right_subtract(inter_val, cur_itv); | |
if(!icl::is_empty(lead_gap)) | |
// [lead_gap--- . . . | |
// [prior_) [-- it_ ... | |
object._insert(prior_, lead_gap); | |
interval_type end_gap = left_subtract(inter_val, cur_itv); | |
if(!icl::is_empty(end_gap)) | |
// [---------------end_gap) | |
// [-- it_ --) | |
it_ = object._insert(it_, end_gap); | |
else | |
{ | |
// only for the last there can be a right_resid: a part of *it_ right of addend | |
interval_type right_resid = left_subtract(cur_itv, inter_val); | |
if(!icl::is_empty(right_resid)) | |
{ | |
// [--------------) | |
// [-- it_ --right_resid) | |
const_cast<interval_type&>(*it_) = right_subtract(*it_, right_resid); | |
it_ = object._insert(it_, right_resid); | |
} | |
} | |
} | |
//============================================================================== | |
//= Addition | |
//============================================================================== | |
template<class Type> | |
typename Type::iterator | |
add(Type& object, const typename Type::value_type& addend) | |
{ | |
typedef typename Type::interval_type interval_type; | |
typedef typename Type::iterator iterator; | |
typedef typename on_style<Type, Type::fineness>::type on_style_; | |
if(icl::is_empty(addend)) | |
return object.end(); | |
std::pair<iterator,bool> insertion = object._insert(addend); | |
if(insertion.second) | |
return on_style_::handle_inserted(object, insertion.first); | |
else | |
return on_style_::add_over(object, addend, insertion.first); | |
} | |
template<class Type> | |
typename Type::iterator | |
add(Type& object, typename Type::iterator prior_, | |
const typename Type::value_type& addend) | |
{ | |
typedef typename Type::interval_type interval_type; | |
typedef typename Type::iterator iterator; | |
typedef typename on_style<Type, Type::fineness>::type on_style_; | |
if(icl::is_empty(addend)) | |
return prior_; | |
iterator insertion = object._insert(prior_, addend); | |
if(*insertion == addend) | |
return on_style_::handle_inserted(object, insertion); | |
else | |
return on_style_::add_over(object, addend); | |
} | |
//============================================================================== | |
//= Subtraction | |
//============================================================================== | |
template<class Type> | |
void subtract(Type& object, const typename Type::value_type& minuend) | |
{ | |
typedef typename Type::iterator iterator; | |
typedef typename Type::interval_type interval_type; | |
typedef typename Type::value_type value_type; | |
if(icl::is_empty(minuend)) return; | |
std::pair<iterator, iterator> exterior = object.equal_range(minuend); | |
if(exterior.first == exterior.second) return; | |
iterator first_ = exterior.first; | |
iterator end_ = exterior.second; | |
iterator last_ = end_; --last_; | |
interval_type leftResid = right_subtract(*first_, minuend); | |
interval_type rightResid; | |
if(first_ != end_ ) | |
rightResid = left_subtract(*last_ , minuend); | |
object.erase(first_, end_); | |
if(!icl::is_empty(leftResid)) | |
object._insert(leftResid); | |
if(!icl::is_empty(rightResid)) | |
object._insert(rightResid); | |
} | |
} // namespace Interval_Set | |
}} // namespace icl boost | |
#endif | |