[Boost-commit] svn:boost r53792 - sandbox/itl/boost/itl

Subject: [Boost-commit] svn:boost r53792 - sandbox/itl/boost/itl
From: afojgo_at_[hidden]
Date: 2009-06-11 10:42:32

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

Log:
Refactoring, efficiency: Improved efficiency of X_interval_set::add/subtract.
Used hinted insert, range erase and inplace key modifications on implementing sets.
Stable {msvc-9.0} 

Text files modified: 
   sandbox/itl/boost/itl/interval.hpp              |    17 ++++                                    
   sandbox/itl/boost/itl/interval_map.hpp          |     4                                         
   sandbox/itl/boost/itl/interval_set.hpp          |    80 ++++++++++----------                    
   sandbox/itl/boost/itl/separate_interval_set.hpp |    67 +++++++++--------                       
   sandbox/itl/boost/itl/split_interval_map.hpp    |     4                                         
   sandbox/itl/boost/itl/split_interval_set.hpp    |   151 ++++++++++++++++----------------------- 
   6 files changed, 158 insertions(+), 165 deletions(-)

Modified: sandbox/itl/boost/itl/interval.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval.hpp	(original)
+++ sandbox/itl/boost/itl/interval.hpp	2009-06-11 10:42:31 EDT (Thu, 11 Jun 2009)
@@ -1019,6 +1019,23 @@
 };
 
 
+//==============================================================================
+//= Subtraction
+//==============================================================================
+template <class DomainT, ITL_COMPARE Compare>
+interval<DomainT,Compare> right_subtract(interval<DomainT,Compare>  left, 
+                                   const interval<DomainT,Compare>& right_subtrahend)
+{
+	return left.right_subtract(right_subtrahend);
+}
+
+template <class DomainT, ITL_COMPARE Compare>
+interval<DomainT,Compare> left_subtract(interval<DomainT,Compare>  right, 
+                                  const interval<DomainT,Compare>& left_subtrahend)
+{
+	return right.left_subtract(left_subtrahend);
+}
+
 // ----------------------------------------------------------------------------
 // operators
 // ----------------------------------------------------------------------------

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-11 10:42:31 EDT (Thu, 11 Jun 2009)
@@ -5,8 +5,8 @@
       (See accompanying file LICENCE.txt or copy at
            http://www.boost.org/LICENSE_1_0.txt)
 +-----------------------------------------------------------------------------*/
-#ifndef __interval_map_h_JOFA_080705__
-#define __interval_map_h_JOFA_080705__
+#ifndef __itl_interval_map_h_JOFA_080705__
+#define __itl_interval_map_h_JOFA_080705__
 
 #include <boost/assert.hpp>
 #include <boost/itl/type_traits/is_map.hpp>

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 10:42:31 EDT (Thu, 11 Jun 2009)
@@ -221,71 +221,69 @@
     BOOST_ASSERT((*left_it).exclusive_less(*right_it));
     BOOST_ASSERT((*left_it).touches(*right_it));
 
-    interval_type curItv = (*left_it);
-    curItv.extend(*right_it);
-
-    this->_set.erase(left_it);
+    interval_type right_itv = (*right_it);
     this->_set.erase(right_it);
-    
-    iterator new_it = this->_set.insert(curItv).ITERATOR;
-    BOOST_ASSERT(new_it!=this->_set.end());
-    return new_it;
+	left_it->extend(right_itv);
+
+    return left_it;
 }
 
 
 template<class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-void interval_set<DomainT,Compare,Interval,Alloc>::add_(const value_type& x)
