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>
Add(T start,T end)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>
DCheckLT(const T & lhs,const T & rhs)113 void Ranges<T>::DCheckLT(const T& lhs, const T& rhs) const {
114 DCHECK_LT(lhs, rhs);
115 }
116
117 template<class T>
size()118 size_t Ranges<T>::size() const {
119 return ranges_.size();
120 }
121
122 template<class T>
start(size_t i)123 T Ranges<T>::start(size_t i) const {
124 return ranges_[i].first;
125 }
126
127 template<class T>
end(size_t i)128 T Ranges<T>::end(size_t i) const {
129 return ranges_[i].second;
130 }
131
132 template<class T>
clear()133 void Ranges<T>::clear() {
134 ranges_.clear();
135 }
136
137 template<class T>
IntersectionWith(const Ranges<T> & other)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