Subject: [Boost-commit] svn:boost r55129 - in sandbox/itl: boost/itl libs/itl/doc libs/validate/src/gentor
From: afojgo_at_[hidden]
Date: 2009-07-23 11:59:21
Author: jofaber
Date: 2009-07-23 11:59:20 EDT (Thu, 23 Jul 2009)
New Revision: 55129
URL: http://svn.boost.org/trac/boost/changeset/55129
Log:
Refactoring. Modified add with hint to version that is portable - hopefully. Stable {msvc-9.0}
Text files modified:
sandbox/itl/boost/itl/interval_base_map.hpp | 2 +-
sandbox/itl/boost/itl/interval_base_set.hpp | 13 ++++++++++++-
sandbox/itl/boost/itl/interval_map.hpp | 11 +++++------
sandbox/itl/boost/itl/interval_set.hpp | 17 +++++++++--------
sandbox/itl/boost/itl/separate_interval_set.hpp | 15 ++++++++-------
sandbox/itl/boost/itl/split_interval_map.hpp | 11 +++++------
sandbox/itl/boost/itl/split_interval_set.hpp | 15 ++++++++-------
sandbox/itl/libs/itl/doc/implementation.qbk | 20 ++++++++++----------
sandbox/itl/libs/itl/doc/itl.qbk | 2 ++
sandbox/itl/libs/validate/src/gentor/gentorprofile.cpp | 4 ++--
10 files changed, 62 insertions(+), 48 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-23 11:59:20 EDT (Thu, 23 Jul 2009)
@@ -854,7 +854,7 @@
{
interval_type common_interval = it_->KEY_VALUE & sectant_interval;
if(!common_interval.empty())
- prior_ = section.that()->add(prior_, value_type(common_interval, it_->CONT_VALUE) );
+ prior_ = section.that()->gap_insert<codomain_combine>(prior_, common_interval, it_->CONT_VALUE );
}
}
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-23 11:59:20 EDT (Thu, 23 Jul 2009)
@@ -409,6 +409,13 @@
iterator prior(iterator it_)
{ return it_ == this->_set.begin() ? this->_set.end() : --it_; }
+ iterator gap_insert(iterator prior_, const interval_type& inter_val)
+ {
+ // inter_val is not conained in this map. Insertion will be successful
+ BOOST_ASSERT(this->_set.find(inter_val) == this->_set.end());
+ return this->_set.insert(prior_, inter_val);
+ }
+
protected:
ImplSetT _set;
} ;
@@ -461,7 +468,11 @@
iterator prior_ = section.end();
for(const_iterator it_=first_; it_ != end_; it_++)
- prior_ = section.add(prior_, (*it_) & inter_val);
+ {
+ interval_type common_interval = (*it_) & inter_val;
+ if(!common_interval.empty())
+ prior_ = section.gap_insert(prior_, common_interval);
+ }
}
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-23 11:59:20 EDT (Thu, 23 Jul 2009)
@@ -321,18 +321,17 @@
return prior_;
std::pair<iterator,bool> insertion
- = this->template map_insert<Combiner>(inter_val, co_val);
+ = 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_;
+ std::pair<iterator,iterator> overlap = this->_map.equal_range(inter_val);
+ iterator it_ = overlap.first,
+ last_ = overlap.second;
+ --last_;
interval_type rest_interval = inter_val;
add_front (rest_interval, co_val, it_);
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-23 11:59:20 EDT (Thu, 23 Jul 2009)
@@ -251,7 +251,7 @@
{
iterator first_ = this->_set.lower_bound(addend),
last_ = insertion.ITERATOR,
- end_ = insertion.ITERATOR; end_ ++;
+ end_ = insertion.ITERATOR; ++end_;
//BOOST_ASSERT(end_ == this->_map.upper_bound(inter_val));
iterator second_= first_; ++second_;
@@ -275,16 +275,17 @@
if(addend.empty())
return prior_;
- std::pair<iterator,bool> insertion = this->_set.insert(addend);
+ iterator insertion = this->_set.insert(prior_, addend);
- if(insertion.WAS_SUCCESSFUL)
- return handle_neighbours(insertion.ITERATOR);
+ if(*insertion == addend)
+ return handle_neighbours(insertion);
else
{
- iterator first_ = this->_set.lower_bound(addend),
- last_ = insertion.ITERATOR,
- end_ = last_; ++end_;
- //BOOST_ASSERT(end_ == this->_map.upper_bound(inter_val));
+ std::pair<iterator,iterator> overlap = this->_set.equal_range(addend);
+ iterator first_ = overlap.first,
+ end_ = overlap.second,
+ last_ = end_; --last_;
+
iterator second_= first_; ++second_;
interval_type leftResid = right_subtract(*first_, addend);
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-23 11:59:20 EDT (Thu, 23 Jul 2009)
@@ -191,16 +191,17 @@
if(addend.empty())
return prior_;
- std::pair<iterator,bool> insertion = this->_set.insert(addend);
+ iterator insertion = this->_set.insert(prior_, addend);
- if(insertion.WAS_SUCCESSFUL)
- return insertion.ITERATOR;
+ if(*insertion == addend)
+ return insertion;
else
{
- iterator first_ = this->_set.lower_bound(addend),
- last_ = insertion.ITERATOR,
- end_ = last_; ++end_;
- //BOOST_ASSERT(end_ == this->_map.upper_bound(inter_val));
+ std::pair<iterator,iterator> overlap = this->_set.equal_range(addend);
+ iterator first_ = overlap.first,
+ end_ = overlap.second,
+ last_ = end_; --last_;
+
iterator second_= first_; ++second_;
interval_type leftResid = right_subtract(*first_, addend);
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-23 11:59:20 EDT (Thu, 23 Jul 2009)
@@ -224,18 +224,17 @@
return prior_;
std::pair<iterator,bool> insertion
- = this->template map_insert<Combiner>(inter_val, co_val);
+ = 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_ = first_;
+ std::pair<iterator,iterator> overlap = this->_map.equal_range(inter_val);
+ iterator it_ = overlap.first,
+ last_ = overlap.second;
+ --last_;
interval_type rest_interval = inter_val;
add_front (rest_interval, co_val, 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-23 11:59:20 EDT (Thu, 23 Jul 2009)
@@ -188,15 +188,16 @@
if(addend.empty())
return prior_;
- std::pair<iterator,bool> insertion = this->_set.insert(addend);
+ iterator insertion = this->_set.insert(prior_, addend);
- if(insertion.WAS_SUCCESSFUL)
- return insertion.ITERATOR;
- else
+ if(*insertion == addend)
+ return insertion;
+ else
{
- iterator first_ = this->_set.lower_bound(addend),
- last_ = insertion.ITERATOR;
- //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
+ std::pair<iterator,iterator> overlap = this->_set.equal_range(addend);
+ iterator first_ = overlap.first,
+ end_ = overlap.second,
+ last_ = end_; --last_;
iterator it_ = first_;
interval_type rest_interval = addend;
Modified: sandbox/itl/libs/itl/doc/implementation.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/implementation.qbk (original)
+++ sandbox/itl/libs/itl/doc/implementation.qbk 2009-07-23 11:59:20 EDT (Thu, 23 Jul 2009)
@@ -36,11 +36,11 @@
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.
+containers behave like containers 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
+`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
@@ -48,14 +48,14 @@
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__] ]
+[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& object, const P& addend)`] [element] [] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ]
+[[] [segment] [best case] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ]
+[[where] [] [worst case] [__On__] [__On__] [__On__] [__On__] [__On__] ]
+[[ /n/ = `object.interval_count()`] [] [amortized] [__Olgn__] [__Olgn__] [] [] [] ]
+[[ /m/ = `addend.interval_count()`] [container] [] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] ]
]
In the ['*worst case*], where the inserted segment overlaps with
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-23 11:59:20 EDT (Thu, 23 Jul 2009)
@@ -121,6 +121,8 @@
[def __On__ ['O(n)]]
[def __Olgn__ ['O(log n)]]
[def __Onlgn__ ['O(n log n)]]
+[def __Omlgn__ ['O(m log n)]]
+[def __Omlgnpm__ ['O(m log(n+m))]]
[/ Cited Boost resources ]
Modified: sandbox/itl/libs/validate/src/gentor/gentorprofile.cpp
==============================================================================
--- sandbox/itl/libs/validate/src/gentor/gentorprofile.cpp (original)
+++ sandbox/itl/libs/validate/src/gentor/gentorprofile.cpp 2009-07-23 11:59:20 EDT (Thu, 23 Jul 2009)
@@ -111,10 +111,10 @@
set_range_element_ContainerSize(0,20);
set_repeat_count(1);
- set_trials_count(10);
+ set_trials_count(20);
set_laws_per_cycle(100);
- set_debug_defaults();
+ //set_debug_defaults();
//--------------------------------------------------------------------------
// values for novial_tree test