+void interval_set<DomainT,Compare,Interval,Alloc>::add_(const value_type& addend)
 {
-    if(x.empty()) return;
+    if(addend.empty()) return;
 
-    std::pair<typename ImplSetT::iterator,bool> insertion = this->_set.insert(x);
+    std::pair<typename ImplSetT::iterator,bool> insertion = this->_set.insert(addend);
 
     if(insertion.WAS_SUCCESSFUL)
         handle_neighbours(insertion.ITERATOR);
     else
     {
-        typename ImplSetT::iterator fst_it = this->_set.lower_bound(x);
-        typename ImplSetT::iterator end_it = this->_set.upper_bound(x);
+        iterator fst_it = this->_set.lower_bound(addend),
+                 end_it = this->_set.upper_bound(addend);
+        iterator lst_it = end_it; --lst_it;
+        iterator snd_it = fst_it; ++snd_it;
+
+        interval_type leftResid  = right_subtract(*fst_it, addend);
+        interval_type rightResid =  left_subtract(*lst_it, addend);
 
-        typename ImplSetT::iterator it=fst_it, nxt_it=fst_it, victim;
-        interval_type leftResid;  (*it).right_subtract(leftResid,x);
-        interval_type rightResid;
-
-        while(it!=end_it)
-        { 
-            if((++nxt_it)==end_it) 
-                (*it).left_subtract(rightResid,x);
-            victim = it; it++; this->_set.erase(victim);
-        }
+		this->_set.erase(snd_it, end_it);
 
-        interval_type extended = x;
+        interval_type extended = addend;
         extended.extend(leftResid).extend(rightResid);
-        extended.extend(rightResid);
-        add(extended);
+
+		*fst_it = extended;
+		handle_neighbours(fst_it);
     }
 }
 
 
 template<class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-void interval_set<DomainT,Compare,Interval,Alloc>::subtract_(const value_type& x)
+void interval_set<DomainT,Compare,Interval,Alloc>::subtract_(const value_type& minuend)
 {
-    if(x.empty()) return;
-    typename ImplSetT::iterator fst_it = this->_set.lower_bound(x);
+    if(minuend.empty()) return;
+    iterator fst_it = this->_set.lower_bound(minuend);
     if(fst_it==this->_set.end()) return;
-    typename ImplSetT::iterator end_it = this->_set.upper_bound(x);
+    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; 
+	if(fst_it != end_it)
+		rightResid = left_subtract(*lst_it, minuend);
 
-    typename ImplSetT::iterator it=fst_it, nxt_it=fst_it, victim;
-    interval_type leftResid; (*it).right_subtract(leftResid,x);
-    interval_type rightResid;
-
-    while(it!=end_it)
-    { 
-        if((++nxt_it)==end_it) (*it).left_subtract(rightResid,x);
-        victim = it; it++; this->_set.erase(victim);
-    }
+	this->_set.erase(fst_it, end_it);
+
+	if(!leftResid.empty())
+		pre_it = this->_set.insert(pre_it, leftResid);
 
-    add(leftResid);
-    add(rightResid);
+	if(!rightResid.empty())
+		this->_set.insert(pre_it, 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 10:42:31 EDT (Thu, 11 Jun 2009)
@@ -155,58 +155,59 @@
 
 
 template<class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-void separate_interval_set<DomainT,Compare,Interval,Alloc>::add_(const value_type& x)
+void separate_interval_set<DomainT,Compare,Interval,Alloc>::add_(const value_type& addend)
 {
-    if(x.empty()) return;
+    if(addend.empty()) return;
 
-    std::pair<typename ImplSetT::iterator,bool> insertion = this->_set.insert(x);
+    std::pair<typename ImplSetT::iterator,bool> insertion = this->_set.insert(addend);
 
     if(insertion.WAS_SUCCESSFUL)
         handle_neighbours(insertion.ITERATOR);
     else
     {
-        typename ImplSetT::iterator fst_it = this->_set.lower_bound(x);
-        typename ImplSetT::iterator end_it = this->_set.upper_bound(x);
+        iterator fst_it = this->_set.lower_bound(addend),
+                 end_it = this->_set.upper_bound(addend);
+        iterator lst_it = end_it; --lst_it;
+        iterator snd_it = fst_it; ++snd_it;
 
-        typename ImplSetT::iterator it=fst_it, nxt_it=fst_it, victim;
-        interval_type leftResid;  (*it).right_subtract(leftResid,x);
-        interval_type rightResid;
-
-        while(it!=end_it)
-        { 
-            if((++nxt_it)==end_it) 
-                (*it).left_subtract(rightResid,x);
-            victim = it; it++; this->_set.erase(victim);
-        }
+        interval_type leftResid  = right_subtract(*fst_it, addend);
+        interval_type rightResid =  left_subtract(*lst_it, addend);
 
-        interval_type extended = x;
+		this->_set.erase(snd_it, end_it);
+
+        interval_type extended = addend;
         extended.extend(leftResid).extend(rightResid);
-        extended.extend(rightResid);
-        add_(extended);
+
+		*fst_it = extended;
     }
 }
 
 
 template<class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-void separate_interval_set<DomainT,Compare,Interval,Alloc>::subtract_(const value_type& x)
+void separate_interval_set<DomainT,Compare,Interval,Alloc>::subtract_(const value_type& minuend)
 {
-    if(x.empty()) return;
-    typename ImplSetT::iterator fst_it = this->_set.lower_bound(x);
+    if(minuend.empty()) return;
+    iterator fst_it = this->_set.lower_bound(minuend);
     if(fst_it==this->_set.end()) return;
-    typename ImplSetT::iterator end_it = this->_set.upper_bound(x);
+    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; 
+	if(fst_it != end_it)
+		rightResid = left_subtract(*lst_it, minuend);
 
-    typename ImplSetT::iterator it=fst_it, nxt_it=fst_it, victim;
-    interval_type leftResid; (*it).right_subtract(leftResid,x);
-    interval_type rightResid;
-
-    while(it!=end_it)
-    { 
-        if((++nxt_it)==end_it) (*it).left_subtract(rightResid,x);
-        victim = it; it++; this->_set.erase(victim);
-    }
+	this->_set.erase(fst_it, end_it);
+
+	if(!leftResid.empty())
+		pre_it = this->_set.insert(pre_it, leftResid);
 
-    add_(leftResid);
-    add_(rightResid);
+	if(!rightResid.empty())
+		this->_set.insert(pre_it, rightResid);
 }
 
 //-----------------------------------------------------------------------------

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-11 10:42:31 EDT (Thu, 11 Jun 2009)
@@ -6,8 +6,8 @@
       (See accompanying file LICENCE.txt or copy at
            http://www.boost.org/LICENSE_1_0.txt)
 +-----------------------------------------------------------------------------*/
-#ifndef __split_interval_map_h_JOFA_000706__
-#define __split_interval_map_h_JOFA_000706__
+#ifndef __itl_split_interval_map_h_JOFA_000706__
+#define __itl_split_interval_map_h_JOFA_000706__
 
 #include <boost/itl/interval_set.hpp>
 #include <boost/itl/interval_map.hpp>

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 10:42:31 EDT (Thu, 11 Jun 2009)
@@ -154,125 +154,103 @@
 
 
 template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-void split_interval_set<DomainT,Compare,Interval,Alloc>::add_(const value_type& x)
+void split_interval_set<DomainT,Compare,Interval,Alloc>::add_(const value_type& addend)
 {
-    if(x.empty()) return;
+    if(addend.empty()) return;
 
-    std::pair<typename ImplSetT::iterator,bool> insertion = this->_set.insert(x);
+    std::pair<typename ImplSetT::iterator,bool> insertion = this->_set.insert(addend);
 
     if(!insertion.WAS_SUCCESSFUL)
     {
-        iterator fst_it = this->_set.lower_bound(x);
-        iterator end_it = this->_set.upper_bound(x);
-
-        if(fst_it == this->_set.end())
-            fst_it = end_it;
-
-        iterator cur_it       = fst_it ;
-        interval_type cur_itv = *cur_it;
-
-        interval_type leadGap; x.right_subtract(leadGap, cur_itv);
-        // this is a new Interval that is a gap in the current map
-        add_(leadGap);
-
-        // only for the first there can be a leftResid: a part of *it left of x
-        interval_type leftResid;  cur_itv.right_subtract(leftResid, x);
+        iterator fst_it = this->_set.lower_bound(addend);
+        iterator end_it = this->_set.upper_bound(addend);
+		iterator lst_it = end_it; lst_it--;
+		iterator pre_it = fst_it;
+		if(pre_it != this->_set.begin())
+			--pre_it;
+
+		// handle the beginning of the sequence of intervals of *this
+		// overlapped by insertee inverval 'addend'
+		interval_type leadGap = right_subtract(addend, *fst_it);
+        // this is a new interval that is a gap in the current map
+		if(!leadGap.empty())
+			this->_set.insert(pre_it, leadGap);
+		else
+		{
+			interval_type leftResid = right_subtract(*fst_it, addend);
+			if(!leftResid.empty())
+			{
+				fst_it->left_subtract(leftResid);
+				this->_set.insert(pre_it, leftResid);
+			}
+		}
 
-        // handle special case for first
-        interval_type interSec = cur_itv & x;
+		// handle the ending of the sequence of intervals of *this
+		// overlapped by insertee inverval 'addend'
+		interval_type endGap = left_subtract(addend, *lst_it);
 
+		if(!endGap.empty())
+			this->_set.insert(lst_it, endGap);
+		else
+		{
+			//CL lst_it->left_subtract(rightResid, x);
+			interval_type rightResid = left_subtract(*lst_it, addend);
+			if(!rightResid.empty())
+			{
+				lst_it->right_subtract(rightResid);
+				this->_set.insert(lst_it, rightResid);
+			}
+		}
+        
         iterator snd_it = fst_it; snd_it++;
-        if(snd_it == end_it) 
-        {
-            // first == last
-
-            interval_type endGap; x.left_subtract(endGap, cur_itv);
-            // this is a new Interval that is a gap in the current map
-            add_(endGap);
-
-            // only for the last there can be a rightResid: a part of *it right of x
-            interval_type rightResid;  (*cur_it).left_subtract(rightResid, x);
-
-            this->_set.erase(cur_it);
-            add_(leftResid);
-            add_(interSec);
-            add_(rightResid);
-        }
-        else
-        {
-            this->_set.erase(cur_it);
-            add_(leftResid);
-            add_(interSec);
-
-            // shrink interval
-            interval_type x_rest(x);
-            x_rest.left_subtract(cur_itv);
-
-            insert_rest(x_rest, snd_it, end_it);
-        }
+        interval_type addend_rest = left_subtract(addend, *fst_it);
+        insert_rest(addend_rest, snd_it, end_it);
     }
 }
 
 
 template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-void split_interval_set<DomainT,Compare,Interval,Alloc>::insert_rest(interval_type& x_itv, iterator& it, iterator& end_it)
+void split_interval_set<DomainT,Compare,Interval,Alloc>::insert_rest(interval_type& addend, iterator& it, iterator& end_it)
 {
         interval_type left_gap, cur_itv;
-	while(it != end_it && !x_itv.empty())
+	iterator pred_it = it; --pred_it;
+	while(it != end_it)
         {
         cur_itv = *it;
-		x_itv.right_subtract(left_gap, cur_itv);
-        add_(left_gap);
-		if(x_itv.contains(cur_itv))
-		{
-			x_itv.left_subtract(cur_itv);
-			++it;
-		}
-		else
-		{
-			interval_type intersec = cur_itv & x_itv;
-			interval_type right_over; 
-			cur_itv.left_subtract(right_over, x_itv);
-			this->_set.erase(it);
-			add_(intersec);
-			add_(right_over);
-			x_itv.clear();
-		}
-	}
-
-	if(!x_itv.empty())
-	{
-		interval_type right_gap; 
-		x_itv.left_subtract(right_gap, cur_itv);
-		// this is a new Interval that is a gap in the current map
-		add_(right_gap);
+		left_gap = right_subtract(addend, cur_itv);
+		if(!left_gap.empty())
+			this->_set.insert(pred_it, left_gap);
+
+		pred_it = it;
+		addend.left_subtract(cur_itv);
+		++it;
         }
 }
 
 
 template <typename 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& x)
+void split_interval_set<DomainT,Compare,Interval,Alloc>::subtract_(const value_type& minuend)
 {
-    if(x.empty()) return;
+    if(minuend.empty()) return;
     if(this->_set.empty()) return;
 
     iterator fst_it;
-    if(x.exclusive_less(*(this->_set.begin())))
+    if(minuend.exclusive_less(*(this->_set.begin())))
         return;
-    if(x.lower() < this->_set.begin()->upper())
+    if(minuend.lower() < this->_set.begin()->upper())
         fst_it = this->_set.begin();
     else
-        fst_it = this->_set.lower_bound(x);
+        fst_it = this->_set.lower_bound(minuend);
 
     if(fst_it==this->_set.end()) return;
-    iterator end_it = this->_set.upper_bound(x);
+    iterator end_it = this->_set.upper_bound(minuend);
     if(fst_it==end_it) return;
 
     iterator cur_it = fst_it ;
     interval_type cur_itv   = *cur_it ;
 
-    // only for the first there can be a leftResid: a part of *it left of x
-    interval_type leftResid;  cur_itv.right_subtract(leftResid, x);
+    // 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
 
@@ -280,8 +258,8 @@
     if(snd_it == end_it) 
     {
         // first == last
-        // only for the last there can be a rightResid: a part of *it right of x
-        interval_type rightResid;  (*cur_it).left_subtract(rightResid, x);
+        // 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);
@@ -292,7 +270,7 @@
         // first AND NOT last
         this->_set.erase(cur_it);
         add_(leftResid);
-        subtract_rest(x, snd_it, end_it);
+        subtract_rest(minuend, snd_it, end_it);
     }
     return;
 }
@@ -324,7 +302,6 @@
     }
 }
 
-
 //==============================================================================
 //= Equivalences and Orderings
 //==============================================================================