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
5cr.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