Home | History | Annotate | Download | only in base 
      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(int i) const;
     36   T end(int 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(int i) const {
    123   return ranges_[i].first;
    124 }
    125 
    126 template<class T>
    127 T Ranges<T>::end(int 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_
    163