|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r54277 - in sandbox/itl/boost: itl validate/driver
From: afojgo_at_[hidden]
Date: 2009-06-23 07:17:54
Author: jofaber
Date: 2009-06-23 07:17:53 EDT (Tue, 23 Jun 2009)
New Revision: 54277
URL: http://svn.boost.org/trac/boost/changeset/54277
Log:
Refactoring, optimizing: Improved efficiency of split_interval_map::insert,erase. Stable {msvc-9.0}
Text files modified:
sandbox/itl/boost/itl/interval_map.hpp | 6
sandbox/itl/boost/itl/split_interval_map.hpp | 577 ++++++++++++++++++---------------------
sandbox/itl/boost/validate/driver/itl_morphic_driver.hpp | 40 +-
sandbox/itl/boost/validate/driver/signed_quantifier_driver.hpp | 42 +-
4 files changed, 315 insertions(+), 350 deletions(-)
Modified: sandbox/itl/boost/itl/interval_map.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_map.hpp (original)
+++ sandbox/itl/boost/itl/interval_map.hpp 2009-06-23 07:17:53 EDT (Tue, 23 Jun 2009)
@@ -604,8 +604,7 @@
return;
iterator lst_it = end_it; --lst_it;
-
- iterator it_ = fst_it;
+ iterator it_ = fst_it;
subtract_front (inter_val, co_val, it_);
subtract_main<Combiner>(inter_val, co_val, it_, lst_it);
subtract_rear<Combiner>(inter_val, co_val, it_);
@@ -727,6 +726,7 @@
if(prior_ != this->_map.end())
--prior_;
interval_type rest_interval = inter_val, left_gap, cur_itv;
+ interval_type last_interval = lst_it->KEY_VALUE;
while(it != end_it)
{
@@ -748,7 +748,7 @@
}
//insert_rear(rest_interval, co_val, lst_it):
- interval_type end_gap = left_subtract(rest_interval, lst_it->KEY_VALUE);
+ interval_type end_gap = left_subtract(rest_interval, last_interval);
if(!end_gap.empty())
{
inserted_ = this->_map.insert(prior_, value_type(end_gap, co_val));
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-23 07:17:53 EDT (Tue, 23 Jun 2009)
@@ -142,23 +142,30 @@
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);
-
+ void add_main(interval_type& x_itv, const CodomainT& x_val,
+ iterator& it, const iterator& end_it);
template<class Combiner>
+ void add_segment(const interval_type& x_itv, const CodomainT& x_val,
+ iterator& it);
+
void add_front(const interval_type& x_itv, const CodomainT& x_val, iterator& it);
template<class Combiner>
void add_rear(const interval_type& x_itv, const CodomainT& x_val, iterator& it);
template<class Combiner>
- void subtract_rest(const interval_type& x_itv, const CodomainT& x_val,
+ void subtract_main(const interval_type& x_itv, const CodomainT& x_val,
iterator& it, iterator& end_it);
- void insert_rest(const interval_type& x_itv, const CodomainT& x_val, iterator& it, iterator& end_it);
- void insert_rear(const interval_type& x_itv, const CodomainT& x_val, iterator& it);
+ void subtract_front(const interval_type& x_itv, const CodomainT& x_val, iterator& it);
+
+ template<class Combiner>
+ void subtract_rear(const interval_type& x_itv, const CodomainT& x_val, iterator& it);
+
+ void insert_range(const interval_type& x_itv, const CodomainT& x_val, iterator& it, iterator& end_it);
+ //CL void insert_rear(const interval_type& x_itv, const CodomainT& x_val, iterator& it);
- void erase_rest(const interval_type& x_itv, const CodomainT& x_val, iterator& it, iterator& end_it);
+ void erase_rest(const interval_type& x_itv, const CodomainT& x_val, iterator& it, iterator& lst_it);
} ;
@@ -237,356 +244,330 @@
}
+
//-----------------------------------------------------------------------------
// 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& addend)
+ ::add_(const value_type& x)
{
- interval_type inter_val = addend.KEY_VALUE;
+ const interval_type& inter_val = x.KEY_VALUE;
if(inter_val.empty())
return;
- const CodomainT& co_val = addend.CONT_VALUE;
+ const CodomainT& co_val = x.CONT_VALUE;
if(Traits::absorbs_neutrons && co_val==Combiner::neutron())
return;
- std::pair<iterator,bool> insertion = this->template map_insert<Combiner>(inter_val, co_val);
+ std::pair<iterator,bool> insertion
+ = this->template 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(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);
+ //assert(end_it == this->_map.upper_bound(inter_val));
- add_front<Combiner>(inter_val, co_val, fst_it);
+ iterator it_ = fst_it;
+ interval_type rest_interval = inter_val;
- 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);
+ add_front (rest_interval, co_val, it_);
+ add_main<Combiner>(rest_interval, co_val, it_, lst_it);
+ add_rear<Combiner>(rest_interval, co_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_front(const interval_type& inter_val, const CodomainT& co_val, iterator& fst_it)
+inline void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::add_front(const interval_type& inter_val, const CodomainT& co_val, iterator& first_)
{
- 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));
- }
+ // If the collision sequence has a right residual 'right_resid' is will
+ // be split, to provide a standardized start of algorithms:
+ // The addend interval 'inver_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_->KEY_VALUE, inter_val);
+
+ if(!left_resid.empty())
+ { // [------------ . . .
+ // [left_resid---fst_it --- . . .
+ iterator prior_ = first_;
+ if(prior_ != this->_map.begin())
+ --prior_;
+ const_cast<interval_type&>(first_->KEY_VALUE).left_subtract(left_resid);
+ //NOTE: Only splitting
+ iterator insertion_ = this->_map.insert(prior_, value_type(left_resid, first_->CONT_VALUE));
}
+
+ //POST:
+ // [----- inter_val ---- . . .
+ // ...[-- first_ --...
}
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)
+inline void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::add_main(interval_type& x_rest, const CodomainT& co_val, iterator& it, const iterator& lst_it)
{
- iterator it = snd_it;
- iterator end_it = lst_it; ++end_it;
-
- iterator prior_, nxt_it = it; ++nxt_it;
- interval_type left_gap, common, cur_itv;
- interval_type rest_itv = inter_val;
-
- while(nxt_it!=end_it)
+ interval_type cur_interval;
+ while(it!=lst_it)
{
- // [----- . . . . . ------) inter_val->co_val
- // [prior_) [ it_ ) . . .
- cur_itv = it->KEY_VALUE;
- left_gap = right_subtract(rest_itv, cur_itv);
-
- Combiner()(it->CONT_VALUE, co_val);
- if(!left_gap.empty())
- {
- prior_ = it; --prior_;
- this->template map_insert<Combiner>(prior_, left_gap, co_val);
- }
-
- if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
- this->_map.erase(it++);
- else ++it;
-
+ cur_interval = it->KEY_VALUE ;
+ add_segment<Combiner>(x_rest, co_val, it);
// shrink interval
- rest_itv.left_subtract(cur_itv);
- ++nxt_it;
+ x_rest.left_subtract(cur_interval);
}
+}
- cur_itv = it->KEY_VALUE;
- left_gap = right_subtract(rest_itv, cur_itv);
- if(!left_gap.empty())
+
+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>
+inline void split_interval_map<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_->KEY_VALUE);
+ if(!lead_gap.empty())
{
- prior_ = it; --prior_;
- this->template map_insert<Combiner>(prior_, left_gap, co_val);
+ // [------ . . .
+ // [-- it ...
+ iterator prior_ = it_; prior_--;
+ fill_gap<Combiner>(prior_, lead_gap, co_val);
}
+
+ // . . . ------------ . . . addend interval
+ // [-- fst_it --) has a common part with the first overval
+ Combiner()(it_->CONT_VALUE, co_val);
+ if(Traits::absorbs_neutrons && it_->CONT_VALUE == Combiner::neutron())
+ this->_map.erase(it_++);
+ else
+ ++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>
+inline 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 ;
+ iterator prior_ = it; --prior_;
+ interval_type cur_itv = (*it).KEY_VALUE ;
+
+ interval_type lead_gap = right_subtract(inter_val, cur_itv);
+ if(!lead_gap.empty())
+ // [------ . . .
+ // [-- it ...
+ fill_gap<Combiner>(prior_, lead_gap, co_val);
interval_type end_gap = left_subtract(inter_val, cur_itv);
if(!end_gap.empty())
{
- // addend: [----------------)
- // collseq: [ it )
- fill_gap<Combiner>(it, end_gap, co_val);
- this->template combine<Combiner>(it, co_val);
+ // [------------------)
+ // [-- it --)
+ Combiner()(it->CONT_VALUE, co_val);
+
+ if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
+ {
+ this->_map.erase(it);
+ iterator inserted_ = this->template map_insert<Combiner>(prior_, end_gap, co_val);
+ }
+ else
+ {
+ fill_gap<Combiner>(it, end_gap, co_val);
+ }
}
else
{
- // addend: [---------)
- // collseq: [ it )
- // only for the last there can be a rightResid: a part of *it right of addend
+ // 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(!right_resid.empty())
+
+ 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);
- this->template combine<Combiner>(inserted_, co_val);
+ // [---------------)
+ // [-- it ----)
+ Combiner()(it->CONT_VALUE, co_val);
+
+ if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
+ this->_map.erase(it);
}
else
- this->template combine<Combiner>(it, co_val);
+ {
+ // [-------------)
+ // [-- it ---right_resid)
+ const_cast<interval_type&>(it->KEY_VALUE).right_subtract(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->CONT_VALUE));
+
+ Combiner()(it->CONT_VALUE, co_val);
+
+ if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
+ this->_map.erase(it);
+ }
}
}
+
+
//-----------------------------------------------------------------------------
// subtract<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>
- ::subtract_(const value_type& x)
+ ::subtract_(const value_type& minuend)
{
- const interval_type& x_itv = x.KEY_VALUE;
+ interval_type inter_val = minuend.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 = minuend.CONT_VALUE;
+ if(Traits::absorbs_neutrons && co_val==Combiner::neutron())
return;
- iterator fst_it = this->_map.lower_bound(x_itv);
- if(fst_it==this->_map.end()) return;
- iterator end_it = this->_map.upper_bound(x_itv);
- if(fst_it==end_it) return;
-
- interval_type fst_itv = (*fst_it).KEY_VALUE ;
- // must be copies because fst_it will be erased
- CodomainT fst_val = (*fst_it).CONT_VALUE ;
-
- // 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);
-
- // handle special case for first
+ iterator fst_it = this->_map.lower_bound(inter_val);
+ if(fst_it==this->_map.end())
+ return;
+ iterator end_it = this->_map.upper_bound(inter_val);
+ if(fst_it==end_it)
+ return;
+
+ iterator lst_it = end_it; --lst_it;
+ iterator it_ = fst_it;
+ subtract_front (inter_val, co_val, it_);
+ subtract_main<Combiner>(inter_val, co_val, it_, lst_it);
+ subtract_rear<Combiner>(inter_val, co_val, it_);
+}
- interval_type interSec = fst_itv & x_itv;
- CodomainT cmb_val = fst_val;
- Combiner()(cmb_val, x_val);
- iterator snd_it = fst_it; snd_it++;
- if(snd_it == end_it)
- {
- // 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);
+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>
+inline void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::subtract_front(const interval_type& inter_val, const CodomainT& co_val, iterator& it_)
+{
+ interval_type left_resid = right_subtract(it_->KEY_VALUE, inter_val);
- this->_map.erase(fst_it);
- fill(value_type(leftResid, fst_val));
- fill(value_type(interSec, cmb_val));
- fill(value_type(rightResid, fst_val));
- }
- else
+ if(!left_resid.empty())
{
- // first AND NOT last
- this->_map.erase(fst_it);
- fill(value_type(leftResid, fst_val));
- fill(value_type(interSec, cmb_val));
-
- subtract_rest<Combiner>(x_itv, x_val, snd_it, end_it);
+ iterator prior_ = it_;
+ if(prior_ != this->_map.begin())
+ --prior_;
+ const_cast<interval_type&>(it_->KEY_VALUE).left_subtract(left_resid);
+ this->_map.insert(prior_, value_type(left_resid, 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>
- ::subtract_rest(const interval_type& x_itv, const CodomainT& x_val,
- iterator& it, iterator& end_it)
-{
- iterator nxt_it=it; nxt_it++;
-
- while(nxt_it!=end_it)
- {
- CodomainT& cur_val = (*it).CONT_VALUE ;
- Combiner()(cur_val, x_val);
-
- if(Traits::absorbs_neutrons && cur_val==Combiner::neutron())
- this->_map.erase(it++);
- else it++;
-
- nxt_it=it; nxt_it++;
+inline void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::subtract_main(const interval_type& inter_val, const CodomainT& co_val,
+ iterator& it_, iterator& lst_it)
+{
+ while(it_ != lst_it)
+ {
+ Combiner()(it_->CONT_VALUE, co_val);
+ if(Traits::absorbs_neutrons && it_->CONT_VALUE==Combiner::neutron())
+ this->_map.erase(it_++);
+ else ++it_;
}
+}
- // it refers the last overlaying intervals of x_itv
- const interval_type& cur_itv = (*it).KEY_VALUE ;
- interval_type rightResid;
- cur_itv.left_subtract(rightResid, x_itv);
+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>
+inline void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::subtract_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_)
+{
+ interval_type right_resid = left_subtract(it_->KEY_VALUE, inter_val);
- if(rightResid.empty())
+ if(right_resid.empty())
{
- CodomainT& cur_val = (*it).CONT_VALUE ;
- Combiner()(cur_val, x_val);
+ CodomainT& cur_val = it_->CONT_VALUE ;
+ Combiner()(cur_val, co_val);
if(Traits::absorbs_neutrons && cur_val==Combiner::neutron())
- this->_map.erase(it);
+ this->_map.erase(it_);
}
else
- {
- CodomainT cur_val = (*it).CONT_VALUE ;
- CodomainT cmb_val = cur_val ;
- Combiner()(cmb_val, x_val);
-
- // I have to compute intersec here, because reference cur_itv will be invalid after erase(it);
- interval_type interSec = cur_itv & x_itv;
- this->_map.erase(it);
- fill(value_type(interSec, cmb_val));
- fill(value_type(rightResid, cur_val));
+ { // . . . ---)
+ // . . . ---right_resid) : split it_
+ const_cast<interval_type&>(it_->KEY_VALUE).right_subtract(right_resid);
+ iterator next_ = this->_map.insert(it_, value_type(right_resid, it_->CONT_VALUE));
+ Combiner()(it_->CONT_VALUE, co_val);
+ if(Traits::absorbs_neutrons && it_->CONT_VALUE==Combiner::neutron())
+ this->_map.erase(it_);
}
}
-
//-----------------------------------------------------------------------------
// insert(pair(interval,value)):
//-----------------------------------------------------------------------------
-template <typename DomainT, typename CodomainT, class Traits,
+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>
void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::insert_(const value_type& x)
+ ::insert_(const value_type& addend)
{
- const interval_type& x_itv = x.KEY_VALUE;
- if(x_itv.empty())
+ interval_type inter_val = addend.KEY_VALUE;
+ if(inter_val.empty())
return;
- const CodomainT& x_val = x.CONT_VALUE;
- if(Traits::absorbs_neutrons && x_val == codomain_combine::neutron())
+ const CodomainT& co_val = addend.CONT_VALUE;
+ if(Traits::absorbs_neutrons && co_val==codomain_combine::neutron())
return;
- std::pair<typename ImplMapT::iterator,bool>
- insertion = this->_map.insert(x);
+ std::pair<iterator,bool> insertion = this->_map.insert(addend);
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;
- if(end_it != this->_map.end())
- end_it++;
- //assert(end_it == this->_map.upper_bound(x_itv));
- interval_type fst_itv = (*fst_it).KEY_VALUE ;
-
- 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(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);
-
- // handle special case for first
-
- iterator snd_it = fst_it; snd_it++;
- if(snd_it == end_it)
- {
- interval_type endGap; x_itv.left_subtract(endGap, fst_itv);
- // this is a new Interval that is a gap in the current map
- fill(value_type(endGap, x_val));
- }
- else
- {
- // shrink interval
- interval_type x_rest(x_itv);
- x_rest.left_subtract(fst_itv);
-
- insert_rest(x_rest, x_val, snd_it, end_it);
- }
+ iterator fst_it = this->_map.lower_bound(inter_val),
+ lst_it = insertion.ITERATOR;
+ //assert((++lst_it) == this->_map.upper_bound(inter_val));
+ iterator it_ = fst_it;
+ insert_range(inter_val, co_val, it_, lst_it);
}
}
-template <typename DomainT, typename CodomainT, class Traits,
+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>
void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::insert_rest(const interval_type& x_itv, const CodomainT& x_val,
- iterator& it, iterator& end_it)
+ ::insert_range(const interval_type& inter_val, const CodomainT& co_val, iterator& it, iterator& lst_it)
{
- iterator nxt_it = it; nxt_it++;
- interval_type x_rest = x_itv, gap, common, cur_itv;
+ iterator end_it = lst_it; ++end_it;
+ iterator prior_ = it, inserted_;
+ if(prior_ != this->_map.end())
+ --prior_;
+ interval_type rest_interval = inter_val, left_gap, cur_itv;
+ interval_type last_interval = lst_it->KEY_VALUE;
- for(; nxt_it!=end_it; ++it, ++nxt_it)
+ while(it != end_it)
{
- cur_itv = (*it).KEY_VALUE ;
- x_rest.right_subtract(gap, cur_itv);
- fill(value_type(gap, x_val));
- // shrink interval
- x_rest.left_subtract(cur_itv);
- }
+ cur_itv = it->KEY_VALUE ;
+ left_gap = right_subtract(rest_interval, cur_itv);
- insert_rear(x_rest, x_val, it);
-}
+ if(!left_gap.empty())
+ inserted_ = this->_map.insert(prior_, 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>
-void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::insert_rear(const interval_type& x_rest, const CodomainT& x_val,
- iterator& it)
-{
- interval_type cur_itv = (*it).KEY_VALUE ;
+ // shrink interval
+ rest_interval.left_subtract(cur_itv);
+ prior_ = it;
+ ++it;
+ }
- interval_type left_gap;
- x_rest.right_subtract(left_gap, cur_itv);
- fill(value_type(left_gap, x_val));
-
- interval_type end_gap;
- x_rest.left_subtract(end_gap, cur_itv);
- fill(value_type(end_gap, x_val));
+ //insert_rear(rest_interval, co_val, lst_it):
+ interval_type end_gap = left_subtract(rest_interval, last_interval);
+ if(!end_gap.empty())
+ inserted_ = this->_map.insert(prior_, value_type(end_gap, co_val));
}
@@ -595,99 +576,83 @@
//-----------------------------------------------------------------------------
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>
void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::erase_(const value_type& x)
+ ::erase_(const value_type& minuend)
{
- const interval_type& x_itv = x.KEY_VALUE;
- if(x_itv.empty())
+ interval_type inter_val = minuend.KEY_VALUE;
+ if(inter_val.empty())
return;
- const CodomainT& x_val = x.CONT_VALUE;
- if(Traits::absorbs_neutrons && x_val==codomain_combine::neutron())
+ const CodomainT& co_val = minuend.CONT_VALUE;
+ if(Traits::absorbs_neutrons && co_val==codomain_combine::neutron())
return;
- iterator fst_it = this->_map.lower_bound(x_itv);
- if(fst_it==this->_map.end()) return;
- iterator end_it = this->_map.upper_bound(x_itv);
- if(fst_it==end_it) return;
-
- interval_type fst_itv = (*fst_it).KEY_VALUE ;
- // must be copies because fst_it will be erased
- CodomainT fst_val = (*fst_it).CONT_VALUE ;
+ iterator fst_it = this->_map.lower_bound(inter_val);
+ if(fst_it==this->_map.end())
+ return;
+ iterator end_it = this->_map.upper_bound(inter_val);
+ if(fst_it==end_it)
+ return;
- // 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);
-
- // handle special case for first
-
- interval_type interSec = fst_itv & x_itv;
+ iterator lst_it = end_it; --lst_it;
iterator snd_it = fst_it; snd_it++;
- if(snd_it == end_it)
+ if(fst_it == lst_it)
{
- // 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 right_resid: a part of *it right of minuend
+ interval_type right_resid; (*fst_it).KEY_VALUE.left_subtract(right_resid, inter_val);
- if(!interSec.empty() && fst_val == x_val)
+ if(fst_it->CONT_VALUE == co_val)
{
- this->_map.erase(fst_it);
- fill(value_type(leftResid, fst_val));
- fill(value_type(rightResid, fst_val));
+ interval_type left_resid = right_subtract(fst_it->KEY_VALUE, inter_val);
+ if(!left_resid.empty())
+ {
+ const_cast<interval_type&>(fst_it->KEY_VALUE) = left_resid;
+ if(!right_resid.empty())
+ this->_map.insert(fst_it, value_type(right_resid, co_val));
+ }
+ else if(!right_resid.empty())
+ const_cast<interval_type&>(fst_it->KEY_VALUE) = right_resid;
+ else
+ this->_map.erase(fst_it);
}
}
else
{
// first AND NOT last
- if(!interSec.empty() && fst_val == x_val)
- {
- this->_map.erase(fst_it);
- fill(value_type(leftResid, fst_val));
- }
+ if(fst_it->CONT_VALUE == co_val)
+ {
+ interval_type left_resid = right_subtract(fst_it->KEY_VALUE, inter_val);
+ if(left_resid.empty())
+ this->_map.erase(fst_it);
+ else
+ const_cast<interval_type&>(fst_it->KEY_VALUE) = left_resid;
+ }
- erase_rest(x_itv, x_val, snd_it, end_it);
+ erase_rest(inter_val, co_val, snd_it, 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>
-void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::erase_rest(const interval_type& x_itv, const CodomainT& x_val,
- iterator& it, iterator& end_it)
-{
- iterator nxt_it=it; nxt_it++;
-
- // For all intervals within loop: it->KEY_VALUE are contained_in x_itv
- while(nxt_it!=end_it)
- {
- if((*it).CONT_VALUE == x_val)
- this->_map.erase(it++);
- else it++;
-
- nxt_it=it; nxt_it++;
- }
-
- // it refers the last overlaying intervals of x_itv
- interval_type cur_itv = (*it).KEY_VALUE ;
- // Has to be a copy, cause 'it' will be erased
- CodomainT cur_val = (*it).CONT_VALUE;
+inline void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::erase_rest(const interval_type& inter_val, const CodomainT& co_val,
+ iterator& it_, iterator& lst_it)
+{
+ // For all intervals within loop: it_->KEY_VALUE are contained_in inter_val
+ while(it_ != lst_it)
+ if((*it_).CONT_VALUE == co_val)
+ this->_map.erase(it_++);
+ else it_++;
- interval_type rightResid;
- cur_itv.left_subtract(rightResid, x_itv);
-
- if(rightResid.empty())
- {
- if(cur_val == x_val)
- this->_map.erase(it);
- }
- else
- {
- interval_type interSec = cur_itv & x_itv;
- if(!interSec.empty() && cur_val == x_val)
- {
- this->_map.erase(it);
- fill(value_type(rightResid, cur_val));
- }
- }
+ //erase_rear:
+ if(it_->CONT_VALUE == co_val)
+ {
+ interval_type right_resid = left_subtract(it_->KEY_VALUE, inter_val);
+ if(right_resid.empty())
+ this->_map.erase(it_);
+ else
+ const_cast<interval_type&>(it_->KEY_VALUE) = right_resid;
+ }
}
Modified: sandbox/itl/boost/validate/driver/itl_morphic_driver.hpp
==============================================================================
--- sandbox/itl/boost/validate/driver/itl_morphic_driver.hpp (original)
+++ sandbox/itl/boost/validate/driver/itl_morphic_driver.hpp 2009-06-23 07:17:53 EDT (Tue, 23 Jun 2009)
@@ -28,12 +28,12 @@
_rootChoice.setSize(RootType::Types_size);
_rootChoice.setMaxWeights(100);
_rootChoice[RootType::itl_set] = 0;
- _rootChoice[RootType::interval_set] = 0;//20;
- _rootChoice[RootType::separate_interval_set] = 0;//20;
- _rootChoice[RootType::split_interval_set] = 0;//20;
+ _rootChoice[RootType::interval_set] = 20;
+ _rootChoice[RootType::separate_interval_set] = 20;
+ _rootChoice[RootType::split_interval_set] = 20;
_rootChoice[RootType::itl_map] = 0;
- _rootChoice[RootType::interval_map] = 100;//20;
- _rootChoice[RootType::split_interval_map] = 0;//20;
+ _rootChoice[RootType::interval_map] = 20;
+ _rootChoice[RootType::split_interval_map] = 20;
setRootTypeNames();
_rootChoice.init();
@@ -100,24 +100,24 @@
//-----------------------------------------------------------------
// Sets
//-----------------------------------------------------------------
- //case RootType::interval_set: return new interval_morphic_validater<interval_set<int> >;
- //case RootType::separate_interval_set: return new interval_morphic_validater<separate_interval_set<int> >;
- //case RootType::split_interval_set: return new interval_morphic_validater<split_interval_set<int> >;
+ case RootType::interval_set: return new interval_morphic_validater<interval_set<int> >;
+ case RootType::separate_interval_set: return new interval_morphic_validater<separate_interval_set<int> >;
+ case RootType::split_interval_set: return new interval_morphic_validater<split_interval_set<int> >;
//-----------------------------------------------------------------
// Maps
//-----------------------------------------------------------------
- //case RootType::split_interval_map: {
- // switch(domainChoice) {
- // case DomainType::Int:
- // switch(neutronizerChoice) {
- // NEURONIZER_CASES(interval_morphic_validater, split_interval_map, int, int)
- // default: return choiceError(ITL_LOCATION("\nRootType::split_interval_map: neutronizerChoice:\n"),
- // neutronizerChoice, _neutronizerChoice);
- // }
- // default: return choiceError(ITL_LOCATION("\nRootType::split_interval_map: domainChoice:\n"),
- // domainChoice, _domainChoice);
- // }
- //}
+ case RootType::split_interval_map: {
+ switch(domainChoice) {
+ case DomainType::Int:
+ switch(neutronizerChoice) {
+ NEURONIZER_CASES(interval_morphic_validater, split_interval_map, int, int)
+ default: return choiceError(ITL_LOCATION("\nRootType::split_interval_map: neutronizerChoice:\n"),
+ neutronizerChoice, _neutronizerChoice);
+ }
+ default: return choiceError(ITL_LOCATION("\nRootType::split_interval_map: domainChoice:\n"),
+ domainChoice, _domainChoice);
+ }
+ }
case RootType::interval_map: {
switch(domainChoice) {
case DomainType::Int:
Modified: sandbox/itl/boost/validate/driver/signed_quantifier_driver.hpp
==============================================================================
--- sandbox/itl/boost/validate/driver/signed_quantifier_driver.hpp (original)
+++ sandbox/itl/boost/validate/driver/signed_quantifier_driver.hpp 2009-06-23 07:17:53 EDT (Tue, 23 Jun 2009)
@@ -33,9 +33,9 @@
_rootChoice[RootType::interval_set] = 0;
_rootChoice[RootType::separate_interval_set] = 0;
_rootChoice[RootType::split_interval_set] = 0;
- _rootChoice[RootType::itl_map] = 0;//JODO 33,33,34
- _rootChoice[RootType::interval_map] = 100;
- _rootChoice[RootType::split_interval_map] = 0;
+ _rootChoice[RootType::itl_map] = 33;
+ _rootChoice[RootType::interval_map] = 33;
+ _rootChoice[RootType::split_interval_map] = 34;
setRootTypeNames();
_rootChoice.init();
@@ -101,15 +101,15 @@
switch(rootChoice)
{
//-----------------------------------------------------------------
- //case RootType::itl_map: { //JODO URG
- // switch(neutronizerChoice) {
- // case NeutronHandlerType::partial_absorber: return new signed_quantifier_validater<itl::map<int,int,partial_absorber> >;
- // case NeutronHandlerType::partial_enricher: return new signed_quantifier_validater<itl::map<int,int,partial_enricher> >;
- // case NeutronHandlerType::total_absorber: return new signed_quantifier_validater<itl::map<int,int,total_absorber > >;
- // case NeutronHandlerType::total_enricher: return new signed_quantifier_validater<itl::map<int,int,total_enricher > >;
- // default: return choiceError(ITL_LOCATION("\nRootType::itl_map: neutronizerChoice:\n"), neutronizerChoice, _neutronizerChoice);
- // }//switch neutronizerChoice
- //}//case itl_map
+ case RootType::itl_map: { //JODO URG
+ switch(neutronizerChoice) {
+ case NeutronHandlerType::partial_absorber: return new signed_quantifier_validater<itl::map<int,int,partial_absorber> >;
+ case NeutronHandlerType::partial_enricher: return new signed_quantifier_validater<itl::map<int,int,partial_enricher> >;
+ case NeutronHandlerType::total_absorber: return new signed_quantifier_validater<itl::map<int,int,total_absorber > >;
+ case NeutronHandlerType::total_enricher: return new signed_quantifier_validater<itl::map<int,int,total_enricher > >;
+ default: return choiceError(ITL_LOCATION("\nRootType::itl_map: neutronizerChoice:\n"), neutronizerChoice, _neutronizerChoice);
+ }//switch neutronizerChoice
+ }//case itl_map
//-----------------------------------------------------------------
case RootType::interval_map: {
switch(neutronizerChoice) {
@@ -121,15 +121,15 @@
}//switch neutronizerChoice
}//case interval_map
//-----------------------------------------------------------------
- //case RootType::split_interval_map: {
- // switch(neutronizerChoice) {
- // case NeutronHandlerType::partial_absorber: return new signed_quantifier_validater<split_interval_map<int,int,partial_absorber> >;
- // case NeutronHandlerType::partial_enricher: return new signed_quantifier_validater<split_interval_map<int,int,partial_enricher> >;
- // case NeutronHandlerType::total_absorber: return new signed_quantifier_validater<split_interval_map<int,int,total_absorber > >;
- // case NeutronHandlerType::total_enricher: return new signed_quantifier_validater<split_interval_map<int,int,total_enricher > >;
- // default: return choiceError(ITL_LOCATION("\nRootType::split_interval_map: neutronizerChoice:\n"), neutronizerChoice, _neutronizerChoice);
- // }//switch neutronizerChoice
- //}//case split_interval_map
+ case RootType::split_interval_map: {
+ switch(neutronizerChoice) {
+ case NeutronHandlerType::partial_absorber: return new signed_quantifier_validater<split_interval_map<int,int,partial_absorber> >;
+ case NeutronHandlerType::partial_enricher: return new signed_quantifier_validater<split_interval_map<int,int,partial_enricher> >;
+ case NeutronHandlerType::total_absorber: return new signed_quantifier_validater<split_interval_map<int,int,total_absorber > >;
+ case NeutronHandlerType::total_enricher: return new signed_quantifier_validater<split_interval_map<int,int,total_enricher > >;
+ default: return choiceError(ITL_LOCATION("\nRootType::split_interval_map: neutronizerChoice:\n"), neutronizerChoice, _neutronizerChoice);
+ }//switch neutronizerChoice
+ }//case split_interval_map
//-----------------------------------------------------------------
default: return choiceError(ITL_LOCATION("rootChoice:\n"), rootChoice, _rootChoice);
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