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
|
/*-----------------------------------------------------------------------------+
Copyright (c) 2007-2010: 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_INTERVAL_SET_HPP_JOFA_990223
#define BOOST_ICL_INTERVAL_SET_HPP_JOFA_990223
#include <boost/assert.hpp>
#include <boost/icl/type_traits/is_interval_joiner.hpp>
#include <boost/icl/interval_base_set.hpp>
namespace boost{namespace icl
{
/** \brief Implements a set as a set of intervals - merging adjoining intervals */
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 interval_set:
public interval_base_set<interval_set<DomainT,Compare,Interval,Alloc>,
DomainT,Compare,Interval,Alloc>
{
public:
typedef interval_set<DomainT,Compare,Interval,Alloc> type;
/// The base_type of this class
typedef interval_base_set<type,DomainT,Compare,Interval,Alloc> base_type;
typedef type overloadable_type;
typedef type joint_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 = 1 };
public:
//==========================================================================
//= Construct, copy, destruct
//==========================================================================
/// Default constructor for the empty object
interval_set(): base_type() {}
/// Copy constructor
interval_set(const interval_set& src): base_type(src) {}
/// Copy constructor for base_type
template<class SubType>
explicit interval_set
(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
{
this->assign(src);
}
/// Constructor for a single element
explicit interval_set(const domain_type& value): base_type()
{ this->add(interval_type(value)); }
/// Constructor for a single interval
explicit interval_set(const interval_type& itv): base_type()
{
this->add(itv);
}
/// Assignment operator
template<class SubType>
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)
{
typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> base_set_type;
this->clear();
// Has to be implemented via add. there might be touching borders to be joined
iterator prior_ = this->_set.end();
ICL_const_FORALL(typename base_set_type, it_, src)
prior_ = this->add(prior_, *it_);
}
# ifndef BOOST_NO_RVALUE_REFERENCES
//==========================================================================
//= Move semantics
//==========================================================================
/// Move constructor
interval_set(interval_set&& src)
: base_type(boost::move(src))
{}
/// Move assignment operator
interval_set& operator = (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 <interval_set<DomainT,Compare,Interval,Alloc>,
DomainT,Compare,Interval,Alloc>;
iterator handle_inserted(iterator it_)
{
return segmental::join_neighbours(*this, it_);
}
iterator add_over(const interval_type& addend, iterator last_)
{
iterator joined_ = segmental::join_under(*this, addend, last_);
return segmental::join_neighbours(*this, joined_);
}
iterator add_over(const interval_type& addend)
{
iterator joined_ = segmental::join_under(*this, addend);
return segmental::join_neighbours(*this, joined_);
}
} ;
//-----------------------------------------------------------------------------
// type traits
//-----------------------------------------------------------------------------
template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
struct is_set<icl::interval_set<DomainT,Compare,Interval,Alloc> >
{
typedef is_set<icl::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::interval_set<DomainT,Compare,Interval,Alloc> >
{
typedef is_interval_container<icl::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_joiner<icl::interval_set<DomainT,Compare,Interval,Alloc> >
{
typedef is_interval_joiner<icl::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::interval_set<DomainT,Compare,Interval,Alloc> >
{
static std::string apply()
{ return "itv_set<"+ type_to_string<DomainT>::apply() +">"; }
};
}} // namespace icl boost
#endif
|