Subject: [Boost-commit] svn:boost r53980 - sandbox/itl/boost/itl
From: afojgo_at_[hidden]
Date: 2009-06-16 07:08:51
Author: jofaber
Date: 2009-06-16 07:08:50 EDT (Tue, 16 Jun 2009)
New Revision: 53980
URL: http://svn.boost.org/trac/boost/changeset/53980
Log:
Refactoring: Simplified split_interval_map::add 3. Stable {msvc-9.0}
Text files modified:
sandbox/itl/boost/itl/split_interval_map.hpp | 106 ++++++++++++++++++++++++++-------------
1 files changed, 69 insertions(+), 37 deletions(-)
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 2009-06-16 07:08:50 EDT (Tue, 16 Jun 2009)
@@ -139,6 +139,9 @@
void fill_gap(const value_type&);
template<class Combiner>
+ void fill_gap(iterator& prior_, const interval_type&, const CodomainT&);
+
+ template<class Combiner>
void add_main(const interval_type& x_itv, const CodomainT& x_val,
iterator& it, iterator& end_it);
@@ -218,6 +221,21 @@
this->template map_insert<Combiner>(value.KEY_VALUE, value.CONT_VALUE);
}
+template <typename DomainT, typename CodomainT, class Traits,
+ ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
+ template<class Combiner>
+void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::fill_gap(iterator& prior_, const interval_type& inter_val, const codomain_type& co_val)
+{
+ //collision free insert is asserted
+ if(inter_val.empty())
+ return;
+ if(Traits::absorbs_neutrons && co_val == Combiner::neutron())
+ return;
+
+ this->template map_insert<Combiner>(prior_, inter_val, co_val);
+}
+
//-----------------------------------------------------------------------------
// add<Combinator>(pair(interval,value)):
@@ -241,31 +259,61 @@
// Detect the first and the end iterator of the collision sequence
iterator fst_it = this->_map.lower_bound(inter_val),
lst_it = insertion.ITERATOR;
+ iterator snd_it = fst_it; ++snd_it;
+ iterator end_it = lst_it; ++end_it;
//assert((++lst_it) == this->_map.upper_bound(inter_val));
+ interval_type rest_interval = left_subtract(inter_val, fst_it->KEY_VALUE);
add_front<Combiner>(inter_val, co_val, fst_it);
- add_main<Combiner> (inter_val, co_val, fst_it, lst_it);
+
+ if(snd_it != end_it)
+ {
+ this->template combine<Combiner>(fst_it, co_val);
+ add_main<Combiner> (rest_interval, co_val, snd_it, lst_it);
+ }
+
add_rear<Combiner> (inter_val, co_val, lst_it);
}
}
+
template <typename DomainT, typename CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
template<class Combiner>
void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::add_main(const interval_type& inter_val, const CodomainT& co_val,
- iterator& fst_it, iterator& lst_it)
+ ::add_front(const interval_type& inter_val, const CodomainT& co_val, iterator& fst_it)
{
- if(fst_it == lst_it)
- return;
+ interval_type fst_itv = fst_it->KEY_VALUE ;
- iterator it = fst_it; ++it;
+ // handle the beginning of the sequence of intervals of *this
+ // overlapped by insertee interval 'inter_val'
+ interval_type lead_gap = right_subtract(inter_val, fst_itv);
+ // this is a new Interval that is a gap in the current map
+ if(!lead_gap.empty())
+ fill_gap<Combiner>(value_type(lead_gap, co_val));
+ else
+ {
+ interval_type left_resid = right_subtract(fst_itv, inter_val);
+ if(!left_resid.empty())
+ {
+ const_cast<interval_type&>(fst_it->KEY_VALUE).left_subtract(left_resid);
+ fill(value_type(left_resid, fst_it->CONT_VALUE));
+ }
+ }
+}
+
+
+template <typename DomainT, typename CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
+ template<class Combiner>
+void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::add_main(const interval_type& inter_val, const CodomainT& co_val,
+ iterator& snd_it, iterator& lst_it)
+{
+ iterator it = snd_it;
iterator end_it = lst_it; ++end_it;
- iterator pred_it, nxt_it = it; ++nxt_it;
+ iterator prior_, nxt_it = it; ++nxt_it;
interval_type left_gap, common, cur_itv;
- interval_type rest_itv = left_subtract(inter_val, fst_it->KEY_VALUE);
-
- this->template combine<Combiner>(fst_it, co_val);
+ interval_type rest_itv = inter_val;
while(nxt_it!=end_it)
{
@@ -277,8 +325,8 @@
Combiner()(it->CONT_VALUE, co_val);
if(!left_gap.empty())
{
- pred_it = it; --pred_it;
- this->template map_insert<Combiner>(pred_it, left_gap, co_val);
+ prior_ = it; --prior_;
+ this->template map_insert<Combiner>(prior_, left_gap, co_val);
}
if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
@@ -293,31 +341,9 @@
cur_itv = it->KEY_VALUE;
left_gap = right_subtract(rest_itv, cur_itv);
if(!left_gap.empty())
- fill_gap<Combiner>(value_type(left_gap, co_val));
-}
-
-
-template <typename DomainT, typename CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
- template<class Combiner>
-void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::add_front(const interval_type& inter_val, const CodomainT& co_val, iterator& fst_it)
-{
- interval_type fst_itv = fst_it->KEY_VALUE ;
-
- // handle the beginning of the sequence of intervals of *this
- // overlapped by insertee interval 'inter_val'
- interval_type lead_gap = right_subtract(inter_val, fst_itv);
- // this is a new Interval that is a gap in the current map
- if(!lead_gap.empty())
- fill_gap<Combiner>(value_type(lead_gap, co_val));
- else
{
- interval_type left_resid = right_subtract(fst_itv, inter_val);
- if(!left_resid.empty())
- {
- const_cast<interval_type&>(fst_it->KEY_VALUE).left_subtract(left_resid);
- fill(value_type(left_resid, fst_it->CONT_VALUE));
- }
+ prior_ = it; --prior_;
+ this->template map_insert<Combiner>(prior_, left_gap, co_val);
}
}
@@ -327,16 +353,22 @@
void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
::add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it)
{
+ // addend: [----- . . .
+ // collseq: [ it )
interval_type cur_itv = it->KEY_VALUE ;
interval_type end_gap = left_subtract(inter_val, cur_itv);
if(!end_gap.empty())
{
- fill_gap<Combiner>(value_type(end_gap, co_val));
+ // addend: [----------------)
+ // collseq: [ it )
+ fill_gap<Combiner>(it, end_gap, co_val);
this->template combine<Combiner>(it, co_val);
}
else
{
+ // addend: [---------)
+ // collseq: [ it )
// only for the last there can be a rightResid: a part of *it right of addend
interval_type right_resid = left_subtract(cur_itv, inter_val);
if(!right_resid.empty())