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