src/third_party/trace-viewer/third_party/tvcm/src/tvcm/interval_tree_test.html

   1 <!DOCTYPE html>
   2 <!--
   3 Copyright (c) 2014 The Chromium Authors. All rights reserved.
   4 Use of this source code is governed by a BSD-style license that can be
   5 found in the LICENSE file.
   6 -->
   7 <link rel="import" href="/tvcm/interval_tree.html">
   8 <script>
   9 'use strict';
  10
  11 tvcm.unittest.testSuite(function() {
  12   function buildSimpleTree() {
  13     var tree = new tvcm.IntervalTree(
  14         function(s) { return s.start; },
  15         function(e) { return e.end; });
  16
  17     tree.insert({start: 2}, {end: 6});
  18     tree.insert({start: 1}, {end: 3});
  19     tree.insert({start: 5}, {end: 7});
  20     tree.insert({start: 1}, {end: 5});
  21     tree.insert({start: 3}, {end: 5});
  22     tree.insert({start: 3}, {end: 5});
  23     tree.insert({start: 3}, {end: 6});
  24     tree.insert({start: 1}, {end: 1});
  25     tree.insert({start: 4}, {end: 8});
  26     tree.insert({start: 0}, {end: 2});
  27
  28     tree.updateHighValues();
  29
  30     return tree;
  31   }
  32
  33   test('findIntersection', function() {
  34     var tree = buildSimpleTree();
  35     var intersect = tree.findIntersection(2, 4);
  36
  37     // Intersect will hold an array of begin/end objects. As a simple way
  38     // to compare, we just grab the start and end values of those objects
  39     // and compare to what we expect to see.
  40     var values = intersect.map(function(v) { return [v[0].start, v[1].end]; });
  41     values.sort(function(a, b) {
  42       return (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
  43     });
  44
  45     var expected = [[1, 3], [1, 5], [2, 6], [3, 5], [3, 5], [3, 6]];
  46     assertEquals(6, values.length);
  47     assertEquals(JSON.stringify(expected), JSON.stringify(values));
  48   });
  49
  50   test('findIntersection_noMatching', function() {
  51     var tree = buildSimpleTree();
  52     var intersect = tree.findIntersection(9, 10);
  53     assertArrayEquals([], intersect);
  54   });
  55
  56   test('findIntersection_emptyTree', function() {
  57     var tree = new tvcm.IntervalTree();
  58     tree.updateHighValues();
  59
  60     var intersect = tree.findIntersection(2, 4);
  61     assertArrayEquals([], intersect);
  62   });
  63
  64   test('findIntersection_emptyInterval', function() {
  65     var tree = new tvcm.IntervalTree();
  66     tree.updateHighValues();
  67
  68     assertThrows(function() {
  69       tree.findIntersection();
  70     });
  71     assertThrows(function() {
  72       tree.findIntersection(1);
  73     });
  74     assertThrows(function() {
  75       tree.findIntersection('a', 'b');
  76     });
  77   });
  78
  79   test('insert', function() {
  80     var tree = new tvcm.IntervalTree(
  81         function(s) { return s.start; },
  82         function(e) { return e.end; });
  83
  84     assertEquals(0, tree.size);
  85
  86     tree.insert({start: 1}, {end: 4});
  87     tree.insert({start: 3}, {end: 5});
  88     tree.updateHighValues();
  89
  90     var outTree = {
  91       'left': {
  92         'node': [1, 4]
  93       },
  94       'node': [3, 5]
  95     };
  96
  97     assertEquals(2, tree.size);
  98     assertEquals(JSON.stringify(outTree), JSON.stringify(tree.dump_()));
  99   });
 100
 101   test('insert_withoutEnd', function() {
 102     var tree = new tvcm.IntervalTree(
 103         function(s) { return s.start; },
 104         function(e) { return e.end; });
 105
 106     assertEquals(0, tree.size);
 107
 108     tree.insert({start: 3, end: 5});
 109     tree.insert({start: 1, end: 4});
 110     tree.updateHighValues();
 111
 112     var outTree = {
 113       'left': {
 114         'node': [1, 4]
 115       },
 116       'node': [3, 5]
 117     };
 118
 119     assertEquals(2, tree.size);
 120     assertEquals(JSON.stringify(outTree), JSON.stringify(tree.dump_()));
 121   });
 122
 123   test('insert_balancesTree', function() {
 124     var tree = new tvcm.IntervalTree(
 125         function(s) { return s.start; },
 126         function(e) { return e.end; });
 127
 128     assertEquals(0, tree.size);
 129
 130     for (var i = 0; i < 10; ++i)
 131       tree.insert({start: i, end: 5});
 132     tree.updateHighValues();
 133
 134     var outTree = {
 135       'left': {
 136         'left': {
 137           'node': [0, 5]
 138         },
 139         'node': [1, 5],
 140         'right': {
 141           'node': [2, 5]
 142         }
 143       },
 144       'node': [3, 5],
 145       'right': {
 146         'left': {
 147           'left': {
 148             'node': [4, 5]
 149           },
 150           'node': [5, 5],
 151           'right': {
 152             'node': [6, 5]
 153           }
 154         },
 155         'node': [7, 5],
 156         'right': {
 157           'left': {
 158             'node': [8, 5]
 159           },
 160           'node': [9, 5]
 161         }
 162       }
 163     };
 164
 165     assertEquals(JSON.stringify(outTree, null, ' '),
 166         JSON.stringify(tree.dump_(), null, ' '));
 167   });
 168
 169   test('insert_withDuplicateIntervals', function() {
 170     var tree = new tvcm.IntervalTree(
 171         function(s) { return s.start; },
 172         function(e) { return e.end; });
 173
 174     assertEquals(0, tree.size);
 175
 176     tree.insert({start: 1}, {end: 4});
 177     tree.insert({start: 3}, {end: 5});
 178     tree.insert({start: 3}, {end: 5});
 179     tree.insert({start: 3}, {end: 6});
 180     tree.updateHighValues();
 181
 182     var outTree = {
 183       'left': {
 184         'node': [1, 4]
 185       },
 186       'node': [[3, 5], [3, 5], [3, 6]]
 187     };
 188
 189     assertEquals(4, tree.size);
 190     assertEquals(JSON.stringify(outTree), JSON.stringify(tree.dump_()));
 191   });
 192
 193   test('insert_updatesHighValues', function() {
 194     var tree = buildSimpleTree();
 195
 196     var expected = [
 197       [undefined, undefined],
 198       [2, undefined],
 199       [5, 8],
 200       [undefined, undefined],
 201       [6, 7],
 202       [undefined, undefined]
 203     ];
 204
 205     var result = [];
 206     function walk(node) {
 207       if (node === undefined)
 208         return;
 209
 210       walk(node.leftNode);
 211       result.push([node.maxHighLeft, node.maxHighRight]);
 212       walk(node.rightNode);
 213     }
 214     walk(tree.root);
 215
 216     assertEquals(JSON.stringify(expected), JSON.stringify(result));
 217   });
 218 });
 219 </script>