content/browser/resources/media/disjoint_range_set.js

   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 });