|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r65469 - in sandbox/itl: boost/itl boost/itl/detail libs/itl/test libs/validate/example/labat_single_
From: afojgo_at_[hidden]
Date: 2010-09-19 16:55:32
Author: jofaber
Date: 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
New Revision: 65469
URL: http://svn.boost.org/trac/boost/changeset/65469
Log:
Refactoring: Moving some functions to interval container classes in order to ensure class invariants. Stable{msvc-9.0, gcc-3.4.4}
Removed:
sandbox/itl/boost/itl/seqs.hpp
Text files modified:
sandbox/itl/boost/itl/detail/interval_map_algo.hpp | 934 ----------------------------------------
sandbox/itl/boost/itl/detail/interval_set_algo.hpp | 9
sandbox/itl/boost/itl/functions.hpp | 342 ++++----------
sandbox/itl/boost/itl/interval_base_map.hpp | 929 ++++++++++++++++++++++++++++++++++++++
sandbox/itl/boost/itl/interval_base_set.hpp | 190 +++++++
sandbox/itl/boost/itl/interval_map.hpp | 98 ++++
sandbox/itl/boost/itl/interval_set.hpp | 27 +
sandbox/itl/boost/itl/separate_interval_set.hpp | 24
sandbox/itl/boost/itl/split_interval_map.hpp | 63 ++
sandbox/itl/boost/itl/split_interval_set.hpp | 43 +
sandbox/itl/libs/itl/test/test_interval_map_shared.hpp | 2
sandbox/itl/libs/validate/example/labat_single_/labat_single.cpp | 2
12 files changed, 1420 insertions(+), 1243 deletions(-)
Modified: sandbox/itl/boost/itl/detail/interval_map_algo.hpp
==============================================================================
--- sandbox/itl/boost/itl/detail/interval_map_algo.hpp (original)
+++ sandbox/itl/boost/itl/detail/interval_map_algo.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -166,940 +166,6 @@
return Interval_Set::within(sub, super);
}
-
-template <class Type, class Combiner>
-inline typename Type::iterator
-gap_insert( Type& object,
- typename Type::iterator prior_,
- const typename Type::interval_type& inter_val,
- const typename Type::codomain_type& co_val)
-{
- typedef typename Type::value_type value_type;
- // inter_val is not conained in this map. Insertion will be successful
- BOOST_ASSERT(object.find(inter_val) == object.end());
- BOOST_ASSERT(!(absorbs_neutrons<Type>::value && co_val==Combiner::neutron()));
-
- return object._insert(prior_, value_type(inter_val, version<Combiner>()(co_val)));
-}
-
-template <class Type, class Combiner>
-inline typename Type::iterator
-_map_insert( Type& object,
- typename Type::iterator prior_,
- const typename Type::interval_type& inter_val,
- const typename Type::codomain_type& co_val)
-{
- typedef typename Type::value_type value_type;
-
- return object._insert(prior_, value_type(inter_val, version<Combiner>()(co_val)));
-}
-
-template <class Type, class Combiner>
-inline std::pair<typename Type::iterator, bool>
-_map_insert( Type& object,
- const typename Type::interval_type& inter_val,
- const typename Type::codomain_type& co_val)
-{
- typedef typename Type::value_type value_type;
-
- return object._insert(value_type(inter_val, version<Combiner>()(co_val)));
-}
-
-template<class Type, class Combiner, int absorbs_neutrons>
-struct on_neutric;
-
-template <class Type, class Combiner>
-inline std::pair<typename Type::iterator, bool>
-informing_add( Type& object,
- const typename Type::iterator& prior_,
- const typename Type::interval_type& inter_val,
- const typename Type::codomain_type& co_val )
-{
- typedef typename Type::value_type value_type;
- typedef typename Type::iterator iterator;
- typedef typename on_neutric<Type,Combiner,
- absorbs_neutrons<Type>::value>::type on_neutric_;
-
- // Never try to insert a neutron into a neutron absorber here:
- BOOST_ASSERT(!(on_neutric_::is_absorbable(co_val)));
-
- iterator inserted_
- = object._insert(prior_, value_type(inter_val, Combiner::neutron()));
-
- if(inserted_->first == inter_val && inserted_->second == Combiner::neutron())
- {
- Combiner()(inserted_->second, co_val);
- return std::pair<iterator,bool>(inserted_, true);
- }
- else
- return std::pair<iterator,bool>(inserted_, false);
-}
-
-template <class Type>
-inline std::pair<typename Type::iterator, bool>
-informing_insert( Type& object,
- const typename Type::iterator& prior_,
- const typename Type::interval_type& inter_val,
- const typename Type::codomain_type& co_val )
-{
- typedef typename Type::value_type value_type;
- typedef typename Type::iterator iterator;
-
- iterator inserted_
- = object._insert(prior_, value_type(inter_val, co_val));
-
- if(inserted_ == prior_)
- return std::pair<iterator,bool>(inserted_, false);
- else if(inserted_->first == inter_val)
- return std::pair<iterator,bool>(inserted_, true);
- else
- return std::pair<iterator,bool>(inserted_, false);
-}
-
-//------------------------------------------------------------------------------
-//------------------------------------------------------------------------------
-template<class Type, class Combiner>
-struct on_neutric<Type, Combiner, false>
-{
- typedef on_neutric type;
- typedef typename Type::codomain_type codomain_type;
-
- static bool is_absorbable(const codomain_type&){ return false; }
-};
-
-template<class Type, class Combiner>
-struct on_neutric<Type, Combiner, true>
-{
- typedef on_neutric type;
- typedef typename Type::codomain_type codomain_type;
- typedef typename Type::codomain_combine codomain_combine;
-
- static bool is_absorbable(const codomain_type& co_value)
- {
- return absorbs_neutrons<Type>::value
- && co_value == Combiner::neutron();
- }
-};
-
-//------------------------------------------------------------------------------
-//------------------------------------------------------------------------------
-template<class Type, int combining_style>
-struct on_style;
-
-template<class Type>
-struct on_style<Type, interval_combine::splitting>
-{
- typedef on_style type;
- typedef typename Type::iterator iterator;
-
- static iterator handle_inserted(Type&, iterator it_){ return it_; }
- static void handle_inserted(Type&, iterator, iterator&) {}
-};
-
-template<class Type>
-struct on_style<Type, interval_combine::joining>
-{
- typedef on_style type;
- typedef typename Type::iterator iterator;
-
- static iterator handle_inserted(Type& object, iterator it_)
- {
- return join_neighbours(object, it_);
- }
-
- static void handle_inserted(Type& object, iterator inserted_, iterator& it_)
- {
- join_left(object, inserted_);
- // after filling that gap there may be another joining opportunity
- join_left(object, it_);
- }
-};
-
-
-//------------------------------------------------------------------------------
-//------------------------------------------------------------------------------
-template<class Type, class Combiner, bool abosorbs_neutrons, int combining_style>
-struct on_segment;
-
-template<class Type, class Combiner>
-struct on_segment<Type, Combiner, false, interval_combine::splitting>
-{
- typedef on_segment type;
- typedef typename Type::iterator iterator;
- typedef typename Type::interval_type interval_type;
- typedef typename Type::codomain_type codomain_type;
-
- static void handle_left_combined(Type&, iterator){}
- static void handle_combined(Type&, iterator){}
- static void handle_succeeded_combined(Type&, iterator, iterator){}
- static void handle_preceeded_combined(Type&, iterator, iterator&){}
- static void handle_inserted(Type&, iterator, iterator){}
- static void handle_reinserted(Type&, iterator insertion_){}
-
- static void insert_at(Type& object, iterator& it_, iterator,
- const interval_type& end_gap, const codomain_type& co_val)
- {
- it_ = gap_insert<Type,Combiner>(object, it_, end_gap, co_val);
- }
-
-};
-
-template<class Type, class Combiner>
-struct on_segment<Type, Combiner, true, interval_combine::splitting>
-{
- typedef on_segment type;
- typedef typename Type::iterator iterator;
- typedef typename Type::interval_type interval_type;
- typedef typename Type::codomain_type codomain_type;
-
- static void handle_left_combined(Type& object, iterator it_)
- {
- if(it_->second == Combiner::neutron())
- object.erase(it_);
- }
-
- static void handle_combined(Type& object, iterator it_)
- {
- if(it_->second == Combiner::neutron())
- object.erase(it_);
- }
-
- static void handle_preceeded_combined(Type& object, iterator prior_, iterator& it_)
- {
- if(it_->second == Combiner::neutron())
- {
- object.erase(it_);
- it_ = prior_;
- }
- }
-
- static void handle_succeeded_combined(Type& object, iterator it_, iterator)
- {
- if(it_->second == Combiner::neutron())
- object.erase(it_);
- }
-
- static void handle_inserted(Type&, iterator, iterator){}
- static void handle_reinserted(Type&, iterator insertion_){}
-
- static void insert_at(Type& object, iterator& it_, iterator prior_,
- const interval_type& end_gap, const codomain_type& co_val)
- {
- if(it_->second == Combiner::neutron())
- {
- object.erase(it_);
- it_ = gap_insert<Type,Combiner>(object, prior_, end_gap, co_val);
- }
- else
- it_ = gap_insert<Type,Combiner>(object, it_, end_gap, co_val);
- }
-
-};
-
-template<class Type, class Combiner>
-struct on_segment<Type, Combiner, false, interval_combine::joining>
-{
- typedef on_segment type;
- typedef typename Type::iterator iterator;
- typedef typename Type::interval_type interval_type;
- typedef typename Type::codomain_type codomain_type;
-
- static void handle_left_combined(Type& object, iterator it_)
- {
- join_left(object, it_);
- }
-
- static void handle_combined(Type& object, iterator it_)
- {
- join_neighbours(object, it_);
- }
-
- static void handle_preceeded_combined(Type& object, iterator, iterator& it_)
- {
- join_neighbours(object, it_);
- }
-
- static void handle_succeeded_combined(Type& object, iterator it_, iterator next_)
- {
- join_left(object, it_);
- join_neighbours(object, next_);
- }
-
- static void handle_inserted(Type& object, iterator prior_, iterator inserted_)
- {
- if(prior_ != object.end() && joinable(object, prior_, inserted_))
- join_on_right(object, prior_, inserted_);
- }
- static void handle_reinserted(Type& object, iterator insertion_)
- { join_right(object, insertion_); }
-
- static void insert_at(Type& object, iterator& it_, iterator,
- const interval_type& end_gap, const codomain_type& co_val)
- {
- join_left(object, it_);
- iterator inserted_ = gap_insert<Type,Combiner>(object, it_, end_gap, co_val);
- it_ = join_neighbours(object, inserted_);
- }
-};
-
-template<class Type, class Combiner>
-struct on_segment<Type, Combiner, true, interval_combine::joining>
-{
- typedef on_segment type;
- typedef typename Type::iterator iterator;
- typedef typename Type::interval_type interval_type;
- typedef typename Type::codomain_type codomain_type;
-
- static void handle_left_combined(Type& object, iterator it_)
- {
- if(it_->second == Combiner::neutron())
- object.erase(it_);
- else
- join_left(object, it_);
- }
-
- static void handle_combined(Type& object, iterator it_)
- {
- if(it_->second == Combiner::neutron())
- object.erase(it_);
- else
- join_neighbours(object, it_);
- }
-
- static void handle_preceeded_combined(Type& object, iterator prior_, iterator& it_)
- {
- if(it_->second == Combiner::neutron())
- {
- object.erase(it_);
- it_ = prior_;
- }
- else // After a new combination (e.g. combiner=max) joining neighbours may be possible
- join_neighbours(object, it_);
- }
-
- static void handle_succeeded_combined(Type& object, iterator it_, iterator next_)
- {
- if(it_->second==Combiner::neutron())
- {
- object.erase(it_);
- join_right(object, next_);
- }
- else
- {
- join_left(object, it_);
- join_neighbours(object, next_);
- }
- }
-
- static void handle_inserted(Type& object, iterator prior_, iterator inserted_)
- {
- if(prior_ != object.end() && joinable(object, prior_, inserted_))
- join_on_right(object, prior_, inserted_);
- }
-
- static void handle_reinserted(Type& object, iterator insertion_)
- { join_right(object, insertion_); }
-
- static void insert_at(Type& object, iterator& it_, iterator prior_,
- const interval_type& end_gap, const codomain_type& co_val)
- {
- if(it_->second == Combiner::neutron())
- {
- object.erase(it_);
- it_ = gap_insert<Type,Combiner>(object, prior_, end_gap, co_val);
- join_right(object, it_);
- }
- else
- {
- join_left(object, it_);
- iterator inserted_ = gap_insert<Type,Combiner>(object, it_, end_gap, co_val);
- it_ = join_neighbours(object, inserted_);
- }
- }
-};
-//------------------------------------------------------------------------------
-
-//==============================================================================
-//= Addition detail
-//==============================================================================
-
-template<class Type, class Combiner>
-void add_segment( Type& object,
- const typename Type::interval_type& inter_val,
- const typename Type::codomain_type& co_val,
- typename Type::iterator& it_ )
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::iterator iterator;
- typedef typename on_segment<Type,Combiner,
- absorbs_neutrons<Type>::value,
- Type::fineness>::type on_segment_;
-
- interval_type lead_gap = right_subtract(inter_val, it_->first);
- if(!itl::is_empty(lead_gap))
- {
- // [lead_gap--- . . .
- // [-- it_ ...
- iterator prior_ = prior(it_);
- iterator inserted_ = gap_insert<Type,Combiner>(object, prior_, lead_gap, co_val);
- on_segment_::handle_inserted(object, prior_, inserted_);
- }
-
- // . . . --------- . . . addend interval
- // [-- it_ --) has a common part with the first overval
- Combiner()(it_->second, co_val);
- on_segment_::handle_left_combined(object, it_++);
-}
-
-
-
-template<class Type, class Combiner>
-void add_main( Type& object,
- typename Type::interval_type& rest_interval,
- const typename Type::codomain_type& co_val,
- typename Type::iterator& it_,
- const typename Type::iterator& last_ )
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::iterator iterator;
-
- interval_type cur_interval;
- while(it_!=last_)
- {
- cur_interval = it_->first ;
- add_segment<Type,Combiner>(object, rest_interval, co_val, it_);
- // shrink interval
- rest_interval = left_subtract(rest_interval, cur_interval);
- }
-}
-
-
-
-template<class Type, class Combiner>
-void add_rear( Type& object,
- typename Type::interval_type& inter_val,
- const typename Type::codomain_type& co_val,
- typename Type::iterator& it_ )
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::iterator iterator;
- typedef typename on_segment<Type,Combiner,
- absorbs_neutrons<Type>::value,
- Type::fineness>::type on_segment_;
-
- iterator prior_ = cyclic_prior(object, it_);
- interval_type cur_itv = it_->first ;
-
- interval_type lead_gap = right_subtract(inter_val, cur_itv);
- if(!itl::is_empty(lead_gap))
- { // [lead_gap--- . . .
- // [prior) [-- it_ ...
- iterator inserted_ = gap_insert<Type,Combiner>(object, prior_, lead_gap, co_val);
- on_segment_::handle_inserted(object, prior_, inserted_);
- }
-
- interval_type end_gap = left_subtract(inter_val, cur_itv);
- if(!itl::is_empty(end_gap))
- {
- // [----------------end_gap)
- // . . . -- it_ --)
- Combiner()(it_->second, co_val);
- on_segment_::insert_at(object, it_, prior_, end_gap, co_val);
- }
- else
- {
- // only for the last there can be a right_resid: a part of *it_ right of x
- interval_type right_resid = left_subtract(cur_itv, inter_val);
-
- if(itl::is_empty(right_resid))
- {
- // [---------------)
- // [-- it_ ---)
- Combiner()(it_->second, co_val);
- on_segment_::handle_preceeded_combined(object, prior_, it_);
- }
- else
- {
- // [--------------)
- // [-- it_ --right_resid)
- const_cast<interval_type&>(it_->first) = right_subtract(it_->first, right_resid);
-
- //NOTE: This is NOT an insertion that has to take care for correct application of
- // the Combiner functor. It only reestablished that state after splitting the
- // 'it_' interval value pair. Using _map_insert<Combiner> does not work here.
- iterator insertion_ = object._insert(it_, value_type(right_resid, it_->second));
- on_segment_::handle_reinserted(object, insertion_);
-
- Combiner()(it_->second, co_val);
- on_segment_::handle_preceeded_combined(object, insertion_, it_);
- }
- }
-}
-
-//==============================================================================
-//= Addition
-//==============================================================================
-template<class Type, class Combiner>
-typename Type::iterator add( Type& object,
- const typename Type::value_type& addend)
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::codomain_type codomain_type;
- typedef typename Type::iterator iterator;
- typedef typename on_style<Type,Type::fineness>::type on_style_;
- typedef typename on_neutric<Type,Combiner,
- absorbs_neutrons<Type>::value>::type on_neutric_;
-
- const interval_type& inter_val = addend.first;
- if(itl::is_empty(inter_val))
- return object.end();
-
- const codomain_type& co_val = addend.second;
- if(on_neutric_::is_absorbable(co_val))
- return object.end();
-
- std::pair<iterator,bool> insertion
- = _map_insert<Type,Combiner>(object, inter_val, co_val);
-
- if(insertion.second)
- return on_style_::handle_inserted(object, insertion.first);
- else
- {
- // Detect the first and the end iterator of the collision sequence
- iterator first_ = object.lower_bound(inter_val),
- last_ = insertion.first;
- //assert(end_ == this->_map.upper_bound(inter_val));
-
- iterator it_ = first_;
- interval_type rest_interval = inter_val;
-
- Interval_Set::add_front (object, rest_interval, it_ );
- Interval_Map::add_main<Type,Combiner>(object, rest_interval, co_val, it_, last_);
- Interval_Map::add_rear<Type,Combiner>(object, rest_interval, co_val, it_ );
- return it_;
- }
-}
-
-
-template<class Type, class Combiner>
-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::value_type value_type;
- typedef typename Type::codomain_type codomain_type;
- typedef typename Type::iterator iterator;
- typedef typename on_style<Type,Type::fineness>::type on_style_;
- typedef typename on_neutric<Type,Combiner,
- absorbs_neutrons<Type>::value>::type on_neutric_;
-
- const interval_type& inter_val = addend.first;
- if(itl::is_empty(inter_val))
- return prior_;
-
- const codomain_type& co_val = addend.second;
- if(on_neutric_::is_absorbable(co_val))
- return prior_;
-
- std::pair<iterator,bool> insertion
- = informing_add<Type,Combiner>(object,prior_, inter_val, co_val);
-
- if(insertion.second)
- return on_style_::handle_inserted(object, insertion.first);
- else
- {
- // Detect the first and the end iterator of the collision sequence
- std::pair<iterator,iterator> overlap = object.equal_range(inter_val);
- iterator it_ = overlap.first,
- last_ = overlap.second;
- --last_;
- interval_type rest_interval = inter_val;
-
- Interval_Set::add_front (object, rest_interval, it_ );
- Interval_Map::add_main<Type,Combiner>(object, rest_interval, co_val, it_, last_);
- Interval_Map::add_rear<Type,Combiner>(object, rest_interval, co_val, it_ );
-
- return it_;
- }
-}
-
-//==============================================================================
-//= Subtract detail
-//==============================================================================
-
-template<class Type>
-void subtract_front( Type& object,
- const typename Type::interval_type& inter_val,
- typename Type::iterator& it_ )
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::iterator iterator;
-
- interval_type left_resid = right_subtract(it_->first, inter_val);
-
- if(!itl::is_empty(left_resid)) // [--- inter_val ---)
- { //[prior_) [left_resid)[--- it_ . . .
- iterator prior_ = cyclic_prior(object, it_);
- const_cast<interval_type&>(it_->first) = left_subtract(it_->first, left_resid);
- object._insert(prior_, value_type(left_resid, it_->second));
- // The segemnt *it_ is split at inter_val.first(), so as an invariant
- // segment *it_ is always "under" inter_val and a left_resid is empty.
- }
-}
-
-
-template<class Type, class Combiner>
-void subtract_main( Type& object,
- const typename Type::codomain_type& co_val,
- typename Type::iterator& it_,
- const typename Type::iterator& last_ )
-{
- typedef typename on_segment<Type,Combiner,
- absorbs_neutrons<Type>::value,
- Type::fineness>::type on_segment_;
- while(it_ != last_)
- {
- Combiner()(it_->second, co_val);
- on_segment_::handle_left_combined(object, it_++);
- }
-}
-
-
-template<class Type, class Combiner>
-void subtract_rear( Type& object,
- typename Type::interval_type& inter_val,
- const typename Type::codomain_type& co_val,
- typename Type::iterator& it_ )
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::iterator iterator;
- typedef typename on_segment<Type,Combiner,
- absorbs_neutrons<Type>::value,
- Type::fineness>::type on_segment_;
-
- interval_type right_resid = left_subtract(it_->first, inter_val);
-
- if(itl::is_empty(right_resid))
- {
- Combiner()(it_->second, co_val);
- on_segment_::handle_combined(object, it_);
- }
- else
- {
- const_cast<interval_type&>(it_->first) = right_subtract(it_->first, right_resid);
- iterator next_ = object._insert(it_, value_type(right_resid, it_->second));
- Combiner()(it_->second, co_val);
- on_segment_::handle_succeeded_combined(object, it_, next_);
- }
-}
-
-//==============================================================================
-//= Subtract
-//==============================================================================
-template<class Type, class Combiner>
-void subtract( Type& object,
- const typename Type::value_type& minuend)
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::codomain_type codomain_type;
- typedef typename Type::iterator iterator;
- typedef typename on_style<Type,Type::fineness>::type on_style_;
- typedef typename on_neutric<Type,Combiner,
- absorbs_neutrons<Type>::value>::type on_neutric_;
-
- interval_type inter_val = minuend.first;
- if(itl::is_empty(inter_val))
- return;
-
- const codomain_type& co_val = minuend.second;
- if(on_neutric_::is_absorbable(co_val))
- return;
-
- std::pair<iterator, iterator> exterior = object.equal_range(inter_val);
- if(exterior.first == exterior.second)
- return;
-
- iterator last_ = prior(exterior.second);
- iterator it_ = exterior.first;
- Interval_Map::subtract_front<Type> (object, inter_val, it_ );
- Interval_Map::subtract_main <Type,Combiner>(object, co_val, it_, last_);
- Interval_Map::subtract_rear <Type,Combiner>(object, inter_val, co_val, it_ );
-}
-
-
-//==============================================================================
-//= Insertion
-//==============================================================================
-
-template<class Type>
-void insert_main( Type& object,
- typename Type::interval_type& inter_val,
- const typename Type::codomain_type& co_val,
- typename Type::iterator& it_,
- const typename Type::iterator& last_ )
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::iterator iterator;
- typedef typename on_style<Type,Type::fineness>::type on_style_;
-
- iterator end_ = last_ ; ++end_;
- iterator prior_ = it_, inserted_;
- if(prior_ != object.end())
- --prior_;
- interval_type rest_interval = inter_val, left_gap, cur_itv;
- interval_type last_interval = last_ ->first;
-
- while(it_ != end_ )
- {
- cur_itv = it_->first ;
- left_gap = right_subtract(rest_interval, cur_itv);
-
- if(!itl::is_empty(left_gap))
- {
- inserted_ = object._insert(prior_, value_type(left_gap, co_val));
- on_style_::handle_inserted(object, inserted_, it_);
- }
-
- // shrink interval
- rest_interval = left_subtract(rest_interval, cur_itv);
- prior_ = it_;
- ++it_;
- }
-
- //insert_rear(rest_interval, co_val, last_):
- interval_type end_gap = left_subtract(rest_interval, last_interval);
- if(!itl::is_empty(end_gap))
- {
- inserted_ = object._insert(prior_, value_type(end_gap, co_val));
- it_ = on_style_::handle_inserted(object, inserted_);
- }
- else
- it_ = prior_;
-}
-
-
-
-template<class Type>
-typename Type::iterator insert( Type& object,
- const typename Type::value_type& addend)
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::codomain_type codomain_type;
- typedef typename Type::iterator iterator;
- typedef typename Type::codomain_combine codomain_combine;
- typedef typename on_style<Type,Type::fineness>::type on_style_;
- typedef typename on_neutric<Type, codomain_combine,
- absorbs_neutrons<Type>::value>::type on_neutric_;
-
- interval_type inter_val = addend.first;
- if(itl::is_empty(inter_val))
- return object.end();
-
- const codomain_type& co_val = addend.second;
- if(on_neutric_::is_absorbable(co_val))
- return object.end();
-
- std::pair<iterator,bool> insertion = object._insert(addend);
-
- if(insertion.second)
- return on_style_::handle_inserted(object, insertion.first);
- else
- {
- // Detect the first and the end iterator of the collision sequence
- iterator first_ = object.lower_bound(inter_val),
- last_ = insertion.first;
- //assert((++last_) == this->_map.upper_bound(inter_val));
- iterator it_ = first_;
- Interval_Map::insert_main(object, inter_val, co_val, it_, last_);
- return it_;
- }
-}
-
-
-template<class Type>
-typename Type::iterator insert( Type& object,
- typename Type::iterator prior_,
- const typename Type::value_type& addend)
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::codomain_type codomain_type;
- typedef typename Type::iterator iterator;
- typedef typename Type::codomain_combine codomain_combine;
- typedef typename on_style<Type,Type::fineness>::type on_style_;
- typedef typename on_neutric<Type, codomain_combine,
- absorbs_neutrons<Type>::value>::type on_neutric_;
-
- interval_type inter_val = addend.first;
- if(itl::is_empty(inter_val))
- return prior_;
-
- const codomain_type& co_val = addend.second;
- if(on_neutric_::is_absorbable(co_val))
- return prior_;
-
- std::pair<iterator,bool> insertion
- = informing_insert(object, prior_, inter_val, co_val);
-
- if(insertion.second)
- return on_style_::handle_inserted(object, insertion.first);
- {
- // Detect the first and the end iterator of the collision sequence
- std::pair<iterator,iterator> overlap = object.equal_range(inter_val);
- iterator it_ = overlap.first,
- last_ = prior(overlap.second);
- Interval_Map::insert_main(object, inter_val, co_val, it_, last_);
- return it_;
- }
-}
-
-
-//==============================================================================
-//= Erasure
-//==============================================================================
-
-template<class Type>
-void erase_rest( Type& object,
- typename Type::interval_type& inter_val,
- const typename Type::codomain_type& co_val,
- typename Type::iterator& it_,
- const typename Type::iterator& last_ )
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::iterator iterator;
-
- // For all intervals within loop: it_->first are contained_in inter_val
- while(it_ != last_)
- if(it_->second == co_val)
- object.erase(it_++);
- else it_++;
-
- //erase_rear:
- if(it_->second == co_val)
- {
- interval_type right_resid = left_subtract(it_->first, inter_val);
- if(itl::is_empty(right_resid))
- object.erase(it_);
- else
- const_cast<interval_type&>(it_->first) = right_resid;
- }
-}
-
-template<class Type>
-void erase(Type& object, const typename Type::value_type& minuend)
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::codomain_type codomain_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::iterator iterator;
- typedef typename on_neutric<Type,
- typename Type::codomain_combine,
- absorbs_neutrons<Type>::value>::type
- on_neutric_;
-
- interval_type inter_val = minuend.first;
- if(itl::is_empty(inter_val))
- return;
-
- const codomain_type& co_val = minuend.second;
- if(on_neutric_::is_absorbable(co_val))
- return;
-
- std::pair<iterator,iterator> exterior = object.equal_range(inter_val);
- if(exterior.first == exterior.second)
- return;
-
- iterator first_ = exterior.first, end_ = exterior.second,
- last_ = cyclic_prior(object, end_);
- iterator second_= first_; ++second_;
-
- if(first_ == last_)
- { // [----inter_val----)
- // .....first_==last_.....
- // only for the last there can be a right_resid: a part of *it_ right of minuend
- interval_type right_resid = left_subtract(first_->first, inter_val);
-
- if(first_->second == co_val)
- {
- interval_type left_resid = right_subtract(first_->first, inter_val);
- if(!itl::is_empty(left_resid)) // [----inter_val----)
- { // [left_resid)..first_==last_......
- const_cast<interval_type&>(first_->first) = left_resid;
- if(!itl::is_empty(right_resid))
- object._insert(first_, value_type(right_resid, co_val));
- }
- else if(!itl::is_empty(right_resid))
- const_cast<interval_type&>(first_->first) = right_resid;
- else
- object.erase(first_);
- }
- }
- else
- {
- // first AND NOT last
- if(first_->second == co_val)
- {
- interval_type left_resid = right_subtract(first_->first, inter_val);
- if(itl::is_empty(left_resid))
- object.erase(first_);
- else
- const_cast<interval_type&>(first_->first) = left_resid;
- }
-
- erase_rest(object, inter_val, co_val, second_, last_);
- }
-}
-
-
-//------------------------------------------------------------------------------
-//------------------------------------------------------------------------------
-template<class Type, bool has_set_semantics>
-struct on_codomain_model;
-
-template<class Type>
-struct on_codomain_model<Type, true>
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::codomain_type codomain_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::codomain_combine codomain_combine;
- typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
-
- static void add(Type& intersection, interval_type& common_interval,
- const codomain_type& flip_value, const codomain_type& co_value)
- {
- codomain_type common_value = flip_value;
- inverse_codomain_intersect()(common_value, co_value);
- Interval_Map::add<Type,codomain_combine>
- (intersection, value_type(common_interval, common_value));
- }
-};
-
-template<class Type>
-struct on_codomain_model<Type, false>
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::codomain_type codomain_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::codomain_combine codomain_combine;
-
- static void add(Type& intersection, interval_type& common_interval,
- const codomain_type&, const codomain_type&)
- {
- Interval_Map::add<Type,codomain_combine>
- (intersection, value_type(common_interval,
- neutron<codomain_type>::value()));
- }
-};
-
-
-
} // namespace Interval_Map
}} // namespace itl boost
Modified: sandbox/itl/boost/itl/detail/interval_set_algo.hpp
==============================================================================
--- sandbox/itl/boost/itl/detail/interval_set_algo.hpp (original)
+++ sandbox/itl/boost/itl/detail/interval_set_algo.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -304,7 +304,7 @@
{
typedef typename Type::interval_type interval_type;
interval_type right_interval = Type::key_value(right_);
- object.erase(right_);
+ ((typename Type::base_type&)object).erase(right_); //JODO
const_cast<interval_type&>(Type::key_value(left_))
= hull(Type::key_value(left_), right_interval);
}
@@ -338,10 +338,6 @@
return right_;
}
-
-
-
-
template<class Type>
typename Type::iterator join_left(Type& object, typename Type::iterator& it_)
{
@@ -358,7 +354,6 @@
return it_;
}
-
template<class Type>
typename Type::iterator join_right(Type& object, typename Type::iterator& it_)
{
@@ -376,7 +371,6 @@
return it_;
}
-
template<class Type>
typename Type::iterator join_neighbours(Type& object, typename Type::iterator& it_)
{
@@ -384,7 +378,6 @@
return join_right(object, it_);
}
-
template<class Type>
inline typename Type::iterator
join_under(Type& object, const typename Type::value_type& addend)
Modified: sandbox/itl/boost/itl/functions.hpp
==============================================================================
--- sandbox/itl/boost/itl/functions.hpp (original)
+++ sandbox/itl/boost/itl/functions.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -226,18 +226,14 @@
typename enable_if<is_interval_map<Type>, Type>::type&
add(Type& object, const typename Type::element_type& operand)
{
- typedef typename Type::codomain_combine codomain_combine;
- Interval_Map::add<Type,codomain_combine>(object, make_segment<Type>(operand));
- return object;
+ return object.add(operand);
}
template<class Type>
typename enable_if<is_interval_map<Type>, Type>::type&
add(Type& object, const typename Type::segment_type& operand)
{
- typedef typename Type::codomain_combine codomain_combine;
- Interval_Map::add<Type,codomain_combine>(object, operand);
- return object;
+ return object.add(operand);
}
template<class Type>
@@ -245,8 +241,9 @@
add(Type& object, typename Type::iterator prior_,
const typename Type::segment_type& operand)
{
- typedef typename Type::codomain_combine codomain_combine;
- return Interval_Map::add<Type,codomain_combine>(object, prior_, operand);
+ //CL typedef typename Type::codomain_combine codomain_combine;
+ //CL return Interval_Map::add<Type,codomain_combine>(object, prior_, operand);
+ return object.add(prior_, operand);
}
//------------------------------------------------------------------------------
@@ -421,16 +418,14 @@
typename enable_if<is_interval_map<Type>, Type>::type&
insert(Type& object, const typename Type::element_type& operand)
{
- Interval_Map::insert(object, make_segment<Type>(operand));
- return object;
+ return object.insert(operand);
}
template<class Type>
typename enable_if<is_interval_map<Type>, Type>::type&
insert(Type& object, const typename Type::segment_type& operand)
{
- Interval_Map::insert(object, operand);
- return object;
+ return object.insert(operand);
}
template<class Type>
@@ -438,7 +433,7 @@
insert(Type& object, typename Type::iterator prior,
const typename Type::segment_type& operand)
{
- return Interval_Map::insert(object, prior, operand);
+ return object.insert(prior, operand);
}
//------------------------------------------------------------------------------
@@ -480,59 +475,14 @@
typename enable_if<is_interval_map<Type>, Type>::type&
erase(Type& object, const typename Type::interval_type& minuend)
{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::iterator iterator;
-
- if(itl::is_empty(minuend))
- return object;
-
- std::pair<iterator, iterator> exterior = object.equal_range(minuend);
- if(exterior.first == exterior.second)
- return object;
-
- iterator first_ = exterior.first,
- end_ = exterior.second,
- last_ = prior(end_);
-
- interval_type left_resid = right_subtract(first_->first, minuend);
- interval_type right_resid = left_subtract(last_ ->first, minuend);
-
- if(first_ == last_ )
- if(!itl::is_empty(left_resid))
- {
- const_cast<interval_type&>(first_->first) = left_resid;
- if(!itl::is_empty(right_resid))
- itl::insert(object, first_, value_type(right_resid, first_->second));
- }
- else if(!itl::is_empty(right_resid))
- const_cast<interval_type&>(first_->first) = left_subtract(first_->first, minuend);
- else
- object.erase(first_);
- else
- { // [-------- minuend ---------)
- // [left_resid fst) . . . . [lst right_resid)
- iterator second_= first_; ++second_;
-
- iterator start_ = itl::is_empty(left_resid)? first_: second_;
- iterator stop_ = itl::is_empty(right_resid)? end_ : last_ ;
- object.erase(start_, stop_); //erase [start_, stop_)
-
- if(!itl::is_empty(left_resid))
- const_cast<interval_type&>(first_->first) = left_resid;
-
- if(!itl::is_empty(right_resid))
- const_cast<interval_type&>(last_ ->first) = right_resid;
- }
- return object;
+ return object.erase(minuend);
}
template<class Type>
typename enable_if<is_interval_map<Type>, Type>::type&
erase(Type& object, const typename Type::domain_type& minuend)
{
- typedef typename Type::interval_type interval_type;
- return itl::erase(object, interval_type(minuend));
+ return object.erase(minuend);
}
//------------------------------------------------------------------------------
@@ -542,15 +492,14 @@
typename enable_if<is_interval_map<Type>, Type>::type&
erase(Type& object, const typename Type::segment_type& minuend)
{
- Interval_Map::erase(object, minuend);
- return object;
+ return object.erase(minuend);
}
template<class Type>
typename enable_if<is_interval_map<Type>, Type>::type&
erase(Type& object, const typename Type::element_type& minuend)
{
- return itl::erase(object, make_segment<Type>(minuend));
+ return object.erase(minuend);
}
//------------------------------------------------------------------------------
@@ -601,34 +550,12 @@
//- Subtraction<Interval_Map> fragment_types
//------------------------------------------------------------------------------
template<class Type>
-typename enable_if
- <mpl::and_< is_interval_map<Type>
- , mpl::and_< is_total<Type>
- , has_inverse<typename Type::codomain_type> >
- >,
- Type>::type&
-subtract(Type& object, const typename Type::segment_type& operand)
-{
- typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
- Interval_Map::add<Type,inverse_codomain_combine>(object, operand);
- return object;
-}
-
-template<class Type>
-typename enable_if
- <mpl::and_< is_interval_map<Type>
- , mpl::not_<mpl::and_< is_total<Type>
- , has_inverse<typename Type::codomain_type> > >
- >,
- Type>::type&
+typename enable_if<is_interval_map<Type>, Type>::type&
subtract(Type& object, const typename Type::segment_type& operand)
{
- typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
- Interval_Map::subtract<Type,inverse_codomain_combine>(object, operand);
- return object;
+ return object.subtract(operand);
}
-
template<class Type>
typename enable_if<is_interval_map<Type>, Type>::type&
subtract(Type& object, const typename Type::element_type& operand)
@@ -644,17 +571,14 @@
typename enable_if<is_interval_map<Type>, Type>::type&
subtract(Type& object, const typename Type::domain_type& operand)
{
- typedef typename Type::interval_type interval_type;
- Interval_Map::erase(object, interval_type(operand));
- return object;
+ return object.erase(operand);
}
template<class Type>
typename enable_if<is_interval_map<Type>, Type>::type&
subtract(Type& object, const typename Type::interval_type& operand)
{
- Interval_Map::erase(object, operand);
- return object;
+ return object.erase(operand);
}
@@ -786,7 +710,7 @@
{
interval_type common_interval = Type::key_value(it_) & segment;
if(!itl::is_empty(common_interval))
- prior_ = section._insert(prior_, common_interval);
+ prior_ = section.insert(prior_, common_interval);
}
}
@@ -813,58 +737,44 @@
//------------------------------------------------------------------------------
-//- Intersection add_intersection<IntervalMaps> for key_types
+//- Intersection add_intersection<IntervalMaps> for fragment_types
//------------------------------------------------------------------------------
-template<class Type, class OperandT>
-typename enable_if<mpl::and_< is_total<Type>
- , is_interval_map_fragment_type_of<OperandT, Type> >, void>::type
-add_intersection(Type& section, const Type& object, const OperandT& operand)
+template<class Type>
+typename enable_if<is_interval_map<Type>, void>::type
+add_intersection(Type& section, const Type& object,
+ const typename Type::element_type& operand)
{
- section += object;
- section += operand;
+ object.add_intersection(section, operand);
}
template<class Type>
-typename enable_if<mpl::and_< mpl::not_<is_total<Type> >, is_interval_map<Type> >, void>::type
-add_intersection(Type& section, const Type& object, const typename Type::element_type& operand)
+typename enable_if<is_interval_map<Type>, void>::type
+add_intersection(Type& section, const Type& object,
+ const typename Type::segment_type& operand)
{
- add_intersection(section, object, make_segment<Type>(operand));
+ object.add_intersection(section, operand);
}
-template<class Type>
-typename enable_if<mpl::and_< mpl::not_<is_total<Type> >, is_interval_map<Type> >, void>::type
-add_intersection(Type& section, const Type& object, const typename Type::segment_type& operand)
+template<class Type, class MapT>
+typename enable_if
+<
+ mpl::and_< is_total<Type>
+ , is_concept_compatible<is_interval_map, Type, MapT> >
+ , void
+>::type
+add_intersection(Type& section, const Type& object, const MapT& operand)
{
- typedef typename Type::segment_type segment_type;
- typedef typename Type::interval_type interval_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::const_iterator const_iterator;
- typedef typename Type::codomain_combine codomain_combine;
- typedef typename Type::codomain_intersect codomain_intersect;
-
- interval_type inter_val = operand.first;
- if(itl::is_empty(inter_val))
- return;
-
- std::pair<const_iterator, const_iterator> exterior
- = object.equal_range(inter_val);
- if(exterior.first == exterior.second)
- return;
-
- for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
- {
- interval_type common_interval = it_->first & inter_val;
- if(!itl::is_empty(common_interval))
- {
- Interval_Map::add<Type,codomain_combine> (section, value_type(common_interval, it_->second) );
- Interval_Map::add<Type,codomain_intersect>(section, value_type(common_interval, operand.second));
- }
- }
+ section += object;
+ section += operand;
}
template<class Type, class MapT>
-typename enable_if<mpl::and_< mpl::not_<is_total<Type> >
- , is_concept_compatible<is_interval_map, Type, MapT> >, void>::type
+typename enable_if
+<
+ mpl::and_< mpl::not_<is_total<Type> >
+ , is_concept_compatible<is_interval_map, Type, MapT> >
+ , void
+>::type
add_intersection(Type& section, const Type& object, const MapT& operand)
{
typedef typename Type::segment_type segment_type;
@@ -882,7 +792,7 @@
}
//------------------------------------------------------------------------------
-//- Intersection add_intersection<IntervalMaps> for fragment_types
+//- Intersection add_intersection<IntervalMaps> for key_types
//------------------------------------------------------------------------------
template<class Type>
@@ -1041,56 +951,51 @@
//------------------------------------------------------------------------------
-#ifdef BOOST_MSVC
-#pragma warning(push)
-#pragma warning(disable:4127) // conditional expression is constant
-#endif
-
template<class LeftT, class RightT>
-typename enable_if<is_intra_combinable<LeftT, RightT>,
- bool>::type
+typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
+ , mpl::or_<is_total<LeftT>, is_total<RightT> > >
+ , bool>::type
intersects(const LeftT& left, const RightT& right)
{
- if(mpl::or_<is_total<LeftT>, is_total<RightT> >::value)
- return true;
+ return true;
+}
+template<class LeftT, class RightT>
+typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
+ , mpl::not_<mpl::or_< is_total<LeftT>
+ , is_total<RightT> > > >
+ , bool>::type
+intersects(const LeftT& left, const RightT& right)
+{
+ typedef typename RightT::const_iterator const_iterator;
LeftT intersection;
- typename RightT::const_iterator right_common_lower_;
- typename RightT::const_iterator right_common_upper_;
-
+ const_iterator right_common_lower_, right_common_upper_;
if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
return false;
- typename RightT::const_iterator it_ = right_common_lower_;
+ const_iterator it_ = right_common_lower_;
while(it_ != right_common_upper_)
{
itl::add_intersection(intersection, left, *it_++);
if(!itl::is_empty(intersection))
return true;
}
-
return false;
}
-#ifdef BOOST_MSVC
-#pragma warning(pop)
-#endif
-
template<class LeftT, class RightT>
-typename enable_if<is_cross_combinable<LeftT, RightT>,
- bool>::type
+typename enable_if<is_cross_combinable<LeftT, RightT>, bool>::type
intersects(const LeftT& left, const RightT& right)
{
+ typedef typename RightT::const_iterator const_iterator;
LeftT intersection;
if(itl::is_empty(left) || itl::is_empty(right))
return false;
- typename RightT::const_iterator right_common_lower_;
- typename RightT::const_iterator right_common_upper_;
-
+ const_iterator right_common_lower_, right_common_upper_;
if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
return false;
@@ -1224,115 +1129,56 @@
//------------------------------------------------------------------------------
//- Symmetric difference flip<Interval_Map> fragment_types
//------------------------------------------------------------------------------
-template<class Type, class OperandT>
-typename enable_if< mpl::and_< is_interval_map_right_intra_combinable<Type, OperandT> //JODO =^= fragment_type_of
- , is_total<Type>
- , absorbs_neutrons<Type> >
- , Type >::type&
-flip(Type& object, const OperandT&)
+//JODO NOTE: typename enable_if< mpl::and_< is_interval_map_right_intra_combinable<Type, OperandT> //JODO =^= fragment_type_of
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+flip(Type& object, const typename Type::element_type& operand)
{
- itl::clear(object);
- return object;
+ return object.flip(operand);
}
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+flip(Type& object, const typename Type::segment_type& operand)
+{
+ return object.flip(operand);
+}
template<class Type, class OperandT>
-typename enable_if< mpl::and_< is_interval_map_right_intra_combinable<Type, OperandT>
- , is_total<Type>
- , mpl::not_<absorbs_neutrons<Type> > >
- , Type >::type&
+typename enable_if< mpl::and_< is_total<Type>
+ , absorbs_neutrons<Type>
+ , is_concept_compatible<is_interval_map,
+ Type, OperandT >
+ >
+ , Type>::type&
flip(Type& object, const OperandT& operand)
{
- typedef typename Type::codomain_type codomain_type;
- object += operand;
- ITL_FORALL(typename Type, it_, object) //JODO: neutralisierendes add.
- it_->second = neutron<codomain_type>::value();
-
- if(mpl::not_<is_interval_splitter<Type> >::value) //JODO
- itl::join(object);
-
+ object.clear();
return object;
}
-
-template<class Type>
-typename enable_if<mpl::and_< is_interval_map<Type>
- , mpl::not_<is_total<Type> > >, Type>::type&
-flip(Type& object, const typename Type::segment_type& interval_value_pair)
+template<class Type, class OperandT>
+typename enable_if< mpl::and_< is_total<Type>
+ , mpl::not_<absorbs_neutrons<Type> >
+ , is_concept_compatible<is_interval_map,
+ Type, OperandT >
+ >
+ , Type>::type&
+flip(Type& object, const OperandT& operand)
{
- typedef typename Type::set_type set_type;
- typedef typename Type::interval_type interval_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::const_iterator const_iterator;
typedef typename Type::codomain_type codomain_type;
- typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
- // That which is common shall be subtracted
- // That which is not shall be added
- // So interval_value_pair has to be 'complementary added' or flipped
-
- interval_type span = interval_value_pair.first;
- std::pair<const_iterator, const_iterator> exterior
- = object.equal_range(span);
-
- const_iterator first_ = exterior.first;
- const_iterator end_ = exterior.second;
-
- interval_type covered, left_over, common_interval;
- const codomain_type& x_value = interval_value_pair.second;
- const_iterator it_ = first_;
-
- set_type eraser;
- Type intersection;
-
- while(it_ != end_ )
- {
- const codomain_type& co_value = it_->second;
- covered = (*it_++).first;
- //[a ... : span
- // [b ... : covered
- //[a b) : left_over
- left_over = right_subtract(span, covered);
-
- //That which is common ...
- common_interval = span & covered;
- if(!itl::is_empty(common_interval))
- {
- // ... shall be subtracted
- itl::add(eraser, common_interval);
-
- Interval_Map::on_codomain_model<Type, has_set_semantics<codomain_type>::value>
- ::add(intersection, common_interval, x_value, co_value);
- }
- itl::add(object, value_type(left_over, x_value)); //That which is not shall be added
- // Because this is a collision free addition I don't have to distinguish codomain_types.
-
- //... 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
- itl::add(object, value_type(span, x_value));
+ object += operand;
+ ITL_FORALL(typename Type, it_, object) //JODO: neutralisierendes add.
+ it_->second = neutron<codomain_type>::value();
- //finally rewrite the common segments
- itl::erase(object, eraser);
- object += intersection;
+ if(mpl::not_<is_interval_splitter<Type> >::value) //JODO
+ itl::join(object);
return object;
}
-template<class Type>
-typename enable_if<mpl::and_< is_interval_map<Type>
- , mpl::not_<is_total<Type> > >, Type>::type&
-flip(Type& object, const typename Type::element_type& key_value_pair)
-{
- return itl::flip(object, make_segment<Type>(key_value_pair));
-}
-
-
-
template<class Type, class OperandT>
typename enable_if< mpl::and_< mpl::not_<is_total<Type> >
, is_concept_compatible<is_interval_map,
Modified: sandbox/itl/boost/itl/interval_base_map.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_base_map.hpp (original)
+++ sandbox/itl/boost/itl/interval_base_map.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -17,11 +17,14 @@
#include <boost/itl/detail/notate.hpp>
#include <boost/itl/detail/design_config.hpp>
+#include <boost/itl/detail/on_neutric.hpp> //JODO rename
#include <boost/itl/type_traits/is_interval_splitter.hpp>
#include <boost/itl/map.hpp>
#include <boost/itl/interval_base_set.hpp>
#include <boost/itl/detail/interval_map_algo.hpp>
+#include <boost/mpl/bool.hpp> //CL
+
#define const_FOR_IMPLMAP(iter) for(typename ImplMapT::const_iterator iter=_map.begin(); (iter)!=_map.end(); (iter)++)
#define FOR_IMPLMAP(iter) for(typename ImplMapT::iterator iter=_map.begin(); (iter)!=_map.end(); (iter)++)
@@ -199,9 +202,15 @@
/// element const reverse iterator: Depreciated, see documentation.
typedef boost::itl::element_iterator<const_reverse_iterator> element_const_reverse_iterator;
+ typedef typename on_neutric<type, codomain_combine,
+ Traits::absorbs_neutrons>::type on_codomain_absorbtion;
+
public:
- enum { is_itl_container = true };
- enum { fineness = 0 };
+ BOOST_STATIC_CONSTANT(bool,
+ is_total_invertible = ( Traits::is_total
+ && has_inverse<codomain_type>::value));
+
+ BOOST_STATIC_CONSTANT(int, fineness = 0);
public:
//==========================================================================
@@ -331,13 +340,15 @@
/** Addition of a key value pair to the map */
SubType& add(const element_type& key_value_pair)
{
- return itl::add(*that(), key_value_pair);
+ return add(make_segment(key_value_pair));
}
/** Addition of an interval value pair to the map. */
SubType& add(const segment_type& interval_value_pair)
{
- return itl::add(*that(), interval_value_pair);
+ //CL return itl::add(*that(), interval_value_pair);
+ this->template _add<codomain_combine>(interval_value_pair);
+ return *that();
}
/** Addition of an interval value pair \c interval_value_pair to the map.
@@ -345,7 +356,8 @@
inserted after. */
iterator add(iterator prior_, const segment_type& interval_value_pair)
{
- return itl::add(*that(), prior_, interval_value_pair);
+ //CL return itl::add(*that(), prior_, interval_value_pair);
+ return this->template _add<codomain_combine>(prior_, interval_value_pair);
}
//==========================================================================
@@ -355,39 +367,42 @@
/** Subtraction of a key value pair from the map */
SubType& subtract(const element_type& key_value_pair)
{
- return itl::subtract(*that(), key_value_pair);
+ return subtract(make_segment(key_value_pair));
}
/** Subtraction of an interval value pair from the map. */
SubType& subtract(const segment_type& interval_value_pair)
{
- return itl::subtract(*that(), interval_value_pair);
+ on_invertible<type, is_total_invertible>
+ ::subtract(*that(), interval_value_pair);
+ return *that();
}
//==========================================================================
//= Insertion
//==========================================================================
- std::pair<iterator,bool> _insert(const value_type& value_pair){ return _map.insert(value_pair); }
- iterator _insert(iterator prior, const value_type& value_pair){ return _map.insert(prior, value_pair); }
+ std::pair<iterator,bool> _insert(const value_type& value_pair){ return _map.insert(value_pair); } //CL
+ iterator _insert(iterator prior, const value_type& value_pair){ return _map.insert(prior, value_pair); } //CL
/** Insertion of a \c key_value_pair into the map. */
SubType& insert(const element_type& key_value_pair)
{
- return itl::insert(*that(), key_value_pair);
+ return insert(make_segment(key_value_pair));
}
/** Insertion of an \c interval_value_pair into the map. */
SubType& insert(const segment_type& interval_value_pair)
{
- return itl::insert(*that(), interval_value_pair);
+ _insert(interval_value_pair);
+ return *that();
}
/** Insertion of an \c interval_value_pair into the map. Iterator \c prior_.
serves as a hint to insert after the element \c prior point to. */
iterator insert(iterator prior, const segment_type& interval_value_pair)
{
- return itl::insert(*that(), prior, interval_value_pair);
+ return _insert(prior, interval_value_pair);
}
/** With <tt>key_value_pair = (k,v)</tt> set value \c v for key \c k */
@@ -408,22 +423,51 @@
//= Erasure
//==========================================================================
- template<class CoType>
- SubType& erase(const CoType& operand)
- {
- return itl::erase(*that(), operand);
+ /** Erase a \c key_value_pair from the map. */
+ SubType& erase(const element_type& key_value_pair)
+ {
+ erase(make_segment(key_value_pair));
+ return *that();
}
+ /** Erase an \c interval_value_pair from the map. */
+ SubType& erase(const segment_type& interval_value_pair);
+
+ /** Erase a key value pair for \c key. */
+ SubType& erase(const domain_type& key)
+ {
+ return erase(interval_type(key));
+ }
+
+ /** Erase all value pairs within the range of the
+ interval <tt>inter_val</tt> from the map. */
+ SubType& erase(const interval_type& inter_val);
+
+
/** Erase all value pairs within the range of the interval that iterator
\c position points to. */
- void erase(iterator position){ _map.erase(position); }
+ void erase(iterator position){ this->_map.erase(position); }
/** Erase all value pairs for a range of iterators <tt>[first,past)</tt>. */
- void erase(iterator first, iterator past){ _map.erase(first, past); }
+ void erase(iterator first, iterator past){ this->_map.erase(first, past); }
//==========================================================================
//= Intersection
//==========================================================================
+
+ /** The intersection of \c key_value_pair and \c *this map is added to \c section. */
+ void add_intersection(SubType& section, const element_type& key_value_pair)const
+ {
+ add_intersection(section, make_segment(key_value_pair));
+ }
+
+ /** The intersection of \c interval_value_pair and \c *this map is added to \c section. */
+ void add_intersection(SubType& section, const segment_type& interval_value_pair)const
+ {
+ on_definedness<SubType, Traits::is_total>
+ ::add_intersection(section, *that(), interval_value_pair);
+ }
+
/** Returns \c true, if element \c key is found in \c *this map.
Complexity: logarithmic. */
bool intersects(const domain_type& key)const
@@ -459,13 +503,15 @@
/** If \c *this map contains \c key_value_pair it is erased, otherwise it is added. */
SubType& flip(const element_type& key_value_pair)
{
- return itl::flip(*that(), key_value_pair);
+ return flip(make_segment(key_value_pair));
}
/** If \c *this map contains \c interval_value_pair it is erased, otherwise it is added. */
SubType& flip(const segment_type& interval_value_pair)
{
- return itl::flip(*that(), interval_value_pair);
+ return
+ on_total_absorbable<SubType, Traits::is_total, Traits::absorbs_neutrons>
+ ::flip(*that(), interval_value_pair);
}
//==========================================================================
@@ -516,19 +562,858 @@
static value_type make_value(const key_type& key_value, const codomain_type& codom_val)
{ return value_type(key_value, codom_val); }
+ static segment_type make_segment(const element_type& element)
+ { return segment_type(interval_type(element.key), element.data); }
+
+private:
+ template<class Combiner>
+ iterator _add(const segment_type& interval_value_pair);
+
+ template<class Combiner>
+ iterator _add(iterator prior_, const segment_type& interval_value_pair);
+
+ template<class Combiner>
+ void _subtract(const segment_type& interval_value_pair);
+
+ iterator _insert(const segment_type& interval_value_pair);
+ iterator _insert(iterator prior_, const segment_type& interval_value_pair);
+
+private:
+ template<class Combiner>
+ void add_segment(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
+
+ template<class Combiner>
+ void add_main(interval_type& inter_val, const CodomainT& co_val,
+ iterator& it_, const iterator& last_);
+
+ template<class Combiner>
+ void add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
+
+ void add_front(const interval_type& inter_val, iterator& first_);
+
+private:
+ void subtract_front(const interval_type& inter_val, iterator& first_);
+
+ template<class Combiner>
+ void subtract_main(const CodomainT& co_val, iterator& it_, const iterator& last_);
+
+ template<class Combiner>
+ void subtract_rear(interval_type& inter_val, const CodomainT& co_val, iterator& it_);
+
+private:
+ void insert_main(const interval_type&, const CodomainT&, iterator&, const iterator&);
+ void erase_rest ( interval_type&, const CodomainT&, iterator&, const iterator&);
+
+ template<class FragmentT>
+ void total_add_intersection(SubType& section, const FragmentT& fragment)const
+ {
+ section += *that();
+ section.add(fragment);
+ }
+
+ void partial_add_intersection(SubType& section, const segment_type& operand)const
+ {
+ interval_type inter_val = operand.first;
+ if(itl::is_empty(inter_val))
+ return;
+
+ std::pair<const_iterator, const_iterator> exterior
+ = this->_map.equal_range(inter_val);
+ if(exterior.first == exterior.second)
+ return;
+
+ for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
+ {
+ interval_type common_interval = it_->first & inter_val;
+ if(!itl::is_empty(common_interval))
+ {
+ section.template _add<codomain_combine> (value_type(common_interval, it_->second) );
+ section.template _add<codomain_intersect>(value_type(common_interval, operand.second));
+ }
+ }
+ }
+
+ void partial_add_intersection(SubType& section, const element_type& operand)const
+ {
+ partial_add_intersection(section, make_segment(operand));
+ }
+
+
+protected:
+
+ template <class Combiner>
+ iterator gap_insert(iterator prior_, const interval_type& inter_val,
+ const codomain_type& co_val )
+ {
+ // inter_val is not conained in this map. Insertion will be successful
+ BOOST_ASSERT(this->_map.find(inter_val) == this->_map.end());
+ BOOST_ASSERT((!on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(co_val)));
+ return this->_map.insert(prior_, value_type(inter_val, version<Combiner>()(co_val)));
+ }
+
+ template <class Combiner>
+ std::pair<iterator, bool>
+ add_at(const iterator& prior_, const interval_type& inter_val,
+ const codomain_type& co_val )
+ {
+ // Never try to insert a neutron into a neutron absorber here:
+ BOOST_ASSERT((!(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(co_val))));
+
+ iterator inserted_
+ = this->_map.insert(prior_, value_type(inter_val, Combiner::neutron()));
+
+ if(inserted_->first == inter_val && inserted_->second == Combiner::neutron())
+ {
+ Combiner()(inserted_->second, co_val);
+ return std::pair<iterator,bool>(inserted_, true);
+ }
+ else
+ return std::pair<iterator,bool>(inserted_, false);
+ }
+
+ std::pair<iterator, bool>
+ insert_at(const iterator& prior_, const interval_type& inter_val,
+ const codomain_type& co_val )
+ {
+ iterator inserted_
+ = this->_map.insert(prior_, value_type(inter_val, co_val));
+
+ if(inserted_ == prior_)
+ return std::pair<iterator,bool>(inserted_, false);
+ else if(inserted_->first == inter_val)
+ return std::pair<iterator,bool>(inserted_, true);
+ else
+ return std::pair<iterator,bool>(inserted_, false);
+ }
+
+
protected:
sub_type* that() { return static_cast<sub_type*>(this); }
const sub_type* that()const { return static_cast<const sub_type*>(this); }
protected:
ImplMapT _map;
+
+
+private:
+ //--------------------------------------------------------------------------
+ template<class Type, bool is_total_invertible>
+ struct on_invertible;
+
+ template<class Type>
+ struct on_invertible<Type, true>
+ {
+ typedef typename Type::segment_type segment_type;
+ typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
+
+ static void subtract(Type& object, const segment_type& operand)
+ { object.template _add<inverse_codomain_combine>(operand); }
+ };
+
+ template<class Type>
+ struct on_invertible<Type, false>
+ {
+ typedef typename Type::segment_type segment_type;
+ typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
+
+ static void subtract(Type& object, const segment_type& operand)
+ { object.template _subtract<inverse_codomain_combine>(operand); }
+ };
+
+ friend struct on_invertible<type, true>;
+ friend struct on_invertible<type, false>;
+ //--------------------------------------------------------------------------
+
+ //--------------------------------------------------------------------------
+ template<class Type, bool is_total>
+ struct on_definedness;
+
+ template<class Type>
+ struct on_definedness<Type, true>
+ {
+ static void add_intersection(Type& section, const Type& object,
+ const segment_type& operand)
+ { object.total_add_intersection(section, operand); }
+ };
+
+ template<class Type>
+ struct on_definedness<Type, false>
+ {
+ static void add_intersection(Type& section, const Type& object,
+ const segment_type& operand)
+ { object.partial_add_intersection(section, operand); }
+ };
+
+ friend struct on_definedness<type, true>;
+ friend struct on_definedness<type, false>;
+ //--------------------------------------------------------------------------
+
+ //--------------------------------------------------------------------------
+ template<class Type, bool has_set_semantics>
+ struct on_codomain_model;
+
+ template<class Type>
+ struct on_codomain_model<Type, true>
+ {
+ typedef typename Type::interval_type interval_type;
+ typedef typename Type::codomain_type codomain_type;
+ typedef typename Type::segment_type segment_type;
+ typedef typename Type::codomain_combine codomain_combine;
+ typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
+
+ static void add(Type& intersection, interval_type& common_interval,
+ const codomain_type& flip_value, const codomain_type& co_value)
+ {
+ codomain_type common_value = flip_value;
+ inverse_codomain_intersect()(common_value, co_value);
+ intersection.template
+ _add<codomain_combine>(segment_type(common_interval, common_value));
+ }
+ };
+
+ template<class Type>
+ struct on_codomain_model<Type, false>
+ {
+ typedef typename Type::interval_type interval_type;
+ typedef typename Type::codomain_type codomain_type;
+ typedef typename Type::segment_type segment_type;
+ typedef typename Type::codomain_combine codomain_combine;
+
+ static void add(Type& intersection, interval_type& common_interval,
+ const codomain_type&, const codomain_type&)
+ {
+ intersection.template
+ _add<codomain_combine>(segment_type(common_interval,
+ neutron<codomain_type>::value()));
+ }
+ };
+
+ friend struct on_codomain_model<type, true>;
+ friend struct on_codomain_model<type, false>;
+ //--------------------------------------------------------------------------
+
+
+ //--------------------------------------------------------------------------
+ template<class Type, bool is_total, bool absorbs_neutrons>
+ struct on_total_absorbable;
+
+ template<class Type>
+ struct on_total_absorbable<Type, true, true>
+ {
+ static Type& flip(Type& object, const typename Type::segment_type& operand)
+ { itl::clear(object); return object; }
+ };
+
+ template<class Type>
+ struct on_total_absorbable<Type, true, false>
+ {
+ typedef typename Type::segment_type segment_type;
+ typedef typename Type::codomain_type codomain_type;
+
+ static Type& flip(Type& object, const segment_type& operand)
+ {
+ object += operand;
+ ITL_FORALL(typename Type, it_, object) //JODO: neutralisierendes add.
+ it_->second = neutron<codomain_type>::value();
+
+ if(mpl::not_<is_interval_splitter<Type> >::value) //JODO
+ itl::join(object);
+
+ return object;
+ }
+ };
+
+ template<class Type, bool absorbs_neutrons>
+ struct on_total_absorbable<Type, false, absorbs_neutrons>
+ {
+ typedef typename Type::segment_type segment_type;
+ typedef typename Type::codomain_type codomain_type;
+ typedef typename Type::interval_type interval_type;
+ typedef typename Type::value_type value_type;
+ typedef typename Type::const_iterator const_iterator;
+ typedef typename Type::set_type set_type;
+ typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
+
+ static Type& flip(Type& object, const segment_type& interval_value_pair)
+ {
+ // That which is common shall be subtracted
+ // That which is not shall be added
+ // So interval_value_pair has to be 'complementary added' or flipped
+ interval_type span = interval_value_pair.first;
+ std::pair<const_iterator, const_iterator> exterior
+ = object.equal_range(span);
+
+ const_iterator first_ = exterior.first;
+ const_iterator end_ = exterior.second;
+
+ interval_type covered, left_over, common_interval;
+ const codomain_type& x_value = interval_value_pair.second;
+ const_iterator it_ = first_;
+
+ set_type eraser;
+ Type intersection;
+
+ while(it_ != end_ )
+ {
+ const codomain_type& co_value = it_->second;
+ covered = (*it_++).first;
+ //[a ... : span
+ // [b ... : covered
+ //[a b) : left_over
+ left_over = right_subtract(span, covered);
+
+ //That which is common ...
+ common_interval = span & covered;
+ if(!itl::is_empty(common_interval))
+ {
+ // ... shall be subtracted
+ itl::add(eraser, common_interval);
+
+ on_codomain_model<Type, has_set_semantics<codomain_type>::value>
+ ::add(intersection, common_interval, x_value, co_value);
+ }
+
+ itl::add(object, value_type(left_over, x_value)); //That which is not shall be added
+ // Because this is a collision free addition I don't have to distinguish codomain_types.
+
+ //... 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
+ itl::add(object, value_type(span, x_value));
+
+ //finally rewrite the common segments
+ itl::erase(object, eraser);
+ object += intersection;
+ return object;
+ }
+ };
+ //--------------------------------------------------------------------------
} ;
+//==============================================================================
+//= Addition detail
+//==============================================================================
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::add_front(const interval_type& inter_val, iterator& first_)
+{
+ // 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(first_), inter_val);
+
+ if(!itl::is_empty(left_resid))
+ { // [------------ . . .
+ // [left_resid---first_ --- . . .
+ iterator prior_ = cyclic_prior(*this, first_);
+ const_cast<interval_type&>(key_value(first_))
+ = left_subtract(key_value(first_), left_resid);
+ //NOTE: Only splitting
+ this->_map.insert(prior_, make_value(left_resid, co_value(first_)));
+ }
+ //POST:
+ // [----- inter_val ---- . . .
+ // ...[-- first_ --...
+}
+
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+ template<class Combiner>
+inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::add_segment(const interval_type& inter_val, const CodomainT& co_val, iterator& it_)
+{
+ interval_type lead_gap = right_subtract(inter_val, it_->first);
+ if(!itl::is_empty(lead_gap))
+ {
+ // [lead_gap--- . . .
+ // [-- it_ ...
+ iterator prior_ = prior(it_);
+ iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val);
+ that()->handle_inserted(prior_, inserted_);
+ }
+
+ // . . . --------- . . . addend interval
+ // [-- it_ --) has a common part with the first overval
+ Combiner()(it_->second, co_val);
+ that()->template handle_left_combined<Combiner>(it_++);
+}
+
+
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+ template<class Combiner>
+inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::add_main(interval_type& inter_val, const CodomainT& co_val,
+ iterator& it_, const iterator& last_)
+{
+ interval_type cur_interval;
+ while(it_!=last_)
+ {
+ cur_interval = it_->first ;
+ add_segment<Combiner>(inter_val, co_val, it_);
+ // shrink interval
+ inter_val = left_subtract(inter_val, cur_interval);
+ }
+}
+
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+ template<class Combiner>
+inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_)
+{
+ iterator prior_ = cyclic_prior(*that(), it_);
+ interval_type cur_itv = it_->first ;
+
+ interval_type lead_gap = right_subtract(inter_val, cur_itv);
+ if(!itl::is_empty(lead_gap))
+ { // [lead_gap--- . . .
+ // [prior) [-- it_ ...
+ iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val);
+ that()->handle_inserted(prior_, inserted_);
+ }
+
+ interval_type end_gap = left_subtract(inter_val, cur_itv);
+ if(!itl::is_empty(end_gap))
+ {
+ // [----------------end_gap)
+ // . . . -- it_ --)
+ Combiner()(it_->second, co_val);
+ that()->template gap_insert_at<Combiner>(it_, prior_, end_gap, co_val);
+ }
+ else
+ {
+ // only for the last there can be a right_resid: a part of *it_ right of x
+ interval_type right_resid = left_subtract(cur_itv, inter_val);
+
+ if(itl::is_empty(right_resid))
+ {
+ // [---------------)
+ // [-- it_ ---)
+ Combiner()(it_->second, co_val);
+ that()->template handle_preceeded_combined<Combiner>(prior_, it_);
+ }
+ else
+ {
+ // [--------------)
+ // [-- it_ --right_resid)
+ const_cast<interval_type&>(it_->first) = right_subtract(it_->first, right_resid);
+
+ //NOTE: This is NOT an insertion that has to take care for correct application of
+ // the Combiner functor. It only reestablished that state after splitting the
+ // 'it_' interval value pair. Using _map_insert<Combiner> does not work here.
+ iterator insertion_ = this->_map.insert(it_, value_type(right_resid, it_->second));
+ that()->handle_reinserted(insertion_);
+
+ Combiner()(it_->second, co_val);
+ that()->template handle_preceeded_combined<Combiner>(insertion_, it_);
+ }
+ }
+}
+
+
+//==============================================================================
+//= Addition
+//==============================================================================
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+ template<class Combiner>
+inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
+ interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::_add(const segment_type& addend)
+{
+ typedef typename on_neutric<type,Combiner,
+ absorbs_neutrons<type>::value>::type on_neutric_;
+
+ const interval_type& inter_val = addend.first;
+ if(itl::is_empty(inter_val))
+ return this->_map.end();
+
+ const codomain_type& co_val = addend.second;
+ if(on_neutric_::is_absorbable(co_val))
+ return this->_map.end();
+
+ std::pair<iterator,bool> insertion
+ = this->_map.insert(value_type(inter_val, version<Combiner>()(co_val)));
+
+ if(insertion.second)
+ return that()->handle_inserted(insertion.first);
+ else
+ {
+ // Detect the first and the end iterator of the collision sequence
+ iterator first_ = this->_map.lower_bound(inter_val),
+ last_ = insertion.first;
+ //assert(end_ == this->_map.upper_bound(inter_val));
+ iterator it_ = first_;
+ interval_type rest_interval = inter_val;
+
+ add_front (rest_interval, it_ );
+ add_main<Combiner>(rest_interval, co_val, it_, last_);
+ add_rear<Combiner>(rest_interval, co_val, it_ );
+ return it_;
+ }
+}
+
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+ template<class Combiner>
+inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
+ interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::_add(iterator prior_, const segment_type& addend)
+{
+ typedef typename on_neutric<type,Combiner,
+ absorbs_neutrons<type>::value>::type on_neutric_;
+
+ const interval_type& inter_val = addend.first;
+ if(itl::is_empty(inter_val))
+ return prior_;
+
+ const codomain_type& co_val = addend.second;
+ if(on_neutric_::is_absorbable(co_val))
+ return prior_;
+
+ std::pair<iterator,bool> insertion
+ = add_at<Combiner>(prior_, inter_val, co_val);
+
+ if(insertion.second)
+ return that()->handle_inserted(insertion.first);
+ else
+ {
+ // Detect the first and the end iterator of the collision sequence
+ std::pair<iterator,iterator> overlap = this->_map.equal_range(inter_val);
+ iterator it_ = overlap.first,
+ last_ = prior(overlap.second);
+ interval_type rest_interval = inter_val;
+
+ add_front (rest_interval, it_ );
+ add_main<Combiner>(rest_interval, co_val, it_, last_);
+ add_rear<Combiner>(rest_interval, co_val, it_ );
+ return it_;
+ }
+}
+
+//==============================================================================
+//= Subtraction detail
+//==============================================================================
+
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::subtract_front(const interval_type& inter_val, iterator& it_)
+{
+ interval_type left_resid = right_subtract(it_->first, inter_val);
+
+ if(!itl::is_empty(left_resid)) // [--- inter_val ---)
+ { //[prior_) [left_resid)[--- it_ . . .
+ iterator prior_ = cyclic_prior(*this, it_);
+ const_cast<interval_type&>(it_->first) = left_subtract(it_->first, left_resid);
+ this->_map.insert(prior_, value_type(left_resid, it_->second));
+ // The segemnt *it_ is split at inter_val.first(), so as an invariant
+ // segment *it_ is always "under" inter_val and a left_resid is empty.
+ }
+}
+
+
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+ template<class Combiner>
+inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::subtract_main(const CodomainT& co_val, iterator& it_, const iterator& last_)
+{
+ while(it_ != last_)
+ {
+ Combiner()(it_->second, co_val);
+ that()->template handle_left_combined<Combiner>(it_++);
+ }
+}
+
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+ template<class Combiner>
+inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::subtract_rear(interval_type& inter_val, const CodomainT& co_val, iterator& it_)
+{
+ interval_type right_resid = left_subtract(it_->first, inter_val);
+
+ if(itl::is_empty(right_resid))
+ {
+ Combiner()(it_->second, co_val);
+ that()->template handle_combined<Combiner>(it_);
+ }
+ else
+ {
+ const_cast<interval_type&>(it_->first) = right_subtract(it_->first, right_resid);
+ iterator next_ = this->_map.insert(it_, value_type(right_resid, it_->second));
+ Combiner()(it_->second, co_val);
+ that()->template handle_succeeded_combined<Combiner>(it_, next_);
+ }
+}
+
+//==============================================================================
+//= Subtraction
+//==============================================================================
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+ template<class Combiner>
+inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::_subtract(const segment_type& minuend)
+{
+ interval_type inter_val = minuend.first;
+ if(itl::is_empty(inter_val))
+ return;
+
+ const codomain_type& co_val = minuend.second;
+ if(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(co_val))
+ return;
+
+ std::pair<iterator, iterator> exterior = this->_map.equal_range(inter_val);
+ if(exterior.first == exterior.second)
+ return;
+
+ iterator last_ = prior(exterior.second);
+ iterator it_ = exterior.first;
+ subtract_front (inter_val, it_ );
+ subtract_main <Combiner>( co_val, it_, last_);
+ subtract_rear <Combiner>(inter_val, co_val, it_ );
+}
+
+//==============================================================================
+//= Insertion
+//==============================================================================
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::insert_main(const interval_type& inter_val, const CodomainT& co_val,
+ iterator& it_, const iterator& last_)
+{
+ iterator end_ = next(last_);
+ iterator prior_ = it_, inserted_;
+ if(prior_ != this->_map.end())
+ --prior_;
+ interval_type rest_interval = inter_val, left_gap, cur_itv;
+ interval_type last_interval = last_ ->first;
+
+ while(it_ != end_ )
+ {
+ cur_itv = it_->first ;
+ left_gap = right_subtract(rest_interval, cur_itv);
+
+ if(!itl::is_empty(left_gap))
+ {
+ inserted_ = this->_map.insert(prior_, value_type(left_gap, co_val));
+ it_ = that()->handle_inserted(inserted_);
+ }
+
+ // shrink interval
+ rest_interval = left_subtract(rest_interval, cur_itv);
+ prior_ = it_;
+ ++it_;
+ }
+
+ //insert_rear(rest_interval, co_val, last_):
+ interval_type end_gap = left_subtract(rest_interval, last_interval);
+ if(!itl::is_empty(end_gap))
+ {
+ inserted_ = this->_map.insert(prior_, value_type(end_gap, co_val));
+ it_ = that()->handle_inserted(inserted_);
+ }
+ else
+ it_ = prior_;
+}
+
+
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
+ interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::_insert(const segment_type& addend)
+{
+ interval_type inter_val = addend.first;
+ if(itl::is_empty(inter_val))
+ return this->_map.end();
+
+ const codomain_type& co_val = addend.second;
+ if(on_codomain_absorbtion::is_absorbable(co_val))
+ return this->_map.end();
+
+ std::pair<iterator,bool> insertion = this->_map.insert(addend);
+
+ if(insertion.second)
+ return that()->handle_inserted(insertion.first);
+ else
+ {
+ // Detect the first and the end iterator of the collision sequence
+ iterator first_ = this->_map.lower_bound(inter_val),
+ last_ = insertion.first;
+ //assert((++last_) == this->_map.upper_bound(inter_val));
+ iterator it_ = first_;
+ insert_main(inter_val, co_val, it_, last_);
+ return it_;
+ }
+}
+
+
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
+ interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::_insert(iterator prior_, const segment_type& addend)
+{
+ interval_type inter_val = addend.first;
+ if(itl::is_empty(inter_val))
+ return prior_;
+
+ const codomain_type& co_val = addend.second;
+ if(on_codomain_absorbtion::is_absorbable(co_val))
+ return prior_;
+
+ std::pair<iterator,bool> insertion = insert_at(prior_, inter_val, co_val);
+
+ if(insertion.second)
+ return that()->handle_inserted(insertion.first);
+ {
+ // Detect the first and the end iterator of the collision sequence
+ std::pair<iterator,iterator> overlap = this->_map.equal_range(inter_val);
+ iterator it_ = overlap.first,
+ last_ = prior(overlap.second);
+ insert_main(inter_val, co_val, it_, last_);
+ return it_;
+ }
+}
+
+//==============================================================================
+//= Erasure segment_type
+//==============================================================================
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::erase_rest(interval_type& inter_val, const CodomainT& co_val,
+ iterator& it_, const iterator& last_)
+{
+ // For all intervals within loop: it_->first are contained_in inter_val
+ while(it_ != last_)
+ if(it_->second == co_val)
+ this->_map.erase(it_++);
+ else it_++;
+
+ //erase_rear:
+ if(it_->second == co_val)
+ {
+ interval_type right_resid = left_subtract(it_->first, inter_val);
+ if(itl::is_empty(right_resid))
+ this->_map.erase(it_);
+ else
+ const_cast<interval_type&>(it_->first) = right_resid;
+ }
+}
+
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline SubType& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::erase(const segment_type& minuend)
+{
+ interval_type inter_val = minuend.first;
+ if(itl::is_empty(inter_val))
+ return *that();
+
+ const codomain_type& co_val = minuend.second;
+ if(on_codomain_absorbtion::is_absorbable(co_val))
+ return *that();
+
+ std::pair<iterator,iterator> exterior = this->_map.equal_range(inter_val);
+ if(exterior.first == exterior.second)
+ return *that();
+
+ iterator first_ = exterior.first, end_ = exterior.second,
+ last_ = cyclic_prior(*this, end_);
+ iterator second_= first_; ++second_;
+
+ if(first_ == last_)
+ { // [----inter_val----)
+ // .....first_==last_.....
+ // only for the last there can be a right_resid: a part of *it_ right of minuend
+ interval_type right_resid = left_subtract(first_->first, inter_val);
+
+ if(first_->second == co_val)
+ {
+ interval_type left_resid = right_subtract(first_->first, inter_val);
+ if(!itl::is_empty(left_resid)) // [----inter_val----)
+ { // [left_resid)..first_==last_......
+ const_cast<interval_type&>(first_->first) = left_resid;
+ if(!itl::is_empty(right_resid))
+ this->_map.insert(first_, value_type(right_resid, co_val));
+ }
+ else if(!itl::is_empty(right_resid))
+ const_cast<interval_type&>(first_->first) = right_resid;
+ else
+ this->_map.erase(first_);
+ }
+ }
+ else
+ {
+ // first AND NOT last
+ if(first_->second == co_val)
+ {
+ interval_type left_resid = right_subtract(first_->first, inter_val);
+ if(itl::is_empty(left_resid))
+ this->_map.erase(first_);
+ else
+ const_cast<interval_type&>(first_->first) = left_resid;
+ }
+
+ erase_rest(inter_val, co_val, second_, last_);
+ }
+
+ return *that();
+}
+
+//==============================================================================
+//= Erasure key_type
+//==============================================================================
+template <class SubType, class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline SubType& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::erase(const interval_type& minuend)
+{
+ if(itl::is_empty(minuend))
+ return *that();
+
+ std::pair<iterator, iterator> exterior = this->_map.equal_range(minuend);
+ if(exterior.first == exterior.second)
+ return *that();
+
+ iterator first_ = exterior.first,
+ end_ = exterior.second,
+ last_ = prior(end_);
+
+ interval_type left_resid = right_subtract(first_->first, minuend);
+ interval_type right_resid = left_subtract(last_ ->first, minuend);
+
+ if(first_ == last_ )
+ if(!itl::is_empty(left_resid))
+ {
+ const_cast<interval_type&>(first_->first) = left_resid;
+ if(!itl::is_empty(right_resid))
+ this->_map.insert(first_, value_type(right_resid, first_->second));
+ }
+ else if(!itl::is_empty(right_resid))
+ const_cast<interval_type&>(first_->first) = left_subtract(first_->first, minuend);
+ else
+ this->_map.erase(first_);
+ else
+ { // [-------- minuend ---------)
+ // [left_resid fst) . . . . [lst right_resid)
+ iterator second_= first_; ++second_;
+
+ iterator start_ = itl::is_empty(left_resid)? first_: second_;
+ iterator stop_ = itl::is_empty(right_resid)? end_ : last_ ;
+ this->_map.erase(start_, stop_); //erase [start_, stop_)
+
+ if(!itl::is_empty(left_resid))
+ const_cast<interval_type&>(first_->first) = left_resid;
+
+ if(!itl::is_empty(right_resid))
+ const_cast<interval_type&>(last_ ->first) = right_resid;
+ }
+
+ return *that();
+}
+
//-----------------------------------------------------------------------------
// type traits
//-----------------------------------------------------------------------------
-
template
<
class SubType,
@@ -576,7 +1461,7 @@
template
<
class SubType,
- class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc
+ class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc
>
struct is_total<itl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
{
Modified: sandbox/itl/boost/itl/interval_base_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_base_set.hpp (original)
+++ sandbox/itl/boost/itl/interval_base_set.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -339,13 +339,14 @@
/** Add a single element \c key to the set */
SubType& add(const element_type& key)
{
- return itl::add(*that(), key);
+ return add(segment_type(key));
}
/** Add an interval of elements \c inter_val to the set */
SubType& add(const segment_type& inter_val)
{
- return itl::add(*that(), inter_val);
+ _add(inter_val);
+ return *that();
}
/** Add an interval of elements \c inter_val to the set. Iterator
@@ -353,7 +354,7 @@
inserted after. */
iterator add(iterator prior_, const segment_type& inter_val)
{
- return itl::add(*that(), prior_, inter_val);
+ return _add(prior_, inter_val);
}
//==========================================================================
@@ -363,14 +364,11 @@
/** Subtract a single element \c key from the set */
SubType& subtract(const element_type& key)
{
- return itl::subtract(*that(), key);
+ return subtract(segment_type(key));
}
/** Subtract an interval of elements \c inter_val from the set */
- SubType& subtract(const segment_type& inter_val)
- {
- return itl::subtract(*that(), inter_val);
- }
+ SubType& subtract(const segment_type& inter_val);
//==========================================================================
//= Insertion, erasure
@@ -383,13 +381,13 @@
/** Insert an element \c key into the set */
SubType& insert(const element_type& key)
{
- return itl::add(*that(), key);
+ return add(key);
}
/** Insert an interval of elements \c inter_val to the set */
SubType& insert(const segment_type& inter_val)
{
- return itl::add(*that(), inter_val);
+ return add(inter_val);
}
/** Insert an interval of elements \c inter_val to the set. Iterator
@@ -397,7 +395,7 @@
inserted after. */
iterator insert(iterator prior_, const segment_type& inter_val)
{
- return itl::add(*that(), prior_, inter_val);
+ return add(prior_, inter_val);
}
@@ -405,13 +403,13 @@
/** Erase an element \c key from the set */
SubType& erase(const element_type& key)
{
- return itl::subtract(*that(), key);
+ return subtract(key);
}
/** Erase an interval of elements \c inter_val from the set */
SubType& erase(const segment_type& inter_val)
{
- return itl::subtract(*that(), inter_val);
+ return subtract(inter_val);
}
/** Erase the interval that iterator \c position points to. */
@@ -549,6 +547,16 @@
static value_type make_value(const key_type& key_value, const codomain_type&)
{ return value_type(key_value); }
+private:
+ iterator _add(const segment_type& addend);
+ iterator _add(iterator prior, const segment_type& addend);
+
+protected:
+ void add_front(const interval_type& inter_val, iterator& first_);
+ void add_main(interval_type& inter_val, iterator& it_, const iterator& last_);
+ void add_segment(const interval_type& inter_val, iterator& it_);
+ void add_rear(const interval_type& inter_val, iterator& it_);
+
protected:
sub_type* that() { return static_cast<sub_type*>(this); }
const sub_type* that()const { return static_cast<const sub_type*>(this); }
@@ -558,6 +566,162 @@
} ;
+template <class SubType, class DomainT, ITL_COMPARE Compare, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
+ ::add_front(const interval_type& inter_val, iterator& first_)
+{
+ // 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(*first_, inter_val);
+
+ if(!itl::is_empty(left_resid))
+ { // [------------ . . .
+ // [left_resid---first_ --- . . .
+ iterator prior_ = cyclic_prior(*this, first_);
+ const_cast<interval_type&>(*first_) = left_subtract(*first_, left_resid);
+ //NOTE: Only splitting
+ this->_set.insert(prior_, left_resid);
+ }
+
+ //POST:
+ // [----- inter_val ---- . . .
+ // ...[-- first_ --...
+}
+
+template <class SubType, class DomainT, ITL_COMPARE Compare, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
+ ::add_segment(const interval_type& inter_val, iterator& it_)
+{
+ interval_type lead_gap = right_subtract(inter_val, *it_);
+ if(!itl::is_empty(lead_gap))
+ // [lead_gap--- . . .
+ // [prior_) [-- it_ ...
+ this->_set.insert(prior(it_), lead_gap);
+
+ // . . . --------- . . . addend interval
+ // [-- it_ --) has a common part with the first overval
+ ++it_;
+}
+
+template <class SubType, class DomainT, ITL_COMPARE Compare, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
+ ::add_main(interval_type& rest_interval, iterator& it_, const iterator& last_)
+{
+ interval_type cur_interval;
+ while(it_ != last_)
+ {
+ cur_interval = *it_ ;
+ add_segment(rest_interval, it_);
+ // shrink interval
+ rest_interval = left_subtract(rest_interval, cur_interval);
+ }
+}
+
+template <class SubType, class DomainT, ITL_COMPARE Compare, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
+ ::add_rear(const interval_type& inter_val, iterator& it_)
+{
+ iterator prior_ = cyclic_prior(*this, it_);
+ interval_type cur_itv = *it_;
+
+ interval_type lead_gap = right_subtract(inter_val, cur_itv);
+ if(!itl::is_empty(lead_gap))
+ // [lead_gap--- . . .
+ // [prior_) [-- it_ ...
+ this->_set.insert(prior_, lead_gap);
+
+ interval_type end_gap = left_subtract(inter_val, cur_itv);
+ if(!itl::is_empty(end_gap))
+ // [---------------end_gap)
+ // [-- it_ --)
+ it_ = this->_set.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(!itl::is_empty(right_resid))
+ {
+ // [--------------)
+ // [-- it_ --right_resid)
+ const_cast<interval_type&>(*it_) = right_subtract(*it_, right_resid);
+ it_ = this->_set.insert(it_, right_resid);
+ }
+ }
+}
+
+//==============================================================================
+//= Addition
+//==============================================================================
+template <class SubType, class DomainT, ITL_COMPARE Compare, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator
+ interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
+ ::_add(const segment_type& addend)
+{
+ if(itl::is_empty(addend))
+ return this->_set.end();
+
+ std::pair<iterator,bool> insertion = this->_set.insert(addend);
+
+ if(insertion.second)
+ return that()->handle_inserted(insertion.first);
+ else
+ return that()->add_over(addend, insertion.first);
+}
+
+template <class SubType, class DomainT, ITL_COMPARE Compare, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator
+ interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
+ ::_add(iterator prior_, const segment_type& addend)
+{
+ if(itl::is_empty(addend))
+ return prior_;
+
+ iterator insertion = this->_set.insert(prior_, addend);
+
+ if(*insertion == addend)
+ return that()->handle_inserted(insertion);
+ else
+ return that()->add_over(addend);
+}
+
+//==============================================================================
+//= Subtraction
+//==============================================================================
+template <class SubType, class DomainT, ITL_COMPARE Compare, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+inline SubType& interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
+ ::subtract(const segment_type& minuend)
+{
+ if(itl::is_empty(minuend))
+ return *that();
+
+ std::pair<iterator, iterator> exterior = this->_set.equal_range(minuend);
+ if(exterior.first == exterior.second)
+ return *that();
+
+ iterator first_ = exterior.first;
+ iterator end_ = exterior.second;
+ iterator last_ = prior(end_);
+
+ interval_type left_resid = right_subtract(*first_, minuend);
+ interval_type right_resid;
+ if(first_ != end_)
+ right_resid = left_subtract(*last_ , minuend);
+
+ this->_set.erase(first_, end_);
+
+ if(!itl::is_empty(left_resid))
+ this->_set.insert(left_resid);
+
+ if(!itl::is_empty(right_resid))
+ this->_set.insert(right_resid);
+
+ return *that();
+}
+
//-----------------------------------------------------------------------------
// type traits
//-----------------------------------------------------------------------------
Modified: sandbox/itl/boost/itl/interval_map.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_map.hpp (original)
+++ sandbox/itl/boost/itl/interval_map.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -49,10 +49,12 @@
DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> base_type;
typedef ITL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
- typedef typename base_type::iterator iterator;
- typedef typename base_type::value_type value_type;
- typedef typename base_type::element_type element_type;
- typedef typename base_type::segment_type segment_type;
+ typedef typename base_type::iterator iterator;
+ typedef typename base_type::value_type value_type;
+ typedef typename base_type::element_type element_type;
+ typedef typename base_type::segment_type segment_type;
+ typedef typename base_type::domain_type domain_type;
+ typedef typename base_type::codomain_type codomain_type;
typedef typename base_type::domain_mapping_type domain_mapping_type;
typedef typename base_type::interval_mapping_type interval_mapping_type;
typedef typename base_type::ImplMapT ImplMapT;
@@ -109,6 +111,94 @@
prior_ = this->add(prior_, *it_);
}
+private:
+ // Private functions that shall be accessible by the baseclass:
+ friend class
+ interval_base_map <interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>,
+ DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>;
+
+ iterator handle_inserted(iterator it_)
+ {
+ return segmental::join_neighbours(*this, it_);
+ }
+
+ void handle_inserted(iterator prior_, iterator it_)
+ {
+ if(prior_ != this->_map.end() && segmental::joinable(*this, prior_, it_))
+ segmental::join_on_right(*this, prior_, it_);
+ }
+
+ template<class Combiner>
+ void handle_left_combined(iterator it_)
+ {
+ if(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(it_->second))
+ this->_map.erase(it_);
+ else
+ segmental::join_left(*this, it_);
+ }
+
+ template<class Combiner>
+ void handle_combined(iterator it_)
+ {
+ if(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(it_->second))
+ this->_map.erase(it_);
+ else
+ segmental::join_neighbours(*this, it_);
+ }
+
+ template<class Combiner>
+ void handle_preceeded_combined(iterator prior_, iterator& it_)
+ {
+ if(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(it_->second))
+ {
+ this->_map.erase(it_);
+ it_ = prior_;
+ }
+ else // After a new combination (e.g. combiner=max) joining neighbours may be possible
+ segmental::join_neighbours(*this, it_);
+ }
+
+ template<class Combiner>
+ void handle_succeeded_combined(iterator it_, iterator next_)
+ {
+ if(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(it_->second))
+ {
+ this->_map.erase(it_);
+ segmental::join_right(*this, next_);
+ }
+ else
+ {
+ segmental::join_left(*this, it_);
+ segmental::join_neighbours(*this, next_);
+ }
+ }
+
+
+
+ void handle_reinserted(iterator insertion_)
+ {
+ segmental::join_right(*this, insertion_);
+ }
+
+
+ template<class Combiner>
+ void gap_insert_at(iterator& it_, iterator prior_,
+ const interval_type& end_gap, const codomain_type& co_val)
+ {
+ if(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(it_->second))
+ {
+ this->_map.erase(it_);
+ it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val);
+ segmental::join_right(*this, it_);
+ }
+ else
+ {
+ segmental::join_left(*this, it_);
+ iterator inserted_ = this->template gap_insert<Combiner>(it_, end_gap, co_val);
+ it_ = segmental::join_neighbours(*this, inserted_);
+ }
+ }
+
} ;
Modified: sandbox/itl/boost/itl/interval_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_set.hpp (original)
+++ sandbox/itl/boost/itl/interval_set.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -1,5 +1,5 @@
/*-----------------------------------------------------------------------------+
-Copyright (c) 2007-2009: Joachim Faulhaber
+Copyright (c) 2007-2010: Joachim Faulhaber
Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
+------------------------------------------------------------------------------+
Distributed under the Boost Software License, Version 1.0.
@@ -138,6 +138,31 @@
ITL_const_FORALL(typename base_set_type, it_, src)
prior_ = this->add(prior_, *it_);
}
+
+
+private:
+ // Private functions that shall be accessible by the baseclass:
+ friend class
+ interval_base_set <interval_set<DomainT,Compare,Interval,Alloc>,
+ DomainT,Compare,Interval,Alloc>;
+
+ iterator handle_inserted(iterator it_)
+ {
+ return segmental::join_neighbours(*this, it_);
+ }
+
+ iterator add_over(const interval_type& addend, iterator last_)
+ {
+ iterator joined_ = segmental::join_under(*this, addend, last_);
+ return segmental::join_neighbours(*this, joined_);
+ }
+
+ iterator add_over(const interval_type& addend)
+ {
+ iterator joined_ = segmental::join_under(*this, addend);
+ return segmental::join_neighbours(*this, joined_);
+ }
+
} ;
Modified: sandbox/itl/boost/itl/separate_interval_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/separate_interval_set.hpp (original)
+++ sandbox/itl/boost/itl/separate_interval_set.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -123,6 +123,29 @@
this->clear();
this->_set.insert(src.begin(), src.end());
}
+
+
+private:
+ // Private functions that shall be accessible by the baseclass:
+ friend class
+ interval_base_set<separate_interval_set<DomainT,Compare,Interval,Alloc>,
+ DomainT,Compare,Interval,Alloc>;
+
+ iterator handle_inserted(iterator inserted_)
+ {
+ return inserted_;
+ }
+
+ iterator add_over(const interval_type& addend, iterator last_)
+ {
+ return segmental::join_under(*this, addend, last_);
+ }
+
+ iterator add_over(const interval_type& addend)
+ {
+ return segmental::join_under(*this, addend);
+ }
+
} ;
Deleted: sandbox/itl/boost/itl/seqs.hpp
==============================================================================
--- sandbox/itl/boost/itl/seqs.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
+++ (empty file)
@@ -1,66 +0,0 @@
-/*-----------------------------------------------------------------------------+
-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)
-+-----------------------------------------------------------------------------*/
-
-/*------------------------------------------------------------------------------
-itl_rational provides adapter code for boost::rational.
-------------------------------------------------------------------------------*/
-
-#ifndef BOOST_ITL_SEQS_HPP_JOFA_100824
-#define BOOST_ITL_SEQS_HPP_JOFA_100824
-
-
-namespace boost{namespace itl
-{
-
-template<class SeqT>
-struct seqs
-{
- typedef SeqT seq_type;
- typedef typename seq_type::domain_type domain_type;
- typedef typename seq_type::codomain_type codomain_type;
- typedef typename seq_type::element_type element_type;
- typedef typename seq_type::size_type size_type;
- typedef typename seq_type::iterator iterator;
- typedef typename seq_type::const_iterator const_iterator;
-
- static const_iterator begin(const seq_type&);
- static iterator begin( seq_type&);
- static const_iterator end (const seq_type&);
- static iterator end ( seq_type&);
- static size_type size (const seq_type&);
- static const_iterator find (const seq_type&, const domain_type&);
- static iterator find ( seq_type&, const domain_type&);
-
- static std::pair<iterator,bool> insert(seq_type&, const element_type&);
- static iterator insert(seq_type&, iterator, const element_type&);
- static void erase (seq_type&, iterator);
- static void erase (seq_type&, iterator, iterator);
-
- static void swap(seq_type&, seq_type&);
-
- //--------------------------------------------------------------------------
- template<typename IteratorT>
- static const domain_type& key_value(IteratorT value_);
-
- template<typename IteratorT>
- static const codomain_type& co_value(IteratorT value_);
-
- template<typename LeftIterT, typename RightIterT>
- static bool key_less(LeftIterT lhs_, RightIterT rhs_);
-
- static element_type make_value(const domain_type& key_value, const codomain_type& data_value);
-
-};
-
-
-}} // namespace itl boost
-
-
-#endif
-
-
Modified: sandbox/itl/boost/itl/split_interval_map.hpp
==============================================================================
--- sandbox/itl/boost/itl/split_interval_map.hpp (original)
+++ sandbox/itl/boost/itl/split_interval_map.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -93,17 +93,60 @@
this->_map.insert(src.begin(), src.end());
}
- //==========================================================================
- //= Selection
- //==========================================================================
-
- //MEMO DESIGN DECISION: split_interval_map::operator[](interval):
- // If used for selection will deliver a set of associated
- // values. It could only implemented for a single key value. But this
- // would mislead the unexperienced user to hash a split_interval_map into
- // singular intervals by inapt usage of op[]. So op[] will not be implemented
- // codomain_type& operator[](const interval_type& interval_of_keys)
+private:
+ // Private functions that shall be accessible by the baseclass:
+ friend class
+ interval_base_map <split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>,
+ DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>;
+
+ iterator handle_inserted(iterator it_)const { return it_; }
+ void handle_inserted(iterator prior_, iterator it_)const{ }
+
+ template<class Combiner>
+ void handle_left_combined(iterator it_)
+ {
+ if(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(it_->second))
+ this->_map.erase(it_);
+ }
+
+ template<class Combiner>
+ void handle_combined(iterator it_)
+ {
+ if(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(it_->second))
+ this->_map.erase(it_);
+ }
+
+ template<class Combiner>
+ void handle_preceeded_combined(iterator prior_, iterator& it_)
+ {
+ if(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(it_->second))
+ {
+ this->_map.erase(it_);
+ it_ = prior_;
+ }
+ }
+ template<class Combiner>
+ void handle_succeeded_combined(iterator it_, iterator)
+ {
+ if(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(it_->second))
+ this->_map.erase(it_);
+ }
+
+ void handle_reinserted(iterator insertion_){}
+
+ template<class Combiner>
+ void gap_insert_at(iterator& it_, iterator prior_,
+ const interval_type& end_gap, const codomain_type& co_val)
+ {
+ if(on_neutric<type,Combiner,Traits::absorbs_neutrons>::is_absorbable(it_->second))
+ {
+ this->_map.erase(it_);
+ it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val);
+ }
+ else
+ it_ = this->template gap_insert<Combiner>(it_, end_gap, co_val);
+ }
} ;
//-----------------------------------------------------------------------------
Modified: sandbox/itl/boost/itl/split_interval_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/split_interval_set.hpp (original)
+++ sandbox/itl/boost/itl/split_interval_set.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -117,7 +117,50 @@
this->clear();
this->_set.insert(src.begin(), src.end());
}
+
+private:
+ // Private functions that shall be accessible by the baseclass:
+ friend class
+ interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>,
+ DomainT,Compare,Interval,Alloc>;
+
+ iterator handle_inserted(iterator inserted_)
+ {
+ return inserted_;
+ }
+
+ iterator add_over(const interval_type& addend, iterator last_)
+ {
+ iterator first_ = this->_set.lower_bound(addend);
+ //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
+
+ iterator it_ = first_;
+ interval_type rest_interval = addend;
+
+ add_front(rest_interval, it_);
+ add_main (rest_interval, it_, last_);
+ add_rear (rest_interval, it_);
+ return it_;
+ }
+
+ iterator add_over(const interval_type& addend)
+ {
+ std::pair<iterator,iterator> overlap = this->_set.equal_range(addend);
+ iterator first_ = overlap.first,
+ end_ = overlap.second,
+ last_ = end_; --last_;
+
+ iterator it_ = first_;
+ interval_type rest_interval = addend;
+
+ add_front(rest_interval, it_);
+ add_main (rest_interval, it_, last_);
+ add_rear (rest_interval, it_);
+
+ return it_;
+ }
+
} ;
Modified: sandbox/itl/libs/itl/test/test_interval_map_shared.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_map_shared.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_map_shared.hpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -538,7 +538,7 @@
all -= section;
complement += all;
//complement.erase(I3_5I);
- complement.erase(section);
+ itl::erase(complement, section);
BOOST_CHECK_EQUAL( disjoint(section, complement), true );
BOOST_CHECK_EQUAL( intersects(section, complement), false );
}
Modified: sandbox/itl/libs/validate/example/labat_single_/labat_single.cpp
==============================================================================
--- sandbox/itl/libs/validate/example/labat_single_/labat_single.cpp (original)
+++ sandbox/itl/libs/validate/example/labat_single_/labat_single.cpp 2010-09-19 16:55:25 EDT (Sun, 19 Sep 2010)
@@ -86,7 +86,7 @@
//typedef Antisymmetry<itl::map<int,int>, itl::sub_super_set, itl::element_equal> TestLawT;
//typedef InplaceAssociativity<itl::interval_map<int,itl::set<int> >, itl::inplace_caret, itl::element_equal> TestLawT;
- typedef InplaceFlip<itl::interval_map<int,int> > TestLawT;
+ typedef InplaceFlip<itl::interval_map<int,int,total_enricher> > TestLawT;
LawValidater<TestLawT> test_law;
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk