1<!DOCTYPE html>
2<!--
3Copyright (c) 2014 The Chromium Authors. All rights reserved.
4Use of this source code is governed by a BSD-style license that can be
5found in the LICENSE file.
6-->
7
8<link rel="import" href="/tracing/base/base.html">
9<link rel="import" href="/tracing/base/iteration_helpers.html">
10
11<script>
12'use strict';
13
14/**
15 * @fileoverview Quick range computations.
16 */
17tr.exportTo('tr.b', function() {
18
19  function Range() {
20    this.isEmpty_ = true;
21    this.min_ = undefined;
22    this.max_ = undefined;
23  };
24
25  Range.prototype = {
26    __proto__: Object.prototype,
27
28    reset: function() {
29      this.isEmpty_ = true;
30      this.min_ = undefined;
31      this.max_ = undefined;
32    },
33
34    get isEmpty() {
35      return this.isEmpty_;
36    },
37
38    addRange: function(range) {
39      if (range.isEmpty)
40        return;
41      this.addValue(range.min);
42      this.addValue(range.max);
43    },
44
45    addValue: function(value) {
46      if (this.isEmpty_) {
47        this.max_ = value;
48        this.min_ = value;
49        this.isEmpty_ = false;
50        return;
51      }
52      this.max_ = Math.max(this.max_, value);
53      this.min_ = Math.min(this.min_, value);
54    },
55
56    set min(min) {
57      this.isEmpty_ = false;
58      this.min_ = min;
59    },
60
61    get min() {
62      if (this.isEmpty_)
63        return undefined;
64      return this.min_;
65    },
66
67    get max() {
68      if (this.isEmpty_)
69        return undefined;
70      return this.max_;
71    },
72
73    set max(max) {
74      this.isEmpty_ = false;
75      this.max_ = max;
76    },
77
78    get range() {
79      if (this.isEmpty_)
80        return undefined;
81      return this.max_ - this.min_;
82    },
83
84    get center() {
85      return (this.min_ + this.max_) * 0.5;
86    },
87
88    get duration() {
89      if (this.isEmpty_)
90        return 0;
91      return this.max_ - this.min_;
92    },
93
94    equals: function(that) {
95      if (this.isEmpty && that.isEmpty)
96        return true;
97      if (this.isEmpty != that.isEmpty)
98        return false;
99      return this.min === that.min &&
100          this.max === that.max;
101    },
102
103    containsExplicitRangeInclusive: function(min, max) {
104      if (this.isEmpty)
105        return false;
106      return this.min_ <= min && max <= this.max_;
107    },
108
109    containsExplicitRangeExclusive: function(min, max) {
110      if (this.isEmpty)
111        return false;
112      return this.min_ < min && max < this.max_;
113    },
114
115    intersectsExplicitRangeInclusive: function(min, max) {
116      if (this.isEmpty)
117        return false;
118      return this.min_ <= max && min <= this.max_;
119    },
120
121    intersectsExplicitRangeExclusive: function(min, max) {
122      if (this.isEmpty)
123        return false;
124      return this.min_ < max && min < this.max_;
125    },
126
127    containsRangeInclusive: function(range) {
128      if (range.isEmpty)
129        return false;
130      return this.containsExplicitRangeInclusive(range.min_, range.max_);
131    },
132
133    containsRangeExclusive: function(range) {
134      if (range.isEmpty)
135        return false;
136      return this.containsExplicitRangeExclusive(range.min_, range.max_);
137    },
138
139    intersectsRangeInclusive: function(range) {
140      if (range.isEmpty)
141        return false;
142      return this.intersectsExplicitRangeInclusive(range.min_, range.max_);
143    },
144
145    intersectsRangeExclusive: function(range) {
146      if (range.isEmpty)
147        return false;
148      return this.intersectsExplicitRangeExclusive(range.min_, range.max_);
149    },
150
151    findIntersection: function(range) {
152      if (this.isEmpty || range.isEmpty)
153        return new Range();
154
155      var min = Math.max(this.min, range.min);
156      var max = Math.min(this.max, range.max);
157
158      if (max < min)
159        return new Range();
160
161      return Range.fromExplicitRange(min, max);
162    },
163
164    toJSON: function() {
165      if (this.isEmpty_)
166        return {isEmpty: true};
167      return {
168        isEmpty: false,
169        max: this.max,
170        min: this.min
171      };
172    },
173
174    /**
175     * Returns a slice of the input array that intersects with this range. If
176     * the range does not have a min, it is treated as unbounded from below.
177     * Similarly, if max is undefined, the range is unbounded from above.
178     *
179     * @param {Array} array The array of elements to be filtered.
180     * @param {Funcation=} opt_keyFunc A function that extracts a numeric value,
181     *        to be used in comparisons, from an element of the array. If not
182     *        specified, array elements themselves will be used.
183     * @param {Object=} opt_this An optional this argument to be passed to
184     *        opt_keyFunc.
185     */
186    filterArray: function(array, opt_keyFunc, opt_this) {
187      if (this.isEmpty_)
188        return [];
189      // Binary search. |test| is a function that should return true when we
190      // need to explore the left branch and false to explore the right branch.
191      function binSearch(test) {
192        var i0 = 0;
193        var i1 = array.length;
194        while (i0 < i1 - 1) {
195          var i = Math.trunc((i0 + i1) / 2);
196          if (test(i))
197            i1 = i;  // Explore the left branch.
198          else
199            i0 = i;  // Explore the right branch.
200        }
201        return i1;
202      }
203
204      var keyFunc = opt_keyFunc || tr.b.identity;
205      function getValue(index) {
206        return keyFunc.call(opt_this, array[index]);
207      }
208
209      var first = binSearch(function(i) {
210        return this.min_ === undefined || this.min_ <= getValue(i);
211      }.bind(this));
212      var last = binSearch(function(i) {
213        return this.max_ !== undefined && this.max_ < getValue(i);
214      }.bind(this));
215      return array.slice(first, last);
216    }
217  };
218
219  Range.fromDict = function(d) {
220    if (d.isEmpty === true) {
221      return new Range();
222    } else if (d.isEmpty === false) {
223      var range = new Range();
224      range.min = d.min;
225      range.max = d.max;
226      return range;
227    } else {
228      throw new Error('Not a range');
229    }
230  };
231
232  Range.fromExplicitRange = function(min, max) {
233    var range = new Range();
234    range.min = min;
235    range.max = max;
236    return range;
237  };
238
239  Range.compareByMinTimes = function(a, b) {
240    if (!a.isEmpty && !b.isEmpty)
241      return a.min_ - b.min_;
242
243    if (a.isEmpty && !b.isEmpty)
244      return -1;
245
246    if (!a.isEmpty && b.isEmpty)
247      return 1;
248
249    return 0;
250  };
251
252  return {
253    Range: Range
254  };
255});
256</script>
257