sorted_array_utils_test.html revision 4a4f2fe02baf385f6c24fc98c6e17bf6ac5e0724 
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<link rel="import" href="/tracing/base/sorted_array_utils.html">
8<script>
9'use strict';
10
11tr.b.unittest.testSuite(function() {
12  var ArrayOfIntervals = function(array) {
13    this.array = array;
14  }
15
16  ArrayOfIntervals.prototype = {
17
18    get: function(index) {
19      return this.array[index];
20    },
21
22    findLowElementIndex: function(ts) {
23      return tr.b.findLowIndexInSortedArray(
24          this.array,
25          function(x) { return x.lo; },
26          ts);
27    },
28
29    findIntervalIndex: function(ts) {
30      return tr.b.findIndexInSortedIntervals(
31          this.array,
32          function(x) { return x.lo; },
33          function(x) { return x.hi - x.lo; },
34          ts);
35    },
36
37    findIndexInClosedIntervals: function(ts) {
38      return tr.b.findIndexInSortedClosedIntervals(
39          this.array,
40          function(x) { return x.lo; },
41          function(x) { return x.hi; },
42          ts);
43    },
44
45    findIntersectingIntervals: function(tsA, tsB) {
46      var array = this.array;
47      var result = [];
48      tr.b.iterateOverIntersectingIntervals(
49          this.array,
50          function(x) { return x.lo; },
51          function(x) { return x.hi - x.lo; },
52          tsA,
53          tsB,
54          function(x) { result.push(array.indexOf(x)); });
55      return result;
56    },
57
58    findClosestElement: function(ts, tsDiff) {
59      return tr.b.findClosestElementInSortedArray(
60          this.array,
61          function(x) { return x.lo; },
62          ts,
63          tsDiff);
64    },
65
66    findClosestInterval: function(ts, tsDiff) {
67      return tr.b.findClosestIntervalInSortedIntervals(
68          this.array,
69          function(x) { return x.lo; },
70          function(x) { return x.hi; },
71          ts,
72          tsDiff);
73    }
74  };
75
76  test('findLowElementIndex', function() {
77    var array = new ArrayOfIntervals([
78      {lo: 10, hi: 15},
79      {lo: 20, hi: 30}
80    ]);
81
82    assert.equal(array.findLowElementIndex(-100), 0);
83    assert.equal(array.findLowElementIndex(0), 0);
84    assert.equal(array.findLowElementIndex(10), 0);
85
86    assert.equal(array.findLowElementIndex(10.1), 1);
87    assert.equal(array.findLowElementIndex(15), 1);
88    assert.equal(array.findLowElementIndex(20), 1);
89
90    assert.equal(array.findLowElementIndex(20.1), 2);
91    assert.equal(array.findLowElementIndex(21), 2);
92    assert.equal(array.findLowElementIndex(100), 2);
93  });
94
95  test('findIntervalIndex', function() {
96    var array = new ArrayOfIntervals([
97      {lo: 10, hi: 15},
98      {lo: 20, hi: 30}
99    ]);
100
101    assert.equal(array.findIntervalIndex(0), -1);
102    assert.equal(array.findIntervalIndex(9.9), -1);
103
104    assert.equal(array.findIntervalIndex(10), 0);
105    assert.equal(array.findIntervalIndex(12), 0);
106    assert.equal(array.findIntervalIndex(14.9), 0);
107
108    assert.equal(array.findIntervalIndex(20), 1);
109    assert.equal(array.findIntervalIndex(21), 1);
110    assert.equal(array.findIntervalIndex(29.99), 1);
111
112    assert.equal(array.findIntervalIndex(30), 2);
113    assert.equal(array.findIntervalIndex(40), 2);
114
115
116    // misses, in between the intervals, return array length
117    assert.equal(array.findIntervalIndex(15), 2);
118    assert.equal(array.findIntervalIndex(19.9), 2);
119  });
120
121  test('findClosedIntervalIndex', function() {
122    var array = new ArrayOfIntervals([
123      {lo: 10, hi: 15},
124      {lo: 15, hi: 20},
125      {lo: 21, hi: 25}
126    ]);
127
128    assert.equal(array.findIndexInClosedIntervals(0), -1);
129    assert.equal(array.findIndexInClosedIntervals(9.999), -1);
130    assert.equal(array.findIndexInClosedIntervals(10), 0);
131    assert.equal(array.findIndexInClosedIntervals(14), 0);
132    assert.equal(array.findIndexInClosedIntervals(15), 0);
133    assert.equal(array.findIndexInClosedIntervals(15.00001), 1);
134    assert.equal(array.findIndexInClosedIntervals(20.5), 3);
135    assert.equal(array.findIndexInClosedIntervals(22), 2);
136    assert.equal(array.findIndexInClosedIntervals(25), 2);
137    assert.equal(array.findIndexInClosedIntervals(25.00001), 3);
138  });
139
140  test('findClosedInEmptyArray', function() {
141    var array = new ArrayOfIntervals([]);
142    assert.equal(array.findIndexInClosedIntervals(0), 0);
143  });
144
145  test('findIntersectingIntervals', function() {
146    var array = new ArrayOfIntervals([
147      {lo: 10, hi: 15},
148      {lo: 20, hi: 30}
149    ]);
150
151    assert.deepEqual(array.findIntersectingIntervals(0, 0), []);
152    assert.deepEqual(array.findIntersectingIntervals(100, 0), []);
153    assert.deepEqual(array.findIntersectingIntervals(0, 10), []);
154
155    assert.deepEqual(array.findIntersectingIntervals(0, 10.1), [0]);
156    assert.deepEqual(array.findIntersectingIntervals(5, 15), [0]);
157    assert.deepEqual(array.findIntersectingIntervals(15, 20), [0]);
158
159    assert.deepEqual(array.findIntersectingIntervals(15.1, 20), []);
160
161    assert.deepEqual(array.findIntersectingIntervals(15.1, 20.1), [1]);
162    assert.deepEqual(array.findIntersectingIntervals(20, 30), [1]);
163    assert.deepEqual(array.findIntersectingIntervals(30, 100), [1]);
164
165    assert.deepEqual(array.findIntersectingIntervals(0, 100), [0, 1]);
166    assert.deepEqual(array.findIntersectingIntervals(15, 20.1), [0, 1]);
167  });
168
169  test('findClosestElement', function() {
170    var array = new ArrayOfIntervals([
171      {lo: 10, hi: 15},
172      {lo: 20, hi: 30}
173    ]);
174
175    // Test the helper method first.
176    assert.isUndefined(array.get(-1));
177    assert.equal(array.get(0), array.array[0]);
178    assert.equal(array.get(1), array.array[1]);
179    assert.isUndefined(array.get(2));
180
181    assert.isNull(array.findClosestElement(0, 0));
182    assert.isNull(array.findClosestElement(0, 9.9));
183    assert.isNull(array.findClosestElement(10, -10));
184
185    assert.equal(array.get(0), array.findClosestElement(0, 10));
186    assert.equal(array.get(0), array.findClosestElement(8, 5));
187    assert.equal(array.get(0), array.findClosestElement(10, 0));
188    assert.equal(array.get(0), array.findClosestElement(12, 2));
189
190    assert.isNull(array.findClosestElement(15, 3));
191    assert.isNotNull(array.findClosestElement(15, 5));
192
193    assert.equal(array.get(1), array.findClosestElement(19, 1));
194    assert.equal(array.get(1), array.findClosestElement(20, 0));
195    assert.equal(array.get(1), array.findClosestElement(30, 15));
196
197    assert.isNull(array.findClosestElement(30, 9.9));
198    assert.isNull(array.findClosestElement(100, 50));
199  });
200
201  test('findClosestInterval', function() {
202    var array = new ArrayOfIntervals([
203      {lo: 10, hi: 15},
204      {lo: 20, hi: 30}
205    ]);
206
207    assert.isNull(array.findClosestInterval(0, 0));
208    assert.isNull(array.findClosestInterval(0, 9.9));
209    assert.isNull(array.findClosestInterval(0, -100));
210
211    assert.equal(array.get(0), array.findClosestInterval(0, 10));
212    assert.equal(array.get(0), array.findClosestInterval(10, 0));
213    assert.equal(array.get(0), array.findClosestInterval(12, 3));
214    assert.equal(array.get(0), array.findClosestInterval(12, 100));
215
216    assert.equal(array.get(0), array.findClosestInterval(13, 3));
217    assert.equal(array.get(0), array.findClosestInterval(13, 20));
218    assert.equal(array.get(0), array.findClosestInterval(15, 0));
219
220    assert.isNull(array.findClosestInterval(17.5, 0));
221    assert.isNull(array.findClosestInterval(17.5, 2.4));
222    assert.isNotNull(array.findClosestInterval(17.5, 2.5));
223    assert.isNotNull(array.findClosestInterval(17.5, 10));
224
225    assert.equal(array.get(1), array.findClosestInterval(19, 2));
226    assert.equal(array.get(1), array.findClosestInterval(20, 0));
227    assert.equal(array.get(1), array.findClosestInterval(24, 100));
228    assert.equal(array.get(1), array.findClosestInterval(26, 100));
229
230    assert.equal(array.get(1), array.findClosestInterval(30, 0));
231    assert.equal(array.get(1), array.findClosestInterval(35, 10));
232    assert.equal(array.get(1), array.findClosestInterval(50, 100));
233
234    assert.isNull(array.findClosestInterval(50, 19));
235    assert.isNull(array.findClosestInterval(100, 50));
236    assert.isNull(array.findClosestInterval(50, -100));
237  });
238});
239</script>
240