|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r55255 - in sandbox/itl: boost/itl boost/validate/driver boost/validate/gentor libs/itl/doc libs/itl/test libs/validate/example/labat_collector_ libs/validate/src/gentor
From: afojgo_at_[hidden]
Date: 2009-07-30 14:44:39
Author: jofaber
Date: 2009-07-29 04:00:22 EDT (Wed, 29 Jul 2009)
New Revision: 55255
URL: http://svn.boost.org/trac/boost/changeset/55255
Log:
Refactoring, optimizing. Improved copy ctors and assignment for interval container.
Replaced enclosure by hull. Added documentation for complexity. Stable {msvc-9.0}
Text files modified:
sandbox/itl/boost/itl/interval.hpp | 39 +++++++++++++-
sandbox/itl/boost/itl/interval_base_map.hpp | 2
sandbox/itl/boost/itl/interval_base_set.hpp | 5 -
sandbox/itl/boost/itl/interval_map.hpp | 3
sandbox/itl/boost/itl/interval_maps.hpp | 4
sandbox/itl/boost/itl/interval_set.hpp | 3
sandbox/itl/boost/itl/interval_sets.hpp | 17 ++++-
sandbox/itl/boost/itl/operators.hpp | 21 ++++++-
sandbox/itl/boost/itl/separate_interval_set.hpp | 7 -
sandbox/itl/boost/itl/split_interval_map.hpp | 8 --
sandbox/itl/boost/itl/split_interval_set.hpp | 7 -
sandbox/itl/boost/validate/driver/itl_driver.hpp | 6 +
sandbox/itl/boost/validate/gentor/gentorprofile.hpp | 45 +++++++++++++---
sandbox/itl/boost/validate/gentor/randomgentor.hpp | 4
sandbox/itl/libs/itl/doc/examples.qbk | 18 +++---
sandbox/itl/libs/itl/doc/implementation.qbk | 90 ++++++++++++++++++++++++++++-------
sandbox/itl/libs/itl/doc/itl.qbk | 1
sandbox/itl/libs/itl/test/test_interval_map_shared.hpp | 8 +-
sandbox/itl/libs/itl/test/test_interval_set_shared.hpp | 6 +-
sandbox/itl/libs/validate/example/labat_collector_/labat_collector.cpp | 2
sandbox/itl/libs/validate/src/gentor/gentorprofile.cpp | 101 +++++++++++++++++----------------------
21 files changed, 254 insertions(+), 143 deletions(-)
Modified: sandbox/itl/boost/itl/interval.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval.hpp (original)
+++ sandbox/itl/boost/itl/interval.hpp 2009-07-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -58,24 +58,34 @@
/** A class template for intervals */
template <class DomainT, ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, DomainT)>
-#ifdef USE_CONCEPTS
- requires std::LessThanComparable<DomainT>
-#endif
class interval
{
public:
+ //==========================================================================
+ //= Associated types
+ //==========================================================================
typedef interval<DomainT,Compare> type;
- /// Domain type or element type
+ //--------------------------------------------------------------------------
+ //- Associated types: Data
+ //--------------------------------------------------------------------------
+ /// The domain type of the interval
typedef DomainT domain_type;
+ /// The codomaintype is the same as domain_type
typedef DomainT codomain_type;
+ /// The element type of the interval
typedef DomainT element_type;
+ /// The segment type is the interval's type
typedef type segment_type;
+ /// The interval type is the interval's type
+ typedef type interval_type;
+ //--------------------------------------------------------------------------
+ //- Associated types: Implementation and stl related
+ //--------------------------------------------------------------------------
typedef DomainT key_type;
typedef DomainT data_type;
typedef DomainT value_type;
- typedef type interval_type;
/// Compare order on the data
typedef ITL_COMPARE_DOMAIN(Compare,DomainT) domain_compare;
@@ -267,6 +277,9 @@
/** Object as string */
const std::string as_string()const;
+ //==========================================================================
+ //= Predicates
+ //==========================================================================
/** What type is the interval?
\code
@@ -969,6 +982,18 @@
//==============================================================================
+//= Addition
+//==============================================================================
+
+/** \c hull returns the smallest interval containing \c left and \c right. */
+template <class DomainT, ITL_COMPARE Compare>
+inline interval<DomainT,Compare> hull(interval<DomainT,Compare> left,
+ const interval<DomainT,Compare>& right)
+{
+ return left.extend(right);
+}
+
+//==============================================================================
//= Subtraction
//==============================================================================
@@ -1016,6 +1041,10 @@
return left &= right;
}
+//==============================================================================
+//= Representation
+//==============================================================================
+
template<class CharType, class CharTraits, class DomainT, ITL_COMPARE Compare>
std::basic_ostream<CharType, CharTraits> &operator<<
(std::basic_ostream<CharType, CharTraits> &stream, interval<DomainT,Compare> const& x)
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -177,7 +177,7 @@
/** Assignment operator */
interval_base_map& operator = (const interval_base_map& src)
{
- if(this!=&src) that()->assign(src);
+ this->_map = src._map;
return *this;
}
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -128,13 +128,12 @@
interval_base_set(){}
/** Copy constructor */
- interval_base_set(const interval_base_set& src): _set()
- { that()->assign(src); }
+ interval_base_set(const interval_base_set& src): _set(src._set){}
/** Assignment operator */
interval_base_set& operator = (const interval_base_set& src)
{
- if(this!=&src) that()->assign(src);
+ this->_set = src._set;
return *this;
}
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -103,8 +103,9 @@
Traits,Compare,Combine,Section,Interval,Alloc> base_map_type;
this->clear();
// Can be implemented via _map.insert: Interval joining not necessary.
+ iterator prior_ = this->_map.end();
const_FORALL(typename base_map_type, it_, src)
- this->add(*it_);
+ prior_ = this->add(prior_, *it_);
}
private:
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -407,7 +407,7 @@
//-----------------------------------------------------------------------------
-// enclosure
+// hull
//-----------------------------------------------------------------------------
template
<
@@ -415,7 +415,7 @@
ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::interval_type
-enclosure(const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>& object)
+hull(const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>& object)
{
typedef interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> IntervalMapT;
typedef typename IntervalMapT::interval_type interval_type;
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -121,8 +121,9 @@
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
+ iterator prior_ = this->_set.end();
const_FORALL(typename base_set_type, it_, src)
- this->add(*it_);
+ prior_ = this->add(prior_, *it_);
}
private:
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -66,9 +66,16 @@
return Interval_Set::is_element_greater(left, right);
}
-//-----------------------------------------------------------------------------
-// addition +=
-//-----------------------------------------------------------------------------
+//==============================================================================
+//= Addition
+//==============================================================================
+/** \c operator \c += adds an interval_base_set \c operand to an interval set
+ \c object.
+
+ \b Returns: A reference to \c object.
+
+ \b Complexity: loglinear.
+*/
template
<
class ObjectT,
@@ -204,7 +211,7 @@
//-----------------------------------------------------------------------------
-// enclosure
+// hull
//-----------------------------------------------------------------------------
template
<
@@ -212,7 +219,7 @@
ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
inline typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::interval_type
-enclosure(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& object)
+hull(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& object)
{
typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> IntervalSetT;
typedef typename IntervalSetT::interval_type interval_type;
Modified: sandbox/itl/boost/itl/operators.hpp
==============================================================================
--- sandbox/itl/boost/itl/operators.hpp (original)
+++ sandbox/itl/boost/itl/operators.hpp 2009-07-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -14,14 +14,27 @@
namespace boost{namespace itl
{
-//------------------------------------------------------------------------------
-// Addability +=, +
-//------------------------------------------------------------------------------
+//==============================================================================
+//= Addition
+//==============================================================================
+/** \par \b Requires: Types \c ObjectT and \c OperandT are addable.
+ \par \b Effects: \c operand is added to \c object.
+ \par \b Returns: A reference to \c object.
+ \par \b Complexity: For <tt>n = object.interval_count()</tt> and all
+ possible combinations of interval containers, segment and element types:
+\code
+ interval
+OperandT: element segment container
+ObjectT: interval container O(log n) O(n) O(n log n)
+\endcode
+*/
template<class ObjectT, class OperandT>
typename boost::enable_if<is_intra_derivative<ObjectT, OperandT>,
ObjectT>::type&
operator += (ObjectT& object, const OperandT& operand)
-{ return object.add(operand); }
+{
+ return object.add(operand);
+}
template<class ObjectT, class OperandT>
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -115,11 +115,8 @@
template<class SubType>
void assign(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
{
- 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_);
+ this->clear();
+ this->_set.insert(src.begin(), src.end());
}
private:
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -88,12 +88,8 @@
void assign(const interval_base_map<SubType,DomainT,CodomainT,
Traits,Compare,Combine,Section,Interval,Alloc>& src)
{
- typedef interval_base_map<SubType,DomainT,CodomainT,
- 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_);
+ this->clear();
+ this->_map.insert(src.begin(), src.end());
}
//==========================================================================
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -112,11 +112,8 @@
template<class SubType>
void assign(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
{
- 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_);
+ this->clear();
+ this->_set.insert(src.begin(), src.end());
}
private:
Modified: sandbox/itl/boost/validate/driver/itl_driver.hpp
==============================================================================
--- sandbox/itl/boost/validate/driver/itl_driver.hpp (original)
+++ sandbox/itl/boost/validate/driver/itl_driver.hpp 2009-07-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -100,8 +100,12 @@
instance_count += law_validation_count;
valid_count++;
}
+
std::cout << "------------------------------------------------------------------------------" << std::endl;
- printf(" %-60s%7d%7.0lf\n", " ", instance_count, avg_evaluation_time/_frequencies.size());
+ // Summary for the current cycle
+ double avg_evaluation_time_per_law = avg_evaluation_time/_frequencies.size();
+ printf( " %10.3lf%-50s%7d%7.0lf\n",
+ avg_evaluation_time_per_law, " ", instance_count, avg_evaluation_time_per_law);
int violation_count = 1;
FORALL(ViolationMapT, it, _violations)
Modified: sandbox/itl/boost/validate/gentor/gentorprofile.hpp
==============================================================================
--- sandbox/itl/boost/validate/gentor/gentorprofile.hpp (original)
+++ sandbox/itl/boost/validate/gentor/gentorprofile.hpp 2009-07-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -9,6 +9,7 @@
+-----------------------------------------------------------------------------*/
#pragma once
+#include <math.h>
#include <boost/validate/type/nat.hpp>
#include <boost/itl/interval.hpp>
@@ -24,6 +25,8 @@
void set_debug_defaults();
void set_release_defaults();
+ void set_std_profile(int unit, int factor);
+
void set_range_int(int lwb, int upb)
{ _range_int = interval<int>::rightopen(lwb, upb); }
void set_range_nat(nat lwb, nat upb)
@@ -38,11 +41,13 @@
{ _range_interval_double = interval<double>::rightopen(lwb, upb); }
void set_maxIntervalLength(int val)
{ _maxIntervalLength = val; }
- void set_range_element_ContainerSize(int lwb, int upb)
- { _range_element_ContainerSize = interval<int>::rightopen(lwb, upb); }
+ void set_range_codomain_ContainerSize(int lwb, int upb)
+ { _range_codomain_ContainerSize = interval<int>::rightopen(lwb, upb); }
void set_repeat_count(int repeat) { _repeat_count = repeat; }
void set_trials_count(int trials) { _trials_count = trials; }
+ void set_trials_count_release(int trials) { _trials_count_release = trials; }
void set_laws_per_cycle(int count){ _laws_per_cycle = count; }
+ void set_debug_slowdown(double factor){ _debug_slowdown = factor; }
interval<int> range_int() { return _range_int; }
interval<nat> range_nat() { return _range_nat; }
@@ -51,11 +56,21 @@
interval<int> range_interval_int() { return _range_interval_int; }
interval<double> range_interval_double() { return _range_interval_double; }
int maxIntervalLength() { return _maxIntervalLength; }
- interval<int> range_element_ContainerSize()
- { return _range_element_ContainerSize; }
+ interval<int> range_codomain_ContainerSize()
+ { return _range_codomain_ContainerSize; }
int repeat_count() { return _repeat_count; }
int trials_count() { return _trials_count; }
- int laws_per_cycle() { return _laws_per_cycle; }
+ int trials_count_release() { return _trials_count_release; }
+ int laws_per_cycle() { return _laws_per_cycle; }
+
+ int unit() { return _unit; }
+ int scaling() { return _scaling; }
+
+ double debug_slowdown()const { return _debug_slowdown; }
+
+ int adjusted_trials_count()const;
+
+ void report_profile();
private:
interval<int> _range_int;
@@ -67,10 +82,16 @@
interval<double> _range_interval_double;
int _maxIntervalLength;
- interval<int> _range_element_ContainerSize;
+ interval<int> _range_codomain_ContainerSize;
int _repeat_count;
int _trials_count;
+ int _trials_count_release;
int _laws_per_cycle;
+
+ double _debug_slowdown;
+
+ int _unit;
+ int _scaling;
};
@@ -93,8 +114,8 @@
void set_range_interval_int(int lwb, int upb) { m_profile.set_range_interval_int(lwb, upb); }
void set_range_interval_double(double lwb, double upb){ m_profile.set_range_interval_double(lwb, upb); }
void set_maxIntervalLength(int val) { m_profile.set_maxIntervalLength(val); }
- void set_range_element_ContainerSize(int lwb, int upb)
- { m_profile.set_range_element_ContainerSize(lwb, upb); }
+ void set_range_codomain_ContainerSize(int lwb, int upb)
+ { m_profile.set_range_codomain_ContainerSize(lwb, upb); }
void set_repeat_count(int repeat) { m_profile.set_repeat_count(repeat); }
void set_trials_count(int trials) { m_profile.set_trials_count(trials); }
void set_laws_per_cycle(int count) { m_profile.set_laws_per_cycle(count); }
@@ -102,15 +123,19 @@
interval<int> range_int() { return m_profile.range_int(); }
interval<nat> range_nat() { return m_profile.range_nat(); }
interval<double> range_double() { return m_profile.range_double(); }
- interval<int> range_ContainerSize() { return m_profile.range_ContainerSize(); }
+ interval<int> range_ContainerSize(){ return m_profile.range_ContainerSize(); }
interval<int> range_interval_int() { return m_profile.range_interval_int(); }
interval<double> range_interval_double() { return m_profile.range_interval_double();}
int maxIntervalLength() { return m_profile.maxIntervalLength(); }
- interval<int> range_element_ContainerSize(){ return m_profile.range_element_ContainerSize(); }
+ interval<int> range_codomain_ContainerSize(){ return m_profile.range_codomain_ContainerSize(); }
int repeat_count() { return m_profile.repeat_count(); }
int trials_count() { return m_profile.trials_count(); }
int laws_per_cycle() { return m_profile.laws_per_cycle(); }
+ void report_profile() { return m_profile.report_profile(); }
+
+ void set_std_profile(int unit, int factor){ return m_profile.set_std_profile(unit, factor); }
+
private:
// Singleton pattern part -------------------------------------------------
Modified: sandbox/itl/boost/validate/gentor/randomgentor.hpp
==============================================================================
--- sandbox/itl/boost/validate/gentor/randomgentor.hpp (original)
+++ sandbox/itl/boost/validate/gentor/randomgentor.hpp 2009-07-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -371,7 +371,7 @@
elementGentor->setRange(GentorProfileSgl::it()->range_int());
codomainGentor->setDomainGentor(elementGentor);
- codomainGentor->setRangeOfSampleSize(GentorProfileSgl::it()->range_element_ContainerSize());
+ codomainGentor->setRangeOfSampleSize(GentorProfileSgl::it()->range_codomain_ContainerSize());
gentor.setDomainGentor(itvGentor);
gentor.setCodomainGentor(codomainGentor);
@@ -426,7 +426,7 @@
elementGentor->setRange(GentorProfileSgl::it()->range_int());
codomainGentor->setDomainGentor(elementGentor);
- codomainGentor->setRangeOfSampleSize(GentorProfileSgl::it()->range_element_ContainerSize());
+ codomainGentor->setRangeOfSampleSize(GentorProfileSgl::it()->range_codomain_ContainerSize());
gentor.setDomainGentor(itvGentor);
gentor.setCodomainGentor(codomainGentor);
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -54,7 +54,7 @@
[endsect]
[section Party]
-[import ../example/boost_party/boost_party.cpp]
+[import ../example/boost_party_/boost_party.cpp]
Example *party* demonstrates the possibilities of an interval map
(__itv_map__ or __spl_itv_map__).
@@ -108,7 +108,7 @@
* Some borderline functions calls on open interval borders are tested e.g.:
`interval<double>::rightopen(1/sqrt(2.0), sqrt(2.0)).contains(sqrt(2.0));`
-[import ../example/interval/interval.cpp]
+[import ../example/interval_/interval.cpp]
[example_interval]
[endsect]
@@ -118,7 +118,7 @@
of different interval containers that are also summarized
in the introductory [link boost_itl.introduction.interval_combining_styles Interval Combining Styles].
-[import ../example/interval_container/interval_container.cpp]
+[import ../example/interval_container_/interval_container.cpp]
[example_interval_container]
[endsect]
@@ -135,7 +135,7 @@
the interval_map are just the number of overlaps of all added
intervals.
-[import ../example/overlap_counter/overlap_counter.cpp]
+[import ../example/overlap_counter_/overlap_counter.cpp]
[example_overlap_counter]
[endsect]
@@ -149,7 +149,7 @@
Based on the `operator +=` we can aggregate counted sums on addition
of interval value pairs into an interval_map.
-[import ../example/partys_height_average/partys_height_average.cpp]
+[import ../example/partys_height_average_/partys_height_average.cpp]
[example_partys_height_average]
Required for `class counted_sum` is a default constructor
@@ -189,7 +189,7 @@
__spl_itv_map__ that preserves all borders of inserted
intervals.
-[import ../example/partys_tallest_guests/partys_tallest_guests.cpp]
+[import ../example/partys_tallest_guests_/partys_tallest_guests.cpp]
[example_partys_tallest_guests]
[endsect]
@@ -213,7 +213,7 @@
In this example we provide an intersection of two __spl_itv_sets__
representing a month and week time grid.
-[import ../example/month_and_week_grid/month_and_week_grid.cpp]
+[import ../example/month_and_week_grid_/month_and_week_grid.cpp]
[example_month_and_week_grid]
[endsect]
@@ -228,7 +228,7 @@
times (man-power) of a company's employees accounting for weekends,
holidays, sickness times and vacations.
-[import ../example/man_power/man_power.cpp]
+[import ../example/man_power_/man_power.cpp]
[example_man_power]
[endsect]
@@ -251,7 +251,7 @@
* Computing an intersection `&` shows who is member of both med_users
and admin_users at what times.
-[import ../example/user_groups/user_groups.cpp]
+[import ../example/user_groups_/user_groups.cpp]
[example_user_groups]
[endsect]
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -12,41 +12,48 @@
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.
+classes of std::set and std::map.
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
+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
+the basic operations of ['itl containers].
+
+[h5 Complexity of element 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.
+deletion and search are all using logarithmic time.
+
+[h5 Complexity of interval containers]
-The operations of interval containers behave differently
+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
+any number of other intervals in a container. So as long as
intervals are relatively small or just singleton, interval
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
-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.
+`operator +=` for ['*addition*].
+In this table `T` is a placeholder for the type of the operation's
+first argument `object` that can be an /interval container/.
+Instance types of `T` appear as headers of columns 4 to 8.
+`P` is a placeholder for the type of the operation's second
+argument. `P` can be an `element_type`, a `segment_type` of `T` or
+an appropriate interval container type. This is denoted in
+column 2 as /element/, /segment/ or /container/.
+Column 3 containes the specific kind of complexity statement.
+If column 3 is empty ['*worst case*] complexity is given
+in the related row.
[table Time Complexity of Addition:
[[] [`P`] [][interval\nset][separate\ninterval\nset][split\ninterval\nset][interval\nmap][split\ninterval\nmap]]
@@ -58,8 +65,16 @@
[[ /m/ = `addend.interval_count()`] [container] [] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] ]
]
+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.
+
In the ['*worst case*], where the inserted segment overlaps with
-all intervals in the container, the algorithms usually
+all intervals in the container, the algorithms
iterate over all the overlapped segments.
Using inplace manipulations of segments and
hinted inserts, it is possible to perform
@@ -77,9 +92,48 @@
/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.
+time*] for the addition of an interval or interval value pair.
+For the addition of ['*interval containers*] complexity is __Omlgnpm__.
+So for the ['*worst case*], where the container sizes /n/ and /m/
+are equal and both containers cover the same ranges,
+the complexity of container addition is ['*loglinear*].
+For other cases, that occur frequently in realworld applications
+performance can be much better.
+If the added container `addend` is much smaller than
+`object` and the intervals in `addend` are relatively
+small, performance can be /logarithmic/.
+If /m/ is small compared with /n/ and intervals in `addend`
+are large, performance tends to be /linear/.
+
+
+The next table denotes the time complexity characteristics of
+the ['*subtraction*] on interval containers.
+The table shows almost the same patterns of complexities
+that has been stated for ['*addition*].
+
+[table Time Complexity of Subtraction:
+[[] [`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& minuend)`] [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__] [__Olgn__] [] [] ]
+[[ /m/ = `addend.interval_count()`] [container] [] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] ]
+]
+For __spl_itv_sets__, subtraction of an interval reduces the
+__spl_itv_set_s__ size particularly in the worst case, where
+the subracted interval `minuend` overlaps with the whole
+all intervals in `object`.
+After a worst case subtraction only 0 to 2 intervals are
+left in `object` after subtraction. That leads to a
+['*logarithmic amortized time*].
+
+While this section covers the complexity characteristics of
+the most important operations only, more complexity statements
+are included in the doxygen generated
+[link interval_template_library_reference reference documentation].
[endsect]
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -41,6 +41,7 @@
[def __Itv_sets__ [classref boost::itl::interval_set Interval_sets]]
[def __spl_itv_set__ [classref boost::itl::split_interval_set split_interval_set]]
[def __spl_itv_sets__ [classref boost::itl::split_interval_set split_interval_sets]]
+[def __spl_itv_set_s__ [classref boost::itl::split_interval_set split_interval_set's]]
[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]]
Modified: sandbox/itl/libs/itl/test/test_interval_map_shared.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_map_shared.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_map_shared.hpp 2009-07-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -60,7 +60,7 @@
BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
(mt_map += mt_u1) += mt_u1;
BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
- BOOST_CHECK_EQUAL(enclosure(mt_map), neutron<interval<T> >::value());
+ BOOST_CHECK_EQUAL(hull(mt_map), neutron<interval<T> >::value());
//subtracting emptieness
mt_map.subtract(mt_u1).subtract(mt_u1);
@@ -113,7 +113,7 @@
BOOST_CHECK_EQUAL(single_I0_0I_u1_from_element, single_I0_0I_u1_from_interval);
BOOST_CHECK_EQUAL(single_I0_0I_u1_from_element, single_I0_0I_u1);
- BOOST_CHECK_EQUAL(enclosure(single_I0_0I_u1), I0_0I);
+ BOOST_CHECK_EQUAL(hull(single_I0_0I_u1), I0_0I);
BOOST_CHECK_EQUAL(single_I0_0I_u1.lower(), I0_0I.lower());
BOOST_CHECK_EQUAL(single_I0_0I_u1.upper(), I0_0I.upper());
@@ -128,7 +128,7 @@
IntervalMapT single_I0_1I_u1(single_I0_1I_u1_from_interval);
BOOST_CHECK_EQUAL(single_I0_1I_u1_from_interval, single_I0_1I_u1);
- BOOST_CHECK_EQUAL(enclosure(single_I0_1I_u1), I0_1I);
+ BOOST_CHECK_EQUAL(hull(single_I0_1I_u1), I0_1I);
BOOST_CHECK_EQUAL(single_I0_1I_u1.lower(), I0_1I.lower());
BOOST_CHECK_EQUAL(single_I0_1I_u1.upper(), I0_1I.upper());
@@ -253,7 +253,7 @@
IntervalMapT map_A = IntervalMapT(I5_6I_u1).add(v0_u1).add(v9_u1);
IntervalMapT map_B = IntervalMapT().insert(v9_u1).insert(I5_6I_u1).insert(v0_u1);
BOOST_CHECK_EQUAL( map_A, map_B );
- BOOST_CHECK_EQUAL( enclosure(map_A), I0_9I );
+ BOOST_CHECK_EQUAL( hull(map_A), I0_9I );
BOOST_CHECK_EQUAL( map_A.lower(), I0_9I.lower() );
BOOST_CHECK_EQUAL( map_A.upper(), I0_9I.upper() );
Modified: sandbox/itl/libs/itl/test/test_interval_set_shared.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_set_shared.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_set_shared.hpp 2009-07-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -53,7 +53,7 @@
BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
(mt_set += mt_interval) += mt_interval;
BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
- BOOST_CHECK_EQUAL(enclosure(mt_set), neutron<interval<T> >::value());
+ BOOST_CHECK_EQUAL(hull(mt_set), neutron<interval<T> >::value());
//subtracting emptieness
mt_set.subtract(mt_interval).subtract(mt_interval);
@@ -114,7 +114,7 @@
IntervalSet<T> single_I0_1I(single_I0_1I_from_interval);
BOOST_CHECK_EQUAL(single_I0_1I_from_interval, single_I0_1I);
- BOOST_CHECK_EQUAL(enclosure(single_I0_1I), I0_1I);
+ BOOST_CHECK_EQUAL(hull(single_I0_1I), I0_1I);
BOOST_CHECK_EQUAL(single_I0_1I.lower(), I0_1I.lower());
BOOST_CHECK_EQUAL(single_I0_1I.upper(), I0_1I.upper());
@@ -213,7 +213,7 @@
IntervalSet<T> set_A = IntervalSet<T>(I5_6I).add(v0).add(v9);
IntervalSet<T> set_B = IntervalSet<T>().insert(v9).insert(I5_6I).insert(v0);
BOOST_CHECK_EQUAL( set_A, set_B );
- BOOST_CHECK_EQUAL( enclosure(set_A), I0_9I );
+ BOOST_CHECK_EQUAL( hull(set_A), I0_9I );
BOOST_CHECK_EQUAL( set_A.lower(), I0_9I.lower() );
BOOST_CHECK_EQUAL( set_A.upper(), I0_9I.upper() );
Modified: sandbox/itl/libs/validate/example/labat_collector_/labat_collector.cpp
==============================================================================
--- sandbox/itl/libs/validate/example/labat_collector_/labat_collector.cpp (original)
+++ sandbox/itl/libs/validate/example/labat_collector_/labat_collector.cpp 2009-07-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -24,6 +24,8 @@
">> Output will be generated in a few seconds\n"
">> terminate by typing <CTRL>C\n"
">> ------------------------------------------------------ <<\n";
+ GentorProfileSgl::it()->report_profile();
+
validater.validate();
};
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-29 04:00:22 EDT (Wed, 29 Jul 2009)
@@ -26,6 +26,8 @@
void GentorProfile::set_defaults()
{
+ set_debug_slowdown(8.45);
+ set_trials_count_release(100);
#ifdef _DEBUG
set_debug_defaults();
#else
@@ -33,6 +35,17 @@
#endif
}
+
+int GentorProfile::adjusted_trials_count()const
+{
+#ifdef _DEBUG
+ return static_cast<int>(floor(0.5+(_trials_count_release / _debug_slowdown)));
+#else
+ return _trials_count_release;
+#endif
+}
+
+
void GentorProfile::set_debug_defaults()
{
set_range_int(-5, 5);
@@ -44,10 +57,10 @@
set_range_interval_double(-5.0, 5.0);
set_maxIntervalLength(5);
- set_range_element_ContainerSize(0,4);
+ set_range_codomain_ContainerSize(0,4);
set_repeat_count(1);
- set_trials_count(20);
+ set_trials_count(adjusted_trials_count());
set_laws_per_cycle(100);
}
@@ -62,80 +75,52 @@
set_range_interval_double(-20.0, 20.0);
set_maxIntervalLength(10);
- set_range_element_ContainerSize(0,20);
+ set_range_codomain_ContainerSize(0,20);
set_repeat_count(1);
- set_trials_count(20);
+ set_trials_count(trials_count_release());
set_laws_per_cycle(100);
}
-
-
-GentorProfile::GentorProfile()
+void GentorProfile::set_std_profile(int unit, int factor)
{
+ int value = unit*factor;
+ _unit = unit;
+ _scaling = factor;
set_defaults();
- //---------------------------------
- //standard values
- //set_range_int(-10, 10);
- //set_range_nat(0, 20);
- //set_range_double(0.0, 1.0);
- //set_range_ContainerSize(0,10);
-
- //set_range_interval_int(-10, 10);
- //set_maxIntervalLength(8);
-
- //set_range_element_ContainerSize(0,5);
-
- //---------------------------------
- //small values
- //set_range_int(-5, 5);
- //set_range_nat(0, 16);
- //set_range_double(0.0, 1.0);
- //set_range_ContainerSize(0,4);
-
- //set_range_interval_int(-5, 5);
- //set_maxIntervalLength(5);
- //set_range_element_ContainerSize(0,4);
- //---------------------------------
- //current values
+ // Codomain values
set_range_int(-5, 5);
set_range_nat(0, 16);
set_range_double(0.0, 1.0);
- set_range_ContainerSize(0,20);
+ set_range_codomain_ContainerSize(0,4);
- set_range_interval_int(-20, 20);
- set_range_interval_double(-20.0, 20.0);
- set_maxIntervalLength(10);
+ // Parameter that influence speed
+ set_range_ContainerSize(0, value);
+ set_range_interval_int(-value, value);
+ set_range_interval_double(-value, value);
+ set_maxIntervalLength(value);
- set_range_element_ContainerSize(0,20);
+ // Parameter to influence frequencies of output update.
set_repeat_count(1);
- set_trials_count(20);
- set_laws_per_cycle(100);
+ set_trials_count(adjusted_trials_count());
+ set_laws_per_cycle(std::max(1, 100/factor));
+}
+
- //set_debug_defaults();
- //--------------------------------------------------------------------------
- // values for novial_tree test
- //set_range_int(-5, 5);
- //set_range_nat(0, 16);
- //set_range_double(0.0, 1.0);
- //set_range_ContainerSize(0,1000);
-
- //set_range_interval_int(0, 100000);
- //set_maxIntervalLength(1200);
- //set_range_element_ContainerSize(0,10);
-
- //set_range_int(-5, 5);
- //set_range_nat(0, 16);
- //set_range_double(0.0, 1.0);
- //set_range_ContainerSize(0,40);
-
- //set_range_interval_int(0, 1000);
- //set_maxIntervalLength(50);
- //set_range_element_ContainerSize(0,10);
+GentorProfile::GentorProfile()
+{
+ set_std_profile(4, 1);
+}
+void GentorProfile::report_profile()
+{
+ printf("(cycl=%d trls=%d rep=%d unit=%d scale=%d)\n",
+ laws_per_cycle(), trials_count(), repeat_count(),
+ unit(), scaling()
+ );
}
// -------------------------------------
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk