src/third_party/trace-viewer/src/base/interval_tree_test.js

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