media/base/ranges.h

   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>
  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>
 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  // MEDIA_BASE_RANGES_H_