|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r65548 - in sandbox/itl: boost/itl boost/itl/concept boost/itl/concept/abstract boost/itl/concept/element boost/itl/concept/interval boost/itl/detail boost/itl/type_traits libs/itl/test/test_casual_ libs/validate/example/labat_single_
From: afojgo_at_[hidden]
Date: 2010-09-23 11:35:29
Author: jofaber
Date: 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
New Revision: 65548
URL: http://svn.boost.org/trac/boost/changeset/65548
Log:
Refactoring: Reorganizing namespace global functions in a directory concept. Stable{msvc-9.0, gcc-3.4.4}
Added:
sandbox/itl/boost/itl/concept/
sandbox/itl/boost/itl/concept/abstract/
sandbox/itl/boost/itl/concept/abstract/comparable.hpp (contents, props changed)
sandbox/itl/boost/itl/concept/abstract/container.hpp (contents, props changed)
sandbox/itl/boost/itl/concept/element/
sandbox/itl/boost/itl/concept/element/map.hpp (contents, props changed)
sandbox/itl/boost/itl/concept/element/set.hpp (contents, props changed)
sandbox/itl/boost/itl/concept/element/set_or_map.hpp (contents, props changed)
sandbox/itl/boost/itl/concept/interval/
sandbox/itl/boost/itl/concept/interval/base.hpp (contents, props changed)
sandbox/itl/boost/itl/concept/interval/map.hpp (contents, props changed)
sandbox/itl/boost/itl/concept/interval/set.hpp (contents, props changed)
sandbox/itl/boost/itl/concept/interval/set_or_map.hpp (contents, props changed)
Text files modified:
sandbox/itl/boost/itl/detail/interval_map_functors.hpp | 4
sandbox/itl/boost/itl/detail/interval_set_algo.hpp | 3
sandbox/itl/boost/itl/detail/map_algo.hpp | 10
sandbox/itl/boost/itl/detail/map_functors.hpp | 11
sandbox/itl/boost/itl/detail/set_algo.hpp | 315 ++++----
sandbox/itl/boost/itl/functions.hpp | 1354 ---------------------------------------
sandbox/itl/boost/itl/interval_base_map.hpp | 11
sandbox/itl/boost/itl/interval_base_set.hpp | 6
sandbox/itl/boost/itl/map.hpp | 365 +++++++++
sandbox/itl/boost/itl/map_functions.hpp | 511 --------------
sandbox/itl/boost/itl/set.hpp | 10
sandbox/itl/boost/itl/set_functions.hpp | 422 ------------
sandbox/itl/boost/itl/split_interval_map.hpp | 4
sandbox/itl/boost/itl/type_traits/is_combinable.hpp | 48 +
sandbox/itl/boost/itl/type_traits/is_fragment_type_of.hpp | 2
sandbox/itl/libs/itl/test/test_casual_/test_casual.cpp | 5
sandbox/itl/libs/validate/example/labat_single_/labat_single.cpp | 6
17 files changed, 588 insertions(+), 2499 deletions(-)
Added: sandbox/itl/boost/itl/concept/abstract/comparable.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/concept/abstract/comparable.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -0,0 +1,44 @@
+/*-----------------------------------------------------------------------------+
+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_CONCEPT_ABSTRACT_COMPARABLE_HPP_JOFA_100921
+#define BOOST_ITL_CONCEPT_ABSTRACT_COMPARABLE_HPP_JOFA_100921
+
+#include <boost/itl/type_traits/is_icl_container.hpp>
+
+namespace boost{ namespace itl
+{
+
+//==============================================================================
+//= Equivalences and Orderings<Comparable>
+//==============================================================================
+template<class Type>
+inline typename enable_if<is_icl_container<Type>, bool>::type
+operator != (const Type& left, const Type& right)
+{ return !(left == right); }
+
+template<class Type>
+inline typename enable_if<is_icl_container<Type>, bool>::type
+operator > (const Type& left, const Type& right)
+{ return right < left; }
+
+/** Partial ordering which is induced by Compare */
+template<class Type>
+inline typename enable_if<is_icl_container<Type>, bool>::type
+operator <= (const Type& left, const Type& right)
+{ return !(left > right); }
+
+template<class Type>
+inline typename enable_if<is_icl_container<Type>, bool>::type
+operator >= (const Type& left, const Type& right)
+{ return !(left < right); }
+
+}} // namespace boost itl
+
+#endif
+
+
Added: sandbox/itl/boost/itl/concept/abstract/container.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/concept/abstract/container.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -0,0 +1,81 @@
+/*-----------------------------------------------------------------------------+
+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_CONCEPT_ABSTRACT_CONTAINER_HPP_JOFA_100923
+#define BOOST_ITL_CONCEPT_ABSTRACT_CONTAINER_HPP_JOFA_100923
+
+#include <boost/itl/type_traits/is_container.hpp>
+
+namespace boost{ namespace itl
+{
+
+//==============================================================================
+//= Emptieness
+//==============================================================================
+
+/** Tests if the container is empty.
+ Complexity: constant. */
+template<class Type>
+typename enable_if<is_container<Type>, bool>::type
+is_empty(const Type& object)
+{
+ return object.begin()==object.end();
+}
+
+
+/** All content of the container is dropped.
+ Complexity: linear. */
+template<class Type>
+typename enable_if<is_container<Type>, void>::type
+clear(Type& object)
+{
+ object.erase(object.begin(), object.end());
+}
+
+//==============================================================================
+//= Size
+//==============================================================================
+
+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
+}
+
+//==============================================================================
+//= Iteration
+//==============================================================================
+
+template<class Type>
+typename enable_if<is_container<Type>, typename Type::iterator>::type
+cyclic_prior(Type& object, typename Type::iterator it_)
+{ return it_ == object.begin() ? object.end() : --it_; }
+
+template<class Type>
+typename enable_if<is_container<Type>, typename Type::const_iterator>::type
+cyclic_prior(const Type& object, typename Type::const_iterator it_)
+{ return it_ == object.begin() ? object.end() : --it_; }
+
+
+
+}} // namespace boost itl
+
+#endif
+
+
Added: sandbox/itl/boost/itl/concept/element/map.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/concept/element/map.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -0,0 +1,446 @@
+/*-----------------------------------------------------------------------------+
+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_CONCEPT_ELEMENT_MAP_HPP_JOFA_100921
+#define BOOST_ITL_CONCEPT_ELEMENT_MAP_HPP_JOFA_100921
+
+#include <boost/mpl/and.hpp>
+#include <boost/mpl/not.hpp>
+#include <boost/itl/detail/map_algo.hpp>
+#include <boost/itl/type_traits/is_total.hpp>
+#include <boost/itl/type_traits/absorbs_neutrons.hpp>
+#include <boost/itl/type_traits/is_associative_element_container.hpp>
+#include <boost/itl/type_traits/is_combinable.hpp>
+
+namespace boost{ namespace itl
+{
+
+//NOTE: Some forward declarations are needed by some compilers.
+template<class Type, class Predicate>
+typename enable_if<is_associative_element_container<Type>, Type>::type&
+erase_if(const Predicate& pred, Type& object);
+
+
+//==============================================================================
+//= Containedness<ElementMap>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- bool within(c P&, c T&) T:{m} P:{b} fragment_types
+//------------------------------------------------------------------------------
+/** Checks if a key-value pair is in the map */
+template<class Type>
+typename enable_if<is_element_map<Type>, bool>::type
+within(const typename Type::element_type& value_pair, const Type& super)
+{
+ typedef typename Type::const_iterator const_iterator;
+ const_iterator found_ = super.find(value_pair.first);
+ return found_ != super.end() && found_->second == value_pair.second;
+}
+
+//------------------------------------------------------------------------------
+//- bool contains(c T&, c P&) T:{m} P:{b} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_element_map<Type>, bool>::type
+contains(const Type& super, const typename Type::element_type& value_pair)
+{
+ return itl::within(value_pair, super);
+}
+
+//==============================================================================
+//= Equivalences and Orderings<ElementSet|ElementMap>
+//==============================================================================
+
+/** Protonic equality is equality on all elements that do not carry a neutron as content. */
+template<class Type>
+inline typename enable_if<is_element_map<Type>, bool>::type
+is_protonic_equal(const Type& lhs, const Type& rhs)
+{
+ return Map::lexicographical_protonic_equal(lhs, rhs);
+}
+
+//==============================================================================
+//= Addition
+//==============================================================================
+/** \c add inserts \c value_pair into the map if it's key does
+ not exist in the map.
+ If \c value_pairs's key value exists in the map, it's data
+ value is added to the data value already found in the map. */
+template <class Type>
+typename enable_if<is_element_map<Type>, Type>::type&
+add(Type& object, const typename Type::value_type& value_pair)
+{
+ return object.add(value_pair);
+}
+
+/** \c add add \c value_pair into the map using \c prior as a hint to
+ insert \c value_pair after the position \c prior is pointing to. */
+template <class Type>
+typename enable_if<is_element_map<Type>, typename Type::iterator>::type
+add(Type& object, typename Type::iterator prior,
+ const typename Type::value_type& value_pair)
+{
+ return object.add(prior, value_pair);
+}
+
+//==============================================================================
+//= Erasure
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& erase(T&, c P&) T:{m} P:{b} fragment_type
+//------------------------------------------------------------------------------
+template <class Type>
+typename enable_if<is_element_map<Type>, typename Type::size_type>::type
+erase(Type& object, const typename Type::element_type& value_pair)
+{
+ typedef typename Type::size_type size_type;
+ typedef typename Type::iterator iterator;
+ typedef typename Type::on_neutron_absorbtion on_neutron_absorbtion;
+
+ if(on_neutron_absorbtion::is_absorbable(value_pair.second))
+ return neutron<size_type>::value();
+
+ iterator it_ = object.find(value_pair.first);
+ if(it_ != object.end() && value_pair.second == it_->second)
+ {
+ object.erase(it_);
+ return unon<size_type>::value();
+ }
+
+ return neutron<size_type>::value();
+}
+
+template<class Type>
+typename enable_if<is_element_map<Type>, Type>::type&
+erase(Type& object, const typename Type::set_type& erasure)
+{
+ typedef typename Type::set_type set_type;
+ ITL_const_FORALL(typename set_type, elem_, erasure)
+ itl::erase(object, *elem_);
+
+ return object;
+}
+
+//==============================================================================
+//= Subtraction
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& subtract(T&, c P&) T:{m} P:{b} fragment_type
+//------------------------------------------------------------------------------
+template <class Type>
+inline typename enable_if<is_element_map<Type>, Type>::type&
+subtract(Type& object, const typename Type::element_type& operand)
+{
+ return object.subtract(operand);
+}
+
+//------------------------------------------------------------------------------
+//- T& subtract(T&, c P&) T:{m} P:{e} key_type
+//------------------------------------------------------------------------------
+template <class Type>
+typename enable_if<is_element_map<Type>, Type>::type&
+subtract(Type& object, const typename Type::domain_type& key_value)
+{
+ return itl::erase(object, key_value);
+}
+
+//------------------------------------------------------------------------------
+//- T& subtract(T&, c P&) T:{m} P:{s} set key_type
+//------------------------------------------------------------------------------
+template <class Type>
+inline typename enable_if<is_element_map<Type>, Type>::type&
+operator -= (Type& object, const typename Type::set_type& subtrahend)
+{
+ return Set::erase(object, subtrahend); //JODO
+}
+
+template <class Type>
+inline typename enable_if<is_element_map<Type>, Type>::type
+operator - (Type object, const typename Type::set_type& subtrahend)
+{
+ return object -= subtrahend;
+}
+
+//==============================================================================
+//= Intersection
+//==============================================================================
+template<class Type>
+inline typename enable_if<is_element_map<Type>, void>::type
+add_intersection(Type& section, const Type& object,
+ const typename Type::element_type& operand)
+{
+ object.add_intersection(section, operand);
+}
+
+template<class Type>
+inline typename enable_if<is_element_map<Type>, void>::type
+add_intersection(Type& section, const Type& object, const Type& operand)
+{
+ ITL_const_FORALL(typename Type, it_, operand)
+ itl::add_intersection(section, object, *it_);
+}
+
+//------------------------------------------------------------------------------
+//- T& op &=(T&, c P&) T:{m} P:{b m} fragment_types
+//------------------------------------------------------------------------------
+
+template<class Type>
+inline typename enable_if<mpl::and_<is_element_map<Type>, is_total<Type> >, Type>::type&
+operator &=(Type& object, const typename Type::element_type& operand)
+{
+ object.add(operand);
+ return object;
+}
+
+template<class Type>
+inline typename enable_if<mpl::and_<is_element_map<Type>, mpl::not_<is_total<Type> > >, Type>::type&
+operator &=(Type& object, const typename Type::element_type& operand)
+{
+ Type section;
+ itl::add_intersection(section, object, operand);
+ object.swap(section);
+ return object;
+}
+
+template<class Type>
+inline typename enable_if<is_element_map<Type>, Type>::type
+operator & (Type object, const typename Type::element_type& operand)
+{
+ return object &= operand;
+}
+
+template<class Type>
+inline typename enable_if<is_element_map<Type>, Type>::type
+operator & (const typename Type::element_type& operand, Type object)
+{
+ return object &= operand;
+}
+
+
+template<class Type>
+inline typename enable_if<mpl::and_<is_element_map<Type>, is_total<Type> >, Type>::type&
+operator &=(Type& object, const Type& operand)
+{
+ object += operand;
+ return object;
+}
+
+template<class Type>
+inline typename enable_if<mpl::and_<is_element_map<Type>, mpl::not_<is_total<Type> > >, Type>::type&
+operator &=(Type& object, const Type& operand)
+{
+ Type section;
+ itl::add_intersection(section, object, operand);
+ object.swap(section);
+ return object;
+}
+
+template<class Type>
+inline typename enable_if<is_element_map<Type>, Type>::type
+operator & (Type object, const Type& operand)
+{
+ return object &= operand;
+}
+
+template<class Type>
+inline typename enable_if<is_element_map<Type>, Type>::type
+operator & (Type object, const typename Type::key_object_type& operand)
+{
+ return object &= operand; //JODO test a - (a & s) == a - s
+}
+
+template<class Type>
+inline typename enable_if<is_element_map<Type>, Type>::type
+operator & (const typename Type::key_object_type& operand, Type object)
+{
+ return object &= operand; //JODO test a - (s & a) == a - s
+}
+
+//==============================================================================
+//= Intersection<ElementMap> bool intersects(x,y)
+//==============================================================================
+template<class Type, class CoType>
+inline typename enable_if< mpl::and_< is_element_map<Type>
+ , is_total<Type> >
+ , bool>::type
+intersects(const Type&, const CoType&)
+{
+ return true;
+}
+
+template<class Type>
+inline typename enable_if< mpl::and_< is_element_map<Type>
+ , mpl::not_<is_total<Type> > >
+ , bool>::type
+intersects(const Type& object, const typename Type::domain_type& operand)
+{
+ return itl::contains(object, operand);
+}
+
+template<class Type>
+inline typename enable_if< mpl::and_< is_element_map<Type>
+ , mpl::not_<is_total<Type> > >
+ , bool>::type
+intersects(const Type& object, const typename Type::set_type& operand)
+{
+ if(object.iterative_size() < operand.iterative_size())
+ return Map::intersects(object, operand);
+ else
+ return Map::intersects(operand, object);
+}
+
+template<class Type>
+inline typename enable_if< mpl::and_< is_element_map<Type>
+ , mpl::not_<is_total<Type> > >
+ , bool>::type
+intersects(const Type& object, const typename Type::element_type& operand)
+{
+ Type intersection; //JODO opti
+ itl::add_intersection(intersection, object, operand);
+ return !intersection.empty();
+}
+
+template<class Type>
+inline typename enable_if< mpl::and_< is_element_map<Type>
+ , mpl::not_<is_total<Type> > >
+ , bool>::type
+intersects(const Type& object, const Type& operand)
+{
+ if(object.iterative_size() < operand.iterative_size())
+ return Map::intersects(object, operand);
+ else
+ return Map::intersects(operand, object);
+}
+
+//==============================================================================
+//= Symmetric difference
+//==============================================================================
+template<class Type>
+inline typename enable_if<is_element_map<Type>, Type>::type&
+flip(Type& object, const typename Type::element_type& operand)
+{
+ return object.flip(operand);
+}
+
+template<class Type, class CoType>
+inline typename enable_if< mpl::and_< is_element_map<Type>
+ , is_total<Type>
+ , absorbs_neutrons<Type> >
+ , Type>::type&
+operator ^= (Type& object, const CoType&)
+{
+ itl::clear(object);
+ return object;
+}
+
+template<class Type>
+inline typename enable_if< mpl::and_< is_element_map<Type>
+ , is_total<Type>
+ , mpl::not_<absorbs_neutrons<Type> > >
+ , Type>::type&
+operator ^= (Type& object, const typename Type::element_type& operand)
+{
+ return object.flip(operand);
+}
+
+template<class Type>
+inline typename enable_if< mpl::and_< is_element_map<Type>
+ , is_total<Type>
+ , mpl::not_<absorbs_neutrons<Type> > >
+ , Type>::type&
+operator ^= (Type& object, const Type& operand)
+{
+ ITL_const_FORALL(typename Type, it_, operand)
+ itl::flip(object, *it_);
+
+ ITL_FORALL(typename Type, it2_, object)
+ it2_->second = neutron<typename Type::codomain_type>::value();
+
+ return object;
+}
+
+
+template<class Type>
+inline typename enable_if< mpl::and_< is_element_map<Type>
+ , mpl::not_<is_total<Type> > >
+ , Type>::type&
+operator ^= (Type& object, const typename Type::element_type& operand)
+{
+ return itl::flip(object, operand);
+}
+
+/** Symmetric subtract map \c x2 and \c *this.
+ So \c *this becomes the symmetric difference of \c *this and \c x2 */
+template<class Type>
+inline typename enable_if< mpl::and_< is_element_map<Type>
+ , mpl::not_<is_total<Type> > >
+ , Type>::type&
+operator ^= (Type& object, const Type& operand)
+{
+ typedef typename Type::const_iterator const_iterator;
+ const_iterator it_ = operand.begin();
+ while(it_ != operand.end())
+ itl::flip(object, *it_++);
+
+ return object;
+}
+
+
+//==============================================================================
+//= Set selection
+//==============================================================================
+template<class Type>
+inline typename enable_if<is_element_map<Type>,
+ typename Type::set_type>::type&
+domain(typename Type::set_type& domain_set, const Type& object)
+{
+ typename Type::set_type::iterator prior_ = domain_set.end();
+ typename Type::const_iterator it_ = object.begin();
+ while(it_ != object.end())
+ prior_ = domain_set.insert(prior_, (*it_++).first);
+
+ return domain_set;
+}
+
+//==============================================================================
+//= Neutron absorbtion
+//==============================================================================
+template<class Type>
+inline typename enable_if<mpl::and_< is_element_map<Type>
+ , absorbs_neutrons<Type> >, Type>::type&
+absorb_neutrons(Type& object)
+{
+ typedef typename Type::element_type element_type;
+ return itl::erase_if(content_is_neutron<element_type>(), object);
+}
+
+template<class Type>
+inline typename enable_if<mpl::and_< is_element_map<Type>
+ , mpl::not_<absorbs_neutrons<Type> > >
+ , Type>::type&
+absorb_neutrons(Type&){}
+
+//==============================================================================
+//= Streaming<ElementMap>
+//==============================================================================
+template<class CharType, class CharTraits, class Type>
+inline typename enable_if<is_element_map<Type>, std::basic_ostream<CharType, CharTraits> >::type&
+operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
+{
+ stream << "{";
+ ITL_const_FORALL(typename Type, it, object)
+ stream << "(" << it->first << "->" << it->second << ")";
+
+ return stream << "}";
+}
+
+
+}} // namespace boost itl
+
+#endif
+
+
Added: sandbox/itl/boost/itl/concept/element/set.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/concept/element/set.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -0,0 +1,141 @@
+/*-----------------------------------------------------------------------------+
+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_CONCEPT_ELEMENT_SET_HPP_JOFA_100921
+#define BOOST_ITL_CONCEPT_ELEMENT_SET_HPP_JOFA_100921
+
+#include <boost/itl/type_traits/is_combinable.hpp>
+
+namespace boost{ namespace itl
+{
+
+//==============================================================================
+//= Addition
+//==============================================================================
+/** \c add inserts \c operand into the map if it's key does
+ not exist in the map.
+ If \c operands's key value exists in the map, it's data
+ value is added to the data value already found in the map. */
+template <class Type>
+typename enable_if<is_element_set<Type>, Type>::type&
+add(Type& object, const typename Type::element_type& operand)
+{
+ object.insert(operand);
+ return object;
+}
+
+/** \c add add \c operand into the map using \c prior as a hint to
+ insert \c operand after the position \c prior is pointing to. */
+template <class Type>
+typename enable_if<is_element_set<Type>, typename Type::iterator>::type
+add(Type& object, typename Type::iterator prior,
+ const typename Type::element_type& operand)
+{
+ return object.insert(prior, operand);
+}
+
+//==============================================================================
+//= Subtraction
+//==============================================================================
+/** If the \c operand's key value is in the map, it's data value is
+ subtraced from the data value stored in the map. */
+template<class Type>
+typename enable_if<is_element_set<Type>, Type>::type&
+subtract(Type& object, const typename Type::element_type& operand)
+{
+ typedef typename Type::iterator iterator;
+ iterator it_ = object.find(operand);
+ if(it_ != object.end())
+ object.erase(it_);
+
+ return object;
+}
+
+
+//==============================================================================
+//= Intersection
+//==============================================================================
+template<class Type>
+inline typename enable_if<is_element_set<Type>, Type>::type
+operator & (Type object, const Type& operand)
+{
+ return object &= operand;
+}
+
+template<class Type>
+inline typename enable_if<is_element_set<Type>, bool>::type
+intersects(const Type& object, const typename Type::domain_type& operand)
+{
+ return itl::contains(object, operand);
+}
+
+template<class Type>
+inline typename enable_if<is_element_set<Type>, bool>::type
+intersects(const Type& object, const Type& operand)
+{
+ if(iterative_size(object) < iterative_size(operand))
+ return Set::intersects(object, operand);
+ else
+ return Set::intersects(operand, object);
+}
+
+//==============================================================================
+//= Symmetric difference
+//==============================================================================
+template<class Type>
+inline typename enable_if<is_element_set<Type>, Type>::type&
+flip(Type& object, const typename Type::element_type& operand)
+{
+ typedef typename Type::iterator iterator;
+ std::pair<iterator,bool> insertion = object.insert(operand);
+ if(!insertion.second)
+ object.erase(insertion.first);
+
+ return object;
+}
+
+template<class Type>
+inline typename enable_if<is_element_set<Type>, Type>::type&
+operator ^= (Type& object, const typename Type::element_tpye& operand)
+{
+ return itl::flip(object, operand);
+}
+
+/** Symmetric subtract map \c x2 and \c *this.
+ So \c *this becomes the symmetric difference of \c *this and \c x2 */
+template<class Type>
+inline typename enable_if<is_element_set<Type>, Type>::type&
+operator ^= (Type& object, const Type& operand)
+{
+ typedef typename Type::const_iterator const_iterator;
+ const_iterator it_ = operand.begin();
+ while(it_ != operand.end())
+ itl::flip(object, *it_++);
+
+ return object;
+}
+
+//==============================================================================
+//= Streaming<ElementSet>
+//==============================================================================
+template<class CharType, class CharTraits, class Type>
+inline typename enable_if<is_element_set<Type>, std::basic_ostream<CharType, CharTraits> >::type&
+operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
+{
+ stream << "{";
+ ITL_const_FORALL(typename Type, it, object)
+ stream << *it << " ";
+
+ return stream << "}";
+}
+
+
+}} // namespace boost itl
+
+#endif
+
+
Added: sandbox/itl/boost/itl/concept/element/set_or_map.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/concept/element/set_or_map.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -0,0 +1,477 @@
+/*-----------------------------------------------------------------------------+
+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_CONCEPT_ELEMENT_SET_OR_MAP_HPP_JOFA_100921
+#define BOOST_ITL_CONCEPT_ELEMENT_SET_OR_MAP_HPP_JOFA_100921
+
+#include <boost/itl/type_traits/is_associative_element_container.hpp>
+#include <boost/itl/type_traits/is_key_container_of.hpp>
+#include <boost/itl/type_traits/is_combinable.hpp>
+#include <boost/itl/concept/element/set.hpp>
+#include <boost/itl/concept/element/map.hpp>
+
+namespace boost{ namespace itl
+{
+//JODO Declaration forwarding for gcc-3.4.4
+template <class Type>
+typename enable_if<is_element_set<Type>, Type>::type&
+add(Type& object, const typename Type::element_type& operand);
+
+//==============================================================================
+//= 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);
+}
+
+
+//==============================================================================
+//= Containedness<ElementSet|ElementMap>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- bool within(c P&, c T&) T:{s}|{m} P:{e}|{i} fragment_types|key_types
+//------------------------------------------------------------------------------
+/** Checks if a key is in the associative container */
+template<class Type>
+typename enable_if<is_associative_element_container<Type>, bool>::type
+within(const typename Type::domain_type& key, const Type& super)
+{
+ return !(super.find(key) == super.end());
+}
+
+//------------------------------------------------------------------------------
+//- bool within(c P&, c T&) T:{s}|{m} P:{s'} fragment_types|key_types
+//------------------------------------------------------------------------------
+template<class SubT, class SuperT>
+typename enable_if<mpl::and_< is_associative_element_container<SuperT>
+ , is_key_container_of<SubT, SuperT> >,
+ bool>::type
+within(const SubT& sub, const SuperT& super)
+{
+ if(itl::is_empty(sub)) return true;
+ if(itl::is_empty(super)) return false;
+ if(itl::size(super) < itl::size(sub)) return false;
+
+ typename SubT::const_iterator common_lwb_;
+ typename SubT::const_iterator common_upb_;
+ if(!Set::common_range(common_lwb_, common_upb_, sub, super))
+ return false;
+
+ typename SubT::const_iterator sub_ = sub.begin();
+ typename SuperT::const_iterator super_;
+ while(sub_ != sub.end())
+ {
+ super_ = super.find(SubT::key_value(sub_));
+ if(super_ == super.end())
+ return false;
+ else if(!co_equal(sub_, super_, &sub, &super))
+ return false;
+
+ ++sub_;
+ }
+ return true;
+}
+
+//------------------------------------------------------------------------------
+//- bool contains(c T&, c P&) T:{s}|{m} P:{e}|{i} fragment_types|key_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_associative_element_container<Type>, bool>::type
+contains(const Type& super, const typename Type::domain_type& key)
+{
+ return itl::within(key, super);
+}
+
+//------------------------------------------------------------------------------
+//- bool contains(c T&, c P&) T:{s}|{m} P:{s'} fragment_types|key_types
+//------------------------------------------------------------------------------
+template<class SubT, class SuperT>
+typename enable_if<mpl::and_< is_associative_element_container<SuperT>
+ , is_key_container_of<SubT, SuperT> >,
+ bool>::type
+contains(const SuperT& super, const SubT& sub)
+{
+ return itl::within(sub, super);
+}
+
+//==============================================================================
+//= Equivalences and Orderings
+//==============================================================================
+
+#ifdef BOOST_MSVC
+#pragma warning(push)
+#pragma warning(disable:4996) //'std::equal': Function call with parameters that may be unsafe - this call relies on the caller to check that the passed values are correct. To disable this warning, use -D_SCL_SECURE_NO_WARNINGS. See documentation on how to use Visual C++ 'Checked Iterators'
+#endif // I do guarantee here that I am using the parameters correctly :)
+
+/** Standard equality, which is lexicographical equality of the sets
+ as sequences, that are given by their Compare order. */
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, bool>::type
+operator == (const Type& left, const Type& right)
+{
+ return left.size() == right.size()
+ && std::equal(left.begin(), left.end(), right.begin());
+}
+
+#ifdef BOOST_MSVC
+#pragma warning(pop)
+#endif
+
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, bool>::type
+is_element_equal(const Type& left, const Type& right)
+{ return left == right; }
+
+
+/* Strict weak less ordering which is given by the Compare order */
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, bool>::type
+operator < (const Type& left, const Type& right)
+{
+ return std::lexicographical_compare(
+ left.begin(), left.end(), right.begin(), right.end(),
+ typename Type::element_compare()
+ );
+}
+
+//==============================================================================
+//= Addition
+//==============================================================================
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type&
+operator += (Type& object, const typename Type::element_type& operand)
+{
+ return itl::add(object, operand);
+}
+
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator + (Type object, const typename Type::element_type& operand)
+{
+ return object += operand;
+}
+
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator + (const typename Type::element_type& operand, Type object)
+{
+ return object += operand;
+}
+
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator += (Type& object, const Type& operand)
+{
+ return Set::add(object, operand);
+}
+
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator + (Type object, const Type& operand)
+{
+ return object += operand;
+}
+
+//==============================================================================
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type&
+operator |= (Type& object, const typename Type::element_type& operand)
+{
+ return itl::add(object, operand);
+}
+
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator | (Type object, const typename Type::element_type& operand)
+{
+ return object += operand;
+}
+
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator | (const typename Type::element_type& operand, Type object)
+{
+ return object += operand;
+}
+
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type&
+operator |= (Type& object, const Type& operand)
+{
+ return Set::add(object, operand);
+}
+
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator | (Type object, const Type& operand)
+{
+ return object += operand;
+}
+
+
+//==============================================================================
+//= Insertion
+//==============================================================================
+//------------------------------------------------------------------------------
+//- V insert(T&, c P&) T:{s}|{m} P:{e}|{b} fragment_type
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_associative_element_container<Type>,
+ std::pair<typename Type::iterator,bool> >::type
+insert(Type& object, const typename Type::element_type& operand)
+{
+ return object.insert(operand);
+}
+
+template<class Type>
+typename enable_if<is_associative_element_container<Type>,
+ typename Type::iterator>::type
+insert(Type& object, typename Type::iterator prior,
+ const typename Type::element_type& operand)
+{
+ return object.insert(prior, operand);
+}
+
+//------------------------------------------------------------------------------
+//- T insert(T&, c T&) T:{s m} map fragment_type
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_associative_element_container<Type>, Type>::type&
+insert(Type& object, const Type& addend)
+{
+ typedef typename Type::iterator iterator;
+
+ iterator prior_ = object.end();
+ ITL_const_FORALL(typename Type, elem_, addend)
+ itl::insert(object, prior_, *elem_);
+
+ return object;
+}
+
+
+//==============================================================================
+//= Erasure
+//==============================================================================
+template<class Type>
+typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
+erase(Type& object, const typename Type::domain_type& key_value)
+{
+ typedef typename Type::size_type size_type;
+ typename Type::iterator it_ = object.find(key_value);
+ if(it_ != object.end())
+ {
+ object.erase(it_);
+ return unon<size_type>::value();
+ }
+ return neutron<size_type>::value();
+}
+
+template<class Type>
+typename enable_if<is_associative_element_container<Type>, Type>::type&
+erase(Type& object, const Type& erasure)
+{
+ ITL_const_FORALL(typename Type, elem_, erasure)
+ itl::erase(object, *elem_);
+
+ return object;
+}
+
+
+
+//==============================================================================
+//= Subtraction<ElementSet|ElementMap>
+//==============================================================================
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type&
+operator -= (Type& object, const typename Type::element_type& operand)
+{
+ return itl::subtract(object, operand);
+}
+
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator - (Type object, const typename Type::element_type& operand)
+{
+ return object -= operand;
+}
+
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type&
+operator -= (Type& object, const Type& subtrahend)
+{
+ ITL_const_FORALL(typename Type, it_, subtrahend)
+ itl::subtract(object, *it_);
+
+ return object;
+}
+
+template <class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator - (Type object, const Type& subtrahend)
+{
+ return object -= subtrahend;
+}
+
+
+//==============================================================================
+//= Intersection
+//==============================================================================
+//------------------------------------------------------------------------------
+//- void add_intersection(T&, c T&, c P&) T:{s}{m} P:{e}{e} key_type
+//------------------------------------------------------------------------------
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, void>::type
+add_intersection(Type& section, const Type& object,
+ const typename Type::domain_type& operand)
+{
+ typedef typename Type::const_iterator const_iterator;
+ const_iterator it_ = object.find(operand);
+ if(it_ != object.end())
+ itl::add(section, *it_);
+}
+
+//------------------------------------------------------------------------------
+//- void add_intersection(T&, c T&, c P&) T:{s}{m} P:{s}{s} set key_type
+//------------------------------------------------------------------------------
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, void>::type
+add_intersection(Type& section, const Type& object,
+ const typename Type::key_object_type& operand)
+{
+ typedef typename Type::key_object_type key_object_type;
+ typedef typename key_object_type::const_iterator const_iterator;
+ const_iterator common_lwb_, common_upb_;
+ if(!Set::common_range(common_lwb_, common_upb_, operand, object))
+ return;
+
+ const_iterator sec_ = common_lwb_;
+ while(sec_ != common_upb_)
+ add_intersection(section, object, *sec_++);
+}
+
+//------------------------------------------------------------------------------
+//- Intersection<ElementMap|ElementSet>
+//------------------------------------------------------------------------------
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type&
+operator &= (Type& object, const typename Type::domain_type& operand)
+{
+ Type section;
+ add_intersection(section, object, operand);
+ object.swap(section);
+ return object;
+}
+
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator & (Type object, const typename Type::domain_type& operand)
+{
+ return object &= operand;
+}
+
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator & (const typename Type::domain_type& operand, Type object)
+{
+ return object &= operand;
+}
+
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type&
+operator &= (Type& object, const typename Type::key_object_type& operand)
+{
+ Type section;
+ add_intersection(section, object, operand);
+ object.swap(section);
+ return object;
+}
+//------------------------------------------------------------------------------
+
+template<class Type, class CoType>
+inline typename enable_if<is_associative_element_container<Type>, bool>::type
+disjoint(const Type& left, const Type& right)
+{
+ return !intersects(left, right);
+}
+
+//==============================================================================
+//= Symmetric difference<ElementSet|ElementMap>
+//==============================================================================
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator ^ (Type object, const typename Type::element_type& operand)
+{
+ return itl::flip(object, operand);
+}
+
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator ^ (const typename Type::element_type& operand, Type object)
+{
+ return itl::flip(object, operand);
+}
+
+template<class Type>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type
+operator ^ (Type object, const Type& operand)
+{
+ return object ^= operand;
+}
+
+
+//==============================================================================
+//= Manipulation by predicates
+//==============================================================================
+template<class Type, class Predicate>
+typename enable_if<is_associative_element_container<Type>, Type>::type&
+erase_if(const Predicate& pred, Type& object)
+{
+ typename Type::iterator it_ = object.begin();
+ while(it_ != object.end())
+ if(pred(*it_))
+ itl::erase(object, it_++);
+ else ++it_;
+ return object;
+}
+
+template<class Type, class Predicate>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type&
+add_if(const Predicate& pred, Type& object, const Type& src)
+{
+ typename Type::const_iterator it_ = src.begin();
+ while(it_ != src.end())
+ if(pred(*it_))
+ itl::add(object, *it_++);
+
+ return object;
+}
+
+template<class Type, class Predicate>
+inline typename enable_if<is_associative_element_container<Type>, Type>::type&
+assign_if(const Predicate& pred, Type& object, const Type& src)
+{
+ itl::clear(object);
+ return add_if(object, src, pred);
+}
+
+
+
+}} // namespace boost itl
+
+#endif
+
+
Added: sandbox/itl/boost/itl/concept/interval/base.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/concept/interval/base.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -0,0 +1,49 @@
+/*-----------------------------------------------------------------------------+
+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_CONCEPT_INTERVAL_BASE_HPP_JOFA_100920
+#define BOOST_ITL_CONCEPT_INTERVAL_BASE_HPP_JOFA_100920
+
+#include <boost/itl/type_traits/is_combinable.hpp>
+
+namespace boost{ namespace itl
+{
+
+template<class Type>
+inline typename enable_if<is_interval_map<Type>, typename Type::segment_type>::type
+make_segment(const typename Type::element_type& element)
+{
+ typedef typename Type::interval_type interval_type;
+ typedef typename Type::segment_type segment_type;
+ return segment_type(interval_type(element.key), element.data);
+}
+
+namespace segmental
+{
+ template<class Type>
+ typename enable_if<is_interval_set<Type>, bool>::type
+ is_joinable(typename Type::iterator it_, typename Type::iterator next_, Type* = 0)
+ {
+ return touches(*it_, *next_);
+ }
+
+ template<class Type>
+ typename enable_if<is_interval_map<Type>, bool>::type
+ is_joinable(typename Type::iterator it_, typename Type::iterator next_, Type* = 0)
+ {
+ return touches(it_->first, next_->first)
+ && it_->second == next_->second ;
+ }
+}
+
+
+
+}} // namespace boost itl
+
+#endif
+
+
Added: sandbox/itl/boost/itl/concept/interval/map.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/concept/interval/map.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -0,0 +1,629 @@
+/*-----------------------------------------------------------------------------+
+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_CONCEPT_INTERVAL_MAP_HPP_JOFA_100920
+#define BOOST_ITL_CONCEPT_INTERVAL_MAP_HPP_JOFA_100920
+
+#include <boost/itl/type_traits/element_type_of.hpp>
+#include <boost/itl/type_traits/segment_type_of.hpp>
+#include <boost/itl/type_traits/absorbs_neutrons.hpp>
+#include <boost/itl/type_traits/is_combinable.hpp>
+
+namespace boost{ namespace itl
+{
+
+//==============================================================================
+//= Containedness<IntervalMap>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- bool contains(c T&, c P&) T:{M} P:{b p M} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, bool>::type
+contains(const Type& super, const typename Type::element_type& key_value_pair)
+{
+ typedef typename Type::const_iterator const_iterator;
+ const_iterator it_ = super.find(key_value_pair.key);
+ return it_ != super.end() && it_->second == key_value_pair.data;
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, bool>::type
+contains(const Type& super, const typename Type::segment_type& sub_segment)
+{
+ typedef typename Type::interval_type interval_type;
+ typedef typename Type::const_iterator const_iterator;
+
+ interval_type sub_interval = sub_segment.first;
+ if(itl::is_empty(sub_interval))
+ return true;
+
+ std::pair<const_iterator, const_iterator> exterior = super.equal_range(sub_interval);
+ if(exterior.first == exterior.second)
+ return false;
+
+ const_iterator last_overlap = prior(exterior.second);
+
+ if(!(sub_segment.second == exterior.first->second) )
+ return false;
+
+ return
+ itl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
+ && Interval_Map::is_joinable(super, exterior.first, last_overlap);
+}
+
+template<class Type, class CoType>
+typename enable_if<is_concept_compatible<is_interval_map, Type, CoType>, bool>::type
+contains(const Type& super, const CoType& sub)
+{
+ return Interval_Set::within(sub, super);
+}
+
+
+//------------------------------------------------------------------------------
+//- bool contains(c T&, c P&) T:{M} P:{e i S} key_types : total
+//------------------------------------------------------------------------------
+template<class Type, class CoType>
+typename enable_if< mpl::and_< is_interval_map<Type>
+ , is_total<Type>
+ , is_cross_derivative<Type, CoType> >
+ , bool>::type
+contains(const Type& super, const CoType& sub)
+{
+ return true;
+}
+
+//------------------------------------------------------------------------------
+//- bool contains(c T&, c P&) T:{M} P:{e i S} key_types : partial
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if< mpl::and_< is_interval_map<Type>
+ , mpl::not_<is_total<Type> > >
+ , bool>::type
+contains(const Type& super, const typename Type::domain_type& key)
+{
+ return super.find(key) != super.end();
+}
+
+template<class Type>
+typename enable_if< mpl::and_< is_interval_map<Type>
+ , mpl::not_<is_total<Type> > >
+ , bool>::type
+contains(const Type& super, const typename Type::interval_type& sub_interval)
+{
+ typedef typename Type::const_iterator const_iterator;
+
+ if(itl::is_empty(sub_interval))
+ return true;
+
+ std::pair<const_iterator, const_iterator> exterior = super.equal_range(sub_interval);
+ if(exterior.first == exterior.second)
+ return false;
+
+ const_iterator last_overlap = prior(exterior.second);
+
+ return
+ itl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
+ && Interval_Set::is_joinable(super, exterior.first, last_overlap);
+}
+
+template<class Type, class KeyT>
+typename enable_if< mpl::and_< is_concept_combinable<is_interval_map, is_interval_set, Type, KeyT>
+ , mpl::not_<is_total<Type> > >
+ , bool>::type
+contains(const Type& super, const KeyT& sub)
+{
+ return Interval_Set::within(sub, super);
+}
+
+
+//==============================================================================
+//= Addition<IntervalMap>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& add(T&, c P&) T:{M} P:{b p} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+add(Type& object, const typename Type::element_type& operand)
+{
+ return object.add(operand);
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+add(Type& object, const typename Type::segment_type& operand)
+{
+ return object.add(operand);
+}
+
+//------------------------------------------------------------------------------
+//- T& add(T&, J, c P&) T:{M} P:{p} segment_type
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, typename Type::iterator >::type
+add(Type& object, typename Type::iterator prior_,
+ const typename Type::segment_type& operand)
+{
+ return object.add(prior_, operand);
+}
+
+//==============================================================================
+//= Insertion<IntervalMap>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& insert(T&, c P&) T:{M} P:{b p} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+insert(Type& object, const typename Type::element_type& operand)
+{
+ return object.insert(operand);
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+insert(Type& object, const typename Type::segment_type& operand)
+{
+ return object.insert(operand);
+}
+
+//------------------------------------------------------------------------------
+//- T& insert(T&, J, c P&) T:{M} P:{p} with hint
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, typename Type::iterator>::type
+insert(Type& object, typename Type::iterator prior,
+ const typename Type::segment_type& operand)
+{
+ return object.insert(prior, operand);
+}
+
+
+//==============================================================================
+//= Erasure<IntervalMap>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& erase(T&, c P&) T:{M} P:{e i} key_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+erase(Type& object, const typename Type::domain_type& minuend)
+{
+ return object.erase(minuend);
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+erase(Type& object, const typename Type::interval_type& minuend)
+{
+ return object.erase(minuend);
+}
+
+//------------------------------------------------------------------------------
+//- T& erase(T&, c P&) T:{M} P:{b p} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+erase(Type& object, const typename Type::element_type& minuend)
+{
+ return object.erase(minuend);
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+erase(Type& object, const typename Type::segment_type& minuend)
+{
+ return object.erase(minuend);
+}
+
+//==============================================================================
+//= Subtraction<IntervalMap>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& subtract(T&, c P&) T:{M} P:{b p} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+subtract(Type& object, const typename Type::element_type& operand)
+{
+ return object.subtract(operand);
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+subtract(Type& object, const typename Type::segment_type& operand)
+{
+ return object.subtract(operand);
+}
+
+//------------------------------------------------------------------------------
+//- T& subtract(T&, c P&) T:{M} P:{e i} key_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+subtract(Type& object, const typename Type::domain_type& operand)
+{
+ return object.erase(operand);
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+subtract(Type& object, const typename Type::interval_type& operand)
+{
+ return object.erase(operand);
+}
+
+//==============================================================================
+//= Selective Update<IntervalMap>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& set_at(T&, c P&) T:{M} P:{e i}
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+set_at(Type& object, const typename Type::segment_type& operand)
+{
+ itl::erase(object, operand.first);
+ return itl::insert(object, operand);
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+set_at(Type& object, const typename Type::element_type& operand)
+{
+ return itl::set_at(object, make_segment<Type>(operand));
+}
+
+//==============================================================================
+//= Intersection<IntervalMap>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& subtract(T&, c P&) T:{M} P:{b p} fragment_type
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, void>::type
+add_intersection(Type& section, const Type& object,
+ const typename Type::element_type& operand)
+{
+ object.add_intersection(section, operand);
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, void>::type
+add_intersection(Type& section, const Type& object,
+ const typename Type::segment_type& operand)
+{
+ object.add_intersection(section, operand);
+}
+
+//------------------------------------------------------------------------------
+//- T& subtract(T&, c P&) T:{M} P:{M'} map fragment_type total
+//------------------------------------------------------------------------------
+template<class Type, class MapT>
+typename enable_if
+<
+ mpl::and_< is_total<Type>
+ , is_concept_compatible<is_interval_map, Type, MapT> >
+ , void
+>::type
+add_intersection(Type& section, const Type& object, const MapT& operand)
+{
+ section += object;
+ section += operand;
+}
+
+//------------------------------------------------------------------------------
+//- T& subtract(T&, c P&) T:{M} P:{M'} map fragment_type partial
+//------------------------------------------------------------------------------
+template<class Type, class MapT>
+typename enable_if
+<
+ mpl::and_< mpl::not_<is_total<Type> >
+ , is_concept_compatible<is_interval_map, Type, MapT> >
+ , void
+>::type
+add_intersection(Type& section, const Type& object, const MapT& operand)
+{
+ typedef typename Type::segment_type segment_type;
+ typedef typename Type::interval_type interval_type;
+ typedef typename MapT::const_iterator const_iterator;
+
+ if(operand.empty())
+ return;
+ const_iterator common_lwb, common_upb;
+ if(!Set::common_range(common_lwb, common_upb, operand, object))
+ return;
+ const_iterator it_ = common_lwb;
+ while(it_ != common_upb)
+ add_intersection(section, object, *it_++);
+}
+
+//------------------------------------------------------------------------------
+//- T& subtract(T&, c P&) T:{M} P:{e i S} key_type
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, void>::type
+add_intersection(Type& section, const Type& object,
+ const typename Type::domain_type& key_value)
+{
+ typedef typename Type::interval_type interval_type;
+ typedef typename Type::segment_type segment_type;
+ typedef typename Type::const_iterator const_iterator;
+
+ const_iterator it_ = object.find(key_value);
+ if(it_ != object.end())
+ add(section, segment_type(interval_type(key_value),it_->second));
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, void>::type
+add_intersection(Type& section, const Type& object,
+ const typename Type::interval_type& inter_val)
+{
+ typedef typename Type::interval_type interval_type;
+ typedef typename Type::value_type value_type;
+ typedef typename Type::const_iterator const_iterator;
+ typedef typename Type::iterator iterator;
+
+ if(itl::is_empty(inter_val))
+ return;
+
+ std::pair<const_iterator, const_iterator> exterior
+ = object.equal_range(inter_val);
+ if(exterior.first == exterior.second)
+ return;
+
+ iterator prior_ = section.end();
+ for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
+ {
+ interval_type common_interval = it_->first & inter_val;
+ if(!itl::is_empty(common_interval))
+ prior_ = add(section, prior_,
+ value_type(common_interval, it_->second) );
+ }
+}
+
+template<class Type, class KeySetT>
+typename enable_if<is_concept_combinable<is_interval_map, is_interval_set, Type, KeySetT>, void>::type
+add_intersection(Type& section, const Type& object, const KeySetT& key_set)
+{
+ typedef typename KeySetT::const_iterator const_iterator;
+
+ if(itl::is_empty(key_set))
+ return;
+
+ const_iterator common_lwb, common_upb;
+ if(!Set::common_range(common_lwb, common_upb, key_set, object))
+ return;
+
+ const_iterator it_ = common_lwb;
+ while(it_ != common_upb)
+ add_intersection(section, object, *it_++);
+}
+
+//------------------------------------------------------------------------------
+//- intersects<IntervalMaps> fragment_types
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<mpl::and_< is_interval_map<Type>
+ , is_total<Type>
+ , is_same<OperandT, segment_type_of<Type> > >,
+ bool>::type
+intersects(const Type&, const OperandT&)
+{
+ return true;
+}
+
+template<class Type, class OperandT>
+typename enable_if<mpl::and_< is_interval_map<Type>
+ , mpl::not_<is_total<Type> >
+ , is_same<OperandT, segment_type_of<Type> > >,
+ bool>::type
+intersects(const Type& object, const OperandT& operand)
+{
+ Type intersection; //JODO
+ itl::add_intersection(intersection, left, operand);
+ return !itl::is_empty(intersection);
+}
+
+template<class Type, class OperandT>
+typename enable_if<mpl::and_< is_interval_map<Type>
+ , is_same<OperandT, element_type_of<Type> > >,
+ bool>::type
+intersects(const Type& object, const OperandT& operand)
+{
+ return itl::intersects(object, make_segment<Type>(operand));
+}
+
+//------------------------------------------------------------------------------
+//- Symmetric difference flip<Interval_Map> fragment_types
+//------------------------------------------------------------------------------
+//JODO NOTE: typename enable_if< mpl::and_< is_interval_map_right_intra_combinable<Type, OperandT> //JODO =^= fragment_type_of
+//------------------------------------------------------------------------------
+//- T& flip(T&, c P&) T:{M} P:{b p} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+flip(Type& object, const typename Type::element_type& operand)
+{
+ return object.flip(operand);
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+flip(Type& object, const typename Type::segment_type& operand)
+{
+ return object.flip(operand);
+}
+
+//------------------------------------------------------------------------------
+//- T& flip(T&, c P&) T:{M} P:{M'} total absorber
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if< mpl::and_< is_total<Type>
+ , absorbs_neutrons<Type>
+ , is_concept_compatible<is_interval_map,
+ Type, OperandT >
+ >
+ , Type>::type&
+flip(Type& object, const OperandT&)
+{
+ object.clear();
+ return object;
+}
+
+//------------------------------------------------------------------------------
+//- T& flip(T&, c P&) T:{M} P:{M'} total enricher
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if< mpl::and_< is_total<Type>
+ , mpl::not_<absorbs_neutrons<Type> >
+ , is_concept_compatible<is_interval_map,
+ Type, OperandT >
+ >
+ , Type>::type&
+flip(Type& object, const OperandT& operand)
+{
+ typedef typename Type::codomain_type codomain_type;
+
+ object += operand;
+ ITL_FORALL(typename Type, it_, object) //JODO: neutralisierendes add.
+ it_->second = neutron<codomain_type>::value();
+
+ if(mpl::not_<is_interval_splitter<Type> >::value) //JODO
+ itl::join(object);
+
+ return object;
+}
+
+//------------------------------------------------------------------------------
+//- T& flip(T&, c P&) T:{M} P:{M'} partial
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if< mpl::and_< mpl::not_<is_total<Type> >
+ , is_concept_compatible<is_interval_map,
+ Type, OperandT >
+ >
+ , Type>::type&
+flip(Type& object, const OperandT& operand)
+{
+ typedef typename OperandT::const_iterator const_iterator;
+ typedef typename Type::codomain_type codomain_type;
+
+ const_iterator common_lwb, common_upb;
+
+ if(!Set::common_range(common_lwb, common_upb, operand, object))
+ return object += operand;
+
+ const_iterator it_ = operand.begin();
+
+ // All elements of operand left of the common range are added
+ while(it_ != common_lwb)
+ itl::add(object, *it_++);
+ // All elements of operand in the common range are symmetrically subtracted
+ while(it_ != common_upb)
+ itl::flip(object, *it_++);
+ // All elements of operand right of the common range are added
+ while(it_ != operand.end())
+ itl::add(object, *it_++);
+
+ return object;
+}
+
+//==============================================================================
+//= Domain
+//==============================================================================
+template<class Type, class SetT>
+typename enable_if<is_concept_combinable<is_interval_set, is_interval_map,
+ SetT, Type>, SetT>::type&
+domain(SetT& result, const Type& object)
+{
+ result.clear();
+ ITL_const_FORALL(typename Type, it_, object)
+ result += it_->first;
+
+ return result;
+}
+
+//==============================================================================
+//= Manipulation by predicates
+//==============================================================================
+template<class MapT, class Predicate> //JODO unify with element_map . . .
+typename enable_if<is_interval_map<MapT>, MapT>::type&
+erase_if(const Predicate& pred, MapT& object)
+{
+ typename MapT::iterator it_ = object.begin();
+ while(it_ != object.end())
+ if(pred(*it_))
+ object.erase(it_++);
+ else ++it_;
+ return object;
+}
+
+template<class MapT, class Predicate>
+inline typename enable_if<is_interval_map<MapT>, MapT>::type&
+add_if(const Predicate& pred, MapT& object, const MapT& src)
+{
+ typename MapT::const_iterator it_ = src.begin();
+ while(it_ != src.end())
+ if(pred(*it_))
+ itl::add(object, *it_++);
+
+ return object;
+}
+
+template<class MapT, class Predicate>
+inline typename enable_if<is_interval_map<MapT>, MapT>::type&
+assign_if(const Predicate& pred, MapT& object, const MapT& src)
+{
+ itl::clear(object);
+ return add_if(object, src, pred);
+}
+
+
+//==============================================================================
+//= Morphisms
+//==============================================================================
+template<class Type>
+typename enable_if<mpl::and_< is_interval_map<Type>
+ , absorbs_neutrons<Type> >, Type>::type&
+absorb_neutrons(Type& object)
+{
+ return object;
+}
+
+template<class Type>
+typename enable_if<mpl::and_< is_interval_map<Type>
+ , mpl::not_<absorbs_neutrons<Type> > >, Type>::type&
+absorb_neutrons(Type& object)
+{
+ typedef typename Type::segment_type segment_type;
+ return itl::erase_if(content_is_neutron<segment_type>(), object);
+}
+
+//==============================================================================
+//= Streaming
+//==============================================================================
+template<class CharType, class CharTraits, class Type>
+typename enable_if<is_interval_map<Type>,
+ std::basic_ostream<CharType, CharTraits> >::type&
+operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
+{
+ stream << "{";
+ ITL_const_FORALL(typename Type, it_, object)
+ stream << "(" << it_->first << "->" << it_->second << ")";
+
+ return stream << "}";
+}
+
+
+}} // namespace boost itl
+
+#endif
+
+
Added: sandbox/itl/boost/itl/concept/interval/set.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/concept/interval/set.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -0,0 +1,308 @@
+/*-----------------------------------------------------------------------------+
+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_CONCEPT_INTERVAL_SET_HPP_JOFA_100920
+#define BOOST_ITL_CONCEPT_INTERVAL_SET_HPP_JOFA_100920
+
+#include <boost/itl/type_traits/is_combinable.hpp>
+
+namespace boost{ namespace itl
+{
+
+//==============================================================================
+//= Containedness<IntervalSet>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- bool contains(c T&, c P&) T:{S} P:{e i S} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_set<Type>, bool>::type
+contains(const Type& super, const typename Type::element_type& element)
+{
+ return !(super.find(element) == super.end());
+}
+
+template<class Type>
+typename enable_if<is_interval_set<Type>, bool>::type
+contains(const Type& super, const typename Type::segment_type& inter_val)
+{
+ typedef typename Type::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 = cyclic_prior(super, exterior.second);
+
+ return
+ itl::contains(hull(*(exterior.first), *last_overlap), inter_val)
+ && Interval_Set::is_joinable(super, exterior.first, last_overlap);
+}
+
+template<class Type, class OperandT>
+typename enable_if<has_same_concept<is_interval_set, Type, OperandT>,
+ bool>::type
+contains(const Type& super, const OperandT& sub)
+{
+ return Interval_Set::contains(super, sub);
+}
+
+//==============================================================================
+//= Addition<IntervalSet>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& add(T&, c P&) T:{S} P:{e i} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_set<Type>, Type>::type&
+add(Type& object, const typename Type::element_type& operand)
+{
+ return object.add(operand);
+}
+
+template<class Type>
+typename enable_if<is_interval_set<Type>, Type>::type&
+add(Type& object, const typename Type::segment_type& operand)
+{
+ return object.add(operand);
+}
+
+//------------------------------------------------------------------------------
+//- T& add(T&, J, c P&) T:{S} P:{i} interval_type
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
+add(Type& object, typename Type::iterator prior,
+ const typename Type::segment_type& operand)
+{
+ return object.add(prior, operand);
+}
+
+//==============================================================================
+//= Insertion<IntervalSet>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& insert(T&, c P&) T:{S} P:{e i} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_set<Type>, Type>::type&
+insert(Type& object, const typename Type::element_type& operand)
+{
+ return itl::add(object, operand);
+}
+
+template<class Type>
+typename enable_if<is_interval_set<Type>, Type>::type&
+insert(Type& object, const typename Type::segment_type& operand)
+{
+ return itl::add(object, operand);
+}
+
+//------------------------------------------------------------------------------
+//- T& insert(T&, J, c P&) T:{S} P:{i} with hint
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_set<Type>, Type>::type&
+insert(Type& object, const typename Type::iterator prior,
+ const typename Type::segment_type& operand)
+{
+ return itl::add(object, prior, operand);
+}
+
+//==============================================================================
+//= Erasure<IntervalSet>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& erase(T&, c P&) T:{S} P:{e i} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_set<Type>, Type>::type&
+erase(Type& object, const typename Type::segment_type& minuend)
+{
+ return itl::subtract(object, minuend);
+}
+
+template<class Type>
+typename enable_if<is_interval_set<Type>, Type>::type&
+erase(Type& object, const typename Type::element_type& minuend)
+{
+ return itl::subtract(object, minuend);
+}
+
+//==============================================================================
+//= Subtraction<IntervalSet>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& subtract(T&, c P&) T:{S} P:{e i} fragment_type
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_set<Type>, Type>::type&
+subtract(Type& object, const typename Type::element_type& operand)
+{
+ return object.subtract(operand);
+}
+
+template<class Type>
+typename enable_if<is_interval_set<Type>, Type>::type&
+subtract(Type& object, const typename Type::segment_type& operand)
+{
+ return object.subtract(operand);
+}
+
+//==============================================================================
+//= Intersection
+//==============================================================================
+//------------------------------------------------------------------------------
+//- void add_intersection(T&, c T&, c P&) T:{S} P:{e i} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_set<Type>, void>::type
+add_intersection(Type& section, const Type& object,
+ const typename Type::element_type& operand)
+{
+ typedef typename Type::const_iterator const_iterator;
+ const_iterator found = object.find(operand);
+ if(found != object.end())
+ itl::add(section, operand);
+}
+
+
+template<class Type>
+typename enable_if<is_interval_set<Type>, void>::type
+add_intersection(Type& section, const Type& object,
+ const typename Type::segment_type& segment)
+{
+ typedef typename Type::const_iterator const_iterator;
+ typedef typename Type::iterator iterator;
+ typedef typename Type::interval_type interval_type;
+
+ if(itl::is_empty(segment))
+ return;
+
+ std::pair<const_iterator, const_iterator> exterior
+ = object.equal_range(segment);
+ if(exterior.first == exterior.second)
+ return;
+
+ iterator prior_ = section.end();
+ for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
+ {
+ interval_type common_interval = Type::key_value(it_) & segment;
+ if(!itl::is_empty(common_interval))
+ prior_ = section.insert(prior_, common_interval);
+ }
+}
+
+//==============================================================================
+//= Symmetric difference<IntervalSet>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& flip(T&, c P&) T:{S} P:{e i S'} fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_set<Type>, Type>::type&
+flip(Type& object, const typename Type::element_type& operand)
+{
+ if(itl::contains(object, operand))
+ return object -= operand;
+ else
+ return object += operand;
+}
+
+template<class Type>
+typename enable_if<is_interval_set<Type>, Type>::type&
+flip(Type& object, const typename Type::segment_type& segment)
+{
+ typedef typename Type::const_iterator const_iterator;
+ typedef typename Type::interval_type interval_type;
+ // That which is common shall be subtracted
+ // That which is not shall be added
+ // So x has to be 'complementary added' or flipped
+ interval_type span = segment;
+ std::pair<const_iterator, const_iterator> exterior
+ = object.equal_range(span);
+
+ const_iterator fst_ = exterior.first;
+ const_iterator end_ = exterior.second;
+
+ interval_type covered, left_over;
+ const_iterator it_ = fst_;
+ while(it_ != end_)
+ {
+ covered = *it_++;
+ //[a ... : span
+ // [b ... : covered
+ //[a b) : left_over
+ left_over = right_subtract(span, covered);
+ itl::subtract(object, span & covered); //That which is common shall be subtracted
+ itl::add(object, left_over); //That which is not shall be added
+
+ //... d) : span
+ //... c) : covered
+ // [c d) : span'
+ span = left_subtract(span, covered);
+ }
+
+ //If span is not empty here, it_ is not in the set so it_ shall be added
+ itl::add(object, span);
+ return object;
+}
+
+
+template<class Type, class OperandT>
+typename enable_if<is_concept_compatible<is_interval_set, Type, OperandT>, Type>::type&
+flip(Type& object, const OperandT& operand)
+{
+ typedef typename OperandT::const_iterator const_iterator;
+
+ if(operand.empty())
+ return object;
+
+ const_iterator common_lwb, common_upb;
+
+ if(!Set::common_range(common_lwb, common_upb, operand, object))
+ return object += operand;
+
+ const_iterator it_ = operand.begin();
+
+ // All elements of operand left of the common range are added
+ while(it_ != common_lwb)
+ itl::add(object, *it_++);
+ // All elements of operand in the common range are symmertrically subtracted
+ while(it_ != common_upb)
+ itl::flip(object, *it_++);
+ // All elements of operand right of the common range are added
+ while(it_ != operand.end())
+ itl::add(object, *it_++);
+
+ return object;
+}
+
+//==============================================================================
+//= Streaming
+//==============================================================================
+template<class CharType, class CharTraits, class Type>
+typename enable_if<is_interval_set<Type>,
+ std::basic_ostream<CharType, CharTraits> >::type&
+operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
+{
+ stream << "{";
+ ITL_const_FORALL(typename Type, it_, object)
+ stream << (*it_);
+
+ return stream << "}";
+}
+
+
+}} // namespace boost itl
+
+#endif
+
+
Added: sandbox/itl/boost/itl/concept/interval/set_or_map.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/concept/interval/set_or_map.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -0,0 +1,836 @@
+/*-----------------------------------------------------------------------------+
+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_CONCEPT_INTERVAL_SET_OR_MAP_HPP_JOFA_100920
+#define BOOST_ITL_CONCEPT_INTERVAL_SET_OR_MAP_HPP_JOFA_100920
+
+#include <boost/itl/type_traits/is_combinable.hpp>
+
+namespace boost{ namespace itl
+{
+
+//==============================================================================
+//= Containedness<IntervalSet|IntervalMap>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- bool within(c T&, c P&) T={Set,Map} P={e i b p S M}
+//------------------------------------------------------------------------------
+template<class SubT, class SuperT>
+typename enable_if<is_interval_container<SuperT>, bool>::type
+within(const SubT& sub, const SuperT& super)
+{
+ return itl::contains(super, sub);
+}
+
+//==============================================================================
+//= Equivalences and Orderings<IntervalSet|IntervalMap>
+//==============================================================================
+template<class Type>
+inline typename enable_if<is_interval_container<Type>, bool>::type
+operator == (const Type& left, const Type& right)
+{
+ return Set::lexicographical_equal(left, right);
+}
+
+template<class Type>
+inline typename enable_if<is_interval_container<Type>, bool>::type
+operator < (const Type& left, const Type& right)
+{
+ typedef typename Type::segment_compare segment_compare;
+ return std::lexicographical_compare(
+ left.begin(), left.end(), right.begin(), right.end(),
+ segment_compare()
+ );
+}
+
+/** Returns true, if \c left and \c right contain the same elements.
+ Complexity: linear. */
+template<class LeftT, class RightT>
+typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
+is_element_equal(const LeftT& left, const RightT& right)
+{
+ return Interval_Set::is_element_equal(left, right);
+}
+
+/** Returns true, if \c left is lexicographically less than \c right.
+ Intervals are interpreted as sequence of elements.
+ Complexity: linear. */
+template<class LeftT, class RightT>
+typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
+is_element_less(const LeftT& left, const RightT& right)
+{
+ return Interval_Set::is_element_less(left, right);
+}
+
+/** Returns true, if \c left is lexicographically greater than \c right.
+ Intervals are interpreted as sequence of elements.
+ Complexity: linear. */
+template<class LeftT, class RightT>
+typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
+is_element_greater(const LeftT& left, const RightT& right)
+{
+ return Interval_Set::is_element_greater(left, right);
+}
+
+//------------------------------------------------------------------------------
+template<class LeftT, class RightT>
+typename 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 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());
+}
+//------------------------------------------------------------------------------
+
+template<class LeftT, class RightT>
+typename enable_if< is_concept_compatible<is_interval_map, LeftT, RightT>,
+ bool >::type
+is_protonic_equal(const LeftT& left, const RightT& right)
+{
+ return Map::lexicographical_protonic_equal(left, right);
+}
+
+//==============================================================================
+//= Size<IntervalSet|IntervalMap>
+//==============================================================================
+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<IntervalSet|IntervalMap>
+//==============================================================================
+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()));
+}
+
+//==============================================================================
+//= Addition<IntervalSet|IntervalMap>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& op +=(T&, c P&) T:{S}|{M} P:{e i}|{b p}
+//------------------------------------------------------------------------------
+/* \par \b Requires: \c OperandT is an addable derivative type of \c Type.
+ \b Effects: \c operand is added to \c object.
+ \par \b Returns: A reference to \c object.
+ \b Complexity:
+\code
+ \ OperandT:
+ \ element segment
+Type:
+ interval container O(log n) O(n)
+
+ interval_set amortized
+ spearate_interval_set O(log n)
+
+n = object.interval_count()
+\endcode
+
+For the addition of \b elements or \b segments
+complexity is \b logarithmic or \b linear respectively.
+For \c interval_sets and \c separate_interval_sets addition of segments
+is \b amortized \b logarithmic.
+*/
+template<class Type, class OperandT>
+typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
+operator += (Type& object, const OperandT& operand)
+{
+ return itl::add(object, operand);
+}
+
+
+//------------------------------------------------------------------------------
+//- T& op +=(T&, c P&) T:{S}|{M} P:{S'}|{M'}
+//------------------------------------------------------------------------------
+/** \par \b Requires: \c OperandT is an interval container addable to \c Type.
+ \b Effects: \c operand is added to \c object.
+ \par \b Returns: A reference to \c object.
+ \b Complexity: loglinear */
+template<class Type, class OperandT>
+typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
+operator += (Type& object, const OperandT& operand)
+{
+ typename Type::iterator prior_ = object.end();
+ ITL_const_FORALL(typename OperandT, elem_, operand)
+ prior_ = itl::add(object, prior_, *elem_);
+
+ return object;
+}
+
+
+//------------------------------------------------------------------------------
+//- T op + (T, c P&) T:{S}|{M} P:{e i S}|{b p M}
+//------------------------------------------------------------------------------
+/** \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
+ \c Type \c object compared to inplace \c operator \c += */
+template<class Type, class OperandT>
+typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
+operator + (Type object, const OperandT& operand)
+{
+ return object += operand;
+}
+
+//------------------------------------------------------------------------------
+//- T op + (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'}
+//------------------------------------------------------------------------------
+/** \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
+ \c Type \c object compared to inplace \c operator \c += */
+template<class Type, class OperandT>
+typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
+operator + (const OperandT& operand, Type object)
+{
+ return object += operand;
+}
+
+//------------------------------------------------------------------------------
+//- T op + (T, c P&) T:{S}|{M} P:{S}|{M}
+//------------------------------------------------------------------------------
+/** \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
+ \c Type \c object compared to inplace \c operator \c += */
+template<class Type>
+typename enable_if<is_interval_container<Type>, Type>::type
+operator + (Type object, const Type& operand)
+{
+ return object += operand;
+}
+
+
+//------------------------------------------------------------------------------
+//- Addition |=, |
+//------------------------------------------------------------------------------
+
+//------------------------------------------------------------------------------
+//- T& op |=(c P&) T:{S}|{M} P:{e i}|{b p}
+//------------------------------------------------------------------------------
+/** \par \b Requires: Types \c Type and \c OperandT are addable.
+ \par \b Effects: \c operand is added to \c object.
+ \par \b Returns: A reference to \c object.
+ \b Complexity:
+\code
+ \ OperandT: interval
+ \ element segment container
+Type:
+ interval container O(log n) O(n) O(m log(n+m))
+
+ interval_set amortized
+ spearate_interval_set O(log n)
+
+n = object.interval_count()
+m = operand.interval_count()
+\endcode
+
+For the addition of \b elements, \b segments and \b interval \b containers
+complexity is \b logarithmic, \b linear and \b loglinear respectively.
+For \c interval_sets and \c separate_interval_sets addition of segments
+is \b amortized \b logarithmic.
+*/
+template<class Type, class OperandT>
+typename enable_if<is_right_intra_combinable<Type, OperandT>, Type>::type&
+operator |= (Type& object, const OperandT& operand)
+{
+ return object += operand;
+}
+
+//------------------------------------------------------------------------------
+//- T op | (T, c P&) T:{S}|{M} P:{e i S}|{b p M}
+//------------------------------------------------------------------------------
+/** \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
+ \c Type \c object compared to inplace \c operator \c |= */
+template<class Type, class OperandT>
+typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
+operator | (Type object, const OperandT& operand)
+{
+ return object += operand;
+}
+
+//------------------------------------------------------------------------------
+//- T op | (T, c P&) T:{S}|{M} P:{S}|{M}
+//------------------------------------------------------------------------------
+/** \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
+ \c Type \c object compared to inplace \c operator \c |= */
+template<class Type, class OperandT>
+typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
+operator | (const OperandT& operand, Type object)
+{
+ return object += operand;
+}
+
+//------------------------------------------------------------------------------
+//- T op | (T, c P&) T:{S}|{M} P:{S}|{M}
+//------------------------------------------------------------------------------
+/** \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
+ \c Type \c object compared to inplace \c operator \c |= */
+template<class Type>
+typename enable_if<is_interval_container<Type>, Type>::type
+operator | (Type object, const Type& operand)
+{
+ return object += operand;
+}
+
+//==============================================================================
+//= Insertion<IntervalSet|IntervalSet>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& insert(T&, c P&) T:{S}|{M} P:{S'}|{M'}
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
+insert(Type& object, const OperandT& operand)
+{
+ typename Type::iterator prior_ = object.end();
+ ITL_const_FORALL(typename OperandT, elem_, operand)
+ insert(object, *elem_);
+
+ return object;
+}
+
+//==============================================================================
+//= Erasure<IntervalSet|IntervalSet>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& erase(T&, c P&) T:{S}|{M} P:{S'}|{S' M'}
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<combines_right_to_interval_container<Type, OperandT>,
+ Type>::type&
+erase(Type& object, const OperandT& operand)
+{
+ typedef typename OperandT::const_iterator const_iterator;
+
+ if(itl::is_empty(operand))
+ return object;
+
+ const_iterator common_lwb, common_upb;
+ if(!Set::common_range(common_lwb, common_upb, operand, object))
+ return object;
+
+ const_iterator it_ = common_lwb;
+ while(it_ != common_upb)
+ itl::erase(object, *it_++);
+
+ return object;
+}
+
+//==============================================================================
+//= Subtraction<IntervalSet|IntervalSet>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- T& op -= (c P&) T:{M} P:{M'}
+//------------------------------------------------------------------------------
+/** \par \b Requires: Types \c Type and \c OperandT are subtractable.
+ \par \b Effects: \c operand is subtracted from \c object.
+ \par \b Returns: A reference to \c object.
+ \b Complexity:
+\code
+ \ OperandT: interval
+ \ element segment container
+Type:
+ interval container O(log n) O(n) O(m log(n+m))
+
+ amortized
+ interval_sets O(log n)
+
+n = object.interval_count()
+m = operand.interval_count()
+\endcode
+
+For the subtraction of \em elements, \b segments and \b interval \b containers
+complexity is \b logarithmic, \b linear and \b loglinear respectively.
+For interval sets subtraction of segments
+is \b amortized \b logarithmic.
+*/
+template<class Type, class OperandT>
+typename enable_if<is_concept_compatible<is_interval_map, Type, OperandT>,
+ Type>::type&
+operator -=(Type& object, const OperandT& operand)
+{
+ ITL_const_FORALL(typename OperandT, elem_, operand)
+ itl::subtract(object, *elem_);
+
+ return object;
+}
+
+//------------------------------------------------------------------------------
+//- T& op -= (c P&) T:{S}|{M} P:{e i}|{b p}
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
+operator -= (Type& object, const OperandT& operand)
+{
+ return itl::subtract(object, operand);
+}
+
+//------------------------------------------------------------------------------
+//- T& op -= (c P&) T:{M} P:{e i}
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<is_cross_derivative<Type, OperandT>, Type>::type&
+operator -= (Type& object, const OperandT& operand)
+{
+ return itl::erase(object, operand);
+}
+
+//------------------------------------------------------------------------------
+//- T& op -= (c P&) T:{S M} P:{S'}
+//------------------------------------------------------------------------------
+template<class Type, class IntervalSetT>
+typename enable_if<combines_right_to_interval_set<Type, IntervalSetT>,
+ Type>::type&
+operator -= (Type& object, const IntervalSetT& operand)
+{
+ return erase(object, operand);
+}
+
+
+//------------------------------------------------------------------------------
+//- T op - (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'}
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
+operator - (Type object, const OperandT& operand)
+{
+ return object -= operand;
+}
+
+
+//==============================================================================
+//= Intersection<IntervalSet|IntervalSet>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- void add_intersection(T&, c T&, c P&) T:{S M} P:{S'}
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<mpl::and_<is_interval_set<Type>,
+ combines_right_to_interval_set<Type, OperandT> >,
+ void>::type
+add_intersection(Type& section, const Type& object, const OperandT& operand)
+{
+ typedef typename OperandT::const_iterator const_iterator;
+
+ if(operand.empty())
+ return;
+
+ const_iterator common_lwb, common_upb;
+ if(!Set::common_range(common_lwb, common_upb, operand, object))
+ return;
+
+ const_iterator it_ = common_lwb;
+ while(it_ != common_upb)
+ itl::add_intersection(section, object, OperandT::key_value(it_++));
+}
+
+//------------------------------------------------------------------------------
+//- T& op &=(T&, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'}
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type&
+operator &= (Type& object, const OperandT& operand)
+{
+ Type intersection;
+ add_intersection(intersection, object, operand);
+ object.swap(intersection);
+ return object;
+}
+
+//------------------------------------------------------------------------------
+//- T op & (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
+operator & (Type object, const OperandT& operand)
+{
+ return object &= operand;
+}
+
+//------------------------------------------------------------------------------
+//- T op & (c P&, T) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
+operator & (const OperandT& operand, Type object)
+{
+ return object &= operand;
+}
+
+//------------------------------------------------------------------------------
+//- T op & (T, c T&) T:{S M}
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_container<Type>, Type>::type
+operator & (Type object, const Type& operand)
+{
+ return object &= operand;
+}
+
+//------------------------------------------------------------------------------
+//- intersects<IntervalSet|IntervalMap>
+//------------------------------------------------------------------------------
+//------------------------------------------------------------------------------
+//- bool intersects(c T&, c P&) T:{S}|{M} P:{e i}
+//------------------------------------------------------------------------------
+template<class Type, class CoType>
+typename enable_if<mpl::and_< is_interval_container<Type>
+ , is_same<CoType, domain_type_of<Type> > >,
+ bool>::type
+intersects(const Type& left, const CoType& right)
+{
+ return itl::contains(left, right);
+}
+
+template<class Type, class CoType>
+typename enable_if<mpl::and_< is_interval_container<Type>
+ , is_same<CoType, interval_type_of<Type> > >,
+ bool>::type
+intersects(const Type& left, const CoType& right)
+{
+ return left.find(right) != left.end();
+}
+
+template<class LeftT, class RightT>
+typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
+ , mpl::or_<is_total<LeftT>, is_total<RightT> > >
+ , bool>::type
+intersects(const LeftT& left, const RightT& right)
+{
+ return true;
+}
+
+template<class LeftT, class RightT>
+typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
+ , mpl::not_<mpl::or_< is_total<LeftT>
+ , is_total<RightT> > > >
+ , bool>::type
+intersects(const LeftT& left, const RightT& right)
+{
+ typedef typename RightT::const_iterator const_iterator;
+ LeftT intersection;
+
+ const_iterator right_common_lower_, right_common_upper_;
+ if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
+ return false;
+
+ const_iterator it_ = right_common_lower_;
+ while(it_ != right_common_upper_)
+ {
+ itl::add_intersection(intersection, left, *it_++);
+ if(!itl::is_empty(intersection))
+ return true;
+ }
+ return false;
+}
+
+template<class LeftT, class RightT>
+typename enable_if<is_cross_combinable<LeftT, RightT>, bool>::type
+intersects(const LeftT& left, const RightT& right)
+{
+ typedef typename RightT::const_iterator const_iterator;
+ LeftT intersection;
+
+ if(itl::is_empty(left) || itl::is_empty(right))
+ return false;
+
+ const_iterator right_common_lower_, 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_)
+ {
+ itl::add_intersection(intersection, left, RightT::key_value(it_++));
+ if(!itl::is_empty(intersection))
+ return true;
+ }
+
+ return false;
+}
+
+template<class Type, class AssociateT>
+typename enable_if<mpl::and_< is_interval_map<Type>
+ , is_inter_derivative<Type, AssociateT> >,
+ bool>::type
+intersects(const Type& left, const AssociateT& right)
+{
+ return itl::intersects(left, right);
+}
+
+/** \b Returns true, if \c left and \c right have no common elements.
+ Intervals are interpreted as sequence of elements.
+ \b Complexity: loglinear, if \c left and \c right are interval containers. */
+template<class LeftT, class RightT>
+typename enable_if<is_inter_combinable<LeftT, RightT>, bool>::type
+disjoint(const LeftT& left, const RightT& right)
+{
+ return !intersects(left, right);
+}
+
+/** \b Returns true, if \c left and \c right have no common elements.
+ Intervals are interpreted as sequence of elements.
+ \b Complexity: logarithmic, if \c AssociateT is an element type \c Type::element_type.
+ linear, if \c AssociateT is a segment type \c Type::segment_type. */
+template<class Type, class AssociateT>
+typename enable_if<is_inter_derivative<Type, AssociateT>, bool>::type
+disjoint(const Type& left, const AssociateT& right)
+{
+ return !intersects(left,right);
+}
+
+//==============================================================================
+//= Symmetric difference<IntervalSet|IntervalSet>
+//==============================================================================
+//------------------------------------------------------------------------------
+//- Symmetric difference ^=, ^
+//------------------------------------------------------------------------------
+//------------------------------------------------------------------------------
+//- T& op ^=(T&, c P&) T:{S}|{M} P:{S'}|{M'}
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
+operator ^= (Type& object, const OperandT& operand)
+{
+ return itl::flip(object, operand);
+}
+
+//------------------------------------------------------------------------------
+//- T& op ^=(T&, c P&) T:{S}|{M} P:{e i}|{b p}
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
+operator ^= (Type& object, const OperandT& operand)
+{
+ return itl::flip(object, operand);
+}
+
+//------------------------------------------------------------------------------
+//- T op ^ (T, c P&) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
+operator ^ (Type object, const OperandT& operand)
+{
+ return object ^= operand;
+}
+
+//------------------------------------------------------------------------------
+//- T op ^ (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser
+//------------------------------------------------------------------------------
+template<class Type, class OperandT>
+typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
+operator ^ (const OperandT& operand, Type object)
+{
+ return object ^= operand;
+}
+
+//------------------------------------------------------------------------------
+//- T op ^ (T, c T&) T:{S M}
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if<is_interval_container<Type>, Type>::type
+operator ^ (typename Type::overloadable_type object, const Type& operand)
+{
+ return object ^= operand;
+}
+
+//==========================================================================
+//= Element Iteration <IntervalSet|IntervalMap>
+//==========================================================================
+//--------------------------------------------------------------------------
+//- Forward
+//--------------------------------------------------------------------------
+template<class Type>
+typename enable_if
+<mpl::and_< is_interval_container<Type>
+ , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
+typename Type::element_iterator>::type
+elements_begin(Type& object)
+{
+ return typename Type::element_iterator(object.begin());
+}
+
+template<class Type>
+typename enable_if
+<mpl::and_< is_interval_container<Type>
+ , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
+typename Type::element_iterator>::type
+elements_end(Type& object)
+{
+ return typename Type::element_iterator(object.end());
+}
+
+template<class Type>
+typename enable_if
+<mpl::and_< is_interval_container<Type>
+ , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
+typename Type::element_const_iterator>::type
+elements_begin(const Type& object)
+{
+ return typename Type::element_const_iterator(object.begin());
+}
+
+template<class Type>
+typename enable_if
+<mpl::and_< is_interval_container<Type>
+ , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
+typename Type::element_const_iterator>::type
+elements_end(const Type& object)
+{
+ return typename Type::element_const_iterator(object.end());
+}
+
+//--------------------------------------------------------------------------
+//- Reverse
+//--------------------------------------------------------------------------
+template<class Type>
+typename enable_if
+<mpl::and_< is_interval_container<Type>
+ , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
+typename Type::element_reverse_iterator>::type
+elements_rbegin(Type& object)
+{
+ return typename Type::element_reverse_iterator(object.rbegin());
+}
+
+template<class Type>
+typename enable_if
+<mpl::and_< is_interval_container<Type>
+ , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
+typename Type::element_reverse_iterator>::type
+elements_rend(Type& object)
+{
+ return typename Type::element_reverse_iterator(object.rend());
+}
+
+template<class Type>
+typename enable_if
+<mpl::and_< is_interval_container<Type>
+ , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
+typename Type::element_const_reverse_iterator>::type
+elements_rbegin(const Type& object)
+{
+ return typename Type::element_const_reverse_iterator(object.rbegin());
+}
+
+template<class Type>
+typename enable_if
+<mpl::and_< is_interval_container<Type>
+ , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
+typename Type::element_const_reverse_iterator>::type
+elements_rend(const Type& object)
+{
+ return typename Type::element_const_reverse_iterator(object.rend());
+}
+
+//==============================================================================
+//= Morphisms
+//==============================================================================
+template<class Type>
+typename enable_if<is_interval_container<Type>, Type>::type&
+join(Type& object)
+{
+ typedef typename Type::interval_type interval_type;
+ typedef typename Type::iterator iterator;
+
+ iterator it_ = object.begin();
+ if(it_ == object.end())
+ return object;
+
+ iterator next_ = it_; next_++;
+
+ while(next_ != object.end())
+ {
+ if( segmental::is_joinable<Type>(it_, next_) )
+ {
+ iterator fst_mem = it_; // hold the first member
+
+ // Go on while touching members are found
+ it_++; next_++;
+ while( next_ != object.end()
+ && segmental::is_joinable<Type>(it_, next_) )
+ { it_++; next_++; }
+
+ // finally we arrive at the end of a sequence of joinable intervals
+ // and it points to the last member of that sequence
+ const_cast<interval_type&>(Type::key_value(it_))
+ = hull(Type::key_value(it_), Type::key_value(fst_mem));
+ object.erase(fst_mem, it_);
+
+ it_++; next_=it_;
+ if(next_!=object.end())
+ next_++;
+ }
+ else { it_++; next_++; }
+ }
+ return object;
+}
+
+
+
+}} // namespace boost itl
+
+#endif
+
+
Modified: sandbox/itl/boost/itl/detail/interval_map_functors.hpp
==============================================================================
--- sandbox/itl/boost/itl/detail/interval_map_functors.hpp (original)
+++ sandbox/itl/boost/itl/detail/interval_map_functors.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -20,7 +20,7 @@
//=P Containment
//==============================================================================
-
+/*CL
template<class MapT>
struct interval_map_contains
{
@@ -134,6 +134,8 @@
return Interval_Set::within(sub, super);
}
};
+CL delete whole file
+*/
}} // namespace itl boost
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-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -245,6 +245,7 @@
return result == inclusion::superset || result == inclusion::equal;
}
+/*CL
//JODO check if this is still needed
template<class IntervalContainerT>
bool contains(const IntervalContainerT& container,
@@ -264,7 +265,7 @@
itl::contains(hull(*(exterior.first), *last_overlap), sub_interval)
&& Interval_Set::is_joinable(container, exterior.first, last_overlap);
}
-
+*/
template<class IntervalContainerT>
bool is_dense(const IntervalContainerT& container,
Modified: sandbox/itl/boost/itl/detail/map_algo.hpp
==============================================================================
--- sandbox/itl/boost/itl/detail/map_algo.hpp (original)
+++ sandbox/itl/boost/itl/detail/map_algo.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -1,5 +1,5 @@
/*-----------------------------------------------------------------------------+
-Copyright (c) 2007-2009: Joachim Faulhaber
+Copyright (c) 2007-2010: Joachim Faulhaber
+------------------------------------------------------------------------------+
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENCE.txt or copy at
@@ -27,14 +27,14 @@
template <class ObjectT, class CoObjectT>
bool intersects(const ObjectT& left, const CoObjectT& right)
{
- typename CoObjectT::const_iterator right_common_lower_;
- typename CoObjectT::const_iterator right_common_upper_;
+ typedef typename CoObjectT::const_iterator co_iterator;
+ co_iterator right_common_lower_, 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_;
+ co_iterator right_ = right_common_lower_;
while(right_ != right_common_upper_)
- if(left.intersects(CoObjectT::key_value(right_++)))
+ if(itl::intersects(left, CoObjectT::key_value(right_++)))
return true;
return false;
Modified: sandbox/itl/boost/itl/detail/map_functors.hpp
==============================================================================
--- sandbox/itl/boost/itl/detail/map_functors.hpp (original)
+++ sandbox/itl/boost/itl/detail/map_functors.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -14,7 +14,6 @@
#include <boost/itl/type_traits/adds_inversely.hpp>
#include <boost/itl/type_traits/absorbs_neutrons.hpp>
#include <boost/itl/functors.hpp>
-//CL #include <boost/itl/map_functions.hpp>
namespace boost{namespace itl
{
@@ -29,10 +28,10 @@
typename enable_if<is_element_map<MapT>, MapT>::type&
add(MapT&, const typename MapT::value_type&);
-template<class MapT>
-typename enable_if<is_element_map<MapT>,
- std::pair<typename MapT::iterator,bool> >::type
-insert(MapT&, const typename MapT::element_type&);
+//CL template<class MapT>
+//typename enable_if<is_element_map<MapT>,
+// std::pair<typename MapT::iterator,bool> >::type
+//insert(MapT&, const typename MapT::element_type&);
template<class MapT, class Predicate>
typename enable_if<is_element_map<MapT>, MapT>::type&
@@ -194,6 +193,7 @@
static map_type& apply(map_type& object, const element_type& value_pair)
{
+ cout << "1";
return map_add<map_type
,inverse_codomain_combine
,absorbs_neutrons<MapT>::value
@@ -214,6 +214,7 @@
static map_type& apply(map_type& object, const element_type& value_pair)
{
+ cout << "2";
iterator it_ = object.find(value_pair.first);
if(it_ != object.end())
{
Modified: sandbox/itl/boost/itl/detail/set_algo.hpp
==============================================================================
--- sandbox/itl/boost/itl/detail/set_algo.hpp (original)
+++ sandbox/itl/boost/itl/detail/set_algo.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -1,5 +1,5 @@
/*-----------------------------------------------------------------------------+
-Copyright (c) 2007-2009: Joachim Faulhaber
+Copyright (c) 2007-2010: Joachim Faulhaber
+------------------------------------------------------------------------------+
Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
+------------------------------------------------------------------------------+
@@ -24,145 +24,150 @@
namespace boost{namespace itl
{
- namespace Set
+namespace Set
+{
+
+template<class ObjectT, class ConstObjectT, class IteratorT>
+bool common_range(IteratorT& lwb, IteratorT& upb, ObjectT& x1, const ConstObjectT& x2)
+{
+ // lwb and upb are iterator of x1 marking the lower and upper bound of
+ // the common range of x1 and x2.
+ typedef typename ConstObjectT::const_iterator ConstObject_iterator;
+
+ lwb = x1.end();
+ upb = x1.end();
+
+ //JODO gcc.3.4.4 :( if(itl::is_empty(x1) || itl::is_empty(x2))
+ if(x1.empty() || x2.empty())
+ return false;
+
+ IteratorT x1_fst_ = x1.begin();
+ IteratorT x1_lst_ = x1.end(); x1_lst_--;
+
+ ConstObject_iterator x2_fst_ = x2.begin();
+ ConstObject_iterator x2_lst_ = x2.end(); x2_lst_--;
+
+ typename ObjectT::key_compare key_less;
+
+ if(key_less(ObjectT::key_value(x1_lst_), ConstObjectT::key_value(x2_fst_))) // {x1} {x2}
+ return false;
+ if(key_less(ConstObjectT::key_value(x2_lst_), ObjectT::key_value(x1_fst_))) // {x2} {x1}
+ return false;
+
+ // We do have a common range
+ lwb = x1.lower_bound(ConstObjectT::key_value(x2_fst_));
+ upb = x1.upper_bound(ConstObjectT::key_value(x2_lst_));
+
+ return true;
+}
+
+template<class ObjectT>
+ObjectT& add(ObjectT& result, const ObjectT& x2)
+{
+ if(&result == &x2)
+ return result;
+
+ typedef typename ObjectT::const_iterator Object_const_iterator;
+ typename ObjectT::iterator prior_ = result.end();
+ for(Object_const_iterator x2_ = x2.begin(); x2_ != x2.end(); x2_++)
+ prior_ = add(result, prior_, *x2_);
+
+ return result;
+}
+
+
+template<class ObjectT, class CoObjectT>
+ObjectT& subtract(ObjectT& result, const CoObjectT& x2)
+{
+ typename CoObjectT::const_iterator common_lwb_, common_upb_;
+ if(!common_range(common_lwb_, common_upb_, x2, result))
+ return result;
+
+ typename CoObjectT::const_iterator x2_ = common_lwb_;
+ typename ObjectT::iterator common_;
+
+ while(x2_ != common_upb_)
+ result.subtract(*x2_++);
+
+ return result;
+}
+
+template<class ObjectT, class CoObjectT>
+ObjectT& erase(ObjectT& result, const CoObjectT& x2)
+{
+ typename CoObjectT::const_iterator common_lwb_;
+ typename CoObjectT::const_iterator common_upb_;
+ if(!common_range(common_lwb_, common_upb_, x2, result))
+ return result;
+
+ typename CoObjectT::const_iterator x2_ = common_lwb_;
+ typename ObjectT::iterator common_;
+
+ while(x2_ != common_upb_)
+ result.erase(*x2_++);
+
+ return result;
+}
+
+
+/** Function template <tt>contained_in</tt> implements the subset relation.
+<tt>contained_in(sub, super)</tt> is true if <tt>sub</tt> is contained in <tt>super</tt> */
+template<class SetType>
+bool within(const SetType& sub, const SetType& super)
+{
+ if(&super == &sub) return true;
+ if(itl::is_empty(sub)) return true;
+ if(itl::is_empty(super)) return false;
+
+ typename SetType::const_iterator common_lwb_, common_upb_;
+ if(!common_range(common_lwb_, common_upb_, sub, super))
+ return false;
+
+ typename SetType::const_iterator sub_ = common_lwb_, super_;
+ while(sub_ != common_upb_)
{
+ super_ = super.find(*sub_++);
+ if(super_ == super.end())
+ return false;
+ }
+ return true;
+}
- template<class ObjectT, class ConstObjectT, class IteratorT>
- bool common_range(IteratorT& lwb, IteratorT& upb, ObjectT& x1, const ConstObjectT& x2)
- {
- // lwb and upb are iterator of x1 marking the lower and upper bound of
- // the common range of x1 and x2.
- typedef typename ConstObjectT::const_iterator ConstObject_iterator;
-
- lwb = x1.end();
- upb = x1.end();
-
- //JODO gcc.3.4.4 :( if(itl::is_empty(x1) || itl::is_empty(x2))
- if(x1.empty() || x2.empty())
- return false;
-
- IteratorT x1_fst_ = x1.begin();
- IteratorT x1_lst_ = x1.end(); x1_lst_--;
-
- ConstObject_iterator x2_fst_ = x2.begin();
- ConstObject_iterator x2_lst_ = x2.end(); x2_lst_--;
-
- typename ObjectT::key_compare key_less;
-
- if(key_less(ObjectT::key_value(x1_lst_), ConstObjectT::key_value(x2_fst_))) // {x1} {x2}
- return false;
- if(key_less(ConstObjectT::key_value(x2_lst_), ObjectT::key_value(x1_fst_))) // {x2} {x1}
- return false;
-
- // We do have a common range
- lwb = x1.lower_bound(ConstObjectT::key_value(x2_fst_));
- upb = x1.upper_bound(ConstObjectT::key_value(x2_lst_));
-
- return true;
- }
-
- template<class ObjectT>
- ObjectT& add(ObjectT& result, const ObjectT& x2)
- {
- if(&result == &x2)
- return result;
-
- typedef typename ObjectT::const_iterator Object_const_iterator;
- typename ObjectT::iterator prior_ = result.end();
- for(Object_const_iterator x2_ = x2.begin(); x2_ != x2.end(); x2_++)
- prior_ = add(result, prior_, *x2_);
-
- return result;
- }
-
-
- template<class ObjectT, class CoObjectT>
- ObjectT& subtract(ObjectT& result, const CoObjectT& x2)
- {
- typename CoObjectT::const_iterator common_lwb_;
- typename CoObjectT::const_iterator common_upb_;
- if(!common_range(common_lwb_, common_upb_, x2, result))
- return result;
-
- typename CoObjectT::const_iterator x2_ = common_lwb_;
- typename ObjectT::iterator common_;
-
- while(x2_ != common_upb_)
- result.subtract(*x2_++);
-
- return result;
- }
-
- template<class ObjectT, class CoObjectT>
- ObjectT& erase(ObjectT& result, const CoObjectT& x2)
- {
- typename CoObjectT::const_iterator common_lwb_;
- typename CoObjectT::const_iterator common_upb_;
- if(!common_range(common_lwb_, common_upb_, x2, result))
- return result;
-
- typename CoObjectT::const_iterator x2_ = common_lwb_;
- typename ObjectT::iterator common_;
-
- while(x2_ != common_upb_)
- result.erase(*x2_++);
-
- return result;
- }
-
-
- /** Function template <tt>contained_in</tt> implements the subset relation.
- <tt>contained_in(sub, super)</tt> is true if <tt>sub</tt> is contained in <tt>super</tt> */
- template<class SetType>
- bool within(const SetType& sub, const SetType& super)
- {
- if(&super == &sub) return true;
- if(itl::is_empty(sub)) return true;
- if(itl::is_empty(super)) 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(!common_range(common_lwb_, common_upb_, sub, super))
- return false;
-
- typename SetType::const_iterator sub_ = common_lwb_, super_;
- while(sub_ != common_upb_)
- {
- super_ = super.find(*sub_++);
- if(super_ == super.end())
- return false;
- }
- return true;
- }
-
- template<class SetType>
- bool intersects(const SetType& left, const SetType& right)
- {
- typename SetType::const_iterator common_lwb_right_;
- typename SetType::const_iterator common_upb_right_;
-
- if(!common_range(common_lwb_right_, common_upb_right_, right, left))
- return false;
-
- typename SetType::const_iterator right_ = common_lwb_right_, found_;
-
- while(right_ != common_upb_right_)
- {
- found_ = left.find(*right_++);
- if(found_ != left.end())
- return true; // found a common element
- }
- // found no common element
- return false;
- }
-
- template<class SetType>
- inline bool is_disjoint(const SetType& left, const SetType& right)
- {
- return !intersects(left, right);
- }
+template<class SetType>
+bool intersects(const SetType& left, const SetType& right)
+{
+ typename SetType::const_iterator common_lwb_right_, common_upb_right_;
+ if(!common_range(common_lwb_right_, common_upb_right_, right, left))
+ return false;
+
+ typename SetType::const_iterator right_ = common_lwb_right_, found_;
+ while(right_ != common_upb_right_)
+ {
+ found_ = left.find(*right_++);
+ if(found_ != left.end())
+ return true; // found a common element
+ }
+ // found no common element
+ return false;
+}
+
+template<class SetType>
+inline bool is_disjoint(const SetType& left, const SetType& right)
+{
+ return !intersects(left, right);
+}
+
+template<class SetType>
+void flip(SetType& result, const SetType& x2)
+{
+ typename SetType::const_iterator x2_ = x2.begin(), x1_;
+ while(x2_ != x2.end())
+ {
+ std::pair<typename SetType::iterator,bool> insertion = result.insert(*x2_++);
+ if(!insertion.second)
+ result.erase(insertion.first);
+ }
+}
#ifdef BOOST_MSVC
@@ -170,35 +175,23 @@
#pragma warning(disable:4996) //'std::equal': Function call with parameters that may be unsafe - this call relies on the caller to check that the passed values are correct. To disable this warning, use -D_SCL_SECURE_NO_WARNINGS. See documentation on how to use Visual C++ 'Checked Iterators'
#endif // I do guarantee here that I am using the parameters correctly :)
- /** Function template <tt>lexicographical_equal</tt> implements
- lexicographical equality. */
- template<class SetType>
- bool lexicographical_equal(const SetType& left, const SetType& right)
- {
- if(&left == &right)
- return true;
- else return left.iterative_size() == right.iterative_size()
- && std::equal(left.begin(), left.end(), right.begin());
- }
+/** Function template <tt>lexicographical_equal</tt> implements
+ lexicographical equality. */
+template<class SetType>
+bool lexicographical_equal(const SetType& left, const SetType& right)
+{
+ if(&left == &right)
+ return true;
+ else return left.iterative_size() == right.iterative_size()
+ && std::equal(left.begin(), left.end(), right.begin());
+}
#ifdef BOOST_MSVC
#pragma warning(pop)
#endif
- template<class SetType>
- void flip(SetType& result, const SetType& x2)
- {
- typename SetType::const_iterator x2_ = x2.begin(), x1_;
- while(x2_ != x2.end())
- {
- std::pair<typename SetType::iterator,bool> insertion = result.insert(*x2_++);
- if(!insertion.second)
- result.erase(insertion.first);
- }
- }
-
- } // namespace 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 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -22,1392 +22,52 @@
#include <boost/itl/type_traits/is_element_container.hpp>
#include <boost/itl/type_traits/is_combinable.hpp>
#include <boost/itl/type_traits/is_fragment_type_of.hpp>
-#include <boost/itl/detail/interval_map_functors.hpp>
#include <boost/itl/detail/interval_map_algo.hpp>
-#include <boost/itl/functions/container.hpp>
+#include <boost/itl/concept/abstract/container.hpp>
+
+#include <boost/itl/concept/interval/base.hpp>
+#include <boost/itl/concept/interval/set.hpp>
+#include <boost/itl/concept/interval/map.hpp>
+#include <boost/itl/concept/interval/set_or_map.hpp>
+
namespace boost{namespace itl
{
-//JODO Forward 4 gcc-3.4.4 -----------------------------------------------------
-template<class Type>
-inline typename enable_if<is_interval_map<Type>, typename Type::segment_type>::type
-make_segment(const typename Type::element_type&);
-//JODO Forward 4 gcc-3.4.4 -----------------------------------------------------
-
//==============================================================================
//= Containedness
//==============================================================================
-//------------------------------------------------------------------------------
-//- contains
-//------------------------------------------------------------------------------
-
-template<class Type, class OperandT>
-typename enable_if<has_same_concept<is_interval_map, Type, OperandT>, //JODO parameter compatibility
- bool>::type
-contains(const Type& super, const OperandT& sub)
-{
- return interval_map_contains<Type>::apply(super, sub);
- //CL?? return Interval_Set::contains(super, sub);
-}
-
-template<class Type, class OperandT>
-typename enable_if<has_same_concept<is_interval_set, Type, OperandT>,
- bool>::type
-contains(const Type& super, const OperandT& sub)
-{
- return Interval_Set::contains(super, sub);
-}
-
-template<class Type, class OperandT>
-typename enable_if<mpl::and_<is_interval_map<Type>,
- is_intra_derivative<Type, OperandT> >,
- bool>::type
-contains(const Type& super, const OperandT& sub)
-{
- return interval_map_contains<Type>::apply(super, sub);
- //CL?? return Interval_Map::contains(super, sub);
-}
-
-template<class Type>
-typename enable_if<is_interval_set<Type>, bool>::type
-contains(const Type& super, const typename Type::segment_type& inter_val)
-{
- typedef typename Type::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 = cyclic_prior(super, exterior.second);
-
- return
- itl::contains(hull(*(exterior.first), *last_overlap), inter_val)
- && Interval_Set::is_joinable(super, exterior.first, last_overlap);
-}
-
-template<class Type>
-typename enable_if<is_interval_set<Type>, bool>::type
-contains(const Type& super, const typename Type::element_type& element)
-{
- return !(super.find(element) == super.end());
-}
-
-template<class Type, class OperandT>
-typename enable_if<is_cross_derivative<Type, OperandT>,
- bool>::type
-contains(const Type& super, const OperandT& sub)
-{
- return interval_map_contains_key<Type, is_total<Type>::value>::apply(super, sub);
- //CL?? return Interval_Map::contains(super, sub);
-}
-
-template<class Type, class IntervalSetT>
-typename enable_if<mpl::and_<is_interval_map<Type>,
- combines_right_to_interval_set<Type, IntervalSetT> >,
- bool>::type
-contains(const Type& super, const IntervalSetT& sub)
-{
- return interval_map_contains_key<Type, is_total<Type>::value>::apply(super, sub);
- //CL?? return Interval_Map::contains(super, sub);
-}
-
-
-//------------------------------------------------------------------------------
-//- within
-//------------------------------------------------------------------------------
-template<class SubT, class SuperT>
-typename enable_if<is_interval_container<SuperT>, bool>::type
-within(const SubT& sub, const SuperT& super)
-{
- return itl::contains(super, sub);
-}
-
-
//==============================================================================
//= Equivalences and Orderings
//==============================================================================
-/** Returns true, if \c left and \c right contain the same elements.
- Complexity: linear. */
-template<class LeftT, class RightT>
-typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
-is_element_equal(const LeftT& left, const RightT& right)
-{
- return Interval_Set::is_element_equal(left, right);
-}
-
-/** Returns true, if \c left is lexicographically less than \c right.
- Intervals are interpreted as sequence of elements.
- Complexity: linear. */
-template<class LeftT, class RightT>
-typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
-is_element_less(const LeftT& left, const RightT& right)
-{
- return Interval_Set::is_element_less(left, right);
-}
-
-/** Returns true, if \c left is lexicographically greater than \c right.
- Intervals are interpreted as sequence of elements.
- Complexity: linear. */
-template<class LeftT, class RightT>
-typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
-is_element_greater(const LeftT& left, const RightT& right)
-{
- return Interval_Set::is_element_greater(left, right);
-}
-
-//------------------------------------------------------------------------------
-template<class LeftT, class RightT>
-typename 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 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());
-}
-//------------------------------------------------------------------------------
-
-template<class LeftT, class RightT>
-typename enable_if< is_concept_compatible<is_interval_map, LeftT, RightT>,
- bool >::type
-is_protonic_equal(const LeftT& left, const RightT& right)
-{
- return Map::lexicographical_protonic_equal(left, right);
-}
-
-
-
-
//==============================================================================
//= Addition
//==============================================================================
-//- add(interval_sets, [prior], {element, segment}) ----------------------------
-template<class Type>
-typename enable_if<is_interval_set<Type>, Type>::type&
-add(Type& object, const typename Type::element_type& operand)
-{
- Interval_Set::add(object, typename Type::interval_type(operand));
- return object;
-}
-
-template<class Type>
-typename enable_if<is_interval_set<Type>, Type>::type&
-add(Type& object, const typename Type::segment_type& operand)
-{
- Interval_Set::add(object, operand);
- return object;
-}
-
-template<class Type>
-typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
-add(Type& object, typename Type::iterator prior,
- const typename Type::segment_type& operand)
-{
- return Interval_Set::add(object, prior, operand);
-}
-
-//------------------------------------------------------------------------------
-//- add(interval_maps, [prior], {element, segment}) ----------------------------
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-add(Type& object, const typename Type::element_type& operand)
-{
- return object.add(operand);
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-add(Type& object, const typename Type::segment_type& operand)
-{
- return object.add(operand);
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, typename Type::iterator >::type
-add(Type& object, typename Type::iterator prior_,
- const typename Type::segment_type& operand)
-{
- //CL typedef typename Type::codomain_combine codomain_combine;
- //CL return Interval_Map::add<Type,codomain_combine>(object, prior_, operand);
- return object.add(prior_, operand);
-}
-//------------------------------------------------------------------------------
-
-/** \par \b Requires: \c OperandT is an interval container addable to \c Type.
- \b Effects: \c operand is added to \c object.
- \par \b Returns: A reference to \c object.
- \b Complexity: loglinear */
-template<class Type, class OperandT>
-typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
-operator += (Type& object, const OperandT& operand)
-{
- typename Type::iterator prior_ = object.end();
- ITL_const_FORALL(typename OperandT, elem_, operand)
- prior_ = itl::add(object, prior_, *elem_);
-
- return object;
-}
-
-/* \par \b Requires: \c OperandT is an addable derivative type of \c Type.
- \b Effects: \c operand is added to \c object.
- \par \b Returns: A reference to \c object.
- \b Complexity:
-\code
- \ OperandT:
- \ element segment
-Type:
- interval container O(log n) O(n)
-
- interval_set amortized
- spearate_interval_set O(log n)
-
-n = object.interval_count()
-\endcode
-
-For the addition of \b elements or \b segments
-complexity is \b logarithmic or \b linear respectively.
-For \c interval_sets and \c separate_interval_sets addition of segments
-is \b amortized \b logarithmic.
-*/
-template<class Type, class OperandT>
-typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
-operator += (Type& object, const OperandT& operand)
-{
- //JODO return itl::add(object, operand);
- return itl::add(object, 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
- \c Type \c object compared to inplace \c operator \c += */
-template<class Type, class OperandT>
-typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
-operator + (Type object, const OperandT& operand)
-{
- return object += 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
- \c Type \c object compared to inplace \c operator \c += */
-template<class Type, class OperandT>
-typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
-operator + (const OperandT& operand, Type object)
-{
- return object += 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
- \c Type \c object compared to inplace \c operator \c += */
-template<class Type>
-Type operator + (typename Type::overloadable_type object, const Type& operand)
-{
- return object += operand;
-}
-
-
-//------------------------------------------------------------------------------
-//- Addition |=, |
-//------------------------------------------------------------------------------
-
-/** \par \b Requires: Types \c Type and \c OperandT are addable.
- \par \b Effects: \c operand is added to \c object.
- \par \b Returns: A reference to \c object.
- \b Complexity:
-\code
- \ OperandT: interval
- \ element segment container
-Type:
- interval container O(log n) O(n) O(m log(n+m))
-
- interval_set amortized
- spearate_interval_set O(log n)
-
-n = object.interval_count()
-m = operand.interval_count()
-\endcode
-
-For the addition of \b elements, \b segments and \b interval \b containers
-complexity is \b logarithmic, \b linear and \b loglinear respectively.
-For \c interval_sets and \c separate_interval_sets addition of segments
-is \b amortized \b logarithmic.
-*/
-template<class Type, class OperandT>
-typename enable_if<is_right_intra_combinable<Type, OperandT>, Type>::type&
-operator |= (Type& object, const OperandT& operand)
-{
- return object += 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
- \c Type \c object compared to inplace \c operator \c |= */
-template<class Type, class OperandT>
-typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
-operator | (Type object, const OperandT& operand)
-{
- return object += 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
- \c Type \c object compared to inplace \c operator \c |= */
-template<class Type, class OperandT>
-typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
-operator | (const OperandT& operand, Type object)
-{
- return object += 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
- \c Type \c object compared to inplace \c operator \c |= */
-template<class Type>
-Type operator | (typename Type::overloadable_type object, const Type& operand)
-{
- return object += operand;
-}
-
//==============================================================================
//= Insertion
//==============================================================================
-//------------------------------------------------------------------------------
-//- Insertion<Interval_Set> fragment_types
-//------------------------------------------------------------------------------
-template<class Type>
-typename enable_if<is_interval_set<Type>, Type>::type&
-insert(Type& object, const typename Type::element_type& operand)
-{
- return itl::add(object, operand);
-}
-
-template<class Type>
-typename enable_if<is_interval_set<Type>, Type>::type&
-insert(Type& object, const typename Type::segment_type& operand)
-{
- return itl::add(object, operand);
-}
-
-//------------------------------------------------------------------------------
-//- Insertion<Interval_Map> fragment_types
-//------------------------------------------------------------------------------
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-insert(Type& object, const typename Type::element_type& operand)
-{
- return object.insert(operand);
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-insert(Type& object, const typename Type::segment_type& operand)
-{
- return object.insert(operand);
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, typename Type::iterator>::type
-insert(Type& object, typename Type::iterator prior,
- const typename Type::segment_type& operand)
-{
- return object.insert(prior, operand);
-}
-
-//------------------------------------------------------------------------------
-template<class Type, class OperandT>
-typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
-insert(Type& object, const OperandT& operand)
-{
- typename Type::iterator prior_ = object.end();
- ITL_const_FORALL(typename OperandT, elem_, operand)
- insert(object, *elem_);
-
- return object;
-}
-
//==============================================================================
//= Erasure
//==============================================================================
-//------------------------------------------------------------------------------
-//- Erasure<Interval_Set> fragment_types
-//------------------------------------------------------------------------------
-template<class Type>
-typename enable_if<is_interval_set<Type>, Type>::type&
-erase(Type& object, const typename Type::segment_type& minuend)
-{
- return itl::subtract(object, minuend);
-}
-
-template<class Type>
-typename enable_if<is_interval_set<Type>, Type>::type&
-erase(Type& object, const typename Type::element_type& minuend)
-{
- return itl::subtract(object, minuend);
-}
-
-//------------------------------------------------------------------------------
-//- Erasure<Interval_Map> key_types
-//------------------------------------------------------------------------------
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-erase(Type& object, const typename Type::interval_type& minuend)
-{
- return object.erase(minuend);
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-erase(Type& object, const typename Type::domain_type& minuend)
-{
- return object.erase(minuend);
-}
-
-//------------------------------------------------------------------------------
-//- Erasure<Interval_Map> fragment_types
-//------------------------------------------------------------------------------
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-erase(Type& object, const typename Type::segment_type& minuend)
-{
- return object.erase(minuend);
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-erase(Type& object, const typename Type::element_type& minuend)
-{
- return object.erase(minuend);
-}
-
-//------------------------------------------------------------------------------
-template<class Type, class OperandT>
-typename enable_if<combines_right_to_interval_container<Type, OperandT>,
- Type>::type&
-erase(Type& object, const OperandT& operand)
-{
- typedef typename OperandT::const_iterator const_iterator;
-
- if(itl::is_empty(operand))
- return object;
-
- const_iterator common_lwb, common_upb;
- if(!Set::common_range(common_lwb, common_upb, operand, object))
- return object;
-
- const_iterator it_ = common_lwb;
- while(it_ != common_upb)
- itl::erase(object, *it_++);
-
- return object;
-}
-
//==============================================================================
//= Subtraction
//==============================================================================
//------------------------------------------------------------------------------
-//- Subtraction<Interval_Set> fragment_type
-//------------------------------------------------------------------------------
-template<class Type>
-typename enable_if<is_interval_set<Type>, Type>::type&
-subtract(Type& object, const typename Type::element_type& operand)
-{
- Interval_Set::subtract(object, typename Type::segment_type(operand));
- return object;
-}
-
-template<class Type>
-typename enable_if<is_interval_set<Type>, Type>::type&
-subtract(Type& object, const typename Type::segment_type& operand)
-{
- Interval_Set::subtract(object, operand);
- return object;
-}
-
-//------------------------------------------------------------------------------
-//- Subtraction<Interval_Map> fragment_types
-//------------------------------------------------------------------------------
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-subtract(Type& object, const typename Type::segment_type& operand)
-{
- return object.subtract(operand);
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-subtract(Type& object, const typename Type::element_type& operand)
-{
- itl::subtract(object, make_segment<Type>(operand));
- return object;
-}
-
-//------------------------------------------------------------------------------
-//- Subtraction<Interval_Map> key_types
-//------------------------------------------------------------------------------
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-subtract(Type& object, const typename Type::domain_type& operand)
-{
- return object.erase(operand);
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-subtract(Type& object, const typename Type::interval_type& operand)
-{
- return object.erase(operand);
-}
-
-
-//------------------------------------------------------------------------------
-//- Subtraction -=, -
-//------------------------------------------------------------------------------
-
-/** \par \b Requires: Types \c Type and \c OperandT are subtractable.
- \par \b Effects: \c operand is subtracted from \c object.
- \par \b Returns: A reference to \c object.
- \b Complexity:
-\code
- \ OperandT: interval
- \ element segment container
-Type:
- interval container O(log n) O(n) O(m log(n+m))
-
- amortized
- interval_sets O(log n)
-
-n = object.interval_count()
-m = operand.interval_count()
-\endcode
-
-For the subtraction of \em elements, \b segments and \b interval \b containers
-complexity is \b logarithmic, \b linear and \b loglinear respectively.
-For interval sets subtraction of segments
-is \b amortized \b logarithmic.
-*/
-template<class Type, class OperandT>
-typename enable_if<has_same_concept<is_interval_map, Type, OperandT>,
- Type>::type&
-operator -=(Type& object, const OperandT& operand)
-{
- ITL_const_FORALL(typename OperandT, elem_, operand)
- itl::subtract(object, *elem_);
-
- return object;
-}
-
-template<class Type, class OperandT>
-typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
-operator -= (Type& object, const OperandT& operand)
-{
- return itl::subtract(object, operand);
-}
-
-template<class Type, class OperandT>
-typename enable_if<is_cross_derivative<Type, OperandT>, Type>::type&
-operator -= (Type& object, const OperandT& operand)
-{
- return itl::erase(object, operand);
-}
-
-template<class Type, class IntervalSetT>
-typename enable_if<combines_right_to_interval_set<Type, IntervalSetT>,
- Type>::type&
-operator -= (Type& object, const IntervalSetT& operand)
-{
- return erase(object, operand);
-}
-
-
-template<class Type, class OperandT>
-typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
-operator - (Type object, const OperandT& operand)
-{
- return object -= operand;
-}
-
-
-//------------------------------------------------------------------------------
//- set (selective update)
//------------------------------------------------------------------------------
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-set_at(Type& object, const typename Type::segment_type& operand)
-{
- itl::erase(object, operand.first);
- return itl::insert(object, operand);
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-set_at(Type& object, const typename Type::element_type& operand)
-{
- return itl::set_at(object, make_segment<Type>(operand));
-}
-
-
//==============================================================================
//= Intersection
//==============================================================================
-//------------------------------------------------------------------------------
-//- Intersection add_intersection <interval_set>
-//------------------------------------------------------------------------------
-template<class Type>
-typename enable_if<is_interval_set<Type>, void>::type
-add_intersection(Type& section, const Type& object,
- const typename Type::domain_type& operand)
-{
- typedef typename Type::const_iterator const_iterator;
- const_iterator found = object.find(operand);
- if(found != object.end())
- itl::add(section, operand);
-}
-
-
-template<class Type>
-typename enable_if<is_interval_set<Type>, void>::type
-add_intersection(Type& section, const Type& object,
- const typename Type::segment_type& segment)
-{
- typedef typename Type::const_iterator const_iterator;
- typedef typename Type::iterator iterator;
- typedef typename Type::interval_type interval_type;
-
- if(itl::is_empty(segment))
- return;
-
- std::pair<const_iterator, const_iterator> exterior
- = object.equal_range(segment);
- if(exterior.first == exterior.second)
- return;
-
- iterator prior_ = section.end();
- for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
- {
- interval_type common_interval = Type::key_value(it_) & segment;
- if(!itl::is_empty(common_interval))
- prior_ = section.insert(prior_, common_interval);
- }
-}
-
-
-template<class Type, class OperandT>
-typename enable_if<mpl::and_<is_interval_set<Type>,
- combines_right_to_interval_set<Type, OperandT> >,
- void>::type
-add_intersection(Type& section, const Type& object, const OperandT& operand)
-{
- typedef typename OperandT::const_iterator const_iterator;
-
- if(operand.empty())
- return;
-
- const_iterator common_lwb, common_upb;
- if(!Set::common_range(common_lwb, common_upb, operand, object))
- return;
-
- const_iterator it_ = common_lwb;
- while(it_ != common_upb)
- itl::add_intersection(section, object, OperandT::key_value(it_++));
-}
-
-
-//------------------------------------------------------------------------------
-//- Intersection add_intersection<IntervalMaps> for fragment_types
-//------------------------------------------------------------------------------
-template<class Type>
-typename enable_if<is_interval_map<Type>, void>::type
-add_intersection(Type& section, const Type& object,
- const typename Type::element_type& operand)
-{
- object.add_intersection(section, operand);
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, void>::type
-add_intersection(Type& section, const Type& object,
- const typename Type::segment_type& operand)
-{
- object.add_intersection(section, operand);
-}
-
-template<class Type, class MapT>
-typename enable_if
-<
- mpl::and_< is_total<Type>
- , is_concept_compatible<is_interval_map, Type, MapT> >
- , void
->::type
-add_intersection(Type& section, const Type& object, const MapT& operand)
-{
- section += object;
- section += operand;
-}
-
-template<class Type, class MapT>
-typename enable_if
-<
- mpl::and_< mpl::not_<is_total<Type> >
- , is_concept_compatible<is_interval_map, Type, MapT> >
- , void
->::type
-add_intersection(Type& section, const Type& object, const MapT& operand)
-{
- typedef typename Type::segment_type segment_type;
- typedef typename Type::interval_type interval_type;
- typedef typename MapT::const_iterator const_iterator;
-
- if(operand.empty())
- return;
- const_iterator common_lwb, common_upb;
- if(!Set::common_range(common_lwb, common_upb, operand, object))
- return;
- const_iterator it_ = common_lwb;
- while(it_ != common_upb)
- add_intersection(section, object, *it_++);
-}
-
-//------------------------------------------------------------------------------
-//- Intersection add_intersection<IntervalMaps> for key_types
-//------------------------------------------------------------------------------
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, void>::type
-add_intersection(Type& section, const Type& object,
- const typename Type::domain_type& key_value)
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::segment_type segment_type;
- typedef typename Type::const_iterator const_iterator;
-
- const_iterator it_ = object.find(key_value);
- if(it_ != object.end())
- add(section, segment_type(interval_type(key_value),it_->second));
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, void>::type
-add_intersection(Type& section, const Type& object,
- const typename Type::interval_type& inter_val)
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::value_type value_type;
- typedef typename Type::const_iterator const_iterator;
- typedef typename Type::iterator iterator;
-
- if(itl::is_empty(inter_val))
- return;
-
- std::pair<const_iterator, const_iterator> exterior
- = object.equal_range(inter_val);
- if(exterior.first == exterior.second)
- return;
-
- iterator prior_ = section.end();
- for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
- {
- interval_type common_interval = it_->first & inter_val;
- if(!itl::is_empty(common_interval))
- prior_ = add(section, prior_,
- value_type(common_interval, it_->second) );
- }
-}
-
-template<class Type, class KeySetT>
-typename enable_if<is_concept_combinable<is_interval_map, is_interval_set, Type, KeySetT>, void>::type
-add_intersection(Type& section, const Type& object, const KeySetT& key_set)
-{
- typedef typename KeySetT::const_iterator const_iterator;
-
- if(itl::is_empty(key_set))
- return;
-
- const_iterator common_lwb, common_upb;
- if(!Set::common_range(common_lwb, common_upb, key_set, object))
- return;
-
- const_iterator it_ = common_lwb;
- while(it_ != common_upb)
- add_intersection(section, object, *it_++);
-}
-
-
-
-//------------------------------------------------------------------------------
-//- Intersection &=, &
-//------------------------------------------------------------------------------
-template<class Type, class OperandT>
-typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type&
-operator &= (Type& object, const OperandT& operand)
-{
- Type intersection;
- add_intersection(intersection, object, operand);
- object.swap(intersection);
- return object;
-}
-
-template<class Type, class OperandT>
-typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
-operator & (Type object, const OperandT& operand)
-{
- return object &= operand;
-}
-
-template<class Type, class OperandT>
-typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
-operator & (const OperandT& operand, Type object)
-{
- return object &= operand;
-}
-
-template<class Type>
-Type operator & (typename Type::overloadable_type object, const Type& operand)
-{
- return object &= operand;
-}
-
-//------------------------------------------------------------------------------
-//- intersects
-//------------------------------------------------------------------------------
-//------------------------------------------------------------------------------
-//- intersects<Interval_Container> key_types
-//------------------------------------------------------------------------------
-template<class Type, class AssociateT>
-typename enable_if<mpl::and_< is_interval_container<Type>
- , is_same<AssociateT, domain_type_of<Type> > >,
- bool>::type
-intersects(const Type& left, const AssociateT& right)
-{
- return itl::contains(left, right);
-}
-
-template<class Type, class AssociateT>
-typename enable_if<mpl::and_< is_interval_container<Type>
- , is_same<AssociateT, interval_type_of<Type> > >,
- bool>::type
-intersects(const Type& left, const AssociateT& right)
-{
- return left.find(right) != left.end();
-}
-
-//------------------------------------------------------------------------------
-//- intersects<Interval_Maps> fragment_types
-//------------------------------------------------------------------------------
-
-template<class Type, class OperandT>
-typename enable_if<mpl::and_< is_interval_map<Type>
- , is_total<Type>
- , is_same<OperandT, segment_type_of<Type> > >,
- bool>::type
-intersects(const Type&, const OperandT&)
-{
- return true;
-}
-
-template<class Type, class OperandT>
-typename enable_if<mpl::and_< is_interval_map<Type>
- , mpl::not_<is_total<Type> >
- , is_same<OperandT, segment_type_of<Type> > >,
- bool>::type
-intersects(const Type& object, const OperandT& operand)
-{
- Type intersection; //JODO
- itl::add_intersection(intersection, left, operand);
- return !itl::is_empty(intersection);
-}
-
-template<class Type, class OperandT>
-typename enable_if<mpl::and_< is_interval_map<Type>
- , is_same<OperandT, element_type_of<Type> > >,
- bool>::type
-intersects(const Type& object, const OperandT& operand)
-{
- return itl::intersects(object, make_segment<Type>(operand));
-}
-
-//------------------------------------------------------------------------------
-
-template<class LeftT, class RightT>
-typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
- , mpl::or_<is_total<LeftT>, is_total<RightT> > >
- , bool>::type
-intersects(const LeftT& left, const RightT& right)
-{
- return true;
-}
-
-template<class LeftT, class RightT>
-typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
- , mpl::not_<mpl::or_< is_total<LeftT>
- , is_total<RightT> > > >
- , bool>::type
-intersects(const LeftT& left, const RightT& right)
-{
- typedef typename RightT::const_iterator const_iterator;
- LeftT intersection;
-
- const_iterator right_common_lower_, right_common_upper_;
- if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
- return false;
-
- const_iterator it_ = right_common_lower_;
- while(it_ != right_common_upper_)
- {
- itl::add_intersection(intersection, left, *it_++);
- if(!itl::is_empty(intersection))
- return true;
- }
- return false;
-}
-
-
-template<class LeftT, class RightT>
-typename enable_if<is_cross_combinable<LeftT, RightT>, bool>::type
-intersects(const LeftT& left, const RightT& right)
-{
- typedef typename RightT::const_iterator const_iterator;
- LeftT intersection;
-
- if(itl::is_empty(left) || itl::is_empty(right))
- return false;
-
- const_iterator right_common_lower_, 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_)
- {
- itl::add_intersection(intersection, left, RightT::key_value(it_++));
- if(!itl::is_empty(intersection))
- return true;
- }
-
- return false;
-}
-
-template<class Type, class AssociateT>
-typename enable_if<mpl::and_< is_interval_map<Type>
- , is_inter_derivative<Type, AssociateT> >,
- bool>::type
-intersects(const Type& left, const AssociateT& right)
-{
- return itl::intersects(left, right);
-}
-
-/** \b Returns true, if \c left and \c right have no common elements.
- Intervals are interpreted as sequence of elements.
- \b Complexity: loglinear, if \c left and \c right are interval containers. */
-template<class LeftT, class RightT>
-typename enable_if<is_inter_combinable<LeftT, RightT>, bool>::type
-disjoint(const LeftT& left, const RightT& right)
-{
- return !intersects(left, right);
-}
-
-/** \b Returns true, if \c left and \c right have no common elements.
- Intervals are interpreted as sequence of elements.
- \b Complexity: logarithmic, if \c AssociateT is an element type \c Type::element_type.
- linear, if \c AssociateT is a segment type \c Type::segment_type. */
-template<class Type, class AssociateT>
-typename enable_if<is_inter_derivative<Type, AssociateT>, bool>::type
-disjoint(const Type& left, const AssociateT& right)
-{
- return !left.intersects(right);
-}
-
-
//==============================================================================
//= Symmetric difference
//==============================================================================
-//------------------------------------------------------------------------------
-//- Symmetric difference flip<Interval_Set> fragment_types
-//------------------------------------------------------------------------------
-template<class Type>
-typename enable_if<is_interval_set<Type>, Type>::type&
-flip(Type& object, const typename Type::element_type& operand)
-{
- if(itl::contains(object, operand))
- return object -= operand;
- else
- return object += operand;
-}
-
-template<class Type>
-typename enable_if<is_interval_set<Type>, Type>::type&
-flip(Type& object, const typename Type::segment_type& segment)
-{
- typedef typename Type::const_iterator const_iterator;
- typedef typename Type::interval_type interval_type;
- // That which is common shall be subtracted
- // That which is not shall be added
- // So x has to be 'complementary added' or flipped
- interval_type span = segment;
- std::pair<const_iterator, const_iterator> exterior
- = object.equal_range(span);
-
- const_iterator fst_ = exterior.first;
- const_iterator end_ = exterior.second;
-
- interval_type covered, left_over;
- const_iterator it_ = fst_;
- while(it_ != end_)
- {
- covered = *it_++;
- //[a ... : span
- // [b ... : covered
- //[a b) : left_over
- left_over = right_subtract(span, covered);
- itl::subtract(object, span & covered); //That which is common shall be subtracted
- itl::add(object, left_over); //That which is not shall be added
-
- //... d) : span
- //... c) : covered
- // [c d) : span'
- span = left_subtract(span, covered);
- }
-
- //If span is not empty here, it_ is not in the set so it_ shall be added
- itl::add(object, span);
- return object;
-}
-
-
-template<class Type, class OperandT>
-typename enable_if<is_concept_compatible<is_interval_set, Type, OperandT>, Type>::type&
-flip(Type& object, const OperandT& operand)
-{
- typedef typename OperandT::const_iterator const_iterator;
-
- if(operand.empty())
- return object;
-
- const_iterator common_lwb, common_upb;
-
- if(!Set::common_range(common_lwb, common_upb, operand, object))
- return object += operand;
-
- const_iterator it_ = operand.begin();
-
- // All elements of operand left of the common range are added
- while(it_ != common_lwb)
- itl::add(object, *it_++);
- // All elements of operand in the common range are symmertrically subtracted
- while(it_ != common_upb)
- itl::flip(object, *it_++);
- // All elements of operand right of the common range are added
- while(it_ != operand.end())
- itl::add(object, *it_++);
-
- return object;
-}
-
-//------------------------------------------------------------------------------
-//- Symmetric difference flip<Interval_Map> fragment_types
-//------------------------------------------------------------------------------
-//JODO NOTE: typename enable_if< mpl::and_< is_interval_map_right_intra_combinable<Type, OperandT> //JODO =^= fragment_type_of
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-flip(Type& object, const typename Type::element_type& operand)
-{
- return object.flip(operand);
-}
-
-template<class Type>
-typename enable_if<is_interval_map<Type>, Type>::type&
-flip(Type& object, const typename Type::segment_type& operand)
-{
- return object.flip(operand);
-}
-
-template<class Type, class OperandT>
-typename enable_if< mpl::and_< is_total<Type>
- , absorbs_neutrons<Type>
- , is_concept_compatible<is_interval_map,
- Type, OperandT >
- >
- , Type>::type&
-flip(Type& object, const OperandT& operand)
-{
- object.clear();
- return object;
-}
-
-template<class Type, class OperandT>
-typename enable_if< mpl::and_< is_total<Type>
- , mpl::not_<absorbs_neutrons<Type> >
- , is_concept_compatible<is_interval_map,
- Type, OperandT >
- >
- , Type>::type&
-flip(Type& object, const OperandT& operand)
-{
- typedef typename Type::codomain_type codomain_type;
-
- object += operand;
- ITL_FORALL(typename Type, it_, object) //JODO: neutralisierendes add.
- it_->second = neutron<codomain_type>::value();
-
- if(mpl::not_<is_interval_splitter<Type> >::value) //JODO
- itl::join(object);
-
- return object;
-}
-
-template<class Type, class OperandT>
-typename enable_if< mpl::and_< mpl::not_<is_total<Type> >
- , is_concept_compatible<is_interval_map,
- Type, OperandT >
- >
- , Type>::type&
-flip(Type& object, const OperandT& operand)
-{
- typedef typename OperandT::const_iterator const_iterator;
- typedef typename Type::codomain_type codomain_type;
-
- const_iterator common_lwb, common_upb;
-
- if(!Set::common_range(common_lwb, common_upb, operand, object))
- return object += operand;
-
- const_iterator it_ = operand.begin();
-
- // All elements of operand left of the common range are added
- while(it_ != common_lwb)
- itl::add(object, *it_++);
- // All elements of operand in the common range are symmetrically subtracted
- while(it_ != common_upb)
- itl::flip(object, *it_++);
- // All elements of operand right of the common range are added
- while(it_ != operand.end())
- itl::add(object, *it_++);
-
- return object;
-}
-
-
-
-//------------------------------------------------------------------------------
-//- Symmetric difference ^=, ^
-//------------------------------------------------------------------------------
-template<class Type, class OperandT>
-typename enable_if<is_intra_combinable<Type, OperandT>,
- Type>::type&
-operator ^= (Type& object, const OperandT& operand)
-{
- return itl::flip(object, operand);
-}
-
-template<class Type, class OperandT>
-typename enable_if<is_intra_derivative<Type, OperandT>,
- Type>::type&
-operator ^= (Type& object, const OperandT& operand)
-{
- return itl::flip(object, operand);
-}
-
-template<class Type, class OperandT>
-typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
-operator ^ (Type object, const OperandT& operand)
-{
- return object ^= operand;
-}
-
-template<class Type, class OperandT>
-typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
-operator ^ (const OperandT& operand, Type object)
-{
- return object ^= operand;
-}
-
-template<class Type>
-Type operator ^ (typename Type::overloadable_type object, const Type& operand)
-{
- return object ^= operand;
-}
-
//==============================================================================
//= Domain
//==============================================================================
-template<class Type, class SetT>
-typename enable_if<is_concept_combinable<is_interval_set, is_interval_map, SetT, Type>, SetT>::type&
-domain(SetT& result, const Type& object)
-{
- result.clear();
- ITL_const_FORALL(typename Type, it_, object)
- result += it_->first;
-
- return result;
-}
-
-
-//==============================================================================
-//= Manipulation by predicates
-//==============================================================================
-template<class MapT, class Predicate> //JODO unify with element_map . . .
-typename enable_if<is_interval_map<MapT>, MapT>::type&
-erase_if(const Predicate& pred, MapT& object)
-{
- typename MapT::iterator it_ = object.begin();
- while(it_ != object.end())
- if(pred(*it_))
- object.erase(it_++);
- else ++it_;
- return object;
-}
-
-template<class MapT, class Predicate>
-inline typename enable_if<is_interval_map<MapT>, MapT>::type&
-add_if(const Predicate& pred, MapT& object, const MapT& src)
-{
- typename MapT::const_iterator it_ = src.begin();
- while(it_ != src.end())
- if(pred(*it_))
- itl::add(object, *it_++);
-
- return object;
-}
-
-template<class MapT, class Predicate>
-inline typename enable_if<is_interval_map<MapT>, MapT>::type&
-assign_if(const Predicate& pred, MapT& object, const MapT& src)
-{
- itl::clear(object);
- return add_if(object, src, pred);
-}
-
-//==============================================================================
-//= Morphisms
-//==============================================================================
-
-namespace segmental
-{
- template<class Type>
- typename enable_if<is_interval_set<Type>, bool>::type
- is_joinable(typename Type::iterator it_, typename Type::iterator next_, Type* = 0)
- {
- return touches(*it_, *next_);
- }
-
- template<class Type>
- typename enable_if<is_interval_map<Type>, bool>::type
- is_joinable(typename Type::iterator it_, typename Type::iterator next_, Type* = 0)
- {
- return touches(it_->first, next_->first)
- && it_->second == next_->second ;
- }
-}
-
-template<class Type>
-typename enable_if<is_interval_container<Type>, Type>::type&
-join(Type& object)
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::iterator iterator;
-
- iterator it_ = object.begin();
- if(it_ == object.end())
- return object;
-
- iterator next_ = it_; next_++;
-
- while(next_ != object.end())
- {
- if( segmental::is_joinable<Type>(it_, next_) )
- {
- iterator fst_mem = it_; // hold the first member
-
- // Go on while touching members are found
- it_++; next_++;
- while( next_ != object.end()
- && segmental::is_joinable<Type>(it_, next_) )
- { it_++; next_++; }
-
- // finally we arrive at the end of a sequence of joinable intervals
- // and it points to the last member of that sequence
- const_cast<interval_type&>(Type::key_value(it_))
- = hull(Type::key_value(it_), Type::key_value(fst_mem));
- object.erase(fst_mem, it_);
-
- it_++; next_=it_;
- if(next_!=object.end())
- next_++;
- }
- else { it_++; next_++; }
- }
- return object;
-}
-
-
-template<class Type>
-typename enable_if<mpl::and_< is_interval_map<Type>
- , absorbs_neutrons<Type> >, Type>::type&
-absorb_neutrons(Type& object)
-{
- return object;
-}
-
-template<class Type>
-typename enable_if<mpl::and_< is_interval_map<Type>
- , mpl::not_<absorbs_neutrons<Type> > >, Type>::type&
-absorb_neutrons(Type& object)
-{
- typedef typename Type::segment_type segment_type;
- return itl::erase_if(content_is_neutron<segment_type>(), object);
-}
-
//==============================================================================
//= Streaming
//==============================================================================
-template<class CharType, class CharTraits, class Type>
-typename enable_if<is_interval_set<Type>,
- std::basic_ostream<CharType, CharTraits> >::type&
-operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
-{
- stream << "{";
- ITL_const_FORALL(typename Type, it_, object)
- stream << (*it_);
-
- return stream << "}";
-}
-
-template<class CharType, class CharTraits, class Type>
-typename enable_if<is_interval_map<Type>,
- std::basic_ostream<CharType, CharTraits> >::type&
-operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
-{
- stream << "{";
- ITL_const_FORALL(typename Type, it_, object)
- stream << "(" << it_->first << "->" << it_->second << ")";
-
- return stream << "}";
-}
-
}} // 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-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -53,15 +53,6 @@
:key(std_pair.first), data(std_pair.second){}
};
-template<class Type>
-inline typename enable_if<is_interval_map<Type>, typename Type::segment_type>::type
-make_segment(const typename Type::element_type& element)
-{
- typedef typename Type::interval_type interval_type;
- typedef typename Type::segment_type segment_type;
- return segment_type(interval_type(element.key), element.data);
-}
-
/** \brief Implements a map as a map of intervals (base class) */
template
<
@@ -144,7 +135,7 @@
<has_set_semantics<codomain_type>
, ITL_SECTION_CODOMAIN(Section,CodomainT)
, codomain_combine
- >::type codomain_intersect; //JODO extra metafuction?
+ >::type codomain_intersect; //JODO extra metafunction?
//JODO What, if codomain is not a set but the user want's to use a special intersection functor?
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-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -82,7 +82,7 @@
//------------------------------------------------------------------------------
template<class Type>
typename enable_if<is_interval_set<Type>, void>::type
-add_intersection(Type&, const Type&, const typename Type::domain_type&);
+add_intersection(Type&, const Type&, const typename Type::element_type&);
template<class Type>
typename enable_if<is_interval_set<Type>, void>::type
@@ -374,8 +374,8 @@
//= Insertion, erasure
//==========================================================================
- std::pair<iterator,bool> _insert(const value_type& value){ return this->_set.insert(value); }
- iterator _insert(iterator prior, const value_type& value){ return this->_set.insert(prior, value); }
+ //CL std::pair<iterator,bool> _insert(const value_type& value){ return this->_set.insert(value); } //CL
+ //CL iterator _insert(iterator prior, const value_type& value){ return this->_set.insert(prior, value); } //CL
/** Insert an element \c key into the set */
Modified: sandbox/itl/boost/itl/map.hpp
==============================================================================
--- sandbox/itl/boost/itl/map.hpp (original)
+++ sandbox/itl/boost/itl/map.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -23,6 +23,7 @@
#include <boost/itl/detail/notate.hpp>
#include <boost/itl/detail/design_config.hpp>
#include <boost/itl/detail/concept_check.hpp>
+#include <boost/itl/detail/on_neutric.hpp>
#include <boost/itl/type_traits/is_map.hpp>
#include <boost/itl/type_traits/absorbs_neutrons.hpp>
#include <boost/itl/type_traits/is_total.hpp>
@@ -33,13 +34,10 @@
#include <boost/itl/predicates.hpp>
#include <boost/itl/set.hpp>
-#include <boost/itl/functions/container.hpp>
-#include <boost/itl/functions/icl_container.hpp>
-#include <boost/itl/functions/associative_element_container.hpp>
#include <boost/itl/detail/map_algo.hpp>
-//CL #include <boost/itl/detail/map_functors.hpp>
-#include <boost/itl/map_functions.hpp>
-
+#include <boost/itl/concept/abstract/container.hpp>
+#include <boost/itl/concept/element/map.hpp>
+#include <boost/itl/concept/element/set_or_map.hpp>
namespace boost{namespace itl
{
@@ -136,17 +134,8 @@
BOOST_STATIC_CONSTANT(bool,
total_invertible = (mpl::and_<is_total<type>, has_inverse<codomain_type> >::value));
- typedef map_add<type,codomain_combine,_absorbs> add_;
- typedef map_subtract<type,total_invertible> subtract_;
-
- typedef map_insert<type,codomain_combine,_absorbs> insert_;
- typedef map_erase<type,codomain_combine,_absorbs> erase_;
-
- typedef map_add_intersection<type,_total> add_intersection_;
- typedef map_inplace_intersect<type,_total> inplace_intersect_;
- typedef map_intersects<type,_total> intersects_;
-
- typedef map_flip<type,_total,_absorbs> flip_;
+ typedef on_neutric<type,codomain_combine,Traits::absorbs_neutrons>
+ on_neutron_absorbtion;
public:
typedef typename base_type::pointer pointer;
@@ -159,8 +148,13 @@
typedef typename base_type::difference_type difference_type;
typedef typename base_type::reverse_iterator reverse_iterator;
typedef typename base_type::const_reverse_iterator const_reverse_iterator;
-
- enum { fineness = 4 };
+
+public:
+ BOOST_STATIC_CONSTANT(bool,
+ is_total_invertible = ( Traits::is_total
+ && has_inverse<codomain_type>::value));
+
+ BOOST_STATIC_CONSTANT(int, fineness = 4);
public:
//==========================================================================
@@ -262,7 +256,7 @@
}
//==========================================================================
- //= Addition, subtraction
+ //= Addition
//==========================================================================
/** \c add inserts \c value_pair into the map if it's key does
not exist in the map.
@@ -270,26 +264,52 @@
value is added to the data value already found in the map. */
map& add(const value_type& value_pair)
{
- return itl::add(*this, value_pair);
+ return _add<codomain_combine>(value_pair);
}
/** \c add add \c value_pair into the map using \c prior as a hint to
insert \c value_pair after the position \c prior is pointing to. */
iterator add(iterator prior, const value_type& value_pair)
{
- return itl::add(*this, prior, value_pair);
+ return _add<codomain_combine>(prior, value_pair);
}
+ //==========================================================================
+ //= Subtraction
+ //==========================================================================
/** If the \c value_pair's key value is in the map, it's data value is
subtraced from the data value stored in the map. */
- map& subtract(const value_type& value_pair)
+ map& subtract(const element_type& value_pair)
{
- return itl::subtract(*this, value_pair);
+ on_invertible<type, is_total_invertible>
+ ::subtract(*this, value_pair);
+ return *this;
+ }
+
+ map& subtract(const domain_type& key)
+ {
+ itl::erase(*this, key);
+ return *this;
}
//==========================================================================
//= Insertion, erasure
//==========================================================================
+ std::pair<iterator,bool> insert(const value_type& value_pair)
+ {
+ if(on_neutron_absorbtion::is_absorbable(value_pair.second))
+ return std::pair<iterator,bool>(end(),true);
+ else
+ return base_type::insert(value_pair);
+ }
+
+ iterator insert(iterator prior, const value_type& value_pair)
+ {
+ if(on_neutron_absorbtion::is_absorbable(value_pair.second))
+ return end();
+ else
+ return base_type::insert(prior, 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)
@@ -300,16 +320,23 @@
/** 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);
+ size_type erase(const element_type& key_value_pair)
+ { return itl::erase(*this, key_value_pair); }
//==========================================================================
//= Intersection
//==========================================================================
+ /** The intersection of \c key_value_pair and \c *this map is added to \c section. */
+ void add_intersection(map& section, const element_type& key_value_pair)const
+ {
+ on_definedness<type, Traits::is_total>
+ ::add_intersection(section, *this, key_value_pair);
+ }
/** The intersection of \c operand in \c *this map is added to \c section. */
- template<class OperandT>
- map& add_intersection(map& section, const OperandT& operand)const
- { return itl::add_intersection(section, *this, operand); }
+ //CL template<class OperandT>
+ //map& add_intersection(map& section, const OperandT& operand)const
+ //{ return itl::add_intersection(section, *this, operand); }
/** Returns true, if there is an intersection of \c operand and \c *this map. */
template<class OperandT>
@@ -323,8 +350,8 @@
//==========================================================================
map& flip(const element_type& operand)
- {
- return itl::flip(*this, operand);
+ {
+ return on_total_absorbable<type,_total,_absorbs>::flip(*this, operand);
}
//==========================================================================
@@ -357,10 +384,288 @@
ITL_const_FORALL_THIS(it_)
prior_ = domain_set.insert(prior_, it_->first);
}
+
+private:
+ template<class Combiner>
+ map& _add(const element_type& value_pair);
+
+ template<class Combiner>
+ iterator _add(iterator prior, const element_type& value_pair);
+
+ template<class Combiner>
+ map& _subtract(const element_type& value_pair);
+
+ template<class FragmentT>
+ void total_add_intersection(type& section, const FragmentT& fragment)const
+ {
+ section += *this;
+ section.add(fragment);
+ }
+
+ void partial_add_intersection(type& section, const element_type& operand)const
+ {
+ const_iterator it_ = find(operand.first);
+ if(it_ != end())
+ {
+ section.template _add<codomain_combine >(*it_);
+ section.template _add<codomain_intersect>(operand);
+ }
+ }
+
+
+private:
+ //--------------------------------------------------------------------------
+ template<class Type, bool is_total_invertible>
+ struct on_invertible;
+
+ template<class Type>
+ struct on_invertible<Type, true>
+ {
+ typedef typename Type::element_type element_type;
+ typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
+
+ static void subtract(Type& object, const element_type& operand)
+ { object.template _add<inverse_codomain_combine>(operand); }
+ };
+
+ template<class Type>
+ struct on_invertible<Type, false>
+ {
+ typedef typename Type::element_type element_type;
+ typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
+
+ static void subtract(Type& object, const element_type& operand)
+ { object.template _subtract<inverse_codomain_combine>(operand); }
+ };
+
+ friend struct on_invertible<type, true>;
+ friend struct on_invertible<type, false>;
+ //--------------------------------------------------------------------------
+
+ //--------------------------------------------------------------------------
+ template<class Type, bool is_total>
+ struct on_definedness;
+
+ template<class Type>
+ struct on_definedness<Type, true>
+ {
+ static void add_intersection(Type& section, const Type& object,
+ const element_type& operand)
+ { object.total_add_intersection(section, operand); }
+ };
+
+ template<class Type>
+ struct on_definedness<Type, false>
+ {
+ static void add_intersection(Type& section, const Type& object,
+ const element_type& operand)
+ { object.partial_add_intersection(section, operand); }
+ };
+
+ friend struct on_definedness<type, true>;
+ friend struct on_definedness<type, false>;
+ //--------------------------------------------------------------------------
+
+ //--------------------------------------------------------------------------
+ template<class Type, bool has_set_semantics, bool absorbs_neutrons>
+ struct on_codomain_model;
+
+ template<class Type>
+ struct on_codomain_model<Type, false, false>
+ { // !codomain_is_set, !absorbs_neutrons
+ static void subtract(Type& object, typename Type::iterator it_,
+ const typename Type::codomain_type& )
+ { it_->second = neutron<typename Type::codomain_type>::value(); }
+ };
+
+ template<class Type>
+ struct on_codomain_model<Type, false, true>
+ { // !codomain_is_set, absorbs_neutrons
+ static void subtract(Type& object, typename Type::iterator it_,
+ const typename Type::codomain_type& )
+ { object.erase(it_); }
+ };
+
+ template<class Type>
+ struct on_codomain_model<Type, true, false>
+ { // !codomain_is_set, !absorbs_neutrons
+ typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
+ static void subtract(Type& object, typename Type::iterator it_,
+ const typename Type::codomain_type& co_value)
+ {
+ inverse_codomain_intersect()(it_->second, co_value);
+ }
+ };
+
+ template<class Type>
+ struct on_codomain_model<Type, true, true>
+ { // !codomain_is_set, absorbs_neutrons
+ typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
+ static void subtract(Type& object, typename Type::iterator it_,
+ const typename Type::codomain_type& co_value)
+ {
+ inverse_codomain_intersect()(it_->second, co_value);
+ if(it_->second == neutron<codomain_type>::value())
+ object.erase(it_);
+ }
+ };
+ //--------------------------------------------------------------------------
+
+ //--------------------------------------------------------------------------
+ template<class Type, bool is_total, bool absorbs_neutrons>
+ struct on_total_absorbable;
+
+ template<class Type>
+ struct on_total_absorbable<Type, true, true>
+ {
+ typedef typename Type::element_type element_type;
+ static Type& flip(Type& object, const typename Type::element_type&)
+ { itl::clear(object); return object; }
+ };
+
+ template<class Type>
+ struct on_total_absorbable<Type, true, false>
+ {
+ typedef typename Type::element_type element_type;
+ typedef typename Type::codomain_type codomain_type;
+
+ static Type& flip(Type& object, const element_type& operand)
+ {
+ object.add(operand);
+ ITL_FORALL(typename Type, it_, object)//JODO URG sollte man vorher abfangen
+ it_->second = neutron<codomain_type>::value();
+
+ return object;
+ }
+ };
+
+ template<class Type>
+ struct on_total_absorbable<Type, false, true>
+ { // !is_total, absorbs_neutrons
+ typedef typename Type::element_type element_type;
+ typedef typename Type::codomain_type codomain_type;
+ typedef typename Type::iterator iterator;
+ typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
+
+ static Type& flip(Type& object, const element_type& operand)
+ {
+ std::pair<iterator,bool> insertion = object.insert(operand);
+ if(!insertion.second)
+ on_codomain_model<Type, has_set_semantics<codomain_type>::value, true>
+ ::subtract(object, insertion.first, operand.second);
+
+ return object; //JODO return of Type& not necessary
+ }
+ };
+
+ template<class Type>
+ struct on_total_absorbable<Type, false, false>
+ { // !is_total !absorbs_neutrons
+ typedef typename Type::element_type element_type;
+ typedef typename Type::codomain_type codomain_type;
+ typedef typename Type::iterator iterator;
+ typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
+
+ static Type& flip(Type& object, const element_type& operand)
+ {
+ std::pair<iterator,bool> insertion = object.insert(operand);
+ if(!insertion.second)
+ on_codomain_model<Type, has_set_semantics<codomain_type>::value, false>
+ ::subtract(object, insertion.first, operand.second);
+
+ return object; //JODO return of Type& not necessary
+ }
+ };
+
+ friend struct on_total_absorbable<type, true, true >;
+ friend struct on_total_absorbable<type, false, true >;
+ friend struct on_total_absorbable<type, true, false>;
+ friend struct on_total_absorbable<type, false, false>;
+ //--------------------------------------------------------------------------
};
+//==============================================================================
+//= Addition<ElementMap>
+//==============================================================================
+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>
+ ::_add(const element_type& addend)
+{
+ typedef typename on_neutric
+ <type,Combiner,absorbs_neutrons<type>::value>::type on_neutric_;
+
+ const codomain_type& co_val = addend.second;
+ if(on_neutric_::is_absorbable(co_val))
+ return *this;
+
+ std::pair<iterator,bool> insertion
+ = base_type::insert(value_type(addend.first, version<Combiner>()(co_val)));
+
+ if(!insertion.second)
+ {
+ iterator it = insertion.first;
+ Combiner()((*it).second, co_val);
+
+ if(on_neutric_::is_absorbable((*it).second))
+ erase(it);
+ }
+ return *this;
+}
+
+
+template <class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_ALLOC Alloc>
+ template <class Combiner>
+typename map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::iterator
+ map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>
+ ::_add(iterator prior_, const value_type& addend)
+{
+ typedef typename on_neutric
+ <type,Combiner,absorbs_neutrons<type>::value>::type on_neutric_;
+
+ const codomain_type& co_val = addend.second;
+ if(on_neutric_::is_absorbable(co_val))
+ return end();
+
+ iterator inserted_
+ = base_type::insert(prior_,
+ value_type(addend.first, Combiner::neutron()));
+ Combiner()(inserted_->second, addend.second);
+
+ if(on_neutric_::is_absorbable(inserted_->second))
+ {
+ erase(inserted_);
+ return end();
+ }
+ else
+ return inserted_;
+}
+
+
+//==============================================================================
+//= Subtraction<ElementMap>
+//==============================================================================
+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& minuend)
+{
+ typedef typename on_neutric
+ <type,Combiner,absorbs_neutrons<type>::value>::type on_neutric_;
+
+ iterator it_ = find(minuend.first);
+ if(it_ != end())
+ {
+ Combiner()(it_->second, minuend.second);
+ if(on_neutric_::is_absorbable(it_->second))
+ erase(it_);
+ }
+ return *this;
+}
+
//-----------------------------------------------------------------------------
// type traits
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-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -10,518 +10,21 @@
#include <boost/itl/detail/design_config.hpp>
#include <boost/itl/detail/map_algo.hpp>
-#include <boost/itl/detail/map_functors.hpp>
+//CL #include <boost/itl/detail/map_functors.hpp>
#include <boost/itl/type_traits/is_element_container.hpp>
#include <boost/itl/type_traits/is_key_container_of.hpp>
-#include <boost/itl/functions/container.hpp>
-#include <boost/itl/functions/associative_element_container.hpp>
+//CL#include <boost/itl/functions/container.hpp>
+//#include <boost/itl/functions/associative_element_container.hpp>
-namespace boost{namespace itl
-{
-
-//==============================================================================
-//= Containedness
-//==============================================================================
-
-
-/** Checks if a key-value pair is in the map */
-template<class MapT>
-typename enable_if<is_element_map<MapT>, bool>::type
-within(const typename MapT::element_type& value_pair, const MapT& super)
-{
- typedef typename MapT::const_iterator const_iterator;
- const_iterator found_ = super.find(value_pair.first);
- return found_ != super.end() && found_->second == value_pair.second;
-}
-
-template<class MapT>
-typename enable_if<is_element_map<MapT>, bool>::type
-contains(const MapT& super, const typename MapT::element_type& value_pair)
-{
- return itl::within(value_pair, super);
-}
-
-
-//==============================================================================
-//= Equivalences and Orderings
-//==============================================================================
-
-/** Protonic equality is equality on all elements that do not carry a neutron as content. */
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, bool>::type
-is_protonic_equal(const MapT& lhs, const MapT& rhs)
-{
- return Map::lexicographical_protonic_equal(lhs, rhs);
-}
-
-
-//==============================================================================
-//= Addition
-//==============================================================================
-/** \c add inserts \c value_pair into the map if it's key does
- not exist in the map.
- If \c value_pairs's key value exists in the map, it's data
- value is added to the data value already found in the map. */
-template <class MapT>
-typename enable_if<is_element_map<MapT>, MapT>::type&
-add(MapT& object, const typename MapT::value_type& value_pair)
-{
- return MapT::add_::apply(object, value_pair);
-}
-
-/** \c add add \c value_pair into the map using \c prior as a hint to
- insert \c value_pair after the position \c prior is pointing to. */
-template <class MapT>
-typename enable_if<is_element_map<MapT>, typename MapT::iterator>::type
-add(MapT& object, typename MapT::iterator prior,
- const typename MapT::value_type& value_pair)
-{
- return MapT::add_::apply(object, prior, value_pair);
-}
-
-
-//==============================================================================
-//= Subtraction
-//==============================================================================
-/** If the \c value_pair's key value is in the map, it's data value is
- subtraced from the data value stored in the map. */
-template <class MapT>
-typename enable_if<is_element_map<MapT>, MapT>::type&
-subtract(MapT& object, const typename MapT::element_type& value_pair)
-{
- return MapT::subtract_::apply(object, value_pair);
-}
-
-template <class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-operator -= (MapT& object, const typename MapT::element_type& value_pair)
-{
- return itl::subtract(object, value_pair);
-}
-
-template <class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type
-operator - (MapT object, const typename MapT::element_type& value_pair)
-{
- return object -= value_pair;
-}
-
-template <class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-operator -= (MapT& object, const MapT& subtrahend)
-{
- ITL_const_FORALL(typename MapT, it_, subtrahend)
- itl::subtract(object, *it_);
-
- return object;
-}
-
-template <class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type
-operator - (MapT object, const MapT& subtrahend)
-{
- return object -= subtrahend;
-}
-
-template <class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-operator -= (MapT& object, const typename MapT::set_type& subtrahend)
-{
- return Set::erase(object, subtrahend);
-}
-
-template <class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type
-operator - (MapT object, const typename MapT::set_type& subtrahend)
-{
- return object -= subtrahend;
-}
-
-
-
-//==============================================================================
-//= Insertion
-//==============================================================================
-
-template<class MapT>
-typename enable_if<is_element_map<MapT>,
- std::pair<typename MapT::iterator,bool> >::type
-insert(MapT& object, const typename MapT::element_type& value_pair)
-{
- typedef typename MapT::insert_ map_insert;
- return map_insert::apply(object, value_pair);
-}
-
-template<class MapT>
-typename enable_if<is_element_map<MapT>,
- typename MapT::iterator>::type
-insert(MapT& object, typename MapT::iterator prior, const typename MapT::element_type& value_pair)
-{
- return MapT::insert_::apply(object, prior, value_pair);
-}
-
-template<class MapT>
-typename enable_if<is_element_map<MapT>, MapT>::type&
-insert(MapT& object, const MapT& addend)
-{
- typedef typename MapT::iterator iterator;
-
- iterator prior_ = object.end();
- ITL_const_FORALL(typename MapT, elem_, addend)
- itl::insert(object, prior_, *elem_);
-
- return object;
-}
-
-//==============================================================================
-//= Erasure
-//==============================================================================
-
-template<class MapT>
-typename enable_if<is_element_map<MapT>, typename MapT::size_type>::type
-erase(MapT& object, const typename MapT::domain_type& key_value)
-{
- return MapT::erase_::apply(object, key_value);
-}
-
-template<class MapT>
-typename enable_if<is_element_map<MapT>, typename MapT::size_type>::type
-erase(MapT& object, const typename MapT::element_type& value_pair)
-{
- return MapT::erase_::apply(object, value_pair);
-}
-
-template<class MapT>
-typename enable_if<is_element_map<MapT>, MapT>::type&
-erase(MapT& object, const typename MapT::set_type& erasure)
-{
- typedef typename MapT::set_type set_type;
- ITL_const_FORALL(typename set_type, elem_, erasure)
- itl::erase(object, *elem_);
-
- return object;
-}
-
-template<class MapT>
-typename enable_if<is_element_map<MapT>, MapT>::type&
-erase(MapT& object, const MapT& erasure)
-{
- ITL_const_FORALL(typename MapT, elem_, erasure)
- itl::erase(object, *elem_);
-
- return object;
-}
-
-
-
-//==============================================================================
-//= Intersection
-//==============================================================================
+#include <boost/itl/concept/abstract/container.hpp>
+#include <boost/itl/concept/element/set_or_map.hpp>
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-add_intersection(MapT& section, const MapT& object, const typename MapT::domain_type& key_value)
-{
- return MapT::add_intersection_::apply(section, object, key_value);
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-add_intersection(MapT& section, const MapT& object, const typename MapT::element_type& value_pair)
-{
- return MapT::add_intersection_::apply(section, object, value_pair);
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-add_intersection(MapT& section, const MapT& object, const typename MapT::set_type& key_set)
-{
- typedef typename MapT::set_type set_type;
- typedef typename set_type::const_iterator const_iterator;
-
- const_iterator common_lwb_;
- const_iterator common_upb_;
- if(!Set::common_range(common_lwb_, common_upb_, key_set, object))
- return section;
-
- const_iterator sec_ = common_lwb_;
- while(sec_ != common_upb_)
- itl::add_intersection(section, object, *sec_++);
-
- return section;
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-add_intersection(MapT& section, const MapT& object, const MapT& operand)
-{
- return MapT::add_intersection_::apply(section, object, operand);
-}
-
-
-/** Intersect map \c x2 and \c *this.
- So \c *this becomes the intersection of \c *this and \c x2 */
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-operator &= (MapT& object, const MapT& operand)
-{
- return MapT::inplace_intersect_::apply(object, operand);
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type
-operator & (MapT object, const MapT& operand)
-{
- return object &= operand;
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-operator &= (MapT& object, const typename MapT::element_type& operand) //JODO codereplica.
-{
- return MapT::inplace_intersect_::apply(object, operand);
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type
-operator & (MapT object, const typename MapT::element_type& value_pair)
-{
- return object &= value_pair;
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type
-operator & (const typename MapT::element_type& value_pair, MapT object)
-{
- return object &= value_pair;
-}
-
-
-/** Intersect set \c x2 and \c *this.
- So \c *this becomes the intersection of \c *this and \c x2 */
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-operator &= (MapT& object, const typename MapT::set_type& operand)
-{
- MapT section;
- add_intersection(section, object, operand);
- object.swap(section);
- return object;
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type
-operator & (MapT object, const typename MapT::set_type& key_set)
-{
- return object &= key_set; //JODO test a - (a & s) == a - s
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type
-operator & (const typename MapT::set_type& key_set, MapT object)
-{
- return object &= key_set; //JODO test a - (s & a) == a - s
-}
-
-
-//------------------------------------------------------------------------------
-//- intersects
-//------------------------------------------------------------------------------
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, bool>::type
-intersects(const MapT& object, const typename MapT::domain_type& operand)
-{
- return MapT::intersects_::apply(object, operand);
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, bool>::type
-intersects(const typename MapT::domain_type& operand, const MapT& object)
-{
- return MapT::intersects_::apply(object, operand);
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, bool>::type
-intersects(const MapT& object, const typename MapT::element_type& operand)
-{
- return MapT::intersects_::apply(object, operand);
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, bool>::type
-intersects(const typename MapT::element_type& operand, const MapT& object)
-{
- return MapT::intersects_::apply(object, operand);
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, bool>::type
-intersects(const MapT& object, const typename MapT::set_type& operand)
-{
- return MapT::intersects_::apply(object, operand);
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, bool>::type
-intersects(const typename MapT::set_type& operand, const MapT& object)
-{
- return MapT::intersects_::apply(object, operand);
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, bool>::type
-intersects(const MapT& object, const MapT& operand)
-{
- return MapT::intersects_::apply(object, operand);
-}
-
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, bool>::type
-disjoint(const MapT& left, const MapT& right)//JODO All variants via meta predicate.
-{
- return !intersects(left, right);
-}
-
-
-
-//==============================================================================
-//= Symmetric difference
-//==============================================================================
-
-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);
-}
-
-
-/** Symmetric subtract map \c x2 and \c *this.
- So \c *this becomes the symmetric difference of \c *this and \c x2 */
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-operator ^= (MapT& object, const MapT& operand)
-{
- return MapT::flip_::apply(object, operand);
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type
-operator ^ (MapT object, const MapT& operand)
-{
- return object ^= operand;
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type
-operator ^ (MapT object, const typename MapT::element_type& value_pair)
-{
- MapT operand;//JODO
- operand.insert(value_pair);
- return object ^= operand;
-}
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type
-operator ^ (const typename MapT::element_type& value_pair, MapT object)
-{
- MapT operand;//JODO
- operand.insert(value_pair);
- return object ^= operand;
-}
-
-//==============================================================================
-//= Set selection
-//==============================================================================
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>,
- typename MapT::set_type>::type&
-domain(typename MapT::set_type& domain_set, const MapT& object)
-{
- typename MapT::set_type::iterator prior_ = domain_set.end();
- typename MapT::const_iterator it_ = object.begin();
- while(it_ != object.end())
- prior_ = domain_set.insert(prior_, (*it_++).first);
- //JODO prior_ = itl::insert(domain_set, prior_, it_->first);
-
- return domain_set;
-}
-
-
-//==============================================================================
-//= Manipulation by predicates
-//==============================================================================
-
-template<class MapT, class Predicate>
-typename enable_if<is_element_map<MapT>, MapT>::type&
-erase_if(const Predicate& pred, MapT& object)
-{
- typename MapT::iterator it_ = object.begin();
- while(it_ != object.end())
- if(pred(*it_))
- itl::erase(object, it_++);
- else ++it_;
- return object;
-}
-
-
-template<class MapT, class Predicate>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-add_if(const Predicate& pred, MapT& object, const MapT& src)
-{
- typename MapT::const_iterator it_ = src.begin();
- while(it_ != src.end())
- if(pred(*it_))
- itl::add(object, *it_++);
-
- return object;
-}
-
-template<class MapT, class Predicate>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-assign_if(const Predicate& pred, MapT& object, const MapT& src)
-{
- itl::clear(object);
- return add_if(object, src, pred);
-}
-
-//==============================================================================
-//= Neutron absorbtion
-//==============================================================================
-
-template<class MapT>
-inline typename enable_if<is_element_map<MapT>, MapT>::type&
-absorb_neutrons(MapT& object)
-{
- BOOST_STATIC_CONSTANT(bool, absorbs = MapT::Traits::absorbs_neutrons);
- return map_absorb_neutrons<MapT,absorbs>::apply(object);
-}
-
-
-//---------------------------------------------------------------------------------
-template<class CharType, class CharTraits, class MapT>
-inline typename enable_if<is_element_map<MapT>, std::basic_ostream<CharType, CharTraits> >::type&
-operator << (std::basic_ostream<CharType, CharTraits>& stream, const MapT& object)
+namespace boost{namespace itl
{
- stream << "{";
- ITL_const_FORALL(typename MapT, it, object)
- stream << "(" << it->first << "->" << it->second << ")";
-
- return stream << "}";
-}
+//JODO remove file
}} // namespace itl boost
Modified: sandbox/itl/boost/itl/set.hpp
==============================================================================
--- sandbox/itl/boost/itl/set.hpp (original)
+++ sandbox/itl/boost/itl/set.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -26,15 +26,15 @@
#include <boost/itl/detail/subset_comparer.hpp>
#include <boost/itl/detail/set_algo.hpp>
#include <boost/itl/predicates.hpp>
-#include <boost/itl/set_functions.hpp>
#include <boost/mpl/or.hpp>
#include <boost/mpl/not.hpp>
#include <boost/type_traits/is_same.hpp>
-#include <boost/itl/functions/container.hpp>
-#include <boost/itl/functions/icl_container.hpp>
-#include <boost/itl/functions/associative_element_container.hpp>
-#include <boost/itl/set_functions.hpp>
+#include <boost/itl/concept/abstract/container.hpp>
+#include <boost/itl/concept/element/set.hpp>
+#include <boost/itl/concept/element/set_or_map.hpp>
+#include <boost/itl/concept/abstract/comparable.hpp>
+
namespace boost{namespace itl
{
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-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -11,7 +11,6 @@
#include <boost/itl/detail/design_config.hpp>
#include <boost/itl/type_traits/is_element_container.hpp>
#include <boost/itl/detail/map_algo.hpp>
-#include <boost/itl/detail/map_functors.hpp>
#include <boost/itl/functions/container.hpp>
#include <boost/itl/functions/associative_element_container.hpp>
@@ -20,426 +19,7 @@
namespace boost{namespace itl
{
-//------------------------------------------------------------------------------
-
-
-//==============================================================================
-//= Addition
-//==============================================================================
-/** \c add inserts \c operand into the map if it's key does
- not exist in the map.
- If \c operands's key value exists in the map, it's data
- value is added to the data value already found in the map. */
-template <class SetT>
-typename enable_if<is_element_set<SetT>, SetT>::type&
-add(SetT& object, const typename SetT::element_type& operand)
-{
- object.insert(operand);
- return object;
-}
-
-/** \c add add \c operand into the map using \c prior as a hint to
- insert \c operand after the position \c prior is pointing to. */
-template <class SetT>
-typename enable_if<is_element_set<SetT>, typename SetT::iterator>::type
-add(SetT& object, typename SetT::iterator prior,
- const typename SetT::element_type& operand)
-{
- return object.insert(prior, operand);
-}
-
-
-//==============================================================================
-//= Subtraction
-//==============================================================================
-/** If the \c operand's key value is in the map, it's data value is
- subtraced from the data value stored in the map. */
-template <class SetT>
-typename enable_if<is_element_set<SetT>, SetT>::type&
-subtract(SetT& object, const typename SetT::element_type& operand)
-{
- typedef typename SetT::iterator iterator;
- iterator it_ = object.find(operand);
- if(it_ != object.end())
- object.erase(it_);
-
- return object;
-}
-
-template <class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-operator -= (SetT& object, const typename SetT::element_type& operand)
-{
- return itl::subtract(object, operand);
-}
-
-template <class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type
-operator - (SetT object, const typename SetT::element_type& operand)
-{
- return object -= operand;
-}
-
-template <class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-operator -= (SetT& object, const SetT& subtrahend)
-{
- ITL_const_FORALL(typename SetT, it_, subtrahend)
- itl::subtract(object, *it_);
-
- return object;
-}
-
-template <class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type
-operator - (SetT object, const SetT& subtrahend)
-{
- return object -= subtrahend;
-}
-
-template <class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-operator -= (SetT& object, const typename SetT::set_type& subtrahend)
-{
- return Set::erase(object, subtrahend);
-}
-
-template <class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type
-operator - (SetT object, const typename SetT::set_type& subtrahend)
-{
- return object -= subtrahend;
-}
-
-
-
-//==============================================================================
-//= Insertion
-//==============================================================================
-
-template<class SetT>
-typename enable_if<is_element_set<SetT>,
- std::pair<typename SetT::iterator,bool> >::type
-insert(SetT& object, const typename SetT::element_type& operand)
-{
- return object.insert(operand);
-}
-
-template<class SetT>
-typename enable_if<is_element_set<SetT>,
- typename SetT::iterator>::type
-insert(SetT& object, typename SetT::iterator prior, const typename SetT::element_type& operand)
-{
- return object.insert(prior, operand);
-}
-
-template<class SetT>
-typename enable_if<is_element_set<SetT>, SetT>::type&
-insert(SetT& object, const SetT& addend)
-{
- typedef typename SetT::iterator iterator;
-
- iterator prior_ = object.end();
- ITL_const_FORALL(typename SetT, elem_, addend)
- itl::insert(object, prior_, *elem_);
-
- return object;
-}
-
-//==============================================================================
-//= Erasure
-//==============================================================================
-
-template<class SetT>
-typename enable_if<is_element_set<SetT>, typename SetT::size_type>::type
-erase(SetT& object, const typename SetT::domain_type& operand)
-{
- typedef typename SetT::iterator iterator;
- iterator it_ = object.find(operand);
- if(it_ != object.end())
- {
- object.erase(it_);
- return 1;
- }
-
- return 0;
-}
-
-template<class SetT>
-typename enable_if<is_element_set<SetT>, SetT>::type&
-erase(SetT& object, const typename SetT::set_type& erasure)
-{
- typedef typename SetT::set_type set_type;
- ITL_const_FORALL(typename set_type, elem_, erasure)
- itl::erase(object, *elem_);
-
- return object;
-}
-
-template<class SetT>
-typename enable_if<is_element_set<SetT>, SetT>::type&
-erase(SetT& object, const SetT& erasure)
-{
- ITL_const_FORALL(typename SetT, elem_, erasure)
- itl::erase(object, *elem_);
-
- return object;
-}
-
-
-
-//==============================================================================
-//= Intersection
-//==============================================================================
-
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-add_intersection(SetT& section, const SetT& object, const typename SetT::domain_type& operand)
-{
- typedef typename SetT::const_iterator const_iterator;
- const_iterator it_ = object.find(operand);
- if(it_ != object.end())
- itl::add(section, *it_);
-
- return section;
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-add_intersection(SetT& section, const SetT& object, const SetT& operand)
-{
- typedef typename SetT::const_iterator const_iterator;
- const_iterator common_lwb_;
- const_iterator common_upb_;
- if(!Set::common_range(common_lwb_, common_upb_, operand, object))
- return section;
-
- const_iterator sec_ = common_lwb_;
- while(sec_ != common_upb_)
- add_intersection(section, object, *sec_++);
-
- return section;
-}
-
-
-/** Intersect map \c x2 and \c *this.
- So \c *this becomes the intersection of \c *this and \c x2 */
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-operator &= (SetT& object, const SetT& operand)
-{
- SetT section;
- itl::add_intersection(section, object, operand);
- object.swap(section);
- return object;
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type
-operator & (SetT object, const SetT& operand)
-{
- return object &= operand;
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-operator &= (SetT& object, const typename SetT::element_type& operand) //JODO codereplica.
-{
- SetT section;
- itl::add_intersection(section, object, operand);
- object.swap(section);
- return object;
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type
-operator & (SetT object, const typename SetT::element_type& operand)
-{
- return object &= operand;
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type
-operator & (const typename SetT::element_type& operand, SetT object)
-{
- return object &= operand;
-}
-
-
-/** Intersect set \c x2 and \c *this.
- So \c *this becomes the intersection of \c *this and \c x2 */
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-operator &= (SetT& object, const typename SetT::set_type& operand)
-{
- SetT section;
- add_intersection(section, object, operand);
- object.swap(section);
- return object;
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type
-operator & (SetT object, const typename SetT::set_type& key_set)
-{
- return object &= key_set; //JODO test a - (a & s) == a - s
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type
-operator & (const typename SetT::set_type& key_set, SetT object)
-{
- return object &= key_set; //JODO test a - (s & a) == a - s
-}
-
-
-//------------------------------------------------------------------------------
-//- intersects
-//------------------------------------------------------------------------------
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, bool>::type
-intersects(const SetT& object, const typename SetT::domain_type& operand)
-{
- return itl::contains(object, operand);
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, bool>::type
-intersects(const typename SetT::domain_type& operand, const SetT& object)
-{
- return itl::contains(object, operand);
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, bool>::type
-intersects(const SetT& object, const SetT& operand)
-{
- if(iterative_size(object) < iterative_size(operand))
- return Set::intersects(object, operand);
- else
- return Set::intersects(operand, object);
-}
-
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, bool>::type
-disjoint(const SetT& left, const SetT& right)//JODO All variants via meta predicate.
-{
- return !intersects(left, right);
-}
-
-
-
-//==============================================================================
-//= Symmetric difference
-//==============================================================================
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-flip(SetT& object, const typename SetT::element_type& operand)
-{
- typedef typename SetT::iterator iterator;
- std::pair<iterator,bool> insertion = object.insert(operand);
- if(!insertion.second)
- object.erase(insertion.first);
-
- return object;
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-operator ^= (SetT& object, const typename SetT::element_tpye& operand)
-{
- return itl::flip(object, operand);
-}
-
-/** Symmetric subtract map \c x2 and \c *this.
- So \c *this becomes the symmetric difference of \c *this and \c x2 */
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-operator ^= (SetT& object, const SetT& operand)
-{
- typedef typename SetT::const_iterator const_iterator;
- const_iterator it_ = operand.begin();
- while(it_ != operand.end())
- itl::flip(object, *it_++);
-
- return object;
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type
-operator ^ (SetT object, const SetT& operand)
-{
- return object ^= operand;
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type
-operator ^ (SetT object, const typename SetT::element_type& operand)
-{
- return itl::flip(object, operand);
-}
-
-template<class SetT>
-inline typename enable_if<is_element_set<SetT>, SetT>::type
-operator ^ (const typename SetT::element_type& operand, SetT object)
-{
- return itl::flip(object, operand);
-}
-
-//==============================================================================
-//= Manipulation by predicates
-//==============================================================================
-
-template<class SetT, class Predicate>
-typename enable_if<is_element_set<SetT>, SetT>::type&
-erase_if(const Predicate& pred, SetT& object)
-{
- typename SetT::iterator it_ = object.begin();
- while(it_ != object.end())
- if(pred(*it_))
- itl::erase(object, it_++);
- else ++it_;
- return object;
-}
-
-
-template<class SetT, class Predicate>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-add_if(const Predicate& pred, SetT& object, const SetT& src)
-{
- typename SetT::const_iterator it_ = src.begin();
- while(it_ != src.end())
- if(pred(*it_))
- itl::add(object, *it_++);
-
- return object;
-}
-
-template<class SetT, class Predicate>
-inline typename enable_if<is_element_set<SetT>, SetT>::type&
-assign_if(const Predicate& pred, SetT& object, const SetT& src)
-{
- itl::clear(object);
- return add_if(object, src, pred);
-}
-
-
-//---------------------------------------------------------------------------------
-template<class CharType, class CharTraits, class SetT>
-inline typename enable_if<is_element_set<SetT>, std::basic_ostream<CharType, CharTraits> >::type&
-operator << (std::basic_ostream<CharType, CharTraits>& stream, const SetT& object)
-{
- stream << "{";
- ITL_const_FORALL(typename SetT, it, object)
- stream << *it << " ";
-
- return stream << "}";
-}
-
+//JODO remove file
}} // namespace itl boost
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 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -100,7 +100,7 @@
DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>;
iterator handle_inserted(iterator it_)const { return it_; }
- void handle_inserted(iterator prior_, iterator it_)const{ }
+ void handle_inserted(iterator, iterator)const{ }
template<class Combiner>
void handle_left_combined(iterator it_)
@@ -133,7 +133,7 @@
this->_map.erase(it_);
}
- void handle_reinserted(iterator insertion_){}
+ void handle_reinserted(iterator){}
template<class Combiner>
void gap_insert_at(iterator& it_, iterator prior_,
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 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -131,6 +131,54 @@
};
//------------------------------------------------------------------------------
+// is_fragment_of
+//------------------------------------------------------------------------------
+template<class FragmentT, class Type>
+struct is_fragment_of
+{
+ typedef is_fragment_of type;
+ BOOST_STATIC_CONSTANT(bool, value = false);
+};
+
+template<class Type>
+struct is_fragment_of<typename Type::element_type, Type>
+{
+ typedef is_fragment_of type;
+ BOOST_STATIC_CONSTANT(bool, value = true);
+};
+
+template<class Type>
+struct is_fragment_of<typename Type::segment_type, Type>
+{
+ typedef is_fragment_of type;
+ BOOST_STATIC_CONSTANT(bool, value = true);
+};
+
+//------------------------------------------------------------------------------
+// is_key_of
+//------------------------------------------------------------------------------
+template<class KeyT, class Type>
+struct is_key_of
+{
+ typedef is_key_of type;
+ BOOST_STATIC_CONSTANT(bool, value = false);
+};
+
+template<class Type>
+struct is_key_of<typename Type::domain_type, Type>
+{
+ typedef is_key_of type;
+ BOOST_STATIC_CONSTANT(bool, value = true);
+};
+
+template<class Type>
+struct is_key_of<typename Type::interval_type, Type>
+{
+ typedef is_key_of type;
+ BOOST_STATIC_CONSTANT(bool, value = true);
+};
+
+//------------------------------------------------------------------------------
// is_interval_set_derivative
//------------------------------------------------------------------------------
template<class Type, class AssociateT>
Modified: sandbox/itl/boost/itl/type_traits/is_fragment_type_of.hpp
==============================================================================
--- sandbox/itl/boost/itl/type_traits/is_fragment_type_of.hpp (original)
+++ sandbox/itl/boost/itl/type_traits/is_fragment_type_of.hpp 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -14,7 +14,7 @@
{
-template<class CompanionT, class GuideT>
+template<class CompanionT, class GuideT>//CL unused
struct is_interval_map_fragment_type_of //JODO equivalent to is_interval_map_right_intra_combinable
{ //JODO generalize
typedef is_interval_map_fragment_type_of<CompanionT, GuideT> type;
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 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -92,7 +92,6 @@
BOOST_AUTO_TEST_CASE(interval_type_traits)
{
BOOST_CHECK_EQUAL(is_interval<continuous_interval<int> >::value, true);
- BOOST_CHECK_EQUAL(is_continuous_interval<continuous_interval<int> >::value, false);
BOOST_CHECK_EQUAL(is_continuous_interval<continuous_interval<double> >::value, true);
BOOST_CHECK_EQUAL((is_interval_set<interval_map<int,int> >::value), false);
@@ -232,6 +231,10 @@
BOOST_CHECK_EQUAL((is_map<MapII>::value), true);
BOOST_CHECK_EQUAL((is_icl_container<MapII>::value), true);
+ BOOST_CHECK_EQUAL((is_fragment_of<IntervalSetT::element_type, IntervalSetT>::value), true);
+ BOOST_CHECK_EQUAL((is_fragment_of<IntervalSetT::segment_type, IntervalSetT>::value), true);
+ BOOST_CHECK_EQUAL((is_fragment_of<discrete_interval<T>, IntervalSetT>::value), true);
+ BOOST_CHECK_EQUAL((is_fragment_of<double, IntervalSetT>::value), false);
//BOOST_CHECK_EQUAL(xx, true);
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 2010-09-23 11:35:20 EDT (Thu, 23 Sep 2010)
@@ -86,7 +86,9 @@
//typedef Antisymmetry<itl::map<int,int>, itl::sub_super_set, itl::element_equal> TestLawT;
//typedef InplaceAssociativity<itl::interval_map<int,itl::set<int> >, itl::inplace_caret, itl::element_equal> TestLawT;
- typedef InplaceFlip<itl::interval_map<int,int,total_enricher> > TestLawT;
+ typedef InplaceFlip< itl::map<int,int,partial_enricher> > TestLawT;
+ //typedef InplaceFlip< itl::map<int,int> > TestLawT;
+ //typedef InplaceFlip< itl::map<int, itl::set<int> > > TestLawT;
LawValidater<TestLawT> test_law;
@@ -104,7 +106,7 @@
start = ptime(microsec_clock::local_time());
test_law.run();
stop = ptime(microsec_clock::local_time());
- std::cout << "Stop. Time elapsed: " << stop - start << endl;
+ std::cout << "Stop. Time elapsed: " << stop - start << " for " << test_count << " tests\n";
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk