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
17namespace 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.
22template<class T>  // Endpoint type; typically a base::TimeDelta or an int64.
23class 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
56template<class T>
57size_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
106template<>
107MEDIA_EXPORT void
108    Ranges<base::TimeDelta>::DCheckLT(const base::TimeDelta& lhs,
109                                      const base::TimeDelta& rhs) const;
110
111template<class T>
112void Ranges<T>::DCheckLT(const T& lhs, const T& rhs) const {
113  DCHECK_LT(lhs, rhs);
114}
115
116template<class T>
117size_t Ranges<T>::size() const {
118  return ranges_.size();
119}
120
121template<class T>
122T Ranges<T>::start(size_t i) const {
123  return ranges_[i].first;
124}
125
126template<class T>
127T Ranges<T>::end(size_t i) const {
128  return ranges_[i].second;
129}
130
131template<class T>
132void Ranges<T>::clear() {
133  ranges_.clear();
134}
135
136template<class T>
137Ranges<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