[Boost-commit] svn:boost r54324 - in sandbox/itl/boost: itl validate/driver

Subject: [Boost-commit] svn:boost r54324 - in sandbox/itl/boost: itl validate/driver
From: afojgo_at_[hidden]
Date: 2009-06-24 18:26:04

Author: jofaber
Date: 2009-06-24 18:26:02 EDT (Wed, 24 Jun 2009)
New Revision: 54324
URL: http://svn.boost.org/trac/boost/changeset/54324

Log:
Refactoring: Improving (split_)interval_map::add,subtract. Stable {msvc-9.0} 
Text files modified: 
   sandbox/itl/boost/itl/interval_base_map.hpp                    |     9 +                                       
   sandbox/itl/boost/itl/interval_map.hpp                         |   221 +++++++++++---------------------------- 
   sandbox/itl/boost/itl/interval_set.hpp                         |    14 +-                                      
   sandbox/itl/boost/itl/split_interval_map.hpp                   |    24 ++-                                     
   sandbox/itl/boost/validate/driver/signed_quantifier_driver.hpp |     2                                         
   5 files changed, 92 insertions(+), 178 deletions(-)

Modified: sandbox/itl/boost/itl/interval_base_map.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_base_map.hpp	(original)
+++ sandbox/itl/boost/itl/interval_base_map.hpp	2009-06-24 18:26:02 EDT (Wed, 24 Jun 2009)
@@ -623,6 +623,15 @@
     sub_type& self() { return *that(); }
 
 protected:
