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
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>
16 namespace boost{namespace icl
19 /** \brief implements a set as a set of intervals - on insertion
20 overlapping intervals are split */
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
28 class split_interval_set:
29 public interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>,
30 DomainT,Compare,Interval,Alloc>
33 typedef split_interval_set<DomainT,Compare,Interval,Alloc> type;
34 typedef interval_base_set<type,DomainT,Compare,Interval,Alloc> base_type;
36 typedef interval_set<DomainT,Compare,Interval,Alloc> joint_type;
37 typedef type overloadable_type;
38 typedef type key_object_type;
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;
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;
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;
57 /// Comparison functor for keys
58 typedef exclusive_less_than<interval_type> key_compare;
60 /// The allocator type of the set
61 typedef Alloc<interval_type> allocator_type;
63 /// allocator type of the corresponding element set
64 typedef Alloc<DomainT> domain_allocator_type;
66 /// The corresponding atomized type representing this interval container of elements
67 typedef typename base_type::atomized_type atomized_type;
69 /// Container type for the implementation
70 typedef typename base_type::ImplSetT ImplSetT;
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;
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;
84 enum { fineness = 3 };
87 //==========================================================================
88 //= Construct, copy, destruct
89 //==========================================================================
90 /// Default constructor for the empty object
91 split_interval_set(): base_type() {}
94 split_interval_set(const split_interval_set& src): base_type(src) {}
96 /// Copy constructor for base_type
97 template<class SubType>
99 (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
100 { this->assign(src); }
102 /// Constructor for a single element
103 explicit split_interval_set(const interval_type& elem): base_type() { this->add(elem); }
104 /// Constructor for a single interval
105 explicit split_interval_set(const domain_type& itv): base_type() { this->add(itv); }
107 /// Assignment from a base interval_set.
108 template<class SubType>
109 void assign(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
112 this->_set.insert(src.begin(), src.end());
115 /// Assignment operator for base type
116 template<class SubType>
117 split_interval_set& operator =
118 (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
124 # ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
125 //==========================================================================
127 //==========================================================================
130 split_interval_set(split_interval_set&& src)
131 : base_type(boost::move(src))
134 /// Move assignment operator
135 split_interval_set& operator = (split_interval_set src)
137 base_type::operator=(boost::move(src));
140 //==========================================================================
143 /// Assignment operator
144 split_interval_set& operator = (const split_interval_set& src)
146 base_type::operator=(src);
150 # endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
153 // Private functions that shall be accessible by the baseclass:
155 interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>,
156 DomainT,Compare,Interval,Alloc>;
158 iterator handle_inserted(iterator inserted_)
163 iterator add_over(const interval_type& addend, iterator last_)
165 iterator first_ = this->_set.lower_bound(addend);
166 //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
168 iterator it_ = first_;
169 interval_type rest_interval = addend;
171 this->add_front(rest_interval, it_);
172 this->add_main (rest_interval, it_, last_);
173 this->add_rear (rest_interval, it_);
177 iterator add_over(const interval_type& addend)
179 std::pair<iterator,iterator> overlap = this->equal_range(addend);
180 iterator first_ = overlap.first,
181 end_ = overlap.second,
182 last_ = end_; --last_;
184 iterator it_ = first_;
185 interval_type rest_interval = addend;
187 this->add_front(rest_interval, it_);
188 this->add_main (rest_interval, it_, last_);
189 this->add_rear (rest_interval, it_);
197 //-----------------------------------------------------------------------------
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> >
203 typedef is_set<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
204 BOOST_STATIC_CONSTANT(bool, value = true);
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> >
210 typedef is_interval_container<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
211 BOOST_STATIC_CONSTANT(bool, value = true);
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> >
217 typedef is_interval_splitter<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
218 BOOST_STATIC_CONSTANT(bool, value = true);
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> >
227 static std::string apply()
228 { return "sp_itv_set<"+ type_to_string<DomainT>::apply() +">"; }
232 }} // namespace icl boost
234 #endif // BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223