boost/icl/split_interval_set.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2007-2009: Joachim Faulhaber
0003 Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
0004 +------------------------------------------------------------------------------+
0005    Distributed under the Boost Software License, Version 1.0.
0006       (See accompanying file LICENCE.txt or copy at
0007            http://www.boost.org/LICENSE_1_0.txt)
0008 +-----------------------------------------------------------------------------*/
0009 #ifndef BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223
0010 #define BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223
0011
0012 #include <boost/icl/type_traits/is_interval_splitter.hpp>
0013 #include <boost/icl/interval_base_set.hpp>
0014 #include <boost/icl/interval_set.hpp>
0015
0016 namespace boost{namespace icl
0017 {
0018
0019 /** \brief implements a set as a set of intervals - on insertion
0020     overlapping intervals are split */
0021 template
0022 <
0023     typename                  DomainT,
0024     ICL_COMPARE               Compare  = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
0025     ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
0026     ICL_ALLOC                 Alloc    = std::allocator
0027 >
0028 class split_interval_set:
0029     public interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>,
0030                              DomainT,Compare,Interval,Alloc>
0031 {
0032 public:
0033     typedef split_interval_set<DomainT,Compare,Interval,Alloc> type;
0034     typedef interval_base_set<type,DomainT,Compare,Interval,Alloc> base_type;
0035
0036     typedef interval_set<DomainT,Compare,Interval,Alloc> joint_type;
0037     typedef type overloadable_type;
0038     typedef type key_object_type;
0039
0040     /// The domain type of the set
0041     typedef DomainT   domain_type;
0042     /// The codomaintype is the same as domain_type
0043     typedef DomainT   codomain_type;
0044
0045     /// The element type of the set
0046     typedef DomainT   element_type;
0047     /// The interval type of the set
0048     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
0049     /// The segment type of the set
0050     typedef interval_type   segment_type;
0051
0052     /// Comparison functor for domain values
0053     typedef ICL_COMPARE_DOMAIN(Compare,DomainT) domain_compare;
0054     /// Comparison functor for intervals
0055     typedef exclusive_less_than<interval_type> interval_compare;
0056
0057     /// Comparison functor for keys
0058     typedef exclusive_less_than<interval_type> key_compare;
0059
0060     /// The allocator type of the set
0061     typedef Alloc<interval_type> allocator_type;
0062
0063     /// allocator type of the corresponding element set
0064     typedef Alloc<DomainT> domain_allocator_type;
0065
0066     /// The corresponding atomized type representing this interval container of elements
0067     typedef typename base_type::atomized_type atomized_type;
0068
0069     /// Container type for the implementation
0070     typedef typename base_type::ImplSetT ImplSetT;
0071
0072     /// key type of the implementing container
0073     typedef typename ImplSetT::key_type   key_type;
0074     /// data type of the implementing container
0075     typedef typename ImplSetT::value_type data_type;
0076     /// value type of the implementing container
0077     typedef typename ImplSetT::value_type value_type;
0078
0079     /// iterator for iteration over intervals
0080     typedef typename ImplSetT::iterator iterator;
0081     /// const_iterator for iteration over intervals
0082     typedef typename ImplSetT::const_iterator const_iterator;
0083
0084     enum { fineness = 3 };
0085
0086 public:
0087     //==========================================================================
0088     //= Construct, copy, destruct
0089     //==========================================================================
0090     /// Default constructor for the empty object
0091     split_interval_set(): base_type() {}
0092
0093     /// Copy constructor
0094     split_interval_set(const split_interval_set& src): base_type(src) {}
0095
0096     /// Copy constructor for base_type
0097     template<class SubType>
0098     split_interval_set
0099         (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
0100     { this->assign(src); }
0101
0102     /// Constructor for a single element
0103     explicit split_interval_set(const interval_type& elem): base_type() { this->add(elem); }
0104     /// Constructor for a single interval
0105     explicit split_interval_set(const domain_type& itv): base_type() { this->add(itv); }
0106
0107     /// Assignment from a base interval_set.
0108     template<class SubType>
0109     void assign(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
0110     {
0111         this->clear();
0112         this->_set.insert(src.begin(), src.end());
0113     }
0114
0115     /// Assignment operator for base type
0116     template<class SubType>
0117     split_interval_set& operator =
0118         (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
0119     {
0120         this->assign(src);
0121         return *this;
0122     }
0123
0124 #   ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0125     //==========================================================================
0126     //= Move semantics
0127     //==========================================================================
0128
0129     /// Move constructor
0130     split_interval_set(split_interval_set&& src)
0131         : base_type(boost::move(src))
0132     {}
0133
0134     /// Move assignment operator
0135     split_interval_set& operator = (split_interval_set src)
0136     {
0137         base_type::operator=(boost::move(src));
0138         return *this;
0139     }
0140     //==========================================================================
0141 #   else
0142
0143     /// Assignment operator
0144     split_interval_set& operator = (const split_interval_set& src)
0145     {
0146         base_type::operator=(src);
0147         return *this;
0148     }
0149
0150 #   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0151
0152 private:
0153     // Private functions that shall be accessible by the baseclass:
0154     friend class
0155         interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>,
0156                                              DomainT,Compare,Interval,Alloc>;
0157
0158     iterator handle_inserted(iterator inserted_)
0159     {
0160         return inserted_;
0161     }
0162
0163     iterator add_over(const interval_type& addend, iterator last_)
0164     {
0165         iterator first_ = this->_set.lower_bound(addend);
0166         //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
0167
0168         iterator it_ = first_;
0169         interval_type rest_interval = addend;
0170
0171         this->add_front(rest_interval, it_);
0172         this->add_main (rest_interval, it_, last_);
0173         this->add_rear (rest_interval, it_);
0174         return it_;
0175     }
0176
0177     iterator add_over(const interval_type& addend)
0178     {
0179         std::pair<iterator,iterator> overlap = this->equal_range(addend);
0180         iterator first_ = overlap.first,
0181                  end_   = overlap.second,
0182                  last_  = end_; --last_;
0183
0184         iterator it_ = first_;
0185         interval_type rest_interval = addend;
0186
0187         this->add_front(rest_interval, it_);
0188         this->add_main (rest_interval, it_, last_);
0189         this->add_rear (rest_interval, it_);
0190
0191         return it_;
0192     }
0193
0194 } ;
0195
0196
0197 //-----------------------------------------------------------------------------
0198 // type traits
0199 //-----------------------------------------------------------------------------
0200 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0201 struct is_set<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
0202 {
0203     typedef is_set<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
0204     BOOST_STATIC_CONSTANT(bool, value = true);
0205 };
0206
0207 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0208 struct is_interval_container<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
0209 {
0210     typedef is_interval_container<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
0211     BOOST_STATIC_CONSTANT(bool, value = true);
0212 };
0213
0214 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0215 struct is_interval_splitter<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
0216 {
0217     typedef is_interval_splitter<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
0218     BOOST_STATIC_CONSTANT(bool, value = true);
0219 };
0220
0221 //-----------------------------------------------------------------------------
0222 // type representation
0223 //-----------------------------------------------------------------------------
0224 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0225 struct type_to_string<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
0226 {
0227     static std::string apply()
0228     { return "sp_itv_set<"+ type_to_string<DomainT>::apply() +">"; }
0229 };
0230
0231
0232 }} // namespace icl boost
0233
0234 #endif // BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223
0235
0236
0237