Chris@16: /*-----------------------------------------------------------------------------+    
Chris@16: Copyright (c) 2010-2010: 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_CONCEPT_ELEMENT_ASSOCIATOR_HPP_JOFA_100921
Chris@16: #define BOOST_ICL_CONCEPT_ELEMENT_ASSOCIATOR_HPP_JOFA_100921
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/icl/type_traits/is_associative_element_container.hpp>
Chris@16: #include <boost/icl/type_traits/is_key_container_of.hpp>
Chris@16: #include <boost/icl/type_traits/is_combinable.hpp>
Chris@16: #include <boost/icl/detail/subset_comparer.hpp>
Chris@16: #include <boost/icl/concept/element_set.hpp>
Chris@16: #include <boost/icl/concept/element_map.hpp>
Chris@16: 
Chris@16: namespace boost{ namespace icl
Chris@16: {
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Size
Chris@16: //==============================================================================
Chris@16: template<class Type> 
Chris@16: typename enable_if<is_element_container<Type>, std::size_t>::type
Chris@16: iterative_size(const Type& object)
Chris@16: { 
Chris@16:     return object.size(); 
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
Chris@16: size(const Type& object)
Chris@16: { 
Chris@16:     return icl::iterative_size(object); 
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
Chris@16: cardinality(const Type& object)
Chris@16: { 
Chris@16:     return icl::iterative_size(object); 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Containedness<ElementSet|ElementMap>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- bool within(c P&, c T&) T:{s}|{m} P:{e}|{i} fragment_types|key_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: /** Checks if a key is in the associative container */
Chris@16: template<class Type>
Chris@16: typename enable_if<is_associative_element_container<Type>, bool>::type
Chris@16: within(const typename Type::key_type& key, const Type& super)
Chris@16: { 
Chris@16:     return !(super.find(key) == super.end()); 
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- bool within(c P&, c T&) T:{s}|{m} P:{s'} fragment_types|key_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class SubT, class SuperT>
Chris@16: typename enable_if<mpl::and_< is_associative_element_container<SuperT> 
Chris@16:                             , is_key_container_of<SubT, SuperT> >,
Chris@16:                    bool>::type
Chris@16: within(const SubT& sub, const SuperT& super)
Chris@16: {
Chris@16:     if(icl::is_empty(sub))                return true;
Chris@16:     if(icl::is_empty(super))              return false;
Chris@16:     if(icl::size(super) < icl::size(sub)) return false;
Chris@16: 
Chris@16:     typename SubT::const_iterator common_lwb_;
Chris@16:     typename SubT::const_iterator common_upb_;
Chris@16:     if(!Set::common_range(common_lwb_, common_upb_, sub, super))
Chris@16:         return false;
Chris@16: 
Chris@16:     typename SubT::const_iterator sub_ = sub.begin();
Chris@16:     typename SuperT::const_iterator super_;
Chris@16:     while(sub_ != sub.end())
Chris@16:     {
Chris@16:         super_ = super.find(key_value<SubT>(sub_));
Chris@16:         if(super_ == super.end()) 
Chris@16:             return false;
Chris@16:         else if(!co_equal(sub_, super_, &sub, &super))
Chris@16:             return false;
Chris@16: 
Chris@16:         ++sub_;
Chris@16:     }
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- bool contains(c T&, c P&) T:{s}|{m} P:{e}|{i} fragment_types|key_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_associative_element_container<Type>, bool>::type
Chris@16: contains(const Type& super, const typename Type::key_type& key)
Chris@16: { 
Chris@16:     return icl::within(key, super); 
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- bool contains(c T&, c P&) T:{s}|{m} P:{s'} fragment_types|key_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class SubT, class SuperT>
Chris@16: typename enable_if<mpl::and_< is_associative_element_container<SuperT>
Chris@16:                             , is_key_container_of<SubT, SuperT> >,
Chris@16:                    bool>::type
Chris@16: contains(const SuperT& super, const SubT& sub)
Chris@16: { 
Chris@16:     return icl::within(sub, super); 
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Equivalences and Orderings
Chris@16: //==============================================================================
Chris@16: 
Chris@16: #ifdef BOOST_MSVC 
Chris@16: #pragma warning(push)
Chris@16: #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'
Chris@16: #endif                        // I do guarantee here that I am using the parameters correctly :)
Chris@16: 
Chris@16: /** Standard equality, which is lexicographical equality of the sets
Chris@16:     as sequences, that are given by their Compare order. */
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, bool>::type
Chris@16: operator == (const Type& left, const Type& right)
Chris@16: {
Chris@16:     return left.size() == right.size() 
Chris@16:         && std::equal(left.begin(), left.end(), right.begin());
Chris@16: }
Chris@16: 
Chris@16: #ifdef BOOST_MSVC
Chris@16: #pragma warning(pop)
Chris@16: #endif
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, bool>::type
Chris@16: is_element_equal(const Type& left, const Type& right)
Chris@16: { return left == right; }
Chris@16: 
Chris@16: 
Chris@16: /* Strict weak less ordering which is given by the Compare order */
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, bool>::type
Chris@16: operator < (const Type& left, const Type& right)
Chris@16: {
Chris@16:     return std::lexicographical_compare(
Chris@16:         left.begin(), left.end(), right.begin(), right.end(), 
Chris@16:         typename Type::element_compare()
Chris@16:         );
Chris@16: }
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: typename enable_if<is_concept_equivalent<is_element_container,LeftT, RightT>, 
Chris@16:                    int>::type
Chris@16: inclusion_compare(const LeftT& left, const RightT& right)
Chris@16: {
Chris@16:     return Set::subset_compare(left, right, 
Chris@16:                                left.begin(), left.end(),
Chris@16:                                right.begin(), right.end());
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Addition
Chris@16: //==============================================================================
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: operator += (Type& object, const typename Type::value_type& operand) 
Chris@16: { 
Chris@16:     return icl::add(object, operand); 
Chris@16: }
Chris@16: 
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator + (Type object, const typename Type::value_type& operand) 
Chris@16: { 
Chris@16:     return object += operand; 
Chris@16: }
Chris@16: 
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator + (const typename Type::value_type& operand, Type object) 
Chris@16: { 
Chris@16:     return object += operand; 
Chris@16: }
Chris@16: 
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: operator += (Type& object, const Type& operand) 
Chris@16: { 
Chris@16:     if(&object == &operand)
Chris@16:         return object;
Chris@16: 
Chris@16:     typename Type::iterator prior_ = object.end();
Chris@16:     ICL_const_FORALL(typename Type, it_, operand)
Chris@16:         prior_ = icl::add(object, prior_, *it_);
Chris@16: 
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator + (Type object, const Type& operand) 
Chris@16: { 
Chris@16:     return object += operand; 
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: operator |= (Type& object, const typename Type::value_type& operand) 
Chris@16: { 
Chris@16:     return icl::add(object, operand); 
Chris@16: }
Chris@16: 
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator | (Type object, const typename Type::value_type& operand) 
Chris@16: { 
Chris@16:     return object += operand; 
Chris@16: }
Chris@16: 
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator | (const typename Type::value_type& operand, Type object) 
Chris@16: { 
Chris@16:     return object += operand; 
Chris@16: }
Chris@16: 
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: operator |= (Type& object, const Type& operand) 
Chris@16: { 
Chris@16:     return object += operand; 
Chris@16: }
Chris@16: 
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator | (Type object, const Type& operand) 
Chris@16: { 
Chris@16:     return object += operand; 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Insertion
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- V insert(T&, c P&) T:{s}|{m} P:{e}|{b} fragment_type
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_associative_element_container<Type>, 
Chris@16:                    std::pair<typename Type::iterator,bool> >::type
Chris@16: insert(Type& object, const typename Type::value_type& operand)
Chris@16: {
Chris@16:     return object.insert(operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_associative_element_container<Type>, 
Chris@16:                    typename Type::iterator>::type
Chris@16: insert(Type& object, typename Type::iterator      prior, 
Chris@16:                const typename Type::value_type& operand)
Chris@16: {
Chris@16:     return object.insert(prior, operand);
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T insert(T&, c T&) T:{s m}  map fragment_type
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: insert(Type& object, const Type& addend)
Chris@16: {
Chris@16:     typedef typename Type::iterator iterator;
Chris@16: 
Chris@16:     iterator prior_ = object.end();
Chris@16:     ICL_const_FORALL(typename Type, elem_, addend) 
Chris@16:         icl::insert(object, prior_, *elem_);
Chris@16: 
Chris@16:     return object; 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Erasure
Chris@16: //==============================================================================
Chris@16: template<class Type>
Chris@16: typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
Chris@16: erase(Type& object, const typename Type::key_type& key_value)
Chris@16: {
Chris@16:     typedef typename Type::size_type size_type;
Chris@16:     typename Type::iterator it_ = object.find(key_value);
Chris@16:     if(it_ != object.end())
Chris@16:     {
Chris@16:         object.erase(it_);
Chris@16:         return unit_element<size_type>::value();
Chris@16:     }
Chris@16:     return identity_element<size_type>::value();
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: erase(Type& object, const Type& erasure)
Chris@16: {
Chris@16:     ICL_const_FORALL(typename Type, elem_, erasure) 
Chris@16:         icl::erase(object, *elem_); 
Chris@16: 
Chris@16:     return object; 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Subtraction<ElementSet|ElementMap>
Chris@16: //==============================================================================
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: operator -= (Type& object, const typename Type::value_type& operand) 
Chris@16: { 
Chris@16:     return icl::subtract(object, operand); 
Chris@16: }
Chris@16: 
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator - (Type object, const typename Type::value_type& operand) 
Chris@16: { 
Chris@16:     return object -= operand; 
Chris@16: }
Chris@16: 
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: operator -= (Type& object, const Type& subtrahend) 
Chris@16: { 
Chris@16:     ICL_const_FORALL(typename Type, it_, subtrahend)
Chris@16:         icl::subtract(object, *it_);
Chris@16: 
Chris@16:     return object; 
Chris@16: }
Chris@16: 
Chris@16: template <class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator - (Type object, const Type& subtrahend) 
Chris@16: { 
Chris@16:     return object -= subtrahend; 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Intersection
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- void add_intersection(T&, c T&, c P&) T:{s}{m} P:{e}{e} key_type 
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, void>::type
Chris@16: add_intersection(Type& section, const Type&              object, 
Chris@16:                        const typename Type::key_type& operand)
Chris@16: {
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16:     const_iterator it_ = object.find(operand);
Chris@16:     if(it_ != object.end()) 
Chris@16:         icl::add(section, *it_);
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- void add_intersection(T&, c T&, c P&) T:{s}{m} P:{s}{s} set key_type 
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, void>::type
Chris@16: add_intersection(Type& section, const Type& object, 
Chris@16:                  const typename key_container_type_of<Type>::type& operand)
Chris@16: {
Chris@16:     typedef typename key_container_type_of<Type>::type key_container_type;
Chris@16:     typedef typename key_container_type::const_iterator const_iterator;
Chris@16:     const_iterator common_lwb_, common_upb_;
Chris@16:     if(!Set::common_range(common_lwb_, common_upb_, operand, object))
Chris@16:         return;
Chris@16: 
Chris@16:     const_iterator sec_ = common_lwb_;
Chris@16:     while(sec_ != common_upb_)
Chris@16:         add_intersection(section, object, *sec_++);
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- Intersection<ElementMap|ElementSet> 
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: operator &= (Type& object, const typename Type::key_type& operand)
Chris@16: { 
Chris@16:     Type section;
Chris@16:     add_intersection(section, object, operand);
Chris@16:     object.swap(section);
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator & (Type object, const typename Type::key_type& operand)
Chris@16: {
Chris@16:     return object &= operand;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator & (const typename Type::key_type& operand, Type object)
Chris@16: {
Chris@16:     return object &= operand;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: operator &= (Type& object, const typename key_container_type_of<Type>::type& operand)
Chris@16: { 
Chris@16:     Type section;
Chris@16:     add_intersection(section, object, operand);
Chris@16:     object.swap(section);
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator & (Type object, const Type& operand)
Chris@16: {
Chris@16:     return object &= operand;
Chris@16: }
Chris@16: //------------------------------------------------------------------------------
Chris@16: 
Chris@16: template<class Type, class CoType>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, bool>::type
Chris@16: disjoint(const Type& left, const Type& right)
Chris@16: {
Chris@16:     return !intersects(left, right);
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Symmetric difference<ElementSet|ElementMap>
Chris@16: //==============================================================================
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator ^ (Type object, const typename Type::value_type& operand)
Chris@16: {
Chris@16:     return icl::flip(object, operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator ^ (const typename Type::value_type& operand, Type object)
Chris@16: {
Chris@16:     return icl::flip(object, operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type
Chris@16: operator ^ (Type object, const Type& operand)
Chris@16: {
Chris@16:     return object ^= operand; 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Manipulation by predicates
Chris@16: //==============================================================================
Chris@16: template<class Type, class Predicate>
Chris@16: typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: erase_if(const Predicate& pred, Type& object)
Chris@16: {
Chris@16:     typename Type::iterator it_ = object.begin();
Chris@16:     while(it_ != object.end())
Chris@16:         if(pred(*it_))
Chris@16:             icl::erase(object, it_++); 
Chris@16:         else ++it_;
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: template<class Type, class Predicate>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: add_if(const Predicate& pred, Type& object, const Type& src)
Chris@16: {
Chris@16:     typename Type::const_iterator it_ = src.begin();
Chris@16:     while(it_ != src.end())
Chris@16:         if(pred(*it_)) 
Chris@16:             icl::add(object, *it_++); 
Chris@16:     
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: template<class Type, class Predicate>
Chris@16: inline typename enable_if<is_associative_element_container<Type>, Type>::type&
Chris@16: assign_if(const Predicate& pred, Type& object, const Type& src)
Chris@16: {
Chris@16:     icl::clear(object);
Chris@16:     return add_if(object, src, pred);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost icl
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: