ranges.h

// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef MEDIA_BASE_RANGES_H_
#define MEDIA_BASE_RANGES_H_

#include <stddef.h>
#include <stdint.h>

#include <algorithm>
#include <ostream>
#include <vector>

using namespace std;

namespace media {
    
    // Ranges allows holding an ordered list of ranges of [start,end) intervals.
    // The canonical example use-case is holding the list of ranges of buffered
    // bytes or times in a <video> tag.
    template <typename T>  // Endpoint type; typically a base::TimeDelta or an int64_t.
    class Ranges {
    public:
        // Allow copy & assign.
        
        // Add (start,end) to this object, coallescing overlaps as appropriate.
        // Returns the number of stored ranges, post coallescing.
        size_t Add(T start, T end);
        
        // Return the number of disjoint ranges.
        size_t size() const;
        
        // Return the "i"'th range's start & end (0-based).
        T start(size_t i) const;
        T end(size_t i) const;
        
        // Clear all ranges.
        void clear();
        
        // Computes the intersection between this range and |other|.
        Ranges<T> IntersectionWith(const Ranges<T>& other) const;
        
    private:
        // Wrapper around DCHECK_LT allowing comparisons of operator<<'able T's.
        void DCheckLT(const T& lhs, const T& rhs) const;
        
        // Disjoint, in increasing order of start.
        std::vector<std::pair<T, T> > ranges_;
    };
    
    //////////////////////////////////////////////////////////////////////
    // EVERYTHING BELOW HERE IS IMPLEMENTATION DETAIL!!
    //////////////////////////////////////////////////////////////////////
    
    template<class T>
    size_t Ranges<T>::Add(T start, T end) {
        if (start == end)  // Nothing to be done with empty ranges.
            return ranges_.size();
        
        //DCheckLT(start, end);
        size_t i;
        // Walk along the array of ranges until |start| is no longer larger than the
        // current interval's end.
        for (i = 0; i < ranges_.size() && ranges_[i].second < start; ++i) {
            // Empty body
        }
        
        // Now we know |start| belongs in the i'th slot.
        // If i is the end of the range, append new range and done.
        if (i == ranges_.size()) {
            ranges_.push_back(std::make_pair(start, end));
            return ranges_.size();
        }
        
        // If |end| is less than i->first, then [start,end) is a new (non-overlapping)
        // i'th entry pushing everyone else back, and done.
        if (end < ranges_[i].first) {
            ranges_.insert(ranges_.begin() + i, std::make_pair(start, end));
            return ranges_.size();
        }
        
        // Easy cases done.  Getting here means there is overlap between [start,end)
        // and the existing ranges.
        
        // Now: start <= i->second && i->first <= end
        if (start < ranges_[i].first)
            ranges_[i].first = start;
        if (ranges_[i].second < end)
            ranges_[i].second = end;
        
        // Now: [start,end) is contained in the i'th range, and we'd be done, except
        // for the fact that the newly-extended i'th range might now overlap
        // subsequent ranges.  Merge until discontinuities appear.  Note that there's
        // no need to test/merge previous ranges, since needing that would mean the
        // original loop went too far.
        while ((i + 1) < ranges_.size() &&
               ranges_[i + 1].first <= ranges_[i].second) {
            ranges_[i].second = max(ranges_[i].second, ranges_[i + 1].second);
            ranges_.erase(ranges_.begin() + i + 1);
        }
        
        return ranges_.size();
    }
    

    
    template<class T>
    size_t Ranges<T>::size() const {
        return ranges_.size();
    }
    
    template<class T>
    T Ranges<T>::start(size_t i) const {
        return ranges_[i].first;
    }
    
    template<class T>
    T Ranges<T>::end(size_t i) const {
        return ranges_[i].second;
    }
    
    template<class T>
    void Ranges<T>::clear() {
        ranges_.clear();
    }
    
    template<class T>
    Ranges<T> Ranges<T>::IntersectionWith(const Ranges<T>& other) const {
        Ranges<T> result;
        
        size_t i = 0;
        size_t j = 0;
        
        while (i < size() && j < other.size()) {
            T max_start = max(start(i), other.start(j));
            T min_end = min(end(i), other.end(j));
            
            // Add an intersection range to the result if the ranges overlap.
            if (max_start < min_end)
                result.Add(max_start, min_end);
            
            if (end(i) < other.end(j))
                ++i;
            else
                ++j;
        }
        
        return result;
    }
    
}  // namespace media

#endif  // MEDIA_BASE_RANGES_H_