Subject: [Boost-commit] svn:boost r65182 - in sandbox/itl: boost/itl boost/itl/detail boost/itl/functions libs/itl/test libs/itl/test/fastest_set_interval_set_
From: afojgo_at_[hidden]
Date: 2010-09-01 17:55:51
Author: jofaber
Date: 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
New Revision: 65182
URL: http://svn.boost.org/trac/boost/changeset/65182
Log:
Refactoring. Unifying interval_sets. Extracted global functions. Stable{msvc-9.0, gcc-3.4.4}
Added:
sandbox/itl/boost/itl/functions/associative_interval_container.hpp (contents, props changed)
Text files modified:
sandbox/itl/boost/itl/detail/interval_set_algo.hpp | 8 -
sandbox/itl/boost/itl/functions.hpp | 175 +++++++++++++++++++++++++++----
sandbox/itl/boost/itl/functions/associative_element_container.hpp | 18 +++
sandbox/itl/boost/itl/functions/container.hpp | 25 +--
sandbox/itl/boost/itl/interval_base_map.hpp | 16 +
sandbox/itl/boost/itl/interval_base_set.hpp | 222 +++++++++++++++++++++++++++++----------
sandbox/itl/boost/itl/interval_set.hpp | 9 +
sandbox/itl/boost/itl/map.hpp | 69 ------------
sandbox/itl/boost/itl/map_functions.hpp | 7 +
sandbox/itl/boost/itl/set_functions.hpp | 1
sandbox/itl/libs/itl/test/fastest_set_interval_set_/fastest_set_interval_set_cases.hpp | 12 ++
sandbox/itl/libs/itl/test/test_interval_set_mixed.hpp | 8
sandbox/itl/libs/itl/test/test_interval_set_shared.hpp | 16 +-
sandbox/itl/libs/itl/test/test_set_interval_set_shared.hpp | 62 +++++++++++
14 files changed, 460 insertions(+), 188 deletions(-)
Modified: sandbox/itl/boost/itl/detail/interval_set_algo.hpp
==============================================================================
--- sandbox/itl/boost/itl/detail/interval_set_algo.hpp (original)
+++ sandbox/itl/boost/itl/detail/interval_set_algo.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -243,13 +243,7 @@
return result == inclusion::superset || result == inclusion::equal;
}
-template<class IntervalContainerT>
-bool contains(const IntervalContainerT& super,
- const typename IntervalContainerT::element_type& element)
-{
- return super.contains(element);
-}
-
+//JODO check if this is still needed
template<class IntervalContainerT>
bool contains(const IntervalContainerT& container,
const typename IntervalContainerT::segment_type& sub_interval)
Modified: sandbox/itl/boost/itl/functions.hpp
==============================================================================
--- sandbox/itl/boost/itl/functions.hpp (original)
+++ sandbox/itl/boost/itl/functions.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -12,6 +12,9 @@
#include <boost/mpl/or.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/itl/type_traits/is_interval_container.hpp>
+#include <boost/itl/type_traits/is_interval_separator.hpp>
+#include <boost/itl/type_traits/is_interval_splitter.hpp>
+#include <boost/itl/type_traits/is_interval_joiner.hpp>
#include <boost/itl/type_traits/is_element_container.hpp>
#include <boost/itl/type_traits/is_combinable.hpp>
#include <boost/itl/detail/interval_map_functors.hpp>
@@ -58,13 +61,31 @@
//CL?? return Interval_Map::contains(super, sub);
}
-template<class ObjectT, class OperandT>
-typename enable_if<mpl::and_<is_interval_set<ObjectT>,
- is_intra_derivative<ObjectT, OperandT> >,
- bool>::type
-contains(const ObjectT& super, const OperandT& sub)
+template<class ObjectT>
+typename enable_if<is_interval_set<ObjectT>, bool>::type
+contains(const ObjectT& super, const typename ObjectT::segment_type& inter_val)
{
- return Interval_Set::contains(super, sub);
+ typedef typename ObjectT::const_iterator const_iterator;
+ if(itl::is_empty(inter_val))
+ return true;
+
+ std::pair<const_iterator, const_iterator> exterior
+ = super.equal_range(inter_val);
+ if(exterior.first == exterior.second)
+ return false;
+
+ const_iterator last_overlap = super.prior(exterior.second);
+
+ return
+ itl::contains(hull(*(exterior.first), *last_overlap), inter_val)
+ && Interval_Set::is_joinable(super, exterior.first, last_overlap);
+}
+
+template<class ObjectT>
+typename enable_if<is_interval_set<ObjectT>, bool>::type
+contains(const ObjectT& super, const typename ObjectT::element_type& element)
+{
+ return !(super.find(element) == super.end());
}
template<class ObjectT, class OperandT>
@@ -94,7 +115,7 @@
typename enable_if<is_interval_container<SuperT>, bool>::type
within(const SubT& sub, const SuperT& super)
{
- return itl::contains(super, sub);
+ return itl::contains(super, sub);
}
@@ -155,6 +176,96 @@
//==============================================================================
//= Addition
//==============================================================================
+
+//- joining_add ----------------------------------------------------------------
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_joiner<ObjectT> >, ObjectT>::type&
+add(ObjectT& object, const typename ObjectT::element_type& operand)
+{
+ detail::joining_add(object, typename ObjectT::interval_type(operand));
+ return object; //JODO: May be it is better to return the iterator
+}
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_joiner<ObjectT> >, ObjectT>::type&
+add(ObjectT& object, const typename ObjectT::segment_type& operand)
+{
+ detail::joining_add(object, operand);
+ return object; //JODO: May be it is better to return the iterator
+}
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_joiner<ObjectT> >,
+ typename ObjectT::iterator>::type
+add(ObjectT& object, typename ObjectT::iterator prior,
+ const typename ObjectT::segment_type& operand)
+{
+ return detail::joining_add(object, prior, operand);
+}
+
+//- separating_add -------------------------------------------------------------
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_separator<ObjectT> >, ObjectT>::type&
+add(ObjectT& object, const typename ObjectT::element_type& operand)
+{
+ detail::separating_add(object, typename ObjectT::interval_type(operand));
+ return object;
+}
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_separator<ObjectT> >, ObjectT>::type&
+add(ObjectT& object, const typename ObjectT::segment_type& operand)
+{
+ detail::separating_add(object, operand);
+ return object; //JODO: May be it is better to return the iterator
+}
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_separator<ObjectT> >,
+ typename ObjectT::iterator>::type
+add(ObjectT& object, typename ObjectT::iterator prior,
+ const typename ObjectT::segment_type& operand)
+{
+ return detail::separating_add(object, prior, operand);
+}
+
+//- splitting_add -------------------------------------------------------------
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_splitter<ObjectT> >, ObjectT>::type&
+add(ObjectT& object, const typename ObjectT::element_type& operand)
+{
+ detail::splitting_add(object, typename ObjectT::interval_type(operand));
+ return object;
+}
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_splitter<ObjectT> >, ObjectT>::type&
+add(ObjectT& object, const typename ObjectT::segment_type& operand)
+{
+ detail::splitting_add(object, operand);
+ return object; //JODO: May be it is better to return the iterator
+}
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_splitter<ObjectT> >,
+ typename ObjectT::iterator>::type
+add(ObjectT& object, typename ObjectT::iterator prior,
+ const typename ObjectT::segment_type& operand)
+{
+ return detail::splitting_add(object, prior, operand);
+}
+//------------------------------------------------------------------------------
+
+
/** \par \b Requires: \c OperandT is an interval container addable to \c ObjectT.
\b Effects: \c operand is added to \c object.
\par \b Returns: A reference to \c object.
@@ -165,7 +276,7 @@
{
typename ObjectT::iterator prior_ = object.end();
ITL_const_FORALL(typename OperandT, elem_, operand)
- prior_ = object.add(prior_, *elem_);
+ prior_ = object.add(prior_, *elem_); //JODO
return object;
}
@@ -195,9 +306,18 @@
typename enable_if<is_intra_derivative<ObjectT, OperandT>, ObjectT>::type&
operator += (ObjectT& object, const OperandT& operand)
{
- return object.add(operand);
+ //JODO return itl::add(object, operand);
+ return object.add(operand);
}
+//CL
+//template<class ObjectT, class OperandT>
+//typename enable_if<is_intra_derivative<ObjectT, OperandT>, ObjectT>::type&
+//add(ObjectT& object, const OperandT& operand)
+//{
+// return object.add(operand);
+//}
+
/** \par \b Requires: \c object and \c operand are addable.
\b Effects: \c operand is added to \c object.
\par \b Efficieny: There is one additional copy of
@@ -301,6 +421,23 @@
//==============================================================================
//= Subtraction
//==============================================================================
+
+template<class ObjectT>
+typename enable_if<is_interval_set<ObjectT>, ObjectT>::type&
+subtract(ObjectT& object, const typename ObjectT::element_type& operand)
+{
+ detail::subtract(object, typename ObjectT::segment_type(operand));
+ return object; //JODO: May be it is better to return the iterator
+}
+
+template<class ObjectT>
+typename enable_if<is_interval_set<ObjectT>, ObjectT>::type&
+subtract(ObjectT& object, const typename ObjectT::segment_type& operand)
+{
+ detail::subtract(object, operand);
+ return object; //JODO: May be it is better to return the iterator
+}
+
//------------------------------------------------------------------------------
//- Subtraction -=, -
//------------------------------------------------------------------------------
@@ -328,12 +465,12 @@
is \b amortized \b logarithmic.
*/
template<class ObjectT, class OperandT>
-typename enable_if<is_concept_equivalent<is_interval_map, ObjectT, OperandT>,
+typename enable_if<has_same_concept<is_interval_map, ObjectT, OperandT>,
ObjectT>::type&
operator -=(ObjectT& object, const OperandT& operand)
{
ITL_const_FORALL(typename OperandT, elem_, operand)
- object.subtract(*elem_);
+ object.subtract(*elem_); //JODO
return object;
}
@@ -342,7 +479,8 @@
typename enable_if<is_intra_derivative<ObjectT, OperandT>, ObjectT>::type&
operator -= (ObjectT& object, const OperandT& operand)
{
- return object.subtract(operand);
+ //JODO return itl::subtract(object, operand);
+ return object.subtract(operand);
}
template<class ObjectT, class OperandT>
@@ -590,19 +728,6 @@
}
-//-----------------------------------------------------------------------------
-// hull
-//-----------------------------------------------------------------------------
-template<class ObjectT>
-typename enable_if<is_interval_container<ObjectT>,
- typename ObjectT::interval_type>::type
-hull(const ObjectT& object)
-{
- return
- itl::is_empty(object) ? neutron<typename ObjectT::interval_type>::value()
- : hull((ObjectT::key_value(object.begin())), ObjectT::key_value(object.rbegin()));
-}
-
}} // namespace itl boost
Modified: sandbox/itl/boost/itl/functions/associative_element_container.hpp
==============================================================================
--- sandbox/itl/boost/itl/functions/associative_element_container.hpp (original)
+++ sandbox/itl/boost/itl/functions/associative_element_container.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -88,6 +88,24 @@
return itl::within(sub, super);
}
+//==============================================================================
+//= Size
+//==============================================================================
+
+template<class Type>
+typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
+size(const Type& object)
+{
+ return itl::iterative_size(object);
+}
+
+template<class Type>
+typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
+cardinality(const Type& object)
+{
+ return itl::iterative_size(object);
+}
+
//==============================================================================
//= Equivalences and Orderings
Added: sandbox/itl/boost/itl/functions/associative_interval_container.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/functions/associative_interval_container.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -0,0 +1,79 @@
+/*-----------------------------------------------------------------------------+
+Copyright (c) 2010-2010: 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 BOOST_ITL_FUNCTIONS_ASSOCIATIVE_INTERVAL_CONTAINER_HPP_JOFA_100901
+#define BOOST_ITL_FUNCTIONS_ASSOCIATIVE_INTERVAL_CONTAINER_HPP_JOFA_100901
+
+#include <boost/itl/detail/design_config.hpp>
+#include <boost/itl/type_traits/is_interval_container.hpp>
+#include <boost/itl/type_traits/is_continuous.hpp>
+#include <boost/itl/detail/interval_set_algo.hpp>
+
+namespace boost{namespace itl
+{
+
+//==============================================================================
+//= Size
+//==============================================================================
+
+template<class Type>
+typename enable_if<is_interval_container<Type>, typename Type::size_type>::type
+cardinality(const Type& object)
+{
+ using namespace boost::mpl;
+ typedef typename Type::domain_type domain_type;
+
+ return if_<
+ bool_<is_continuous<domain_type>::value>,
+ continuous_interval_container,
+ discrete_interval_container
+ >
+ ::type::cardinality(object);
+}
+
+template<class Type>
+typename enable_if<is_interval_container<Type>, typename Type::difference_type>::type
+length(const Type& object)
+{
+ typedef typename Type::difference_type difference_type;
+ typedef typename Type::const_iterator const_iterator;
+ difference_type length = neutron<difference_type>::value();
+ const_iterator it_ = object.begin();
+
+ while(it_ != object.end())
+ length += itl::length(Type::key_value(it_++));
+ return length;
+}
+
+template<class Type>
+typename enable_if<is_interval_container<Type>, std::size_t>::type
+interval_count(const Type& object)
+{
+ return itl::iterative_size(object);
+}
+
+//==============================================================================
+//= Range
+//==============================================================================
+template<class ObjectT>
+typename enable_if<is_interval_container<ObjectT>,
+ typename ObjectT::interval_type>::type
+hull(const ObjectT& object)
+{
+ return
+ itl::is_empty(object) ? neutron<typename ObjectT::interval_type>::value()
+ : hull((ObjectT::key_value(object.begin())), ObjectT::key_value(object.rbegin()));
+}
+
+
+}} // namespace itl boost
+
+
+
+#endif
+
+
Modified: sandbox/itl/boost/itl/functions/container.hpp
==============================================================================
--- sandbox/itl/boost/itl/functions/container.hpp (original)
+++ sandbox/itl/boost/itl/functions/container.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -40,29 +40,24 @@
//==============================================================================
//= Size
//==============================================================================
-template<class Type>
-typename enable_if<is_container<Type>, typename Type::size_type>::type
-size(const Type& object)
-{
- return object.size();
-}
-template<class Type>
-typename enable_if<is_container<Type>, typename Type::size_type>::type
-cardinality(const Type& object)
-{
- return object.size();
-}
-
-template<class Type>
+template<class Type>
typename enable_if<is_container<Type>, typename Type::size_type>::type
iterative_size(const Type& object)
{
return object.size();
}
+//==============================================================================
+//= Swap
+//==============================================================================
-
+template<class Type>
+typename enable_if<is_container<Type>, void>::type
+swap(Type& left, Type& right)
+{
+ left.swap(right); //JODO test
+}
}} // namespace itl boost
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 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -224,14 +224,12 @@
//==========================================================================
//= Containedness
//==========================================================================
-ITL_BEGIN_COMMON_MEMBER_FUNCTIONS:
/** clear the map */
void clear() { _map.clear(); }
/** is the map empty? */
bool empty()const { return _map.empty(); }
-ITL_END_COMMON_MEMBER_FUNCTIONS:
//--- contains: set view ---------------------------------------------------
/** Does the map contain the domain element \c key? */
bool contains(const domain_type& key)const
@@ -284,10 +282,16 @@
//==========================================================================
/** Number of elements in the map (cardinality). */
- size_type cardinality()const;
+ size_type cardinality()const
+ {
+ return itl::cardinality(*that());
+ }
/** An interval map's size is it's cardinality */
- size_type size()const { return cardinality(); }
+ size_type size()const
+ {
+ return itl::cardinality(*that());
+ }
/** The length of the interval container which is the sum of
interval lengths */
@@ -852,7 +856,7 @@
return Interval_Map::contains(*this, sub_segment);
}
-//CL
+//CL JODO unify
//{
// interval_type sub_interval = sub_segment.first;
// if(itl::is_empty(sub_interval))
@@ -878,6 +882,7 @@
//= Size
//==============================================================================
+/*CL
template
<
class SubType, class DomainT, class CodomainT, class Traits,
@@ -897,6 +902,7 @@
>
::type::cardinality(*this);
}
+*/
template
<
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 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -11,6 +11,9 @@
#include <limits>
#include <boost/itl/type_traits/interval_type_default.hpp>
+#include <boost/itl/type_traits/is_interval_joiner.hpp>
+#include <boost/itl/type_traits/is_interval_separator.hpp>
+#include <boost/itl/type_traits/is_interval_splitter.hpp>
#include <boost/itl/detail/interval_set_algo.hpp>
#include <boost/itl/set.hpp>
#include <boost/itl/interval.hpp>
@@ -26,6 +29,92 @@
namespace boost{namespace itl
{
+//JODO Forward 4 gcc-3.4.4 -----------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_container<Type>, std::size_t>::type
+interval_count(const Type&);
+
+template<class Type>
+typename enable_if<is_interval_container<Type>, typename Type::size_type>::type
+cardinality(const Type&);
+
+template<class Type>
+typename enable_if<is_interval_container<Type>, typename Type::difference_type>::type
+length(const Type&);
+
+template<class ObjectT>
+typename enable_if<is_interval_set<ObjectT>, bool>::type
+contains(const ObjectT& super, const typename ObjectT::segment_type&);
+
+template<class ObjectT>
+typename enable_if<is_interval_set<ObjectT>, bool>::type
+contains(const ObjectT& super, const typename ObjectT::element_type&);
+
+//- joining_add -------------------------------------------------------------
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_joiner<ObjectT> >, ObjectT>::type&
+add(ObjectT&, const typename ObjectT::element_type&);
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_joiner<ObjectT> >, ObjectT>::type&
+add(ObjectT&, const typename ObjectT::segment_type&);
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_joiner<ObjectT> >,
+ typename ObjectT::iterator>::type
+add(ObjectT&, typename ObjectT::iterator,
+ const typename ObjectT::segment_type&);
+
+//- separating_add -------------------------------------------------------------
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_separator<ObjectT> >, ObjectT>::type&
+add(ObjectT&, const typename ObjectT::element_type&);
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_separator<ObjectT> >, ObjectT>::type&
+add(ObjectT& object, const typename ObjectT::segment_type& operand);
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_separator<ObjectT> >,
+ typename ObjectT::iterator>::type
+add(ObjectT& object, typename ObjectT::iterator prior,
+ const typename ObjectT::segment_type& operand);
+
+//- splitting_add -------------------------------------------------------------
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_splitter<ObjectT> >, ObjectT>::type&
+add(ObjectT&, const typename ObjectT::element_type&);
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_splitter<ObjectT> >, ObjectT>::type&
+add(ObjectT& object, const typename ObjectT::segment_type& operand);
+
+template<class ObjectT>
+typename enable_if<mpl::and_< is_interval_set<ObjectT>
+ , is_interval_splitter<ObjectT> >,
+ typename ObjectT::iterator>::type
+add(ObjectT& object, typename ObjectT::iterator prior,
+ const typename ObjectT::segment_type& operand);
+
+template<class ObjectT>
+typename enable_if<is_interval_set<ObjectT>, ObjectT>::type&
+subtract(ObjectT&, const typename ObjectT::element_type&);
+
+template<class ObjectT>
+typename enable_if<is_interval_set<ObjectT>, ObjectT>::type&
+subtract(ObjectT&, const typename ObjectT::segment_type&);
+
+//JODO Forward 4 gcc-3.4.4 -----------------------------------------------------
+
+
/** \brief Implements a set as a set of intervals (base class) */
template
<
@@ -158,42 +247,35 @@
}
/** swap the content of containers */
- void swap(interval_base_set& x) { _set.swap(x._set); }
+ void swap(interval_base_set& operand) { _set.swap(operand._set); }
//==========================================================================
//= Containedness
//==========================================================================
/** sets the container empty */
- void clear() { _set.clear(); }
+ void clear() { itl::clear(*that()); }
/** is the container empty? */
- bool empty()const { return _set.empty(); }
+ bool empty()const { return itl::is_empty(*that()); }
/** Does the container contain the element \c key ? */
bool contains(const element_type& key)const
- { return that()->contains(interval_type(key)); }
+ {
+ return itl::contains(*that(), key);
+ }
/** Does the container contain the interval \c sub_interval ? */
bool contains(const segment_type& sub_interval)const
{
- if(itl::is_empty(sub_interval))
- 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
- itl::contains(hull(*(exterior.first), *last_overlap), sub_interval)
- && Interval_Set::is_joinable(*this, exterior.first, last_overlap);
+ return itl::contains(*that(), sub_interval);
}
/** Does the container contain the subcontainer \c sub ? */
bool contains(const interval_base_set& sub)const
- { return sub.contained_in(*this); }
+ {
+ return itl::within(sub, *that());
+ }
/** Does <tt>*this</tt> container contain <tt>sub</tt>? */
template
@@ -203,7 +285,9 @@
class IntervalSet
>
bool contains(const IntervalSet<DomainT,Compare,Interval,Alloc>& sub)const
- { return sub.contained_in(*that()); }
+ {
+ return itl::within(sub,*that());
+ }
/** Is <tt>*this</tt> container contained in <tt>super</tt>? */
template
@@ -223,40 +307,40 @@
/** Number of elements in the set (cardinality).
Infinite for continuous domain datatyps */
- size_type cardinality()const;
+ size_type cardinality()const
+ {
+ return itl::cardinality(*that());
+ }
/** An interval set's size is it's cardinality */
- size_type size()const { return cardinality(); }
+ size_type size()const
+ {
+ return itl::cardinality(*that());
+ }
/** The length of the interval container which is the sum of interval lengths */
- difference_type length()const;
+ difference_type length()const
+ {
+ return itl::length(*that());
+ }
/** Number of intervals which is also the size of the iteration over the object */
- std::size_t interval_count()const { return _set.size(); }
+ std::size_t interval_count()const
+ {
+ return itl::interval_count(*that());
+ }
/** Size of the iteration over this container */
- std::size_t iterative_size()const { return _set.size(); }
+ std::size_t iterative_size()const
+ {
+ return _set.size();
+ }
//==========================================================================
//= Range
//==========================================================================
- /** lower bound of all intervals in the object */
- DomainT lower()const
- { return empty()? interval_type().lower() : (*(_set.begin())).lower(); }
- /** upper bound of all intervals in the object */
- DomainT upper()const
- { return empty()? interval_type().upper() : (*(_set.rbegin())).upper(); }
-
- /** Smallest element of the set (wrt. the partial ordering on DomainT).
- first() does not exist for continuous datatypes and open interval
- bounds. */
- DomainT first()const { return (*(_set.begin())).first(); }
-
- /** Largest element of the set (wrt. the partial ordering on DomainT).
- last() does not exist for continuous datatypes and open interval
- bounds. */
- DomainT last()const { return (*(_set.rbegin())).last(); }
+ //JODO remove lower, upper, first, last from the interface of all interval containers and docs
//==========================================================================
//= Selection
@@ -265,8 +349,7 @@
/** Find the interval value pair, that contains element \c key */
const_iterator find(const element_type& key)const
{
- typename ImplSetT::const_iterator it_ = this->_set.find(interval_type(key));
- return it_;
+ return this->_set.find(interval_type(key));
}
//==========================================================================
@@ -275,17 +358,23 @@
/** Add a single element \c key to the set */
SubType& add(const element_type& key)
- { that()->add_(interval_type(key)); return *that(); }
+ {
+ return itl::add(*that(), key);
+ }
/** Add an interval of elements \c inter_val to the set */
SubType& add(const segment_type& inter_val)
- { that()->add_(inter_val); return *that(); }
+ {
+ return itl::add(*that(), inter_val);
+ }
/** Add an interval of elements \c inter_val to the set. Iterator
\c prior_ is a hint to the position \c inter_val can be
inserted after. */
iterator add(iterator prior_, const segment_type& inter_val)
- { return that()->add_(prior_, inter_val); }
+ {
+ return itl::add(*that(), prior_, inter_val);
+ }
//==========================================================================
//= Subtraction
@@ -293,11 +382,15 @@
/** Subtract a single element \c key from the set */
SubType& subtract(const element_type& key)
- { that()->subtract_(interval_type(key)); return *that(); }
+ {
+ return itl::subtract(*that(), key);
+ }
/** Subtract an interval of elements \c inter_val from the set */
SubType& subtract(const segment_type& inter_val)
- { that()->subtract_(inter_val); return *that(); }
+ {
+ return itl::subtract(*that(), inter_val);
+ }
//==========================================================================
//= Insertion, erasure
@@ -309,33 +402,49 @@
/** Insert an element \c key into the set */
SubType& insert(const element_type& key)
- { return add(interval_type(key)); }
+ {
+ return itl::add(*that(), key);
+ }
/** Insert an interval of elements \c inter_val to the set */
SubType& insert(const segment_type& inter_val)
- { return add(inter_val); }
+ {
+ return itl::add(*that(), inter_val);
+ }
/** Insert an interval of elements \c inter_val to the set. Iterator
\c prior_ is a hint to the position \c inter_val can be
inserted after. */
iterator insert(iterator prior_, const segment_type& inter_val)
- { return that()->add_(prior_, inter_val); }
+ {
+ return itl::add(*that(), prior_, inter_val);
+ }
/** Erase an element \c key from the set */
SubType& erase(const element_type& key)
- { return subtract(interval_type(key)); }
+ {
+ return itl::subtract(*that(), key);
+ }
/** Erase an interval of elements \c inter_val from the set */
SubType& erase(const segment_type& inter_val)
- { return subtract(inter_val); }
+ {
+ return itl::subtract(*that(), inter_val);
+ }
/** Erase the interval that iterator \c position points to. */
- void erase(iterator position){ _set.erase(position); }
+ void erase(iterator position)
+ {
+ _set.erase(position);
+ }
/** Erase all intervals in the range <tt>[first,past)</tt> of iterators. */
- void erase(iterator first, iterator past){ _set.erase(first, past); }
+ void erase(iterator first, iterator past)
+ {
+ _set.erase(first, past);
+ }
//==========================================================================
@@ -481,11 +590,11 @@
iterator prior(iterator it_)
{ return it_ == this->_set.begin() ? this->_set.end() : --it_; }
-protected:
-
const_iterator prior(const_iterator it_)const
{ return it_ == this->_set.begin() ? this->_set.end() : --it_; }
+protected:
+
iterator gap_insert(iterator prior_, const interval_type& inter_val)
{
// inter_val is not conained in this map. Insertion will be successful
@@ -498,7 +607,7 @@
} ;
-
+/*CL
template
<
class SubType, class DomainT,
@@ -530,6 +639,7 @@
length += itl::length(*it_);
return length;
}
+*/
template<class SubType,
Modified: sandbox/itl/boost/itl/interval_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_set.hpp (original)
+++ sandbox/itl/boost/itl/interval_set.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -11,7 +11,9 @@
#include <boost/assert.hpp>
#include <boost/itl/rightopen_interval.hpp> //JODO REV?
+#include <boost/itl/type_traits/is_interval_joiner.hpp>
#include <boost/itl/interval_base_set.hpp>
+#include <boost/itl/functions/associative_interval_container.hpp>
#include <boost/itl/functions.hpp>
namespace boost{namespace itl
@@ -198,6 +200,13 @@
BOOST_STATIC_CONSTANT(bool, value = true);
};
+template <class DomainT, ITL_COMPARE Compare, ITL_INTERVAL(ITL_COMPARE) Interval, ITL_ALLOC Alloc>
+struct is_interval_joiner<itl::interval_set<DomainT,Compare,Interval,Alloc> >
+{
+ typedef is_interval_joiner<itl::interval_set<DomainT,Compare,Interval,Alloc> > type;
+ BOOST_STATIC_CONSTANT(bool, value = true);
+};
+
//-----------------------------------------------------------------------------
// type representation
Modified: sandbox/itl/boost/itl/map.hpp
==============================================================================
--- sandbox/itl/boost/itl/map.hpp (original)
+++ sandbox/itl/boost/itl/map.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -83,71 +83,6 @@
inline std::string type_to_string<total_enricher>::apply() { return "e^0"; }
-/*CL
-template<class, class, class, ITL_COMPARE, ITL_COMBINE, ITL_SECTION, ITL_ALLOC>
-class map;
-
-//==============================================================================
-//=+ seqs
-//==============================================================================
-
-template<class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
-struct seqs< itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> >
-{
- typedef itl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> map_type;
- typedef typename map_type::domain_type domain_type;
- typedef typename map_type::codomain_type codomain_type;
- typedef typename map_type::element_type element_type;
- typedef typename map_type::size_type size_type;
- typedef typename map_type::domain_compare domain_compare;
-
- typedef typename map_type::iterator iterator;
- typedef typename map_type::const_iterator const_iterator;
-
- static const_iterator begin(const map_type& object){ return object.begin(); }
- static iterator begin( map_type& object){ return object.begin(); }
- static const_iterator end (const map_type& object){ return object.end(); }
- static iterator end ( map_type& object){ return object.end(); }
- static size_type size (const map_type& object){ return object.size(); }
-
- static const_iterator find(const map_type& object, const domain_type& key)
- { return object.find(key); }
-
- static iterator find(map_type& object, const domain_type& key)
- { return object.find(key); }
-
- static std::pair<iterator,bool> insert(map_type& object, const element_type& key_value_pair)
- { return object.insert(key_value_pair); }
-
- static iterator insert(map_type& object, iterator prior, const element_type& key_value_pair)
- { return object.insert(prior, key_value_pair); }
-
- static void erase(map_type& object, iterator pos)
- { object.erase(pos); }
-
- static void erase(map_type& object, iterator first, iterator past)
- { object.erase(first, past); }
-
- static void swap(map_type& left, map_type& right)
- { left.swap(right); }
-
- //--------------------------------------------------------------------------
- template<typename IteratorT>
- static const domain_type& key_value(IteratorT value_){ return value_->first; }
-
- template<typename IteratorT>
- static const codomain_type& co_value(IteratorT value_){ return value_->second; }
-
- template<typename LeftIterT, typename RightIterT>
- static bool key_less(LeftIterT lhs_, RightIterT rhs_)
- { return domain_compare()((*lhs_).first,(*rhs_).first); }
-
- static element_type make_value(const domain_type& key_value, const codomain_type& data_value)
- { return element_type(key_value, data_value); }
-};
-
-//==============================================================================
-*/
/** \brief Addable, subractable and intersectable maps */
template
@@ -387,9 +322,9 @@
//= Symmetric difference
//==========================================================================
- map& flip(const element_type& value_pair)
+ map& flip(const element_type& operand)
{
- return (*this) ^= value_pair;
+ return itl::flip(*this, operand);
}
//==========================================================================
Modified: sandbox/itl/boost/itl/map_functions.hpp
==============================================================================
--- sandbox/itl/boost/itl/map_functions.hpp (original)
+++ sandbox/itl/boost/itl/map_functions.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -395,6 +395,13 @@
template<class MapT>
inline typename enable_if<is_element_map<MapT>, MapT>::type&
+flip(MapT& object, const typename MapT::element_tpye& operand)
+{
+ return MapT::flip_::apply(object, operand);
+}
+
+template<class MapT>
+inline typename enable_if<is_element_map<MapT>, MapT>::type&
operator ^= (MapT& object, const typename MapT::element_tpye& operand)
{
return MapT::flip_::apply(object, operand);
Modified: sandbox/itl/boost/itl/set_functions.hpp
==============================================================================
--- sandbox/itl/boost/itl/set_functions.hpp (original)
+++ sandbox/itl/boost/itl/set_functions.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -17,7 +17,6 @@
#include <boost/itl/functions/associative_element_container.hpp>
-
namespace boost{namespace itl
{
Modified: sandbox/itl/libs/itl/test/fastest_set_interval_set_/fastest_set_interval_set_cases.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/fastest_set_interval_set_/fastest_set_interval_set_cases.hpp (original)
+++ sandbox/itl/libs/itl/test/fastest_set_interval_set_/fastest_set_interval_set_cases.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -67,5 +67,17 @@
(fastest_itl_split_interval_set_check_partial_invertive_monoid_plus_4_bicremental_types)
{ interval_set_check_partial_invertive_monoid_plus_4_bicremental_types<bicremental_type_4, split_interval_set>();}
+
+//------------------------------------------------------------------------------
+// Containedness
+//------------------------------------------------------------------------------
+
+BOOST_AUTO_TEST_CASE
+(fastest_itl_split_interval_set_check_containedness_4_bicremental_types) //JODO complete slowtest
+{ interval_set_check_containedness_4_bicremental_types<bicremental_type_4, split_interval_set>();}
+
+
+
+
#endif // BOOST_ITL_FASTEST_SET_INTERVAL_SET_CASES_HPP_JOFA_090703
Modified: sandbox/itl/libs/itl/test/test_interval_set_mixed.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_set_mixed.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_set_mixed.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -20,8 +20,8 @@
separate_interval_set<T> sep_set(split_set);
interval_set<T> join_set(sep_set);
- BOOST_CHECK_EQUAL( split_set.lower(), sep_set.lower() );
- BOOST_CHECK_EQUAL( split_set.lower(), join_set.lower() );
+ BOOST_CHECK_EQUAL( hull(split_set).lower(), hull(sep_set).lower() );
+ BOOST_CHECK_EQUAL( hull(split_set).lower(), hull(join_set).lower() );
}
template <class T>
@@ -107,8 +107,8 @@
sep_set = split_set;
join_set = sep_set;
- BOOST_CHECK_EQUAL( split_set.lower(), sep_set.lower() );
- BOOST_CHECK_EQUAL( split_set.lower(), join_set.lower() );
+ BOOST_CHECK_EQUAL( hull(split_set).lower(), hull(sep_set).lower() );
+ BOOST_CHECK_EQUAL( hull(split_set).lower(), hull(join_set).lower() );
split_interval_set<T> split_self = split_interval_set<T>().add(v0);
separate_interval_set<T> sep_self = separate_interval_set<T>().add(v0).add(v1);
Modified: sandbox/itl/libs/itl/test/test_interval_set_shared.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_set_shared.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_set_shared.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -102,8 +102,8 @@
BOOST_CHECK_EQUAL(single_I0_0I_from_element, single_I0_0I_from_interval);
BOOST_CHECK_EQUAL(single_I0_0I_from_element, single_I0_0I);
- BOOST_CHECK_EQUAL(single_I0_0I.lower(), I0_0I.lower());
- BOOST_CHECK_EQUAL(single_I0_0I.upper(), I0_0I.upper());
+ BOOST_CHECK_EQUAL(itl::hull(single_I0_0I).lower(), I0_0I.lower());
+ BOOST_CHECK_EQUAL(itl::hull(single_I0_0I).upper(), I0_0I.upper());
IntervalSet<T> single_I1_1I_from_element(v1);
IntervalSet<T> single_I1_1I_from_interval(I1_1I);
@@ -117,8 +117,8 @@
BOOST_CHECK_EQUAL(single_I0_1I_from_interval, single_I0_1I);
BOOST_CHECK_EQUAL(hull(single_I0_1I), I0_1I);
- BOOST_CHECK_EQUAL(single_I0_1I.lower(), I0_1I.lower());
- BOOST_CHECK_EQUAL(single_I0_1I.upper(), I0_1I.upper());
+ BOOST_CHECK_EQUAL(hull(single_I0_1I).lower(), I0_1I.lower());
+ BOOST_CHECK_EQUAL(hull(single_I0_1I).upper(), I0_1I.upper());
//contains predicate
BOOST_CHECK_EQUAL(contains(single_I0_0I, v0), true);
@@ -179,8 +179,8 @@
BOOST_CHECK_EQUAL( _I4_4I.size(), unon<typename IntervalSet<T>::size_type>::value() );
BOOST_CHECK_EQUAL( _I4_4I.interval_count(), 1 );
BOOST_CHECK_EQUAL( _I4_4I.iterative_size(), 1 );
- BOOST_CHECK_EQUAL( _I4_4I.lower(), v4 );
- BOOST_CHECK_EQUAL( _I4_4I.upper(), v4 );
+ BOOST_CHECK_EQUAL( hull(_I4_4I).lower(), v4 );
+ BOOST_CHECK_EQUAL( hull(_I4_4I).upper(), v4 );
IntervalSet<T> _I4_4I_copy(_I4_4I);
IntervalSet<T> _I4_4I_assigned;
@@ -222,8 +222,8 @@
IntervalSet<T> set_B = IntervalSet<T>().insert(v9).insert(I5_6I).insert(v0);
BOOST_CHECK_EQUAL( set_A, set_B );
BOOST_CHECK_EQUAL( hull(set_A), I0_9I );
- BOOST_CHECK_EQUAL( set_A.lower(), I0_9I.lower() );
- BOOST_CHECK_EQUAL( set_A.upper(), I0_9I.upper() );
+ BOOST_CHECK_EQUAL( hull(set_A).lower(), I0_9I.lower() );
+ BOOST_CHECK_EQUAL( hull(set_A).upper(), I0_9I.upper() );
IntervalSet<T> set_A1 = set_A, set_B1 = set_B,
set_A2 = set_A, set_B2 = set_B;
Modified: sandbox/itl/libs/itl/test/test_set_interval_set_shared.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_set_interval_set_shared.hpp (original)
+++ sandbox/itl/libs/itl/test/test_set_interval_set_shared.hpp 2010-09-01 17:55:35 EDT (Wed, 01 Sep 2010)
@@ -9,6 +9,36 @@
#define __test_itl_set_interval_set_h_JOFA_090119__
+
+template <class T,
+ template<class T,
+ ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, U),
+ ITL_INTERVAL(ITL_COMPARE) Interval = ITL_INTERVAL_INSTANCE(ITL_INTERVAL_DEFAULT, T, Compare),
+ ITL_ALLOC Alloc = std::allocator
+ >class IntervalSet
+ >
+void make_3_interval_sets_and_derivatives_1
+ (IntervalSet<T>& set_a,
+ IntervalSet<T>& set_b,
+ IntervalSet<T>& set_c,
+ typename IntervalSet<T>::segment_type& segm_d,
+ typename IntervalSet<T>::element_type& elem_e)
+{
+ typedef IntervalSet<T> IntervalSetT;
+ typedef typename IntervalSetT::segment_type IntervalT;
+ typedef typename IntervalSetT::segment_type segment_type;
+ typedef typename IntervalSetT::element_type element_type;
+
+ segm_d = I_D(6,9);
+ elem_e = MK_v(5);
+
+ set_a.add(I_D(3,6)).add(I_I(5,7));
+ set_b.add(C_D(1,3)).add(I_D(8,9));
+ set_c.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7));
+}
+
+
+
//------------------------------------------------------------------------------
// Monoid EAN
//------------------------------------------------------------------------------
@@ -141,5 +171,37 @@
}
+//------------------------------------------------------------------------------
+// Containedness
+//------------------------------------------------------------------------------
+template <class T,
+ template<class T,
+ ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, U),
+ ITL_INTERVAL(ITL_COMPARE) Interval = ITL_INTERVAL_INSTANCE(ITL_INTERVAL_DEFAULT, T, Compare),
+ ITL_ALLOC Alloc = std::allocator
+ >class IntervalSet
+ >
+void interval_set_check_containedness_4_bicremental_types()
+{
+ typedef IntervalSet<T> IntervalSetT;
+ typedef typename IntervalSetT::segment_type segment_type;
+ typedef typename IntervalSetT::element_type element_type;
+
+ IntervalSetT set_a, set_b, set_c;
+ segment_type segm_d;
+ element_type elem_e;
+ make_3_interval_sets_and_derivatives_1(set_a, set_b, set_c, segm_d, elem_e);
+
+ check_intersection_containedness(set_a, set_c);
+ check_intersection_containedness(set_b, segm_d);
+ check_intersection_containedness(set_c, elem_e);
+
+ check_union_containedness(set_c, set_c);
+ check_union_containedness(set_b, segm_d);
+ check_union_containedness(set_a, elem_e);
+}
+
+
+
#endif // __test_itl_set_interval_set_h_JOFA_090119__