ranges.h 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164
  1. // Copyright (c) 2012 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef MEDIA_BASE_RANGES_H_
  5. #define MEDIA_BASE_RANGES_H_
  6. #include <stddef.h>
  7. #include <stdint.h>
  8. #include <algorithm>
  9. #include <ostream>
  10. #include <vector>
  11. #include "base/check_op.h"
  12. #include "base/time/time.h"
  13. #include "media/base/media_export.h"
  14. namespace media {
  15. // Ranges allows holding an ordered list of ranges of [start,end) intervals.
  16. // The canonical example use-case is holding the list of ranges of buffered
  17. // bytes or times in a <video> tag.
  18. template <class T> // Endpoint type; typically a base::TimeDelta or an int64_t.
  19. class Ranges {
  20. public:
  21. // Allow copy & assign.
  22. // Add (start,end) to this object, coallescing overlaps as appropriate.
  23. // Returns the number of stored ranges, post coallescing.
  24. size_t Add(T start, T end);
  25. // Return the number of disjoint ranges.
  26. size_t size() const;
  27. // Return the "i"'th range's start & end (0-based).
  28. T start(size_t i) const;
  29. T end(size_t i) const;
  30. // Clear all ranges.
  31. void clear();
  32. // Computes the intersection between this range and |other|.
  33. Ranges<T> IntersectionWith(const Ranges<T>& other) const;
  34. private:
  35. // Wrapper around DCHECK_LT allowing comparisons of operator<<'able T's.
  36. void DCheckLT(const T& lhs, const T& rhs) const;
  37. // Disjoint, in increasing order of start.
  38. std::vector<std::pair<T, T> > ranges_;
  39. };
  40. //////////////////////////////////////////////////////////////////////
  41. // EVERYTHING BELOW HERE IS IMPLEMENTATION DETAIL!!
  42. //////////////////////////////////////////////////////////////////////
  43. template<class T>
  44. size_t Ranges<T>::Add(T start, T end) {
  45. if (start == end) // Nothing to be done with empty ranges.
  46. return ranges_.size();
  47. DCheckLT(start, end);
  48. size_t i;
  49. // Walk along the array of ranges until |start| is no longer larger than the
  50. // current interval's end.
  51. for (i = 0; i < ranges_.size() && ranges_[i].second < start; ++i) {
  52. // Empty body
  53. }
  54. // Now we know |start| belongs in the i'th slot.
  55. // If i is the end of the range, append new range and done.
  56. if (i == ranges_.size()) {
  57. ranges_.push_back(std::make_pair(start, end));
  58. return ranges_.size();
  59. }
  60. // If |end| is less than i->first, then [start,end) is a new (non-overlapping)
  61. // i'th entry pushing everyone else back, and done.
  62. if (end < ranges_[i].first) {
  63. ranges_.insert(ranges_.begin() + i, std::make_pair(start, end));
  64. return ranges_.size();
  65. }
  66. // Easy cases done. Getting here means there is overlap between [start,end)
  67. // and the existing ranges.
  68. // Now: start <= i->second && i->first <= end
  69. if (start < ranges_[i].first)
  70. ranges_[i].first = start;
  71. if (ranges_[i].second < end)
  72. ranges_[i].second = end;
  73. // Now: [start,end) is contained in the i'th range, and we'd be done, except
  74. // for the fact that the newly-extended i'th range might now overlap
  75. // subsequent ranges. Merge until discontinuities appear. Note that there's
  76. // no need to test/merge previous ranges, since needing that would mean the
  77. // original loop went too far.
  78. while ((i + 1) < ranges_.size() &&
  79. ranges_[i + 1].first <= ranges_[i].second) {
  80. ranges_[i].second = std::max(ranges_[i].second, ranges_[i + 1].second);
  81. ranges_.erase(ranges_.begin() + i + 1);
  82. }
  83. return ranges_.size();
  84. }
  85. template<>
  86. MEDIA_EXPORT void
  87. Ranges<base::TimeDelta>::DCheckLT(const base::TimeDelta& lhs,
  88. const base::TimeDelta& rhs) const;
  89. template<class T>
  90. void Ranges<T>::DCheckLT(const T& lhs, const T& rhs) const {
  91. DCHECK_LT(lhs, rhs);
  92. }
  93. template<class T>
  94. size_t Ranges<T>::size() const {
  95. return ranges_.size();
  96. }
  97. template<class T>
  98. T Ranges<T>::start(size_t i) const {
  99. return ranges_[i].first;
  100. }
  101. template<class T>
  102. T Ranges<T>::end(size_t i) const {
  103. return ranges_[i].second;
  104. }
  105. template<class T>
  106. void Ranges<T>::clear() {
  107. ranges_.clear();
  108. }
  109. template<class T>
  110. Ranges<T> Ranges<T>::IntersectionWith(const Ranges<T>& other) const {
  111. Ranges<T> result;
  112. size_t i = 0;
  113. size_t j = 0;
  114. while (i < size() && j < other.size()) {
  115. T max_start = std::max(start(i), other.start(j));
  116. T min_end = std::min(end(i), other.end(j));
  117. // Add an intersection range to the result if the ranges overlap.
  118. if (max_start < min_end)
  119. result.Add(max_start, min_end);
  120. if (end(i) < other.end(j))
  121. ++i;
  122. else
  123. ++j;
  124. }
  125. return result;
  126. }
  127. } // namespace media
  128. #endif // MEDIA_BASE_RANGES_H_