|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r55306 - in sandbox/itl: boost/itl libs/itl/doc libs/itl/test libs/itl/test/test_casual_
From: afojgo_at_[hidden]
Date: 2009-07-30 21:12:40
Author: jofaber
Date: 2009-07-30 19:23:26 EDT (Thu, 30 Jul 2009)
New Revision: 55306
URL: http://svn.boost.org/trac/boost/changeset/55306
Log:
Refactoring, documenting. Modified enable_if statements to make overload resolution clearer. Added documentation. Stable {msvc-9.0}
Text files modified:
sandbox/itl/boost/itl/interval_base_map.hpp | 24 +++++--
sandbox/itl/boost/itl/interval_maps.hpp | 44 ++++---------
sandbox/itl/boost/itl/interval_sets.hpp | 56 ++++++++++++++--
sandbox/itl/boost/itl/operators.hpp | 132 ++++++++++++++++++++++++++++++++++++---
sandbox/itl/boost/itl/set.hpp | 2
sandbox/itl/libs/itl/doc/implementation.qbk | 114 ++++++++++++++++++++++++---------
sandbox/itl/libs/itl/doc/interface.qbk | 4
sandbox/itl/libs/itl/test/test_casual_/test_casual.cpp | 15 ++++
sandbox/itl/libs/itl/test/test_interval_map_mixed.hpp | 38 +++++++++-
9 files changed, 329 insertions(+), 100 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-30 19:23:26 EDT (Thu, 30 Jul 2009)
@@ -414,14 +414,24 @@
/** Erase all value pairs for a set of intervals. */
template<class SetSubType>
- SubType& erase(const interval_base_set<SetSubType,DomainT,Compare,Interval,Alloc>& eraser)
+ SubType& erase(const interval_base_set<SetSubType,DomainT,Compare,Interval,Alloc>& operand)
{
- typedef interval_base_set<SetSubType,DomainT,Compare,Interval,Alloc> interval_base_set_type;
- for(typename interval_base_set_type::const_iterator interval_ = eraser.begin();
- interval_ != eraser.end(); ++interval_)
- erase(*interval_);
-
- return *that();
+ typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> operand_type;
+
+ if(operand.empty())
+ return *that();
+
+ typename operand_type::const_iterator common_lwb;
+ typename operand_type::const_iterator common_upb;
+
+ if(!Set::common_range(common_lwb, common_upb, operand, *this))
+ return *that();
+
+ typename operand_type::const_iterator it_ = common_lwb;
+ while(it_ != common_upb)
+ erase(*it_++);
+
+ return *that();
}
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-30 19:23:26 EDT (Thu, 30 Jul 2009)
@@ -5,8 +5,8 @@
(See accompanying file LICENCE.txt or copy at
http://www.boost.org/LICENSE_1_0.txt)
+-----------------------------------------------------------------------------*/
-#ifndef __itl_interval_maps_h_JOFA_081008__
-#define __itl_interval_maps_h_JOFA_081008__
+#ifndef __itl_interval_maps_hpp_JOFA_081008__
+#define __itl_interval_maps_hpp_JOFA_081008__
#include <boost/itl/interval_base_map.hpp>
#include <boost/itl/interval_map_algo.hpp>
@@ -279,7 +279,10 @@
class SubType, class DomainT, class CodomainT, class Traits,
ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
-ObjectT& operator +=
+inline
+typename boost::enable_if<is_interval_map<ObjectT>,
+ ObjectT>::type&
+operator +=
(
ObjectT& object,
const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>& operand
@@ -303,7 +306,10 @@
class SubType, class DomainT, class CodomainT, class Traits,
ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
-ObjectT& operator -=
+inline
+typename boost::enable_if<is_interval_map<ObjectT>,
+ ObjectT>::type&
+operator -=
(
ObjectT& object,
const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>& operand
@@ -326,7 +332,10 @@
class SubType, class DomainT, class CodomainT, class Traits,
ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
-ObjectT& operator ^=
+inline
+typename boost::enable_if<is_interval_map<ObjectT>,
+ ObjectT>::type&
+operator ^=
(
ObjectT& object,
const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>& operand
@@ -336,31 +345,6 @@
}
//-----------------------------------------------------------------------------
-// erasure -= of elements given by an interval_set
-//-----------------------------------------------------------------------------
-template
-<
- class ObjectT,
- class DomainT, class CodomainT, class Traits,
- ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc,
- template<class, ITL_COMPARE, template<class,ITL_COMPARE>class, ITL_ALLOC>class IntervalSet
->
-ObjectT&
-operator -=
-(
- ObjectT& object,
- const IntervalSet<DomainT,Compare,Interval,Alloc>& erasure
-)
-{
- typedef IntervalSet<DomainT,Compare,Interval,Alloc> set_type;
- const_FORALL(typename set_type, interval_, erasure)
- object.erase(*interval_);
-
- return object;
-}
-
-
-//-----------------------------------------------------------------------------
// insert
//-----------------------------------------------------------------------------
template
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-30 19:23:26 EDT (Thu, 30 Jul 2009)
@@ -81,7 +81,10 @@
class ObjectT,
class SubType, class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
-inline ObjectT& operator +=
+inline
+typename boost::enable_if<is_interval_set<ObjectT>,
+ ObjectT>::type&
+operator +=
(
ObjectT& object,
const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& operand
@@ -95,26 +98,42 @@
return object;
}
-//-----------------------------------------------------------------------------
-// difference -=
-//-----------------------------------------------------------------------------
+/*CL?
+//==============================================================================
+//= Subtraction
+//==============================================================================
template
<
class ObjectT,
class SubType, class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
-inline ObjectT& operator -=
+inline
+typename boost::enable_if<is_interval_set_companion<ObjectT, SubType>,
+ ObjectT>::type&
+operator -=
(
ObjectT& object,
const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& operand
)
{
typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> operand_type;
- const_FORALL(typename operand_type, elem_, operand)
- object.erase(*elem_);
+
+ 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;
}
+*/
//-----------------------------------------------------------------------------
// symmetric difference ^=
@@ -124,7 +143,10 @@
class ObjectT,
class SubType, class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc
>
-inline ObjectT& operator ^=
+inline
+typename boost::enable_if<is_interval_set<ObjectT>,
+ ObjectT>::type&
+operator ^=
(
ObjectT& object,
const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& operand
@@ -206,7 +228,23 @@
const IntervalSet <DomainT,Compare,Interval,Alloc>& operand
)
{
- return object -= 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;
}
Modified: sandbox/itl/boost/itl/operators.hpp
==============================================================================
--- sandbox/itl/boost/itl/operators.hpp (original)
+++ sandbox/itl/boost/itl/operators.hpp 2009-07-30 19:23:26 EDT (Thu, 30 Jul 2009)
@@ -17,16 +17,30 @@
//==============================================================================
//= 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 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:
+ \b Complexity:
\code
- interval
-OperandT: element segment container
-ObjectT: interval container O(log n) O(n) O(n log n)
+ \ OperandT: interval
+ \ element segment container
+ObjectT:
+ interval container O(log n) O(n) O(m log(n+m))
+
+ 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.
+For \c interval_sets and \c separate_interval_sets addition of segments
+is \b amortized \b logarithmic.
*/
template<class ObjectT, class OperandT>
typename boost::enable_if<is_intra_derivative<ObjectT, OperandT>,
@@ -60,8 +74,30 @@
//------------------------------------------------------------------------------
-// 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.
+ \b Complexity:
+\code
+ \ OperandT: interval
+ \ element segment container
+ObjectT:
+ interval container O(log n) O(n) O(m log(n+m))
+
+ 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.
+For \c interval_sets and \c separate_interval_sets addition of segments
+is \b amortized \b logarithmic.
+*/
template<class ObjectT, class OperandT>
typename boost::enable_if<is_right_intra_combinable<ObjectT, OperandT>,
ObjectT>::type&
@@ -91,20 +127,83 @@
}
+//==============================================================================
+//= Subtraction
+//==============================================================================
//------------------------------------------------------------------------------
-// Subtraction -=, -
+//- Subtraction -=, -
//------------------------------------------------------------------------------
+/** \par \b Requires: Types \c ObjectT and \c OperandT are subtractable.
+ \par \b Effects: \c operand is subtracted from \c object.
+ \par \b Returns: A reference to \c object.
+ \b Complexity:
+\code
+ \ OperandT: interval
+ \ element segment container
+ObjectT:
+ interval container O(log n) O(n) O(m log(n+m))
+
+ amortized
+ interval_sets O(log n)
+
+n = object.interval_count()
+m = operand.interval_count()
+\endcode
+
+For the subtraction of \em elements, \b segments and \b interval \b containers
+complexity is \b logarithmic, \b linear and \b loglinear respectively.
+For interval sets subtraction of segments
+is \b amortized \b logarithmic.
+*/
template<class ObjectT, class OperandT>
typename boost::enable_if<is_intra_derivative<ObjectT, OperandT>,
ObjectT>::type&
operator -= (ObjectT& object, const OperandT& operand)
-{ return object.subtract(operand); }
+{
+ return object.subtract(operand);
+}
template<class ObjectT, class OperandT>
typename boost::enable_if<is_cross_derivative<ObjectT, OperandT>,
ObjectT>::type&
operator -= (ObjectT& object, const OperandT& operand)
-{ return object.erase(operand); }
+{
+ return object.erase(operand);
+}
+
+template
+<
+ 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 -=
+(
+ 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;
+}
+
template<class ObjectT, class OperandT>
@@ -114,8 +213,11 @@
return object -= operand;
}
+//==============================================================================
+//= Intersection
+//==============================================================================
//------------------------------------------------------------------------------
-// Intersection &=, &
+//- Intersection &=, &
//------------------------------------------------------------------------------
template<class ObjectT, class OperandT>
typename boost::enable_if<is_right_inter_combinable<ObjectT, OperandT>, ObjectT>::type&
@@ -147,15 +249,19 @@
return object &= operand;
}
+//==============================================================================
+//= Symmetric difference
+//==============================================================================
//------------------------------------------------------------------------------
-// Symmetric difference ^=, ^
+//- Symmetric difference ^=, ^
//------------------------------------------------------------------------------
-
template<class ObjectT, class OperandT>
typename boost::enable_if<is_intra_derivative<ObjectT, OperandT>,
ObjectT>::type&
operator ^= (ObjectT& object, const OperandT& operand)
-{ return object.flip(operand); }
+{
+ return object.flip(operand);
+}
template<class ObjectT, class OperandT>
typename boost::enable_if<is_binary_intra_combinable<ObjectT, OperandT>, ObjectT>::type
Modified: sandbox/itl/boost/itl/set.hpp
==============================================================================
--- sandbox/itl/boost/itl/set.hpp (original)
+++ sandbox/itl/boost/itl/set.hpp 2009-07-30 19:23:26 EDT (Thu, 30 Jul 2009)
@@ -385,7 +385,7 @@
return object += operand;
}
-/// Add a set \c operand to this set \object.
+/// Add a set \c operand to set \c object.
template <typename DomainT, ITL_COMPARE Compare, ITL_ALLOC Alloc>
inline itl::set<DomainT,Compare,Alloc>&
operator += ( itl::set<DomainT,Compare,Alloc>& object,
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-30 19:23:26 EDT (Thu, 30 Jul 2009)
@@ -26,14 +26,14 @@
This section gives an overview over the time complextity of
the basic operations of ['itl containers].
-[h5 Complexity of element containers]
+[h4 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.
-[h5 Complexity of interval containers]
+[h4 Complexity of interval containers]
The operations of ['interval containers] behave differently
due to the fact that intervals unlike elements can overlap
@@ -41,28 +41,51 @@
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*].
-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 order to present complexity characteristics of the overloaded
+/inplace/ or /op-assign/ `operators o=` in a concise way we use a
+couple of placeholders.
+
+For an operator
+``
+T& operator o= (T& object, const P& operand)
+``
+
+[table
+[[Placeholder] []]
+[[`T`] [an interval container]]
+[[`P`] [`T::element_type` or]]
+[[] [`T::segment_type` or]]
+[[] [an interval container]]
+[[`interval_sets`][__itv_set__ or __sep_itv_set__ or __spl_itv_set__]]
+[[`interval_maps`][__itv_map__ or __spl_itv_map__]]
+[[ /n/ ] [ /n/ = `object.interval_count()`]]
+[[ /m/ ] [ /m/ = `operand.interval_count()`, if `operand` is an interval container]]
+]
+
+
+[h5 Time Complexity of Addition]
+
+The next table
+gives the time complexities for the overloaded
+`operator +=` on interval containers.
+The instance types of `T` are given as headers
+of columns 4 to 8.
+Instances of type parameter `P` are denoted in
+the second column.
+The third column containes the specific kind of complexity statement.
+If column three 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]]
-[/ 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__] ]
+[[] [`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)`] [`T::element_type`] [] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ]
+[[] [`T::segment_type`] [best case] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ]
+[[] [] [worst case] [__On__] [__On__] [__On__] [__On__] [__On__] ]
+[[] [] [amortized] [__Olgn__] [__Olgn__] [] [] [] ]
+[[] [`interval_sets`] [] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [ ] [ ] ]
+[[] [`interval_maps`] [] [ ] [ ] [ ] [__Omlgnpm__] [__Omlgnpm__] ]
]
Adding an /element/ or
@@ -100,12 +123,13 @@
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
+If the added container `operand` is much smaller than
+`object` and the intervals in `operand` are relatively
small, performance can be /logarithmic/.
-If /m/ is small compared with /n/ and intervals in `addend`
+If /m/ is small compared with /n/ and intervals in `operand`
are large, performance tends to be /linear/.
+[h5 Time Complexity of Subtraction]
The next table denotes the time complexity characteristics of
the ['*subtraction*] on interval containers.
@@ -113,28 +137,54 @@
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__] ]
+[[] [`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& operand)`] [`T::element_type`] [] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ]
+[[] [`T::segment_type`] [best case] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ]
+[[] [] [worst case] [__On__] [__On__] [__On__] [__On__] [__On__] ]
+[[] [] [amortized] [__Olgn__] [__Olgn__] [__Olgn__] [] [] ]
+[[] [`interval_sets`] [] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] ]
+[[] [`interval_maps`] [] [ ] [ ] [ ] [__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
+the subracted interval `operand` overlaps with
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*].
+[/ JODO check this]
+
+
+[h5 Time Complexity of Intersection]
+
+The /complexity patterns/ for ['*intersection*] are identical to those for ['*subtraction*].
+
+[table Time Complexity of Intersection:
+[[] [`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& operand)`] [`T::element_type`] [] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ]
+[[] [`T::segment_type`] [best case] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ]
+[[] [] [worst case] [__On__] [__On__] [__On__] [__On__] [__On__] ]
+[[] [`interval_sets`] [] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] ]
+[[] [`interval_maps`] [] [ ] [ ] [ ] [__Omlgnpm__] [__Omlgnpm__] ]
+]
+
+We can observe a general pattern, that the major operations on
+interval containers are of ['*logarithmic*], ['*linear*], and ['*loglinear*] time
+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/interface.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/interface.qbk (original)
+++ sandbox/itl/libs/itl/doc/interface.qbk 2009-07-30 19:23:26 EDT (Thu, 30 Jul 2009)
@@ -477,8 +477,8 @@
[[`T operator | (const T&, const P&)`] [ ] [__eiS] [__bpM] [__es] [__bm] [ ] [ ]]
[[['*Subtraction*]] [ ] [ ] [ ] [ ] [ ] [ ] [ ]]
[[`T& T::subtract(const P&)`] [ ] [__ei] [__bp] [__e] [__b] [ ] [ ]]
-[[`T& operator -=( T&, const P&)`] [ ] [__eiS] [__bpM] [__es] [__bm] [ ] [ ]]
-[[`T operator - (const T&, const P&)`] [ ] [__eiS] [__bpM] [__es] [__bm] [ ] [ ]]
+[[`T& operator -=( T&, const P&)`] [ ] [__eiS][__eiS __bpM][__es] [__bm] [ ] [ ]]
+[[`T operator - (const T&, const P&)`] [ ] [__eiS][__eiS __bpM][__es] [__bm] [ ] [ ]]
[[['*Insertion, erasure*]] [interval][interval\nsets][interval\nmaps][itl::set][itl::map][std::set][std::map]]
[[`V T::insert(const P&)`] [ ] [__ei] [__bp] [__e] [__b] [__e] [__b]]
[[`T& T::set(const P&)`] [ ] [ ] [__bp] [ ] [1] [ ] [ ]]
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-30 19:23:26 EDT (Thu, 30 Jul 2009)
@@ -49,6 +49,21 @@
cout << ">>> map_a_b = " << map_a_b << endl;
cout << ">>> map_b_a = " << map_b_a << endl;
+ IntervalSetT set_a;
+ set_a.add(I_D(2,4));
+ map_a -= set_a;
+ SplitIntervalMapT map_c;
+ map_c = map_a - set_a;
+
+ BOOST_CHECK_EQUAL(is_interval_container<interval_set<int> >::value, true);
+ BOOST_CHECK_EQUAL(is_interval_container<split_interval_set<int> >::value, true);
+ BOOST_CHECK_EQUAL(is_interval_container<separate_interval_set<int> >::value, true);
+ BOOST_CHECK_EQUAL(is_interval_container<std::string >::value, false);
+
+ bool interval_set_companion
+ = is_interval_set_companion< interval_map<int,int>, interval_set<int> >::value;
+ BOOST_CHECK_EQUAL(interval_set_companion, true);
+
BOOST_CHECK_EQUAL(map_a_b, map_b_a);
}
Modified: sandbox/itl/libs/itl/test/test_interval_map_mixed.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_map_mixed.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_map_mixed.hpp 2009-07-30 19:23:26 EDT (Thu, 30 Jul 2009)
@@ -504,10 +504,12 @@
//--------------------------------------------------------------------------
// Test for split_interval_map
- SplitIntervalMapT split_diff = split_map;
- IntervalMapT join_diff = join_map;
+ SplitIntervalMapT split_diff = split_map;
+ IntervalMapT join_diff = join_map;
+ SplitIntervalMapT split_diff2 = split_map;
+ IntervalMapT join_diff2 = join_map;
- //subtraction combinations
+ //erase combinations
erase(split_diff, split_sub);
erase(join_diff, split_sub);
@@ -518,12 +520,25 @@
BOOST_CHECK_EQUAL( is_element_equal(split_diff, join_diff), true );
BOOST_CHECK_EQUAL( is_element_equal(join_diff, split_diff), true );
+ //subtraction combinations
+ split_diff2 -= split_sub;
+ join_diff2 -= split_sub;
+
+ BOOST_CHECK_EQUAL( split_diff2.iterative_size(), 5 );
+ BOOST_CHECK_EQUAL( join_diff2.iterative_size(), 4 );
+
+ BOOST_CHECK_EQUAL( is_element_equal(split_diff2, split_diff2), true );
+ BOOST_CHECK_EQUAL( is_element_equal(split_diff2, join_diff2), true );
+ BOOST_CHECK_EQUAL( is_element_equal(join_diff2, split_diff2), true );
+
//--------------------------------------------------------------------------
// Test for interval_map. Reinitialize
- split_diff = split_map;
- join_diff = join_map;
+ split_diff = split_map;
+ join_diff = join_map;
+ split_diff2 = split_map;
+ join_diff2 = join_map;
- //subtraction combinations
+ //erase combinations
erase(split_diff, join_sub);
erase(join_diff, join_sub);
@@ -533,6 +548,17 @@
BOOST_CHECK_EQUAL( is_element_equal(join_diff, join_diff), true );
BOOST_CHECK_EQUAL( is_element_equal(join_diff, split_diff), true );
BOOST_CHECK_EQUAL( is_element_equal(split_diff, join_diff), true );
+
+ //subtraction combinations
+ split_diff2 -= join_sub;
+ join_diff2 -= join_sub;
+
+ BOOST_CHECK_EQUAL( split_diff2.iterative_size(), 5 );
+ BOOST_CHECK_EQUAL( join_diff2.iterative_size(), 4 );
+
+ BOOST_CHECK_EQUAL( is_element_equal(join_diff2, join_diff2), true );
+ BOOST_CHECK_EQUAL( is_element_equal(join_diff2, split_diff2), true );
+ BOOST_CHECK_EQUAL( is_element_equal(split_diff2, join_diff2), true );
}
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