Home | History | Annotate | Download | only in media 
      1 // Copyright (c) 2011 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 cr.define('media', function() {
      6 
      7   /**
      8    * This class represents a collection of non-intersecting ranges. Ranges
      9    * specified by (start, end) can be added and removed at will. It is used to
     10    * record which sections of a media file have been cached, e.g. the first and
     11    * last few kB plus several MB in the middle.
     12    *
     13    * Example usage:
     14    * someRange.add(0, 100);     // Contains 0-100.
     15    * someRange.add(150, 200);   // Contains 0-100, 150-200.
     16    * someRange.remove(25, 75);  // Contains 0-24, 76-100, 150-200.
     17    * someRange.add(25, 149);    // Contains 0-200.
     18    */
     19   function DisjointRangeSet() {
     20     this.ranges_ = {};
     21   }
     22 
     23   DisjointRangeSet.prototype = {
     24     /**
     25      * Deletes all ranges intersecting with (start ... end) and returns the
     26      * extents of the cleared area.
     27      * @param {int} start The start of the range to remove.
     28      * @param {int} end The end of the range to remove.
     29      * @param {int} sloppiness 0 removes only strictly overlapping ranges, and
     30      *                         1 removes adjacent ones.
     31      * @return {Object} The start and end of the newly cleared range.
     32      */
     33     clearRange: function(start, end, sloppiness) {
     34       var ranges = this.ranges_;
     35       var result = {start: start, end: end};
     36 
     37       for (var rangeStart in this.ranges_) {
     38         rangeEnd = this.ranges_[rangeStart];
     39         // A range intersects another if its start lies within the other range
     40         // or vice versa.
     41         if ((rangeStart >= start && rangeStart <= (end + sloppiness)) ||
     42             (start >= rangeStart && start <= (rangeEnd + sloppiness))) {
     43           delete ranges[rangeStart];
     44           result.start = Math.min(result.start, rangeStart);
     45           result.end = Math.max(result.end, rangeEnd);
     46         }
     47       }
     48 
     49       return result;
     50     },
     51 
     52     /**
     53      * Adds a range to this DisjointRangeSet.
     54      * Joins adjacent and overlapping ranges together.
     55      * @param {int} start The beginning of the range to add, inclusive.
     56      * @param {int} end The end of the range to add, inclusive.
     57      */
     58     add: function(start, end) {
     59       if (end < start)
     60         return;
     61 
     62       // Remove all touching ranges.
     63       result = this.clearRange(start, end, 1);
     64       // Add back a single contiguous range.
     65       this.ranges_[Math.min(start, result.start)] = Math.max(end, result.end);
     66     },
     67 
     68     /**
     69      * Combines a DisjointRangeSet with this one.
     70      * @param {DisjointRangeSet} ranges A DisjointRangeSet to be squished into
     71      * this one.
     72      */
     73     merge: function(other) {
     74       var ranges = this;
     75       other.forEach(function(start, end) { ranges.add(start, end); });
     76     },
     77 
     78     /**
     79      * Removes a range from this DisjointRangeSet.
     80      * Will split existing ranges if necessary.
     81      * @param {int} start The beginning of the range to remove, inclusive.
     82      * @param {int} end The end of the range to remove, inclusive.
     83      */
     84     remove: function(start, end) {
     85       if (end < start)
     86         return;
     87 
     88       // Remove instersecting ranges.
     89       result = this.clearRange(start, end, 0);
     90 
     91       // Add back non-overlapping ranges.
     92       if (result.start < start)
     93         this.ranges_[result.start] = start - 1;
     94       if (result.end > end)
     95         this.ranges_[end + 1] = result.end;
     96     },
     97 
     98     /**
     99      * Iterates over every contiguous range in this DisjointRangeSet, calling a
    100      * function for each (start, end).
    101      * @param {function(int, int)} iterator The function to call on each range.
    102      */
    103     forEach: function(iterator) {
    104       for (var start in this.ranges_)
    105         iterator(start, this.ranges_[start]);
    106     },
    107 
    108     /**
    109      * Maps this DisjointRangeSet to an array by calling a given function on the
    110      * start and end of each contiguous range, sorted by start.
    111      * @param {function(int, int)} mapper Maps a range to an array element.
    112      * @return {Array} An array of each mapper(range).
    113      */
    114     map: function(mapper) {
    115       var starts = [];
    116       for (var start in this.ranges_)
    117         starts.push(parseInt(start));
    118       starts.sort(function(a, b) {
    119         return a - b;
    120       });
    121 
    122       var ranges = this.ranges_;
    123       var results = starts.map(function(s) {
    124         return mapper(s, ranges[s]);
    125       });
    126 
    127       return results;
    128     },
    129 
    130     /**
    131      * Finds the maximum value present in any of the contained ranges.
    132      * @return {int} The maximum value contained by this DisjointRangeSet.
    133      */
    134     max: function() {
    135       var max = -Infinity;
    136       for (var start in this.ranges_)
    137         max = Math.max(max, this.ranges_[start]);
    138       return max;
    139     },
    140   };
    141 
    142   return {
    143     DisjointRangeSet: DisjointRangeSet
    144   };
    145 });
    146