Subject: [Boost-commit] svn:boost r54908 - in sandbox/itl: boost/itl boost/validate/driver libs/itl/doc libs/itl/example/interval_container_ libs/itl/test/fastest_interval_set_mixed_ libs/itl/test/fastest_itl_interval_
From: afojgo_at_[hidden]
Date: 2009-07-12 08:29:55
Author: jofaber
Date: 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
New Revision: 54908
URL: http://svn.boost.org/trac/boost/changeset/54908
Log:
Adding optimized code, refactoring: Added member functions interval_container::add_(iterator& prior_, x)
that adds x using iterator prior_ as hint. Stable {msvc-9.0}
Added:
sandbox/itl/libs/itl/doc/implementation.qbk (contents, props changed)
Text files modified:
sandbox/itl/boost/itl/interval_base_map.hpp | 211 ++++++++++++----------
sandbox/itl/boost/itl/interval_base_set.hpp | 81 ++++----
sandbox/itl/boost/itl/interval_map.hpp | 366 +++++++++++++++++++++------------------
sandbox/itl/boost/itl/interval_maps.hpp | 3
sandbox/itl/boost/itl/interval_set.hpp | 136 +++++++++-----
sandbox/itl/boost/itl/interval_sets.hpp | 3
sandbox/itl/boost/itl/separate_interval_set.hpp | 75 +++++--
sandbox/itl/boost/itl/split_interval_map.hpp | 249 +++++++++++++++-----------
sandbox/itl/boost/itl/split_interval_set.hpp | 212 +++++++++++++++-------
sandbox/itl/boost/validate/driver/signed_quantifier_driver.hpp | 24 +-
sandbox/itl/libs/itl/doc/examples.qbk | 2
sandbox/itl/libs/itl/doc/interface.qbk | 2
sandbox/itl/libs/itl/doc/itl.qbk | 6
sandbox/itl/libs/itl/doc/semantics.qbk | 2
sandbox/itl/libs/itl/example/interval_container_/vc9_interval_container.vcproj | 4
sandbox/itl/libs/itl/test/fastest_interval_set_mixed_/fastest_interval_set_mixed.cpp | 1
sandbox/itl/libs/itl/test/fastest_itl_interval_/fastest_itl_interval.cpp | 1
17 files changed, 814 insertions(+), 564 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-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -203,8 +203,8 @@
/** Does the map contain the domain element \c key? */
bool contains(const domain_type& key)const
{
- typename ImplMapT::const_iterator it = _map.find(interval_type(key));
- return it != _map.end();
+ typename ImplMapT::const_iterator it_ = _map.find(interval_type(key));
+ return it_ != _map.end();
}
/** Does the map contain the <tt>key_value_pair = (key,value)</tt>? */
@@ -280,16 +280,16 @@
/** Find the interval value pair, that contains \c key */
const_iterator find(const domain_type& key)const
{
- const_iterator it = _map.find(interval_type(key));
- return it;
+ const_iterator it_ = _map.find(interval_type(key));
+ return it_;
}
/** Total select function. */
codomain_type operator()(const domain_type& key)const
{
- const_iterator it = _map.find(interval_type(key));
- return it==end() ? neutron<codomain_type>::value()
- : it->CONT_VALUE;
+ const_iterator it_ = _map.find(interval_type(key));
+ return it_==end() ? neutron<codomain_type>::value()
+ : it_->CONT_VALUE;
}
@@ -314,6 +314,9 @@
SubType& add(const segment_type& interval_value_pair)
{ that()->template add_<codomain_combine>(interval_value_pair); return *that(); }
+ iterator add(iterator prior_, const segment_type& interval_value_pair)
+ { return that()->template add_<codomain_combine>(prior_, interval_value_pair); }
+
//==========================================================================
//= Subtraction
//==========================================================================
@@ -469,9 +472,9 @@
if(!Set::common_range(common_lwb, common_upb, sectant, *this))
return;
- typename sectant_type::const_iterator it = common_lwb;
- while(it != common_upb)
- add_intersection(section, *it++);
+ typename sectant_type::const_iterator it_ = common_lwb;
+ while(it_ != common_upb)
+ add_intersection(section, *it_++);
}
@@ -584,8 +587,8 @@
void domain(IntervalSet<DomainT,Compare,Interval,Alloc>& dom)const
{
dom.clear();
- const_FOR_IMPLMAP(it)
- dom += (*it).KEY_VALUE;
+ const_FOR_IMPLMAP(it_)
+ dom += (*it_).KEY_VALUE;
}
/* Sum of associated elements of the map */
@@ -625,12 +628,7 @@
protected:
iterator prior(iterator it_)
- {
- if(it_ == this->_map.begin())
- return this->_map.end();
- else
- return --it_;
- }
+ { return it_ == this->_map.begin() ? this->_map.end() : --it_; }
template <class Combiner>
bool combine(iterator& it_, const codomain_type& co_val)
@@ -648,26 +646,41 @@
{
CodomainT added_val = Combiner::neutron();
Combiner()(added_val, co_val);
- if(Traits::absorbs_neutrons && added_val == Combiner::neutron())
- return std::pair<iterator,bool>(this->_map.end(), false);
- else
- return this->_map.insert(value_type(inter_val, added_val));
+ return this->_map.insert(value_type(inter_val, added_val));
}
else
return this->_map.insert(value_type(inter_val, co_val));
}
+ // Insertion with hint, that does report insertion failure
+ template <class Combiner>
+ std::pair<iterator, bool>
+ map_insert(iterator prior_, const interval_type& inter_val, const codomain_type& co_val)
+ {
+ iterator inserted_
+ = this->_map.insert(prior_, value_type(inter_val, Combiner::neutron()));
+
+ if(inserted_->KEY_VALUE == inter_val && inserted_->CONT_VALUE == Combiner::neutron())
+ {
+ Combiner()(inserted_->CONT_VALUE, co_val);
+ return std::pair<iterator,bool>(inserted_, true);
+ }
+ else
+ return std::pair<iterator,bool>(inserted_, false);
+ }
+
template <class Combiner>
- iterator map_insert(iterator& prior_, const interval_type& inter_val, const codomain_type& co_val)
+ iterator gap_insert(iterator prior_, const interval_type& inter_val, const codomain_type& co_val)
{
+ // inter_val is not conained in this map. Insertion will be successful
+ BOOST_ASSERT(this->_map.find(inter_val) == this->_map.end());
+ BOOST_ASSERT(!(Traits::absorbs_neutrons && co_val==Combiner::neutron()));
+
if(Traits::is_total)
{
- CodomainT added_val = Combiner::neutron();
- Combiner()(added_val, co_val);
- if(Traits::absorbs_neutrons && added_val == Combiner::neutron())
- return this->_map.end();
- else
- return this->_map.insert(prior_, value_type(inter_val, added_val));
+ iterator inserted_ = this->_map.insert(prior_, value_type(inter_val, Combiner::neutron()));
+ Combiner()(inserted_->CONT_VALUE, co_val);
+ return inserted_;
}
else
return this->_map.insert(prior_, value_type(inter_val, co_val));
@@ -711,8 +724,8 @@
Compare,Combine,Section,Interval,Alloc>::length()const
{
difference_type length = neutron<difference_type>::value();
- const_FOR_IMPLMAP(it)
- length += (*it).KEY_VALUE.length();
+ const_FOR_IMPLMAP(it_)
+ length += (*it_).KEY_VALUE.length();
return length;
}
@@ -760,9 +773,9 @@
typename sectant_type::const_iterator common_upb;
if(!Set::common_range(common_lwb, common_upb, sectant, *this))
return;
- typename sectant_type::const_iterator it = common_lwb;
- while(it != common_upb)
- add_intersection(intersection, *it++);
+ typename sectant_type::const_iterator it_ = common_lwb;
+ while(it_ != common_upb)
+ add_intersection(intersection, *it_++);
}
}
@@ -786,16 +799,16 @@
interval_type sectant_interval = sectant.KEY_VALUE;
if(sectant_interval.empty()) return;
- typename ImplMapT::const_iterator fst_it = _map.lower_bound(sectant_interval);
- typename ImplMapT::const_iterator end_it = _map.upper_bound(sectant_interval);
+ typename ImplMapT::const_iterator first_ = _map.lower_bound(sectant_interval);
+ typename ImplMapT::const_iterator end_ = _map.upper_bound(sectant_interval);
- for(typename ImplMapT::const_iterator it=fst_it; it != end_it; it++)
+ for(typename ImplMapT::const_iterator it_=first_; it_ != end_; it_++)
{
- interval_type common_interval = ((*it).KEY_VALUE) & sectant_interval;
+ interval_type common_interval = ((*it_).KEY_VALUE) & sectant_interval;
if(!common_interval.empty())
{
- section.that()->add( value_type(common_interval, (*it).CONT_VALUE) );
+ section.that()->add( value_type(common_interval, (*it_).CONT_VALUE) );
if(is_set<CodomainT>::value)
section.that()->template add<codomain_intersect>(value_type(common_interval, sectant.CONT_VALUE));
else
@@ -818,14 +831,14 @@
{
if(sectant_interval.empty()) return;
- typename ImplMapT::const_iterator fst_it = _map.lower_bound(sectant_interval);
- typename ImplMapT::const_iterator end_it = _map.upper_bound(sectant_interval);
+ typename ImplMapT::const_iterator first_ = _map.lower_bound(sectant_interval);
+ typename ImplMapT::const_iterator end_ = _map.upper_bound(sectant_interval);
- for(typename ImplMapT::const_iterator it=fst_it; it != end_it; it++)
+ for(typename ImplMapT::const_iterator it_=first_; it_ != end_; it_++)
{
- interval_type common_interval = ((*it).KEY_VALUE) & sectant_interval;
+ interval_type common_interval = ((*it_).KEY_VALUE) & sectant_interval;
if(!common_interval.empty())
- section.that()->add( value_type(common_interval, (*it).CONT_VALUE) );
+ section.that()->add( value_type(common_interval, (*it_).CONT_VALUE) );
}
}
@@ -864,20 +877,20 @@
interval_type span = interval_value_pair.KEY_VALUE;
- typename ImplMapT::const_iterator fst_it = _map.lower_bound(span);
- typename ImplMapT::const_iterator end_it = _map.upper_bound(span);
+ typename ImplMapT::const_iterator first_ = _map.lower_bound(span);
+ typename ImplMapT::const_iterator end_ = _map.upper_bound(span);
interval_type covered, left_over, common_interval;
const codomain_type& x_value = interval_value_pair.CONT_VALUE;
- typename ImplMapT::const_iterator it = fst_it;
+ typename ImplMapT::const_iterator it_ = first_;
interval_set<DomainT,Compare,Interval,Alloc> eraser;
interval_base_map intersection;
- while(it != end_it)
+ while(it_ != end_ )
{
- const codomain_type& co_value = it->CONT_VALUE;
- covered = (*it++).KEY_VALUE;
+ const codomain_type& co_value = it_->CONT_VALUE;
+ covered = (*it_++).KEY_VALUE;
//[a ... : span
// [b ... : covered
//[a b) : left_over
@@ -904,7 +917,7 @@
// Because this is a collision free addition I don't have to distinguish codomain_types.
//... d) : span
- //... c) : (*it); span.left_subtract(*it);
+ //... c) : (*it_); span.left_subtract(*it_);
// [c d) : span'
span.left_subtract(covered);
}
@@ -957,17 +970,17 @@
if(!Set::common_range(common_lwb, common_upb, operand, *this))
return *that() += operand;
- typename operand_type::const_iterator it = operand.begin();
+ typename operand_type::const_iterator it_ = operand.begin();
// All elements of operand left of the common range are added
- while(it != common_lwb)
- add(*it++);
+ while(it_ != common_lwb)
+ add(*it_++);
// All elements of operand in the common range are symmetrically subtracted
- while(it != common_upb)
- flip(*it++);
+ while(it_ != common_upb)
+ flip(*it_++);
// All elements of operand right of the common range are added
- while(it != operand.end())
- add(*it++);
+ while(it_ != operand.end())
+ add(*it_++);
if(Traits::is_total && !Traits::absorbs_neutrons)
FORALL(typename ImplMapT, it_, _map)
@@ -986,42 +999,42 @@
interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
::join()
{
- iterator it=_map.begin();
- if(it==_map.end())
+ iterator it_=_map.begin();
+ if(it_==_map.end())
return *this;
- iterator nxt=it; nxt++;
+ iterator nxt=it_; nxt++;
if(nxt==_map.end())
return *this;
while(nxt != _map.end())
{
- if( (*it).KEY_VALUE.touches((*nxt).KEY_VALUE)
- && (*it).CONT_VALUE == (*nxt).CONT_VALUE )
+ if( (*it_).KEY_VALUE.touches((*nxt).KEY_VALUE)
+ && (*it_).CONT_VALUE == (*nxt).CONT_VALUE )
{
- iterator fst_mem = it; // hold the fist member
+ iterator fst_mem = it_; // hold the fist member
// go noodling on while touchin members found
- it++; nxt++;
+ it_++; nxt++;
while( nxt != _map.end()
- && (*it).KEY_VALUE.touches((*nxt).KEY_VALUE)
- && (*it).CONT_VALUE == (*nxt).CONT_VALUE )
- { it++; nxt++; }
+ && (*it_).KEY_VALUE.touches((*nxt).KEY_VALUE)
+ && (*it_).CONT_VALUE == (*nxt).CONT_VALUE )
+ { it_++; nxt++; }
// finally we arrive at the end of a sequence of joinable intervals
// and it points to the last member of that sequence
- iterator lst_mem = it, end_mem = nxt;
+ iterator lst_mem = it_, end_mem = nxt;
interval_type joinedInterval((*fst_mem).KEY_VALUE);
joinedInterval.extend((*lst_mem).KEY_VALUE);
CodomainT value = (*fst_mem).CONT_VALUE; //CodomainT::OP =
_map.erase(fst_mem, end_mem);
- it = _map.insert(value_type(joinedInterval, value)).ITERATOR;
+ it_ = _map.insert(value_type(joinedInterval, value)).ITERATOR;
- it++; // go on for the next after the currently inserted
- nxt=it; if(nxt!=_map.end())nxt++;
+ it_++; // go on for the next after the currently inserted
+ nxt=it_; if(nxt!=_map.end())nxt++;
}
- else { it++; nxt++; }
+ else { it_++; nxt++; }
}
return *this;
}
@@ -1035,11 +1048,11 @@
std::string interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::as_string()const
{
std::string res("");
- const_FOR_IMPLMAP(it) {
+ const_FOR_IMPLMAP(it_) {
std::string cur("(");
- cur += (*it).KEY_VALUE.as_string();
+ cur += (*it_).KEY_VALUE.as_string();
cur += ",";
- cur += itl::to_string<CodomainT>::apply((*it).CONT_VALUE);
+ cur += itl::to_string<CodomainT>::apply((*it_).CONT_VALUE);
cur += ")";
res += cur;
}
@@ -1056,8 +1069,8 @@
::sum(codomain_type& total)const
{
total = codomain_combine::neutron();
- const_FOR_IMPLMAP(it)
- total += (*it).CONT_VALUE;
+ const_FOR_IMPLMAP(it_)
+ total += (*it_).CONT_VALUE;
}
@@ -1070,7 +1083,7 @@
{
// I can do this only, because I am shure that the contents and the
// ordering < on interval is invariant wrt. this transformation on bounds
- FOR_IMPLMAP(it) const_cast<interval_type&>((*it).KEY_VALUE).as(bounded);
+ FOR_IMPLMAP(it_) const_cast<interval_type&>((*it_).KEY_VALUE).as(bounded);
}
@@ -1085,43 +1098,43 @@
if(minuend.empty())
return *that();
- iterator fst_it = _map.lower_bound(minuend);
- if(fst_it==_map.end())
+ iterator first_ = _map.lower_bound(minuend);
+ if(first_==_map.end())
return *that();
- iterator end_it = _map.upper_bound(minuend);
- if(fst_it==end_it)
+ iterator end_ = _map.upper_bound(minuend);
+ if(first_==end_ )
return *that();
- iterator lst_it = end_it; --lst_it;
+ iterator last_ = end_; --last_;
- interval_type left_resid = right_subtract(fst_it->KEY_VALUE, minuend);
- interval_type right_resid = left_subtract(lst_it->KEY_VALUE, minuend);
+ interval_type left_resid = right_subtract(first_->KEY_VALUE, minuend);
+ interval_type right_resid = left_subtract(last_ ->KEY_VALUE, minuend);
- if(fst_it == lst_it)
+ if(first_ == last_ )
if(!left_resid.empty())
{
- const_cast<interval_type&>(fst_it->KEY_VALUE).right_subtract(minuend);
+ const_cast<interval_type&>(first_->KEY_VALUE).right_subtract(minuend);
if(!right_resid.empty())
- this->_map.insert(fst_it, value_type(right_resid, fst_it->CONT_VALUE));
+ this->_map.insert(first_, value_type(right_resid, first_->CONT_VALUE));
}
else if(!right_resid.empty())
- const_cast<interval_type&>(fst_it->KEY_VALUE).left_subtract(minuend);
+ const_cast<interval_type&>(first_->KEY_VALUE).left_subtract(minuend);
else
- this->_map.erase(fst_it);
+ this->_map.erase(first_);
else
- { // [-------- minuend ---------)
+ { // [-------- minuend ---------)
// [left_resid fst) . . . . [lst right_resid)
- iterator snd_it = fst_it; ++snd_it;
+ iterator second_= first_; ++second_;
- iterator start_ = left_resid.empty()? fst_it: snd_it;
- iterator stop_ = right_resid.empty()? end_it: lst_it;
+ iterator start_ = left_resid.empty()? first_: second_;
+ iterator stop_ = right_resid.empty()? end_ : last_ ;
this->_map.erase(start_, stop_); //erase [start_, stop_)
if(!left_resid.empty())
- const_cast<interval_type&>(fst_it->KEY_VALUE).right_subtract(minuend);
+ const_cast<interval_type&>(first_->KEY_VALUE).right_subtract(minuend);
if(!right_resid.empty())
- const_cast<interval_type&>(lst_it->KEY_VALUE).left_subtract(minuend);
+ const_cast<interval_type&>(last_ ->KEY_VALUE).left_subtract(minuend);
}
return *that();
}
@@ -1299,8 +1312,8 @@
typedef interval_base_map<SubType,DomainT,CodomainT,
Traits,Compare,Combine,Section,Interval,Alloc> IntervalMapT;
stream << "{";
- const_FORALL(typename IntervalMapT, it, object)
- stream << "(" << (*it).KEY_VALUE << "->" << (*it).CONT_VALUE << ")";
+ const_FORALL(typename IntervalMapT, it_, object)
+ stream << "(" << (*it_).KEY_VALUE << "->" << (*it_).CONT_VALUE << ")";
return stream << "}";
}
Modified: sandbox/itl/boost/itl/interval_base_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_base_set.hpp (original)
+++ sandbox/itl/boost/itl/interval_base_set.hpp 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -232,8 +232,8 @@
/** Find the interval value pair, that contains element \c key */
const_iterator find(const element_type& key)const
{
- typename ImplSetT::const_iterator it = this->_set.find(interval_type(key));
- return it;
+ typename ImplSetT::const_iterator it_ = this->_set.find(interval_type(key));
+ return it_;
}
//==========================================================================
@@ -248,6 +248,9 @@
SubType& add(const segment_type& inter_val)
{ that()->add_(inter_val); return *that(); }
+ iterator add(iterator prior_, const segment_type& inter_val)
+ { return that()->add_(prior_, inter_val); }
+
//==========================================================================
//= Subtraction
//==========================================================================
@@ -371,7 +374,7 @@
/** Interval container's string representation */
const std::string as_string()const
- { std::string res(""); const_FOR_IMPL(it) res += (*it).as_string(); return res; }
+ { std::string res(""); const_FOR_IMPL(it_) res += (*it_).as_string(); return res; }
//==========================================================================
@@ -400,6 +403,10 @@
sub_type& self() { return *that(); }
protected:
+ iterator prior(iterator it_)
+ { return it_ == this->_set.begin() ? this->_set.end() : --it_; }
+
+protected:
ImplSetT _set;
} ;
@@ -446,8 +453,8 @@
interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::length()const
{
difference_type length = neutron<difference_type>::value();
- const_FOR_IMPL(it)
- length += (*it).length();
+ const_FOR_IMPL(it_)
+ length += (*it_).length();
return length;
}
@@ -460,11 +467,11 @@
if(inter_val.empty())
return;
- typename ImplSetT::const_iterator fst_it = _set.lower_bound(inter_val);
- typename ImplSetT::const_iterator end_it = _set.upper_bound(inter_val);
+ typename ImplSetT::const_iterator first_ = _set.lower_bound(inter_val);
+ typename ImplSetT::const_iterator end_ = _set.upper_bound(inter_val);
- for(typename ImplSetT::const_iterator it=fst_it; it != end_it; it++)
- section.add((*it) & inter_val);
+ for(typename ImplSetT::const_iterator it_=first_; it_ != end_; it_++)
+ section.add((*it_) & inter_val);
}
@@ -494,9 +501,9 @@
if(!Set::common_range(common_lwb, common_upb, operand, *this))
return;
- typename operand_type::const_iterator it = common_lwb;
- while(it != common_upb)
- add_intersection(intersection, *it++);
+ typename operand_type::const_iterator it_ = common_lwb;
+ while(it_ != common_upb)
+ add_intersection(intersection, *it_++);
}
//==============================================================================
@@ -528,12 +535,12 @@
add(left_over); //That which is not shall be added
//... d) : span
- //... c) : (*it); span.left_subtract(*it);
+ //... c) : (*it_); span.left_subtract(*it_);
// [c d) : span'
span.left_subtract(covered);
}
- //If span is not empty here, it is not in the set so it shall be added
+ //If span is not empty here, it_ is not in the set so it_ shall be added
add(span);
return *that();
}
@@ -559,17 +566,17 @@
if(!Set::common_range(common_lwb, common_upb, operand, *this))
return *that() += operand;
- typename operand_type::const_iterator it = operand.begin();
+ typename operand_type::const_iterator it_ = operand.begin();
// All elements of operand left of the common range are added
- while(it != common_lwb)
- add(*it++);
+ while(it_ != common_lwb)
+ add(*it_++);
// All elements of operand in the common range are symmertrically subtracted
- while(it != common_upb)
- flip(*it++);
+ while(it_ != common_upb)
+ flip(*it_++);
// All elements of operand right of the common range are added
- while(it != operand.end())
- add(*it++);
+ while(it_ != operand.end())
+ add(*it_++);
return *that();
}
@@ -580,39 +587,39 @@
interval_base_set<SubType,DomainT,Compare,Interval,Alloc>&
interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::join()
{
- iterator it=_set.begin();
- if(it==_set.end())
+ iterator it_=_set.begin();
+ if(it_==_set.end())
return *this;
- iterator nxt=it; nxt++;
+ iterator nxt=it_; nxt++;
if(nxt==_set.end())
return *this;
while(nxt != _set.end())
{
- if( (*it).touches(*nxt) )
+ if( (*it_).touches(*nxt) )
{
- iterator fst_mem = it; // hold the fist member
+ iterator fst_mem = it_; // hold the fist member
// go noodling on while touchin members found
- it++; nxt++;
+ it_++; nxt++;
while( nxt != _set.end()
- && (*it).touches(*nxt) )
- { it++; nxt++; }
+ && (*it_).touches(*nxt) )
+ { it_++; nxt++; }
// finally we arrive at the end of a sequence of joinable intervals
// and it points to the last member of that sequence
- iterator lst_mem = it, end_mem = nxt;
+ iterator lst_mem = it_, end_mem = nxt;
interval_type joinedInterval(*fst_mem);
joinedInterval.extend(*lst_mem);
_set.erase(fst_mem, end_mem);
- it = _set.insert(joinedInterval).ITERATOR;
+ it_ = _set.insert(joinedInterval).ITERATOR;
- it++; // go on for the next after the currently inserted
- nxt=it; if(nxt!=_set.end())nxt++;
+ it_++; // go on for the next after the currently inserted
+ nxt=it_; if(nxt!=_set.end())nxt++;
}
- else { it++; nxt++; }
+ else { it_++; nxt++; }
}
return *this;
}
@@ -625,7 +632,7 @@
{
// I can do this only, because I am shure that the contents and the
// ordering < on interval is invariant wrt. this transformation on bounds
- FOR_IMPL(it) const_cast<interval_type&>(*it).as(bounded);
+ FOR_IMPL(it_) const_cast<interval_type&>(*it_).as(bounded);
}
@@ -690,8 +697,8 @@
{
typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> IntervalSetT;
stream << "{";
- const_FORALL(typename IntervalSetT, it, object)
- stream << (*it);
+ const_FORALL(typename IntervalSetT, it_, object)
+ stream << (*it_);
return stream << "}";
}
Modified: sandbox/itl/boost/itl/interval_map.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_map.hpp (original)
+++ sandbox/itl/boost/itl/interval_map.hpp 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -103,8 +103,8 @@
Traits,Compare,Combine,Section,Interval,Alloc> base_map_type;
this->clear();
// Can be implemented via _map.insert: Interval joining not necessary.
- const_FORALL(typename base_map_type, it, src)
- this->add(*it);
+ const_FORALL(typename base_map_type, it_, src)
+ this->add(*it_);
}
private:
@@ -123,6 +123,9 @@
void add_(const value_type&);
template<class Combiner>
+ iterator add_(iterator prior_, const value_type&);
+
+ template<class Combiner>
void subtract_(const value_type&);
void insert_(const value_type& value);
@@ -135,13 +138,12 @@
&& !(Traits::absorbs_neutrons && value.CONT_VALUE == codomain_combine::neutron());
}
- bool join_left(iterator& it);
- bool join_right(iterator& it);
- void join_neighbours(iterator& it){ join_left(it); join_right(it); };
+ iterator join_left(iterator& it_);
+ iterator join_right(iterator& it_);
+ iterator join_neighbours(iterator& it_){ join_left(it_); return join_right(it_); };
bool joinable(const iterator& some, const iterator& next)const;
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>
void add_main(interval_type& inter_val, const CodomainT& co_val,
@@ -157,16 +159,16 @@
template<class Combiner>
void subtract_main(const interval_type& inter_val, const CodomainT& co_val,
- iterator& it, iterator& end_it);
+ iterator& it_, iterator& end_ );
void subtract_front(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
template<class Combiner>
- void subtract_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it);
+ void subtract_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
- void insert_range(const interval_type& inter_val, const CodomainT& co_val, iterator& it, iterator& end_it);
+ void insert_range(const interval_type& inter_val, const CodomainT& co_val, iterator& it_, iterator& end_ );
- void erase_rest(const interval_type& inter_val, const CodomainT& co_val, iterator& it, iterator& lst_it);
+ void erase_rest(const interval_type& inter_val, const CodomainT& co_val, iterator& it_, iterator& last_);
} ;
@@ -200,79 +202,74 @@
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_left(iterator& left_it, const iterator& right_it)
+ ::join_on_left(iterator& left_, const iterator& right_)
{
// both left and right are in the map and they are neighbours
- BOOST_ASSERT(joinable(left_it, right_it));
+ BOOST_ASSERT(joinable(left_, right_));
- interval_type right_interval = right_it->KEY_VALUE;
- this->_map.erase(right_it);
- const_cast<interval_type&>(left_it->KEY_VALUE).extend(right_interval);
+ interval_type right_interval = right_->KEY_VALUE;
+ this->_map.erase(right_);
+ const_cast<interval_type&>(left_->KEY_VALUE).extend(right_interval);
- return left_it;
+ return left_;
}
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)
+ ::join_on_right(const iterator& left_, iterator& right_)
{
// both left and right are in the map and they are neighbours
- BOOST_ASSERT(joinable(left_it, right_it));
+ BOOST_ASSERT(joinable(left_, right_));
//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;
+ //interval_type left_interval = left_->KEY_VALUE;
+ //this->_map.erase(left_);
+ //const_cast<interval_type&>(right_->KEY_VALUE).extend(left_interval);
+
+ interval_type right_interval = right_->KEY_VALUE;
+ this->_map.erase(right_);
+ const_cast<interval_type&>(left_->KEY_VALUE).extend(right_interval);
+ right_ = left_;
- return right_it;
+ return right_;
}
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 bool interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::join_left(iterator& it)
+inline typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
+ interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::join_left(iterator& it_)
{
- if(it == this->_map.begin())
- return false;
+ if(it_ == this->_map.begin())
+ return it_;
// there is a predecessor
- iterator it_pred = it; it_pred-- ;
-
- if(joinable(it_pred, it))
- {
- join_on_right(it_pred, it);
- return true;
- }
+ iterator pred_ = it_;
+ if(joinable(--pred_, it_))
+ return join_on_right(pred_, it_);
- return false;
+ return 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 bool interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::join_right(iterator& it)
+inline typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
+ interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::join_right(iterator& it_)
{
- if(it == this->_map.end())
- return false;
+ if(it_ == this->_map.end())
+ return it_;
// there is a successor
- iterator it_succ = it; it_succ++ ;
+ iterator succ_ = it_;
- if(it_succ != this->_map.end() && joinable(it, it_succ))
- {
- join_segments(it, it_succ);
- return true;
- }
+ if(++succ_ != this->_map.end() && joinable(it_, succ_))
+ return join_on_left(it_, succ_);
- return false;
+ return it_;
}
@@ -281,14 +278,14 @@
//-----------------------------------------------------------------------------
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>
-void interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::add_(const value_type& x)
+inline void interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::add_(const value_type& addend)
{
- const interval_type& inter_val = x.KEY_VALUE;
+ const interval_type& inter_val = addend.KEY_VALUE;
if(inter_val.empty())
return;
- const CodomainT& co_val = x.CONT_VALUE;
+ const CodomainT& co_val = addend.CONT_VALUE;
if(Traits::absorbs_neutrons && co_val==Combiner::neutron())
return;
@@ -300,34 +297,72 @@
else
{
// Detect the first and the end iterator of the collision sequence
- iterator fst_it = this->_map.lower_bound(inter_val),
- lst_it = insertion.ITERATOR;
- //assert(end_it == this->_map.upper_bound(inter_val));
+ iterator first_ = this->_map.lower_bound(inter_val),
+ last_ = insertion.ITERATOR;
+ //assert(end_ == this->_map.upper_bound(inter_val));
- iterator it_ = fst_it;
+ iterator it_ = first_;
interval_type rest_interval = inter_val;
add_front (rest_interval, co_val, it_);
- add_main<Combiner>(rest_interval, co_val, it_, lst_it);
+ add_main<Combiner>(rest_interval, co_val, it_, last_);
add_rear<Combiner>(rest_interval, co_val, 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>
+ template<class Combiner>
+inline typename interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
+ interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::add_(iterator prior_, const value_type& addend)
+{
+ const interval_type& inter_val = addend.KEY_VALUE;
+ if(inter_val.empty())
+ return prior_;
+
+ const CodomainT& co_val = addend.CONT_VALUE;
+ if(Traits::absorbs_neutrons && co_val==Combiner::neutron())
+ return prior_;
+
+ std::pair<iterator,bool> insertion
+ = this->template map_insert<Combiner>(prior_, inter_val, co_val);
+
+ if(insertion.WAS_SUCCESSFUL)
+ return join_neighbours(insertion.ITERATOR);
+ else
+ {
+ // Detect the first and the end iterator of the collision sequence
+ iterator first_ = this->_map.lower_bound(inter_val),
+ last_ = insertion.ITERATOR;
+ //assert(end_ == this->_map.upper_bound(inter_val));
+
+ iterator it_ = first_;
+ interval_type rest_interval = inter_val;
+
+ add_front (rest_interval, co_val, it_);
+ add_main<Combiner>(rest_interval, co_val, it_, last_);
+ add_rear<Combiner>(rest_interval, co_val, it_);
+
+ return 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 void interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
::add_front(const interval_type& inter_val, const CodomainT& co_val, iterator& first_)
{
- // If the collision sequence has a right residual 'right_resid' is will
+ // If the collision sequence has a left residual 'left_resid' it will
// be split, to provide a standardized start of algorithms:
- // The addend interval 'inver_val' covers the beginning of the collision sequence.
+ // The addend interval 'inter_val' covers the beginning of the collision sequence.
// only for the first there can be a left_resid: a part of *first_ left of inter_val
interval_type left_resid = right_subtract(first_->KEY_VALUE, inter_val);
if(!left_resid.empty())
{ // [------------ . . .
- // [prior) [left_resid---fst_it --- . . .
+ // [prior) [left_resid---first_ --- . . .
iterator prior_ = this->prior(first_);
const_cast<interval_type&>(first_->KEY_VALUE).left_subtract(left_resid);
//NOTE: Only splitting
@@ -343,13 +378,13 @@
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>
inline void interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::add_main(interval_type& x_rest, const CodomainT& co_val, iterator& it, const iterator& lst_it)
+ ::add_main(interval_type& x_rest, const CodomainT& co_val, iterator& it_, const iterator& last_)
{
interval_type cur_interval;
- while(it!=lst_it)
+ while(it_!=last_)
{
- cur_interval = it->KEY_VALUE ;
- add_segment<Combiner>(x_rest, co_val, it);
+ cur_interval = it_->KEY_VALUE ;
+ add_segment<Combiner>(x_rest, co_val, it_);
// shrink interval
x_rest.left_subtract(cur_interval);
}
@@ -364,17 +399,12 @@
interval_type lead_gap = right_subtract(inter_val, it_->KEY_VALUE);
if(!lead_gap.empty())
{
- // [------ . . .
- // [-- it ...
- 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);
+ // [lead_gap--- . . .
+ // [-- it_ ...
+ iterator prior_ = prior(it_);
+ iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val);
+ if(prior_ != this->_map.end() && joinable(prior_, inserted_))
+ join_on_right(prior_, inserted_);
}
// . . . --------- . . . addend interval
@@ -394,16 +424,16 @@
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>
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)
+ ::add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_)
{
- iterator prior_ = this->prior(it);
- interval_type cur_itv = (*it).KEY_VALUE ;
+ 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 ...
- iterator inserted_ = this->template map_insert<Combiner>(prior_, lead_gap, co_val);
+ { // [lead_gap--- . . .
+ // [prior) [-- it_ ...
+ iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val);
if(prior_ != this->_map.end() && joinable(prior_, inserted_))
join_on_left(prior_, inserted_);
}
@@ -411,57 +441,63 @@
interval_type end_gap = left_subtract(inter_val, cur_itv);
if(!end_gap.empty())
{
- // [-------------------)
- // . . . -- it --)
- Combiner()(it->CONT_VALUE, co_val);
+ // [----------------end_gap)
+ // . . . -- it_ --)
+ Combiner()(it_->CONT_VALUE, co_val);
- if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
+ if(Traits::absorbs_neutrons && it_->CONT_VALUE == Combiner::neutron())
{
- this->_map.erase(it);
- iterator inserted_ = this->template map_insert<Combiner>(prior_, end_gap, co_val);
- join_right(inserted_);
+ this->_map.erase(it_);
+ it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val);
+ join_right(it_);
}
else
{
- join_left(it);
- iterator inserted_ = this->template map_insert<Combiner>(it, end_gap, co_val);
- join_neighbours(inserted_);
+ join_left(it_);
+ iterator inserted_ = this->template gap_insert<Combiner>(it_, end_gap, co_val);
+ it_ = join_neighbours(inserted_);
}
}
else
{
- // only for the last there can be a right_resid: a part of *it right of x
+ // only for the last there can be a right_resid: a part of *it_ right of x
interval_type right_resid = left_subtract(cur_itv, inter_val);
if(right_resid.empty())
{
// [---------------)
- // [-- it ----)
- Combiner()(it->CONT_VALUE, co_val);
+ // [-- it_ ---)
+ Combiner()(it_->CONT_VALUE, co_val);
- if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
- this->_map.erase(it);
+ if(Traits::absorbs_neutrons && it_->CONT_VALUE == Combiner::neutron())
+ {
+ this->_map.erase(it_);
+ it_ = prior_;
+ }
else
- join_neighbours(it);
+ join_neighbours(it_);
}
else
{
- // [-------------)
- // [-- it ---right_resid)
- const_cast<interval_type&>(it->KEY_VALUE).right_subtract(right_resid);
+ // [--------------)
+ // [-- it_ --right_resid)
+ const_cast<interval_type&>(it_->KEY_VALUE).right_subtract(right_resid);
//NOTE: This is NOT an insertion that has to take care for correct application of
// the Combiner functor. It only reestablished that state after splitting the
- // 'it' interval value pair. Using map_insert<Combiner> does not work here.
- iterator insertion_ = this->_map.insert(it, value_type(right_resid, it->CONT_VALUE));
+ // 'it_' interval value pair. Using map_insert<Combiner> does not work here.
+ iterator insertion_ = this->_map.insert(it_, value_type(right_resid, it_->CONT_VALUE));
join_right(insertion_);
- Combiner()(it->CONT_VALUE, co_val);
+ Combiner()(it_->CONT_VALUE, co_val);
- if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
- this->_map.erase(it);
+ if(Traits::absorbs_neutrons && it_->CONT_VALUE == Combiner::neutron())
+ {
+ this->_map.erase(it_);
+ it_ = insertion_;
+ }
else
- join_neighbours(it);
+ join_neighbours(it_);
}
}
}
@@ -484,17 +520,17 @@
if(Traits::absorbs_neutrons && co_val==Combiner::neutron())
return;
- iterator fst_it = this->_map.lower_bound(inter_val);
- if(fst_it==this->_map.end())
+ iterator first_ = this->_map.lower_bound(inter_val);
+ if(first_==this->_map.end())
return;
- iterator end_it = this->_map.upper_bound(inter_val);
- if(fst_it==end_it)
+ iterator end_ = this->_map.upper_bound(inter_val);
+ if(first_==end_ )
return;
- iterator lst_it = end_it; --lst_it;
- iterator it_ = fst_it;
+ iterator last_ = end_; --last_;
+ iterator it_ = first_;
subtract_front (inter_val, co_val, it_);
- subtract_main<Combiner>(inter_val, co_val, it_, lst_it);
+ subtract_main<Combiner>(inter_val, co_val, it_, last_);
subtract_rear<Combiner>(inter_val, co_val, it_);
}
@@ -518,9 +554,9 @@
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>
inline void interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::subtract_main(const interval_type& inter_val, const CodomainT& co_val, iterator& it_, iterator& lst_it)
+ ::subtract_main(const interval_type& inter_val, const CodomainT& co_val, iterator& it_, iterator& last_)
{
- while(it_ != lst_it)
+ while(it_ != last_)
{
Combiner()(it_->CONT_VALUE, co_val);
@@ -538,32 +574,32 @@
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>
inline void interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::subtract_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it)
+ ::subtract_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_)
{
- interval_type right_resid = left_subtract(it->KEY_VALUE, inter_val);
+ interval_type right_resid = left_subtract(it_->KEY_VALUE, inter_val);
if(right_resid.empty())
{
- CodomainT& cur_val = it->CONT_VALUE ;
+ CodomainT& cur_val = it_->CONT_VALUE ;
Combiner()(cur_val, co_val);
if(Traits::absorbs_neutrons && cur_val==Combiner::neutron())
- this->_map.erase(it);
+ this->_map.erase(it_);
else
- join_neighbours(it);
+ join_neighbours(it_);
}
else
{
- const_cast<interval_type&>(it->KEY_VALUE).right_subtract(right_resid);
- iterator next_ = this->_map.insert(it, value_type(right_resid, it->CONT_VALUE));
- Combiner()(it->CONT_VALUE, co_val);
- if(Traits::absorbs_neutrons && it->CONT_VALUE==Combiner::neutron())
+ const_cast<interval_type&>(it_->KEY_VALUE).right_subtract(right_resid);
+ iterator next_ = this->_map.insert(it_, value_type(right_resid, it_->CONT_VALUE));
+ Combiner()(it_->CONT_VALUE, co_val);
+ if(Traits::absorbs_neutrons && it_->CONT_VALUE==Combiner::neutron())
{
- this->_map.erase(it);
+ this->_map.erase(it_);
join_right(next_);
}
else
{
- join_left(it);
+ join_left(it_);
join_neighbours(next_);
}
}
@@ -593,11 +629,11 @@
else
{
// Detect the first and the end iterator of the collision sequence
- iterator fst_it = this->_map.lower_bound(inter_val),
- lst_it = insertion.ITERATOR;
- //assert((++lst_it) == this->_map.upper_bound(inter_val));
- iterator it_ = fst_it;
- insert_range(inter_val, co_val, it_, lst_it);
+ iterator first_ = this->_map.lower_bound(inter_val),
+ last_ = insertion.ITERATOR;
+ //assert((++last_) == this->_map.upper_bound(inter_val));
+ iterator it_ = first_;
+ insert_range(inter_val, co_val, it_, last_);
}
}
@@ -605,18 +641,18 @@
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>
void interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::insert_range(const interval_type& inter_val, const CodomainT& co_val, iterator& it, iterator& lst_it)
+ ::insert_range(const interval_type& inter_val, const CodomainT& co_val, iterator& it_, iterator& last_)
{
- iterator end_it = lst_it; ++end_it;
- iterator prior_ = it, inserted_;
+ iterator end_ = last_ ; ++end_;
+ iterator prior_ = it_, inserted_;
if(prior_ != this->_map.end())
--prior_;
interval_type rest_interval = inter_val, left_gap, cur_itv;
- interval_type last_interval = lst_it->KEY_VALUE;
+ interval_type last_interval = last_ ->KEY_VALUE;
- while(it != end_it)
+ while(it_ != end_ )
{
- cur_itv = it->KEY_VALUE ;
+ cur_itv = it_->KEY_VALUE ;
left_gap = right_subtract(rest_interval, cur_itv);
if(!left_gap.empty())
@@ -624,16 +660,16 @@
inserted_ = this->_map.insert(prior_, value_type(left_gap, co_val));
join_left(inserted_);
// after filling that gap there may be another joining opportunity
- join_left(it);
+ join_left(it_);
}
// shrink interval
rest_interval.left_subtract(cur_itv);
- prior_ = it;
- ++it;
+ prior_ = it_;
+ ++it_;
}
- //insert_rear(rest_interval, co_val, lst_it):
+ //insert_rear(rest_interval, co_val, last_):
interval_type end_gap = left_subtract(rest_interval, last_interval);
if(!end_gap.empty())
{
@@ -658,49 +694,49 @@
if(Traits::absorbs_neutrons && co_val==codomain_combine::neutron())
return;
- iterator fst_it = this->_map.lower_bound(inter_val);
- if(fst_it==this->_map.end())
+ iterator first_ = this->_map.lower_bound(inter_val);
+ if(first_==this->_map.end())
return;
- iterator end_it = this->_map.upper_bound(inter_val);
- if(fst_it==end_it)
+ iterator end_ = this->_map.upper_bound(inter_val);
+ if(first_==end_ )
return;
- iterator lst_it = end_it; --lst_it;
+ iterator last_ = end_; --last_;
- iterator snd_it = fst_it; snd_it++;
- if(fst_it == lst_it)
+ iterator second_= first_; second_++;
+ if(first_ == last_)
{
- // only for the last there can be a right_resid: a part of *it right of minuend
- interval_type right_resid = left_subtract(fst_it->KEY_VALUE, inter_val);
+ // only for the last there can be a right_resid: a part of *it_ right of minuend
+ interval_type right_resid = left_subtract(first_->KEY_VALUE, inter_val);
- if(fst_it->CONT_VALUE == co_val)
+ if(first_->CONT_VALUE == co_val)
{
- interval_type left_resid = right_subtract(fst_it->KEY_VALUE, inter_val);
+ interval_type left_resid = right_subtract(first_->KEY_VALUE, inter_val);
if(!left_resid.empty())
{
- const_cast<interval_type&>(fst_it->KEY_VALUE) = left_resid;
+ const_cast<interval_type&>(first_->KEY_VALUE) = left_resid;
if(!right_resid.empty())
- this->_map.insert(fst_it, value_type(right_resid, co_val));
+ this->_map.insert(first_, value_type(right_resid, co_val));
}
else if(!right_resid.empty())
- const_cast<interval_type&>(fst_it->KEY_VALUE) = right_resid;
+ const_cast<interval_type&>(first_->KEY_VALUE) = right_resid;
else
- this->_map.erase(fst_it);
+ this->_map.erase(first_);
}
}
else
{
// first AND NOT last
- if(fst_it->CONT_VALUE == co_val)
+ if(first_->CONT_VALUE == co_val)
{
- interval_type left_resid = right_subtract(fst_it->KEY_VALUE, inter_val);
+ interval_type left_resid = right_subtract(first_->KEY_VALUE, inter_val);
if(left_resid.empty())
- this->_map.erase(fst_it);
+ this->_map.erase(first_);
else
- const_cast<interval_type&>(fst_it->KEY_VALUE) = left_resid;
+ const_cast<interval_type&>(first_->KEY_VALUE) = left_resid;
}
- erase_rest(inter_val, co_val, snd_it, lst_it);
+ erase_rest(inter_val, co_val, second_, last_);
}
}
@@ -708,10 +744,10 @@
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 void interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
::erase_rest(const interval_type& inter_val, const CodomainT& co_val,
- iterator& it_, iterator& lst_it)
+ iterator& it_, iterator& last_)
{
// For all intervals within loop: it_->KEY_VALUE are contained_in inter_val
- while(it_ != lst_it)
+ while(it_ != last_)
if((*it_).CONT_VALUE == co_val)
this->_map.erase(it_++);
else it_++;
Modified: sandbox/itl/boost/itl/interval_maps.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_maps.hpp (original)
+++ sandbox/itl/boost/itl/interval_maps.hpp 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -287,8 +287,9 @@
{
typedef interval_base_map<SubType,DomainT,CodomainT,
Traits,Compare,Combine,Section,Interval,Alloc> operand_type;
+ typename ObjectT::iterator prior_ = object.end();
const_FORALL(typename operand_type, elem_, operand)
- object.add(*elem_);
+ prior_ = object.add(prior_, *elem_);
return object;
}
Modified: sandbox/itl/boost/itl/interval_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_set.hpp (original)
+++ sandbox/itl/boost/itl/interval_set.hpp 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -121,8 +121,8 @@
typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> base_set_type;
this->clear();
// Has to be implemented via add. there might be touching borders to be joined
- const_FORALL(typename base_set_type, it, src)
- this->add(*it);
+ const_FORALL(typename base_set_type, it_, src)
+ this->add(*it_);
}
private:
@@ -136,14 +136,16 @@
/// Insertion of an interval <tt>x</tt>
void add_(const value_type& x);
+ iterator add_(iterator prior_, const value_type& x);
+
/// Removal of an interval <tt>x</tt>
void subtract_(const value_type& x);
private:
/// Treatment of adjoint intervals on insertion
- void handle_neighbours(const iterator& it);
+ iterator handle_neighbours(iterator it_);
- iterator join_segments(const iterator& left_it, const iterator& right_it);
+ iterator join_segments(const iterator& left_, const iterator& right_);
} ;
@@ -162,52 +164,59 @@
else if(this->upper() < x.lower())
return false;
{
- typename ImplSetT::const_iterator it = this->_set.find(x);
- if(it == this->_set.end())
+ typename ImplSetT::const_iterator it_ = this->_set.find(x);
+ if(it_ == this->_set.end())
return false;
else
- return x.contained_in(*it);
+ return x.contained_in(*it_);
}
}
template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-void interval_set<DomainT,Compare,Interval,Alloc>::handle_neighbours(const iterator& it)
+inline typename interval_set<DomainT,Compare,Interval,Alloc>::iterator
+ interval_set<DomainT,Compare,Interval,Alloc>::handle_neighbours(iterator it_)
{
- if(it == this->_set.begin())
+ if(it_ == this->_set.begin())
{
- iterator it_nxt=it; it_nxt++;
- if(it_nxt!=this->_set.end() && (*it).touches(*it_nxt))
- join_segments(it, it_nxt);
+ iterator it_nxt=it_; it_nxt++;
+ if(it_nxt!=this->_set.end() && (*it_).touches(*it_nxt))
+ return join_segments(it_, it_nxt);
}
else
{
// there is a predecessor
- iterator it_pred = it; it_pred-- ;
+ iterator pred_ = it_; pred_-- ;
- if((*it_pred).touches(*it))
+ if((*pred_).touches(*it_))
{
- iterator it_extended = join_segments(it_pred, it);
+ iterator it_extended = join_segments(pred_, it_);
- iterator it_succ=it_extended; it_succ++;
- if(it_succ!=this->_set.end())
+ iterator succ_=it_extended; succ_++;
+ if(succ_!=this->_set.end())
{
// it's a non border element that might have two touching neighbours
- if((*it_extended).touches(*it_succ))
- join_segments(it_extended, it_succ);
+ if((*it_extended).touches(*succ_))
+ return join_segments(it_extended, succ_);
+ else
+ return it_extended;
}
+ else
+ return it_extended;
}
else
{
- iterator it_succ=it; it_succ++;
- if(it_succ!=this->_set.end())
+ iterator succ_=it_; succ_++;
+ if(succ_!=this->_set.end())
{
// it's a non border element that might have a right touching neighbours
- if((*it).touches(*it_succ))
- join_segments(it, it_succ);
+ if((*it_).touches(*succ_))
+ return join_segments(it_, succ_);
}
}
}
+
+ return it_;
}
@@ -215,17 +224,17 @@
template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
inline typename interval_set<DomainT,Compare,Interval,Alloc>::iterator
interval_set<DomainT,Compare,Interval,Alloc>
- ::join_segments(const iterator& left_it, const iterator& right_it)
+ ::join_segments(const iterator& left_, const iterator& right_)
{
// both left and right are in the set and they are neighbours
- BOOST_ASSERT((*left_it).exclusive_less(*right_it));
- BOOST_ASSERT((*left_it).touches(*right_it));
+ BOOST_ASSERT((*left_).exclusive_less(*right_));
+ BOOST_ASSERT((*left_).touches(*right_));
- interval_type right_itv = (*right_it);
- this->_set.erase(right_it);
- const_cast<value_type&>(*left_it).extend(right_itv);
+ interval_type right_itv = (*right_);
+ this->_set.erase(right_);
+ const_cast<value_type&>(*left_).extend(right_itv);
- return left_it;
+ return left_;
}
@@ -240,41 +249,72 @@
handle_neighbours(insertion.ITERATOR);
else
{
- iterator fst_it = this->_set.lower_bound(addend),
- lst_it = insertion.ITERATOR,
- end_it = insertion.ITERATOR; end_it++;
- //BOOST_ASSERT(end_it == this->_map.upper_bound(inter_val));
- iterator snd_it = fst_it; ++snd_it;
+ iterator first_ = this->_set.lower_bound(addend),
+ last_ = insertion.ITERATOR,
+ end_ = insertion.ITERATOR; end_ ++;
+ //BOOST_ASSERT(end_ == this->_map.upper_bound(inter_val));
+ iterator second_= first_; ++second_;
- interval_type leftResid = right_subtract(*fst_it, addend);
- interval_type rightResid = left_subtract(*lst_it, addend);
+ interval_type leftResid = right_subtract(*first_, addend);
+ interval_type rightResid = left_subtract(*last_ , addend);
- this->_set.erase(snd_it, end_it);
+ this->_set.erase(second_, end_ );
interval_type extended = addend;
extended.extend(leftResid).extend(rightResid);
- const_cast<value_type&>(*fst_it) = extended;
- handle_neighbours(fst_it);
+ const_cast<value_type&>(*first_) = extended;
+ handle_neighbours(first_);
}
}
+template<class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
+typename interval_set<DomainT,Compare,Interval,Alloc>::iterator
+ interval_set<DomainT,Compare,Interval,Alloc>::add_(iterator prior_, const value_type& addend)
+{
+ if(addend.empty())
+ return prior_;
+
+ iterator insertion = this->_set.insert(prior_, addend);
+
+ if(*insertion == addend)
+ return handle_neighbours(insertion);
+ else
+ {
+ iterator first_ = this->_set.lower_bound(addend),
+ last_ = insertion,
+ end_ = insertion; end_ ++;
+ //BOOST_ASSERT(end_ == this->_map.upper_bound(inter_val));
+ iterator second_= first_; ++second_;
+
+ interval_type leftResid = right_subtract(*first_, addend);
+ interval_type rightResid = left_subtract(*last_ , addend);
+
+ this->_set.erase(second_, end_ );
+
+ interval_type extended = addend;
+ extended.extend(leftResid).extend(rightResid);
+
+ const_cast<value_type&>(*first_) = extended;
+ return handle_neighbours(first_);
+ }
+}
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& minuend)
{
if(minuend.empty()) return;
- iterator fst_it = this->_set.lower_bound(minuend);
- if(fst_it==this->_set.end()) return;
- iterator end_it = this->_set.upper_bound(minuend);
- iterator lst_it = end_it; --lst_it;
+ iterator first_ = this->_set.lower_bound(minuend);
+ if(first_==this->_set.end()) return;
+ iterator end_ = this->_set.upper_bound(minuend);
+ iterator last_ = end_; --last_;
- interval_type leftResid = right_subtract(*fst_it, minuend);
+ interval_type leftResid = right_subtract(*first_, minuend);
interval_type rightResid;
- if(fst_it != end_it)
- rightResid = left_subtract(*lst_it, minuend);
+ if(first_ != end_ )
+ rightResid = left_subtract(*last_ , minuend);
- this->_set.erase(fst_it, end_it);
+ this->_set.erase(first_, end_ );
if(!leftResid.empty())
this->_set.insert(leftResid);
Modified: sandbox/itl/boost/itl/interval_sets.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_sets.hpp (original)
+++ sandbox/itl/boost/itl/interval_sets.hpp 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -81,8 +81,9 @@
)
{
typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> operand_type;
+ typename ObjectT::iterator prior_ = object.end();
const_FORALL(typename operand_type, elem_, operand)
- object.add(*elem_);
+ prior_ = object.add(prior_, *elem_);
return object;
}
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-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -118,8 +118,8 @@
typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> base_set_type;
this->clear();
// Can be implemented via _set.insert: Interval joining not necessary.
- const_FORALL(typename base_set_type, it, src)
- this->_set.insert(*it);
+ const_FORALL(typename base_set_type, it_, src)
+ this->_set.insert(*it_);
}
private:
@@ -132,13 +132,14 @@
/// Insertion of an interval <tt>x</tt>
void add_(const value_type& x);
+ iterator add_(iterator prior_, const value_type& x);
/// Removal of an interval <tt>x</tt>
void subtract_(const value_type& x);
private:
/// Treatment of adjoint intervals on insertion
- void handle_neighbours(const iterator& it){}
+ void handle_neighbours(const iterator& it_){}
} ;
@@ -165,21 +166,53 @@
handle_neighbours(insertion.ITERATOR);
else
{
- iterator fst_it = this->_set.lower_bound(addend),
- lst_it = insertion.ITERATOR,
- end_it = insertion.ITERATOR; end_it++;
- //BOOST_ASSERT(end_it == this->_map.upper_bound(inter_val));
- iterator snd_it = fst_it; ++snd_it;
+ iterator first_ = this->_set.lower_bound(addend),
+ last_ = insertion.ITERATOR,
+ end_ = insertion.ITERATOR; end_ ++;
+ //BOOST_ASSERT(end_ == this->_map.upper_bound(inter_val));
+ iterator second_= first_; ++second_;
- interval_type leftResid = right_subtract(*fst_it, addend);
- interval_type rightResid = left_subtract(*lst_it, addend);
+ interval_type leftResid = right_subtract(*first_, addend);
+ interval_type rightResid = left_subtract(*last_ , addend);
- this->_set.erase(snd_it, end_it);
+ this->_set.erase(second_, end_ );
interval_type extended = addend;
extended.extend(leftResid).extend(rightResid);
- const_cast<value_type&>(*fst_it) = extended;
+ const_cast<value_type&>(*first_) = extended;
+ }
+}
+
+template<class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
+typename separate_interval_set<DomainT,Compare,Interval,Alloc>::iterator
+ separate_interval_set<DomainT,Compare,Interval,Alloc>::add_(iterator prior_, const value_type& addend)
+{
+ if(addend.empty())
+ return prior_;
+
+ iterator insertion = this->_set.insert(prior_, addend);
+
+ if(*insertion == addend)
+ return insertion;
+ else
+ {
+ iterator first_ = this->_set.lower_bound(addend),
+ last_ = insertion,
+ end_ = insertion; end_ ++;
+ //BOOST_ASSERT(end_ == this->_map.upper_bound(inter_val));
+ iterator second_= first_; ++second_;
+
+ interval_type leftResid = right_subtract(*first_, addend);
+ interval_type rightResid = left_subtract(*last_ , addend);
+
+ this->_set.erase(second_, end_ );
+
+ interval_type extended = addend;
+ extended.extend(leftResid).extend(rightResid);
+
+ const_cast<value_type&>(*first_) = extended;
+ return first_;
}
}
@@ -188,18 +221,18 @@
inline void separate_interval_set<DomainT,Compare,Interval,Alloc>::subtract_(const value_type& minuend)
{
if(minuend.empty()) return;
- iterator fst_it = this->_set.lower_bound(minuend);
- if(fst_it==this->_set.end()) return;
- iterator end_it = this->_set.upper_bound(minuend);
- iterator snd_it = fst_it; ++snd_it;
- iterator lst_it = end_it; --lst_it;
+ iterator first_ = this->_set.lower_bound(minuend);
+ if(first_==this->_set.end()) return;
+ iterator end_ = this->_set.upper_bound(minuend);
+ iterator second_= first_; ++second_;
+ iterator last_ = end_; --last_;
- interval_type leftResid = right_subtract(*fst_it, minuend);
+ interval_type leftResid = right_subtract(*first_, minuend);
interval_type rightResid;
- if(fst_it != end_it)
- rightResid = left_subtract(*lst_it, minuend);
+ if(first_ != end_ )
+ rightResid = left_subtract(*last_ , minuend);
- this->_set.erase(fst_it, end_it);
+ this->_set.erase(first_, end_ );
if(!leftResid.empty())
this->_set.insert(leftResid);
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-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -92,8 +92,8 @@
Traits,Compare,Combine,Section,Interval,Alloc> base_map_type;
this->clear();
// Can be implemented via _map.insert: Interval joining not necessary.
- const_FORALL(typename base_map_type, it, src)
- this->_map.insert(*it);
+ const_FORALL(typename base_map_type, it_, src)
+ this->_map.insert(*it_);
}
//==========================================================================
@@ -124,37 +124,40 @@
void add_(const value_type&);
template<class Combiner>
+ iterator add_(iterator, const value_type&);
+
+ template<class Combiner>
void subtract_(const value_type&);
void insert_(const value_type& value);
void erase_(const value_type& value);
private:
- void handle_neighbours(const iterator& it){}
+ void handle_neighbours(const iterator& it_){}
template<class Combiner>
void add_main(interval_type& inter_val, const CodomainT& co_val,
- iterator& it, const iterator& end_it);
+ iterator& it_, const iterator& end_ );
template<class Combiner>
void add_segment(const interval_type& inter_val, const CodomainT& co_val,
- iterator& it);
+ iterator& it_);
- void add_front(const interval_type& inter_val, const CodomainT& co_val, iterator& it);
+ void add_front(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
template<class Combiner>
- void add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it);
+ void add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
template<class Combiner>
void subtract_main(const interval_type& inter_val, const CodomainT& co_val,
- iterator& it, iterator& end_it);
+ iterator& it_, iterator& end_ );
- void subtract_front(const interval_type& inter_val, const CodomainT& co_val, iterator& it);
+ void subtract_front(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
template<class Combiner>
- void subtract_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it);
+ void subtract_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
- void insert_range(const interval_type& inter_val, const CodomainT& co_val, iterator& it, iterator& end_it);
- void erase_rest(const interval_type& inter_val, const CodomainT& co_val, iterator& it, iterator& lst_it);
+ void insert_range(const interval_type& inter_val, const CodomainT& co_val, iterator& it_, iterator& end_ );
+ void erase_rest(const interval_type& inter_val, const CodomainT& co_val, iterator& it_, iterator& last_);
} ;
@@ -179,7 +182,7 @@
inline void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
::add_(const value_type& addend)
{
- const interval_type& inter_val = addend.KEY_VALUE;
+ interval_type inter_val = addend.KEY_VALUE;
if(inter_val.empty())
return;
@@ -193,16 +196,53 @@
if(!insertion.WAS_SUCCESSFUL)
{
// Detect the first and the end iterator of the collision sequence
- iterator fst_it = this->_map.lower_bound(inter_val),
- lst_it = insertion.ITERATOR;
- //assert(end_it == this->_map.upper_bound(inter_val));
+ iterator first_ = this->_map.lower_bound(inter_val),
+ last_ = insertion.ITERATOR;
+ //assert(end_ == this->_map.upper_bound(inter_val));
+
+ iterator it_ = first_;
+ interval_type rest_interval = inter_val;
+
+ add_front (rest_interval, co_val, it_);
+ add_main<Combiner>(rest_interval, co_val, it_, last_);
+ add_rear<Combiner>(rest_interval, co_val, 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>
+ template<class Combiner>
+inline typename split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
+ split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::add_(iterator prior_, const value_type& addend)
+{
+ interval_type inter_val = addend.KEY_VALUE;
+ if(inter_val.empty())
+ return prior_;
+
+ const CodomainT& co_val = addend.CONT_VALUE;
+ if(Traits::absorbs_neutrons && co_val==Combiner::neutron())
+ return prior_;
+
+ std::pair<iterator,bool> insertion
+ = this->template map_insert<Combiner>(prior_, inter_val, co_val);
+
+ if(insertion.WAS_SUCCESSFUL)
+ return insertion.ITERATOR;
+ else
+ {
+ // Detect the first and the end iterator of the collision sequence
+ iterator first_ = this->_map.lower_bound(inter_val),
+ last_ = insertion.ITERATOR;
+ //assert(end_ == this->_map.upper_bound(inter_val));
- iterator it_ = fst_it;
+ iterator it_ = first_;
interval_type rest_interval = inter_val;
add_front (rest_interval, co_val, it_);
- add_main<Combiner>(rest_interval, co_val, it_, lst_it);
+ add_main<Combiner>(rest_interval, co_val, it_, last_);
add_rear<Combiner>(rest_interval, co_val, it_);
+
+ return it_;
}
}
@@ -211,16 +251,16 @@
inline void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
::add_front(const interval_type& inter_val, const CodomainT& co_val, iterator& first_)
{
- // If the collision sequence has a right residual 'right_resid' is will
+ // If the collision sequence has a left residual 'left_resid' it will
// be split, to provide a standardized start of algorithms:
- // The addend interval 'inver_val' covers the beginning of the collision sequence.
+ // The addend interval 'inter_val' covers the beginning of the collision sequence.
// only for the first there can be a left_resid: a part of *first_ left of inter_val
interval_type left_resid = right_subtract(first_->KEY_VALUE, inter_val);
if(!left_resid.empty())
{ // [------------ . . .
- // [left_resid---fst_it --- . . .
+ // [left_resid---first_ --- . . .
iterator prior_ = this->prior(first_);
const_cast<interval_type&>(first_->KEY_VALUE).left_subtract(left_resid);
//NOTE: Only splitting
@@ -236,13 +276,13 @@
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>
inline void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::add_main(interval_type& x_rest, const CodomainT& co_val, iterator& it, const iterator& lst_it)
+ ::add_main(interval_type& x_rest, const CodomainT& co_val, iterator& it_, const iterator& last_)
{
interval_type cur_interval;
- while(it!=lst_it)
+ while(it_!=last_)
{
- cur_interval = it->KEY_VALUE ;
- add_segment<Combiner>(x_rest, co_val, it);
+ cur_interval = it_->KEY_VALUE ;
+ add_segment<Combiner>(x_rest, co_val, it_);
// shrink interval
x_rest.left_subtract(cur_interval);
}
@@ -256,15 +296,9 @@
{
interval_type lead_gap = right_subtract(inter_val, it_->KEY_VALUE);
if(!lead_gap.empty())
- {
- // [------ . . .
- // [-- it ...
- 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);
- }
+ // [lead_gap--- . . .
+ // [prior_) [-- it_ ...
+ this->template gap_insert<Combiner>(prior(it_), lead_gap, co_val);
// . . . --------- . . . addend interval
// [-- it_ --) has a common part with the first overval
@@ -280,62 +314,67 @@
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>
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)
+ ::add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_)
{
- iterator prior_ = this->prior(it);
- interval_type cur_itv = (*it).KEY_VALUE ;
+ 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())
- // [------ . . .
- // [prior) [-- it ...
- this->template map_insert<Combiner>(prior_, lead_gap, co_val);
+ // [lead_gap--- . . .
+ // [prior_) [-- it_ ...
+ this->template gap_insert<Combiner>(prior_, lead_gap, co_val);
interval_type end_gap = left_subtract(inter_val, cur_itv);
if(!end_gap.empty())
{
- // [------------------)
- // [-- it --)
- Combiner()(it->CONT_VALUE, co_val);
+ // [---------------end_gap)
+ // [-- it_ --)
+ Combiner()(it_->CONT_VALUE, co_val);
- if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
+ if(Traits::absorbs_neutrons && it_->CONT_VALUE == Combiner::neutron())
{
- this->_map.erase(it);
- iterator inserted_ = this->template map_insert<Combiner>(prior_, end_gap, co_val);
+ this->_map.erase(it_);
+ it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val);
}
else
- this->template map_insert<Combiner>(it, end_gap, co_val);
+ it_ = this->template gap_insert<Combiner>(it_, end_gap, co_val);
}
else
{
- // only for the last there can be a right_resid: a part of *it right of addend
+ // only for the last there can be a right_resid: a part of *it_ right of addend
interval_type right_resid = left_subtract(cur_itv, inter_val);
if(right_resid.empty())
{
// [---------------)
- // [-- it ----)
- Combiner()(it->CONT_VALUE, co_val);
+ // [-- it_ ---)
+ Combiner()(it_->CONT_VALUE, co_val);
- if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
- this->_map.erase(it);
+ if(Traits::absorbs_neutrons && it_->CONT_VALUE == Combiner::neutron())
+ {
+ this->_map.erase(it_);
+ it_ = prior_;
+ }
}
else
{
- // [-------------)
- // [-- it ---right_resid)
- const_cast<interval_type&>(it->KEY_VALUE).right_subtract(right_resid);
+ // [--------------)
+ // [-- it_ --right_resid)
+ const_cast<interval_type&>(it_->KEY_VALUE).right_subtract(right_resid);
//NOTE: This is NOT an insertion that has to take care for correct application of
// the Combiner functor. It only reestablished that state after splitting the
- // 'it' interval value pair. Using map_insert<Combiner> does not work here.
- iterator insertion_ = this->_map.insert(it, value_type(right_resid, it->CONT_VALUE));
+ // 'it_' interval value pair. Using map_insert<Combiner> does not work here.
+ iterator insertion_ = this->_map.insert(it_, value_type(right_resid, it_->CONT_VALUE));
- Combiner()(it->CONT_VALUE, co_val);
+ Combiner()(it_->CONT_VALUE, co_val);
- if(Traits::absorbs_neutrons && it->CONT_VALUE == Combiner::neutron())
- this->_map.erase(it);
+ if(Traits::absorbs_neutrons && it_->CONT_VALUE == Combiner::neutron())
+ this->_map.erase(it_);
+
+ it_ = insertion_;
}
}
}
@@ -360,17 +399,17 @@
if(Traits::absorbs_neutrons && co_val==Combiner::neutron())
return;
- iterator fst_it = this->_map.lower_bound(inter_val);
- if(fst_it==this->_map.end())
+ iterator first_ = this->_map.lower_bound(inter_val);
+ if(first_==this->_map.end())
return;
- iterator end_it = this->_map.upper_bound(inter_val);
- if(fst_it==end_it)
+ iterator end_ = this->_map.upper_bound(inter_val);
+ if(first_==end_ )
return;
- iterator lst_it = end_it; --lst_it;
- iterator it_ = fst_it;
+ iterator last_ = end_; --last_;
+ iterator it_ = first_;
subtract_front (inter_val, co_val, it_);
- subtract_main<Combiner>(inter_val, co_val, it_, lst_it);
+ subtract_main<Combiner>(inter_val, co_val, it_, last_);
subtract_rear<Combiner>(inter_val, co_val, it_);
}
@@ -396,9 +435,9 @@
template<class Combiner>
inline void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
::subtract_main(const interval_type& inter_val, const CodomainT& co_val,
- iterator& it_, iterator& lst_it)
+ iterator& it_, iterator& last_)
{
- while(it_ != lst_it)
+ while(it_ != last_)
{
Combiner()(it_->CONT_VALUE, co_val);
if(Traits::absorbs_neutrons && it_->CONT_VALUE==Combiner::neutron())
@@ -455,11 +494,11 @@
if(!insertion.WAS_SUCCESSFUL)
{
// Detect the first and the end iterator of the collision sequence
- iterator fst_it = this->_map.lower_bound(inter_val),
- lst_it = insertion.ITERATOR;
- //assert((++lst_it) == this->_map.upper_bound(inter_val));
- iterator it_ = fst_it;
- insert_range(inter_val, co_val, it_, lst_it);
+ iterator first_ = this->_map.lower_bound(inter_val),
+ last_ = insertion.ITERATOR;
+ //assert((++last_) == this->_map.upper_bound(inter_val));
+ iterator it_ = first_;
+ insert_range(inter_val, co_val, it_, last_);
}
}
@@ -467,18 +506,18 @@
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 void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::insert_range(const interval_type& inter_val, const CodomainT& co_val, iterator& it, iterator& lst_it)
+ ::insert_range(const interval_type& inter_val, const CodomainT& co_val, iterator& it_, iterator& last_)
{
- iterator end_it = lst_it; ++end_it;
- iterator prior_ = it, inserted_;
+ iterator end_ = last_ ; ++end_;
+ iterator prior_ = it_, inserted_;
if(prior_ != this->_map.end())
--prior_;
interval_type rest_interval = inter_val, left_gap, cur_itv;
- interval_type last_interval = lst_it->KEY_VALUE;
+ interval_type last_interval = last_ ->KEY_VALUE;
- while(it != end_it)
+ while(it_ != end_ )
{
- cur_itv = it->KEY_VALUE ;
+ cur_itv = it_->KEY_VALUE ;
left_gap = right_subtract(rest_interval, cur_itv);
if(!left_gap.empty())
@@ -486,11 +525,11 @@
// shrink interval
rest_interval.left_subtract(cur_itv);
- prior_ = it;
- ++it;
+ prior_ = it_;
+ ++it_;
}
- //insert_rear(rest_interval, co_val, lst_it):
+ //insert_rear(rest_interval, co_val, last_):
interval_type end_gap = left_subtract(rest_interval, last_interval);
if(!end_gap.empty())
inserted_ = this->_map.insert(prior_, value_type(end_gap, co_val));
@@ -512,49 +551,49 @@
if(Traits::absorbs_neutrons && co_val==codomain_combine::neutron())
return;
- iterator fst_it = this->_map.lower_bound(inter_val);
- if(fst_it==this->_map.end())
+ iterator first_ = this->_map.lower_bound(inter_val);
+ if(first_==this->_map.end())
return;
- iterator end_it = this->_map.upper_bound(inter_val);
- if(fst_it==end_it)
+ iterator end_ = this->_map.upper_bound(inter_val);
+ if(first_==end_ )
return;
- iterator lst_it = end_it; --lst_it;
+ iterator last_ = end_; --last_;
- iterator snd_it = fst_it; ++snd_it;
- if(fst_it == lst_it)
+ iterator second_= first_; ++second_;
+ if(first_ == last_)
{
- // only for the last there can be a right_resid: a part of *it right of minuend
- interval_type right_resid = left_subtract(fst_it->KEY_VALUE, inter_val);
+ // only for the last there can be a right_resid: a part of *it_ right of minuend
+ interval_type right_resid = left_subtract(first_->KEY_VALUE, inter_val);
- if(fst_it->CONT_VALUE == co_val)
+ if(first_->CONT_VALUE == co_val)
{
- interval_type left_resid = right_subtract(fst_it->KEY_VALUE, inter_val);
+ interval_type left_resid = right_subtract(first_->KEY_VALUE, inter_val);
if(!left_resid.empty())
{
- const_cast<interval_type&>(fst_it->KEY_VALUE) = left_resid;
+ const_cast<interval_type&>(first_->KEY_VALUE) = left_resid;
if(!right_resid.empty())
- this->_map.insert(fst_it, value_type(right_resid, co_val));
+ this->_map.insert(first_, value_type(right_resid, co_val));
}
else if(!right_resid.empty())
- const_cast<interval_type&>(fst_it->KEY_VALUE) = right_resid;
+ const_cast<interval_type&>(first_->KEY_VALUE) = right_resid;
else
- this->_map.erase(fst_it);
+ this->_map.erase(first_);
}
}
else
{
// first AND NOT last
- if(fst_it->CONT_VALUE == co_val)
+ if(first_->CONT_VALUE == co_val)
{
- interval_type left_resid = right_subtract(fst_it->KEY_VALUE, inter_val);
+ interval_type left_resid = right_subtract(first_->KEY_VALUE, inter_val);
if(left_resid.empty())
- this->_map.erase(fst_it);
+ this->_map.erase(first_);
else
- const_cast<interval_type&>(fst_it->KEY_VALUE) = left_resid;
+ const_cast<interval_type&>(first_->KEY_VALUE) = left_resid;
}
- erase_rest(inter_val, co_val, snd_it, lst_it);
+ erase_rest(inter_val, co_val, second_, last_);
}
}
@@ -562,10 +601,10 @@
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 void split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
::erase_rest(const interval_type& inter_val, const CodomainT& co_val,
- iterator& it_, iterator& lst_it)
+ iterator& it_, iterator& last_)
{
// For all intervals within loop: it_->KEY_VALUE are contained_in inter_val
- while(it_ != lst_it)
+ while(it_ != last_)
if((*it_).CONT_VALUE == co_val)
this->_map.erase(it_++);
else it_++;
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-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -115,8 +115,8 @@
typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> base_set_type;
this->clear();
// Can be implemented via _set.insert: Interval joining not necessary.
- const_FORALL(typename base_set_type, it, src)
- this->_set.insert(*it);
+ const_FORALL(typename base_set_type, it_, src)
+ this->_set.insert(*it_);
}
private:
@@ -129,16 +129,21 @@
/// Insertion of an interval <tt>x</tt>
void add_(const value_type& x);
+ iterator add_(iterator prior_, const value_type& x);
/// Removal of an interval <tt>x</tt>
void subtract_(const value_type& x);
private:
/// Treatment of adjoint intervals on insertion
- void handle_neighbours(const iterator& it){}
+ void handle_neighbours(const iterator& it_){}
- void insert_rest(interval_type& x_itv, iterator& it, iterator& end_it);
- void subtract_rest(const interval_type& x_itv, iterator& it, iterator& end_it);
+ void add_front(const interval_type& inter_val, iterator& first_);
+ void add_main(interval_type& inter_val, iterator& it_, const iterator& last_);
+ void add_segment(const interval_type& inter_val, iterator& it_);
+ void add_rear(const interval_type& inter_val, iterator& it_);
+
+ void subtract_rest(const interval_type& x_itv, iterator& it_, iterator& end_ );
} ;
template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
@@ -162,69 +167,136 @@
if(!insertion.WAS_SUCCESSFUL)
{
- iterator fst_it = this->_set.lower_bound(addend),
- lst_it = insertion.ITERATOR,
- end_it = insertion.ITERATOR; end_it++;
- //BOOST_ASSERT(end_it == this->_map.upper_bound(inter_val));
-
- 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())
- {
- const_cast<value_type&>(*fst_it).left_subtract(leftResid);
- this->_set.insert(pre_it, leftResid);
- }
- }
+ iterator first_ = this->_set.lower_bound(addend),
+ last_ = insertion.ITERATOR;
+ //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
+
+ iterator it_ = first_;
+ interval_type rest_interval = addend;
+
+ add_front(rest_interval, it_);
+ add_main (rest_interval, it_, last_);
+ add_rear (rest_interval, it_);
+ }
+}
- // 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
- {
- interval_type rightResid = left_subtract(*lst_it, addend);
- if(!rightResid.empty())
- {
- const_cast<value_type&>(*lst_it).right_subtract(rightResid);
- this->_set.insert(lst_it, rightResid);
- }
- }
-
- iterator snd_it = fst_it; snd_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>
+inline typename split_interval_set<DomainT,Compare,Interval,Alloc>::iterator
+ split_interval_set<DomainT,Compare,Interval,Alloc>::add_(iterator prior_, const value_type& addend)
+{
+ if(addend.empty())
+ return prior_;
+
+ iterator insertion = this->_set.insert(prior_, addend);
+
+ if(*insertion == addend) //successful insertion
+ return insertion;
+ else
+ {
+ iterator first_ = this->_set.lower_bound(addend),
+ last_ = insertion;
+ //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
+
+ iterator it_ = first_;
+ interval_type rest_interval = addend;
+
+ add_front(rest_interval, it_);
+ add_main (rest_interval, it_, last_);
+ add_rear (rest_interval, it_);
+
+ return it_;
}
}
template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-inline void split_interval_set<DomainT,Compare,Interval,Alloc>::insert_rest(interval_type& addend, iterator& it, iterator& end_it)
-{//JODO add_rest
- interval_type left_gap, cur_itv;
- iterator pred_it = it; --pred_it;
- while(it != end_it)
+inline void split_interval_set<DomainT,Compare,Interval,Alloc>
+ ::add_front(const interval_type& inter_val, iterator& first_)
+{
+ // If the collision sequence has a left residual 'left_resid' it will
+ // be split, to provide a standardized start of algorithms:
+ // The addend interval 'inter_val' covers the beginning of the collision sequence.
+
+ // only for the first there can be a left_resid: a part of *first_ left of inter_val
+ interval_type left_resid = right_subtract(*first_, inter_val);
+
+ if(!left_resid.empty())
+ { // [------------ . . .
+ // [left_resid---first_ --- . . .
+ iterator prior_ = this->prior(first_);
+ const_cast<interval_type&>(*first_).left_subtract(left_resid);
+ //NOTE: Only splitting
+ iterator insertion_ = this->_set.insert(prior_, left_resid);
+ }
+
+ //POST:
+ // [----- inter_val ---- . . .
+ // ...[-- first_ --...
+}
+
+
+template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
+inline void split_interval_set<DomainT,Compare,Interval,Alloc>
+ ::add_main(interval_type& x_rest, iterator& it_, const iterator& last_)
+{
+ interval_type cur_interval;
+ while(it_!=last_)
{
- cur_itv = *it;
- 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;
+ cur_interval = *it_ ;
+ add_segment(x_rest, it_);
+ // shrink interval
+ x_rest.left_subtract(cur_interval);
+ }
+}
+
+
+template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
+inline void split_interval_set<DomainT,Compare,Interval,Alloc>
+ ::add_segment(const interval_type& inter_val, iterator& it_)
+{
+ interval_type lead_gap = right_subtract(inter_val, *it_);
+ if(!lead_gap.empty())
+ // [lead_gap--- . . .
+ // [prior_) [-- it_ ...
+ this->_set.insert(prior(it_), lead_gap);
+
+ // . . . --------- . . . addend interval
+ // [-- it_ --) has a common part with the first overval
+ ++it_;
+}
+
+
+template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
+inline void split_interval_set<DomainT,Compare,Interval,Alloc>
+ ::add_rear(const interval_type& inter_val, iterator& it_)
+{
+ iterator prior_ = this->prior(it_);
+ interval_type cur_itv = *it_;
+
+ interval_type lead_gap = right_subtract(inter_val, cur_itv);
+ if(!lead_gap.empty())
+ // [lead_gap--- . . .
+ // [prior_) [-- it_ ...
+ this->_set.insert(prior_, lead_gap);
+
+ interval_type end_gap = left_subtract(inter_val, cur_itv);
+ if(!end_gap.empty())
+ // [---------------end_gap)
+ // [-- it_ --)
+ it_ = this->_set.insert(it_, end_gap);
+ else
+ {
+ // only for the last there can be a right_resid: a part of *it_ right of addend
+ interval_type right_resid = left_subtract(cur_itv, inter_val);
+
+ if(!right_resid.empty())
+ {
+ // [--------------)
+ // [-- it_ --right_resid)
+ const_cast<interval_type&>(*it_).right_subtract(right_resid);
+ it_ = this->_set.insert(it_, right_resid);
+ }
}
}
@@ -233,18 +305,18 @@
inline void split_interval_set<DomainT,Compare,Interval,Alloc>::subtract_(const value_type& minuend)
{
if(minuend.empty()) return;
- iterator fst_it = this->_set.lower_bound(minuend);
- if(fst_it==this->_set.end()) return;
- iterator end_it = this->_set.upper_bound(minuend);
- iterator snd_it = fst_it; ++snd_it;
- iterator lst_it = end_it; --lst_it;
+ iterator first_ = this->_set.lower_bound(minuend);
+ if(first_==this->_set.end()) return;
+ iterator end_ = this->_set.upper_bound(minuend);
+ iterator second_= first_; ++second_;
+ iterator last_ = end_; --last_;
- interval_type leftResid = right_subtract(*fst_it, minuend);
+ interval_type leftResid = right_subtract(*first_, minuend);
interval_type rightResid;
- if(fst_it != end_it)
- rightResid = left_subtract(*lst_it, minuend);
+ if(first_ != end_ )
+ rightResid = left_subtract(*last_ , minuend);
- this->_set.erase(fst_it, end_it);
+ this->_set.erase(first_, end_ );
if(!leftResid.empty())
this->_set.insert(leftResid);
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-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -33,9 +33,9 @@
_rootChoice[RootType::interval_set] = 0;
_rootChoice[RootType::separate_interval_set] = 0;
_rootChoice[RootType::split_interval_set] = 0;
- _rootChoice[RootType::itl_map] = 33;
- _rootChoice[RootType::interval_map] = 33;
- _rootChoice[RootType::split_interval_map] = 34;
+ _rootChoice[RootType::itl_map] = 0;//33;
+ _rootChoice[RootType::interval_map] = 50;//33;
+ _rootChoice[RootType::split_interval_map] = 50;//34;
setRootTypeNames();
_rootChoice.init();
@@ -101,15 +101,15 @@
switch(rootChoice)
{
//-----------------------------------------------------------------
- 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> >;
- case NeutronHandlerType::total_absorber: return new signed_quantifier_validater<itl::map<int,int,total_absorber > >;
- case NeutronHandlerType::total_enricher: return new signed_quantifier_validater<itl::map<int,int,total_enricher > >;
- default: return choiceError(ITL_LOCATION("\nRootType::itl_map: neutronizerChoice:\n"), neutronizerChoice, _neutronizerChoice);
- }//switch neutronizerChoice
- }//case itl_map
+ //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> >;
+ // case NeutronHandlerType::total_absorber: return new signed_quantifier_validater<itl::map<int,int,total_absorber > >;
+ // case NeutronHandlerType::total_enricher: return new signed_quantifier_validater<itl::map<int,int,total_enricher > >;
+ // default: return choiceError(ITL_LOCATION("\nRootType::itl_map: neutronizerChoice:\n"), neutronizerChoice, _neutronizerChoice);
+ // }//switch neutronizerChoice
+ //}//case itl_map
//-----------------------------------------------------------------
case RootType::interval_map: {
switch(neutronizerChoice) {
Modified: sandbox/itl/libs/itl/doc/examples.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/examples.qbk (original)
+++ sandbox/itl/libs/itl/doc/examples.qbk 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -1,5 +1,5 @@
[/
- Copyright (c) 2008-2008 Joachim Faulhaber
+ Copyright (c) 2008-2009 Joachim Faulhaber
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
Added: sandbox/itl/libs/itl/doc/implementation.qbk
==============================================================================
--- (empty file)
+++ sandbox/itl/libs/itl/doc/implementation.qbk 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -0,0 +1,87 @@
+[/
+ Copyright (c) 2008-2009 Joachim Faulhaber
+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+]
+
+[section Implementation]
+
+The implementation of the *itl's* conainers is based on
+std::set and std::map. So the underlying datastructure of
+interval containers is a red black tree of intervals or
+interval value pairs.
+
+The element containers itl::set and itl::map are wrapper
+classes of std::set and std::map using private inherience.
+Interval containers are then using itl::sets of intervals
+or itl::maps of interval value pairs as implementing
+containers.
+
+So all the complexity characteristics of itl conainers
+are based on and limited by the red-black tree implementation
+of the underlying std::AssociativeContainers.
+
+[section Complexity]
+
+This section gives an overview over the time complextity of
+the basic operations on interval containers. Since element
+containers __itl_set__ and __itl_map__ are only extensions of
+stl::set and stl::map, their complexity characteristics are
+accordingly. So their major operations insertion (addition),
+deletion and search are all using logarithmic time.
+
+The operations of interval containers behave differently
+due to the fact that intervals unlike elements can overlap
+any number of other inervals in a container. So as long as
+intervals are relatively small or just singleton, interval
+containers behave like an container of elements.
+
+This situation can be found in the first row of the next table,
+that gives the time complexities of the poymorphic
+`operator +=` for ['*addition]. Adding an element or
+element value pair is always done in /logarithmic time/,
+where /n/ is the number of intervals in the interval container.
+The same row of complexities applies to the insertion
+of a /segment/ (an interval or an interval value pair)
+in the ['*best case*], where the inserted segment does overlap
+with only a ['*small*] number of intervals in the container.
+
+[table Time Complexity of Addition
+[[] [`P`] [][interval\nset][separate\ninterval\nset][split\ninterval\nset][interval\nmap][split\ninterval\nmap]]
+[/ 1operation 2granul. 3case 4itvset 5se_itvset 6sp_itvset 7itv_map 8sp_itvmap]
+[[`T& operator +=( T&, const P&)`][element] [] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ]
+[[] [segment] [best case] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ]
+[[] [] [worst case] [__On__] [__On__] [__On__] [__On__] [__On__] ]
+[[] [] [amortized] [__Olgn__] [__Olgn__] [] [] [] ]
+[[] [container] [] [__Onlgn__] [__Onlgn__] [__Onlgn__] [__Onlgn__] [__Onlgn__] ]
+]
+
+In the ['*worst case*], where the inserted segment overlaps with
+all intervals in the container, the algorithms usually
+iterate over all the overlapped segments.
+Using inplace manipulations of segments and
+hinted inserts, it is possible to perform
+all necessary operations on each iteration step
+in /constant time/.
+This results in ['*linear worst case time*] complexity for
+segment addition for all interval containers.
+
+After performing
+a worst case addition
+for an __itv_set__ or a __sep_itv_sets__
+adding an interval that overlaps /n/
+intervals, we
+need /n/ non overlapping additions of
+/logarithmic time/ before we can launch
+another __On__ worst case addition.
+So we have only a ['*logarithmic amortized
+time*] for the addition of an interval.
+
+
+
+[endsect]
+
+[endsect]
+
Modified: sandbox/itl/libs/itl/doc/interface.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/interface.qbk (original)
+++ sandbox/itl/libs/itl/doc/interface.qbk 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -1,5 +1,5 @@
[/
- Copyright (c) 2008-2008 Joachim Faulhaber
+ Copyright (c) 2008-2009 Joachim Faulhaber
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
Modified: sandbox/itl/libs/itl/doc/itl.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/itl.qbk (original)
+++ sandbox/itl/libs/itl/doc/itl.qbk 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -43,6 +43,7 @@
[def __spl_itv_sets__ [classref boost::itl::split_interval_set split_interval_sets]]
[def __Spl_itv_set__ [classref boost::itl::split_interval_set Split_interval_set]]
[def __sep_itv_set__ [classref boost::itl::separate_interval_set separate_interval_set]]
+[def __sep_itv_sets__ [classref boost::itl::separate_interval_set separate_interval_sets]]
[def __Sep_itv_set__ [classref boost::itl::separate_interval_set Separate_interval_set]]
[def __itv_map__ [classref boost::itl::interval_map interval_map]]
[def __itv_maps__ [classref boost::itl::interval_map interval_maps]]
@@ -117,6 +118,10 @@
[def __iterative__ iterative]
[def __Iterative__ Iterative]
+[def __On__ ['O(n)]]
+[def __Olgn__ ['O(log n)]]
+[def __Onlgn__ ['O(n log n)]]
+
[/ Cited Boost resources ]
[/ Other web resources ]
@@ -132,6 +137,7 @@
[include concepts.qbk]
[include semantics.qbk]
[include interface.qbk]
+[include implementation.qbk]
[include acknowledgments.qbk]
[xinclude itldoc.xml]
Modified: sandbox/itl/libs/itl/doc/semantics.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/semantics.qbk (original)
+++ sandbox/itl/libs/itl/doc/semantics.qbk 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -1,5 +1,5 @@
[/
- Copyright (c) 2008-2008 Joachim Faulhaber
+ Copyright (c) 2008-2009 Joachim Faulhaber
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
Modified: sandbox/itl/libs/itl/example/interval_container_/vc9_interval_container.vcproj
==============================================================================
--- sandbox/itl/libs/itl/example/interval_container_/vc9_interval_container.vcproj (original)
+++ sandbox/itl/libs/itl/example/interval_container_/vc9_interval_container.vcproj 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -198,6 +198,10 @@
>
</File>
<File
+ RelativePath="..\..\..\..\boost\itl\interval_map.hpp"
+ >
+ </File>
+ <File
RelativePath="..\..\..\..\boost\itl\interval_set.hpp"
>
</File>
Modified: sandbox/itl/libs/itl/test/fastest_interval_set_mixed_/fastest_interval_set_mixed.cpp
==============================================================================
--- sandbox/itl/libs/itl/test/fastest_interval_set_mixed_/fastest_interval_set_mixed.cpp (original)
+++ sandbox/itl/libs/itl/test/fastest_interval_set_mixed_/fastest_interval_set_mixed.cpp 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -9,7 +9,6 @@
#include <string>
#include <boost/mpl/list.hpp>
#include <boost/test/unit_test.hpp>
-//CL #include <boost/test/test_case_template.hpp>
// interval instance types
#include "../test_type_lists.hpp"
Modified: sandbox/itl/libs/itl/test/fastest_itl_interval_/fastest_itl_interval.cpp
==============================================================================
--- sandbox/itl/libs/itl/test/fastest_itl_interval_/fastest_itl_interval.cpp (original)
+++ sandbox/itl/libs/itl/test/fastest_itl_interval_/fastest_itl_interval.cpp 2009-07-12 08:29:53 EDT (Sun, 12 Jul 2009)
@@ -9,7 +9,6 @@
#include <string>
#include <boost/mpl/list.hpp>
#include <boost/test/unit_test.hpp>
-//CL #include <boost/test/test_case_template.hpp>
// interval instance types
#include "../test_type_lists.hpp"