Subject: [Boost-commit] svn:boost r53904 - sandbox/itl/boost/itl
From: afojgo_at_[hidden]
Date: 2009-06-14 07:19:08
Author: jofaber
Date: 2009-06-14 07:19:08 EDT (Sun, 14 Jun 2009)
New Revision: 53904
URL: http://svn.boost.org/trac/boost/changeset/53904
Log:
Refactoring, efficiency: Improved efficiency of split_interval_map::add. Stable {msvc-9.0}
Text files modified:
sandbox/itl/boost/itl/interval_base_map.hpp | 42 +++++++++
sandbox/itl/boost/itl/interval_set.hpp | 7
sandbox/itl/boost/itl/separate_interval_set.hpp | 7
sandbox/itl/boost/itl/split_interval_map.hpp | 173 +++++++++++++++++++++------------------
sandbox/itl/boost/itl/split_interval_set.hpp | 10 +
5 files changed, 149 insertions(+), 90 deletions(-)
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 2009-06-14 07:19:08 EDT (Sun, 14 Jun 2009)
@@ -623,6 +623,48 @@
sub_type& self() { return *that(); }
protected:
+ template <class Combiner>
+ bool combine(iterator& it_, const codomain_type& co_val)
+ {
+ Combiner()(it_->CONT_VALUE, co_val);
+ if(Traits::absorbs_neutrons && it_->CONT_VALUE == Combiner::neutron())
+ { this->_map.erase(it_); it_ = _map.end(); return false; }
+ return true;
+ }
+
+ template <class Combiner>
+ std::pair<iterator,bool> map_insert(const interval_type& inter_val, const codomain_type& co_val)
+ {
+ if(Traits::is_total)
+ {
+ CodomainT added_val = Combiner::neutron();
+ Combiner()(added_val, co_val);
+ if(Traits::absorbs_neutrons && added_val == Combiner::neutron())
+ return std::pair<iterator,bool>(this->_map.end(), false);
+ else
+ return this->_map.insert(value_type(inter_val, added_val));
+ }
+ else
+ return this->_map.insert(value_type(inter_val, co_val));
+ }
+
+ template <class Combiner>
+ iterator map_insert(iterator& prior_, const interval_type& inter_val, const codomain_type& co_val)
+ {
+ if(Traits::is_total)
+ {
+ CodomainT added_val = Combiner::neutron();
+ Combiner()(added_val, co_val);
+ if(Traits::absorbs_neutrons && added_val == Combiner::neutron())
+ return this->_map.end();
+ else
+ return this->_map.insert(prior_, value_type(inter_val, added_val));
+ }
+ else
+ return this->_map.insert(prior_, value_type(inter_val, co_val));
+ }
+
+protected:
ImplMapT _map;
} ;
Modified: sandbox/itl/boost/itl/interval_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_set.hpp (original)
+++ sandbox/itl/boost/itl/interval_set.hpp 2009-06-14 07:19:08 EDT (Sun, 14 Jun 2009)
@@ -234,15 +234,16 @@
{
if(addend.empty()) return;
- std::pair<typename ImplSetT::iterator,bool> insertion = this->_set.insert(addend);
+ std::pair<iterator,bool> insertion = this->_set.insert(addend);
if(insertion.WAS_SUCCESSFUL)
handle_neighbours(insertion.ITERATOR);
else
{
iterator fst_it = this->_set.lower_bound(addend),
- end_it = this->_set.upper_bound(addend);
- iterator lst_it = end_it; --lst_it;
+ lst_it = insertion.ITERATOR,
+ end_it = insertion.ITERATOR; end_it++;
+ //BOOST_ASSERT(end_it == this->_map.upper_bound(inter_val));
iterator snd_it = fst_it; ++snd_it;
interval_type leftResid = right_subtract(*fst_it, addend);
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 2009-06-14 07:19:08 EDT (Sun, 14 Jun 2009)
@@ -159,15 +159,16 @@
{
if(addend.empty()) return;
- std::pair<typename ImplSetT::iterator,bool> insertion = this->_set.insert(addend);
+ std::pair<iterator,bool> insertion = this->_set.insert(addend);
if(insertion.WAS_SUCCESSFUL)
handle_neighbours(insertion.ITERATOR);
else
{
iterator fst_it = this->_set.lower_bound(addend),
- end_it = this->_set.upper_bound(addend);
- iterator lst_it = end_it; --lst_it;
+ lst_it = insertion.ITERATOR,
+ end_it = insertion.ITERATOR; end_it++;
+ //BOOST_ASSERT(end_it == this->_map.upper_bound(inter_val));
iterator snd_it = fst_it; ++snd_it;
interval_type leftResid = right_subtract(*fst_it, addend);
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-14 07:19:08 EDT (Sun, 14 Jun 2009)
@@ -131,13 +131,14 @@
void handle_neighbours(const iterator& it){}
void fill(const value_type&);
+ iterator fill(iterator&, const interval_type&, const codomain_type&);
template<class Combiner>
void fill_gap(const value_type&);
template<class Combiner>
- void add_rest(const interval_type& x_itv, const CodomainT& x_val,
- iterator& it, iterator& end_it);
+ void add_mid(interval_type& x_itv, const CodomainT& x_val,
+ iterator& it, iterator& end_it);
template<class Combiner>
void add_rear(const interval_type& x_itv, const CodomainT& x_val,
@@ -185,6 +186,21 @@
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>
+typename split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
+ split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::fill(iterator& prior_, const interval_type& inter_val, const codomain_type& co_val)
+{
+ //collision free insert is asserted
+ if(inter_val.empty())
+ return this->_map.end();
+ if(Traits::absorbs_neutrons && co_val == codomain_combine::neutron())
+ return this->_map.end();
+
+ return this->_map.insert(prior_, value_type(inter_val, 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>
::fill_gap(const value_type& value)
@@ -195,86 +211,70 @@
if(Traits::absorbs_neutrons && value.CONT_VALUE == Combiner::neutron())
return;
- if(Traits::is_total)
- {
- CodomainT added_val = Combiner::neutron();
- Combiner()(added_val, value.CONT_VALUE);
- if(Traits::absorbs_neutrons && added_val == Combiner::neutron())
- return;
- else
- this->_map.insert(value_type(value.KEY_VALUE, added_val));
- }
- else
- this->_map.insert(value);
+ map_insert<Combiner>(value.KEY_VALUE, value.CONT_VALUE);
}
+
//-----------------------------------------------------------------------------
// add<Combinator>(pair(interval,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_(const value_type& x)
+ ::add_(const value_type& addend)
{
- const interval_type& x_itv = x.KEY_VALUE;
+ const interval_type& inter_val = addend.KEY_VALUE;
- if(x_itv.empty())
+ if(inter_val.empty())
return;
- const CodomainT& x_val = x.CONT_VALUE;
- if(Traits::absorbs_neutrons && x_val==Combiner::neutron())
+ const CodomainT& co_val = addend.CONT_VALUE;
+ if(Traits::absorbs_neutrons && co_val==Combiner::neutron())
return;
- std::pair<iterator,bool> insertion;
- if(Traits::is_total)
- {
- CodomainT added_val = Combiner::neutron();
- Combiner()(added_val, x_val);
- if(Traits::absorbs_neutrons && added_val == Combiner::neutron())
- return;
- else
- insertion = this->_map.insert(value_type(x_itv, added_val));
- }
- else
- insertion = this->_map.insert(x);
+ std::pair<iterator,bool> insertion = map_insert<Combiner>(inter_val, co_val);
if(!insertion.WAS_SUCCESSFUL)
{
// Detect the first and the end iterator of the collision sequence
- iterator fst_it = this->_map.lower_bound(x_itv);
- iterator end_it = insertion.ITERATOR;
+ iterator fst_it = this->_map.lower_bound(inter_val),
+ lst_it = insertion.ITERATOR,
+ end_it = insertion.ITERATOR;
if(end_it != this->_map.end())
end_it++;
- //assert(end_it == this->_map.upper_bound(x_itv));
+ //assert(end_it == this->_map.upper_bound(inter_val));
interval_type fst_itv = (*fst_it).KEY_VALUE ;
CodomainT cur_val = (*fst_it).CONT_VALUE ;
- interval_type leadGap; x_itv.right_subtract(leadGap, fst_itv);
+ // 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
- fill_gap<Combiner>(value_type(leadGap, x_val));
-
- // only for the first there can be a leftResid: a part of *it left of x
- interval_type leftResid; fst_itv.right_subtract(leftResid, x_itv);
+ if(!lead_gap.empty())
+ fill_gap<Combiner>(value_type(lead_gap, co_val));
+
+ // only for the first there can be a leftResid: a part of *it left of addend
+ interval_type leftResid; fst_itv.right_subtract(leftResid, inter_val);
// handle special case for first
- interval_type interSec = fst_itv & x_itv;
+ interval_type interSec = fst_itv & inter_val;
CodomainT cmb_val = cur_val;
- Combiner()(cmb_val, x_val);
+ Combiner()(cmb_val, co_val);
iterator snd_it = fst_it; snd_it++;
if(snd_it == end_it)
{
// first == last
- interval_type endGap; x_itv.left_subtract(endGap, fst_itv);
+ interval_type endGap; inter_val.left_subtract(endGap, fst_itv);
// this is a new Interval that is a gap in the current map
- fill_gap<Combiner>(value_type(endGap, x_val));
+ fill_gap<Combiner>(value_type(endGap, co_val));
- // only for the last there can be a rightResid: a part of *it right of x
- interval_type rightResid; (*fst_it).KEY_VALUE.left_subtract(rightResid, x_itv);
+ // only for the last there can be a rightResid: a part of *it right of addend
+ interval_type rightResid; (*fst_it).KEY_VALUE.left_subtract(rightResid, inter_val);
this->_map.erase(fst_it);
fill(value_type(leftResid, cur_val));
@@ -288,10 +288,12 @@
fill(value_type(interSec, cmb_val));
// shrink interval
- interval_type x_rest(x_itv);
+ interval_type x_rest(inter_val);
x_rest.left_subtract(fst_itv);
- add_rest<Combiner>(x_rest, x_val, snd_it, end_it);
+ add_mid<Combiner> (x_rest, co_val, snd_it, end_it);
+ add_rear<Combiner>(x_rest, co_val, snd_it);
+
}
}
}
@@ -299,59 +301,70 @@
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_rest(const interval_type& x_itv, const CodomainT& x_val,
- iterator& it, iterator& end_it)
+ ::add_mid(interval_type& inter_val, const CodomainT& co_val,
+ iterator& it, iterator& end_it)
{
- iterator nxt_it = it; nxt_it++;
- interval_type x_rest = x_itv, gap, common, cur_itv;
+ iterator pred_it, nxt_it = it; ++nxt_it;
+ interval_type left_gap, common, cur_itv;
while(nxt_it!=end_it)
{
+ // [----- . . . . . ------) inter_val->co_val
+ // [prior_) [ it_ ) . . .
cur_itv = (*it).KEY_VALUE ;
- x_rest.right_subtract(gap, cur_itv);
+ left_gap = right_subtract(inter_val, cur_itv);
- Combiner()(it->CONT_VALUE, x_val);
- fill_gap<Combiner>(value_type(gap, x_val));
+ Combiner()(it->CONT_VALUE, co_val);
+ if(!left_gap.empty())
+ {
+ pred_it = it; --pred_it;
+ map_insert<Combiner>(pred_it, left_gap, co_val);
+ }
if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
this->_map.erase(it++);
- else it++;
+ else ++it;
// shrink interval
- x_rest.left_subtract(cur_itv);
- nxt_it++;
+ inter_val.left_subtract(cur_itv);
+ ++nxt_it;
}
- add_rear<Combiner>(x_rest, x_val, 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_rear(const interval_type& x_rest, const CodomainT& x_val, iterator& it)
+ ::add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it)
{
interval_type cur_itv = (*it).KEY_VALUE ;
- CodomainT cur_val = (*it).CONT_VALUE ;
-
- interval_type left_gap;
- x_rest.right_subtract(left_gap, cur_itv);
- fill_gap<Combiner>(value_type(left_gap, x_val));
-
- interval_type common = cur_itv & x_rest;
- CodomainT cmb_val = cur_val;
- Combiner()(cmb_val, x_val);
-
- interval_type end_gap;
- x_rest.left_subtract(end_gap, cur_itv);
- fill_gap<Combiner>(value_type(end_gap, x_val));
+ //CodomainT cur_val = (*it).CONT_VALUE ;
- // only for the last there can be a rightResid: a part of *it right of x
- interval_type right_resid;
- cur_itv.left_subtract(right_resid, x_rest);
-
- this->_map.erase(it);
- fill(value_type(common, cmb_val));
- fill(value_type(right_resid, cur_val));
+ interval_type left_gap = right_subtract(inter_val, cur_itv);
+ if(!left_gap.empty())
+ fill_gap<Combiner>(value_type(left_gap, co_val));
+
+ interval_type end_gap = left_subtract(inter_val, cur_itv);
+ if(!end_gap.empty())
+ {
+ fill_gap<Combiner>(value_type(end_gap, co_val));
+ combine<Combiner>(it, co_val);
+ }
+ else
+ {
+ // 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())
+ {
+ interval_type common = inter_val & it->KEY_VALUE;
+ const_cast<interval_type&>(it->KEY_VALUE) = right_resid;
+ iterator prior_ = it; --prior_;
+ iterator inserted_ = fill(prior_, common, it->CONT_VALUE);
+ combine<Combiner>(inserted_, co_val);
+ }
+ else
+ combine<Combiner>(it, co_val);
+ }
}
@@ -493,9 +506,9 @@
//assert(end_it == this->_map.upper_bound(x_itv));
interval_type fst_itv = (*fst_it).KEY_VALUE ;
- interval_type leadGap; x_itv.right_subtract(leadGap, fst_itv);
+ interval_type lead_gap; x_itv.right_subtract(lead_gap, fst_itv);
// this is a new Interval that is a gap in the current map
- fill(value_type(leadGap, x_val));
+ fill(value_type(lead_gap, x_val));
// only for the first there can be a leftResid: a part of *it left of x
interval_type leftResid; fst_itv.right_subtract(leftResid, x_itv);
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 2009-06-14 07:19:08 EDT (Sun, 14 Jun 2009)
@@ -158,13 +158,15 @@
{
if(addend.empty()) return;
- std::pair<typename ImplSetT::iterator,bool> insertion = this->_set.insert(addend);
+ std::pair<iterator,bool> insertion = this->_set.insert(addend);
if(!insertion.WAS_SUCCESSFUL)
{
- iterator fst_it = this->_set.lower_bound(addend);
- iterator end_it = this->_set.upper_bound(addend);
- iterator lst_it = end_it; lst_it--;
+ iterator fst_it = this->_set.lower_bound(addend),
+ lst_it = insertion.ITERATOR,
+ end_it = insertion.ITERATOR; end_it++;
+ //BOOST_ASSERT(end_it == this->_map.upper_bound(inter_val));
+
iterator pre_it = fst_it;
if(pre_it != this->_set.begin())
--pre_it;