Subject: [Boost-commit] svn:boost r55874 - in sandbox/itl: boost/itl boost/itl/detail boost/itl/type_traits boost/validate/laws libs/itl/doc libs/itl/test libs/itl/test/fastest_interval_map_mixed_ libs/itl/test/fastest_itl_map_ libs/itl/test/test_casual_ libs/itl/test/test_interval_map_mixed_ libs/itl/test/test_itl_map_ libs/validate/example/labat_single_
From: afojgo_at_[hidden]
Date: 2009-08-30 10:27:06
Author: jofaber
Date: 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
New Revision: 55874
URL: http://svn.boost.org/trac/boost/changeset/55874
Log:
Diverse changes at Havingsblick. Added inclusion_compare, intersects, completed and
bugfixed T::contains. Added function documentation. Stable {msvc-9.0}
Added:
sandbox/itl/boost/validate/laws/minor_set_laws.hpp (contents, props changed)
Text files modified:
sandbox/itl/boost/itl/detail/element_comparer.hpp | 6
sandbox/itl/boost/itl/detail/subset_comparer.hpp | 240 ++++++-----------
sandbox/itl/boost/itl/functions.hpp | 55 ++++
sandbox/itl/boost/itl/interval.hpp | 2
sandbox/itl/boost/itl/interval_base_map.hpp | 127 ++++++++-
sandbox/itl/boost/itl/interval_base_set.hpp | 23 +
sandbox/itl/boost/itl/interval_map.hpp | 15 -
sandbox/itl/boost/itl/interval_map_algo.hpp | 133 ----------
sandbox/itl/boost/itl/interval_set.hpp | 51 +--
sandbox/itl/boost/itl/interval_set_algo.hpp | 67 ++++
sandbox/itl/boost/itl/map.hpp | 266 +++++++++++++++++--
sandbox/itl/boost/itl/map_algo.hpp | 520 +++++++++++++++++++++++++++++----------
sandbox/itl/boost/itl/predicates.hpp | 2
sandbox/itl/boost/itl/separate_interval_set.hpp | 35 +-
sandbox/itl/boost/itl/set.hpp | 63 ++++
sandbox/itl/boost/itl/split_interval_map.hpp | 14 -
sandbox/itl/boost/itl/split_interval_set.hpp | 25 -
sandbox/itl/boost/itl/type_traits/is_combinable.hpp | 32 --
sandbox/itl/boost/itl/type_traits/is_interval_container.hpp | 17 +
sandbox/itl/libs/itl/doc/functions.qbk | 228 +++++++++++++++++
sandbox/itl/libs/itl/doc/functions_addition.qbk | 93 -------
sandbox/itl/libs/itl/doc/functions_cons_copy_dest.qbk | 79 +++++
sandbox/itl/libs/itl/doc/functions_containedness.qbk | 99 +++++++
sandbox/itl/libs/itl/doc/functions_insertion.qbk | 2
sandbox/itl/libs/itl/doc/implementation.qbk | 200 ++++++++------
sandbox/itl/libs/itl/doc/interface.qbk | 5
sandbox/itl/libs/itl/doc/itl.qbk | 15 +
sandbox/itl/libs/itl/test/fastest_interval_map_cases.hpp | 9
sandbox/itl/libs/itl/test/fastest_interval_map_mixed_/fastest_interval_map_mixed.cpp | 9
sandbox/itl/libs/itl/test/fastest_itl_map_/fastest_itl_map_cases.hpp | 4
sandbox/itl/libs/itl/test/test_casual_/test_casual.cpp | 53 ++++
sandbox/itl/libs/itl/test/test_interval_map_cases.hpp | 8
sandbox/itl/libs/itl/test/test_interval_map_mixed.hpp | 243 ++++++++++++++++++
sandbox/itl/libs/itl/test/test_interval_map_mixed_/test_interval_map_mixed.cpp | 218 ++--------------
sandbox/itl/libs/itl/test/test_interval_map_shared.hpp | 159 +++++++++--
sandbox/itl/libs/itl/test/test_itl_map.hpp | 80 +++++
sandbox/itl/libs/itl/test/test_itl_map_/test_itl_map_cases.hpp | 4
sandbox/itl/libs/validate/example/labat_single_/labat_single.cpp | 21 +
38 files changed, 2169 insertions(+), 1053 deletions(-)
Modified: sandbox/itl/boost/itl/detail/element_comparer.hpp
==============================================================================
--- sandbox/itl/boost/itl/detail/element_comparer.hpp (original)
+++ sandbox/itl/boost/itl/detail/element_comparer.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -27,9 +27,9 @@
typedef typename RightT::const_iterator RightIterT;
element_comparer(const LeftT& left,
- const RightT& right,
- const LeftIterT& left_end,
- const RightIterT& right_end)
+ const RightT& right,
+ const LeftIterT& left_end,
+ const RightIterT& right_end)
: _left(left), _right(right),
_left_end(left_end), _right_end(right_end),
_compare_codomain(false), _result(equal)
Modified: sandbox/itl/boost/itl/detail/subset_comparer.hpp
==============================================================================
--- sandbox/itl/boost/itl/detail/subset_comparer.hpp (original)
+++ sandbox/itl/boost/itl/detail/subset_comparer.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -17,9 +17,43 @@
namespace boost{namespace itl
{
-namespace Interval_Set
+namespace Set
{
+//------------------------------------------------------------------------------
+template<class LeftT, class RightT>
+struct settic_codomain_compare
+{
+ static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
+ {
+ return inclusion_compare( LeftT::codomain_value(left_),
+ RightT::codomain_value(right_));
+ }
+};
+
+template<class LeftT, class RightT>
+struct atomic_codomain_compare
+{
+ static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
+ {
+ if(LeftT::codomain_value(left_) == RightT::codomain_value(right_))
+ return inclusion::equal;
+ else
+ return inclusion::unrelated;
+ }
+};
+
+template<class LeftT, class RightT>
+struct empty_codomain_compare
+{
+ static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
+ {
+ return inclusion::equal;
+ }
+};
+
+
+//------------------------------------------------------------------------------
template<class LeftT, class RightT>
class subset_comparer
{
@@ -36,7 +70,7 @@
_compare_codomain(false), _result(equal)
{}
- enum{nextboth, nextleft, nextright, stop};
+ enum{nextboth, stop};
enum
{
@@ -53,192 +87,90 @@
int result()const{ return _result; }
- bool covalues_are_equal(LeftIterT& left, RightIterT& right)
+
+ int co_compare(LeftIterT& left, RightIterT& right)
{
- if(LeftT::codomain_value(left) == RightT::codomain_value(right))
- return true;
-
- _result = unrelated;
- return false;
+ using namespace boost::mpl;
+ typedef typename LeftT::codomain_type LeftCodomainT;
+ typedef typename RightT::codomain_type RightCodomainT;
+
+ return
+ if_<
+ bool_<is_concept_equivalent<is_element_map,LeftT,RightT>::value>,
+ if_<
+ bool_<is_concept_equivalent<is_set,LeftCodomainT,
+ RightCodomainT>::value>,
+ settic_codomain_compare<LeftT,RightT>, // codomain is a set
+ atomic_codomain_compare<LeftT,RightT> // codomain is not a set
+ >::type,
+ empty_codomain_compare<LeftT,RightT> // no codomain component exits
+ >
+ ::type::apply(left,right);
}
int restrict_result(int state) { return _result &= state; }
- int proceed(LeftIterT& left, RightIterT& right)
- {
- if(LeftT::key_value(left).upper_less(RightT::key_value(right)))
- { // left ..)
- // right .....)
- _prior_left = left;
- ++left;
- return nextleft;
- }
- else if(RightT::key_value(right).upper_less(LeftT::key_value(left)))
- { // left .....)
- // right ..)
- _prior_right = right;
- ++right;
- return nextright;
- }
- else//LeftT::key_value(left).upper_equal(RightT::key_value(right))
- { // left ..)
- // right ..)
- ++left;
- ++right;
- return nextboth;
- }
- }
-
int next_both(LeftIterT& left, RightIterT& right)
{
if(left == _left_end && right == _right_end)
return stop;
else if(left == _left_end)
- { // left: ....end left could be subset
- // right:....[..
+ {
restrict_result(subset);
return stop;
}
else if(right == _right_end)
- { // left: ....[.. left could be superset
- // right:....end
+ {
restrict_result(superset);
return stop;
}
- else if(LeftT::key_value(left).exclusive_less(RightT::key_value(right)))
- { // left: [..) . . .[---) left could be superset
- // right: [..).... if [---) exists
+ else if(LeftT::domain_compare()(LeftT::key_value(left), RightT::key_value(right)))
+ { // left: *left . . *joint_ left could be superset
+ // right: *right ... if joint_ exists
restrict_result(superset);
if(unrelated == _result)
return stop;
else
{
LeftIterT joint_ = _left.lower_bound(RightT::key_value(right));
- if(joint_ == _left.end())
+ if( joint_ == _left.end()
+ || LeftT::domain_compare()(RightT::key_value(right), LeftT::key_value(joint_)))
{
_result = unrelated;
return stop;
}
else
- {
left = joint_;
- return nextboth;
- }
}
}
- else if(RightT::key_value(right).exclusive_less(LeftT::key_value(left)))
- { // left: [.. left could be subset
- // right:....) . . .[---) if [---) exists
+ else if(LeftT::domain_compare()(RightT::key_value(right), LeftT::key_value(left)))
+ { // left: *left left could be subset
+ // right:*right . . .*joint_ if *joint_ exists
restrict_result(subset);
if(unrelated == _result)
return stop;
else
{
RightIterT joint_ = _right.lower_bound(LeftT::key_value(left));
- if(joint_ == _right.end())
+ if( joint_ == _right.end()
+ || LeftT::domain_compare()(LeftT::key_value(left), RightT::key_value(joint_)))
{
_result = unrelated;
return stop;
}
else
- {
right = joint_;
- return nextboth;
- }
}
}
- // left and right have intervals with nonempty intersection:
- if(compare_codomain() && !covalues_are_equal(left, right))
- return stop;
-
- // examine left borders only. Right borders are checked in proceed
- if(LeftT::key_value(left).lower_less(RightT::key_value(right)))
- { // left: ....[... left could be superset
- // right:.... [..
- if(unrelated == restrict_result(superset))
- return stop;
- }
- else if(LeftT::key_value(right).lower_less(RightT::key_value(left)))
- { // left: .... [.. left can be subset
- // right:....[...
- if(unrelated == restrict_result(subset))
- return stop;
- }
- //else LeftT::key_value(right).lower_equal(RightT::key_value(left))
- // left: ....[.. both can be equal
- // right:....[..
- // nothing to do: proceed
-
- return proceed(left, right);
- }
-
- int next_left(LeftIterT& left, RightIterT& right)
- {
- if(left == _left_end)
- { // left: ..)end left could be subset
- // right:......)
- restrict_result(subset);
- return stop;
- }
- else if(!LeftT::key_value(_prior_left).touches(LeftT::key_value(left)))
- { // left: ..) [..
- // right:.........)
- if(RightT::key_value(right).lower_less(LeftT::key_value(left)))
- { // ..) [.. left could be subset
- // ..........)
- if(unrelated == restrict_result(subset))
- return stop;
- }
- //else ..) [...
- // [..
- if(compare_codomain() && !LeftT::key_value(left).is_disjoint(RightT::key_value(right))
- && !covalues_are_equal(left, right))
- return stop;
- }
- else
- { // left: ..)[.. left could be subset
- // right:.......)
- if(compare_codomain() && !LeftT::key_value(left).is_disjoint(RightT::key_value(right))
- && !covalues_are_equal(left, right))
- return stop;
- }
-
- return proceed(left, right);
- }
-
-
- int next_right(LeftIterT& left, RightIterT& right)
- {
- if(right == _right_end)
- { // left: ......) left could be superset
- // right:..)end
- restrict_result(superset);
- return stop;
- }
- else if(!RightT::key_value(_prior_right).touches(RightT::key_value(right)))
- { // left: .........)
- // right:..) [..
- if(LeftT::key_value(left).lower_less(RightT::key_value(right)))
- { // [....) left could be superset
- // ..) [..
- if(unrelated == restrict_result(superset))
- return stop;
- }
- //else [....)
- // ..) [..
- if(compare_codomain() && !LeftT::key_value(left).is_disjoint(RightT::key_value(right))
- && !covalues_are_equal(left, right))
- return stop;
- }
- else
- {
- if(compare_codomain() && !LeftT::key_value(left).is_disjoint(RightT::key_value(right))
- && !covalues_are_equal(left, right))
- return stop;
- }
-
- return proceed(left, right);
+ // left =key= right
+ if(compare_codomain())
+ if(unrelated == restrict_result(co_compare(left,right)))
+ return stop;
+
+ ++left;
+ ++right;
+ return nextboth;
}
private:
@@ -247,8 +179,6 @@
LeftIterT _left_end;
RightIterT _right_end;
bool _compare_codomain;
- LeftIterT _prior_left;
- RightIterT _prior_right;
int _result;
};
@@ -279,18 +209,24 @@
int state = Step::nextboth;
while(state != Step::stop)
- {
- switch(state){
- case Step::nextboth: state = step.next_both(left_, right_); break;
- case Step::nextleft: state = step.next_left(left_, right_); break;
- case Step::nextright: state = step.next_right(left_, right_); break;
- }
- }
+ state = step.next_both(left_, right_);
+
return step.result();
}
+template<class LeftT, class RightT>
+int subset_compare(const LeftT& left, const RightT& right)
+{
+ return subset_compare
+ (
+ left, right,
+ left.begin(), left.end(),
+ right.begin(), right.end()
+ );
+}
+
-} // namespace Interval_Set
+} // namespace Set
}} // namespace itl boost
Modified: sandbox/itl/boost/itl/functions.hpp
==============================================================================
--- sandbox/itl/boost/itl/functions.hpp (original)
+++ sandbox/itl/boost/itl/functions.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -9,6 +9,7 @@
#define __itl_functions_JOFA_090803_H__
#include <boost/utility/enable_if.hpp>
+#include <boost/itl/type_traits/is_element_container.hpp>
#include <boost/itl/type_traits/is_combinable.hpp>
namespace boost{namespace itl
@@ -49,6 +50,29 @@
return Interval_Set::is_element_greater(left, right);
}
+//------------------------------------------------------------------------------
+template<class LeftT, class RightT>
+typename boost::enable_if<is_inter_combinable<LeftT, RightT>,
+ int>::type
+inclusion_compare(const LeftT& left, const RightT& right)
+{
+ return Interval_Set::subset_compare(left, right,
+ left.begin(), left.end(),
+ right.begin(), right.end());
+}
+
+template<class LeftT, class RightT>
+typename boost::enable_if<is_concept_equivalent<is_element_container,LeftT, RightT>,
+ int>::type
+inclusion_compare(const LeftT& left, const RightT& right)
+{
+ return Set::subset_compare(left, right,
+ left.begin(), left.end(),
+ right.begin(), right.end());
+}
+//------------------------------------------------------------------------------
+
+
//==============================================================================
//= Addition
//==============================================================================
@@ -351,7 +375,34 @@
//- intersects
//------------------------------------------------------------------------------
template<class LeftT, class RightT>
-typename boost::enable_if<is_inter_combinable<LeftT, RightT>,
+typename boost::enable_if<is_intra_combinable<LeftT, RightT>,
+ bool>::type
+intersects(const LeftT& left, const RightT& right)
+{
+ if(is_total<LeftT>::value || is_total<RightT>::value)
+ return true;
+
+ LeftT intersection;
+
+ typename RightT::const_iterator right_common_lower_;
+ typename RightT::const_iterator right_common_upper_;
+
+ if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
+ return false;
+
+ typename RightT::const_iterator it_ = right_common_lower_;
+ while(it_ != right_common_upper_)
+ {
+ left.add_intersection(intersection, *it_++);
+ if(!intersection.empty())
+ return true;
+ }
+
+ return false;
+}
+
+template<class LeftT, class RightT>
+typename boost::enable_if<is_cross_combinable<LeftT, RightT>,
bool>::type
intersects(const LeftT& left, const RightT& right)
{
@@ -360,7 +411,7 @@
if(left.empty() || right.empty())
return false;
- typename RightT::const_iterator right_common_lower_;
+ typename RightT::const_iterator right_common_lower_;
typename RightT::const_iterator right_common_upper_;
if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
Modified: sandbox/itl/boost/itl/interval.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval.hpp (original)
+++ sandbox/itl/boost/itl/interval.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -130,7 +130,7 @@
//NOTE: Compiler generated assignment operator = used
//==========================================================================
- //= Emptieness, containment
+ //= Containedness
//==========================================================================
/** Is the interval empty? */
bool empty()const;
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-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -185,7 +185,7 @@
{ _map.assign_if(src._map, pred); return *this; }
//==========================================================================
- //= Emptieness, containment
+ //= Containedness
//==========================================================================
/** clear the map */
@@ -198,28 +198,59 @@
/** Does the map contain the domain element \c key? */
bool contains(const domain_type& key)const
{
- typename ImplMapT::const_iterator it_ = _map.find(interval_type(key));
- return it_ != _map.end();
+ return Traits::is_total || _map.find(interval_type(key)) != _map.end();
}
+ /** Does the map contain the interval \c sub_interval ? */
+ bool contains(const interval_type& sub_interval)const
+ {
+ if(Traits::is_total || sub_interval.empty())
+ return true;
+
+ std::pair<const_iterator, const_iterator> exterior = equal_range(sub_interval);
+ if(exterior.first == exterior.second)
+ return false;
+
+ const_iterator last_overlap = prior(exterior.second);
+
+ return
+ hull(exterior.first->KEY_VALUE, last_overlap->KEY_VALUE).contains(sub_interval)
+ && Interval_Set::is_dense(*this, exterior.first, last_overlap);
+ }
+
+ /** Does the map contain the key key set \c sub_set ? */
+ template<class SetType>
+ bool contains(const interval_base_set<SetType,DomainT,Compare,Interval,Alloc>& sub_set)const
+ {
+ if(Traits::is_total || sub_set.empty())
+ return true;
+
+ return Interval_Set::is_contained_in(sub_set, *this);
+ }
+
/** Does the map contain the <tt>key_value_pair = (key,value)</tt>? */
bool contains(const element_type& key_value_pair)const
{
- return that()->contains_(value_type(interval_type(key_value_pair.key),
- key_value_pair.data));
+ return contains(value_type(interval_type(key_value_pair.key),
+ key_value_pair.data));
}
/** Does the map contain all element value pairs represented by the
\c interval_value_pair ? */
- bool contains(const segment_type& interval_value_pair)const
- { return that()->contains_(interval_value_pair); }
+ bool contains(const segment_type& interval_value_pair)const;
/** Does <tt>*this</tt> container contain <tt>sub</tt>? */
- bool contains(const interval_base_map& sub)const
- { return sub.contained_in(*this); }
+ template<class MapType>
+ bool contains(const interval_base_map<MapType,DomainT,CodomainT,Traits,
+ Compare,Combine,Section,Interval,Alloc>& sub)const
+ {
+ return sub.contained_in(*this);
+ }
/** <tt>*this</tt> is subset of <tt>super</tt>? */
- bool contained_in(const interval_base_map& super)const
+ template<class MapType>
+ bool contained_in(const interval_base_map<MapType,DomainT,CodomainT,Traits,
+ Compare,Combine,Section,Interval,Alloc>& super)const
{
return Interval_Set::is_contained_in(*this, super);
}
@@ -478,7 +509,8 @@
)const
{
typedef IntervalSet<DomainT,Compare,Interval,Alloc> sectant_type;
- if(sectant.empty()) return;
+ if(sectant.empty())
+ return;
typename sectant_type::const_iterator common_lwb;
typename sectant_type::const_iterator common_upb;
@@ -512,28 +544,37 @@
/** Returns \c true, if element \c key is found in \c *this map.
Complexity: logarithmic. */
bool intersects(const domain_type& key)const
- { return _map.find(interval_type(key)) != _map.end(); }
+ {
+ return contains(key);
+ }
/** Returns \c true, if \c inter_val intersects with \c *this map.
- Complexity: logarithmic. */
+ Complexity: Logarithmic in iterative size. */
bool intersects(const interval_type& inter_val)const
- { return _map.find(inter_val) != _map.end(); }
+ {
+ if(Traits::is_total)
+ return true;
+ std::pair<const_iterator,const_iterator> overlap = equal_range(inter_val);
+ return overlap.first == overlap.second;
+ }
/** Returns \c true, if \c key_value_pair is found in \c *this map.
Complexity: logarithmic. */
bool intersects(const element_type& key_value_pair)const
{
- const_iterator found_ = _map.find(interval_type(key_value_pair.key));
- return found_ != _map.end() && found_->KEY_VALUE == key_value_pair.data;
+ return intersects(segment_type(interval_type(key_value_pair.key), key_value_pair.data));
}
/** Returns \c true, if \c interval_value_pair intersects with \c *this map:
- Complexity: logarithmic. */
+ Complexity: Linear in iterative_size. */
bool intersects(const segment_type& interval_value_pair)const
{
- type intersection;
- add(intersection, interval_value_pair);
- return !intersection.empty();
+ if(traits::is_total)
+ return true;
+
+ type intersection;
+ add_intersection(intersection, interval_value_pair);
+ return !intersection.empty();
}
@@ -661,7 +702,8 @@
static codomain_type codomain_value(IteratorT value_){ return (*value_).second; }
template<typename LeftIterT, typename RightIterT>
- static bool key_less(LeftIterT lhs_, RightIterT rhs_) { return key_compare()((*lhs_).first, (*rhs_).first); }
+ static bool key_less(LeftIterT left_, RightIterT right_)
+ { return key_compare()((*left_).first, (*right_).first); }
static value_type make_domain_element(const domain_type& dom_val, const codomain_type& codom_val)
{ return value_type(interval_type(dom_val), codom_val); }
@@ -678,6 +720,9 @@
iterator prior(iterator it_)
{ return it_ == this->_map.begin() ? this->_map.end() : --it_; }
+ const_iterator prior(const_iterator it_)const
+ { return it_ == this->_map.begin() ? this->_map.end() : --it_; }
+
template <class Combiner>
bool combine(iterator& it_, const codomain_type& co_val)
{
@@ -740,6 +785,43 @@
+//==============================================================================
+//= Containedness
+//==============================================================================
+
+template
+<
+ 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
+>
+bool interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::contains(const typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
+ ::segment_type& sub_segment)const
+{
+ interval_type sub_interval = sub_segment.KEY_VALUE;
+ if(sub_interval.empty())
+ return true;
+
+ std::pair<const_iterator, const_iterator> exterior = equal_range(sub_interval);
+ if(exterior.first == exterior.second)
+ return false;
+
+ const_iterator last_overlap = prior(exterior.second);
+
+ if(!(sub_segment.CONT_VALUE == exterior.first->CONT_VALUE) )
+ return false;
+
+ return
+ hull(exterior.first->KEY_VALUE, last_overlap->KEY_VALUE).contains(sub_interval)
+ && Interval_Set::is_joinable(*this, exterior.first, last_overlap);
+}
+
+
+
+//==============================================================================
+//= Size
+//==============================================================================
+
template
<
class SubType, class DomainT, class CodomainT, class Traits,
@@ -889,7 +971,8 @@
const typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
::interval_type& sectant_interval)const
{
- if(sectant_interval.empty()) return;
+ if(sectant_interval.empty())
+ return;
typename ImplMapT::const_iterator first_ = _map.lower_bound(sectant_interval);
typename ImplMapT::const_iterator end_ = _map.upper_bound(sectant_interval);
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-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -139,7 +139,7 @@
void swap(interval_base_set& x) { _set.swap(x._set); }
//==========================================================================
- //= Emptieness, containment
+ //= Containedness
//==========================================================================
/** sets the container empty */
@@ -149,11 +149,21 @@
/** Does the container contain the element \c key ? */
bool contains(const element_type& key)const
- { return that()->contains_(interval_type(key)); }
+ { return that()->contains(interval_type(key)); }
+
+ /** Does the container contain the interval \c sub_interval ? */
+ bool contains(const segment_type& sub_interval)const
+ {
+ if(sub_interval.empty())
+ return true;
+
+ std::pair<const_iterator, const_iterator> exterior = equal_range(sub_interval);
+ if(exterior.first == exterior.second)
+ return false;
+
+ return Interval_Set::is_joinable(*this, exterior.first, exterior.second);
+ }
- /** Does the container contain the interval \c inter_val ? */
- bool contains(const segment_type& inter_val)const
- { return that()->contains_(inter_val); }
/** Does the container contain the subcontainer \c sub ? */
bool contains(const interval_base_set& sub)const
@@ -428,6 +438,9 @@
iterator prior(iterator it_)
{ return it_ == this->_set.begin() ? this->_set.end() : --it_; }
+ const_iterator prior(const_iterator it_)const
+ { return it_ == this->_map.begin() ? this->_map.end() : --it_; }
+
iterator gap_insert(iterator prior_, const interval_type& inter_val)
{
// inter_val is not conained in this map. Insertion will be successful
Modified: sandbox/itl/boost/itl/interval_map.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_map.hpp (original)
+++ sandbox/itl/boost/itl/interval_map.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -172,21 +172,6 @@
} ;
-
-template <typename DomainT, typename CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-bool interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::contains_(const value_type& interv_value)const
-{
- interval_type interv = interv_value.KEY_VALUE;
- if(interv.empty())
- return true;
-
- type section;
- add_intersection(section, interv);
- return is_element_equal(section, type(interv_value));
-}
-
-
template <typename DomainT, typename CodomainT, class Traits,
ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
inline bool interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Modified: sandbox/itl/boost/itl/interval_map_algo.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_map_algo.hpp (original)
+++ sandbox/itl/boost/itl/interval_map_algo.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -11,138 +11,7 @@
#include <boost/itl/detail/notate.hpp>
#include <boost/itl/type_traits/neutron.hpp>
-namespace boost{namespace itl
-{
-
-namespace Map
-{
-
-template<class LeftT, class RightT>
-class interval_map_sequence_tracker
-{
-public:
- typedef typename LeftT::const_iterator LeftIterT;
- typedef typename RightT::const_iterator RightIterT;
-
- interval_map_sequence_tracker(const LeftT& left,
- const RightT& right)
- : _left(left), _right(right), _result(false)
- {}
-
- enum{nextboth, nextleft, nextright, leftaligned, stop};
-
- bool result()const{ return _result; }
-
- int proceed(LeftIterT& left, RightIterT& right)
- {
- if(LeftT::key_value(left).upper_equal(RightT::key_value(right)))
- {
- ++left;
- ++right;
- return nextboth;
- }
- else if(LeftT::key_value(left).upper_less(RightT::key_value(right)))
- {
- _prior_left = left;
- ++left;
- return nextleft;
- }
- else
- {
- _prior_right = right;
- ++right;
- return nextright;
- }
- }
-
- int next_both(LeftIterT& left, RightIterT& right)
- {
- if(left == _left.end())
- {
- _result = (right == _right.end()) ? true : false;
- return stop;
- }
-
- // left != _left.end()
- if(right == _right.end())
- return stop; //_result = false;
-
- // The starting intervals have to begin equally
- if(!LeftT::key_value(left).lower_equal(RightT::key_value(right)))
- return stop; //_result = false;
-
- if(!(LeftT::data_value(left) == RightT::data_value(right)))
- return stop; //_result = false;
-
- return leftaligned;
- }
-
- int next_left(LeftIterT& left, RightIterT& right)
- {
- if(left == _left.end())
- return stop;
-
- if(!LeftT::key_value(_prior_left).touches(LeftT::key_value(left)))
- return stop; //_result = false;
-
- if(!(LeftT::data_value(left) == RightT::data_value(right)))
- return stop; //_result = false;
-
- return proceed(left, right);
- }
-
- int next_right(LeftIterT& left, RightIterT& right)
- {
- if(right == _right.end())
- return stop;
-
- if(!RightT::key_value(_prior_right).touches(RightT::key_value(right)))
- return stop; //_result = false;
-
- if(!(LeftT::data_value(left) == RightT::data_value(right)))
- return stop; //_result = false;
-
- return proceed(left, right);
- }
-
-private:
- const LeftT& _left;
- const RightT& _right;
- LeftIterT _prior_left;
- RightIterT _prior_right;
- bool _result;
-};
-
-template<class LeftT, class RightT>
-bool is_element_equal(const LeftT& left, const RightT& right)
-{
- if(left.empty())
- return right.empty();
- else if(right.empty())
- return false;
-
- typedef interval_map_sequence_tracker<LeftT,RightT> Step;
- Step step(left, right);
-
- typename LeftT::const_iterator left_ = left.begin();
- typename RightT::const_iterator right_ = right.begin();
-
- int state = Step::nextboth;
- while(state != Step::stop)
- {
- switch(state){
- case Step::nextboth: state = step.next_both(left_, right_); break;
- case Step::nextleft: state = step.next_left(left_, right_); break;
- case Step::nextright: state = step.next_right(left_, right_); break;
- case Step::leftaligned: state = step.proceed(left_, right_); break;
- }
- }
- return step.result();
-}
-
-} //Map
-
-}} // namespace itl boost
+//CL complete
#endif
Modified: sandbox/itl/boost/itl/interval_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_set.hpp (original)
+++ sandbox/itl/boost/itl/interval_set.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -98,20 +98,27 @@
template<class SubType>
explicit interval_set
(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
- { assign(src); }
+ {
+ assign(src);
+ }
/// Constructor for a single element
explicit interval_set(const domain_type& value): base_type()
{ add(interval_type(value)); }
/// Constructor for a single interval
explicit interval_set(const interval_type& itv): base_type()
- { add(itv); }
+ {
+ add(itv);
+ }
/// Assignment operator
template<class SubType>
interval_set& operator =
(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
- { assign(src); return *this; }
+ {
+ assign(src);
+ return *this;
+ }
/// Assignment from a base interval_set.
@@ -131,16 +138,16 @@
interval_base_set<interval_set<DomainT,Compare,Interval,Alloc>,
DomainT,Compare,Interval,Alloc>;
- /// Does the set contain the interval <tt>x</tt>?
- bool contains_(const interval_type& x)const;
+ /// Does the set contain the interval <tt>sub</tt>?
+ bool contains_(const interval_type& sub)const;
- /// Insertion of an interval <tt>x</tt>
- void add_(const value_type& x);
+ /// Insertion of an interval <tt>addend</tt>
+ void add_(const value_type& addend);
- iterator add_(iterator prior_, const value_type& x);
+ iterator add_(iterator prior_, const value_type& addend);
- /// Removal of an interval <tt>x</tt>
- void subtract_(const value_type& x);
+ /// Removal of an interval <tt>minuend</tt>
+ void subtract_(const value_type& minuend);
private:
/// Treatment of adjoint intervals on insertion
@@ -150,30 +157,6 @@
} ;
-
-
-template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-bool interval_set<DomainT,Compare,Interval,Alloc>::contains_(const interval_type& x)const
-{
- // Emptiness is contained in everything
- if(x.empty())
- return true;
- else if (this->empty())
- return false;
- else if(x.upper() < this->lower())
- return false;
- else if(this->upper() < x.lower())
- return false;
- {
- typename ImplSetT::const_iterator it_ = this->_set.find(x);
- if(it_ == this->_set.end())
- return false;
- else
- return x.contained_in(*it_);
- }
-}
-
-
template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
inline typename interval_set<DomainT,Compare,Interval,Alloc>::iterator
interval_set<DomainT,Compare,Interval,Alloc>::handle_neighbours(iterator it_)
Modified: sandbox/itl/boost/itl/interval_set_algo.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_set_algo.hpp (original)
+++ sandbox/itl/boost/itl/interval_set_algo.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -14,7 +14,7 @@
#include <boost/itl/type_traits/neutron.hpp>
#include <boost/itl/interval.hpp>
#include <boost/itl/detail/element_comparer.hpp>
-#include <boost/itl/detail/subset_comparer.hpp>
+#include <boost/itl/detail/interval_subset_comparer.hpp>
namespace boost{namespace itl
{
@@ -123,31 +123,80 @@
}
template<class LeftT, class RightT>
-bool is_contained_in(const LeftT& left, const RightT& right)
+bool is_contained_in(const LeftT& sub, const RightT& super)
{
int result =
subset_compare
(
- left, right,
- left.begin(), left.end(),
- right.begin(), right.end()
+ sub, super,
+ sub.begin(), sub.end(),
+ super.begin(), super.end()
);
return result == inclusion::subset || result == inclusion::equal;
}
template<class LeftT, class RightT>
-bool contains(const LeftT& left, const RightT& right)
+bool contains(const LeftT& super, const RightT& sub)
{
int result =
subset_compare
(
- left, right,
- left.begin(), left.end(),
- right.begin(), right.end()
+ super, sub,
+ super.begin(), super.end(),
+ sub.begin(), sub.end()
);
return result == inclusion::superset || result == inclusion::equal;
}
+template<class IntervalContainerT>
+bool is_joinable(const IntervalContainerT& container,
+ typename IntervalContainerT::const_iterator first,
+ typename IntervalContainerT::const_iterator past)
+{
+ if(first == container.end())
+ return true;
+
+ typename IntervalContainerT::const_iterator it_ = first, next_ = first;
+ ++next_;
+
+ if(is_interval_map<IntervalContainerT>::value)
+ {
+ const typename IntervalContainerT::codomain_type& co_value
+ = IntervalContainerT::codomain_value(first);
+ while(it_ != past)
+ {
+ if(IntervalContainerT::codomain_value(next_) != co_value)
+ return false;
+ if(!IntervalContainerT::key_value(it_++).touches(IntervalContainerT::key_value(next_++)))
+ return false;
+ }
+ }
+ else
+ while(next_ != container.end() && it_ != past)
+ if(!IntervalContainerT::key_value(it_++).touches(IntervalContainerT::key_value(next_++)))
+ return false;
+
+ return true;
+}
+
+template<class IntervalContainerT>
+bool is_dense(const IntervalContainerT& container,
+ typename IntervalContainerT::const_iterator first,
+ typename IntervalContainerT::const_iterator past)
+{
+ if(first == container.end())
+ return true;
+
+ typename IntervalContainerT::const_iterator it_ = first, next_ = first;
+ ++next_;
+
+ while(next_ != container.end() && it_ != past)
+ if(!IntervalContainerT::key_value(it_++).touches(IntervalContainerT::key_value(next_++)))
+ return false;
+
+ return true;
+}
+
} // namespace Interval_Set
}} // namespace itl boost
Modified: sandbox/itl/boost/itl/map.hpp
==============================================================================
--- sandbox/itl/boost/itl/map.hpp (original)
+++ sandbox/itl/boost/itl/map.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -83,7 +83,7 @@
typedef typename itl::map<DomainT,CodomainT,Traits, Compare,Combine,Section,Alloc> type;
typedef typename std::map<DomainT, CodomainT, ITL_COMPARE_DOMAIN(Compare,DomainT),
allocator_type> base_type;
- typedef typename itl::set<DomainT, Compare, Alloc > set_type;
+ typedef typename itl::set<DomainT, Compare, Alloc > set_type;
typedef Traits traits;
@@ -125,10 +125,10 @@
map(const key_compare& comp): base_type(comp){}
template <class InputIterator>
- map(InputIterator f, InputIterator l): base_type(f,l) {}
+ map(InputIterator first, InputIterator past): base_type(first,past) {}
template <class InputIterator>
- map(InputIterator f, InputIterator l, const key_compare& comp): base_type(f,l,comp) {}
+ map(InputIterator first, InputIterator past, const key_compare& comp): base_type(first,past,comp) {}
map(const map& src): base_type::map(src){}
@@ -169,11 +169,18 @@
public:
//==========================================================================
- //= Emptieness, containment
+ //= Containedness
//==========================================================================
- /** Checks if a key element is in the map */
- bool contains(const DomainT& x)const { return !(find(x) == end()); }
+ /** Checks if a key is in the map */
+ bool contains(const domain_type& key)const { return !(find(key) == end()); }
+
+ /** Checks if a key-value pair is in the map */
+ bool contains(const element_type& key_value_pair)const
+ {
+ const_iterator found_ = find(key_value_pair.first);
+ return found_ != end() && found_->second == key_value_pair.second;
+ }
/** Is <tt>*this</tt> contained in <tt>super</tt>? */
bool contained_in(const map& super)const
@@ -193,13 +200,6 @@
size_t cardinality()const { return size(); }
- std::pair<iterator,bool> insert(const value_type& value_pair)
- {
- if(Traits::absorbs_neutrons && value_pair.CONT_VALUE == codomain_combine::neutron())
- return std::pair<iterator,bool>(end(),true);
- else
- return base_type::insert(value_pair);
- }
//==========================================================================
//= Selection
//==========================================================================
@@ -242,13 +242,21 @@
//= Insertion, erasure
//==========================================================================
+ std::pair<iterator,bool> insert(const value_type& value_pair)
+ {
+ if(Traits::absorbs_neutrons && value_pair.CONT_VALUE == codomain_combine::neutron())
+ return std::pair<iterator,bool>(end(),true);
+ else
+ return base_type::insert(value_pair);
+ }
+
/** With <tt>key_value_pair = (k,v)</tt> set value \c v for key \c k */
map& set(const element_type& key_value_pair)
{ (*this)[key_value_pair.KEY_VALUE] = key_value_pair.CONT_VALUE; return *this; }
- /** erase the value pair \c pair(key,val) from the map.
- Erase only if, the exact value content \c val is stored at key \key. */
- size_type erase(const value_type& value);
+ /** erase \c key_value_pair from the map.
+ Erase only if, the exact value content \c val is stored for the given key. */
+ size_type erase(const element_type& key_value_pair);
//==========================================================================
//= Intersection
@@ -266,6 +274,17 @@
/** The intersection of map \c sectant with \c *this map is added to \c section. */
void add_intersection(map& section, const map& sectant)const;
+ /** Returns true, if there is an intersection of \c key and \c *this map.
+ Functions \c intersects and \c contains are identical on key value arguments
+ of type \c domain_type. Complexity: Logarithmic in container size. */
+ bool intersects(const domain_type& key)const;
+
+ /** Returns true, if there is an intersection of \key_value_pair and \c *this map.
+ If the key is found, the content of \c key_value_pair has to have an intersection
+ with the content of the data value in the map.
+ Complexity: Logarithmic in container size. */
+ bool intersects(const element_type& key_value_pair)const;
+
//==========================================================================
//= Symmetric difference
//==========================================================================
@@ -307,6 +326,11 @@
template<typename IteratorT>
static const data_type& data_value(IteratorT value_){ return (*value_).second; }
+ /** \c codomain_value allows for a uniform access to \c codomain_values which is
+ is used for common algorithms on sets and maps. */
+ template<typename IteratorT>
+ static const codomain_type& codomain_value(IteratorT value_){ return (*value_).second; }
+
/** \c key_less allows for a uniform notation of key comparison which
is used for common algorithms on sets and maps. */
template<typename LeftIterT, typename RightIterT>
@@ -329,6 +353,14 @@
template<class Predicate>
map& assign_if(const map& src, const Predicate&);
+ /** Copy the key values of the map to \c domain_set. Complexity: Linear. */
+ void domain(set_type& domain_set)const
+ {
+ set_type::iterator prior_ = domain_set.end();
+ const_FORALL_THIS(it_)
+ prior_ = domain_set.insert(prior_, it_->KEY_VALUE);
+ }
+
private:
template<class Combiner>
map& add(const value_type& value_pair);
@@ -341,6 +373,10 @@
};
+//==============================================================================
+//= Addition
+//==============================================================================
+
template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
template <class Combiner>
map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>&
@@ -395,7 +431,29 @@
}
+//==============================================================================
+//= Subtraction
+//==============================================================================
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+ template <class Combiner>
+map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>&
+ map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::subtract(const value_type& val)
+{
+ iterator it_ = find(val.KEY_VALUE);
+ if(it_ != end())
+ {
+ Combiner()((*it_).CONT_VALUE, val.CONT_VALUE);
+ if(Traits::absorbs_neutrons && (*it_).CONT_VALUE == codomain_combine::neutron())
+ erase(it_);
+ }
+ return *this;
+}
+
+
+//==============================================================================
+//= Erasure
+//==============================================================================
template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
typename map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::size_type
map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>
@@ -416,20 +474,9 @@
}
-template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
- template <class Combiner>
-map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>&
- map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::subtract(const value_type& val)
-{
- iterator it_ = find(val.KEY_VALUE);
- if(it_ != end())
- {
- Combiner()((*it_).CONT_VALUE, val.CONT_VALUE);
- if(Traits::absorbs_neutrons && (*it_).CONT_VALUE == codomain_combine::neutron())
- erase(it_);
- }
- return *this;
-}
+//==============================================================================
+//= Intersection
+//==============================================================================
template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
void map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>
@@ -446,7 +493,7 @@
if(it_ != end())
{
section.add(*it_);
- if(is_set<CodomainT>::value)
+ if(is_set<codomain_type>::value)
section.template add<codomain_intersect>(sectant);
else
section.template add<codomain_combine>(sectant);
@@ -505,8 +552,34 @@
}
}
+//------------------------------------------------------------------------------
+//- intersects
+//------------------------------------------------------------------------------
+
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+inline bool map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>
+ ::intersects(const domain_type& key)const
+{
+ return traits::is_total || contains(key);
+}
template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+inline bool map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>
+ ::intersects(const element_type& key_value_pair)const
+{
+ if(traits::is_total)
+ return true;
+
+ type intersection;
+ add_intersection(intersection, key_value_pair);
+ return !intersection.empty();
+}
+
+
+//==============================================================================
+//= Conversion
+//==============================================================================
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
std::string map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::as_string()const
{
std::string repr;
@@ -579,6 +652,20 @@
return object;
}
+template <class DomainT, class CodomainT, class Traits,
+ ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>&
+ erase(map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& object,
+ const set<DomainT,Compare,Alloc>& erasure)
+{
+ typedef set<DomainT,Compare,Alloc> operand_type;
+
+ const_FORALL(typename operand_type, elem_, erasure)
+ object.erase(*elem_);
+
+ return object;
+}
+
//-----------------------------------------------------------------------------
// non member functions
@@ -643,7 +730,11 @@
const itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& rhs)
{ return !(lhs < rhs); }
-//--------------------------------------------------------------------------
+//------------------------------------------------------------------------------
+//==============================================================================
+//= Addition
+//==============================================================================
+
template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
inline itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>&
operator += ( itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& object,
@@ -731,7 +822,9 @@
}
-//--------------------------------------------------------------------------
+//==============================================================================
+//= Subtraction
+//==============================================================================
/** Subtract a map \c x2 from this map. If an element of \c x2 already exists
in \c *this, subtract the contents using <tt>operator -=</tt>. */
@@ -775,6 +868,10 @@
}
+//==============================================================================
+//= Intersection
+//==============================================================================
+
/** Intersect map \c x2 and \c *this.
So \c *this becomes the intersection of \c *this and \c x2 */
template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
@@ -782,8 +879,9 @@
operator &= ( itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& object,
const itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& operand)
{
- typedef typename itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> object_type;
- if(Traits::is_total) return object += operand;
+ typedef itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> object_type;
+ if(Traits::is_total)
+ return object += operand;
else
{
object_type section;
@@ -808,8 +906,11 @@
operator &= ( itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& object,
const typename itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::set_type& operand)
{
- Map::intersect(object, operand);
- return object;
+ typedef itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> object_type;
+ object_type section;
+ object.add_intersection(section, operand);
+ object.swap(section);
+ return object;
}
@@ -829,7 +930,97 @@
return object &= operand;
}
+//------------------------------------------------------------------------------
+//- intersects
+//------------------------------------------------------------------------------
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+bool intersects(const map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& object,
+ const typename map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::domain_type& key)
+{
+ return object.intersects(key);
+}
+
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+bool intersects(
+ const typename map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::domain_type& key,
+ const map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& object)
+{
+ return object.intersects(key);
+}
+
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+bool intersects(const map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& object,
+ const typename map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::element_type& key_value_pair)
+{
+ return object.intersects(key_value_pair);
+}
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+bool intersects(
+ const typename map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::element_type& key_value_pair,
+ const map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& object)
+{
+ return object.intersects(key_value_pair);
+}
+
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+bool intersects(const map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& left,
+ const typename map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::set_type& right)
+{
+ typedef map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> MapT;
+ if(is_total<MapT>::value)
+ return true;
+
+ if(left.iterative_size() < right.iterative_size())
+ return Map::key_intersects(right, left);
+ else
+ return Map::key_intersects(left, right);
+}
+
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+bool intersects(
+ const typename map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::set_type& left,
+ const map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& right)
+{
+ typedef map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> MapT;
+ if(is_total<MapT>::value)
+ return true;
+
+ if(left.iterative_size() < right.iterative_size())
+ return Map::key_intersects(right, left);
+ else
+ return Map::key_intersects(left, right);
+}
+
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+bool intersects(const map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& left,
+ const map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>& right)
+{
+ typedef map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> MapT;
+ if(is_total<MapT>::value)
+ return true;
+
+ if(left.iterative_size() < right.iterative_size())
+ return Map::intersects(right, left);
+ else
+ return Map::intersects(left, right);
+}
+
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc,
+ class LeftT, class RightT>
+enable_if<mpl::or_<is_same< typename itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>, LeftT >,
+ is_same< typename itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>, RightT>
+ >, bool>
+is_disjoint(const LeftT& left, const RightT& right)
+{
+ return !intersects(left, right);
+}
+
+
+
+//==============================================================================
+//= Symmetric difference
+//==============================================================================
/** Symmetric subtract map \c x2 and \c *this.
So \c *this becomes the symmetric difference of \c *this and \c x2 */
@@ -866,7 +1057,6 @@
return stream << "}";
}
-
//-----------------------------------------------------------------------------
// type traits
//-----------------------------------------------------------------------------
Modified: sandbox/itl/boost/itl/map_algo.hpp
==============================================================================
--- sandbox/itl/boost/itl/map_algo.hpp (original)
+++ sandbox/itl/boost/itl/map_algo.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -13,186 +13,424 @@
namespace boost{namespace itl
{
- namespace Map
+namespace Map
+{
+
+template<class MapType>
+bool contained_in(const MapType& sub, const MapType& super)
+{
+ if(&super == &sub) return true;
+ if(sub.empty()) return true;
+ if(super.empty()) return false;
+ if(super.size() < sub.size() ) return false;
+ if(*sub.begin() < *super.begin()) return false;
+ if(*super.rbegin() < *sub.rbegin() ) return false;
+
+ typename MapType::const_iterator common_lwb_;
+ typename MapType::const_iterator common_upb_;
+ if(!Set::common_range(common_lwb_, common_upb_, sub, super))
+ return false;
+
+ typename MapType::const_iterator sub_ = sub.begin(), super_;
+ while(sub_ != sub.end())
{
- template<class MapType>
- bool contained_in(const MapType& sub, const MapType& super)
- {
- if(&super == &sub) return true;
- if(sub.empty()) return true;
- if(super.empty()) return false;
- if(super.size() < sub.size() ) return false;
- if(*sub.begin() < *super.begin()) return false;
- if(*super.rbegin() < *sub.rbegin() ) return false;
-
- typename MapType::const_iterator common_lwb_;
- typename MapType::const_iterator common_upb_;
- if(!Set::common_range(common_lwb_, common_upb_, sub, super))
- return false;
+ super_ = super.find((*sub_).KEY_VALUE);
+ if(super_ == super.end())
+ return false;
+ else if(!(sub_->CONT_VALUE == super_->CONT_VALUE))
+ return false;
+ sub_++;
+ }
+ return true;
+}
- typename MapType::const_iterator sub_ = sub.begin(), super_;
- while(sub_ != sub.end())
- {
- super_ = super.find((*sub_).KEY_VALUE);
- if(super_ == super.end())
- return false;
- else if(!(sub_->CONT_VALUE == super_->CONT_VALUE))
- return false;
- sub_++;
- }
- return true;
- }
+template<class MapType>
+bool contained_in(const typename MapType::set_type& sub, const MapType& super)
+{
+ typedef typename MapType::set_type SetType;
+
+ if(sub.empty()) return true;
+ if(super.empty()) return false;
+ if(super.size() < sub.size() ) return false;
+ if(*sub.begin() < *super.begin()) return false;
+ if(*super.rbegin() < *sub.rbegin() ) return false;
+
+ typename SetType::const_iterator common_lwb_;
+ typename SetType::const_iterator common_upb_;
+ if(!Set::common_range(common_lwb_, common_upb_, sub, super))
+ return false;
+
+ typename SetType::const_iterator sub_ = sub.begin();
+ typename MapType::const_iterator super_;
+ while(sub_ != sub.end())
+ {
+ super_ = super.find(*sub_++);
+ if(super_ == super.end())
+ return false;
+ }
+ return true;
+}
- template<class MapType>
- void intersect(MapType& result, const MapType& x1, const MapType& x2)
- {
- typename MapType::const_iterator common_lwb_;
- typename MapType::const_iterator common_upb_;
- result.clear();
- if(!Set::common_range(common_lwb_, common_upb_, x1, x2))
- return;
+template <class MapType>
+bool intersects(const MapType& left, const MapType& right)
+{
+ typename MapType::const_iterator right_common_lower_;
+ typename MapType::const_iterator right_common_upper_;
+ if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
+ return false;
+
+ typename MapType::const_iterator right_ = right_common_lower_;
+ while(right_ != right_common_upper_)
+ if(left.intersects(*right_++))
+ return true;
- typename MapType::const_iterator x1_ = common_lwb_, x2_;
+ return false;
+}
+
+template <class ObjectT, class CoObjectT>
+bool key_intersects(const ObjectT& left, const CoObjectT& right)
+{
+ typename CoObjectT::const_iterator right_common_lower_;
+ typename CoObjectT::const_iterator right_common_upper_;
+ if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
+ return false;
+
+ typename CoObjectT::const_iterator right_ = right_common_lower_;
+ while(right_ != right_common_upper_)
+ if(left.intersects(CoObjectT::key_value(right_++)))
+ return true;
+
+ return false;
+}
+
+//----------------------------------------------------------------------
+// flip
+//----------------------------------------------------------------------
+template<class MapType>
+void flip(MapType& result, const MapType& x2)
+{
+ if(is_total<MapType>::value && absorbs_neutrons<MapType>::value)
+ {
+ result.clear();
+ return;
+ }
- while(x1_ != common_upb_)
+ typename MapType::const_iterator x2_ = x2.begin(), cur_x2_, x1_;
+ while(x2_ != x2.end())
+ {
+ cur_x2_ = x2_;
+ std::pair<typename MapType::iterator,bool> insertion
+ = result.insert(*x2_++);
+ if(!insertion.WAS_SUCCESSFUL)
+ {
+ //result.erase(insertion.ITERATOR);
+ if(is_set<typename MapType::codomain_type>::value)
{
- x2_ = x2.find((*x1_).KEY_VALUE);
- if(x2_ != x2.end())
- {
- result.insert(*x1_);
- if(is_set<typename MapType::codomain_type>::value)
- result.template add<MapType::codomain_intersect>(*x2_); //MEMO template cast for gcc
- else
- result.template add<MapType::codomain_combine>(*x2_);
- }
- x1_++;
+ typename MapType::iterator res_ = insertion.ITERATOR;
+ typename MapType::codomain_type common_value = res_->CONT_VALUE;
+ typename MapType::key_type key_value = res_->KEY_VALUE;
+ typename MapType::inverse_codomain_intersect()(common_value, cur_x2_->CONT_VALUE);
+ result.subtract(*res_);
+ result.add(typename MapType::value_type(key_value, common_value));
}
+ else
+ result.subtract(*insertion.ITERATOR);
}
+ }
- template<class MapType>
- void intersect(MapType& result, const MapType& x2)
- {
- // result = result * x2;
- MapType tmp;
- intersect(tmp, result, x2);
- tmp.swap(result);
- }
+ if(is_total<MapType>::value && !absorbs_neutrons<MapType>::value)
+ FORALL(typename MapType, it_, result)
+ it_->CONT_VALUE = neutron<typename MapType::codomain_type>::value();
+}
- template<class MapType, class SetType>
- void intersect(MapType& result, const MapType& x1, const SetType& x2)
- {
- typename MapType::const_iterator common_lwb_;
- typename MapType::const_iterator common_upb_;
- result.clear();
- if(!Set::common_range(common_lwb_, common_upb_, x1, x2))
- return;
- typename MapType::const_iterator x1_ = common_lwb_;
- typename SetType::const_iterator common_;
+template<class MapType>
+typename MapType::const_iterator next_proton(typename MapType::const_iterator& iter_, const MapType& object)
+{
+ while( iter_ != object.end()
+ && iter_->CONT_VALUE == neutron<typename MapType::codomain_type>::value())
+ ++iter_;
+
+ return iter_;
+}
+
+/** Function template <tt>lexicographical_equal</tt> implements
+lexicographical equality except for neutronic content values. */
+template<class MapType>
+bool lexicographical_protonic_equal(const MapType& left, const MapType& right)
+{
+ if(&left == &right)
+ return true;
- while(x1_ != common_upb_)
- {
- common_ = x2.find((*x1_).KEY_VALUE);
- if(common_ != x2.end())
- result.insert(*x1_);
+ typename MapType::const_iterator left_ = left.begin();
+ typename MapType::const_iterator right_ = right.begin();
- x1_++;
- }
- }
+ left_ = next_proton(left_, left);
+ right_ = next_proton(right_, right);
- template<class MapType, class SetType>
- void intersect(MapType& result, const SetType& x2)
- {
- // result = result * x2;
- MapType tmp;
- intersect(tmp, result, x2);
- tmp.swap(result);
+ while(left_ != left.end() && right_ != right.end())
+ {
+ if(!(left_->KEY_VALUE == right_->KEY_VALUE && left_->CONT_VALUE == right_->CONT_VALUE))
+ return false;
+
+ ++left_;
+ ++right_;
+ left_ = next_proton(left_, left);
+ right_ = next_proton(right_, right);
+ }
+
+ return left_ == left.end() && right_ == right.end();
+}
+
+
+//------------------------------------------------------------------------------
+template<class LeftT, class RightT>
+class subset_comparer
+{
+public:
+ typedef typename LeftT::const_iterator LeftIterT;
+ typedef typename RightT::const_iterator RightIterT;
+
+ subset_comparer(const LeftT& left,
+ const RightT& right,
+ const LeftIterT& left_end,
+ const RightIterT& right_end)
+ : _left(left), _right(right),
+ _left_end(left_end), _right_end(right_end),
+ _compare_codomain(false), _result(equal)
+ {}
+
+ enum{nextboth, nextleft, nextright, stop};
+
+ enum
+ {
+ unrelated = inclusion::unrelated,
+ subset = inclusion::subset, // left is_subset_of right
+ superset = inclusion::superset, // left is_superset_of right
+ equal = inclusion::equal // equal = subset | superset
+ };
+
+ void set_compare_codomain(bool truth=true)
+ { _compare_codomain = truth; }
+
+ bool compare_codomain()const { return _compare_codomain; }
+
+ int result()const{ return _result; }
+
+
+ int co_compare(LeftIterT& left, RightIterT& right)
+ {
+ using namespace boost::mpl;
+
+ return
+ if_<
+ bool_<is_concept_equivalent<is_interval_map,LeftT,RightT>::value>,
+ map_codomain_compare<LeftT,RightT>,
+ empty_codomain_compare<LeftT,RightT>
+ >
+ ::type::apply(left,right);
+ }
+
+ int restrict_result(int state) { return _result &= state; }
+
+ int proceed(LeftIterT& left, RightIterT& right)
+ {
+ if(LeftT::key_value(left).upper_less(RightT::key_value(right)))
+ { // left ..)
+ // right .....)
+ _prior_left = left;
+ ++left;
+ return nextleft;
+ }
+ else if(RightT::key_value(right).upper_less(LeftT::key_value(left)))
+ { // left .....)
+ // right ..)
+ _prior_right = right;
+ ++right;
+ return nextright;
+ }
+ else//LeftT::key_value(left).upper_equal(RightT::key_value(right))
+ { // left ..)
+ // right ..)
+ ++left;
+ ++right;
+ return nextboth;
}
+ }
- //----------------------------------------------------------------------
- // flip
- //----------------------------------------------------------------------
- template<class MapType>
- void flip(MapType& result, const MapType& x2)
- {
- if(is_total<MapType>::value && absorbs_neutrons<MapType>::value)
+ int next_both(LeftIterT& left, RightIterT& right)
+ {
+ if(left == _left_end && right == _right_end)
+ return stop;
+ else if(left == _left_end)
+ { // left: ....end left could be subset
+ // right:....[..
+ restrict_result(subset);
+ return stop;
+ }
+ else if(right == _right_end)
+ { // left: ....[.. left could be superset
+ // right:....end
+ restrict_result(superset);
+ return stop;
+ }
+ else if(LeftT::key_value(left).exclusive_less(RightT::key_value(right)))
+ { // left: [..) . . .[---) left could be superset
+ // right: [..).... if [---) exists
+ restrict_result(superset);
+ if(unrelated == _result)
+ return stop;
+ else
{
- result.clear();
- return;
+ LeftIterT joint_ = _left.lower_bound(RightT::key_value(right));
+ if(joint_ == _left.end())
+ {
+ _result = unrelated;
+ return stop;
+ }
+ else
+ {
+ left = joint_;
+ return nextboth;
+ }
}
-
- typename MapType::const_iterator x2_ = x2.begin(), cur_x2_, x1_;
- while(x2_ != x2.end())
+ }
+ else if(RightT::key_value(right).exclusive_less(LeftT::key_value(left)))
+ { // left: [.. left could be subset
+ // right:....) . . .[---) if [---) exists
+ restrict_result(subset);
+ if(unrelated == _result)
+ return stop;
+ else
{
- cur_x2_ = x2_;
- std::pair<typename MapType::iterator,bool> insertion
- = result.insert(*x2_++);
- if(!insertion.WAS_SUCCESSFUL)
+ RightIterT joint_ = _right.lower_bound(LeftT::key_value(left));
+ if(joint_ == _right.end())
+ {
+ _result = unrelated;
+ return stop;
+ }
+ else
{
- //result.erase(insertion.ITERATOR);
- if(is_set<typename MapType::codomain_type>::value)
- {
- typename MapType::iterator res_ = insertion.ITERATOR;
- typename MapType::codomain_type common_value = res_->CONT_VALUE;
- typename MapType::key_type key_value = res_->KEY_VALUE;
- typename MapType::inverse_codomain_intersect()(common_value, cur_x2_->CONT_VALUE);
- result.subtract(*res_);
- result.add(typename MapType::value_type(key_value, common_value));
- }
- else
- result.subtract(*insertion.ITERATOR);
+ right = joint_;
+ return nextboth;
}
}
+ }
- if(is_total<MapType>::value && !absorbs_neutrons<MapType>::value)
- FORALL(typename MapType, it_, result)
- it_->CONT_VALUE = neutron<typename MapType::codomain_type>::value();
+ // left and right have intervals with nonempty intersection:
+ if(compare_codomain())
+ if(unrelated == restrict_result(co_compare(left,right)))
+ return stop;
+
+ // examine left borders only. Right borders are checked in proceed
+ if(LeftT::key_value(left).lower_less(RightT::key_value(right)))
+ { // left: ....[... left could be superset
+ // right:.... [..
+ if(unrelated == restrict_result(superset))
+ return stop;
+ }
+ else if(RightT::key_value(right).lower_less(LeftT::key_value(left)))
+ { // left: .... [.. left can be subset
+ // right:....[...
+ if(unrelated == restrict_result(subset))
+ return stop;
}
+ //else LeftT::key_value(right).lower_equal(RightT::key_value(left))
+ // left: ....[.. both can be equal
+ // right:....[..
+ // nothing to do: proceed
+ return proceed(left, right);
+ }
+ int next_left(LeftIterT& left, RightIterT& right)
+ {
+ if(left == _left_end)
+ { // left: ..)end left could be subset
+ // right:......)
+ restrict_result(subset);
+ return stop;
+ }
+ else if(!LeftT::key_value(_prior_left).touches(LeftT::key_value(left)))
+ { // left: ..) [..
+ // right:.........)
+ if(RightT::key_value(right).lower_less(LeftT::key_value(left)))
+ { // ..) [.. left could be subset
+ // ..........)
+ if(unrelated == restrict_result(subset))
+ return stop;
+ }
+ //else ..) [...
+ // [..
+ if(compare_codomain() && !LeftT::key_value(left).is_disjoint(RightT::key_value(right)) )
+ if(unrelated == restrict_result(co_compare(left,right)))
+ return stop;
+ }
+ else
+ { // left: ..)[.. left could be subset
+ // right:.......)
+ if(compare_codomain() && !LeftT::key_value(left).is_disjoint(RightT::key_value(right)) )
+ if(unrelated == restrict_result(co_compare(left,right)))
+ return stop;
+ }
- template<class MapType>
- typename MapType::const_iterator next_proton(typename MapType::const_iterator& iter_, const MapType& object)
- {
- while( iter_ != object.end()
- && iter_->CONT_VALUE == neutron<typename MapType::codomain_type>::value())
- ++iter_;
+ return proceed(left, right);
+ }
- return iter_;
- }
- /** Function template <tt>lexicographical_equal</tt> implements
- lexicographical equality except for neutronic content values. */
- template<class MapType>
- bool lexicographical_protonic_equal(const MapType& left, const MapType& right)
+ int next_right(LeftIterT& left, RightIterT& right)
+ {
+ if(right == _right_end)
+ { // left: ......) left could be superset
+ // right:..)end
+ restrict_result(superset);
+ return stop;
+ }
+ else if(!RightT::key_value(_prior_right).touches(RightT::key_value(right)))
+ { // left: .........)
+ // right:..) [..
+ if(LeftT::key_value(left).lower_less(RightT::key_value(right)))
+ { // [....) left could be superset
+ // ..) [..
+ if(unrelated == restrict_result(superset))
+ return stop;
+ }
+ //else [....)
+ // ..) [..
+ if(compare_codomain() && !LeftT::key_value(left).is_disjoint(RightT::key_value(right)) )
+ if(unrelated == restrict_result(co_compare(left,right)))
+ return stop;
+ }
+ else
{
- if(&left == &right)
- return true;
+ if(compare_codomain() && !LeftT::key_value(left).is_disjoint(RightT::key_value(right)) )
+ if(unrelated == restrict_result(co_compare(left,right)))
+ return stop;
+ }
+
+ return proceed(left, right);
+ }
+
+private:
+ const LeftT& _left;
+ const RightT& _right;
+ LeftIterT _left_end;
+ RightIterT _right_end;
+ bool _compare_codomain;
+ LeftIterT _prior_left;
+ RightIterT _prior_right;
+ int _result;
+};
- typename MapType::const_iterator left_ = left.begin();
- typename MapType::const_iterator right_ = right.begin();
- left_ = next_proton(left_, left);
- right_ = next_proton(right_, right);
- while(left_ != left.end() && right_ != right.end())
- {
- if(!(left_->KEY_VALUE == right_->KEY_VALUE && left_->CONT_VALUE == right_->CONT_VALUE))
- return false;
- ++left_;
- ++right_;
- left_ = next_proton(left_, left);
- right_ = next_proton(right_, right);
- }
- return left_ == left.end() && right_ == right.end();
- }
- } // namespace Map
+} // namespace Map
}} // namespace boost itl
#endif
Modified: sandbox/itl/boost/itl/predicates.hpp
==============================================================================
--- sandbox/itl/boost/itl/predicates.hpp (original)
+++ sandbox/itl/boost/itl/predicates.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -70,6 +70,8 @@
}
};
+ //-----------------------------------------------------------------------------
+
template<>
inline std::string unary_template_to_string<itl::std_equal>::apply()
{ return "=="; }
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-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -98,7 +98,9 @@
template<class SubType>
separate_interval_set
(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
- { assign(src); }
+ {
+ assign(src);
+ }
/// Constructor for a single element
explicit separate_interval_set(const domain_type& elem): base_type() { add(elem); }
@@ -109,7 +111,10 @@
template<class SubType>
separate_interval_set& operator =
(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
- { assign(src); return *this; }
+ {
+ assign(src);
+ return *this;
+ }
/// Assignment from a base interval_set.
template<class SubType>
@@ -124,15 +129,15 @@
interval_base_set<separate_interval_set<DomainT,Compare,Interval,Alloc>,
DomainT,Compare,Interval,Alloc>;
- /// Does the set contain the interval <tt>x</tt>?
- bool contains_(const interval_type& x)const;
+ /// Does the set contain the interval <tt>sub</tt>?
+ bool contains_(const interval_type& sub)const;
- /// Insertion of an interval <tt>x</tt>
- void add_(const value_type& x);
- iterator add_(iterator prior_, const value_type& x);
+ /// Insertion of an interval <tt>addend</tt>
+ void add_(const value_type& addend);
+ iterator add_(iterator prior_, const value_type& addend);
- /// Removal of an interval <tt>x</tt>
- void subtract_(const value_type& x);
+ /// Removal of an interval <tt>minuend</tt>
+ void subtract_(const value_type& minuend);
private:
/// Treatment of adjoint intervals on insertion
@@ -140,18 +145,6 @@
} ;
-template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-inline bool separate_interval_set<DomainT,Compare,Interval,Alloc>::contains_(const interval_type& interv)const
-{
- if(interv.empty())
- return true;
-
- type section;
- add_intersection(section, interv);
- return is_element_equal(section, type(interv));
-}
-
-
template<class DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
inline void separate_interval_set<DomainT,Compare,Interval,Alloc>::add_(const value_type& addend)
{
Modified: sandbox/itl/boost/itl/set.hpp
==============================================================================
--- sandbox/itl/boost/itl/set.hpp (original)
+++ sandbox/itl/boost/itl/set.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -19,9 +19,14 @@
#include <boost/itl/type_traits/is_total.hpp>
#include <boost/itl/detail/notate.hpp>
#include <boost/itl/detail/design_config.hpp>
+#include <boost/itl/detail/subset_comparer.hpp>
#include <boost/itl/set_algo.hpp>
#include <boost/itl/predicates.hpp>
+#include <boost/utility/enable_if.hpp>
+#include <boost/mpl/or.hpp>
+#include <boost/mpl/not.hpp>
+#include <boost/type_traits/is_same.hpp>
namespace boost{namespace itl
{
@@ -74,12 +79,12 @@
std::set<DomainT, domain_compare, Alloc<DomainT> >(comp){}
template <class InputIterator>
- set(InputIterator first, InputIterator last):
- std::set<InputIterator>(first,last) {}
+ set(InputIterator first, InputIterator past):
+ std::set<InputIterator>(first,past) {}
template <class InputIterator>
- set(InputIterator first, InputIterator last, const key_compare& comp):
- std::set<InputIterator>(first, last, comp) {}
+ set(InputIterator first, InputIterator past, const key_compare& comp):
+ std::set<InputIterator>(first, past, comp) {}
set(const set& src): base_type::set(src){}
@@ -119,7 +124,7 @@
public:
//==========================================================================
- //= Emptieness, containment
+ //= Containedness
//==========================================================================
/// Checks if the element \c value is in the set
@@ -178,6 +183,11 @@
to \c section. */
void add_intersection(set& section, const set& sectant)const;
+ /** Returns true, if there is an intersection of \c element and \c *this set.
+ Functions \c intersects and \c contains are identical on arguments
+ of type \c element_type. Complexity: Logarithmic in container size. */
+ bool intersects(const element_type& element)const { return contains(element); }
+
/** If \c *this set contains \c element it is erased, otherwise it is added. */
set& flip(const element_type& element);
@@ -523,6 +533,44 @@
return object &= operand;
}
+
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+bool intersects(const itl::set<DomainT,Compare,Alloc>& object,
+ const typename itl::set<DomainT,Compare,Alloc>::element_type& element)
+{
+ return object.intersects(element);
+}
+
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+bool intersects(
+ const typename itl::set<DomainT,Compare,Alloc>::element_type& element,
+ const itl::set<DomainT,Compare,Alloc>& object)
+{
+ return object.intersects(element);
+}
+
+template <typename DomainT, ITL_COMPARE Compare, ITL_ALLOC Alloc>
+bool intersects(const itl::set<DomainT,Compare,Alloc>& left,
+ const itl::set<DomainT,Compare,Alloc>& right)
+{
+ if(left.iterative_size() < right.iterative_size())
+ return Set::intersects(right, left);
+ else
+ return Set::intersects(left, right);
+}
+
+template <typename DomainT, ITL_COMPARE Compare, ITL_ALLOC Alloc,
+ class LeftT, class RightT>
+enable_if<mpl::or_<is_same< typename itl::set<DomainT,Compare,Alloc>, LeftT >,
+ is_same< typename itl::set<DomainT,Compare,Alloc>, RightT>
+ >, bool>
+is_disjoint(const LeftT& left, const RightT& right)
+{
+ return !intersects(left,right);
+}
+
+
+
//--------------------------------------------------------------------------
// itl::set::symmetric_difference operators ^=, ^
//--------------------------------------------------------------------------
@@ -602,7 +650,10 @@
}
-//-------------------------------------------------------------------------
+
+//-----------------------------------------------------------------------------
+// type traits
+//-----------------------------------------------------------------------------
template <class Type>
struct is_set<itl::set<Type> >
{
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-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -155,20 +155,6 @@
void erase_rest(const interval_type& inter_val, const CodomainT& co_val, iterator& it_, iterator& last_);
} ;
-
-template <typename DomainT, typename CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-bool split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
- ::contains_(const value_type& interv_value)const
-{
- interval_type interv = interv_value.KEY_VALUE;
- if(interv.empty())
- return true;
-
- type section;
- add_intersection(section, interv);
- return is_element_equal(section, type(interv_value));
-}
-
//-----------------------------------------------------------------------------
// add<Combinator>(pair(interval,value)):
//-----------------------------------------------------------------------------
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-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -121,15 +121,15 @@
interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>,
DomainT,Compare,Interval,Alloc>;
- /// Does the set contain the interval <tt>x</tt>?
- bool contains_(const interval_type& x)const;
+ /// Does the set contain the interval <tt>sub</tt>?
+ bool contains_(const interval_type& sub)const;
- /// Insertion of an interval <tt>x</tt>
- void add_(const value_type& x);
- iterator add_(iterator prior_, const value_type& x);
+ /// Addition of an interval <tt>addend</tt>
+ void add_(const value_type& addend);
+ iterator add_(iterator prior_, const value_type& addend);
- /// Removal of an interval <tt>x</tt>
- void subtract_(const value_type& x);
+ /// Subtraction of an interval <tt>minuend</tt>
+ void subtract_(const value_type& minuend);
private:
/// Treatment of adjoint intervals on insertion
@@ -143,17 +143,6 @@
void subtract_rest(const interval_type& x_itv, iterator& it_, iterator& end_ );
} ;
-template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
-inline bool split_interval_set<DomainT,Compare,Interval,Alloc>::contains_(const interval_type& interv)const
-{
- if(interv.empty())
- return true;
-
- type section;
- add_intersection(section, interv);
- return is_element_equal(section, type(interv));
-}
-
template <typename DomainT, ITL_COMPARE Compare, template<class,ITL_COMPARE>class Interval, ITL_ALLOC Alloc>
inline void split_interval_set<DomainT,Compare,Interval,Alloc>::add_(const value_type& addend)
Modified: sandbox/itl/boost/itl/type_traits/is_combinable.hpp
==============================================================================
--- sandbox/itl/boost/itl/type_traits/is_combinable.hpp (original)
+++ sandbox/itl/boost/itl/type_traits/is_combinable.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -14,6 +14,7 @@
#include <boost/mpl/or.hpp>
#include <boost/mpl/not.hpp>
#include <boost/type_traits/is_same.hpp>
+#include <boost/itl/type_traits/is_concept_equivalent.hpp>
namespace boost{namespace itl
{
@@ -26,29 +27,6 @@
is_same<Type, typename Type::overloadable_type>::value;
};
-template<class Type>
-struct is_interval_map
-{
- typedef is_interval_map<Type> type;
- static const bool value =
- is_interval_container<Type>::value && is_map<Type>::value;
-};
-
-template<class Type>
-struct is_interval_set
-{
- typedef is_interval_set<Type> type;
- static const bool value =
- is_interval_container<Type>::value && !is_interval_map<Type>::value;
-};
-
-template<template<class>class IsConcept, class LeftT, class RightT>
-struct is_concept_equivalent
-{
- typedef is_concept_equivalent<IsConcept, LeftT, RightT> type;
- static const bool value =
- mpl::and_<IsConcept<LeftT>, IsConcept<RightT> >::value;
-};
//------------------------------------------------------------------------------
template<class LeftT, class RightT>
@@ -71,12 +49,12 @@
};
template<class LeftT, class RightT>
-struct is_content_type_equal
+struct is_codomain_type_equal
{
- typedef is_content_type_equal<LeftT, RightT> type;
+ typedef is_codomain_type_equal<LeftT, RightT> type;
static const bool value =
mpl::and_<is_domain_compare_equal<LeftT, RightT>,
- is_codomain_equal<LeftT, RightT> >::value;//JODO
+ is_codomain_equal<LeftT, RightT> >::value;
};
@@ -89,7 +67,7 @@
mpl::and_
<
mpl::and_<IsConcept<LeftT>, IsConcept<RightT> >
- , is_content_type_equal<LeftT, RightT>
+ , is_codomain_type_equal<LeftT, RightT>
>::value;
};
Modified: sandbox/itl/boost/itl/type_traits/is_interval_container.hpp
==============================================================================
--- sandbox/itl/boost/itl/type_traits/is_interval_container.hpp (original)
+++ sandbox/itl/boost/itl/type_traits/is_interval_container.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -16,6 +16,23 @@
static const bool value = false;
};
+ template<class Type>
+ struct is_interval_map
+ {
+ typedef is_interval_map<Type> type;
+ static const bool value =
+ is_interval_container<Type>::value && is_map<Type>::value;
+ };
+
+ template<class Type>
+ struct is_interval_set
+ {
+ typedef is_interval_set<Type> type;
+ static const bool value =
+ is_interval_container<Type>::value && !is_interval_map<Type>::value;
+ };
+
+
}} // namespace boost itl
#endif
Added: sandbox/itl/boost/validate/laws/minor_set_laws.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/validate/laws/minor_set_laws.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -0,0 +1,156 @@
+/*-----------------------------------------------------------------------------+
+A Law Based Test Automaton 'LaBatea'
+Author: Joachim Faulhaber
+Copyright (c) 2007-2009: Joachim Faulhaber
++------------------------------------------------------------------------------+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENCE.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
++-----------------------------------------------------------------------------*/
+#ifndef __itl_minor_set_laws_JOFA_090821__
+#define __itl_minor_set_laws_JOFA_090821__
+
+#include <boost/itl/type_traits/value_size.hpp>
+#include <boost/itl/functors.hpp>
+#include <boost/itl/predicates.hpp>
+#include <boost/validate/laws/law.hpp>
+
+namespace boost{namespace itl
+{
+
+ template <typename Type>
+ class IntersectsDefined
+ : public Law<IntersectsDefined<Type>, LOKI_TYPELIST_2(Type,Type), LOKI_TYPELIST_2(bool,bool)>
+ {
+ /** is_total<T> || (intersects(a, b) == !(a & b).empty()) : Definition of intersects predicate
+ Input = (a := inVal1, b := inVal2)
+ Output = (lhs_result, rhs_result)
+ */
+ public:
+ std::string name()const { return "IntersectsDefined defined"; }
+ std::string formula()const { return "is_total<T> || intersects(a, b) == !(a & b).empty()"; }
+
+ std::string typeString()const
+ {
+ return "IntersectsDefined<"+type_to_string<Type>::apply()+">";
+ }
+
+ public:
+
+ bool holds()
+ {
+ // is_total<T> || intersects(a, b) == !(a & b).empty()
+ // --- left hand side ------------------------
+ bool a_intersects_b
+ = intersects(this->template getInputValue<operand_a>(),
+ this->template getInputValue<operand_b>());
+ // --- right hand side ------------------------
+ Type a_sec_b = this->template getInputValue<operand_a>();
+ a_sec_b &= this->template getInputValue<operand_b>();
+
+ bool a_sec_b_non_empty = !a_sec_b.empty();
+
+ this->template setOutputValue<lhs_result>(a_intersects_b);
+ this->template setOutputValue<rhs_result>(a_sec_b_non_empty);
+
+ if(is_total<Type>::value)
+ // For a total map y, y.empty() does not mean that y is empty
+ // it means that y is a null vector. In this sense total maps
+ // always intersect with themselves and with key sets.
+ return a_intersects_b == true;
+ else
+ return a_intersects_b == a_sec_b_non_empty;
+ }
+
+ bool debug_holds()
+ {
+ // intersects(a, b) == !(a & b).empty() : Definition of intersects predicate
+ // --- left hand side ------------------------
+ Type value_a = this->template getInputValue<operand_a>();
+ Type value_b = this->template getInputValue<operand_b>();
+ cout << "a = " << value_a << endl;
+ cout << "b = " << value_b << endl;
+ cout << "a&b = " << (value_a & value_b) << endl;
+
+ bool a_intersects_b
+ = intersects(this->template getInputValue<operand_a>(),
+ this->template getInputValue<operand_b>());
+ // --- right hand side ------------------------
+ Type a_sec_b = this->template getInputValue<operand_a>();
+ a_sec_b &= this->template getInputValue<operand_b>();
+
+ bool a_sec_b_non_empty = !a_sec_b.empty();
+
+ this->template setOutputValue<lhs_result>(a_intersects_b);
+ this->template setOutputValue<rhs_result>(a_sec_b_non_empty);
+
+ if(is_total<Type>::value)
+ return a_intersects_b == true;
+ else
+ return a_intersects_b == a_sec_b_non_empty;
+ }
+
+ size_t size()const
+ {
+ return value_size<Type>::apply(this->template getInputValue<operand_a>())+
+ value_size<Type>::apply(this->template getInputValue<operand_b>());
+ }
+ };
+
+ template <typename Type, typename CoType>
+ class Interinclusion
+ : public Law<Interinclusion<Type,CoType>, LOKI_TYPELIST_2(Type,CoType), LOKI_TYPELIST_1(bool)>
+ {
+ /** a.contains(a & b)
+ Input = (a := inVal1, b := inVal2)
+ Output = (lhs_result, rhs_result)
+ */
+ public:
+ std::string name()const { return "Interinclusion"; }
+ std::string formula()const { return "a.contains(a & b)"; }
+
+ std::string typeString()const
+ {
+ return "Interinclusion<"+ type_to_string<Type>::apply()+","
+ +type_to_string<CoType>::apply()+">";
+ }
+
+ public:
+
+ bool holds()
+ {
+ // a.contains(a & b)
+ Type value_a = this->template getInputValue<operand_a>();
+ CoType value_b = this->template getInputValue<operand_b>();
+ return value_a.contains(value_a & value_b);
+ }
+
+ bool debug_holds()
+ {
+ // a.contains(a & b)
+ Type value_a = this->template getInputValue<operand_a>();
+ CoType value_b = this->template getInputValue<operand_b>();
+ Type a_sec_b = value_a & value_b;
+ bool result = value_a.contains(value_a & value_b);
+ // -------------------------------------------
+ cout << "a = " << value_a << endl;
+ cout << "b = " << value_b << endl;
+ cout << "a&b = " << a_sec_b << endl;
+ cout << "a.contains(a&b) = " << result << endl;
+ // -------------------------------------------
+ value_a.contains(a_sec_b);
+
+ return result;
+ }
+
+ size_t size()const
+ {
+ return value_size< Type>::apply(this->template getInputValue<operand_a>())+
+ value_size<CoType>::apply(this->template getInputValue<operand_b>());
+ }
+ };
+
+}} // namespace itl boost
+
+#endif // __itl_minor_set_laws_JOFA_070411__
+
Modified: sandbox/itl/libs/itl/doc/functions.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/functions.qbk (original)
+++ sandbox/itl/libs/itl/doc/functions.qbk 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -11,9 +11,10 @@
Section [link boost_itl.interface.function_synopsis Function Synopsis]
above gave an overview of the polymorphic functions of the itl.
-This is what you will need to find the desired possibilites to combine itl objects.
-Most of the time, the functions and overloads that you intuitively expect
-should be provided, so you won't need to refer to the documentation often.
+This is what you will need to find the desired possibilites to combine itl
+functions and objects most of the time.
+The functions and overloads that you intuitively expect
+should be provided, so you won't need to refer to the documentation very often.
If you are interested
@@ -24,9 +25,228 @@
refer to this section that describes the polymorphic function families of the itl
in detail.
-For a concise representaion the same __eiS_phs__ will be used that have been
+[/ JODO placeholders again]
+[h5 Placeholders]
+
+For a concise representation the same __eiS_phs__ will be used that have been
introduced in section [link boost_itl.interface.function_synopsis Function Synopsis].
+[h5 More specific function documentation]
+
+This section covers the most important polymorphical and namespace global
+functions of the *itl*. More specific functions are may be looked up
+in the doxygen generated
+[link interval_template_library_reference reference documentation].
+
+[/ JODO introducing overload tables. ==========================================]
+[section Overload tables]
+
+Many of the *itl's* functions are overloaded for
+elements, segments, element and interval containers.
+But not all type combinations are provided. Also
+the admissable type combinations are different for
+different functions and operations.
+To concisely represent the overloads that can be
+used we use synoptical tables that contain
+possible type combinations for an operation.
+These are called ['*overload tables*]. As an example
+the overload tables for the inplace intersection
+`operator &=` are given:
+
+``
+// overload tables for
+T& operator &= (T&, const P&)
+
+element containers: interval containers:
+&= | e b s m &= | e i b p S M
+---+-------- ---+------------
+s | s s S | S S S
+m | m m m m M | M M M M M M
+``
+
+For the binary `T& operator &= (T&, const P&)` there are two
+different tables for the overloads of element and interval containers.
+The first argument type `T` is displayed as row headers
+of the tables.
+The second argument type `P` is displayed as column headers
+of the tables.
+If a combination of `T` and `P` is admissable the related
+cell of the table is non empty.
+It displays the result type of the operation. In this example
+the result type is always equal to the first argument.
+
+The possible types that can be instaniated for `T` and `P`
+are element, interval and container types abbreviated by
+placeholders that are defined
+[link boost_itl.interface.function_synopsis here]
+and can be summerized as
+
+__s : element set, __S : interval sets, __e : elements, __i : intervals\n
+__m:element map, __M:interval maps, __b:element-value pairs, __p:interval-value pairs
+
+
+[endsect][/ Overload tables]
+
+[/ JODO Si Mj and segmentational fineness. ====================================]
+[section Segmentational Fineness]
+
+For overloading tables on infix operators, we need to
+break down __itv_sets__ and __itv_maps__ to the
+specific class templates
+
+[table
+[[][] [][] [][]]
+[[[#ph_def_S1][*S1]][__itv_set__][[#ph_def_S2][*S2]][__sep_itv_set__][[#ph_def_S3][*S3]][__spl_itv_set__]]
+[[[#ph_def_M1][*M1]][__itv_map__][][] [[#ph_def_M3][*M3]][__spl_itv_map__]]
+]
+
+
+choosing *Si* and *Mi* as placeholders.
+
+The indices *i* of *Si* and *Mi* represent a property
+called ['*segmentational fineness*] or short ['*fineness*],
+which is a ['*type trait] on interval containers.
+
+[table
+[[]]
+[[`segmentational_fineness<`[*Si]`>::value` == *i*]]
+[[`segmentational_fineness<`[*Mi]`>::value` == *i*]]
+]
+
+
+Segmentational fineness represents the fact,
+that for interval containers holding the same elements, a
+splitting interval container may contain more segments as
+a separating container which in turn may contain more
+segments than a joining one. So for an
+``
+operator >
+``
+where
+``
+x > y // means that
+x is_finer_than y
+
+// we have
+
+finer coarser
+split_interval_set interval_set
+ > separate_interval_set >
+split_interval_map interval_map
+``
+
+This relation is needed to resolve the instantiation of
+infix operators e.g. `T operator + (P, Q)` for two interval container types
+`P` and `Q`. If both `P` and `Q` are candidates for the result
+type `T`, one of them must be chosen by the compiler.
+We choose the type that is segmentational finer as
+result type `T`. This way we do not loose the ['*segment informations*]
+that are stored in the ['*finer*] one of the container types `P` and `Q`.
+
+``
+// overload tables for
+T operator + (T, const P&)
+T operator + (const P&, T)
+
+element containers: interval containers:
++ | e b s m + | e i b p S1 S2 S3 M1 M3
+---+-------- ---+---------------------------
+e | s e | S1 S2 S3
+b | m i | S1 S2 S3
+s | s s b | M1 M3
+m | m m p | M1 M3
+ S1 | S1 S1 S1 S2 S3
+ S2 | S2 S2 S2 S2 S3
+ S3 | S3 S3 S3 S3 S3
+ M1 | M1 M1 M1 M3
+ M3 | M3 M3 M3 M3
+``
+
+
+So looking up a type combination for e.g.
+`T operator + (interval_map, split_interval_map)`
+which is equivalent to
+`T operator + (M1, M3)`
+we find for row type `M1` and column type `M3`
+that `M3`
+will be assigned as result type, because `M3`
+is finer than `M1`.
+So this type combination will result in
+choosing this
+``
+split_interval_map operator + (const interval_map&, split_interval_map)
+``
+implementation by the compiler.
+
+[endsect][/ Segmentational Fineness]
+
+[/ JODO introducing key types. ================================================]
+[section Key Types]
+
+In an *stl* map `map<K,D>` the first parameter type of the map
+template `K` is called `key_type`. It allows to select key-value pairs
+pairs via `find(const K&)`
+and to remove key-value pairs using `erase(const K&)`.
+For itl Maps we have generalized key types to a larger
+set of types. Not only the `key_type` (`domain_type`)
+but also an interval type and a set type can be ['*key types*],
+that allow for ['*selection*] and ['*removal*] of map elements
+segments and submaps.
+
+[table Selection of elements, segments and sub maps using key types
+[[ ][ __M: __itv_maps__ ][ __m: itl_map ]]
+[[__e: `domain_type` ][ key value pair ][ key value pair ]]
+[[__i: `interval_type` ][ interval value pair ][ ]]
+[[__S: __itv_sets__ ][ interval map ][ ]]
+[[__s: __itl_set__ ][ ][ interval map ]]
+]
+
+__biLSubtraction__, __biLerasure__, __biLintersection__,
+which is a generalized find
+and __biLcontainedness__ predicates
+can be used with those kinds of key types.
+For instance, the overload table for intersection
+
+``
+// overload tables for
+T& operator &= (T&, const P&)
+
+element containers: interval containers:
+&= | e b s m &= | e i b p S M
+---+-------- ---+------------
+s | s s S | S S S
+m | m m m m M | M M M M M M
+``
+
+has a part that that allows for selection by key objects
+
+``
+element containers: interval containers:
+&= | e b s m &= | e i b p S M
+---+-------- ---+------------
+s | s s S | S S S
+m | m m M | M M M
+``
+
+and another part that provides overloads for
+generalized intersection:
+
+``
+element containers: interval containers:
+&= | e b s m &= | e i b p S M
+---+-------- ---+------------
+s | s s S | S S S
+m | m m M | M M M
+``
+
+For `Sets`, the ['*key types*] defined for maps
+are identical with the set types themselves.
+So the distiction between the function groups
+['*selection by key*] and ['*generalized intersection*]
+fall thogether in the well known ['*set intersection*].
+
+[endsect][/ Key Types]
+
[include functions_cons_copy_dest.qbk]
[include functions_containedness.qbk]
[include functions_equivs_orderings.qbk]
Modified: sandbox/itl/libs/itl/doc/functions_addition.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/functions_addition.qbk (original)
+++ sandbox/itl/libs/itl/doc/functions_addition.qbk 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -168,43 +168,8 @@
[section Infix operators]
-For every inplace operator
-``
-T& operator o= (T& object, const P& operand)
-``
-the *itl* provides corresponding infix operators.
-``
-T operator o (T object, const P& operand){ return object o= operand; }
-T operator o (const P& operand, T object){ return object o= operand; }
-``
-
-From this implementation of infix `operator o`
-the compiler will hopefully use return value optimization
-[@http://en.wikipedia.org/wiki/Return_value_optimization (RVO)]
-creatiing no temporary object and performing one copy of
-the first argument `object`.
-
-[caution
-Compared to the /inplace/ `operator o=` every use of an
-/infix/ `operator o` requires ['*one extra copy*]
-of the first argument `object` that passes a container.]
-
-Use infix operators only, if
-
-* efficiency is not crucial, e.g. the containers copied are small.
-* a concise and short notation is more important than efficiency in your context.
-* you need the result of operator `o=` as a copy anyway.
-
-
The admissable type combinations for infix `operator +`
-is defined by the overload tables below. For interval containers
-__itv_sets__ __S and __itv_maps__ __M are split up into
-
-``
-S1: interval_set M1: interval_map
-S2: separate_interval_set
-S3: split_interval_set M3: split_interval_map
-``
+are defined by the overload tables below.
``
// overload tables for
@@ -225,62 +190,6 @@
M3 | M3 M3 M3 M3
``
-[h5 Segmentational Fineness]
-
-The indices `i` of `Si` and `Mi` represent a property
-called ['*segmentational fineness*] or short ['*fineness*].
-Segmentational fineness represents the fact,
-that for interval containers holding the same elements, a
-splitting interval container may contain more segments as
-a separating container which in turn may contain more
-segments than a joining one. So for an
-``
-operator >
-``
-where
-``
-x > y // means that
-x is_finer_than y
-
-// we have
-
-finer coarser
-split_interval_set interval_set
- > separate_interval_set >
-split_interval_map interval_map
-``
-
-This relation is needed to resolve the instantiation of an
-infix `T operator + (P, Q)` for two interval container types
-`P` and `Q`. If both `P` and `Q` are candidates for the result
-type `T`, one of them must be chosen by the compiler.
-We choose the type that is segmentational finer as
-result type `T`. This way we do not loose the ['*segment informations*]
-that are stored in the ['*finer] one of the container types `P` and `Q`.
-
-So looking up a type combination for e.g.
-`T operator + (interval_map, split_interval_map)`
-which is equivalent to
-`T operator + (M1, M3)`
-we find for row type `M1` and column type `M3`,
-`M3` will be assigned as result type.
-So this type combination will result in
-choosing an
-``
-split_interval_map operator + (const interval_map&, split_interval_map)
-``
-
-[h5 Time Complexity of infix `operators o`]
-
-The time complexity of all infix operators of the *itl*
-is biased by the extra copy of the `object` argument.
-So all infix `operators o` are at least
-/linear/ in `n = object.iterative_size()`.
-Taking this into account, the complexities of all
-infix operators can be determined
-from the corresponding inplace `operators o=` they depend
-on.
-
[endsect][/ Infix operators]
[endsect][/ Addition]
Modified: sandbox/itl/libs/itl/doc/functions_cons_copy_dest.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/functions_cons_copy_dest.qbk (original)
+++ sandbox/itl/libs/itl/doc/functions_cons_copy_dest.qbk 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -13,13 +13,86 @@
[table
[[['*Construct, copy, destruct*]] [interval][__ch_itv_sets__][__ch_itv_maps__][itl::set][itl::map] ]
[[`T::T()`] [1] [1] [1] [1] [1] ]
-[[`T::T(const T&)`] [A] [1] [1] [1] [1] ]
-[[`T::T(const P&)`] [ ] [__eiS] [__bpM] [ ] [ ] ]
-[[`T::T(...)`] [3] [ ] [ ] [3] [3] ]
+[[`T::T(const P&)`] [A] [__eiS] [__bpM] [1] [1] ]
[[`T& T::operator=(const P&)`] [A] [__S] [__M] [1] [1] ]
[[`void T::swap(T&)`] [ ] [1] [1] [1] [1] ]
]
+All *itl* types are ['*regular types*]. They are ['*default constructible*],
+['*copy constructible*] and ['*assignable*]. On itl Sets and Maps a `swap`
+function is available, that allows for *constant time* swapping of
+container contents.
+The /regular and swappable part/ of the basic functions and their complexities
+are described in the tables below.
+
+[table
+[[['*Regular and swap*]] [interval][__ch_itv_sets__][__ch_itv_maps__][itl::set][itl::map] ]
+[[`T::T()`] [__O1__] [__O1__] [__O1__][__O1__] [__O1__] ]
+[[`T::T(const T&)`] [__O1__] [__On__] [__On__][__On__] [__On__] ]
+[[`T& T::operator=(const T&)`] [__O1__] [__On__] [__On__][__On__] [__On__] ]
+[[`void T::swap(T&)`] [ ] [__O1__] [__O1__][__O1__] [__O1__] ]
+]
+
+where /n/ `= iterative_size()`.
+
+[table
+[[['*Construct, copy, destruct*]] [Description] ]
+[[`T::T()`] [Object of type T is default constructed.] ]
+[[`T::T(const T& src)`] [Object of type T is copy constructed from object `src`. ] ]
+[[`T& T::operator=(const T&)` src][Assigns the contents of src to `*this` object. Returns a reference to the assigned object.] ]
+[[`void T::swap(T& src)`] [Swaps the content containers `*this` and `src` in constant time. ] ]
+]
+
+In addition we have overloads of constructors and assingnment operators
+for itl container types.
+``
+// overload tables for constructors
+T::T(const P& src)
+
+element containers: interval containers:
+T \ P | e b s m T \ P | e i b p S M
+------+-------- ------+------------
+s | s s S | S S S
+m | m m M | M M M
+``
+
+For an object of type `T` and an argument `src` of type `P` let
+``
+n = this->iterative_size();
+m = src.iterative_size();
+``
+in the following tables.
+
+[table Time Complexity for overloaded constructors on element containers
+[[`T(const P& src)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[__itl_set__] [__Olgn__] [] [__Om__] [] ]
+[[__itl_map__] [] [__Olgn__] [] [__Om__] ]
+]
+
+Time complexity characteristics of inplace insertion for interval containers
+is given by this table.
+
+[table Time Complexity for overloaded constructors on interval containers
+[[`T(const P& src)`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[interval_sets] [__O1__] [__O1__][] [] [__Om__] [] ]
+[[interval_maps] [] [] [__O1__][__O1__][] [__Om__] ]
+]
+
+``
+// overload tables for assignment
+T& operator = (const P& src)
+
+interval containers:
+T \ P | S M
+------+----
+S | S
+M | M
+``
+
+The assignment `T& operator = (const P& src)` is overloaded within interval containers.
+For all type combinations we have ['*linear time complexity*]
+in the maximum of the `iterative_size` of `*this` and `src`.
+
[endsect][/ Construct, copy, destruct]
Modified: sandbox/itl/libs/itl/doc/functions_containedness.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/functions_containedness.qbk (original)
+++ sandbox/itl/libs/itl/doc/functions_containedness.qbk 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -18,6 +18,105 @@
[[`bool T::contained_in(const P&)const`] [__i] [__S] [__M] [1] [1] ]
]
+This group of functions refers to ['*contain*]edness which should
+be fundamental to ['*contain*]ers. The function `contains`
+is overloaded. It covers different kinds of containedness:
+Containedness of elements, segments, and sub containers.
+
+[table
+[[['*Containedness*]] [ /O(...)/ ][Description ] ]
+[[`void T::clear()`] [__On__][All content is removed from the container.] ]
+[[`bool T::empty()const`] [__O1__][Returns `true`, if the container is empty, `false` otherwise.] ]
+[[`bool T::contains(const P& sub)const`] [[link complexities_contains ['see below]]]
+ [Returns `true`, if `*this` container contains object `sub`.] ]
+[[`bool T::contained_in(const P& super)const`][__Omlgn__][Returns `true`, if `*this` is contained in object `super`.] ]
+[[ ] [where] [ /n/` = this->iterative_size()`] ]
+[[ ] [ ] [ /m/` = super.iterative_size()`] ]
+]
+
+``
+// overload tables for
+bool T::contains(const P& src)
+
+element containers: interval containers:
+contains| e b s m contains| e i b p S M
+--------+-------- --------+------------
+ s | 1 1 S | 1 1 1
+ m | 1 1 1 1 M | 1 1 1 1 1 1
+``
+
+The overloads of `bool T::contains(const P& src)` cover various kinds
+of containedness. We can group them into a part (1) that checks
+if an element, a segment or a container /of same kinds/ is contained in
+an element or interval container
+
+``
+// (1) containedness of elements, segments or containers of same kind
+contains| e b s m contains| e i b p S M
+--------+-------- --------+------------
+ s | 1 1 S | 1 1 1
+ m | 1 1 M | 1 1 1
+``
+
+and another part (2) that checks the containedness of
+/key objects/, which can be /elements/ an /intervals/ or a /sets/.
+
+``
+// (2) containedness of key objects.
+contains| e b s m contains| e i b p S M
+--------+-------- --------+------------
+ s | 1 1 S | 1 1 1
+ m | 1 1 M | 1 1 1
+``
+
+For type *m* = __itl_map__,
+a key element (*m*`::domain_type`) and an __itl_set__
+(*m*`::set_type`) can be a ['*key object*].
+
+For an interval map type *M*,
+a key element (*M*`::domain_type`),
+an interval (*M*`::interval_type`) and an
+['*interval set*], can be ['*key objects*].
+
+[#complexities_contains] Complexity characteristics for function
+`bool T::contains(const P& sub)const`
+are given by the next tables where
+``
+n = this->iterative_size();
+m = sub.iterative_size(); //if P is a container type
+``
+
+[table Time Complexity for function contains on element containers
+[[`bool T::contains(const P& sub)const`][__ch_dom_t__][__ch_dom_mp_t__][__ch_itl_set__][__ch_itl_map__]]
+[[__itl_set__] [__Olgn__] [] [__Omlgn__] [] ]
+[[__itl_map__] [__Olgn__] [__Olgn__] [__Omlgn__] [__Omlgn__] ]
+]
+
+
+[table Time Complexity for function contains on interval containers
+[[`bool T::contains(const P& sub)const`][][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[interval_sets] [__itv_set__][__Olgn__] [__Olgn__] [] [] [__Omlgn__] [] ]
+[[] [__sep_itv_set__\n__spl_itv_set__][__Olgn__] [__On__ ] [] [] [__Omlgn__] [] ]
+[[interval_maps] [__itv_map__][__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Omlgn__] [__Omlgn__] ]
+[[] [__spl_itv_map__][__Olgn__] [__On__ ] [__Olgn__] [__On__] [__Omlgn__] [__Omlgn__] ]
+]
+
+All tests of containedness of containers in containers
+``
+bool T::contains(const P& sub_container)const
+bool T::contained_in(const P& super_container)const
+``
+are of ['*loglinear*] time: __Omlgn__.
+If both containers have same iterative_sizes so that /m = n/
+we have the worst case ( __Onlgn__ ).
+There is an alternative implementation that has a ['*linear*]
+complextity of __Onpm__.
+The loglinear implementation has been chosen,
+because it can be faster, if the container argument is
+small. In this case the loglinear implementation approaches
+logarithmic behavior, whereas the linear implementation
+stays linear.
+
[endsect][/ Containedness]
Modified: sandbox/itl/libs/itl/doc/functions_insertion.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/functions_insertion.qbk (original)
+++ sandbox/itl/libs/itl/doc/functions_insertion.qbk 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -63,7 +63,7 @@
``
[table Time Complexity for member function insert on itl containers
-[[`T& T::add(const P&)`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
+[[`T& T::insert(const P&)`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
[[__itl_set__] [__Olgn__] [] [] [] ]
[[__itl_map__] [] [] [__Olgn__][] ]
[[__itv_set__\n__sep_itv_set__][__Olgn__] [__a_Olgn__][] [] ]
Modified: sandbox/itl/libs/itl/doc/implementation.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/implementation.qbk (original)
+++ sandbox/itl/libs/itl/doc/implementation.qbk 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -8,23 +8,69 @@
[section Implementation]
-The implementation of the *itl's* conainers is based on
-std::set and std::map. So the underlying datastructure of
+The [link boost_itl.interface previous section] gave an overview over the interface
+of the *itl* outlining
+[link boost_itl.interface.class_templates class templates],
+[link boost_itl.interface.associated_types associated types]
+and polymorphic
+[link boost_itl.interface.function_synopsis functions and operators].
+In preparation to the
+[link boost_itl.function_reference next section],
+that describes the *itl's* polymorphic functions in
+more detail together with ['*complexity characteristics*],
+this section summarizes some general informations on
+implementation and performance.
+
+[h5 STL based implementation]
+
+The *implementation* of the *itl's* conainers is based on
+[*std::set] and [*std::map]. So the underlying datastructure of
interval containers is a red black tree of intervals or
interval value pairs.
-The element containers itl::set and itl::map are wrapper
-classes of std::set and std::map.
-Interval containers are then using itl::sets of intervals
-or itl::maps of interval value pairs as implementing
+The element containers __itl_set__ and __itl_map__ are wrapper
+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
+So all the ['*complexity characteristics*] of itl conainers
are based on and limited by the ['*red-black tree implementation*]
of the underlying std::AssociativeContainers.
-[section Complexity]
-This section gives an overview over the time complextity of
-the basic operations of ['itl containers].
+[section Iterative size]
+
+Throughout the documentation on complexity,
+big /O/ expressions like __On__ or __Omlgn__ refere to container sizes
+/n/ and /m/. In this documentaion these sizes ['*do not*] refer
+to the familiar `size` function that returns
+the ['*number of elements*] of a container. Because for an interval container
+``
+interval_set<int> mono;
+mono += interval<int>(1,5); // {[1 ... 5]}
+mono.size() == 5; // true, 5 elements
+mono.interval_count() == 1; // true, only one interval
+``
+
+it's size and the number of contained intervals is usually different.
+To refer uniformely to a /size/ that matters for iteration, which is
+the decisive kind of size concering algorithmic behavior there is a function
+``
+bool T::iterative_size()const; // Number of entities that can be iterated over.
+``
+for all element and interval containers of the itl. So for
+complexity statements throughout the itl's documentation
+the sizes will be `iterative_sizes` and big /O/ expressions like
+__Omlgn__ will refer to sizes
+``
+n = y.iterative_size();
+m = x.iterative_size();
+``
+for containers `y` and `x`.
+
+[endsect][/ Iterative size]
+
+
+[section Complexity]
[h4 Complexity of element containers]
@@ -35,32 +81,20 @@
[h4 Complexity of interval containers]
-The operations of ['interval containers] behave differently
+The operations on ['interval containers] behave differently
due to the fact that intervals unlike elements can overlap
-any number of other intervals in a container. So as long as
+any number of other intervals in a container. As long as
intervals are relatively small or just singleton, interval
containers behave like containers of elements.
-
-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]]
-]
+For large intervals however time consumption of operations
+on interval containers may be worse, because most or all
+intervals of a container may have to be visited.
+As an example, time complexity of __biLAddition__ on
+interval containers is briefly discussed.
+
+More information on ['*complexity characteristics*]
+of *itl's* functions is contained in section
+[link boost_itl.function_reference Function Reference]
[h5 Time Complexity of Addition]
@@ -68,8 +102,7 @@
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.
+The instance types of `T` are given as column headers.
Instances of type parameter `P` are denoted in
the second column.
The third column containes the specific kind of complexity statement.
@@ -129,59 +162,56 @@
If /m/ is small compared with /n/ and intervals in `operand`
are large, performance tends to be /linear/.
-[h5 Time Complexity of Subtraction]
+[endsect][/ Complexity]
-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& 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__] ]
-]
+[section Inplace and infix operators]
-For __spl_itv_sets__, subtraction of an interval reduces the
-__spl_itv_set_s__ size particularly in the worst case, where
-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__] ]
-]
+For the major operations /addition, subtraction, intersection/
+of *itl* containers and for /symmetric difference/
+inplace `operator`s `+= |=, -=, &=` and `^=`
+are provided.
+
+For every ['*inplace*] operator
+``
+T& operator o= (T& object, const P& operand)
+``
+the *itl* provides corresponding ['*infix*] operators.
+``
+T operator o (T object, const P& operand){ return object o= operand; }
+T operator o (const P& operand, T object){ return object o= operand; }
+``
+
+From this implementation of the infix `operator o`
+the compiler will hopefully use return value optimization
+[@http://en.wikipedia.org/wiki/Return_value_optimization (RVO)]
+creating no temporary object and performing one copy of
+the first argument `object`.
+
+[caution
+Compared to the /inplace/ `operator o=` every use of an
+/infix/ `operator o` requires ['*one extra copy*]
+of the first argument `object` that passes a container.]
+
+Use infix operators only, if
+
+* efficiency is not crucial, e.g. the containers copied are small.
+* a concise and short notation is more important than efficiency in your context.
+* you need the result of operator `o=` as a copy anyway.
+
+[h5 Time Complexity of infix `operators o`]
+
+The time complexity of all infix operators of the *itl*
+is biased by the extra copy of the `object` argument.
+So all infix `operators o` are at least
+/linear/ in `n = object.iterative_size()`.
+Taking this into account, the complexities of all
+infix operators can be determined
+from the corresponding inplace `operators o=` they depend
+on.
+
+[endsect][/ Inplace and infix operators]
-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]
+[endsect][/ Implementation]
Modified: sandbox/itl/libs/itl/doc/interface.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/interface.qbk (original)
+++ sandbox/itl/libs/itl/doc/interface.qbk 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -435,9 +435,8 @@
[/ interval itvset itvmap itl:set itl:map std:set std:map]
[[__biLConsCopyDest__] [ ] [ ] [ ] [ ] [ ] [ ] [ ]]
[[`T::T()`] [1] [1] [1] [1] [1] [1] [1]]
-[[`T::T(const T&)`] [A] [1] [1] [1] [1] [1] [1]]
-[[`T::T(const P&)`] [ ] [__eiS] [__bpM] [ ] [ ] [ ] [ ]]
-[[`T::T(...)`] [3] [ ] [ ] [3] [3] [3] [3]]
+[[`T::T(const P&)`] [A] [__eiS] [__bpM] [1] [1] [1] [1]]
+[/ JODO [`T::T(...)`] [3] [ ] [ ] [3] [3] [3] [3]]
[[`T& T::operator=(const P&)`] [A] [__S] [__M] [1] [1] [1] [1]]
[[`void T::swap(T&)`] [ ] [1] [1] [1] [1] [1] [1]]
Modified: sandbox/itl/libs/itl/doc/itl.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/itl.qbk (original)
+++ sandbox/itl/libs/itl/doc/itl.qbk 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -108,9 +108,17 @@
[def __es [link element_type *e*] [link itl_set_type *s*]]
[def __bM [link element_mapping_type *b*] [link interval_map_types *M*]]
[def __bm [link element_mapping_type *b*] [link itl_map_type *m*]]
+[def __ebm [link element_type *e*] [link element_mapping_type *b*] [link itl_map_type *m*]]
[def __eiS [link element_type *e*] [link interval_type *i*] [link interval_set_types *S*]]
[def __bpM [link element_mapping_type *b*] [link interval_mapping_type *p*] [link interval_map_types *M*]]
+[def __S1 [link ph_def_S1 *S1*]]
+[def __S2 [link ph_def_S2 *S2*]]
+[def __S3 [link ph_def_S3 *S3*]]
+
+[def __M1 [link ph_def_M1 *M1*]]
+[def __M3 [link ph_def_M3 *M3*]]
+
[def __eiS_phs__ [link element_type placeholders]]
[def __eiS_Phs__ [link element_type Placeholders]]
@@ -121,15 +129,19 @@
[def __biLConsCopyDest__ [link boost_itl.function_reference.construct__copy__destruct ['*Construct, copy, destruct*]]]
[def __biLContainedness__ [link boost_itl.function_reference.containment ['*Containedness*]]]
+[def __biLcontainedness__ [link boost_itl.function_reference.containment ['*containedness*]]]
[def __biLEquivsOrderings__ [link boost_itl.function_reference.equivalences_and_orderings ['*Equivalences and Orderings*]]]
[def __biLSize__ [link boost_itl.function_reference.size ['*Size*]]]
[def __biLRange__ [link boost_itl.function_reference.range ['*Range*]]]
[def __biLSelection__ [link boost_itl.function_reference.selection ['*Selection*]]]
[def __biLAddition__ [link boost_itl.function_reference.addition ['*Addition*]]]
[def __biLSubtraction__ [link boost_itl.function_reference.subtraction ['*Subtraction*]]]
+[def __biLsubtraction__ [link boost_itl.function_reference.subtraction ['*subtraction*]]]
[def __biLInsertion__ [link boost_itl.function_reference.insertion ['*Insertion*]]]
[def __biLErasure__ [link boost_itl.function_reference.erasure ['*Erasure*]]]
+[def __biLerasure__ [link boost_itl.function_reference.erasure ['*erasure*]]]
[def __biLIntersection__ [link boost_itl.function_reference.intersection ['*Intersection*]]]
+[def __biLintersection__ [link boost_itl.function_reference.intersection ['*intersection*]]]
[def __biLSymmetricDifference__ [link boost_itl.function_reference.symmetric_difference ['*Symmetric difference*]]]
[def __biLIteratorRelated__ [link boost_itl.function_reference.iterator_related ['*Iterator related*]]]
[def __biLStreaming__ [link boost_itl.function_reference.streaming__conversion ['*Streaming, conversion*]]]
@@ -157,6 +169,7 @@
[def __On__ ['O(n)]]
[def __Om__ ['O(m)]]
[def __Ok__ ['O(k)]]
+[def __Onpm__ ['O(n+m)]]
[def __Olgn__ ['O(log n)]]
[def __a_Olgn__ ['amortized\nO(log n)]]
[def __Onlgn__ ['O(n log n)]]
@@ -182,8 +195,8 @@
[include concepts.qbk]
[include semantics.qbk]
[include interface.qbk]
-[include functions.qbk]
[include implementation.qbk]
+[include functions.qbk]
[include acknowledgments.qbk]
[xinclude itldoc.xml]
Modified: sandbox/itl/libs/itl/test/fastest_interval_map_cases.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/fastest_interval_map_cases.hpp (original)
+++ sandbox/itl/libs/itl/test/fastest_interval_map_cases.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -37,6 +37,10 @@
{ interval_map_contains_4_bicremental_types<INTERVAL_MAP, bicremental_type_4, int>();}
BOOST_AUTO_TEST_CASE
+(fastest_itl_interval_map_contains_key_objects_4_bicremental_types)
+{ interval_map_contains_key_objects_4_bicremental_types<INTERVAL_MAP, bicremental_type_4, int>();}
+
+BOOST_AUTO_TEST_CASE
(fastest_itl_interval_map_operators_4_bicremental_types)
{ interval_map_operators_4_bicremental_types<INTERVAL_MAP, bicremental_type_5, int>();}
@@ -63,5 +67,10 @@
(fastest_itl_interval_map_set_4_bicremental_types)
{ interval_map_set_4_bicremental_types<INTERVAL_MAP, bicremental_type_3, int>();}
+BOOST_AUTO_TEST_CASE
+(fastest_itl_interval_map_inclusion_compare_4_bicremental_types)
+{ interval_map_inclusion_compare_4_bicremental_types<discrete_type_4, int, partial_absorber, INTERVAL_MAP>();}
+
+
#endif // __itl_fastest_interval_map_cases_hpp_JOFA_090702__
Modified: sandbox/itl/libs/itl/test/fastest_interval_map_mixed_/fastest_interval_map_mixed.cpp
==============================================================================
--- sandbox/itl/libs/itl/test/fastest_interval_map_mixed_/fastest_interval_map_mixed.cpp (original)
+++ sandbox/itl/libs/itl/test/fastest_interval_map_mixed_/fastest_interval_map_mixed.cpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -51,3 +51,12 @@
BOOST_AUTO_TEST_CASE
(fastest_itl_interval_map_mixed_equal_4_bicremental_types)
{ interval_map_mixed_equal_4_bicremental_types<bicremental_type_3, int>(); }
+
+BOOST_AUTO_TEST_CASE
+(fastest_itl_partial_interval_map_mixed_inclusion_compare_4_bicremental_types)
+{ partial_interval_map_mixed_inclusion_compare_4_bicremental_types<bicremental_type_4, int, partial_absorber>(); }
+
+BOOST_AUTO_TEST_CASE
+(fastest_itl_partial_interval_map_mixed_contains_4_bicremental_types)
+{ partial_interval_map_mixed_contains_4_bicremental_types<int, int, partial_absorber>(); }
+
Modified: sandbox/itl/libs/itl/test/fastest_itl_map_/fastest_itl_map_cases.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/fastest_itl_map_/fastest_itl_map_cases.hpp (original)
+++ sandbox/itl/libs/itl/test/fastest_itl_map_/fastest_itl_map_cases.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -12,4 +12,8 @@
(fastest_itl_itl_map_find_4_bicremental_types)
{ itl_map_find_4_bicremental_types<discrete_type_1, int, partial_absorber, INTERVAL_MAP>();}
+BOOST_AUTO_TEST_CASE
+(fastest_itl_itl_map_inclusion_compare_4_bicremental_types)
+{ itl_map_inclusion_compare_4_bicremental_types<discrete_type_1, int, partial_absorber, INTERVAL_MAP>();}
+
#endif // __itl_test_itl_map_cases_hpp_JOFA_090701__
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-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -24,6 +24,7 @@
#include <boost/itl/split_interval_map.hpp>
#include <boost/validate/type/nat.hpp>
+
using namespace std;
using namespace boost;
using namespace unit_test;
@@ -33,7 +34,9 @@
BOOST_AUTO_TEST_CASE(casual_test)
{
typedef int T;
- typedef itl::map<int,int> ItlMapT;
+ typedef int U;
+ typedef itl::map<int,int> ItlMapT;
+ typedef itl::set<int> ItlSetT;
typedef interval_map<int,int,partial_enricher> IntervalMapT;
typedef split_interval_map<int,int> SplitIntervalMapT;
typedef interval_set<int> IntervalSetT;
@@ -41,4 +44,52 @@
const bool test = is_same<SplitIntervalSetT::key_type, SplitIntervalSetT::interval_type>::value;
BOOST_CHECK_EQUAL(test, true);
+
+ SplitIntervalSetT spliss;
+ spliss.add(I_D(1,3)).add(I_D(3,4)).add(I_D(4,6)).add(I_D(6,8));
+ spliss.contains(I_D(2,5));
+ BOOST_CHECK_EQUAL(spliss.contains(I_D(2,7)), true);
+
+
+ ItlMapT map_a(make_pair(1,1));
+ ItlSetT set_a(1);
+ map_a.add(make_pair(2,1));
+ set_a.add(2);
+ bool its = Map::intersects(map_a, map_a);
+
+ erase(map_a, set_a);
+ BOOST_CHECK_EQUAL(erase(map_a, set_a), ItlMapT());
+ BOOST_CHECK_EQUAL(erase(map_a, map_a), ItlMapT());
+
+ itl::map<int,int,total_absorber> tomp_a, tomp_b, tomp_c;
+ tomp_a.add(make_pair(1,1)).add(make_pair(2,1));
+
+ BOOST_CHECK_EQUAL((tomp_a & tomp_b).empty(), false);
+ BOOST_CHECK_EQUAL((tomp_b & tomp_c).empty(), true);
+
+ interval_map<int, interval_set<int> > maose, maose2;
+ interval_set<int> inse;
+ inse.add(I_I(1,4));
+
+ maose.add(make_pair(I_I(1,4), inse));
+ maose2 = maose;
+ maose2.add(make_pair(I_I(5,6), inse));
+
+
+ BOOST_CHECK_EQUAL(maose2.contains(maose), true);
+
+ itl::set<int> eleset_a, eleset_a2, eleset_b, eleset_c;
+ //eleset_a.add(1).add(2).add(5).add(8).add(11);
+ eleset_a.add(8).add(11);
+ eleset_a2 = eleset_a;
+ eleset_b.add(8).add(2).add(11);
+ eleset_c.add(9);
+
+ //BOOST_CHECK_EQUAL(Set::inclusion_compare(eleset_a, eleset_a2), inclusion::equal);
+ //BOOST_CHECK_EQUAL(Set::inclusion_compare(eleset_a, eleset_b), inclusion::superset);
+ //BOOST_CHECK_EQUAL(Set::inclusion_compare(eleset_b, eleset_a), inclusion::subset);
+
+ inclusion_compare(eleset_a, eleset_c);
+ BOOST_CHECK_EQUAL(inclusion_compare(eleset_a, eleset_c), inclusion::unrelated);
+
}
Modified: sandbox/itl/libs/itl/test/test_interval_map_cases.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_map_cases.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_map_cases.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -37,6 +37,10 @@
{ interval_map_contains_4_bicremental_types<INTERVAL_MAP, T, int>();}
BOOST_AUTO_TEST_CASE_TEMPLATE
+(test_itl_interval_map_contains_key_objects_4_bicremental_types, T, bicremental_types)
+{ interval_map_contains_key_objects_4_bicremental_types<INTERVAL_MAP, T, int>();}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE
(test_itl_interval_map_operators_4_bicremental_types, T, bicremental_types)
{ interval_map_operators_4_bicremental_types<INTERVAL_MAP, T, int>();}
@@ -63,5 +67,9 @@
(test_itl_interval_map_set_4_bicremental_types, T, bicremental_types)
{ interval_map_set_4_bicremental_types<INTERVAL_MAP, T, int>();}
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(test_itl_interval_map_inclusion_compare_4_bicremental_types, T, bicremental_types)
+{ interval_map_inclusion_compare_4_bicremental_types<T, int, partial_absorber, INTERVAL_MAP>();}
+
#endif // __itl_test_interval_map_cases_hpp_JOFA_090701__
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-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -201,6 +201,249 @@
}
+template <class T, class U, class Trt>
+void partial_interval_map_mixed_inclusion_compare_4_bicremental_types()
+{
+ typedef interval_map<T,U,Trt> IntervalMapT;
+ //--------------------------------------------------------------------------
+ // equalities
+ // { 0 1 2 3 4 5 8 9 }
+ // {[0,2)[2,3](3,6) (7,9]}
+ // ->2 ->1 ->1 ->2
+ split_interval_map<T,U,Trt> split_map;
+ interval_map<T,U,Trt> join_map;
+ split_interval_set<T> split_set;
+ separate_interval_set<T> sep_set;
+ interval_set<T> join_set;
+
+ split_map.add(IDv(0,2,2)).add(IIv(2,3,1)).add(CDv(3,6,1)).add(CIv(7,9,2));
+ join_map = split_map;
+ split_map.domain(split_set);
+ split_map.domain(sep_set);
+ split_map.domain(join_set);
+
+ BOOST_CHECK_EQUAL( split_map.iterative_size(), 4 );
+ BOOST_CHECK_EQUAL( join_map.iterative_size(), 3 );
+ BOOST_CHECK_EQUAL( split_set.iterative_size(), 4 );
+ BOOST_CHECK_EQUAL( sep_set.iterative_size(), 4 );
+ BOOST_CHECK_EQUAL( join_set.iterative_size(), 2 );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(split_map, join_map), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(join_map, split_map), inclusion::equal );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(split_map, split_set), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(split_map, sep_set ), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(split_map, join_set ), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(join_map , split_set), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(join_map , sep_set ), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(join_map , join_set ), inclusion::equal );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(split_set, split_map), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(sep_set , split_map), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(join_set , split_map), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(split_set, join_map ), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(sep_set , join_map ), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(join_set , join_map ), inclusion::equal );
+
+ //--------------------------------------------------------------------------
+ // inclusions
+ // { 0 1 2 3 4 5 8 9 }
+ // {[0, 2)[2, 3](3, 6) (7, 9]}
+ // ->2 ->1 ->1 ->2
+ // {[0, 2) [3,3](3, 6) (7, 9]}
+ // ->2 ->1 ->1 ->2
+ split_interval_map<T,U,Trt> split_sub_map1 = split_map;
+ split_sub_map1.erase(MK_v(2));
+ BOOST_CHECK_EQUAL( split_sub_map1.contains(MK_v(2)), false );
+
+ interval_map<T,U,Trt> join_sub_map2;
+ join_sub_map2 = split_map;
+ join_sub_map2.erase(MK_v(1));
+ BOOST_CHECK_EQUAL( join_sub_map2.contains(MK_v(1)), false );
+
+ split_interval_set<T> split_sub_set1;
+ separate_interval_set<T> sep_sub_set1;
+ interval_set<T> join_sub_set1;
+
+ split_sub_map1.domain(split_sub_set1);
+ split_sub_map1.domain(sep_sub_set1);
+ split_sub_map1.domain(join_sub_set1);
+
+ BOOST_CHECK_EQUAL( inclusion_compare(split_sub_map1, split_map), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_sub_map2, split_map), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare(split_sub_map1, join_map), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_sub_map2, join_map), inclusion::subset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(split_sub_set1, split_map), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare( sep_sub_set1, split_map), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_sub_set1, split_map), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare(split_sub_set1, join_map), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare( sep_sub_set1, join_map), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_sub_set1, join_map), inclusion::subset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(split_map, split_sub_map1), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare(split_map, join_sub_map2), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_map, split_sub_map1), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_map, join_sub_map2), inclusion::superset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(split_map, split_sub_set1), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare(split_map, sep_sub_set1), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare(split_map, join_sub_set1), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_map, split_sub_set1), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_map, sep_sub_set1), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_map, join_sub_set1), inclusion::superset );
+
+ split_interval_map<T,U,Trt> split_unrel_map11 = split_sub_map1;
+ split_unrel_map11.set(CIv(7,9,1));
+ BOOST_CHECK_EQUAL( split_unrel_map11(MK_v(8)), MK_u(1) );
+
+ interval_map<T,U,Trt> join_unrel_map21 = join_sub_map2;
+ join_unrel_map21.set(K_v(0,1));
+ BOOST_CHECK_EQUAL( join_unrel_map21(MK_v(0)), MK_u(1) );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(split_unrel_map11, split_map), inclusion::unrelated );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_unrel_map21, split_map), inclusion::unrelated );
+ BOOST_CHECK_EQUAL( inclusion_compare(split_unrel_map11, join_map), inclusion::unrelated );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_unrel_map21, join_map), inclusion::unrelated );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(split_map, split_unrel_map11), inclusion::unrelated );
+ BOOST_CHECK_EQUAL( inclusion_compare(split_map, join_unrel_map21), inclusion::unrelated );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_map, split_unrel_map11), inclusion::unrelated );
+ BOOST_CHECK_EQUAL( inclusion_compare( join_map, join_unrel_map21), inclusion::unrelated );
+
+ split_interval_map<T,U,Trt> split_unrel_map1 = split_sub_map1;
+ split_unrel_map1.add(IDv(11,12,1));
+ BOOST_CHECK_EQUAL( split_unrel_map1(MK_v(11)), MK_u(1) );
+
+ interval_map<T,U,Trt> join_unrel_map2 = join_sub_map2;
+ join_unrel_map2.add(K_v(6,1));
+ BOOST_CHECK_EQUAL( join_unrel_map2(MK_v(6)), MK_u(1) );
+}
+
+
+template <class T, class U, class Trt>
+void partial_interval_map_mixed_contains_4_bicremental_types()
+{
+ typedef interval_map<T,U,Trt> IntervalMapT;
+ //--------------------------------------------------------------------------
+ // { 0 1 2 3 4 5 8 9 }
+ // {[0,2)[2,3](3,6) (7,9]}
+ // ->2 ->1 ->1 ->2
+ split_interval_map<T,U,Trt> split_map;
+ interval_map<T,U,Trt> join_map;
+ split_interval_set<T> split_set;
+ separate_interval_set<T> sep_set;
+ interval_set<T> join_set;
+
+ split_map.add(IDv(0,2,2)).add(IIv(2,3,1)).add(CDv(3,6,1)).add(CIv(7,9,2));
+ join_map = split_map;
+ split_map.domain(split_set);
+ split_map.domain(sep_set);
+ split_map.domain(join_set);
+
+ BOOST_CHECK_EQUAL( split_map.iterative_size(), 4 );
+ BOOST_CHECK_EQUAL( join_map.iterative_size(), 3 );
+ BOOST_CHECK_EQUAL( split_set.iterative_size(), 4 );
+ BOOST_CHECK_EQUAL( sep_set.iterative_size(), 4 );
+ BOOST_CHECK_EQUAL( join_set.iterative_size(), 2 );
+
+ // Key types
+ BOOST_CHECK_EQUAL( split_map.contains(MK_v(0)), true );
+ BOOST_CHECK_EQUAL( split_map.contains(MK_v(5)), true );
+ BOOST_CHECK_EQUAL( split_map.contains(MK_v(9)), true );
+
+ BOOST_CHECK_EQUAL( split_map.contains(I_D(2,3)), true );
+ BOOST_CHECK_EQUAL( split_map.contains(I_D(0,6)), true );
+ BOOST_CHECK_EQUAL( split_map.contains(I_D(0,7)), false );
+ BOOST_CHECK_EQUAL( join_map.contains(I_D(2,3)), true );
+ BOOST_CHECK_EQUAL( join_map.contains(I_D(0,6)), true );
+ BOOST_CHECK_EQUAL( join_map.contains(I_D(0,7)), false );
+
+ // Map types
+ BOOST_CHECK_EQUAL( join_map.contains(K_v(1,2)), true );
+ BOOST_CHECK_EQUAL( join_map.contains(K_v(5,1)), true );
+ BOOST_CHECK_EQUAL( join_map.contains(K_v(9,2)), true );
+
+ BOOST_CHECK_EQUAL( split_map.contains(IDv(2,6,1)), true );
+ BOOST_CHECK_EQUAL( split_map.contains(IDv(1,6,1)), false );
+ BOOST_CHECK_EQUAL( split_map.contains(IIv(8,9,2)), true );
+ BOOST_CHECK_EQUAL( split_map.contains(IIv(8,9,3)), false );
+ BOOST_CHECK_EQUAL( join_map.contains(IDv(2,6,1)), true );
+ BOOST_CHECK_EQUAL( join_map.contains(IDv(1,6,1)), false );
+ BOOST_CHECK_EQUAL( join_map.contains(IIv(8,9,2)), true );
+ BOOST_CHECK_EQUAL( join_map.contains(IIv(8,9,3)), false );
+
+ BOOST_CHECK_EQUAL( split_map.contains(join_map), true );
+ BOOST_CHECK_EQUAL( join_map.contains(split_map), true );
+ BOOST_CHECK_EQUAL( split_map.contained_in(join_map), true );
+ BOOST_CHECK_EQUAL( join_map.contained_in(split_map), true );
+
+ //--------------------------------------------------------------------------
+ // inclusions
+ // { 0 1 2 3 4 5 8 9 }
+ // {[0, 2)[2, 3](3, 6) (7, 9]}
+ // ->2 ->1 ->1 ->2
+ // {[0, 2) [3,3](3, 6) (7, 9]}
+ // ->2 ->1 ->1 ->2
+ split_interval_map<T,U,Trt> split_sub_map1 = split_map;
+ split_sub_map1.erase(MK_v(2));
+ BOOST_CHECK_EQUAL( split_sub_map1.contains(MK_v(2)), false );
+
+ interval_map<T,U,Trt> join_sub_map2;
+ join_sub_map2 = split_map;
+ join_sub_map2.erase(MK_v(1));
+ BOOST_CHECK_EQUAL( join_sub_map2.contains(MK_v(1)), false );
+
+ split_interval_set<T> split_sub_set1;
+ separate_interval_set<T> sep_sub_set1;
+ interval_set<T> join_sub_set1;
+
+ split_sub_map1.domain(split_sub_set1);
+ split_sub_map1.domain(sep_sub_set1);
+ split_sub_map1.domain(join_sub_set1);
+
+ BOOST_CHECK_EQUAL( split_sub_map1.contained_in(split_map), true );
+ BOOST_CHECK_EQUAL( join_sub_map2.contained_in(split_map), true );
+ BOOST_CHECK_EQUAL( split_sub_map1.contained_in(join_map ), true );
+ BOOST_CHECK_EQUAL( join_sub_map2.contained_in(join_map ), true );
+
+ BOOST_CHECK_EQUAL( split_map.contains(split_sub_map1), true );
+ BOOST_CHECK_EQUAL( split_map.contains( join_sub_map2), true );
+ BOOST_CHECK_EQUAL( join_map.contains(split_sub_map1), true );
+ BOOST_CHECK_EQUAL( join_map.contains( join_sub_map2), true );
+
+ BOOST_CHECK_EQUAL( split_map.contains(split_sub_set1), true );
+ BOOST_CHECK_EQUAL( split_map.contains( sep_sub_set1), true );
+ BOOST_CHECK_EQUAL( split_map.contains( join_sub_set1), true );
+ BOOST_CHECK_EQUAL( join_map.contains(split_sub_set1), true );
+ BOOST_CHECK_EQUAL( join_map.contains( sep_sub_set1), true );
+ BOOST_CHECK_EQUAL( join_map.contains( join_sub_set1), true );
+
+ split_interval_map<T,U,Trt> split_unrel_map11 = split_sub_map1;
+ split_unrel_map11.set(CIv(7,9,1));
+ BOOST_CHECK_EQUAL( split_unrel_map11(MK_v(8)), MK_u(1) );
+
+ interval_map<T,U,Trt> join_unrel_map21 = join_sub_map2;
+ join_unrel_map21.set(K_v(0,1));
+ BOOST_CHECK_EQUAL( join_unrel_map21(MK_v(0)), MK_u(1) );
+
+ BOOST_CHECK_EQUAL( split_unrel_map11.contains(split_map), false );
+ BOOST_CHECK_EQUAL( join_unrel_map21.contains(split_map), false );
+ BOOST_CHECK_EQUAL( split_unrel_map11.contains( join_map), false );
+ BOOST_CHECK_EQUAL( join_unrel_map21.contains( join_map), false );
+
+ BOOST_CHECK_EQUAL( split_unrel_map11.contained_in(split_map), false );
+ BOOST_CHECK_EQUAL( join_unrel_map21.contained_in(split_map), false );
+ BOOST_CHECK_EQUAL( split_unrel_map11.contained_in( join_map), false );
+ BOOST_CHECK_EQUAL( join_unrel_map21.contained_in( join_map), false );
+
+ BOOST_CHECK_EQUAL( split_map.contains(split_unrel_map11), false );
+ BOOST_CHECK_EQUAL( split_map.contains( join_unrel_map21), false );
+ BOOST_CHECK_EQUAL( join_map.contains(split_unrel_map11), false );
+ BOOST_CHECK_EQUAL( join_map.contains( join_unrel_map21), false );
+
+}
+
//------------------------------------------------------------------------------
//- part2: Operations
//------------------------------------------------------------------------------
Modified: sandbox/itl/libs/itl/test/test_interval_map_mixed_/test_interval_map_mixed.cpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_map_mixed_/test_interval_map_mixed.cpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_map_mixed_/test_interval_map_mixed.cpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -26,191 +26,37 @@
using namespace unit_test;
using namespace boost::itl;
+#include "../test_interval_map_mixed.hpp"
-BOOST_AUTO_TEST_CASE_TEMPLATE(test_itl_interval_map_mixed_ctor_4_ordered_types, T, ordered_types)
-{
- typedef int U;
- typedef interval_map<T,U> IntervalMapT;
- typedef split_interval_map<T,U> SplitIntervalMapT;
-
- T v0 = neutron<T>::value();
- U u1 = unon<U>::value();
-
- SplitIntervalMapT split_map(make_pair(v0,u1));
- IntervalMapT join_map(split_map);
-
- BOOST_CHECK_EQUAL( split_map.lower(), join_map.lower() );
- BOOST_CHECK_EQUAL( split_map.upper(), join_map.upper() );
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(test_itl_interval_map_mixed_equal_4_ordered_types, T, ordered_types)
-{
- typedef int U;
- typedef interval_map<T,U> IntervalMapT;
- typedef split_interval_map<T,U> SplitIntervalMapT;
-
- T v0 = neutron<T>::value();
- U u1 = unon<U>::value();
-
- SplitIntervalMapT split_empty, split_single(make_pair(v0,u1));
- IntervalMapT join_empty, join_single(make_pair(v0,u1));
-
- // mixed ==-equality is a strange thing. Most times is does not
- // make sense. It is better to allow only for same type == equality.
- BOOST_CHECK_EQUAL( split_empty == split_empty, true );
- BOOST_CHECK_EQUAL( join_empty == join_empty, true );
-
- // There were Problems with operator== and emtpy sets.
- BOOST_CHECK_EQUAL( split_empty == split_single, false );
- BOOST_CHECK_EQUAL( join_empty == join_single, false );
-
- BOOST_CHECK_EQUAL( split_single == split_empty, false );
- BOOST_CHECK_EQUAL( join_single == join_empty, false );
-
- BOOST_CHECK_EQUAL( is_element_equal(split_empty, split_empty), true );
- BOOST_CHECK_EQUAL( is_element_equal(split_empty, join_empty), true );
-
- BOOST_CHECK_EQUAL( is_element_equal(join_empty, split_empty), true );
- BOOST_CHECK_EQUAL( is_element_equal(join_empty, join_empty), true );
-
- //--------------------------------------------------------------------------
- BOOST_CHECK_EQUAL( is_element_equal(split_empty, split_single), false );
- BOOST_CHECK_EQUAL( is_element_equal(split_empty, join_single), false );
-
- BOOST_CHECK_EQUAL( is_element_equal(join_empty, split_single), false );
- BOOST_CHECK_EQUAL( is_element_equal(join_empty, join_single), false );
-
- BOOST_CHECK_EQUAL( is_element_equal(split_single, split_empty), false );
- BOOST_CHECK_EQUAL( is_element_equal(split_single, join_empty), false );
-
- BOOST_CHECK_EQUAL( is_element_equal(join_single, split_empty), false );
- BOOST_CHECK_EQUAL( is_element_equal(join_single, join_empty), false );
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(test_itl_interval_map_mixed_assign_4_ordered_types, T, ordered_types)
-{
- typedef int U;
- typedef interval_map<T,U> IntervalMapT;
- typedef split_interval_map<T,U> SplitIntervalMapT;
-
- T v0 = neutron<T>::value();
- T v1 = unon<T>::value();
- U u1 = unon<U>::value();
-
- mapping_pair<T,U> v0_u1(v0,u1);
- mapping_pair<T,U> v1_u1(v1,u1);
-
- SplitIntervalMapT split_map;
- IntervalMapT join_map;
- split_map.add(v0_u1); //NOTE: make_pair(v0,u1); fails
- join_map = split_map; //=t T& T::operator=(const P&) ...
-
-
- BOOST_CHECK_EQUAL( split_map.lower(), join_map.lower() );
- BOOST_CHECK_EQUAL( split_map.upper(), join_map.upper() );
-
- SplitIntervalMapT split_self = SplitIntervalMapT().add(v0_u1);
- IntervalMapT join_self = IntervalMapT().add(v1_u1);
-
- split_self = split_self;
- join_self = join_self;
-
- BOOST_CHECK_EQUAL( split_self, split_self );
- BOOST_CHECK_EQUAL( join_self, join_self );
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(test_itl_interval_map_mixed_ctor_4_bicremental_types, T, bicremental_types)
-{
- typedef int U;
- typedef interval_map<T,U> IntervalMapT;
- typedef split_interval_map<T,U> SplitIntervalMapT;
- U u1 = make<U>(1);
- T v1 = make<T>(1);
- T v2 = make<T>(2);
- T v3 = make<T>(3);
- T v4 = make<T>(4);
- T v5 = make<T>(5);
-
-
- interval<T> I1_3D = interval<T>::rightopen(v1,v3);
- interval<T> I2_4D = interval<T>::rightopen(v2,v4);
- interval<T> I4_5D = interval<T>::rightopen(v4,v5);
-
- std::pair<interval<T>,U> I1_3D_1(I1_3D, u1);
- std::pair<interval<T>,U> I2_4D_1(I2_4D, u1);
- std::pair<interval<T>,U> I4_5D_1(I4_5D, u1);
-
- SplitIntervalMapT split_map;
- split_map.add(I1_3D_1).add(I2_4D_1).add(I4_5D_1);
- BOOST_CHECK_EQUAL( split_map.iterative_size(), 4 );
- IntervalMapT join_map(split_map);
-}
-
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(test_itl_interval_map_mixed_assign_4_bicremental_types, T, bicremental_types)
-{
- typedef int U;
- typedef interval_map<T,U> IntervalMapT;
- typedef split_interval_map<T,U> SplitIntervalMapT;
- U u1 = make<U>(1);
-
- T v1 = make<T>(1);
- T v2 = make<T>(2);
- T v3 = make<T>(3);
- T v4 = make<T>(4);
- T v5 = make<T>(5);
-
- interval<T> I1_3D = interval<T>::rightopen(v1,v3);
- interval<T> I2_4D = interval<T>::rightopen(v2,v4);
- interval<T> I4_5D = interval<T>::rightopen(v4,v5);
-
- std::pair<interval<T>,U> I1_3D_1(I1_3D, u1);
- std::pair<interval<T>,U> I2_4D_1(I2_4D, u1);
- std::pair<interval<T>,U> I4_5D_1(I4_5D, u1);
-
- SplitIntervalMapT split_map;
- split_map.add(I1_3D_1).add(I2_4D_1).add(I4_5D_1);
- BOOST_CHECK_EQUAL( split_map.iterative_size(), 4 );
- IntervalMapT join_map;
- join_map = split_map;
- BOOST_CHECK_EQUAL( join_map.iterative_size(), 3 );
-}
-
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(test_itl_interval_map_mixed_equal_4_bicremental_types, T, bicremental_types)
-{
- typedef int U;
- typedef interval_map<T,U> IntervalMapT;
- typedef split_interval_map<T,U> SplitIntervalMapT;
- U u1 = make<U>(1);
-
- T v1 = make<T>(1);
- T v2 = make<T>(2);
- T v3 = make<T>(3);
- T v4 = make<T>(4);
- T v5 = make<T>(5);
-
- interval<T> I1_3D = interval<T>::rightopen(v1,v3);
- interval<T> I2_4D = interval<T>::rightopen(v2,v4);
- interval<T> I4_5D = interval<T>::rightopen(v4,v5);
-
- std::pair<interval<T>,U> I1_3D_1(I1_3D, u1);
- std::pair<interval<T>,U> I2_4D_1(I2_4D, u1);
- std::pair<interval<T>,U> I4_5D_1(I4_5D, u1);
-
- IntervalMapT join_map;
- join_map.add(I1_3D_1).add(I2_4D_1).add(I4_5D_1);
- IntervalMapT join_map2 = join_map;
- BOOST_CHECK_EQUAL( join_map, join_map2 );
- BOOST_CHECK_EQUAL( is_element_equal(join_map, join_map2), true );
-
- SplitIntervalMapT split_map;
- split_map.add(I1_3D_1).add(I2_4D_1).add(I4_5D_1);
- SplitIntervalMapT split_map2 = split_map;
- BOOST_CHECK_EQUAL( split_map, split_map2 );
- BOOST_CHECK_EQUAL( is_element_equal(split_map2, split_map), true );
-
- BOOST_CHECK_EQUAL( is_element_equal(split_map, join_map), true );
- BOOST_CHECK_EQUAL( is_element_equal(join_map, split_map), true );
-}
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(fastest_itl_interval_map_mixed_ctor_4_ordered_types, T, ordered_types)
+{ interval_map_mixed_ctor_4_ordered_types<T, int>(); }
+
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(fastest_itl_interval_map_mixed_equal_4_ordered_types, T, ordered_types)
+{ interval_map_mixed_equal_4_ordered_types<T, int>(); }
+
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(fastest_itl_interval_map_mixed_assign_4_ordered_types, T, ordered_types)
+{ interval_map_mixed_assign_4_ordered_types<T, int>(); }
+
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(fastest_itl_interval_map_mixed_ctor_4_bicremental_types, T, bicremental_types)
+{ interval_map_mixed_ctor_4_bicremental_types<T, int>(); }
+
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(fastest_itl_interval_map_mixed_assign_4_bicremental_types, T, bicremental_types)
+{ interval_map_mixed_assign_4_bicremental_types<T, int>(); }
+
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(fastest_itl_interval_map_mixed_equal_4_bicremental_types, T, bicremental_types)
+{ interval_map_mixed_equal_4_bicremental_types<T, int>(); }
+
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(fastest_itl_partial_interval_map_mixed_inclusion_compare_4_bicremental_types, T, bicremental_types)
+{ partial_interval_map_mixed_inclusion_compare_4_bicremental_types<T, int, partial_absorber>(); }
+
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(fastest_itl_partial_interval_map_mixed_contains_4_bicremental_types, T, bicremental_types)
+{ partial_interval_map_mixed_contains_4_bicremental_types<T, int, partial_absorber>(); }
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-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -422,38 +422,63 @@
void interval_map_contains_4_bicremental_types()
{
typedef IntervalMap<T,U> IntervalMapT;
- //LAW: x.add(e).contains(e); //false!
- //LAW: x.insert(e).contains(e); //??
- T v3 = make<T>(3);
- T v5 = make<T>(5);
- T v7 = make<T>(7);
- T v8 = make<T>(8);
- T v9 = make<T>(9);
- T v11 = make<T>(11);
- U u1 = make<U>(1);
-
- typename IntervalMapT::domain_mapping_type v3_u1(v3,u1);
- typename IntervalMapT::domain_mapping_type v9_u1(v9,u1);
- typename IntervalMapT::domain_mapping_type v11_u1(v11,u1);
-
- typename IntervalMapT::value_type I3_7I_u1(interval<T>(v3,v7),u1);
- IntervalMapT im(v3_u1);
- BOOST_CHECK_EQUAL( im.contains(v3_u1), true );
-
- BOOST_CHECK_EQUAL( IntervalMapT().add(v3_u1).contains(v3_u1), true );
- BOOST_CHECK_EQUAL( IntervalMapT().insert(v3_u1).contains(v3_u1), true );
- im.clear();
- BOOST_CHECK_EQUAL( (im += I3_7I_u1).contains(I3_7I_u1), true );
-
- IntervalMapT im0 = im;
-
- im.clear();
- IntervalMapT im2(typename IntervalMapT::value_type(interval<T>::closed(v5,v8),u1));
- im2.add(v9_u1).add(v11_u1);
- im += im2;
- BOOST_CHECK_EQUAL( im.contains(im2), true );
+ IntervalMapT itv_map(K_v(3,1));
+ BOOST_CHECK_EQUAL( itv_map.contains(K_v(3,1)), true );
+
+ BOOST_CHECK_EQUAL( IntervalMapT().add(K_v(3,1)).contains(K_v(3,1)), true );
+ BOOST_CHECK_EQUAL( IntervalMapT().insert(K_v(3,1)).contains(K_v(3,1)), true );
+ itv_map.clear();
+ BOOST_CHECK_EQUAL( (itv_map += IIv(3,7,1)).contains(IIv(3,7,1)), true );
+
+ IntervalMapT itv_map0 = itv_map;
+
+ itv_map.clear();
+ IntervalMapT itv_map2(IIv(5,8,1));
+ itv_map2.add(K_v(9,1)).add(K_v(11,1));
+ itv_map += itv_map2;
+ BOOST_CHECK_EQUAL( itv_map.contains(itv_map2), true );
+}
+
+template <template<class T, class U,
+ class Traits = partial_absorber,
+ ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, U),
+ ITL_COMBINE Combine = ITL_COMBINE_INSTANCE(itl::inplace_plus, U),
+ ITL_SECTION Section = ITL_SECTION_INSTANCE(itl::inplace_et, U),
+ template<class,ITL_COMPARE>class Interval = interval,
+ ITL_ALLOC Alloc = std::allocator
+ >class IntervalMap,
+ class T, class U>
+void interval_map_contains_key_objects_4_bicremental_types()
+{
+ typedef IntervalMap<T,U> IntervalMapT;
+ typedef typename IntervalMapT::set_type IntervalSetT;
+ IntervalMapT itv_map;
+
+ itv_map.add(IDv(1,3,1));
+ BOOST_CHECK_EQUAL( itv_map.contains(MK_v(0)), false );
+ BOOST_CHECK_EQUAL( itv_map.contains(MK_v(2)), true );
+ BOOST_CHECK_EQUAL( itv_map.contains(MK_v(3)), false );
+
+ itv_map.add(IDv(3,6,2));
+ BOOST_CHECK_EQUAL( itv_map.contains(I_I(0,0)), false );
+ BOOST_CHECK_EQUAL( itv_map.contains(I_I(2,4)), true );
+ BOOST_CHECK_EQUAL( itv_map.contains(I_I(6,6)), false );
+
+ itv_map.add(IDv(8,9,2));
+
+ IntervalSetT itv_set;
+ itv_set.add(C_I(1,2)).add(C_D(2,6)).add(I_I(8,8));
+ BOOST_CHECK_EQUAL( itv_map.contains(itv_set), true );
+ itv_set.add(I_I(1,4));
+ BOOST_CHECK_EQUAL( itv_map.contains(itv_set), true );
+ itv_set.add(I_I(1,4));
+ BOOST_CHECK_EQUAL( itv_map.contains(itv_set), true );
+ itv_set.add(I_I(7,7));
+ BOOST_CHECK_EQUAL( itv_map.contains(itv_set), false );
+
}
+
template <template<class T, class U,
class Traits = partial_absorber,
ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, U),
@@ -1069,5 +1094,79 @@
BOOST_CHECK_EQUAL( map_a.set(K_v(4,5)).set(CDv(3,5,6)).contains(CDv(3,5,6)), true );
}
+
+template <class T, class U, class Trt,
+ template<class T, class U,
+ class Traits = Trt,
+ ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, U),
+ ITL_COMBINE Combine = ITL_COMBINE_INSTANCE(itl::inplace_plus, U),
+ ITL_SECTION Section = ITL_SECTION_INSTANCE(itl::inplace_et, U),
+ template<class,ITL_COMPARE>class Interval = interval,
+ ITL_ALLOC Alloc = std::allocator
+ >class IntervalMap
+ >
+void interval_map_inclusion_compare_4_bicremental_types()
+{
+ typedef IntervalMap<T,U,Trt> IntervalMapT;
+ typedef typename IntervalMap<T,U,Trt>::set_type IntervalSetT;
+ typedef itl::map<T,U,Trt> MapT;
+ typedef itl::set<T> SetT;
+
+ IntervalMapT itv_map_sub_a, itv_map_a, itv_map_a2, itv_map_super_a,
+ itv_map_b, itv_map_c;
+ itv_map_sub_a.add(IDv(2,4,1)).add(IIv(6,7,3));
+ itv_map_a = itv_map_sub_a;
+ itv_map_a.add(IIv(9,9,1));
+ itv_map_a2 = itv_map_a;
+ itv_map_c = itv_map_sub_a;
+ itv_map_c.erase(MK_v(7)).add(IIv(11,11,2));
+ itv_map_b = itv_map_a;
+ itv_map_b.set(IIv(6,7,2));
+
+
+ BOOST_CHECK_EQUAL( inclusion_compare(IntervalMapT(), IntervalMapT()), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, itv_map_a), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, itv_map_a2), inclusion::equal );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, IntervalMapT()), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, itv_map_sub_a), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare(IntervalMapT(), itv_map_a), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare(itv_map_sub_a, itv_map_a), inclusion::subset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, itv_map_b), inclusion::unrelated );
+ BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, itv_map_c), inclusion::unrelated );
+
+ IntervalSetT set_sub_a, set_a, set_a2, set_b, set_c;
+ itv_map_a.domain(set_a);
+ itv_map_a2.domain(set_a2);
+ itv_map_sub_a.domain(set_sub_a);
+
+ BOOST_CHECK_EQUAL( inclusion_compare(IntervalMapT(), IntervalSetT()), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(IntervalSetT(), IntervalMapT()), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(IntervalSetT(), IntervalSetT()), inclusion::equal );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, set_a), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(set_a, itv_map_a), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(set_a, set_a2), inclusion::equal );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, IntervalSetT()), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, set_sub_a), inclusion::superset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(IntervalSetT(), itv_map_a), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare(set_sub_a, itv_map_a), inclusion::subset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(set_a, IntervalSetT()), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare(set_a, set_sub_a), inclusion::superset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(IntervalSetT(), set_a), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare(set_sub_a, set_a), inclusion::subset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(set_a, itv_map_c), inclusion::unrelated );
+ BOOST_CHECK_EQUAL( inclusion_compare(itv_map_c, set_a), inclusion::unrelated );
+
+}
+
+
+
#endif // __test_itl_interval_map_shared_h_JOFA_080920__
Modified: sandbox/itl/libs/itl/test/test_itl_map.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_itl_map.hpp (original)
+++ sandbox/itl/libs/itl/test/test_itl_map.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -9,9 +9,6 @@
#define __test_itl_itl_map_h_JOFA_090119__
-//------------------------------------------------------------------------------
-// Monoid EAN
-//------------------------------------------------------------------------------
template <class T, class U, class Trt,
template<class T, class U,
class Traits = Trt,
@@ -44,5 +41,82 @@
BOOST_CHECK_EQUAL( map_a(MK_v(5)), MK_u(0) );
}
+
+template <class T, class U, class Trt,
+ template<class T, class U,
+ class Traits = Trt,
+ ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, U),
+ ITL_COMBINE Combine = ITL_COMBINE_INSTANCE(itl::inplace_plus, U),
+ ITL_SECTION Section = ITL_SECTION_INSTANCE(itl::inplace_et, U),
+ template<class,ITL_COMPARE>class Interval = interval,
+ ITL_ALLOC Alloc = std::allocator
+ >class IntervalMap
+ >
+void itl_map_inclusion_compare_4_bicremental_types()
+{
+ typedef IntervalMap<T,U,Trt> IntervalMapT;
+ typedef itl::map<T,U,Trt> MapT;
+ typedef itl::set<T> SetT;
+
+ IntervalMapT itv_map_sub_a, itv_map_a, itv_map_super_a,
+ itv_map_b, itv_map_c;
+ itv_map_sub_a.add(IDv(2,4,1)).add(IIv(6,7,3));
+ itv_map_a = itv_map_sub_a;
+ itv_map_a.add(IIv(9,9,1));
+ itv_map_c = itv_map_sub_a;
+ itv_map_c.erase(MK_v(7)).add(IIv(11,11,2));
+ itv_map_b = itv_map_a;
+ itv_map_b.set(IIv(6,7,2));
+
+ MapT map_sub_a, map_a, map_a2, map_b, map_c;
+ Interval::atomize(map_a, itv_map_a);
+ Interval::atomize(map_b, itv_map_b);
+ Interval::atomize(map_c, itv_map_c);
+ Interval::atomize(map_sub_a, itv_map_sub_a);
+
+ map_a2 = map_a;
+ BOOST_CHECK_EQUAL( inclusion_compare(MapT(), MapT()), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(map_a, map_a), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(map_a, map_a2), inclusion::equal );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(map_a, MapT()), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare(map_a, map_sub_a), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare(MapT(), map_a), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare(map_sub_a, map_a), inclusion::subset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(map_a, map_b), inclusion::unrelated );
+ BOOST_CHECK_EQUAL( inclusion_compare(map_a, map_c), inclusion::unrelated );
+
+ SetT set_sub_a, set_a, set_a2, set_b, set_c;
+ map_a.domain(set_a);
+ map_a2.domain(set_a2);
+ map_sub_a.domain(set_sub_a);
+
+ BOOST_CHECK_EQUAL( inclusion_compare(MapT(), SetT()), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(SetT(), MapT()), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(SetT(), SetT()), inclusion::equal );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(map_a, set_a), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(set_a, map_a), inclusion::equal );
+ BOOST_CHECK_EQUAL( inclusion_compare(set_a, set_a2), inclusion::equal );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(map_a, SetT()), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare(map_a, set_sub_a), inclusion::superset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(SetT(), map_a), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare(set_sub_a, map_a), inclusion::subset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(set_a, SetT()), inclusion::superset );
+ BOOST_CHECK_EQUAL( inclusion_compare(set_a, set_sub_a), inclusion::superset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(SetT(), set_a), inclusion::subset );
+ BOOST_CHECK_EQUAL( inclusion_compare(set_sub_a, set_a), inclusion::subset );
+
+ BOOST_CHECK_EQUAL( inclusion_compare(set_a, map_c), inclusion::unrelated );
+ BOOST_CHECK_EQUAL( inclusion_compare(map_c, set_a), inclusion::unrelated );
+
+}
+
+
#endif // __test_itl_itl_map_h_JOFA_090119__
Modified: sandbox/itl/libs/itl/test/test_itl_map_/test_itl_map_cases.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_itl_map_/test_itl_map_cases.hpp (original)
+++ sandbox/itl/libs/itl/test/test_itl_map_/test_itl_map_cases.hpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -12,4 +12,8 @@
(test_itl_itl_map_find_4_bicremental_types, T, discrete_types)
{ itl_map_find_4_bicremental_types<T, int, partial_absorber, INTERVAL_MAP>();}
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(test_itl_itl_map_inclusion_compare_4_bicremental_types, T, discrete_types)
+{ itl_map_inclusion_compare_4_bicremental_types<T, int, partial_absorber, INTERVAL_MAP>();}
+
#endif // __itl_test_itl_map_cases_hpp_JOFA_090701__
Modified: sandbox/itl/libs/validate/example/labat_single_/labat_single.cpp
==============================================================================
--- sandbox/itl/libs/validate/example/labat_single_/labat_single.cpp (original)
+++ sandbox/itl/libs/validate/example/labat_single_/labat_single.cpp 2009-08-30 10:27:02 EDT (Sun, 30 Aug 2009)
@@ -19,6 +19,7 @@
#include <boost/validate/laws/symmetric_difference.hpp>
#include <boost/validate/laws/pushouts.hpp>
#include <boost/validate/laws/set_laws.hpp>
+#include <boost/validate/laws/minor_set_laws.hpp>
//#include <boost/validate/laws/novial_tree.hpp>
#include <boost/validate/laws/inversion_laws.hpp>
#include <boost/validate/validater/law_validater.hpp>
@@ -64,12 +65,24 @@
//typedef Balance<itl::tree<int> > TestLawT;
//LawValidater<TestLawT, RandomGentor> test_law;
- typedef InplaceDeMorgan
- <itl::interval_map<int, int> > TestLawT;
- LawValidater<TestLawT, RandomGentor> test_law;
+ //typedef InplaceDeMorgan
+ // <itl::interval_map<int, int> > TestLawT;
+ //LawValidater<TestLawT, RandomGentor> test_law;
+
+ //typedef IntersectsDefined
+ // <itl::interval_map<int, int, total_absorber> > TestLawT;
+ //LawValidater<TestLawT, RandomGentor> test_law;
+
+ //typedef Interinclusion
+ // <interval_map<int,int>, interval_set<int> > TestLawT;
+ //LawValidater<TestLawT, RandomGentor> test_law;
+
+ typedef Interinclusion
+ <interval_map<int, itl::set<int> >, interval_map<int, itl::set<int> > > TestLawT;
+ LawValidater<TestLawT, RandomGentor> test_law;
//-----------------------------------------------------------------------------
- int test_count = 1000;
+ int test_count = 20000;
ptime start, stop;
test_law.set_trials_count(test_count);