+
+	iterator prior(iterator it_)
+	{
+		if(it_ == this->_map.begin())
+			return this->_map.end();
+		else
+			return --it_;
+	}
+
         template <class Combiner>
         bool combine(iterator& it_, const codomain_type& co_val)
         { 

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-24 18:26:02 EDT (Wed, 24 Jun 2009)
@@ -139,8 +139,11 @@
     bool join_right(iterator& it);
     void join_neighbours(iterator& it){ join_left(it); join_right(it); };
     bool joinable(const iterator& some, const iterator& next)const;
-    iterator joint_insert(iterator& some, const iterator& next);
+	iterator join_on_left(iterator& some, const iterator& next);
+	iterator join_on_right(const iterator& some, iterator& next);
+	iterator join_segments(iterator& some, const iterator& next){ return join_on_left(some, next); };//JODO ausbauen
 
+	/*
     template<class Combiner>
     iterator fill_gap_join_left(const value_type&);
 
@@ -152,6 +155,7 @@
 
     template<class Combiner>
     iterator fill_gap_join_both(iterator& prior_, const value_type&);
+	*/
 
     iterator fill_join_left(const value_type&);
     iterator fill_join_both(const value_type&);
@@ -200,7 +204,7 @@
 
 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>
-bool interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+inline bool interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
     ::joinable(const iterator& some, const iterator& next)const
 {
     // assert: next != end && some++ == next
@@ -208,16 +212,15 @@
         && some->CONT_VALUE == next->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>
-typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator 
+inline typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator 
     interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::joint_insert(iterator& left_it, const iterator& right_it)
+    ::join_on_left(iterator& left_it, const iterator& right_it)
 {
-    // both left and right are in the set and they are neighbours
-    BOOST_ASSERT(right_it != this->_map.end());
-    BOOST_ASSERT(left_it->KEY_VALUE.exclusive_less(right_it->KEY_VALUE));
-    BOOST_ASSERT(left_it->KEY_VALUE.touches(right_it->KEY_VALUE));
+    // both left and right are in the map and they are neighbours
+    BOOST_ASSERT(joinable(left_it, right_it));
 
     interval_type right_interval = right_it->KEY_VALUE;
     this->_map.erase(right_it);
@@ -226,10 +229,32 @@
     return left_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>
+inline typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator 
+    interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+    ::join_on_right(const iterator& left_it, iterator& right_it)
+{
+    // both left and right are in the map and they are neighbours
+    BOOST_ASSERT(joinable(left_it, right_it));
+
+	//JODO: This implementation does not work in very rare cases. Causes are not clear
+	//interval_type left_interval = left_it->KEY_VALUE;
+	//this->_map.erase(left_it);
+	//const_cast<interval_type&>(right_it->KEY_VALUE).extend(left_interval);
+
+    interval_type right_interval = right_it->KEY_VALUE;
+    this->_map.erase(right_it);
+	const_cast<interval_type&>(left_it->KEY_VALUE).extend(right_interval);
+	right_it = left_it;
+
+    return right_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>
-bool interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+inline bool interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
     ::join_left(iterator& it)
 {
     if(it == this->_map.begin())
@@ -240,9 +265,7 @@
 
     if(joinable(it_pred, it)) 
     {
-        iterator it_leftExtended = joint_insert(it_pred, it);
-        //CAUTION: it is now invalidated
-        it = it_leftExtended;
+		join_on_right(it_pred, it); 
         return true;
     }
 
@@ -262,7 +285,7 @@
 
     if(it_succ != this->_map.end() && joinable(it, it_succ)) 
     {
-        joint_insert(it, it_succ);
+        join_segments(it, it_succ);
         return true;
     }
 
@@ -270,132 +293,6 @@
 }
 
 
-
-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>
-typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
-interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::fill_join_left(const value_type& value)
-{
-    //collision free insert is asserted
-    if(value.KEY_VALUE.empty())
-        return this->_map.end();
-    if(Traits::absorbs_neutrons && value.CONT_VALUE == codomain_combine::neutron())
-        return this->_map.end();
-
-    std::pair<iterator,bool> insertion = this->_map.insert(value);
-
-    join_left(insertion.ITERATOR);
-
-    return insertion.ITERATOR;
-}
-
-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>
-typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
-interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::fill_join_both(const value_type& value)
-{
-    //collision free insert is asserted
-    if(value.KEY_VALUE.empty())
-        return this->_map.end();
-    if(Traits::absorbs_neutrons && value.CONT_VALUE == codomain_combine::neutron())
-        return this->_map.end();
-
-    std::pair<iterator,bool> insertion = this->_map.insert(value);
-
-    join_neighbours(insertion.ITERATOR);
-
-    return insertion.ITERATOR;
-}
-
-//-----------------------------------------------------------------------------
-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>
-typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
-interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::fill_gap_join_left(const value_type& value)//JODO hint prior_
-{
-    //collision free insert is asserted
-    if(value.KEY_VALUE.empty())
-        return this->_map.end();
-    if(Traits::absorbs_neutrons && value.CONT_VALUE == Combiner::neutron())
-        return this->_map.end();
-
-    std::pair<iterator,bool> insertion
-		= this->template map_insert(value.KEY_VALUE, value.CONT_VALUE);
-
-    join_left(insertion.ITERATOR);
-
-    return insertion.ITERATOR;
-}
-
-//-----------------------------------------------------------------------------
-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>
-typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
-interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::fill_gap_join_left(iterator& prior_, const value_type& value)
-{
-    //collision free insert is asserted
-    if(value.KEY_VALUE.empty())
-        return this->_map.end();
-    if(Traits::absorbs_neutrons && value.CONT_VALUE == Combiner::neutron())
-        return this->_map.end();
-
-    iterator insertion_
-		= this->template map_insert<Combiner>(prior_, value.KEY_VALUE, value.CONT_VALUE);
-
-	join_left(insertion_);
-
-    return insertion_;
-}
-
-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>
-typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
-interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::fill_gap_join_both(const value_type& value)
-{
-    //collision free insert is asserted
-    if(value.KEY_VALUE.empty())
-        return this->_map.end();
-    if(Traits::absorbs_neutrons && value.CONT_VALUE == Combiner::neutron())
-        return this->_map.end();
-
-	std::pair<iterator,bool> insertion
-		= this->template map_insert<Combiner>(value.KEY_VALUE, value.CONT_VALUE);
-
-    join_neighbours(insertion.ITERATOR);
-
-    return insertion.ITERATOR;
-}
-
-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>
-typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
-interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::fill_gap_join_both(iterator& prior_, const value_type& value)
-{
-    //collision free insert is asserted
-    if(value.KEY_VALUE.empty())
-        return this->_map.end();
-    if(Traits::absorbs_neutrons && value.CONT_VALUE == Combiner::neutron())
-        return this->_map.end();
-
-    iterator insertion_
-		= this->template map_insert<Combiner>(prior_, value.KEY_VALUE, value.CONT_VALUE);
-
-	join_neighbours(insertion_);
-
-    return insertion_;
-}
-
-
 //-----------------------------------------------------------------------------
 // add<Combinator>(pair(interval,value)):
 //-----------------------------------------------------------------------------
@@ -446,15 +343,12 @@
     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_;
+	{   //                     [------------ . . .
+		// [prior)  [left_resid---fst_it --- . . .
+		iterator prior_ = this->prior(first_);
                 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));
-		join_left(insertion_);
+		this->_map.insert(prior_, value_type(left_resid, first_->CONT_VALUE));
         }
 
         //POST:
@@ -489,12 +383,19 @@
         {
                 // [------ . . .
                 //     [-- it ...
-		iterator prior_ = it_; prior_--;
-		fill_gap_join_left<Combiner>(prior_, value_type(lead_gap, co_val));
+		iterator prior_ = it_; 
+		if(prior_ != this->_map.begin())
+		{
+			iterator inserted_ = this->template map_insert<Combiner>(--prior_, lead_gap, co_val);
+			if(joinable(prior_, inserted_))
+				join_on_right(prior_, inserted_);
+		}
+		else
+			this->template map_insert<Combiner>(lead_gap, co_val);
         }
 
-	// . . . ------------ . . . addend interval
-	//      [-- fst_it --)      has a common part with the first overval
+	// . . . --------- . . . addend interval
+	//      [-- 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_++);
@@ -512,20 +413,23 @@
 inline void interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
     ::add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it)
 {
-	iterator prior_ = it; --prior_;
+	iterator prior_ = this->prior(it);
     interval_type cur_itv = (*it).KEY_VALUE ;
 
     interval_type lead_gap = right_subtract(inter_val, cur_itv);
         if(!lead_gap.empty())
-		// [------ . . .
+	{	// [------ . . .
                 //     [-- it ...
-        fill_gap_join_left<Combiner>(prior_, value_type(lead_gap, co_val));
+		iterator inserted_ = this->template map_insert<Combiner>(prior_, lead_gap, co_val);
+		if(prior_ != this->_map.end() && joinable(prior_, inserted_))
+			join_on_left(prior_, inserted_);
+	}
 
     interval_type end_gap = left_subtract(inter_val, cur_itv);
         if(!end_gap.empty())
         {
-		// [------------------)
-		//      [-- it --)
+		// [-------------------)
+		//  . . . -- it --)
                 Combiner()(it->CONT_VALUE, co_val);
 
         if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
@@ -537,7 +441,8 @@
         else
                 {
             join_left(it);
-			fill_gap_join_both<Combiner>(it, value_type(end_gap, co_val));
+			iterator inserted_ = this->template map_insert<Combiner>(it, end_gap, co_val);
+			join_neighbours(inserted_);
                 }
         }
         else
@@ -620,9 +525,7 @@
 
     if(!left_resid.empty())
     {
-		iterator prior_ = it_;
-		if(prior_ != this->_map.begin())
-			--prior_;
+		iterator prior_ = this->prior(it_);
                 const_cast<interval_type&>(it_->KEY_VALUE).left_subtract(left_resid);
                 this->_map.insert(prior_, value_type(left_resid, it_->CONT_VALUE));
     }

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-24 18:26:02 EDT (Wed, 24 Jun 2009)
@@ -143,7 +143,7 @@
     /// Treatment of adjoint intervals on insertion
     void handle_neighbours(const iterator& it);
 
-    iterator joint_insert(const iterator& left_it, const iterator& right_it);
+    iterator join_segments(const iterator& left_it, const iterator& right_it);
 } ;
 
 
@@ -178,7 +178,7 @@
     {
         iterator it_nxt=it; it_nxt++;
         if(it_nxt!=this->_set.end() && (*it).touches(*it_nxt)) 
-            joint_insert(it, it_nxt);
+            join_segments(it, it_nxt);
     }
     else
     {
@@ -187,14 +187,14 @@
 
         if((*it_pred).touches(*it)) 
         {
-            iterator it_extended = joint_insert(it_pred, it);
+            iterator it_extended = join_segments(it_pred, it);
 
             iterator it_succ=it_extended; it_succ++;
             if(it_succ!=this->_set.end())
             {
                 // it's a non border element that might have two touching neighbours
                 if((*it_extended).touches(*it_succ)) 
-                    joint_insert(it_extended, it_succ);
+                    join_segments(it_extended, it_succ);
             }
         }
         else
@@ -204,7 +204,7 @@
             {
                 // it's a non border element that might have a right touching neighbours
                 if((*it).touches(*it_succ)) 
-                    joint_insert(it, it_succ);
+                    join_segments(it, it_succ);
             }
         }
     }
