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
//==============================================================================