| /*-----------------------------------------------------------------------------+ |
| 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 |
| |