[Boost-commit] svn:boost r53796 - in sandbox/itl: boost/itl libs/itl/test

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) );