|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r55314 - in sandbox/itl: boost/itl libs/itl/doc libs/itl/test/test_casual_
From: afojgo_at_[hidden]
Date: 2009-07-31 12:01:13
Author: jofaber
Date: 2009-07-31 12:01:12 EDT (Fri, 31 Jul 2009)
New Revision: 55314
URL: http://svn.boost.org/trac/boost/changeset/55314
Log:
Refactoring, documenting. Changed more enable_if statements to simplity resolution clearer and
to reduce implementations. Added documentation. Stable {msvc-9.0}
Text files modified:
sandbox/itl/boost/itl/interval_maps.hpp | 6 +
sandbox/itl/boost/itl/interval_sets.hpp | 135 +++++++++++++++------------------------
sandbox/itl/boost/itl/operators.hpp | 26 +++----
sandbox/itl/libs/itl/doc/implementation.qbk | 4 -
sandbox/itl/libs/itl/doc/itl.qbk | 4 +
sandbox/itl/libs/itl/test/test_casual_/test_casual.cpp | 134 +++++++++++++++++++++++++++++++++++++++
6 files changed, 206 insertions(+), 103 deletions(-)
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-31 12:01:12 EDT (Fri, 31 Jul 2009)
@@ -26,6 +26,7 @@
//==============================================================================
//= Emptieness, containment
//==============================================================================
+/*CL
template
<
class DomainT, class CodomainT, class Traits,
@@ -61,12 +62,15 @@
{
return Interval_Set::contains(left, right);
}
-
+*/
//-----------------------------------------------------------------------------
// is_disjoint
//-----------------------------------------------------------------------------
//--- IntervalMap -------------------------------------------------------------
+/** \par \b Returns true, if \c object and \c operand have no common elements (key value pairs).
+ Segments are interpreted as sequence of elements (key value pairs).
+ \par \b Complexity: loglinear. */
template
<
class DomainT, class CodomainT, class Traits,
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-31 12:01:12 EDT (Fri, 31 Jul 2009)
@@ -24,6 +24,8 @@
//------------------------------------------------------------------------------
// is_element_equal
//------------------------------------------------------------------------------
+/** \par \b Returns true, if \c left and \c right contain the same elements.
+ \par \b Complexity: linear. */
template
<
class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc,
@@ -38,6 +40,9 @@
return Interval_Set::is_element_equal(left, right);
}
+/** \b Returns true, if \c left is lexicographically less than \c right.
+ \par Intervals are interpreted as sequence of elements.
+ \par \b Complexity: linear. */
template
<
class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc,
@@ -52,6 +57,9 @@
return Interval_Set::is_element_less(left, right);
}
+/** \b Returns true, if \c left is lexicographically greater than \c right.
+ \par Intervals are interpreted as sequence of elements.
+ \par \b Complexity: linear. */
template
<
class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc,
@@ -69,17 +77,14 @@
//==============================================================================
//= 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.
-*/
+/** \par \c operator \c += adds an interval_base_set \c operand to an interval set \c object.
+ \par \b Returns: A reference to \c object.
+ \par \b Complexity: loglinear. */
template
<
- class ObjectT,
- class SubType, class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
+ class ObjectT, class SubType,
+ class DomainT, ITL_COMPARE Compare,
+ template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
inline
typename boost::enable_if<is_interval_set<ObjectT>,
@@ -98,50 +103,42 @@
return object;
}
-/*CL?
-//==============================================================================
-//= Subtraction
-//==============================================================================
+//-----------------------------------------------------------------------------
+// insert
+//-----------------------------------------------------------------------------
+/** Inserts an interval_base_set \c operand to an interval set \c object.
+ In the itl \c insert and \c += have the same effect for all \c Sets.
+ \par \b Returns: A reference to \c object.
+ \par \b Complexity: loglinear. */
template
<
- class ObjectT,
- class SubType, class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
+ class ObjectT, class SubType,
+ class DomainT, ITL_COMPARE Compare,
+ template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
-inline
-typename boost::enable_if<is_interval_set_companion<ObjectT, SubType>,
- ObjectT>::type&
-operator -=
+inline typename boost::enable_if<is_interval_set<ObjectT>, ObjectT>::type&
+insert
(
ObjectT& object,
const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& operand
)
{
- typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> operand_type;
-
- if(operand.empty())
- return object;
-
- typename operand_type::const_iterator common_lwb;
- typename operand_type::const_iterator common_upb;
-
- if(!Set::common_range(common_lwb, common_upb, operand, object))
- return object;
-
- typename operand_type::const_iterator it_ = common_lwb;
- while(it_ != common_upb)
- object.erase(*it_++);
-
- return object;
+ return object += operand;
}
-*/
+
-//-----------------------------------------------------------------------------
-// symmetric difference ^=
-//-----------------------------------------------------------------------------
+//==============================================================================
+//= Symmetric difference ^=
+//==============================================================================
+/** \c operator \c ^= symmetrically subtracts an interval_base_set \c operand from an interval set \c object.
+ \par \b Returns: A reference to \c object.
+ \par \b Complexity: loglinear.
+*/
template
<
- class ObjectT,
- class SubType, class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
+ class ObjectT, class SubType,
+ class DomainT, ITL_COMPARE Compare,
+ template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
inline
typename boost::enable_if<is_interval_set<ObjectT>,
@@ -158,6 +155,9 @@
//-----------------------------------------------------------------------------
// is_disjoint
//-----------------------------------------------------------------------------
+/** \b Returns true, if \c object and \c operand have no common elements.
+ Intervals are interpreted as sequence of elements.
+ \par \b Complexity: loglinear. */
template
<
class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc,
@@ -194,57 +194,26 @@
}
//-----------------------------------------------------------------------------
-// insert
-//-----------------------------------------------------------------------------
-template
-<
- class SubType, class DomainT,
- ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc,
- template<class, ITL_COMPARE, template<class,ITL_COMPARE>class, ITL_ALLOC>class IntervalSet
->
-inline interval_base_set<SubType,DomainT,Compare,Interval,Alloc>&
-insert
-(
- interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& object,
- const IntervalSet <DomainT,Compare,Interval,Alloc>& operand
-)
-{
- return object += operand;
-}
-
-//-----------------------------------------------------------------------------
// erase
//-----------------------------------------------------------------------------
+/** Erases an interval_base_set \c operand from an interval set \c object.
+ In the itl \c erase and \c -= have the same effect for all \c Sets.
+ \par \b Returns: A reference to \c object.
+ \par \b Complexity: loglinear. */
template
<
- class SubType, class DomainT,
- ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc,
- template<class, ITL_COMPARE, template<class,ITL_COMPARE>class, ITL_ALLOC>class IntervalSet
+ class ObjectT, class SubType,
+ class DomainT, ITL_COMPARE Compare,
+ template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
-inline interval_base_set<SubType,DomainT,Compare,Interval,Alloc>&
+inline typename boost::enable_if<is_interval_set<ObjectT>, ObjectT>::type&
erase
(
- interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& object,
- const IntervalSet <DomainT,Compare,Interval,Alloc>& operand
+ ObjectT& object,
+ const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& operand
)
{
- typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> operand_type;
-
- if(operand.empty())
- return object;
-
- typename operand_type::const_iterator common_lwb;
- typename operand_type::const_iterator common_upb;
-
- if(!Set::common_range(common_lwb, common_upb, operand, object))
- return object;
-
- typename operand_type::const_iterator it_ = common_lwb;
- while(it_ != common_upb)
- object.erase(*it_++);
-
- return object;
- //CL return object -= operand;
+ return object -= operand;
}
Modified: sandbox/itl/boost/itl/operators.hpp
==============================================================================
--- sandbox/itl/boost/itl/operators.hpp (original)
+++ sandbox/itl/boost/itl/operators.hpp 2009-07-31 12:01:12 EDT (Fri, 31 Jul 2009)
@@ -17,28 +17,24 @@
//==============================================================================
//= Addition
//==============================================================================
-//------------------------------------------------------------------------------
-//- Addition +=, +
-//------------------------------------------------------------------------------
-/** \par \b Requires: Types \c ObjectT and \c OperandT are addable.
- \par \b Effects: \c operand is added to \c object.
+/** \par \b Requires: \c OperandT is an addable derivative type of \c ObjectT.
+ \b Effects: \c operand is added to \c object.
\par \b Returns: A reference to \c object.
\b Complexity:
\code
- \ OperandT: interval
- \ element segment container
+ \ OperandT:
+ \ element segment
ObjectT:
- interval container O(log n) O(n) O(m log(n+m))
+ interval container O(log n) O(n)
interval_set amortized
spearate_interval_set O(log n)
n = object.interval_count()
-m = operand.interval_count()
\endcode
For the addition of \b elements, \b segments and \b interval \b containers
-complexity is \b logarithmic, \b linear and \b loglinear respectively.
+complexity is \b logarithmic and \b linear respectively.
For \c interval_sets and \c separate_interval_sets addition of segments
is \b amortized \b logarithmic.
*/
@@ -173,20 +169,19 @@
template
<
- class ObjectT,
- class SubType, class DomainT, ITL_COMPARE Compare,
+ class ObjectT, class SetT, class DomainT, ITL_COMPARE Compare,
template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
inline
-typename boost::enable_if<is_interval_set_companion<ObjectT, SubType>,
+typename boost::enable_if<is_interval_set_companion<ObjectT, SetT>,
ObjectT>::type&
operator -=
(
ObjectT& object,
- const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& operand
+ const interval_base_set<SetT,DomainT,Compare,Interval,Alloc>& operand
)
{
- typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> operand_type;
+ typedef interval_base_set<SetT,DomainT,Compare,Interval,Alloc> operand_type;
if(operand.empty())
return object;
@@ -249,6 +244,7 @@
return object &= operand;
}
+
//==============================================================================
//= Symmetric difference
//==============================================================================
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-31 12:01:12 EDT (Fri, 31 Jul 2009)
@@ -176,15 +176,11 @@
complexity for the combination of ['*elements*], ['*segments*] and ['*containers*]
respectively.
-
-
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]
[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-31 12:01:12 EDT (Fri, 31 Jul 2009)
@@ -125,6 +125,10 @@
[def __Omlgn__ ['O(m log n)]]
[def __Omlgnpm__ ['O(m log(n+m))]]
+[def __inpops__ `+= -= &= ^=`]
+[def __ainpop__ `o=`]
+
+
[/ Cited Boost resources ]
[/ Other web resources ]
Modified: sandbox/itl/libs/itl/test/test_casual_/test_casual.cpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_casual_/test_casual.cpp (original)
+++ sandbox/itl/libs/itl/test/test_casual_/test_casual.cpp 2009-07-31 12:01:12 EDT (Fri, 31 Jul 2009)
@@ -27,7 +27,27 @@
using namespace unit_test;
using namespace boost::itl;
+/*CL
+template<template<class, class>class IsCombinable,
+ class LeftT, class RightT>
+void check_combinable(bool truth)
+{
+ bool is_combinable = IsCombinable<LeftT,RightT>::value;
+ BOOST_CHECK_EQUAL(is_combinable, truth);
+}
+*/
+template<template<class, class>class IsCombinable,
+ class LeftT, class RightT>
+void check_combinable(bool truth, const char* type_combi)
+{
+ std::string type_combination = type_combi;
+ bool is_combinable = IsCombinable<LeftT,RightT>::value;
+ std::string combination_result = is_combinable
+ ? (is_combinable == truth ? type_combination : "NOT combinable: "+type_combination)
+ : (is_combinable == truth ? type_combination : "IS combinable: "+type_combination);
+ BOOST_CHECK_EQUAL(type_combination, combination_result);
+}
BOOST_AUTO_TEST_CASE(casual_test)
{
@@ -64,6 +84,120 @@
= is_interval_set_companion< interval_map<int,int>, interval_set<int> >::value;
BOOST_CHECK_EQUAL(interval_set_companion, true);
+ //--------------------------------------------------------------------------
+ bool is_combinable_jS_e
+ = is_intra_derivative<interval_set<int>, interval_set<int>::element_type>::value;
+ BOOST_CHECK_EQUAL(is_combinable_jS_e, true);
+
+ bool is_combinable_zS_e
+ = is_intra_derivative<separate_interval_set<int>, interval_set<int>::element_type>::value;
+ BOOST_CHECK_EQUAL(is_combinable_zS_e, true);
+
+ bool is_combinable_sS_e
+ = is_intra_derivative<split_interval_set<int>, interval_set<int>::element_type>::value;
+ BOOST_CHECK_EQUAL(is_combinable_sS_e, true);
+ //--------------------------------------------------------------------------
+ bool is_combinable_jS_i
+ = is_intra_derivative<interval_set<int>, interval_set<int>::segment_type>::value;
+ BOOST_CHECK_EQUAL(is_combinable_jS_i, true);
+
+ bool is_combinable_zS_i
+ = is_intra_derivative<separate_interval_set<int>, interval_set<int>::segment_type>::value;
+ BOOST_CHECK_EQUAL(is_combinable_zS_i, true);
+
+ bool is_combinable_sS_i
+ = is_intra_derivative<split_interval_set<int>, interval_set<int>::segment_type>::value;
+ BOOST_CHECK_EQUAL(is_combinable_sS_i, true);
+ //--------------------------------------------------------------------------
+ bool is_combinable_jM_e
+ = is_intra_derivative<interval_map<int,int>, interval_map<int,int>::element_type>::value;
+ BOOST_CHECK_EQUAL(is_combinable_jM_e, true);
+
+ bool is_combinable_sM_e
+ = is_intra_derivative<split_interval_map<int,int>, split_interval_map<int,int>::element_type>::value;
+ BOOST_CHECK_EQUAL(is_combinable_sM_e, true);
+ //--------------------------------------------------------------------------
+ bool is_combinable_jM_i
+ = is_intra_derivative<interval_map<int,int>, interval_map<int,int>::segment_type>::value;
+ BOOST_CHECK_EQUAL(is_combinable_jM_i, true);
+
+ bool is_combinable_sM_i
+ = is_intra_derivative<split_interval_map<int,int>, split_interval_map<int,int>::segment_type>::value;
+ BOOST_CHECK_EQUAL(is_combinable_sM_i, true);
+ //--------------------------------------------------------------------------
+ //--------------------------------------------------------------------------
+
+ typedef interval_set<int> jS;
+ typedef separate_interval_set<int> zS;
+ typedef split_interval_set<int> sS;
+ typedef interval_map<int,int> jM;
+ typedef split_interval_map<int,int> sM;
+
+ typedef interval_set<int>::element_type jS_e;
+ typedef separate_interval_set<int>::element_type zS_e;
+ typedef split_interval_set<int>::element_type sS_e;
+ typedef interval_map<int,int>::element_type jM_b;
+ typedef split_interval_map<int,int>::element_type sM_b;
+
+ typedef interval_set<int>::segment_type jS_i;
+ typedef separate_interval_set<int>::segment_type zS_i;
+ typedef split_interval_set<int>::segment_type sS_i;
+ typedef interval_map<int,int>::segment_type jM_p;
+ typedef split_interval_map<int,int>::segment_type sM_p;
+
+ typedef interval_map<int,int>::domain_type jM_e;
+ typedef split_interval_map<int,int>::domain_type sM_e;
+ typedef interval_map<int,int>::interval_type jM_i;
+ typedef split_interval_map<int,int>::interval_type sM_i;
+
+ //
+ // jS
+ // zS
+
+
+ check_combinable<is_intra_derivative, jS, jS_e>(true, "jS_jS_e");
+ check_combinable<is_intra_derivative, zS, zS_e>(true, "zS_zS_e");
+ check_combinable<is_intra_derivative, sS, sS_e>(true, "sS_sS_e");
+
+ check_combinable<is_intra_derivative, jS, jS_i>(true, "jS_jS_i");
+ check_combinable<is_intra_derivative, zS, zS_i>(true, "zS_zS_i");
+ check_combinable<is_intra_derivative, sS, sS_i>(true, "sS_sS_i");
+
+ check_combinable<is_intra_derivative, jM, jM_b>(true, "jM_jM_b");
+ check_combinable<is_intra_derivative, sM, sM_b>(true, "sM_sM_b");
+
+ check_combinable<is_intra_derivative, jM, jM_p>(true, "jM_jM_p");
+ check_combinable<is_intra_derivative, sM, sM_p>(true, "sM_sM_p");
+
+ check_combinable<is_cross_derivative, jM, jM_e>(true, "jM_jM_e");
+ check_combinable<is_cross_derivative, sM, sM_e>(true, "sM_sM_e");
+
+ check_combinable<is_cross_derivative, jM, jM_i>(true, "jM_jM_i");
+ check_combinable<is_cross_derivative, sM, sM_i>(true, "sM_sM_i");
+
+ check_combinable<is_interval_set_companion, jS, jS>(true, "jS_jS");
+ check_combinable<is_interval_set_companion, jS, zS>(true, "jS_zS");
+ check_combinable<is_interval_set_companion, jS, sS>(true, "jS_sS");
+
+ check_combinable<is_interval_set_companion, zS, jS>(true, "zS_jS");
+ check_combinable<is_interval_set_companion, zS, zS>(true, "zS_zS");
+ check_combinable<is_interval_set_companion, zS, sS>(true, "zS_sS");
+
+ check_combinable<is_interval_set_companion, sS, jS>(true, "sS_jS");
+ check_combinable<is_interval_set_companion, sS, zS>(true, "sS_zS");
+ check_combinable<is_interval_set_companion, sS, sS>(true, "sS_sS");
+
+ check_combinable<is_interval_set_companion, jM, jS>(true, "jM_jS");
+ check_combinable<is_interval_set_companion, jM, zS>(true, "jM_zS");
+ check_combinable<is_interval_set_companion, jM, sS>(true, "jM_sS");
+
+ check_combinable<is_interval_set_companion, sM, jS>(true, "sM_jS");
+ check_combinable<is_interval_set_companion, sM, zS>(true, "sM_zS");
+ check_combinable<is_interval_set_companion, sM, sS>(true, "sM_sS");
+
+
+
+ //--------------------------------------------------------------------------
BOOST_CHECK_EQUAL(map_a_b, map_b_a);
}
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