@@ -213,9 +213,9 @@
 
 
 template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-typename interval_set<DomainT,Compare,Interval,Alloc>::iterator 
+inline typename interval_set<DomainT,Compare,Interval,Alloc>::iterator 
     interval_set<DomainT,Compare,Interval,Alloc>
-    ::joint_insert(const iterator& left_it, const iterator& right_it)
+    ::join_segments(const iterator& left_it, const iterator& right_it)
 {
     // both left and right are in the set and they are neighbours
     BOOST_ASSERT((*left_it).exclusive_less(*right_it));

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-24 18:26:02 EDT (Wed, 24 Jun 2009)
@@ -295,9 +295,7 @@
         if(!left_resid.empty())
         {   //            [------------ . . .
                 // [left_resid---fst_it --- . . .
-		iterator prior_ = first_;
-		if(prior_ != this->_map.begin())
-			--prior_;
+		iterator prior_ = this->prior(first_);
                 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));
@@ -335,12 +333,15 @@
         {
                 // [------ . . .
                 //     [-- it ...
-		iterator prior_ = it_; prior_--;
-		fill_gap<Combiner>(prior_, lead_gap, co_val);
+		iterator prior_ = it_; 
+		if(prior_ != this->_map.begin())
+			this->template map_insert<Combiner>(--prior_, lead_gap, co_val);
+		else
+			this->template map_insert<Combiner>(lead_gap, co_val);
         }
 
-	// . . . ------------ . . . addend interval
-	//      [-- fst_it --)      has a common part with the first overval
+	// . . . --------- . . . addend interval
+	//      [-- 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_++);
@@ -355,14 +356,15 @@
 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)
 {
-	iterator prior_ = it; --prior_;
+	iterator prior_ = this->prior(it);
     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);
+		//         [------ . . .
+		// [prior)     [-- it ...
+		this->template map_insert<Combiner>(prior_, lead_gap, co_val);
+	
 
     interval_type end_gap = left_subtract(inter_val, cur_itv);
         if(!end_gap.empty())

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-24 18:26:02 EDT (Wed, 24 Jun 2009)
@@ -101,7 +101,7 @@
             switch(rootChoice)
             {
             //-----------------------------------------------------------------
-            case RootType::itl_map: { //JODO URG
+            case RootType::itl_map: {
                 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> >;