Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r54211 - in sandbox/itl/boost: itl validate/driver
From: afojgo_at_[hidden]
Date: 2009-06-22 11:19:11


Author: jofaber
Date: 2009-06-22 11:19:09 EDT (Mon, 22 Jun 2009)
New Revision: 54211
URL: http://svn.boost.org/trac/boost/changeset/54211

Log:
Refactoring, optimizing: Improved efficiency of interval_map::insert,erase. Stable {msvc-9.0}
Text files modified:
   sandbox/itl/boost/itl/interval_map.hpp | 249 ++++++++++++++-------------------------
   sandbox/itl/boost/itl/interval_set.hpp | 1
   sandbox/itl/boost/validate/driver/itl_morphic_driver.hpp | 40 +++---
   3 files changed, 113 insertions(+), 177 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-22 11:19:09 EDT (Mon, 22 Jun 2009)
@@ -169,18 +169,17 @@
     void add_segment(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
 
     template<class Combiner>
- void subtract_main(const interval_type& x_itv, const CodomainT& x_val,
+ void subtract_main(const interval_type& inter_val, const CodomainT& co_val,
                        iterator& it, iterator& end_it);
 
- void subtract_front(const interval_type& x_itv, const CodomainT& x_val, iterator& it_);
+ void subtract_front(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
 
     template<class Combiner>
- void subtract_rear(const interval_type& x_itv, const CodomainT& x_val, iterator& it);
+ void subtract_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& 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 insert_range(const interval_type& inter_val, const CodomainT& co_val, iterator& it, iterator& end_it);
 
- void erase_rest(const interval_type& x_itv, const CodomainT& x_val, iterator& it, iterator& end_it);
+ void erase_rest(const interval_type& inter_val, const CodomainT& co_val, iterator& it, iterator& lst_it);
 
 } ;
 
@@ -467,13 +466,13 @@
 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 interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::add_main(interval_type& x_rest, const CodomainT& x_val, iterator& it, const iterator& lst_it)
+ ::add_main(interval_type& x_rest, const CodomainT& co_val, iterator& it, const iterator& lst_it)
 {
         interval_type cur_interval;
     while(it!=lst_it)
     {
         cur_interval = it->KEY_VALUE ;
- add_segment<Combiner>(x_rest, x_val, it);
+ add_segment<Combiner>(x_rest, co_val, it);
         // shrink interval
         x_rest.left_subtract(cur_interval);
     }
@@ -692,61 +691,28 @@
 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 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)
         join_neighbours(insertion.ITERATOR);
     else
     {
         // 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
-
- // only for the first there can be a left_resid: a part of *it left of x
- interval_type left_resid; fst_itv.right_subtract(left_resid, x_itv);
-
- // handle special case for first
-
- iterator snd_it = fst_it; snd_it++;
- if(snd_it == end_it)
- {
- //Fill gap after iterator compare bcause iterators are modified by joining
- if(!lead_gap.empty())
- fill_join_both(value_type(lead_gap, x_val));
-
- interval_type end_gap; x_itv.left_subtract(end_gap, fst_itv);
- // this is a new Interval that is a gap in the current map
- fill_join_both(value_type(end_gap, x_val));
- }
- else
- {
- if(!lead_gap.empty())
- fill_join_both(value_type(lead_gap, x_val));
-
- // 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);
     }
 }
 
@@ -754,53 +720,40 @@
 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 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;
 
- for(; nxt_it!=end_it; ++it, ++nxt_it)
+ while(it != end_it)
     {
- cur_itv = (*it).KEY_VALUE ;
- x_rest.right_subtract(gap, cur_itv);
+ cur_itv = it->KEY_VALUE ;
+ left_gap = right_subtract(rest_interval, cur_itv);
 
- if(!gap.empty())
+ if(!left_gap.empty())
         {
- fill_join_left(value_type(gap, x_val));
+ inserted_ = this->_map.insert(prior_, value_type(left_gap, co_val));
+ join_left(inserted_);
             // after filling that gap there may be another joining opportunity
             join_left(it);
         }
 
         // shrink interval
- x_rest.left_subtract(cur_itv);
- }
-
- insert_rear(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>
-void 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 ;
-
- interval_type left_gap;
- x_rest.right_subtract(left_gap, cur_itv);
-
- if(!left_gap.empty())
- {
- fill_join_left(value_type(left_gap, x_val));
- // after filling that gap there may be another joining opportunity
- join_left(it);
+ rest_interval.left_subtract(cur_itv);
+ prior_ = it;
+ ++it;
     }
 
- interval_type end_gap;
- x_rest.left_subtract(end_gap, cur_itv);
-
- fill_join_both(value_type(end_gap, x_val));
+ //insert_rear(rest_interval, co_val, lst_it):
+ interval_type end_gap = left_subtract(rest_interval, lst_it->KEY_VALUE);
+ if(!end_gap.empty())
+ {
+ inserted_ = this->_map.insert(prior_, value_type(end_gap, co_val));
+ join_neighbours(inserted_);
+ }
 }
 
 
@@ -809,99 +762,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 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 ;
-
- // only for the first there can be a left_resid: a part of *it left of x
- interval_type left_resid;
- fst_itv.right_subtract(left_resid, 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;
 
- 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 right_resid: a part of *it right of x
- interval_type right_resid; (*fst_it).KEY_VALUE.left_subtract(right_resid, 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);
- insert_(value_type(left_resid, fst_val));
- insert_(value_type(right_resid, 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);
- insert_(value_type(left_resid, 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 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)
+inline void 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)
 {
- 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;
-
- interval_type right_resid;
- cur_itv.left_subtract(right_resid, x_itv);
+ // 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_++;
 
- if(right_resid.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);
- insert_(value_type(right_resid, 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/itl/interval_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_set.hpp (original)
+++ sandbox/itl/boost/itl/interval_set.hpp 2009-06-22 11:19:09 EDT (Mon, 22 Jun 2009)
@@ -267,7 +267,6 @@
     iterator fst_it = this->_set.lower_bound(minuend);
     if(fst_it==this->_set.end()) return;
     iterator end_it = this->_set.upper_bound(minuend);
- iterator snd_it = fst_it; ++snd_it;
     iterator lst_it = end_it; --lst_it;
 
     interval_type leftResid = right_subtract(*fst_it, minuend);

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-22 11:19:09 EDT (Mon, 22 Jun 2009)
@@ -28,12 +28,12 @@
         _rootChoice.setSize(RootType::Types_size);
         _rootChoice.setMaxWeights(100);
         _rootChoice[RootType::itl_set] = 0;
- _rootChoice[RootType::interval_set] = 20;
- _rootChoice[RootType::separate_interval_set] = 20;
- _rootChoice[RootType::split_interval_set] = 20;
+ _rootChoice[RootType::interval_set] = 0;//20;
+ _rootChoice[RootType::separate_interval_set] = 0;//20;
+ _rootChoice[RootType::split_interval_set] = 0;//20;
         _rootChoice[RootType::itl_map] = 0;
- _rootChoice[RootType::interval_map] = 20;
- _rootChoice[RootType::split_interval_map] = 20;
+ _rootChoice[RootType::interval_map] = 100;//20;
+ _rootChoice[RootType::split_interval_map] = 0;//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:


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