Chris@16: /*-----------------------------------------------------------------------------+
Chris@16: Copyright (c) 2007-2011: Joachim Faulhaber
Chris@16: +------------------------------------------------------------------------------+
Chris@16:    Distributed under the Boost Software License, Version 1.0.
Chris@16:       (See accompanying file LICENCE.txt or copy at
Chris@16:            http://www.boost.org/LICENSE_1_0.txt)
Chris@16: +-----------------------------------------------------------------------------*/
Chris@16: #ifndef BOOST_ICL_MAP_HPP_JOFA_070519
Chris@16: #define BOOST_ICL_MAP_HPP_JOFA_070519
Chris@16: 
Chris@16: #include <boost/icl/impl_config.hpp>
Chris@16: 
Chris@16: #if defined(ICL_USE_BOOST_MOVE_IMPLEMENTATION)
Chris@16: #   include <boost/container/map.hpp>
Chris@16: #   include <boost/container/set.hpp>
Chris@16: #elif defined(ICL_USE_STD_IMPLEMENTATION)
Chris@16: #   include <map>
Chris@16: #   include <set>
Chris@16: #else // Default for implementing containers
Chris@16: #   include <map>
Chris@16: #   include <set>
Chris@16: #endif
Chris@16: 
Chris@16: #include <string>
Chris@16: #include <boost/type_traits/ice.hpp>
Chris@16: #include <boost/call_traits.hpp> 
Chris@16: #include <boost/icl/detail/notate.hpp>
Chris@16: #include <boost/icl/detail/design_config.hpp>
Chris@16: #include <boost/icl/detail/concept_check.hpp>
Chris@16: #include <boost/icl/detail/on_absorbtion.hpp>
Chris@16: #include <boost/icl/type_traits/is_map.hpp>
Chris@16: #include <boost/icl/type_traits/absorbs_identities.hpp>
Chris@16: #include <boost/icl/type_traits/is_total.hpp>
Chris@16: #include <boost/icl/type_traits/is_element_container.hpp>
Chris@16: #include <boost/icl/type_traits/has_inverse.hpp>
Chris@16: #include <boost/icl/type_traits/to_string.hpp>
Chris@16: 
Chris@16: #include <boost/icl/associative_element_container.hpp>
Chris@16: #include <boost/icl/functors.hpp>
Chris@16: 
Chris@16: namespace boost{namespace icl
Chris@16: {
Chris@16: 
Chris@16: struct partial_absorber
Chris@16: {
Chris@16:     enum { absorbs_identities = true };
Chris@16:     enum { is_total = false };
Chris@16: };
Chris@16: 
Chris@16: template<> 
Chris@16: inline std::string type_to_string<partial_absorber>::apply() { return "@0"; }
Chris@16: 
Chris@16: struct partial_enricher
Chris@16: {
Chris@16:     enum { absorbs_identities = false };
Chris@16:     enum { is_total = false };
Chris@16: };
Chris@16: 
Chris@16: template<> 
Chris@16: inline std::string type_to_string<partial_enricher>::apply() { return "e0"; }
Chris@16: 
Chris@16: struct total_absorber
Chris@16: {
Chris@16:     enum { absorbs_identities = true };
Chris@16:     enum { is_total = true };
Chris@16: };
Chris@16: 
Chris@16: template<> 
Chris@16: inline std::string type_to_string<total_absorber>::apply() { return "^0"; }
Chris@16: 
Chris@16: struct total_enricher
Chris@16: {
Chris@16:     enum { absorbs_identities = false };
Chris@16:     enum { is_total = true };
Chris@16: };
Chris@16: 
Chris@16: template<> 
Chris@16: inline std::string type_to_string<total_enricher>::apply() { return "e^0"; }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: /** \brief Addable, subractable and intersectable maps */
Chris@16: template 
Chris@16: <
Chris@16:     typename DomainT, 
Chris@16:     typename CodomainT, 
Chris@16:     class Traits = icl::partial_absorber,
Chris@16:     ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
Chris@16:     ICL_COMBINE Combine = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
Chris@16:     ICL_SECTION Section = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT), 
Chris@16:     ICL_ALLOC   Alloc   = std::allocator 
Chris@16: >
Chris@16: class map: private ICL_IMPL_SPACE::map<DomainT, CodomainT, ICL_COMPARE_DOMAIN(Compare,DomainT), 
Chris@16:                                        Alloc<std::pair<const DomainT, CodomainT> > >
Chris@16: {
Chris@16: public:
Chris@16:     typedef Alloc<typename std::pair<const DomainT, CodomainT> >  allocator_type;
Chris@16: 
Chris@16:     typedef typename icl::map<DomainT,CodomainT,Traits, Compare,Combine,Section,Alloc> type;
Chris@16:     typedef typename ICL_IMPL_SPACE::map<DomainT, CodomainT, ICL_COMPARE_DOMAIN(Compare,DomainT),
Chris@16:                                          allocator_type>   base_type;
Chris@16: 
Chris@16:     typedef Traits traits;
Chris@16: 
Chris@16: public:
Chris@16:     typedef DomainT                                     domain_type;
Chris@16:     typedef typename boost::call_traits<DomainT>::param_type domain_param;
Chris@16:     typedef DomainT                                     key_type;
Chris@16:     typedef CodomainT                                   codomain_type;
Chris@16:     typedef CodomainT                                   mapped_type;
Chris@16:     typedef CodomainT                                   data_type;
Chris@16:     typedef std::pair<const DomainT, CodomainT>         element_type;
Chris@16:     typedef std::pair<const DomainT, CodomainT>         value_type;
Chris@16:     typedef ICL_COMPARE_DOMAIN(Compare,DomainT)         domain_compare;
Chris@16:     typedef ICL_COMBINE_CODOMAIN(Combine,CodomainT)     codomain_combine;
Chris@16:     typedef domain_compare                              key_compare;
Chris@16:     typedef ICL_COMPARE_DOMAIN(Compare,element_type)    element_compare;
Chris@16:     typedef typename inverse<codomain_combine >::type   inverse_codomain_combine;
Chris@16:     typedef typename mpl::if_
Chris@16:         <has_set_semantics<codomain_type>
Chris@16:         , ICL_SECTION_CODOMAIN(Section,CodomainT)     
Chris@16:         , codomain_combine
Chris@16:         >::type                                         codomain_intersect;
Chris@16:     typedef typename inverse<codomain_intersect>::type  inverse_codomain_intersect;
Chris@16:     typedef typename base_type::value_compare           value_compare;
Chris@16: 
Chris@16:     typedef typename ICL_IMPL_SPACE::set<DomainT, domain_compare, Alloc<DomainT> > set_type;
Chris@16:     typedef set_type                                       key_object_type;
Chris@16: 
Chris@16: 
Chris@16:     BOOST_STATIC_CONSTANT(bool, _total   = (Traits::is_total));
Chris@16:     BOOST_STATIC_CONSTANT(bool, _absorbs = (Traits::absorbs_identities));
Chris@16:     BOOST_STATIC_CONSTANT(bool, 
Chris@16:         total_invertible = (mpl::and_<is_total<type>, has_inverse<codomain_type> >::value));
Chris@16: 
Chris@16:     typedef on_absorbtion<type,codomain_combine,Traits::absorbs_identities> 
Chris@16:                                                         on_identity_absorbtion;
Chris@16: 
Chris@16: public:
Chris@16:     typedef typename base_type::pointer                 pointer;
Chris@16:     typedef typename base_type::const_pointer           const_pointer;
Chris@16:     typedef typename base_type::reference               reference;
Chris@16:     typedef typename base_type::const_reference         const_reference;
Chris@16:     typedef typename base_type::iterator                iterator;
Chris@16:     typedef typename base_type::const_iterator          const_iterator;
Chris@16:     typedef typename base_type::size_type               size_type;
Chris@16:     typedef typename base_type::difference_type         difference_type;
Chris@16:     typedef typename base_type::reverse_iterator        reverse_iterator;
Chris@16:     typedef typename base_type::const_reverse_iterator  const_reverse_iterator;
Chris@16: 
Chris@16: public:
Chris@16:     BOOST_STATIC_CONSTANT(bool, 
Chris@16:         is_total_invertible = (   Traits::is_total 
Chris@16:                                && has_inverse<codomain_type>::value));
Chris@16: 
Chris@16:     BOOST_STATIC_CONSTANT(int, fineness = 4); 
Chris@16: 
Chris@16: public:
Chris@16:     //==========================================================================
Chris@16:     //= Construct, copy, destruct
Chris@16:     //==========================================================================
Chris@16:     map()
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
Chris@16:     }
Chris@16: 
Chris@16:     map(const key_compare& comp): base_type(comp){}
Chris@16: 
Chris@16:     template <class InputIterator>
Chris@16:     map(InputIterator first, InputIterator past)
Chris@16:         : base_type(first,past){} 
Chris@16: 
Chris@16:     template <class InputIterator>
Chris@16:     map(InputIterator first, InputIterator past, const key_compare& comp)
Chris@16:         : base_type(first,past,comp) 
Chris@16:     {}
Chris@16: 
Chris@16:     map(const map& src)
Chris@16:         : base_type(src)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
Chris@16:     }
Chris@16: 
Chris@16:     explicit map(const element_type& key_value_pair): base_type::map()
Chris@16:     { 
Chris@16:         insert(key_value_pair); 
Chris@16:     }
Chris@16: 
Chris@16: #   ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
Chris@16:     //==========================================================================
Chris@16:     //= Move semantics
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     map(map&& src)
Chris@16:         : base_type(boost::move(src))
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
Chris@16:     }
Chris@16: 
Chris@101:     map& operator = (map src) 
Chris@101:     { 
Chris@101:         base_type::operator=(boost::move(src));
Chris@101:         return *this; 
Chris@101:     } 
Chris@101:     //==========================================================================
Chris@101: #   else
Chris@101: 
Chris@101:     map& operator = (const map& src) 
Chris@16:     { 
Chris@16:         base_type::operator=(src);
Chris@16:         return *this; 
Chris@16:     } 
Chris@101: 
Chris@16: #   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
Chris@16: 
Chris@16:     void swap(map& src) { base_type::swap(src); }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     using base_type::empty;
Chris@16:     using base_type::clear;
Chris@16: 
Chris@16:     using base_type::begin;
Chris@16:     using base_type::end;
Chris@16:     using base_type::rbegin;
Chris@16:     using base_type::rend;
Chris@16: 
Chris@16:     using base_type::size;
Chris@16:     using base_type::max_size;
Chris@16: 
Chris@16:     using base_type::key_comp;
Chris@16:     using base_type::value_comp;
Chris@16: 
Chris@16:     using base_type::erase;
Chris@16:     using base_type::find;
Chris@16:     using base_type::count;
Chris@16: 
Chris@16:     using base_type::lower_bound;
Chris@16:     using base_type::upper_bound;
Chris@16:     using base_type::equal_range;
Chris@16: 
Chris@16:     using base_type::operator[];
Chris@16: 
Chris@16: public:
Chris@16:     //==========================================================================
Chris@16:     //= Containedness
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     template<class SubObject>
Chris@16:     bool contains(const SubObject& sub)const 
Chris@16:     { return icl::contains(*this, sub); }
Chris@16: 
Chris@16:     bool within(const map& super)const 
Chris@16:     { return icl::contains(super, *this); }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Size
Chris@16:     //==========================================================================
Chris@16:     /** \c iterative_size() yields the number of elements that is visited
Chris@16:         throu complete iteration. For interval sets \c iterative_size() is
Chris@16:         different from \c size(). */
Chris@16:     std::size_t iterative_size()const { return base_type::size(); }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Selection
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     /** Total select function. */
Chris@16:     codomain_type operator()(const domain_type& key)const
Chris@16:     {
Chris@16:         const_iterator it = find(key); 
Chris@16:         return it==end() ? identity_element<codomain_type>::value()
Chris@16:                          : it->second;
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Addition
Chris@16:     //==========================================================================
Chris@16:     /** \c add inserts \c value_pair into the map if it's key does 
Chris@16:         not exist in the map.    
Chris@16:         If \c value_pairs's key value exists in the map, it's data
Chris@16:         value is added to the data value already found in the map. */
Chris@16:     map& add(const value_type& value_pair) 
Chris@16:     { 
Chris@16:         return _add<codomain_combine>(value_pair); 
Chris@16:     }
Chris@16: 
Chris@16:     /** \c add add \c value_pair into the map using \c prior as a hint to
Chris@16:         insert \c value_pair after the position \c prior is pointing to. */
Chris@16:     iterator add(iterator prior, const value_type& value_pair) 
Chris@16:     { 
Chris@16:         return _add<codomain_combine>(prior, value_pair); 
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Subtraction
Chris@16:     //==========================================================================
Chris@16:     /** If the \c value_pair's key value is in the map, it's data value is
Chris@16:         subtraced from the data value stored in the map. */
Chris@16:     map& subtract(const element_type& value_pair)
Chris@16:     {
Chris@16:         on_invertible<type, is_total_invertible>
Chris@16:             ::subtract(*this, value_pair);
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     map& subtract(const domain_type& key)
Chris@16:     {
Chris@16:         icl::erase(*this, key);
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Insertion, erasure
Chris@16:     //==========================================================================
Chris@16:     std::pair<iterator,bool> insert(const value_type& value_pair)
Chris@16:     {
Chris@16:         if(on_identity_absorbtion::is_absorbable(value_pair.second)) 
Chris@16:             return std::pair<iterator,bool>(end(),true);
Chris@16:         else
Chris@16:             return base_type::insert(value_pair);
Chris@16:     }
Chris@16:     
Chris@16:     iterator insert(iterator prior, const value_type& value_pair)
Chris@16:     {
Chris@16:         if(on_identity_absorbtion::is_absorbable(value_pair.second)) 
Chris@16:             return end();
Chris@16:         else
Chris@16:             return base_type::insert(prior, value_pair);
Chris@16:     }
Chris@16: 
Chris@16:     template<class Iterator>
Chris@16:     iterator insert(Iterator first, Iterator last)
Chris@16:     {
Chris@16:         iterator prior = end(), it = first;
Chris@16:         while(it != last)
Chris@16:             prior = this->insert(prior, *it++);
Chris@16:     }
Chris@16: 
Chris@16:     /** With <tt>key_value_pair = (k,v)</tt> set value \c v for key \c k */
Chris@16:     map& set(const element_type& key_value_pair)
Chris@16:     { 
Chris@16:         return icl::set_at(*this, key_value_pair);
Chris@16:     }
Chris@16: 
Chris@16:     /** erase \c key_value_pair from the map.
Chris@16:         Erase only if, the exact value content \c val is stored for the given key. */
Chris@16:     size_type erase(const element_type& key_value_pair)
Chris@16:     {
Chris@16:         return icl::erase(*this, key_value_pair); 
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Intersection
Chris@16:     //==========================================================================
Chris@16:     /** The intersection of \c key_value_pair and \c *this map is added to \c section. */
Chris@16:     void add_intersection(map& section, const element_type& key_value_pair)const
Chris@16:     {
Chris@16:         on_definedness<type, Traits::is_total>
Chris@16:             ::add_intersection(section, *this, key_value_pair);
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Symmetric difference
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     map& flip(const element_type& operand)
Chris@16:     {
Chris@16:         on_total_absorbable<type,_total,_absorbs>::flip(*this, operand);
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     template<class Combiner>
Chris@16:     map& _add(const element_type& value_pair);
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     iterator _add(iterator prior, const element_type& value_pair);
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     map& _subtract(const element_type& value_pair);
Chris@16: 
Chris@16:     template<class FragmentT>
Chris@16:     void total_add_intersection(type& section, const FragmentT& fragment)const
Chris@16:     {
Chris@16:         section += *this;
Chris@16:         section.add(fragment);
Chris@16:     }
Chris@16: 
Chris@16:     void partial_add_intersection(type& section, const element_type& operand)const
Chris@16:     {
Chris@16:         const_iterator it_ = find(operand.first);
Chris@16:         if(it_ != end())
Chris@16:         {
Chris@16:             section.template _add<codomain_combine  >(*it_);
Chris@16:             section.template _add<codomain_intersect>(operand); 
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16: private:
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     template<class Type, bool is_total_invertible>
Chris@16:     struct on_invertible;
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_invertible<Type, true>
Chris@16:     {
Chris@16:         typedef typename Type::element_type element_type;
Chris@16:         typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
Chris@16: 
Chris@16:         static void subtract(Type& object, const element_type& operand)
Chris@16:         { object.template _add<inverse_codomain_combine>(operand); }
Chris@16:     };
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_invertible<Type, false>
Chris@16:     {
Chris@16:         typedef typename Type::element_type element_type;
Chris@16:         typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
Chris@16: 
Chris@16:         static void subtract(Type& object, const element_type& operand)
Chris@16:         { object.template _subtract<inverse_codomain_combine>(operand); }
Chris@16:     };
Chris@16: 
Chris@16:     friend struct on_invertible<type, true>;
Chris@16:     friend struct on_invertible<type, false>;
Chris@16:     //--------------------------------------------------------------------------
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     template<class Type, bool is_total>
Chris@16:     struct on_definedness;
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_definedness<Type, true>
Chris@16:     {
Chris@16:         static void add_intersection(Type& section, const Type& object, 
Chris@16:                                      const element_type& operand)
Chris@16:         { object.total_add_intersection(section, operand); }
Chris@16:     };
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_definedness<Type, false>
Chris@16:     {
Chris@16:         static void add_intersection(Type& section, const Type& object, 
Chris@16:                                      const element_type& operand)
Chris@16:         { object.partial_add_intersection(section, operand); }
Chris@16:     };
Chris@16: 
Chris@16:     friend struct on_definedness<type, true>;
Chris@16:     friend struct on_definedness<type, false>;
Chris@16:     //--------------------------------------------------------------------------
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     template<class Type, bool has_set_semantics, bool absorbs_identities>
Chris@16:     struct on_codomain_model;
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_codomain_model<Type, false, false>
Chris@16:     {                // !codomain_is_set, !absorbs_identities
Chris@16:         static void subtract(Type&, typename Type::iterator it_, 
Chris@16:                               const typename Type::codomain_type& )
Chris@16:         { (*it_).second = identity_element<typename Type::codomain_type>::value(); }
Chris@16:     };
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_codomain_model<Type, false, true>
Chris@16:     {                // !codomain_is_set, absorbs_identities
Chris@16:         static void subtract(Type& object, typename Type::iterator       it_, 
Chris@16:                                      const typename Type::codomain_type&     )
Chris@16:         { object.erase(it_); }
Chris@16:     };
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_codomain_model<Type, true, false>
Chris@16:     {               // !codomain_is_set, !absorbs_identities
Chris@16:         typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
Chris@16:         static void subtract(Type&, typename Type::iterator       it_, 
Chris@16:                               const typename Type::codomain_type& co_value)
Chris@16:         { 
Chris@16:             inverse_codomain_intersect()((*it_).second, co_value); 
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_codomain_model<Type, true, true>
Chris@16:     {               // !codomain_is_set, absorbs_identities
Chris@16:         typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
Chris@16:         static void subtract(Type& object, typename Type::iterator       it_, 
Chris@16:                                      const typename Type::codomain_type& co_value)
Chris@16:         { 
Chris@16:             inverse_codomain_intersect()((*it_).second, co_value); 
Chris@16:             if((*it_).second == identity_element<codomain_type>::value())
Chris@16:                 object.erase(it_);
Chris@16:         }
Chris@16:     };
Chris@16:     //--------------------------------------------------------------------------
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     template<class Type, bool is_total, bool absorbs_identities>
Chris@16:     struct on_total_absorbable;
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_total_absorbable<Type, true, true>
Chris@16:     {
Chris@16:         typedef typename Type::element_type  element_type;
Chris@16:         static void flip(Type& object, const typename Type::element_type&)
Chris@16:         { icl::clear(object); }
Chris@16:     };
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_total_absorbable<Type, true, false>
Chris@16:     {
Chris@16:         typedef typename Type::element_type  element_type;
Chris@16:         typedef typename Type::codomain_type codomain_type;
Chris@16: 
Chris@16:         static void flip(Type& object, const element_type& operand)
Chris@16:         { 
Chris@16:             object.add(operand);
Chris@16:             ICL_FORALL(typename Type, it_, object)
Chris@16:                 (*it_).second = identity_element<codomain_type>::value();
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_total_absorbable<Type, false, true>
Chris@16:     {                         // !is_total, absorbs_identities
Chris@16:         typedef typename Type::element_type   element_type;
Chris@16:         typedef typename Type::codomain_type  codomain_type;
Chris@16:         typedef typename Type::iterator       iterator;
Chris@16:         typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
Chris@16: 
Chris@16:         static void flip(Type& object, const element_type& operand)
Chris@16:         {
Chris@16:             std::pair<iterator,bool> insertion = object.insert(operand);
Chris@16:             if(!insertion.second)
Chris@16:                 on_codomain_model<Type, has_set_semantics<codomain_type>::value, true>
Chris@16:                 ::subtract(object, insertion.first, operand.second);
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_total_absorbable<Type, false, false>
Chris@16:     {                         // !is_total  !absorbs_identities
Chris@16:         typedef typename Type::element_type   element_type;
Chris@16:         typedef typename Type::codomain_type  codomain_type;
Chris@16:         typedef typename Type::iterator       iterator;
Chris@16:         typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
Chris@16: 
Chris@16:         static void flip(Type& object, const element_type& operand)
Chris@16:         {
Chris@16:             std::pair<iterator,bool> insertion = object.insert(operand);
Chris@16:             if(!insertion.second)
Chris@16:                 on_codomain_model<Type, has_set_semantics<codomain_type>::value, false>
Chris@16:                 ::subtract(object, insertion.first, operand.second);
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     friend struct on_total_absorbable<type, true,  true >;
Chris@16:     friend struct on_total_absorbable<type, false, true >;
Chris@16:     friend struct on_total_absorbable<type, true,  false>;
Chris@16:     friend struct on_total_absorbable<type, false, false>;
Chris@16:     //--------------------------------------------------------------------------
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Addition<ElementMap>
Chris@16: //==============================================================================
Chris@16: template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
Chris@16:     template <class Combiner>
Chris@16: map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>&
Chris@16:     map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>
Chris@16:     ::_add(const element_type& addend)
Chris@16: {
Chris@16:     typedef typename on_absorbtion
Chris@16:         <type,Combiner,absorbs_identities<type>::value>::type on_absorbtion_;
Chris@16: 
Chris@16:     const codomain_type& co_val    = addend.second;
Chris@16:     if(on_absorbtion_::is_absorbable(co_val))
Chris@16:         return *this;
Chris@16: 
Chris@16:     std::pair<iterator,bool> insertion 
Chris@16:         = base_type::insert(value_type(addend.first, version<Combiner>()(co_val)));
Chris@16: 
Chris@16:     if(!insertion.second)
Chris@16:     {
Chris@16:         iterator it = insertion.first;
Chris@16:         Combiner()((*it).second, co_val);
Chris@16: 
Chris@16:         if(on_absorbtion_::is_absorbable((*it).second))
Chris@16:             erase(it);
Chris@16:     }
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
Chris@16:     template <class Combiner>
Chris@16: typename map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::iterator
Chris@16:     map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>
Chris@16:     ::_add(iterator prior_, const value_type& addend)
Chris@16: {
Chris@16:     typedef typename on_absorbtion
Chris@16:         <type,Combiner,absorbs_identities<type>::value>::type on_absorbtion_;
Chris@16: 
Chris@16:     const codomain_type& co_val    = addend.second;
Chris@16:     if(on_absorbtion_::is_absorbable(co_val))
Chris@16:         return end();
Chris@16: 
Chris@16:     iterator inserted_ 
Chris@16:         = base_type::insert(prior_, 
Chris@16:                             value_type(addend.first, Combiner::identity_element()));
Chris@16:     Combiner()((*inserted_).second, addend.second);
Chris@16: 
Chris@16:     if(on_absorbtion_::is_absorbable((*inserted_).second))
Chris@16:     {
Chris@16:         erase(inserted_);
Chris@16:         return end();
Chris@16:     }
Chris@16:     else
Chris@16:         return inserted_;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Subtraction<ElementMap>
Chris@16: //==============================================================================
Chris@16: template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
Chris@16:     template <class Combiner>
Chris@16: map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>&
Chris@16:     map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::_subtract(const value_type& minuend)
Chris@16: {
Chris@16:     typedef typename on_absorbtion
Chris@16:         <type,Combiner,absorbs_identities<type>::value>::type on_absorbtion_;
Chris@16: 
Chris@16:     iterator it_ = find(minuend.first);
Chris@16:     if(it_ != end())
Chris@16:     {
Chris@16:         Combiner()((*it_).second, minuend.second);
Chris@16:         if(on_absorbtion_::is_absorbable((*it_).second))
Chris@16:             erase(it_);
Chris@16:     }
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // type traits
Chris@16: //-----------------------------------------------------------------------------
Chris@16: template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
Chris@16: struct is_map<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> >
Chris@16: { 
Chris@16:     typedef is_map<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true); 
Chris@16: };
Chris@16: 
Chris@16: template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
Chris@16: struct has_inverse<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> >
Chris@16: { 
Chris@16:     typedef has_inverse<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value)); 
Chris@16: };
Chris@16: 
Chris@16: template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
Chris@16: struct absorbs_identities<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> >
Chris@16: { 
Chris@16:     typedef absorbs_identities type;
Chris@16:     BOOST_STATIC_CONSTANT(int, value = Traits::absorbs_identities); 
Chris@16: };
Chris@16: 
Chris@16: template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
Chris@16: struct is_total<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> >
Chris@16: { 
Chris@16:     typedef is_total type;
Chris@16:     BOOST_STATIC_CONSTANT(int, value = Traits::is_total); 
Chris@16: };
Chris@16: 
Chris@16: template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
Chris@16: struct type_to_string<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> >
Chris@16: {
Chris@16:     static std::string apply()
Chris@16:     {
Chris@16:         return "map<"+ type_to_string<DomainT>::apply()  + ","
Chris@16:                      + type_to_string<CodomainT>::apply() + ","
Chris@16:                      + type_to_string<Traits>::apply() +">"; 
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: }} // namespace icl boost
Chris@16: 
Chris@16: #endif // BOOST_ICL_MAP_HPP_JOFA_070519
Chris@16: