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