[Boost-commit] svn:boost r65374 - in sandbox/itl/boost/itl: . type_traits

Subject: [Boost-commit] svn:boost r65374 - in sandbox/itl/boost/itl: . type_traits
From: afojgo_at_[hidden]
Date: 2010-09-10 11:08:06

Author: jofaber
Date: 2010-09-10 11:08:03 EDT (Fri, 10 Sep 2010)
New Revision: 65374
URL: http://svn.boost.org/trac/boost/changeset/65374

Log:
Refactoring: Extraction erase member functions from interval_base_map. Stable{msvc-9.0, gcc-3.4.4}
Added:
   sandbox/itl/boost/itl/type_traits/element_type_of.hpp   (contents, props changed)
   sandbox/itl/boost/itl/type_traits/interval_type_of.hpp   (contents, props changed)
Text files modified: 
   sandbox/itl/boost/itl/functions.hpp         |   320 +++++++++++++++++++++++++++--           
   sandbox/itl/boost/itl/interval_base_map.hpp |   423 ++------------------------------------- 
   2 files changed, 314 insertions(+), 429 deletions(-)

Modified: sandbox/itl/boost/itl/functions.hpp
==============================================================================
--- sandbox/itl/boost/itl/functions.hpp	(original)
+++ sandbox/itl/boost/itl/functions.hpp	2010-09-10 11:08:03 EDT (Fri, 10 Sep 2010)
@@ -12,6 +12,8 @@
 #include <boost/mpl/or.hpp>
 #include <boost/utility/enable_if.hpp>
 #include <boost/itl/type_traits/domain_type_of.hpp>
+#include <boost/itl/type_traits/interval_type_of.hpp>
+#include <boost/itl/type_traits/element_type_of.hpp>
 #include <boost/itl/type_traits/segment_type_of.hpp>
 #include <boost/itl/type_traits/is_interval_container.hpp>
 #include <boost/itl/type_traits/is_interval_separator.hpp>
@@ -28,11 +30,15 @@
 namespace boost{namespace itl
 {
 
-//==========================================================================
-//= Containedness
-//==========================================================================
-
+//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
 //------------------------------------------------------------------------------
@@ -210,12 +216,8 @@
 typename enable_if<is_interval_map<Type>, Type>::type&
 add(Type& object, const typename Type::element_type& operand)
 {
-    typedef typename Type::value_type       value_type;
-    typedef typename Type::interval_type    interval_type;
     typedef typename Type::codomain_combine codomain_combine;
-    Interval_Map::add<Type,codomain_combine>
-        (object, value_type(interval_type(operand.key), 
-                            operand.data               ) );
+    Interval_Map::add<Type,codomain_combine>(object, make_segment<Type>(operand));
     return object;
 }
 
@@ -250,7 +252,7 @@
     ITL_const_FORALL(typename OperandT, elem_, operand) 
         prior_ = object.add(prior_, *elem_);
         //JODO prior_ = itl::add(object, prior_, *elem_); 
-        //JODO Problems with missing combining style of interval_base_map.
+        //JODO Problems with missing combining style of interval_baseobject.
         //JODO Prior to this, we have to implement the Trait class for
         //JODO combining styles for interval_base_maps.
 
@@ -390,13 +392,15 @@
 //==============================================================================
 //= 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; //JODO: May be it is better to return the iterator
+    return object;
 }
 
 template<class Type>
@@ -404,9 +408,70 @@
 subtract(Type& object, const typename Type::segment_type& operand)
 {
     Interval_Set::subtract(object, operand);
-    return object; //JODO: May be it is better to return the iterator
+    return object;
+}
+
+//------------------------------------------------------------------------------
+//- Subtraction<Interval_Map> fragment_types
+//------------------------------------------------------------------------------
+template<class Type>
+typename enable_if
+    <mpl::and_< is_interval_map<Type>
+              , mpl::and_< is_total<Type> 
+                         , has_inverse<typename Type::codomain_type> >
+              >, 
+    Type>::type&
+subtract(Type& object, const typename Type::segment_type& operand)
+{
+    typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
+    Interval_Map::add<Type,inverse_codomain_combine>(object, operand);
+    return object;
+}
+
+template<class Type>
+typename enable_if
+    <mpl::and_< is_interval_map<Type>
+              , mpl::not_<mpl::and_< is_total<Type> 
+                                   , has_inverse<typename Type::codomain_type> > >
+              >, 
+    Type>::type&
+subtract(Type& object, const typename Type::segment_type& operand)
+{
+    typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
+    Interval_Map::subtract<Type,inverse_codomain_combine>(object, operand);
+    return object;
+}
+
+
+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)
+{
+    typedef typename Type::interval_type interval_type;
+    Interval_Map::erase(object, interval_type(operand));
+    return object;
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+subtract(Type& object, const typename Type::interval_type& operand)
+{
+    Interval_Map::erase(object, operand);
+    return object;
 }
 
+
 //------------------------------------------------------------------------------
 //- Subtraction -=, -
 //------------------------------------------------------------------------------
@@ -478,13 +543,58 @@
 //==============================================================================
 //= 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)
+{
+    Interval_Map::insert(object, make_segment<Type>(operand));
+    return object;
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+insert(Type& object, const typename Type::segment_type& operand)
+{
+    Interval_Map::insert(object, operand);
+    return object;
+}
+
+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 Interval_Map::insert(object, 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) 
-        object.insert(*elem_); 
+        insert(object, *elem_); 
 
     return object; 
 }
@@ -493,27 +603,144 @@
 //==============================================================================
 //= 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)
+{
+    typedef typename Type::interval_type  interval_type;
+    typedef typename Type::value_type     value_type;
+    typedef typename Type::iterator       iterator;
+
+    if(itl::is_empty(minuend)) 
+        return object;
+
+    std::pair<iterator, iterator> exterior = object.equal_range(minuend);
+    if(exterior.first == exterior.second)
+        return object;
+
+	iterator first_ = exterior.first,
+		     end_   = exterior.second,
+		     last_  = prior(end_);
+
+    interval_type left_resid  = right_subtract(first_->first, minuend);
+    interval_type right_resid =  left_subtract(last_ ->first, minuend);
+
+    if(first_ == last_ )
+        if(!itl::is_empty(left_resid))
+        {
+            const_cast<interval_type&>(first_->first) = left_resid;
+            if(!itl::is_empty(right_resid))
+                object.insert(first_, value_type(right_resid, first_->second));
+        }
+        else if(!itl::is_empty(right_resid))
+            const_cast<interval_type&>(first_->first) = left_subtract(first_->first, minuend);
+        else
+            object.erase(first_);
+    else
+    {   //            [-------- minuend ---------)
+        // [left_resid   fst)   . . . .    [lst  right_resid)
+        iterator second_= first_; ++second_;
+
+        iterator start_ = itl::is_empty(left_resid)? first_: second_;
+        iterator stop_  = itl::is_empty(right_resid)? end_  : last_ ;
+        object.erase(start_, stop_); //erase [start_, stop_)
+
+        if(!itl::is_empty(left_resid))
+            const_cast<interval_type&>(first_->first) = left_resid;
+
+        if(!itl::is_empty(right_resid))
+            const_cast<interval_type&>(last_ ->first) = right_resid;
+    }
+    return object;
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+erase(Type& object, const typename Type::domain_type& minuend)
+{
+    typedef typename Type::interval_type interval_type;
+	return itl::erase(object, interval_type(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)
+{
+	Interval_Map::erase(object, minuend);
+	return object;
+}
+
+template<class Type>
+typename enable_if<is_interval_map<Type>, Type>::type&
+erase(Type& object, const typename Type::element_type& minuend)
+{
+	return itl::erase(object, make_segment<Type>(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;
 
-    typename OperandT::const_iterator common_lwb;
-    typename OperandT::const_iterator common_upb;
-
+    const_iterator common_lwb, common_upb;
     if(!Set::common_range(common_lwb, common_upb, operand, object))
         return object;
 
-    typename OperandT::const_iterator it_ = common_lwb;
+    const_iterator it_ = common_lwb;
     while(it_ != common_upb)
-        object.erase(*it_++);
+		itl::erase(object, *it_++);
 
     return object; 
 }
 
+//------------------------------------------------------------------------------
+//- 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
@@ -584,8 +811,6 @@
 //------------------------------------------------------------------------------
 //- Intersection add_intersection<IntervalMaps> for key_types
 //------------------------------------------------------------------------------
-
-//CL? JODO
 template<class Type, class OperandT>
 typename enable_if<mpl::and_< is_total<Type>
                             , is_interval_map_fragment_type_of<OperandT, Type> >, void>::type
@@ -599,10 +824,7 @@
 typename enable_if<mpl::and_< mpl::not_<is_total<Type> >, is_interval_map<Type> >, void>::type
 add_intersection(Type& section, const Type& object, const typename Type::element_type& operand)
 {
-    typedef typename Type::segment_type  segment_type;
-    typedef typename Type::interval_type interval_type;
-    add_intersection(section, object, 
-                     segment_type(interval_type(operand.key), operand.data));
+    add_intersection(section, object, make_segment<Type>(operand));
 }
 
 template<class Type>
@@ -757,8 +979,11 @@
 //------------------------------------------------------------------------------
 //- intersects
 //------------------------------------------------------------------------------
+//------------------------------------------------------------------------------
+//- intersects<Interval_Container> key_types
+//------------------------------------------------------------------------------
 template<class Type, class AssociateT>
-typename enable_if<mpl::and_< is_interval_set<Type>
+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)
@@ -767,8 +992,8 @@
 }
 
 template<class Type, class AssociateT>
-typename enable_if<mpl::and_< is_interval_set<Type>
-                            , is_same<AssociateT, segment_type_of<Type> > >, 
+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)
 {
@@ -776,6 +1001,41 @@
 }
 
 //------------------------------------------------------------------------------
+//- 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)); 
+}
+
+//------------------------------------------------------------------------------
 
 #ifdef BOOST_MSVC 
 #pragma warning(push)
@@ -801,7 +1061,7 @@
     typename RightT::const_iterator it_ = right_common_lower_;
     while(it_ != right_common_upper_)
     {
-        left.add_intersection(intersection, *it_++);
+        itl::add_intersection(intersection, left, *it_++);
         if(!itl::is_empty(intersection))
             return true;
     }
@@ -833,7 +1093,7 @@
     typename RightT::const_iterator it_ = right_common_lower_;
     while(it_ != right_common_upper_)
     {
-        left.add_intersection(intersection, RightT::key_value(it_++));
+        itl::add_intersection(intersection, left, RightT::key_value(it_++));
         if(!itl::is_empty(intersection))
             return true;
     }

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-10 11:08:03 EDT (Fri, 10 Sep 2010)
@@ -50,6 +50,14 @@
         :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
@@ -295,25 +303,6 @@
 
     //JODO remove lower, upper, first, last from the interface of all interval containers and docs
 
-    //CL .. /** Lower bound of the first interval */
-    //DomainT lower()const 
-    //{ return empty()? interval_type().lower() : (*(_map.begin())).first.lower(); }
-
-    ///** Upper bound of the last interval */
-    //DomainT upper()const 
-    //{ return empty()? interval_type().upper() : (*(_map.rbegin())).first.upper(); }
-
-    ///** Smallest element of the map (wrt. the partial ordering on DomainT).
-    //    first() does not exist for continuous datatypes and open interval 
-    //    bounds. */
-    //DomainT first()const { return (*(_map.begin())).first.first(); }
-
-    ///** Largest element of the map (wrt. the partial ordering on DomainT).
-    //    last() does not exist for continuous datatypes and open interval
-    //    bounds. */
-    //DomainT last()const { return (*(_map.rbegin())).first.last(); }
-
-
     //==========================================================================
     //= Selection
     //==========================================================================
@@ -359,14 +348,12 @@
     {
         return itl::add(*that(), key_value_pair);
     }
-    //CL { return add( value_type(interval_type(key_value_pair.key), key_value_pair.data) ); }
 
     /** Addition of an interval value pair to the map. */
     SubType& add(const segment_type& interval_value_pair) 
     {
         return itl::add(*that(), interval_value_pair);
     }
-    //CL { that()->template add_<codomain_combine>(interval_value_pair); return *that(); }
 
     /** Addition of an interval value pair \c interval_value_pair to the map. 
         Iterator \c prior_ is a hint to the position \c interval_value_pair can be 
@@ -375,7 +362,6 @@
     {
         return itl::add(*that(), prior_, interval_value_pair);
     }
-    //CL { return that()->template add_<codomain_combine>(prior_, interval_value_pair); }
 
     //==========================================================================
     //= Subtraction
@@ -396,19 +382,13 @@
     /** Subtraction of a key value pair from the map */
     SubType& subtract(const element_type& key_value_pair)
     { 
-        return subtract( value_type(interval_type(key_value_pair.key), 
-                                                  key_value_pair.data) ); 
+        return itl::subtract(*that(), key_value_pair);
     }
 
     /** Subtraction of an interval value pair from the map. */
     SubType& subtract(const segment_type& interval_value_pair)
     {
-        if(mpl::and_<is_total<type>, has_inverse<codomain_type> >::value)
-            that()->template add_<inverse_codomain_combine>(interval_value_pair); 
-        else 
-            that()->template subtract_<inverse_codomain_combine>(interval_value_pair); 
-    
-        return *that();
+        return itl::subtract(*that(), interval_value_pair);
     }
 
     //==========================================================================
@@ -420,41 +400,34 @@
 
     /** Insertion of a \c key_value_pair into the map. */
     SubType& insert(const element_type& key_value_pair) 
-    { 
-        that()->insert(value_type(interval_type(key_value_pair.key), 
-                                                key_value_pair.data)); 
-        return *that();
+    {
+        return itl::insert(*that(), key_value_pair);
     }
 
     /** Insertion of an \c interval_value_pair into the map. */
     SubType& insert(const segment_type& interval_value_pair)
     { 
-        that()->insert_(interval_value_pair); 
-        return *that(); 
+        return itl::insert(*that(), interval_value_pair);
     }
 
     /** Insertion of an \c interval_value_pair into the map. Iterator \c prior_. 
         serves as a hint to insert after the element \c prior point to. */
-    iterator insert(iterator prior_, const segment_type& interval_value_pair)
+    iterator insert(iterator prior, const segment_type& interval_value_pair)
     { 
-        return that()->insert_(prior_, interval_value_pair);
+        return itl::insert(*that(), prior, interval_value_pair);
     }
 
     /** With <tt>key_value_pair = (k,v)</tt> set value \c v for key \c k */
     SubType& set(const element_type& key_value_pair) 
     { 
-        that()->set(value_type(interval_type(key_value_pair.key), 
-                                             key_value_pair.data)); 
-        return *that();
+        return itl::set_at(*that(), key_value_pair);
     }
 
     /** With <tt>interval_value_pair = (I,v)</tt> set value \c v 
         for all keys in interval \c I in the map. */
     SubType& set(const segment_type& interval_value_pair)
     { 
-        erase(interval_value_pair.first); 
-        that()->insert_(interval_value_pair); 
-        return *that(); 
+        return itl::set_at(*that(), interval_value_pair);
     }
 
 
@@ -462,54 +435,12 @@
     //= Erasure
     //==========================================================================
 
-    /** Erase a \c key_value_pair from the map. */
-    SubType& erase(const element_type& key_value_pair) 
-    { 
-        that()->erase_(value_type(interval_type(key_value_pair.key), key_value_pair.data));
-        return *that();
-    }
-
-
-    /** Erase an \c interval_value_pair from the map. */
-    SubType& erase(const segment_type& interval_value_pair)
-    { that()->erase_(interval_value_pair); return *that(); }
-
-
-    /** Erase a key value pair for \c key. */
-    SubType& erase(const domain_type& key) 
-    { erase(interval_type(key)); return *that(); }
-
-
-    /** Erase all value pairs within the range of the 
-        interval <tt>inter_val</tt> from the map.   */
-    SubType& erase(const interval_type& inter_val);
-
-    /** Erase all value pairs for a set of intervals. */
-    template<class SetSubType>
-    SubType& erase(const interval_base_set<SetSubType,DomainT,Compare,Interval,Alloc>& operand)
+    template<class CoType>
+    SubType& erase(const CoType& operand) 
     {
-        typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> operand_type;
-
-        if(itl::is_empty(operand))
-            return *that();
-
-        typename operand_type::const_iterator common_lwb;
-        typename operand_type::const_iterator common_upb;
-
-        if(!Set::common_range(common_lwb, common_upb, operand, *this))
-            return *that();
-
-        typename operand_type::const_iterator it_ = common_lwb;
-        while(it_ != common_upb)
-            erase(*it_++);
-
-        return *that(); 
+        return itl::erase(*that(), operand);
     }
 
-
-    /** Erase all value pairs from \c *this map that are elements of map \eraser */
-    SubType& erase(const interval_base_map& eraser);
-
     /** Erase all value pairs within the range of the interval that iterator 
         \c position points to. */
     void erase(iterator position){ _map.erase(position); }
@@ -524,106 +455,34 @@
     //==========================================================================
     //= Intersection
     //==========================================================================
-
-    /** The intersection of \c key in \c *this map is added to \c section.
-        This can also be used to find \c key in \c *this map */
-    void add_intersection(interval_base_map& section, const domain_type& key)const
-    { add_intersection(section, interval_type(key)); }
-
-    /** The intersection of \c key_value_pair and \c *this map is added to \c section. */
-    void add_intersection(interval_base_map& section, const element_type& key_value_pair)const
-    { add_intersection(section, value_type(interval_type(key_value_pair.key), key_value_pair.data)); }
-
-    /** The intersection of \c interval_value_pair and \c *this map is added to \c section. */
-    void add_intersection(interval_base_map& section, const segment_type& interval_value_pair)const;
-
-    /** The intersection of \c inter_val with \c *this map is added to \c section. */
-    void add_intersection(interval_base_map& section, const interval_type& inter_val)const;
-
-    /** The intersection of set \c sectant with \c *this map is added to \c section. */
-    template
-    <
-        template
-        <class DomT, ITL_COMPARE Comp, ITL_INTERVAL2(ITL_COMPARE) Interv, ITL_ALLOC Allc>
-        class IntervalSet
-    >
-    void add_intersection
-    (
-              interval_base_map& section, 
-        const IntervalSet<DomainT,Compare,Interval,Alloc>& sectant
-    )const
-    {
-        typedef IntervalSet<DomainT,Compare,Interval,Alloc> sectant_type;
-        if(itl::is_empty(sectant)) 
-            return;
-
-        typename sectant_type::const_iterator common_lwb;
-        typename sectant_type::const_iterator common_upb;
-        if(!Set::common_range(common_lwb, common_upb, sectant, *this))
-            return;
-
-        typename sectant_type::const_iterator it_ = common_lwb;
-        while(it_ != common_upb)
-            add_intersection(section, *it_++);
-    }
-
-
-    /** The intersection of map \c sectant with \c *this map is added to \c section. */
-    template
-    <
-        template
-        <    
-            class DomT, class CodomT, class Trts, 
-            ITL_COMPARE Comp, ITL_COMBINE Combi, ITL_SECTION Sect,
-            ITL_INTERVAL2(ITL_COMPARE) Interv, ITL_ALLOC Allc
-        >
-        class IntervalMap
-    >
-    void add_intersection
-    (
-        interval_base_map& intersection,
-        const IntervalMap<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>& sectant
-    )const;
-
-
     /** Returns \c true, if element \c key is found in \c *this map.
         Complexity: logarithmic. */
     bool intersects(const domain_type& key)const
     {
-        return contains(key);
+		return itl::intersects(*that(), key);
     }
 
     /** Returns \c true, if \c inter_val intersects with \c *this map.
         Complexity: Logarithmic in iterative size. */
     bool intersects(const interval_type& inter_val)const
     { 
-        if(Traits::is_total)
-            return true;
-        std::pair<const_iterator,const_iterator> overlap = equal_range(inter_val);
-        return overlap.first == overlap.second;
+		return itl::intersects(*that(), inter_val);
     }
 
     /** Returns \c true, if \c key_value_pair is found in \c *this map.
         Complexity: logarithmic. */
     bool intersects(const element_type& key_value_pair)const
     { 
-        return intersects(segment_type(interval_type(key_value_pair.key), key_value_pair.data));
+		return itl::intersects(*that(), key_value_pair);
     }
 
     /** Returns \c true, if \c interval_value_pair intersects with \c *this map:
         Complexity: Linear in iterative_size. */
     bool intersects(const segment_type& interval_value_pair)const
     {
-        if(traits::is_total)
-            return true;
-
-        type intersection;
-        add_intersection(intersection, interval_value_pair);
-        return !itl::is_empty(intersection); 
+		return itl::intersects(*that(), interval_value_pair);
     }
 
-
-
     //==========================================================================
     //= Symmetric difference
     //==========================================================================
@@ -842,171 +701,6 @@
 } ;
 
 
-/*CL
-//==============================================================================
-//= Containedness
-//==============================================================================
-
-template 
-<
-    class SubType,
-    class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE)  Interval, ITL_ALLOC Alloc
->
-bool interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::contains(const typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-               ::segment_type& sub_segment)const
-{
-    return Interval_Map::contains(*this, sub_segment);
-}
-*/
-
-//==============================================================================
-//= Size
-//==============================================================================
-/*CL
-template 
-<
-    class SubType, class DomainT, class CodomainT, class Traits, 
-    ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, 
-    ITL_INTERVAL(ITL_COMPARE)  Interval, ITL_ALLOC Alloc
->
-typename interval_base_map<SubType,DomainT,CodomainT,Traits,
-                           Compare,Combine,Section,Interval,Alloc>::difference_type 
-interval_base_map<SubType,DomainT,CodomainT,Traits,
-                  Compare,Combine,Section,Interval,Alloc>::length()const
-{
-    difference_type length = neutron<difference_type>::value();
-    const_FOR_IMPLMAP(it_)
-        length += itl::length(it_->first);
-    return length;
-}
-*/
-//==============================================================================
-//= Intersection
-//==============================================================================
-
-template 
-<
-    class SubType,
-    class DomainT, class CodomainT, class Traits, 
-    ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, 
-    ITL_INTERVAL(ITL_COMPARE)  Interval, ITL_ALLOC Alloc
->
-    template
-    <
-        template
-        <    
-            class DomT, class CodomT, class Trts, 
-            ITL_COMPARE Comp, ITL_COMBINE Combi, ITL_SECTION Sect,
-            ITL_INTERVAL2(ITL_COMPARE) Interv, ITL_ALLOC Allc
-        >
-        class IntervalMap
-    >
-void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::add_intersection
-(
-    interval_base_map& intersection,
-    const IntervalMap<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>& sectant
-)const
-{
-    typedef IntervalMap<DomainT,CodomainT,
-                        Traits,Compare,Combine,Section,Interval,Alloc> sectant_type;
-
-    if(Traits::is_total)
-    {
-        intersection = *this;
-        intersection += sectant;
-    }
-    else
-    {
-        if(sectant.empty()) 
-            return;
-        typename sectant_type::const_iterator common_lwb;
-        typename sectant_type::const_iterator common_upb;
-        if(!Set::common_range(common_lwb, common_upb, sectant, *this))
-            return;
-        typename sectant_type::const_iterator it_ = common_lwb;
-        while(it_ != common_upb)
-            add_intersection(intersection, *it_++);
-    }
-}
-
-template 
-<
-    class SubType,
-    class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE)  Interval, ITL_ALLOC Alloc
->
-void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::add_intersection(interval_base_map& section, 
-                    const typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-                    ::segment_type& sectant)const
-{
-    if(Traits::is_total)
-    {
-        section = *this;
-        section.add(sectant);
-    }
-    else
-    {
-        interval_type sectant_interval = sectant.first;
-        if(itl::is_empty(sectant_interval)) 
-            return;
-
-        const_iterator first_ = _map.lower_bound(sectant_interval);
-        const_iterator end_   = _map.upper_bound(sectant_interval);
-
-        const_iterator it_;
-        iterator prior_ = section.end();
-
-        if(has_set_semantics<CodomainT>::value)
-            for(it_=first_; it_ != end_; it_++) 
-            {
-                interval_type common_interval = it_->first & sectant_interval; 
-                if(!itl::is_empty(common_interval))
-                {
-                    section.that()->add(value_type(common_interval, it_->second));
-                    section.that()->template _add<codomain_intersect>(value_type(common_interval, sectant.second)); 
-                }
-            }
-        else
-            for(it_=first_; it_ != end_; it_++) 
-            {
-                interval_type common_interval = it_->first & sectant_interval; 
-                if(!itl::is_empty(common_interval))
-                {
-                    section.that()->add(value_type(common_interval, it_->second) );
-                    section.that()->template _add<codomain_combine>(value_type(common_interval, sectant.second));
-                }
-            }
-
-    }
-}
-
-
-template 
-<
-    class SubType,
-    class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE)  Interval, ITL_ALLOC Alloc
->
-void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::add_intersection(interval_base_map& section, 
-                    const typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-                    ::interval_type& sectant_interval)const
-{
-    if(itl::is_empty(sectant_interval)) 
-        return;
-
-    typename ImplMapT::const_iterator first_ = _map.lower_bound(sectant_interval);
-    typename ImplMapT::const_iterator end_   = _map.upper_bound(sectant_interval);
-
-    iterator prior_ = section.end();
-    for(typename ImplMapT::const_iterator it_=first_; it_ != end_; it_++) 
-    {
-        interval_type common_interval = it_->first & sectant_interval; 
-        if(!itl::is_empty(common_interval))
-            prior_ = section.that()->gap_insert<codomain_combine>(prior_, common_interval, it_->second );
-    }
-}
 
 //==============================================================================
 //= Symmetric difference
@@ -1232,75 +926,6 @@
     class SubType,
     class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE)  Interval, ITL_ALLOC Alloc
 >
-inline SubType& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::erase(const interval_type& minuend)
-{
-    if(itl::is_empty(minuend)) 
-        return *that();
-
-    iterator first_ = _map.lower_bound(minuend);
-    if(first_==_map.end()) 
-        return *that();
-    iterator end_   = _map.upper_bound(minuend);
-    if(first_==end_  )
-        return *that();
-
-    iterator last_  = end_; --last_;
-
-    interval_type left_resid  = right_subtract(first_->first, minuend);
-    interval_type right_resid =  left_subtract(last_ ->first, minuend);
-
-    if(first_ == last_ )
-        if(!itl::is_empty(left_resid))
-        {
-            const_cast<interval_type&>(first_->first) = left_resid;
-            if(!itl::is_empty(right_resid))
-                this->_map.insert(first_, value_type(right_resid, first_->second));
-        }
-        else if(!itl::is_empty(right_resid))
-            const_cast<interval_type&>(first_->first) = left_subtract(first_->first, minuend);
-        else
-            this->_map.erase(first_);
-    else
-    {   //            [-------- minuend ---------)
-        // [left_resid   fst)   . . . .    [lst  right_resid)
-        iterator second_= first_; ++second_;
-
-        iterator start_ = itl::is_empty(left_resid)? first_: second_;
-        iterator stop_  = itl::is_empty(right_resid)? end_  : last_ ;
-        this->_map.erase(start_, stop_); //erase [start_, stop_)
-
-        if(!itl::is_empty(left_resid))
-            const_cast<interval_type&>(first_->first) = left_resid;
-
-        if(!itl::is_empty(right_resid))
-            const_cast<interval_type&>(last_ ->first) = right_resid;
-    }
-    return *that();
-}
-
-
-template 
-<
-    class SubType,
-    class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE)  Interval, ITL_ALLOC Alloc
->
-SubType& 
-interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
-    ::erase(const interval_base_map& erasure)
-{
-    ITL_const_FORALL(typename interval_base_map, value_pair_, erasure)
-        that()->erase_(*value_pair_);
-
-    return *that();
-}
-
-
-template 
-<
-    class SubType,
-    class DomainT, class CodomainT, class Traits, ITL_COMPARE Compare, ITL_COMBINE Combine, ITL_SECTION Section, ITL_INTERVAL(ITL_COMPARE)  Interval, ITL_ALLOC Alloc
->
     template<class Predicate>
 SubType& 
 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>

Added: sandbox/itl/boost/itl/type_traits/element_type_of.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/type_traits/element_type_of.hpp	2010-09-10 11:08:03 EDT (Fri, 10 Sep 2010)
@@ -0,0 +1,53 @@
+/*-----------------------------------------------------------------------------+    
+Copyright (c) 2008-2009: Joachim Faulhaber
++------------------------------------------------------------------------------+
+   Distributed under the Boost Software License, Version 1.0.
+      (See accompanying file LICENCE.txt or copy at
+           http://www.boost.org/LICENSE_1_0.txt)
++-----------------------------------------------------------------------------*/
+#ifndef BOOST_ITL_TYPE_TRAITS_ELEMENT_TYPE_OF_HPP_JOFA_100902
+#define BOOST_ITL_TYPE_TRAITS_ELEMENT_TYPE_OF_HPP_JOFA_100902
+
+#include <boost/mpl/has_xxx.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/itl/type_traits/no_type.hpp>
+
+namespace boost{ namespace itl
+{
+    namespace detail
+    {
+        BOOST_MPL_HAS_XXX_TRAIT_DEF(element_type)
+    }
+
+    template <class Type>
+    struct has_element_type 
+      : mpl::bool_<detail::has_element_type<Type>::value>
+    {};
+
+    template <class Type, bool has_element_type> 
+	struct get_element_type;
+
+    template <class Type>
+	struct get_element_type<Type, false>
+    {
+		typedef no_type type;
+    };
+
+    template <class Type>
+	struct get_element_type<Type, true>
+    {
+		typedef typename Type::element_type type;
+    };
+
+    template <class Type>
+	struct element_type_of
+    {
+		typedef typename 
+			get_element_type<Type, has_element_type<Type>::value>::type type;
+    };
+
+}} // namespace boost itl
+
+#endif
+
+

Added: sandbox/itl/boost/itl/type_traits/interval_type_of.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/type_traits/interval_type_of.hpp	2010-09-10 11:08:03 EDT (Fri, 10 Sep 2010)
@@ -0,0 +1,53 @@
+/*-----------------------------------------------------------------------------+    
+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_TYPE_TRAITS_INTERVAL_TYPE_OF_HPP_JOFA_100910
+#define BOOST_ITL_TYPE_TRAITS_INTERVAL_TYPE_OF_HPP_JOFA_100910
+
+#include <boost/mpl/has_xxx.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/itl/type_traits/no_type.hpp>
+
+namespace boost{ namespace itl
+{
+    namespace detail
+    {
+        BOOST_MPL_HAS_XXX_TRAIT_DEF(interval_type)
+    }
+
+    template <class Type>
+    struct has_interval_type 
+      : mpl::bool_<detail::has_interval_type<Type>::value>
+    {};
+
+    template <class Type, bool has_interval_type> 
+	struct get_interval_type;
+
+    template <class Type>
+	struct get_interval_type<Type, false>
+    {
+		typedef no_type type;
+    };
+
+    template <class Type>
+	struct get_interval_type<Type, true>
+    {
+		typedef typename Type::interval_type type;
+    };
+
+    template <class Type>
+	struct interval_type_of
+    {
+		typedef typename 
+			get_interval_type<Type, has_interval_type<Type>::value>::type type;
+    };
+
+}} // namespace boost itl
+
+#endif
+
+