Chris@16: /*-----------------------------------------------------------------------------+
Chris@16: Copyright (c) 2007-2009: Joachim Faulhaber
Chris@16: Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
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_SPLIT_INTERVAL_SET_HPP_JOFA_990223
Chris@16: #define BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223
Chris@16: 
Chris@16: #include <boost/icl/type_traits/is_interval_splitter.hpp>
Chris@16: #include <boost/icl/interval_base_set.hpp>
Chris@16: #include <boost/icl/interval_set.hpp>
Chris@16: 
Chris@16: namespace boost{namespace icl
Chris@16: {
Chris@16: 
Chris@16: /** \brief implements a set as a set of intervals - on insertion 
Chris@16:     overlapping intervals are split */
Chris@16: template 
Chris@16: <
Chris@16:     typename                  DomainT, 
Chris@16:     ICL_COMPARE               Compare  = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
Chris@16:     ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
Chris@16:     ICL_ALLOC                 Alloc    = std::allocator
Chris@16: > 
Chris@16: class split_interval_set: 
Chris@16:     public interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>, 
Chris@16:                              DomainT,Compare,Interval,Alloc>
Chris@16: {
Chris@16: public:
Chris@16:     typedef split_interval_set<DomainT,Compare,Interval,Alloc> type;
Chris@16:     typedef interval_base_set<type,DomainT,Compare,Interval,Alloc> base_type;
Chris@16: 
Chris@16:     typedef interval_set<DomainT,Compare,Interval,Alloc> joint_type;
Chris@16:     typedef type overloadable_type;
Chris@16:     typedef type key_object_type;
Chris@16: 
Chris@16:     /// The domain type of the set
Chris@16:     typedef DomainT   domain_type;
Chris@16:     /// The codomaintype is the same as domain_type
Chris@16:     typedef DomainT   codomain_type;
Chris@16: 
Chris@16:     /// The element type of the set
Chris@16:     typedef DomainT   element_type;
Chris@16:     /// The interval type of the set
Chris@16:     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
Chris@16:     /// The segment type of the set
Chris@16:     typedef interval_type   segment_type;
Chris@16: 
Chris@16:     /// Comparison functor for domain values
Chris@16:     typedef ICL_COMPARE_DOMAIN(Compare,DomainT) domain_compare;
Chris@16:     /// Comparison functor for intervals
Chris@16:     typedef exclusive_less_than<interval_type> interval_compare;
Chris@16: 
Chris@16:     /// Comparison functor for keys
Chris@16:     typedef exclusive_less_than<interval_type> key_compare;
Chris@16: 
Chris@16:     /// The allocator type of the set
Chris@16:     typedef Alloc<interval_type> allocator_type;
Chris@16: 
Chris@16:     /// allocator type of the corresponding element set
Chris@16:     typedef Alloc<DomainT> domain_allocator_type;
Chris@16: 
Chris@16:     /// The corresponding atomized type representing this interval container of elements
Chris@16:     typedef typename base_type::atomized_type atomized_type;
Chris@16: 
Chris@16:     /// Container type for the implementation 
Chris@16:     typedef typename base_type::ImplSetT ImplSetT;
Chris@16: 
Chris@16:     /// key type of the implementing container
Chris@16:     typedef typename ImplSetT::key_type   key_type;
Chris@16:     /// data type of the implementing container
Chris@16:     typedef typename ImplSetT::value_type data_type;
Chris@16:     /// value type of the implementing container
Chris@16:     typedef typename ImplSetT::value_type value_type;
Chris@16: 
Chris@16:     /// iterator for iteration over intervals
Chris@16:     typedef typename ImplSetT::iterator iterator;
Chris@16:     /// const_iterator for iteration over intervals
Chris@16:     typedef typename ImplSetT::const_iterator const_iterator;
Chris@16: 
Chris@16:     enum { fineness = 3 };
Chris@16: 
Chris@16: public:
Chris@16:     //==========================================================================
Chris@16:     //= Construct, copy, destruct
Chris@16:     //==========================================================================
Chris@16:     /// Default constructor for the empty object
Chris@16:     split_interval_set(): base_type() {}
Chris@16: 
Chris@16:     /// Copy constructor
Chris@16:     split_interval_set(const split_interval_set& src): base_type(src) {}
Chris@16: 
Chris@16:     /// Copy constructor for base_type
Chris@16:     template<class SubType>
Chris@16:     split_interval_set
Chris@16:         (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
Chris@16:     { this->assign(src); }
Chris@16: 
Chris@16:     /// Constructor for a single element
Chris@16:     explicit split_interval_set(const interval_type& elem): base_type() { this->add(elem); }
Chris@16:     /// Constructor for a single interval
Chris@16:     explicit split_interval_set(const domain_type& itv): base_type() { this->add(itv); }
Chris@16: 
Chris@101:     /// Assignment from a base interval_set.
Chris@101:     template<class SubType>
Chris@101:     void assign(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
Chris@101:     {
Chris@101:         this->clear();
Chris@101:         this->_set.insert(src.begin(), src.end());
Chris@16:     }
Chris@16: 
Chris@16:     /// Assignment operator for base type
Chris@16:     template<class SubType>
Chris@16:     split_interval_set& operator =
Chris@16:         (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
Chris@101:     { 
Chris@101:         this->assign(src); 
Chris@101:         return *this; 
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:     /// Move constructor
Chris@16:     split_interval_set(split_interval_set&& src)
Chris@16:         : base_type(boost::move(src))
Chris@16:     {}
Chris@16: 
Chris@16:     /// Move assignment operator
Chris@101:     split_interval_set& operator = (split_interval_set src)
Chris@16:     { 
Chris@16:         base_type::operator=(boost::move(src));
Chris@16:         return *this;
Chris@16:     }
Chris@16:     //==========================================================================
Chris@101: #   else
Chris@101: 
Chris@101:     /// Assignment operator
Chris@101:     split_interval_set& operator = (const split_interval_set& src)
Chris@101:     { 
Chris@101:         base_type::operator=(src);
Chris@101:         return *this;
Chris@101:     }
Chris@101: 
Chris@16: #   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
Chris@16:     
Chris@16: private:
Chris@16:     // Private functions that shall be accessible by the baseclass:
Chris@16:     friend class
Chris@16:         interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>, 
Chris@16:                                              DomainT,Compare,Interval,Alloc>;
Chris@16: 
Chris@16:     iterator handle_inserted(iterator inserted_)
Chris@16:     { 
Chris@16:         return inserted_; 
Chris@16:     }
Chris@16: 
Chris@16:     iterator add_over(const interval_type& addend, iterator last_)
Chris@16:     {
Chris@16:         iterator first_ = this->_set.lower_bound(addend);
Chris@16:         //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
Chris@16: 
Chris@16:         iterator it_ = first_;
Chris@16:         interval_type rest_interval = addend;
Chris@16: 
Chris@16:         this->add_front(rest_interval, it_);
Chris@16:         this->add_main (rest_interval, it_, last_);
Chris@16:         this->add_rear (rest_interval, it_);
Chris@16:         return it_;
Chris@16:     }
Chris@16: 
Chris@16:     iterator add_over(const interval_type& addend)
Chris@16:     {
Chris@16:         std::pair<iterator,iterator> overlap = this->equal_range(addend);
Chris@16:         iterator first_ = overlap.first,
Chris@16:                  end_   = overlap.second,
Chris@16:                  last_  = end_; --last_;
Chris@16: 
Chris@16:         iterator it_ = first_;
Chris@16:         interval_type rest_interval = addend;
Chris@16: 
Chris@16:         this->add_front(rest_interval, it_);
Chris@16:         this->add_main (rest_interval, it_, last_);
Chris@16:         this->add_rear (rest_interval, it_);
Chris@16: 
Chris@16:         return it_;
Chris@16:     }
Chris@16: 
Chris@16: } ;
Chris@16: 
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // type traits
Chris@16: //-----------------------------------------------------------------------------
Chris@16: template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
Chris@16: struct is_set<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
Chris@16: { 
Chris@16:     typedef is_set<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true); 
Chris@16: };
Chris@16: 
Chris@16: template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
Chris@16: struct is_interval_container<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
Chris@16: { 
Chris@16:     typedef is_interval_container<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true); 
Chris@16: };
Chris@16: 
Chris@16: template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
Chris@16: struct is_interval_splitter<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
Chris@16: { 
Chris@16:     typedef is_interval_splitter<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true);
Chris@16: };
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // type representation
Chris@16: //-----------------------------------------------------------------------------
Chris@16: template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
Chris@16: struct type_to_string<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
Chris@16: {
Chris@16:     static std::string apply()
Chris@16:     { return "sp_itv_set<"+ type_to_string<DomainT>::apply() +">"; }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: }} // namespace icl boost
Chris@16: 
Chris@16: #endif // BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223
Chris@16: 
Chris@16: 
Chris@16: