Apache Mesos
interval.hpp
Go to the documentation of this file.
1 // Licensed under the Apache License, Version 2.0 (the "License");
2 // you may not use this file except in compliance with the License.
3 // You may obtain a copy of the License at
4 //
5 // http://www.apache.org/licenses/LICENSE-2.0
6 //
7 // Unless required by applicable law or agreed to in writing, software
8 // distributed under the License is distributed on an "AS IS" BASIS,
9 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
10 // limitations under the License.
11 
12 #ifndef __STOUT_INTERVAL_HPP__
13 #define __STOUT_INTERVAL_HPP__
14 
15 #include <functional> // For std::less.
16 #include <iostream>
17 
18 #include <boost/icl/interval.hpp>
19 #include <boost/icl/interval_set.hpp>
20 
21 
22 // Forward declarations.
23 template <typename T>
24 class Interval;
25 
26 
27 template <typename T>
29 
30 
31 // Represents a bound (left or right) for an interval. A bound can
32 // either be open or closed.
33 template <typename T>
34 class Bound
35 {
36 public:
37  // Creates an open bound.
38  static Bound<T> open(const T& value)
39  {
40  return Bound<T>(OPEN, value);
41  }
42 
43  // Creates an closed bound.
44  static Bound<T> closed(const T& value)
45  {
46  return Bound<T>(CLOSED, value);
47  }
48 
49  // Intervals can be created using the comma operator. For example:
50  // (2, 6): (Bound<int>::open(2), Bound<int>::open(6))
51  // (3, 4]: (Bound<int>::open(3), Bound<int>::closed(4))
52  // [0, 5): (Bound<int>::closed(0), Bound<int>::open(5))
53  // [1, 2]: (Bound<int>::closed(1), Bound<int>::closed(2))
54  Interval<T> operator , (const Bound<T>& right) const;
55 
56 private:
57  enum Type
58  {
59  OPEN,
60  CLOSED,
61  };
62 
63  Bound(const Type _type, const T& _value)
64  : type(_type), value(_value) {}
65 
66  const Type type;
67  const T value;
68 };
69 
70 
71 // Represents an interval.
72 template <typename T>
73 class Interval
74 {
75 public:
76  // We must provide a public default constructor as the boost
77  // interval set expects that.
78  Interval() {}
79 
80  // Returns the inclusive lower bound of this interval.
81  T lower() const { return data.lower(); }
82 
83  // Returns the exclusive upper bound of this interval.
84  T upper() const { return data.upper(); }
85 
86  // Checks if this interval intersects with another interval.
87  bool intersects(const Interval<T>& interval) const;
88 
89  // Checks if this interval intersects with an interval set.
90  bool intersects(const IntervalSet<T>& set) const;
91 
92  bool operator==(const Interval<T>& that) const
93  {
94  return data == that.data;
95  }
96 
97  bool operator!=(const Interval<T>& that) const
98  {
99  return !(*this == that);
100  }
101 
102 private:
103  friend class Bound<T>;
104 
105  template <typename X>
106  friend std::ostream& operator<<(
107  std::ostream& stream,
108  const Interval<X>& interval);
109 
110  Interval(const boost::icl::right_open_interval<T, std::less>& _data)
111  : data(_data) {}
112 
113  // We store the interval in right open format: [lower, upper).
114  // Notice that we use composition here instead of inheritance to
115  // prevent Interval from being passed to bare boost icl containers.
116  boost::icl::right_open_interval<T, std::less> data;
117 };
118 
119 
120 template <typename T>
121 std::ostream& operator<<(std::ostream& stream, const Interval<T>& interval)
122 {
123  return stream << interval.data;
124 }
125 
126 
127 template <typename T>
129 {
130  if (type == OPEN) {
131  if (right.type == OPEN) {
132  // For example: (1, 3).
133  return boost::icl::static_interval<
134  boost::icl::right_open_interval<T, std::less>, // Target.
135  boost::icl::is_discrete<T>::value,
136  boost::icl::interval_bounds::static_open, // Input bounds.
137  boost::icl::interval_bounds::static_right_open // Output bounds.
138  >::construct(value, right.value);
139  } else {
140  // For example: (1, 3].
141  return boost::icl::static_interval<
142  boost::icl::right_open_interval<T, std::less>, // Target.
143  boost::icl::is_discrete<T>::value,
144  boost::icl::interval_bounds::static_left_open, // Input bounds.
145  boost::icl::interval_bounds::static_right_open // Output bounds.
146  >::construct(value, right.value);
147  }
148  } else {
149  if (right.type == OPEN) {
150  // For example: [1, 3).
151  return boost::icl::static_interval<
152  boost::icl::right_open_interval<T, std::less>, // Target.
153  boost::icl::is_discrete<T>::value,
154  boost::icl::interval_bounds::static_right_open, // Input bounds.
155  boost::icl::interval_bounds::static_right_open // Output bounds.
156  >::construct(value, right.value);
157  } else {
158  // For example: [1, 3].
159  return boost::icl::static_interval<
160  boost::icl::right_open_interval<T, std::less>, // Target.
161  boost::icl::is_discrete<T>::value,
162  boost::icl::interval_bounds::static_closed, // Input bounds.
163  boost::icl::interval_bounds::static_right_open // Output bounds.
164  >::construct(value, right.value);
165  }
166  }
167 }
168 
169 
170 // Modeled after boost interval_set. Provides a compact representation
171 // of a set by merging adjacent elements into intervals.
172 template <typename T>
173 class IntervalSet : public boost::icl::interval_set<T, std::less, Interval<T>>
174 {
175 public:
177 
178  explicit IntervalSet(const T& value)
179  {
180  Base::add(value);
181  }
182 
183  explicit IntervalSet(const Interval<T>& interval)
184  {
185  Base::add(interval);
186  }
187 
189  {
190  Base::add((lower, upper));
191  }
192 
193  // Checks if an element is in this set.
194  bool contains(const T& value) const
195  {
196  return boost::icl::contains(static_cast<const Base&>(*this), value);
197  }
198 
199  // Checks if an interval is in this set.
200  bool contains(const Interval<T>& interval) const
201  {
202  // TODO(jieyu): Boost has an issue regarding unqualified lookup in
203  // template (http://clang.llvm.org/compatibility.html#dep_lookup),
204  // and gcc-4.8 complains about it. We use a workaround here by
205  // delegating this call to the IntervalSet version below.
206  return contains(IntervalSet<T>(interval));
207  }
208 
209  // Checks if an interval set is a subset of this set.
210  bool contains(const IntervalSet<T>& set) const
211  {
212  return boost::icl::contains(
213  static_cast<const Base&>(*this),
214  static_cast<const Base&>(set));
215  }
216 
217  // Checks if this set intersects with an interval.
218  bool intersects(const Interval<T>& interval) const
219  {
220  return boost::icl::intersects(static_cast<const Base&>(*this), interval);
221  }
222 
223  // Checks if this set intersects with another interval set.
224  bool intersects(const IntervalSet<T>& set) const
225  {
226  return boost::icl::intersects(
227  static_cast<const Base&>(*this),
228  static_cast<const Base&>(set));
229  }
230 
231  // Returns the number of intervals in this set.
232  size_t intervalCount() const
233  {
234  return boost::icl::interval_count(static_cast<const Base&>(*this));
235  }
236 
237  // Overloaded operators.
238  bool operator==(const IntervalSet<T>& that) const
239  {
240  return static_cast<const Base&>(*this) == static_cast<const Base&>(that);
241  }
242 
243  bool operator!=(const IntervalSet<T>& that) const
244  {
245  return !(*this == that);
246  }
247 
248  IntervalSet<T>& operator+=(const T& value)
249  {
250  static_cast<Base&>(*this) += value;
251  return *this;
252  }
253 
255  {
256  static_cast<Base&>(*this) += interval;
257  return *this;
258  }
259 
261  {
262  static_cast<Base&>(*this) += static_cast<const Base&>(set);
263  return *this;
264  }
265 
266  IntervalSet<T>& operator-=(const T& value)
267  {
268  static_cast<Base&>(*this) -= value;
269  return *this;
270  }
271 
273  {
274  static_cast<Base&>(*this) -= interval;
275  return *this;
276  }
277 
279  {
280  static_cast<Base&>(*this) -= static_cast<const Base&>(set);
281  return *this;
282  }
283 
284  IntervalSet<T>& operator&=(const T& value)
285  {
286  static_cast<Base&>(*this) &= value;
287  return *this;
288  }
289 
291  {
292  static_cast<Base&>(*this) &= interval;
293  return *this;
294  }
295 
297  {
298  static_cast<Base&>(*this) &= static_cast<const Base&>(set);
299  return *this;
300  }
301 
302 private:
303  template <typename X>
304  friend std::ostream& operator<<(
305  std::ostream& stream,
306  const IntervalSet<X>& set);
307 
308  // We use typedef here to make the code less verbose.
309  typedef boost::icl::interval_set<T, std::less, Interval<T>> Base;
310 };
311 
312 
313 template <typename T>
314 std::ostream& operator<<(std::ostream& stream, const IntervalSet<T>& set)
315 {
316  return stream << static_cast<const typename IntervalSet<T>::Base&>(set);
317 }
318 
319 
320 template <typename T>
321 bool Interval<T>::intersects(const Interval<T>& interval) const
322 {
323  return IntervalSet<T>(*this).intersects(interval);
324 }
325 
326 
327 template <typename T>
329 {
330  return set.intersects(*this);
331 }
332 
333 
334 template <typename T, typename X>
335 IntervalSet<T> operator+(const IntervalSet<T>& set, const X& x)
336 {
337  IntervalSet<T> result(set);
338  result += x;
339  return result;
340 }
341 
342 
343 template <typename T, typename X>
344 IntervalSet<T> operator-(const IntervalSet<T>& set, const X& x)
345 {
346  IntervalSet<T> result(set);
347  result -= x;
348  return result;
349 }
350 
351 
352 // Defines type traits for the custom Interval above. These type
353 // traits are required by the boost interval set.
354 namespace boost {
355 namespace icl {
356 
357 template <typename T>
358 struct interval_traits<Interval<T>>
359 {
360  typedef interval_traits type;
361  typedef T domain_type;
362  typedef std::less<T> domain_compare;
363 
364  static Interval<T> construct(const T& lower, const T& upper)
365  {
366  return (Bound<T>::closed(lower), Bound<T>::open(upper));
367  }
368 
369  static T lower(const Interval<T>& interval)
370  {
371  return interval.lower();
372  }
373 
374  static T upper(const Interval<T>& interval)
375  {
376  return interval.upper();
377  }
378 };
379 
380 
381 template <typename T>
382 struct interval_bound_type<Interval<T>>
383  : public interval_bound_type<right_open_interval<T, std::less>>
384 {
385  typedef interval_bound_type type;
386 };
387 
388 } // namespace icl {
389 } // namespace boost {
390 
391 #endif // __STOUT_INTERVAL_HPP__
Definition: interval.hpp:34
bool operator!=(const Interval< T > &that) const
Definition: interval.hpp:97
IntervalSet< T > & operator+=(const Interval< T > &interval)
Definition: interval.hpp:254
bool construct(JNIEnv *env, jboolean jbool)
bool operator!=(const IntervalSet< T > &that) const
Definition: interval.hpp:243
static T lower(const Interval< T > &interval)
Definition: interval.hpp:369
Definition: interval.hpp:354
Interval< T > operator,(const Bound< T > &right) const
Definition: interval.hpp:128
IntervalSet(const Interval< T > &interval)
Definition: interval.hpp:183
bool intersects(const IntervalSet< T > &set) const
Definition: interval.hpp:224
IntervalSet(const Bound< T > &lower, const Bound< T > &upper)
Definition: interval.hpp:188
Definition: interval.hpp:28
bool operator==(const IntervalSet< T > &that) const
Definition: interval.hpp:238
IntervalSet< T > & operator-=(const Interval< T > &interval)
Definition: interval.hpp:272
IntervalSet< T > & operator+=(const T &value)
Definition: interval.hpp:248
Future< Nothing > add(const T &metric)
Definition: metrics.hpp:95
bool intersects(const Interval< T > &interval) const
Definition: interval.hpp:321
IntervalSet()
Definition: interval.hpp:176
Definition: interval.hpp:24
static Interval< T > construct(const T &lower, const T &upper)
Definition: interval.hpp:364
static Bound< T > open(const T &value)
Definition: interval.hpp:38
bool contains(const std::string &s, const std::string &substr)
Definition: strings.hpp:423
IntervalSet< T > operator-(const IntervalSet< T > &set, const X &x)
Definition: interval.hpp:344
T lower() const
Definition: interval.hpp:81
Interval()
Definition: interval.hpp:78
size_t intervalCount() const
Definition: interval.hpp:232
bool operator==(const Interval< T > &that) const
Definition: interval.hpp:92
IntervalSet< T > & operator&=(const IntervalSet< T > &set)
Definition: interval.hpp:296
bool contains(const IntervalSet< T > &set) const
Definition: interval.hpp:210
T upper() const
Definition: interval.hpp:84
T domain_type
Definition: interval.hpp:361
IntervalSet< T > & operator&=(const Interval< T > &interval)
Definition: interval.hpp:290
std::string upper(const std::string &s)
Definition: strings.hpp:437
IntervalSet< T > operator+(const IntervalSet< T > &set, const X &x)
Definition: interval.hpp:335
bool contains(const Interval< T > &interval) const
Definition: interval.hpp:200
IntervalSet< T > & operator+=(const IntervalSet< T > &set)
Definition: interval.hpp:260
IntervalSet< T > & operator-=(const T &value)
Definition: interval.hpp:266
IntervalSet(const T &value)
Definition: interval.hpp:178
IntervalSet< T > & operator-=(const IntervalSet< T > &set)
Definition: interval.hpp:278
interval_bound_type type
Definition: interval.hpp:385
std::less< T > domain_compare
Definition: interval.hpp:362
IntervalSet< T > & operator&=(const T &value)
Definition: interval.hpp:284
static T upper(const Interval< T > &interval)
Definition: interval.hpp:374
bool contains(const T &value) const
Definition: interval.hpp:194
interval_traits type
Definition: interval.hpp:360
static Bound< T > closed(const T &value)
Definition: interval.hpp:44
std::string lower(const std::string &s)
Definition: strings.hpp:429
std::ostream & operator<<(std::ostream &stream, const Interval< T > &interval)
Definition: interval.hpp:121
bool intersects(const Interval< T > &interval) const
Definition: interval.hpp:218