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