1 /*-----------------------------------------------------------------------------+ 2 Copyright (c) 2007-2009: Joachim Faulhaber 3 Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin 4 +------------------------------------------------------------------------------+ 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENCE.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 +-----------------------------------------------------------------------------*/ 9 #ifndef BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223 10 #define BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223 11 12 #include <boost/icl/type_traits/is_interval_splitter.hpp> 13 #include <boost/icl/interval_base_set.hpp> 14 #include <boost/icl/interval_set.hpp> 15 16 namespace boost{namespace icl 17 { 18 19 /** \brief implements a set as a set of intervals - on insertion 20 overlapping intervals are split */ 21 template 22 < 23 typename DomainT, 24 ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT), 25 ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare), 26 ICL_ALLOC Alloc = std::allocator 27 > 28 class split_interval_set: 29 public interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>, 30 DomainT,Compare,Interval,Alloc> 31 { 32 public: 33 typedef split_interval_set<DomainT,Compare,Interval,Alloc> type; 34 typedef interval_base_set<type,DomainT,Compare,Interval,Alloc> base_type; 35 36 typedef interval_set<DomainT,Compare,Interval,Alloc> joint_type; 37 typedef type overloadable_type; 38 typedef type key_object_type; 39 40 /// The domain type of the set 41 typedef DomainT domain_type; 42 /// The codomaintype is the same as domain_type 43 typedef DomainT codomain_type; 44 45 /// The element type of the set 46 typedef DomainT element_type; 47 /// The interval type of the set 48 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type; 49 /// The segment type of the set 50 typedef interval_type segment_type; 51 52 /// Comparison functor for domain values 53 typedef ICL_COMPARE_DOMAIN(Compare,DomainT) domain_compare; 54 /// Comparison functor for intervals 55 typedef exclusive_less_than<interval_type> interval_compare; 56 57 /// Comparison functor for keys 58 typedef exclusive_less_than<interval_type> key_compare; 59 60 /// The allocator type of the set 61 typedef Alloc<interval_type> allocator_type; 62 63 /// allocator type of the corresponding element set 64 typedef Alloc<DomainT> domain_allocator_type; 65 66 /// The corresponding atomized type representing this interval container of elements 67 typedef typename base_type::atomized_type atomized_type; 68 69 /// Container type for the implementation 70 typedef typename base_type::ImplSetT ImplSetT; 71 72 /// key type of the implementing container 73 typedef typename ImplSetT::key_type key_type; 74 /// data type of the implementing container 75 typedef typename ImplSetT::value_type data_type; 76 /// value type of the implementing container 77 typedef typename ImplSetT::value_type value_type; 78 79 /// iterator for iteration over intervals 80 typedef typename ImplSetT::iterator iterator; 81 /// const_iterator for iteration over intervals 82 typedef typename ImplSetT::const_iterator const_iterator; 83 84 enum { fineness = 3 }; 85 86 public: 87 //========================================================================== 88 //= Construct, copy, destruct 89 //========================================================================== 90 /// Default constructor for the empty object split_interval_set()91 split_interval_set(): base_type() {} 92 93 /// Copy constructor split_interval_set(const split_interval_set & src)94 split_interval_set(const split_interval_set& src): base_type(src) {} 95 96 /// Copy constructor for base_type 97 template<class SubType> split_interval_set(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc> & src)98 split_interval_set 99 (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src) 100 { this->assign(src); } 101 102 /// Constructor for a single element split_interval_set(const interval_type & elem)103 explicit split_interval_set(const interval_type& elem): base_type() { this->add(elem); } 104 /// Constructor for a single interval split_interval_set(const domain_type & itv)105 explicit split_interval_set(const domain_type& itv): base_type() { this->add(itv); } 106 107 /// Assignment from a base interval_set. 108 template<class SubType> assign(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc> & src)109 void assign(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src) 110 { 111 this->clear(); 112 this->_set.insert(src.begin(), src.end()); 113 } 114 115 /// Assignment operator for base type 116 template<class SubType> operator =(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc> & src)117 split_interval_set& operator = 118 (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src) 119 { 120 this->assign(src); 121 return *this; 122 } 123 124 # ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES 125 //========================================================================== 126 //= Move semantics 127 //========================================================================== 128 129 /// Move constructor split_interval_set(split_interval_set && src)130 split_interval_set(split_interval_set&& src) 131 : base_type(boost::move(src)) 132 {} 133 134 /// Move assignment operator operator =(split_interval_set src)135 split_interval_set& operator = (split_interval_set src) 136 { 137 base_type::operator=(boost::move(src)); 138 return *this; 139 } 140 //========================================================================== 141 # else 142 143 /// Assignment operator operator =(const split_interval_set & src)144 split_interval_set& operator = (const split_interval_set& src) 145 { 146 base_type::operator=(src); 147 return *this; 148 } 149 150 # endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES 151 152 private: 153 // Private functions that shall be accessible by the baseclass: 154 friend class 155 interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>, 156 DomainT,Compare,Interval,Alloc>; 157 handle_inserted(iterator inserted_)158 iterator handle_inserted(iterator inserted_) 159 { 160 return inserted_; 161 } 162 add_over(const interval_type & addend,iterator last_)163 iterator add_over(const interval_type& addend, iterator last_) 164 { 165 iterator first_ = this->_set.lower_bound(addend); 166 //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val)); 167 168 iterator it_ = first_; 169 interval_type rest_interval = addend; 170 171 this->add_front(rest_interval, it_); 172 this->add_main (rest_interval, it_, last_); 173 this->add_rear (rest_interval, it_); 174 return it_; 175 } 176 add_over(const interval_type & addend)177 iterator add_over(const interval_type& addend) 178 { 179 std::pair<iterator,iterator> overlap = this->equal_range(addend); 180 iterator first_ = overlap.first, 181 end_ = overlap.second, 182 last_ = end_; --last_; 183 184 iterator it_ = first_; 185 interval_type rest_interval = addend; 186 187 this->add_front(rest_interval, it_); 188 this->add_main (rest_interval, it_, last_); 189 this->add_rear (rest_interval, it_); 190 191 return it_; 192 } 193 194 } ; 195 196 197 //----------------------------------------------------------------------------- 198 // type traits 199 //----------------------------------------------------------------------------- 200 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 201 struct is_set<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > 202 { 203 typedef is_set<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type; 204 BOOST_STATIC_CONSTANT(bool, value = true); 205 }; 206 207 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 208 struct is_interval_container<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > 209 { 210 typedef is_interval_container<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type; 211 BOOST_STATIC_CONSTANT(bool, value = true); 212 }; 213 214 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 215 struct is_interval_splitter<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > 216 { 217 typedef is_interval_splitter<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type; 218 BOOST_STATIC_CONSTANT(bool, value = true); 219 }; 220 221 //----------------------------------------------------------------------------- 222 // type representation 223 //----------------------------------------------------------------------------- 224 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 225 struct type_to_string<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > 226 { applyboost::icl::type_to_string227 static std::string apply() 228 { return "sp_itv_set<"+ type_to_string<DomainT>::apply() +">"; } 229 }; 230 231 232 }} // namespace icl boost 233 234 #endif // BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223 235 236 237 238