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