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