boost/icl/interval_set.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2007-2010: 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_INTERVAL_SET_HPP_JOFA_990223
0010 #define BOOST_ICL_INTERVAL_SET_HPP_JOFA_990223
0011
0012 #include <boost/assert.hpp>
0013 #include <boost/icl/type_traits/is_interval_joiner.hpp>
0014 #include <boost/icl/interval_base_set.hpp>
0015
0016 namespace boost{namespace icl
0017 {
0018
0019 /** \brief Implements a set as a set of intervals - merging adjoining intervals */
0020 template
0021 <
0022     typename    DomainT,
0023     ICL_COMPARE Compare  = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
0024     ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
0025     ICL_ALLOC   Alloc    = std::allocator
0026 >
0027 class interval_set:
0028     public interval_base_set<interval_set<DomainT,Compare,Interval,Alloc>,
0029                              DomainT,Compare,Interval,Alloc>
0030 {
0031 public:
0032
0033     typedef interval_set<DomainT,Compare,Interval,Alloc> type;
0034
0035     /// The base_type of this class
0036     typedef interval_base_set<type,DomainT,Compare,Interval,Alloc> base_type;
0037
0038     typedef type overloadable_type;
0039
0040     typedef type joint_type;
0041
0042     typedef type key_object_type;
0043
0044     /// The domain type of the set
0045     typedef DomainT   domain_type;
0046     /// The codomaintype is the same as domain_type
0047     typedef DomainT   codomain_type;
0048
0049     /// The element type of the set
0050     typedef DomainT   element_type;
0051     /// The interval type of the set
0052     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
0053     /// The segment type of the set
0054     typedef interval_type   segment_type;
0055
0056     /// Comparison functor for domain values
0057     typedef ICL_COMPARE_DOMAIN(Compare,DomainT) domain_compare;
0058     /// Comparison functor for intervals
0059     typedef exclusive_less_than<interval_type> interval_compare;
0060
0061     /// Comparison functor for keys
0062     typedef exclusive_less_than<interval_type> key_compare;
0063
0064     /// The allocator type of the set
0065     typedef Alloc<interval_type> allocator_type;
0066
0067     /// allocator type of the corresponding element set
0068     typedef Alloc<DomainT> domain_allocator_type;
0069
0070     /// The corresponding atomized type representing this interval container of elements
0071     typedef typename base_type::atomized_type atomized_type;
0072
0073     /// Container type for the implementation
0074     typedef typename base_type::ImplSetT ImplSetT;
0075
0076     /// key type of the implementing container
0077     typedef typename ImplSetT::key_type   key_type;
0078     /// data type of the implementing container
0079     typedef typename ImplSetT::value_type data_type;
0080     /// value type of the implementing container
0081     typedef typename ImplSetT::value_type value_type;
0082
0083     /// iterator for iteration over intervals
0084     typedef typename ImplSetT::iterator iterator;
0085     /// const_iterator for iteration over intervals
0086     typedef typename ImplSetT::const_iterator const_iterator;
0087
0088     enum { fineness = 1 };
0089
0090 public:
0091     //==========================================================================
0092     //= Construct, copy, destruct
0093     //==========================================================================
0094     /// Default constructor for the empty object
0095     interval_set(): base_type() {}
0096
0097     /// Copy constructor
0098     interval_set(const interval_set& src): base_type(src) {}
0099
0100     /// Copy constructor for base_type
0101     template<class SubType>
0102     explicit interval_set
0103         (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
0104     {
0105         this->assign(src);
0106     }
0107
0108     /// Constructor for a single element
0109     explicit interval_set(const domain_type& value): base_type()
0110     { this->add(interval_type(value)); }
0111
0112     /// Constructor for a single interval
0113     explicit interval_set(const interval_type& itv): base_type()
0114     {
0115         this->add(itv);
0116     }
0117
0118     /// Assignment from a base interval_set.
0119     template<class SubType>
0120     void assign(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
0121     {
0122         typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> base_set_type;
0123         this->clear();
0124         // Has to be implemented via add. there might be touching borders to be joined
0125         iterator prior_ = this->_set.end();
0126         ICL_const_FORALL(typename base_set_type, it_, src)
0127             prior_ = this->add(prior_, *it_);
0128     }
0129
0130     /// Assignment operator for base type
0131     template<class SubType>
0132     interval_set& operator =
0133         (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
0134     {
0135         this->assign(src);
0136         return *this;
0137     }
0138
0139 #   ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0140     //==========================================================================
0141     //= Move semantics
0142     //==========================================================================
0143
0144     /// Move constructor
0145     interval_set(interval_set&& src)
0146         : base_type(boost::move(src))
0147     {}
0148
0149     /// Move assignment operator
0150     interval_set& operator = (interval_set src)
0151     {
0152         base_type::operator=(boost::move(src));
0153         return *this;
0154     }
0155
0156     //==========================================================================
0157 #   else
0158     /// Assignment operator
0159     interval_set& operator = (const interval_set& src)
0160     {
0161         base_type::operator=(src);
0162         return *this;
0163     }
0164
0165 #   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0166
0167 private:
0168     // Private functions that shall be accessible by the baseclass:
0169     friend class
0170         interval_base_set <interval_set<DomainT,Compare,Interval,Alloc>,
0171                                         DomainT,Compare,Interval,Alloc>;
0172
0173     iterator handle_inserted(iterator it_)
0174     {
0175         return segmental::join_neighbours(*this, it_);
0176     }
0177
0178     iterator add_over(const interval_type& addend, iterator last_)
0179     {
0180         iterator joined_ = segmental::join_under(*this, addend, last_);
0181         return segmental::join_neighbours(*this, joined_);
0182     }
0183
0184     iterator add_over(const interval_type& addend)
0185     {
0186         iterator joined_ = segmental::join_under(*this, addend);
0187         return segmental::join_neighbours(*this, joined_);
0188     }
0189
0190 } ;
0191
0192
0193 //-----------------------------------------------------------------------------
0194 // type traits
0195 //-----------------------------------------------------------------------------
0196 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0197 struct is_set<icl::interval_set<DomainT,Compare,Interval,Alloc> >
0198 {
0199     typedef is_set<icl::interval_set<DomainT,Compare,Interval,Alloc> > type;
0200     BOOST_STATIC_CONSTANT(bool, value = true);
0201 };
0202
0203 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0204 struct is_interval_container<icl::interval_set<DomainT,Compare,Interval,Alloc> >
0205 {
0206     typedef is_interval_container<icl::interval_set<DomainT,Compare,Interval,Alloc> > type;
0207     BOOST_STATIC_CONSTANT(bool, value = true);
0208 };
0209
0210 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0211 struct is_interval_joiner<icl::interval_set<DomainT,Compare,Interval,Alloc> >
0212 {
0213     typedef is_interval_joiner<icl::interval_set<DomainT,Compare,Interval,Alloc> > type;
0214     BOOST_STATIC_CONSTANT(bool, value = true);
0215 };
0216
0217
0218 //-----------------------------------------------------------------------------
0219 // type representation
0220 //-----------------------------------------------------------------------------
0221 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0222 struct type_to_string<icl::interval_set<DomainT,Compare,Interval,Alloc> >
0223 {
0224     static std::string apply()
0225     { return "itv_set<"+ type_to_string<DomainT>::apply() +">"; }
0226 };
0227
0228 }} // namespace icl boost
0229
0230 #endif
0231
0232