Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r53796 - in sandbox/itl: boost/itl libs/itl/test
From: afojgo_at_[hidden]
Date: 2009-06-11 16:10:58


Author: jofaber
Date: 2009-06-11 16:10:57 EDT (Thu, 11 Jun 2009)
New Revision: 53796
URL: http://svn.boost.org/trac/boost/changeset/53796

Log:
Refactoring, efficiency: Improved efficiency of X_interval_set::add/subtract.
Bugfixes: Invalid iterators. Stable {msvc-9.0}

Text files modified:
   sandbox/itl/boost/itl/interval_set.hpp | 9 +---
   sandbox/itl/boost/itl/separate_interval_set.hpp | 7 +--
   sandbox/itl/boost/itl/split_interval_set.hpp | 79 +++++++--------------------------------
   sandbox/itl/libs/itl/test/test_interval_set_shared.hpp | 1
   4 files changed, 21 insertions(+), 75 deletions(-)

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-11 16:10:57 EDT (Thu, 11 Jun 2009)
@@ -223,7 +223,7 @@
 
     interval_type right_itv = (*right_it);
     this->_set.erase(right_it);
- left_it->extend(right_itv);
+ const_cast<value_type&>(*left_it).extend(right_itv);
 
     return left_it;
 }
@@ -268,9 +268,6 @@
     iterator end_it = this->_set.upper_bound(minuend);
     iterator snd_it = fst_it; ++snd_it;
     iterator lst_it = end_it; --lst_it;
- iterator pre_it = fst_it;
- if(pre_it != this->_set.begin())
- --pre_it;
 
     interval_type leftResid = right_subtract(*fst_it, minuend);
     interval_type rightResid;
@@ -280,10 +277,10 @@
         this->_set.erase(fst_it, end_it);
 
         if(!leftResid.empty())
- pre_it = this->_set.insert(pre_it, leftResid);
+ this->_set.insert(leftResid);
 
         if(!rightResid.empty())
- this->_set.insert(pre_it, rightResid);
+ this->_set.insert(rightResid);
 }
 
 

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-11 16:10:57 EDT (Thu, 11 Jun 2009)
@@ -192,9 +192,6 @@
     iterator end_it = this->_set.upper_bound(minuend);
     iterator snd_it = fst_it; ++snd_it;
     iterator lst_it = end_it; --lst_it;
- iterator pre_it = fst_it;
- if(pre_it != this->_set.begin())
- --pre_it;
 
     interval_type leftResid = right_subtract(*fst_it, minuend);
     interval_type rightResid;
@@ -204,10 +201,10 @@
         this->_set.erase(fst_it, end_it);
 
         if(!leftResid.empty())
- pre_it = this->_set.insert(pre_it, leftResid);
+ this->_set.insert(leftResid);
 
         if(!rightResid.empty())
- this->_set.insert(pre_it, rightResid);
+ this->_set.insert(rightResid);
 }
 
 //-----------------------------------------------------------------------------

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-11 16:10:57 EDT (Thu, 11 Jun 2009)
@@ -228,80 +228,31 @@
 }
 
 
-template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
+template<class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
 void split_interval_set<DomainT,Compare,Interval,Alloc>::subtract_(const value_type& minuend)
 {
     if(minuend.empty()) return;
- if(this->_set.empty()) return;
-
- iterator fst_it;
- if(minuend.exclusive_less(*(this->_set.begin())))
- return;
- if(minuend.lower() < this->_set.begin()->upper())
- fst_it = this->_set.begin();
- else
- fst_it = this->_set.lower_bound(minuend);
-
+ iterator fst_it = this->_set.lower_bound(minuend);
     if(fst_it==this->_set.end()) return;
     iterator end_it = this->_set.upper_bound(minuend);
- if(fst_it==end_it) return;
+ iterator snd_it = fst_it; ++snd_it;
+ iterator lst_it = end_it; --lst_it;
 
- iterator cur_it = fst_it ;
- interval_type cur_itv = *cur_it ;
+ interval_type leftResid = right_subtract(*fst_it, minuend);
+ interval_type rightResid;
+ if(fst_it != end_it)
+ rightResid = left_subtract(*lst_it, minuend);
+
+ this->_set.erase(fst_it, end_it);
+
+ if(!leftResid.empty())
+ this->_set.insert(leftResid);
 
- // only for the first there can be a leftResid: a part of *it left of minuend
- interval_type leftResid; cur_itv.right_subtract(leftResid, minuend);
-
- // handle special case for first
-
- iterator snd_it = fst_it; snd_it++;
- if(snd_it == end_it)
- {
- // first == last
- // only for the last there can be a rightResid: a part of *it right of minuend
- interval_type rightResid; (*cur_it).left_subtract(rightResid, minuend);
-
- this->_set.erase(cur_it);
- add_(leftResid);
- add_(rightResid);
- }
- else
- {
- // first AND NOT last
- this->_set.erase(cur_it);
- add_(leftResid);
- subtract_rest(minuend, snd_it, end_it);
- }
- return;
+ if(!rightResid.empty())
+ this->_set.insert(rightResid);
 }
 
 
-
-template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-void split_interval_set<DomainT,Compare,Interval,Alloc>::subtract_rest(const interval_type& x_itv, iterator& snd_it, iterator& end_it)
-{
- iterator it=snd_it, nxt_it=snd_it; nxt_it++;
-
- while(nxt_it!=end_it)
- {
- { iterator victim; victim=it; it++; this->_set.erase(victim); }
- nxt_it=it; nxt_it++;
- }
-
- // it refers the last overlaying intervals of x_itv
- const interval_type& cur_itv = *it ;
-
- interval_type rightResid; cur_itv.left_subtract(rightResid, x_itv);
-
- if(rightResid.empty())
- this->_set.erase(it);
- else
- {
- this->_set.erase(it);
- this->_set.insert(rightResid);
- }
-}
-
 //==============================================================================
 //= Equivalences and Orderings
 //==============================================================================

Modified: sandbox/itl/libs/itl/test/test_interval_set_shared.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_set_shared.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_set_shared.hpp 2009-06-11 16:10:57 EDT (Thu, 11 Jun 2009)
@@ -321,6 +321,7 @@
     IntervalSet<T> iso_set = IntervalSet<T>(I0_4I);
     IntervalSet<T> gap_set;
     gap_set.add(C0_2D).add(C2_4D);
+ BOOST_CHECK_EQUAL( true, true );
     iso_set -= gap_set;
     
     BOOST_CHECK_EQUAL( iso_set.cardinality(), static_cast<size_T>(3) );


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