libUTL++
Span.h
1 #pragma once
2 
4 
5 #include <libutl/MemStream.h>
6 
8 
9 UTL_NS_BEGIN;
10 
12 
18 {
22 };
23 
25 // Span ////////////////////////////////////////////////////////////////////////////////////////////
27 
44 
46 template <class T, class D = T>
47 class Span : public Object, protected FlagsMI
48 {
50 
51 public:
58  Span(const T& begin, const T& end, bool relaxed = false);
59 
60  virtual int compare(const Object& rhs) const;
61 
62  virtual void copy(const Object& rhs);
63 
64  virtual void serialize(Stream& stream, uint_t io, uint_t mode = ser_default);
65 
66  virtual String toString() const;
67 
69 
70 
71  const T&
72  begin() const
73  {
74  return _begin;
75  }
76 
78  void
79  setBegin(const T& begin)
80  {
81  _begin = begin;
82  }
83 
85  const T&
86  end() const
87  {
88  return _end;
89  }
90 
92  void
93  setEnd(const T& end)
94  {
95  _end = end;
96  }
97 
99  void
100  set(const T& begin, const T& end)
101  {
102  _begin = begin;
103  _end = end;
104  }
105 
107  bool
108  isNil() const
109  {
110  return _begin >= _end;
111  }
112 
114  void
116  {
117  _begin = _end = T();
118  }
119 
121  bool
122  isRelaxed() const
123  {
124  return getFlag(flg_relaxed);
125  }
126 
128  void
129  setRelaxed(bool relaxed)
130  {
131  setFlag(flg_relaxed, relaxed);
132  }
133 
135  D
136  size() const
137  {
138  return _end - _begin;
139  }
141 
143  Span<T, D>& clip(const Span<T, D>& span);
144 
146  Span<T, D>&
147  clipBegin(const T& t)
148  {
149  if (t > _begin) _begin = t;
150  return *this;
151  }
152 
154  Span<T, D>&
155  clipEnd(const T& t)
156  {
157  if (t < _end) _end = t;
158  return *this;
159  }
160 
162  bool
163  contains(const Span<T, D>& span) const
164  {
165  return (_begin <= span._begin) && (_end >= span._end);
166  }
167 
169  bool
170  contains(const T& v) const
171  {
172  return ((v >= _begin) && (v < _end));
173  }
174 
176  bool
177  isContainedBy(const Span<T, D>& span) const
178  {
179  return span.contains(*this);
180  }
181 
183  void
184  merge(const Span<T, D>& span)
185  {
186  _begin = min(_begin, span.begin());
187  _end = max(_end, span.end());
188  }
189 
191  Span<T, D> overlap(const Span<T, D>& span) const;
192 
194  bool
195  overlaps(const Span<T, D>& span) const
196  {
197  return !overlap(span).isNil();
198  }
199 
201  D overlapSize(const Span<T, D>& span) const;
202 
207  Span<T, D> remove(const Span<T, D>& span);
208 
211  {
212  Span<T, D> res(*this);
213  res.merge(rhs);
214  return res;
215  }
216 
218  const Span<T, D>& operator+=(const Span<T, D>& rhs)
219  {
220  merge(rhs);
221  return *this;
222  }
223 
224 protected:
225  T _begin;
226  T _end;
227 
228 private:
229  enum flg_t
230  {
231  flg_relaxed
232  };
233 
234 private:
235  void
236  init(bool relaxed = false)
237  {
238  _begin = _end = T();
239  setRelaxed(relaxed);
240  }
241  void
242  deInit()
243  {
244  }
245 };
246 
248 // SpanSizeOrdering ////////////////////////////////////////////////////////////////////////////////
250 
258 
260 template <class T, class D = T>
262 {
265 
266 public:
267  virtual int cmp(const Object* lhs, const Object* rhs) const;
268 };
269 
271 // ObjectSpan //////////////////////////////////////////////////////////////////////////////////////
273 
281 
283 template <class T, class D = T>
284 class ObjectSpan : public Span<T, D>
285 {
288 
289 public:
295  : Span<T, D>(span)
296  {
297  }
298 
299  virtual void serialize(Stream& stream, uint_t io, uint_t mode = ser_default);
300 
301  virtual String
302  toString() const
303  {
304  return "[" + this->_begin.toString() + "," + this->_end.toString() + ")";
305  }
306 };
307 
309 // Span ////////////////////////////////////////////////////////////////////////////////////////////
311 
312 template <class T, class D>
313 Span<T, D>::Span(const T& begin, const T& end, bool relaxed)
314  : _begin(begin)
315  , _end(end)
316 {
317  setRelaxed(relaxed);
318 }
319 
321 
322 template <class T, class D>
323 int
324 Span<T, D>::compare(const Object& rhs) const
325 {
326  int res;
327  if (rhs.isA2(Span, T, D))
328  {
329  auto& span = utl::cast<Span<T, D>>(rhs);
330  // If "relaxed" comparison, the spans are equal if they overlap,
331  // Else they must be exactly the same.
332  if ((isRelaxed() || span.isRelaxed()) && overlaps(span))
333  {
334  res = 0;
335  }
336  else
337  {
338  res = utl::compare(_begin, span._begin);
339  if (res != 0) return res;
340  res = utl::compare(_end, span._end);
341  }
342  }
343  else
344  {
345  res = super::compare(rhs);
346  }
347  return res;
348 }
349 
351 
352 template <class T, class D>
353 void
355 {
356  auto& span = utl::cast<Span<T, D>>(rhs);
357  FlagsMI::copyFlags(span);
358  _begin = span._begin;
359  _end = span._end;
360 }
361 
363 
364 template <class T, class D>
365 void
367 {
368  utl::serialize(_begin, stream, io, mode);
369  utl::serialize(_end, stream, io, mode);
370 }
371 
373 
374 template <class T, class D>
375 String
377 {
378  MemStream ms(64);
379  ms << "[" << _begin << "," << _end << ")" << '\0';
380  return String(ms.takeString(), true, false);
381 }
382 
384 
385 template <class T, class D>
386 Span<T, D>&
388 {
389  // ensure begin >= span.begin
390  // ensure end <= span.end
391  if (_begin < span._begin) _begin = span._begin;
392  if (_end > span._end) _end = span._end;
393  return *this;
394 }
395 
397 
398 template <class T, class D>
400 Span<T, D>::overlap(const Span<T, D>& span) const
401 {
402  T beg = max(_begin, span._begin);
403  T end = min(_end, span._end);
404  return Span<T, D>(beg, end);
405 }
406 
408 
409 template <class T, class D>
410 D
412 {
413  return utl::min(_end, span._end) - utl::max(_begin, span._begin);
414 }
415 
417 
418 template <class T, class D>
421 {
422  T t = T();
423  Span<T, D> res(t, t);
424 
425  // if span contains* this, removing span makes* this NIL
426  if (span.contains(*this))
427  {
428  setNil();
429  return res;
430  }
431 
432  // get the overlapping time span
433  Span<T, D> overlap = span.overlap(*this);
434 
435  if (overlap.isNil())
436  {
437  return res;
438  }
439 
440  // if begin == beginning of overlap, begin = end of overlap
441  if (_begin == overlap.begin())
442  {
443  setBegin(overlap.end());
444  }
445  // if end == end of overlap, end = beginning of overlap
446  else if (_end == overlap.end())
447  {
448  setEnd(overlap.begin());
449  }
450  // else we are being bi-sected
451  else
452  {
453  // the result is the second section [overlap.end, end)
454  res.setBegin(overlap.end());
455  res.setEnd(end());
456  // this becomes the first section [begin, overlap.begin)
457  setEnd(overlap.begin());
458  }
459 
460  return res;
461 }
462 
464 // SpanSizeOrdering ////////////////////////////////////////////////////////////////////////////////
466 
467 template <class T, class D>
468 int
469 SpanSizeOrdering<T, D>::cmp(const Object* lhs, const Object* rhs) const
470 {
471  const Object& lhsKey = lhs->getKey();
472  const Object& rhsKey = rhs->getKey();
473  if (!lhsKey.isA2(Span, T, D) || !rhsKey.isA2(Span, T, D))
474  {
475  return lhs->compare(*rhs);
476  }
477 
478  const Span<T, D>& lhsSpan = (const Span<T, D>&)lhsKey;
479  const Span<T, D>& rhsSpan = (const Span<T, D>&)rhsKey;
480  int res = lhsSpan.size() - rhsSpan.size();
481  if (res == 0)
482  {
483  res = lhsSpan.compare(rhsSpan);
484  }
485  return res;
486 }
487 
489 // ObjectSpan //////////////////////////////////////////////////////////////////////////////////////
491 
492 template <class T, class D>
493 void
495 {
496  this->_begin.serialize(stream, io, mode);
497  this->_end.serialize(stream, io, mode);
498 }
499 
501 
502 UTL_NS_END;
503 
505 
#define UTL_CLASS_DEFID
Default init() and deInit() (which are merely place-holders).
Definition: macros.h:532
const T & begin() const
Get the beginning of the span.
Definition: Span.h:72
void merge(const Span< T, D > &span)
Merge with the given span.
Definition: Span.h:184
String toString(const FwdIt &begin, const FwdIt &end, const String &sep, bool key=false)
Obtain a string representation of a sequence (via Object::toString()).
void serialize(bool &b, Stream &stream, uint_t io, uint_t mode=ser_default)
Serialize a boolean.
bool overlaps(const Span< T, D > &span) const
Determine whether self overlaps with the given span.
Definition: Span.h:195
void deInit()
De-initialize UTL++.
void merge(const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, FwdIt &out, const Ordering *ordering=nullptr, bool cloning=false)
Merge two sorted sequences into a single sorted sequence.
span overlaps another
Definition: Span.h:19
Object comparison abstraction.
Definition: Ordering.h:30
const T & max(const T &a, const T &b, const R &... args)
Return the largest value among two or more provided values of the same type.
Definition: util_inl.h:89
#define UTL_CLASS_DECL_TPL2_TPL2(DC, DC_T1, DC_T2, BC, BC_T1, BC_T2)
Declaration of standard UTL++ functionality for a template class with two parameters, where the base class also has two template parameters.
Definition: macros.h:739
void setEnd(const T &end)
Set the end of the span.
Definition: Span.h:93
D size() const
Return the size (end - begin).
Definition: Span.h:136
default representation (via getSerializeMode())
Definition: util.h:75
void remove(FwdIt &begin, const FwdIt &end, bool cmp=false, const Predicate *pred=nullptr, bool predVal=false)
Remove objects from a sequence.
const T & max(const T &v)
Base case for utl::max() variadic template.
Definition: util_inl.h:71
Span of object-derived objects.
Definition: Span.h:284
Character string.
Definition: String.h:31
Mix-in to provide 64-bits for space-efficient storage of up to 64 boolean flags.
Definition: FlagsMI.h:25
Order spans by size.
Definition: Span.h:261
Span< T, D > & clipEnd(const T &t)
Clip the end against the given value.
Definition: Span.h:155
bool contains(const T &v) const
Determine whether self contains the given value.
Definition: Span.h:170
void copy(T *dest, const T *src, size_t len)
Copy one array of objects to another.
Definition: util_inl.h:690
virtual int compare(const Object &rhs) const
Compare with another object.
Definition: Span.h:324
char * takeString()
Convert to a string.
ObjectSpan(Span< T, D > span)
Constructor.
Definition: Span.h:294
const T & end() const
Get the end of the span.
Definition: Span.h:86
Memory stream.
Definition: MemStream.h:40
bool isRelaxed() const
Get the relaxed flag.
Definition: Span.h:122
Span< T, D > & clipBegin(const T &t)
Clip the beginning against the given value.
Definition: Span.h:147
bool contains(const Span< T, D > &span) const
Determine whether self contains the given span.
Definition: Span.h:163
void setRelaxed(bool relaxed)
Set the relaxed flag.
Definition: Span.h:129
void setNil()
Set the span to nil.
Definition: Span.h:115
unsigned int uint_t
Unsigned integer.
Definition: types.h:59
void setBegin(const T &begin)
Set the beginning of the span.
Definition: Span.h:79
#define UTL_CLASS_DECL_TPL2(DC, T1, T2, BC)
Declaration of standard UTL++ functionality for a template class with two parameters, where the base class has zero or one template parameters.
Definition: macros.h:726
#define UTL_CLASS_IMPL_TPL2(className, T1, T2)
Implementation of standard UTL++ functionality for a template class with two parameters.
Definition: macros.h:917
Span< T, D > operator+(const Span< T, D > &rhs)
Return self merged with the given span.
Definition: Span.h:210
Span< T, D > overlap(const Span< T, D > &span) const
Return the sub-span that overlaps with the given span.
Definition: Span.h:400
Stream I/O abstraction.
Definition: Stream.h:68
const Span< T, D > & operator+=(const Span< T, D > &rhs)
Merge with the given span.
Definition: Span.h:218
const T & min(const T &a, const T &b, const R &... args)
Return the smallest value among two or more provided values of the same type.
Definition: util_inl.h:61
virtual int compare(const Object &rhs) const
Compare with another object.
span_op_t
Span relationships.
Definition: Span.h:17
virtual const Object & getKey() const
Get the key for this object.
span is contained by another
Definition: Span.h:21
virtual String toString() const
Return a string representation of self.
Definition: Span.h:302
bool isNil() const
Determine whether the span is nil.
Definition: Span.h:108
Span of values.
Definition: Span.h:47
Root of UTL++ class hierarchy.
Definition: Object.h:52
int compare(bool lhs, bool rhs)
Compare two boolean values.
const T & min(const T &v)
Base case for utl::min() variadic template.
Definition: util_inl.h:43
bool isContainedBy(const Span< T, D > &span) const
Determine whether self is contained by the given span.
Definition: Span.h:177
void init()
Initialize UTL++.
virtual String toString() const
Return a string representation of self.
span contains another
Definition: Span.h:20