1<!DOCTYPE html> 2<!-- 3Copyright 2016 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 10<script> 11'use strict'; 12 13/** 14 * @fileoverview Multi-dimensional view data structure. 15 * 16 * A multi-dimensional view provides a hierarchical representation of a 17 * collection of multi-dimensional paths with associated scalar values. Unlike 18 * separate single-dimensional views (e.g. one tree for each dimension), 19 * multi-dimensional views facilitate aggregation over combinations of 20 * substrings of the path dimensions (rather than just substrings of a single 21 * path dimension). 22 * 23 * Every view consists of multi-dimensional nodes (see MultiDimensionalViewNode 24 * for more details). This file also provides a builder class for constructing 25 * top-down and bottom-up representations of arbitrary collections of 26 * multi-dimensional paths (see MultiDimensionalViewBuilder for more details). 27 * 28 * Example: Given the following collection of two dimensional paths: 29 * 30 * <----------- dimension 0 ------------> <-- dimension 1 --> 31 * [['Loop::Run()', 'Execute()', 'Call()'], ['Object', 'View']]: total=1 32 * [['Loop::Run()', 'Execute()', 'Call()'], ['Object', 'Widget']]: total=2 33 * [['Loop::Run()', 'Execute()', 'Load()'], ['Object']]: total=4 34 * [['Loop::Run()', 'Execute()'], ['int']]: total=8 35 * [['Loop::Run()'], ['Object', 'Window']]: total=16 36 * [['Loop::Stop()'], ['Object']]: total=32 37 * 38 * a multi-dimensional view provides a recursive breakdown of the aggregated 39 * values, e.g.: 40 * 41 * (root): total=63 42 * | 43 * | break down by 0th dimension 44 * v 45 * Loop::Run(): total=31 46 * | 47 * | break down by 0th dimension 48 * v 49 * Execute(): total=15 50 * | 51 * | break down by 1st dimension 52 * v 53 * Object: total=7 54 * | 55 * | break down by 0th dimension again 56 * v 57 * Call(): total=3 58 * | 59 * | break down by 1st dimension again 60 * v 61 * View: total=1 62 * 63 * Observe that the recursive breakdown above is over both dimensions. 64 * Furthermore, the underlying single-dimension paths (Loop::Run() -> Execute() 65 * -> Call() and Object -> View) can be arbitrarily interleaved in the 66 * breakdown. 67 */ 68tr.exportTo('tr.b', function() { 69 70 /** 71 * Node of a multi-dimensional view. 72 * 73 * The structure of a view is encoded in the nodes using links to their 74 * children wrt each dimension. The diagram below shows how the nodes 75 * corresponding to the following four two-dimensional view paths: 76 * 77 * 1. [['A', 'B'], ['1', '2']] 78 * 2. [['A', 'C'], ['1', '2']] 79 * 3. [['A', 'B'], ['1', '3']] 80 * 4. [['A', 'C'], ['1', '3']] 81 * 82 * can be reached from the root of a two-dimensional view using these links 83 * ('*' stands for undefined): 84 * 85 * +---------------------+ 86 * | title: [*,*] (root) | 87 * +---------------------+ 88 * children wrt children wrt 89 * 0th dimension 1st dimension 90 * | : 91 * _______A________| :........1......... 92 * | : 93 * v v 94 * +--------------+ +--------------+ 95 * | title: [A,*] | | title: [*,1] | 96 * +--------------+ +--------------+ 97 * children wrt children wrt children wrt children wrt 98 * 0th dimension 1st dimension 0th dimension 1st dimension 99 * | | :.....1...... _____A_____| : : 100 * _B_| |__C__ : | ...2..: :.3.. 101 * | | : | : : 102 * v v v v v v 103 * +-------+ +-------+ +-------+ +-------+ +-------+ 104 * | [B,*] | | [C,*] | | [A,1] | | [*,2] | | [*,3] | 105 * +-------+ +-------+ +-------+ +-------+ +-------+ 106 * : ___:_____B______| | : :......3.....|.... | 107 * :.1.. | :.1.. __C___| :...2... _A_| : _A_| 108 * : | : | : | : | 109 * v v v v v v v v 110 * +-------+ +-------+ +-------+ +-------+ 111 * | [B,1] | | [C,1] | | [A,2] | | [A,3] | 112 * +-------+ +-------+ +-------+ +-------+ 113 * : : : :.......3.......||.......... || 114 * : :..3....:................ BC : BC 115 * : ______:_______________:___|| : || 116 * 2 | 2 _______:____| ______:___|| 117 * : | : | : | : | 118 * v v v v v v v v 119 * +----------+ +----------+ +----------+ +----------+ 120 * | [B,2] | | [C,2] | | [B,3] | | [C,3] | 121 * | (node 1) | | (node 2) | | (node 3) | | (node 4) | 122 * +----------+ +----------+ +----------+ +----------+ 123 * 124 * The self/total value of a node represents the aggregated value of all 125 * paths (in the collection from which the view was built) matching the node 126 * excluding/including the node's descendants. 127 * 128 * Terminology examples: 129 * 130 * - Children of [A,*] wrt 0th dimension: [B,*], [C,*] 131 * - Children of [A,*] (wrt all dimensions): [B,*], [C,*], [A,1] 132 * - Descendants of [A,*] wrt 1st dimension: [A,1], [A,2], [A,3] 133 * - Single-dimensional descendants of [A,*]: [A,1], [A,2], [A,3], [B,*], 134 * [C,*] 135 * - Descendants of [A,*] (wrt all dimensions): [A,1], [A,2], [A,3], [B,*], 136 * [C,*], [B,1], [C,1], [B,2], [C,2], [B,3], [C,3] 137 * 138 * @{constructor} 139 */ 140 function MultiDimensionalViewNode(title, isLowerBound) { 141 // List of titles of this node wrt each dimension. 142 this.title = title; 143 144 // Map from child name to child node for each dimension. 145 var dimensions = title.length; 146 this.children = new Array(dimensions); 147 for (var i = 0; i < dimensions; i++) 148 this.children[i] = new Map(); 149 150 this.total = 0; 151 this.self = 0; 152 153 // Flag whether the values of this node are only lower bounds (i.e. 154 // aggregated from children rather than provided directly). 155 this.isLowerBound = !!isLowerBound; 156 } 157 158 MultiDimensionalViewNode.prototype = { 159 /** Duck type <tr-ui-b-table> rows. */ 160 get subRows() { 161 return tr.b.mapValues(this.children[0]); 162 } 163 }; 164 165 /** 166 * Types of multi-dimensional views provided by MultiDimensionalViewBuilder. 167 * 168 * @enum 169 */ 170 var MultiDimensionalViewType = { 171 TOP_DOWN_TREE_VIEW: 0, 172 TOP_DOWN_HEAVY_VIEW: 1, 173 BOTTOM_UP_HEAVY_VIEW: 2 174 }; 175 176 /** 177 * Builder for multi-dimensional views. 178 * 179 * Given a collection of multi-dimensional paths, a builder can be used to 180 * construct the following three representations of the paths: 181 * 182 * 1. Top-down tree view 183 * A multi-dimensional path in the view corresponds to all paths in the 184 * collection that have it as their prefix. 185 * 186 * 2. Top-down heavy view 187 * A multi-dimensional path in the view corresponds to all paths in the 188 * collection that have it as their substring 189 * 190 * 3. Bottom-up heavy view 191 * A multi-dimensional path in the view corresponds to all paths in the 192 * collection that have it as their substring reversed. 193 * 194 * For example, the following collection of 2-dimensional paths: 195 * 196 * 2-dimensional path | self 197 * Time (0th dimension) | Activity (1st dimension) | value 198 * ========================+========================+======= 199 * Saturday | Cooking | 1 h 200 * Saturday | Sports -> Football | 2 h 201 * Sunday | Sports -> Basketball | 3 h 202 * 203 * gives rise to the following top-down tree view, which aggregates the 204 * scalar values over prefixes of the given paths: 205 * 206 * +---------+ 207 * | * | 208 * | * | 209 * | self=0 | 210 * | total=6 | 211 * +---------+ 212 * | : | : 213 * _________Cooking_______| : | :............Sunday............ 214 * | : | : 215 * | ...Saturday..: |_Sports_ : 216 * | : | : 217 * v v v v 218 * +---------+ +---------+ +---------+ +---------+ 219 * | * | | Sat | | * | | Sun | 220 * | Cooking | | * | | Sports | | * | 221 * | self=0 | | self=0 | | self=0 | | self=0 | 222 * | total=1 | | total=3 | | total=5 | | total=3 | 223 * +---------+ +---------+ +---------+ +---------+ 224 * : | | : | | : | 225 * Saturday | Sports : | | : Sports 226 * : | | .....Saturday....: | | :.....Sunday....... | 227 * : _Cook_| | : _Foot_| |_Bask_ : | 228 * : | | : | | : | 229 * v v v v v v v v 230 * +---------+ +---------+ +------------+ +--------------+ +---------+ 231 * | Sat | | Sat | | * | | * | | Sun | 232 * | Cooking | | Sports | | S/Football | | S/Basketball | | Sports | 233 * | self=1 | | self=0 | | self=0 | | self=0 | | self=0 | 234 * | total=1 | | total=2 | | total=2 | | total=3 | | total=3 | 235 * +---------+ +---------+ +------------+ +--------------+ +---------+ 236 * | : : | 237 * |_Foot_ ..Sat.: :.Sun.. _Bask_| 238 * | : : | 239 * v v v v 240 * +------------+ +--------------+ 241 * | Sat | | Sun | 242 * | S/Football | | S/Basketball | 243 * | self=2 | | self=3 | 244 * | total=2 | | total=3 | 245 * +------------+ +--------------+ 246 * 247 * To build a multi-dimensional view of a collection of multi-dimensional 248 * paths, you create a builder, add the paths to it and then use it to 249 * construct the view. For example, the following code generates the 250 * 2-dimensional top-down tree view shown above: 251 * 252 * var builder = new MultiDimensionalViewBuilder(2); 253 * builder.addPath([['Saturday'], ['Cooking']], 1, SELF); 254 * builder.addPath([['Saturday'], ['Sports', 'Football']], 2, SELF); 255 * builder.addPath([['Sunday'], ['Sports', 'Basketball']], 3, SELF); 256 * var treeViewRoot = builder.buildTopDownTreeView(); 257 * 258 * The heavy views can be constructed analogously (by calling 259 * buildTopDownHeavyView() or buildBottomUpHeavyView() at the end instead). 260 * 261 * Note that the same builder can be used to construct both the tree and 262 * heavy views (for the same collection of paths). However, no more paths can 263 * be added once either view has been built. 264 * 265 * @{constructor} 266 */ 267 function MultiDimensionalViewBuilder(dimensions) { 268 if (dimensions < 0) 269 throw new Error('Dimensions must be non-negative'); 270 this.dimensions_ = dimensions; 271 272 this.buildRoot_ = this.createRootNode_(); 273 this.topDownTreeViewRoot_ = undefined; 274 this.topDownHeavyViewRoot_ = undefined; 275 this.bottomUpHeavyViewNode_ = undefined; 276 277 this.maxDimensionDepths_ = new Array(dimensions); 278 for (var d = 0; d < dimensions; d++) 279 this.maxDimensionDepths_[d] = 0; 280 } 281 282 /** @{enum} */ 283 MultiDimensionalViewBuilder.ValueKind = { 284 SELF: 0, 285 TOTAL: 1 286 }; 287 288 MultiDimensionalViewBuilder.prototype = { 289 /** 290 * Add a value associated with a multi-dimensional path to the tree. 291 * 292 * The path must have the same number of dimensions as the builder. Its 293 * elements must be single-dimension paths (lists of strings) of arbitrary 294 * length (empty for the root of the given dimension). Starting from the 295 * root of the tree, each single-dimension path is traversed from left to 296 * right to reach the node corresponding to the whole path. 297 * 298 * The builder supports adding both kinds of values (self/total) for an 299 * arbitrary multi-dimensional path. The rationale for adding a total value 300 * (in addition to/instead of a self value) is to cater for missing 301 * sub-paths. Example: Consider the following collection of 302 * single-dimensional paths: 303 * 304 * [['Loop::Run()', 'Execute()', 'FunctionBig']]: self=99000 305 * [['Loop::Run()', 'Execute()', 'FunctionSmall1']]: self=1 306 * [['Loop::Run()', 'Execute()', 'FunctionSmall2']]: self=1 307 * ... 308 * [['Loop::Run()', 'Execute()', 'FunctionSmall1000']]: self=1 309 * 310 * If we required that only self values could be added to the builder, then 311 * all of the 1001 paths would need to be provided (most likely in a trace) 312 * to obtain the correct total of [['Loop::Run()', 'Execute()']]. However, 313 * since we allow adding total values as well, only the following 2 paths 314 * need to be provided to get the correct numbers explaining 99% of the 315 * aggregated total value: 316 * 317 * [['Loop::Run()', 'Execute()']]: total=100000 318 * [['Loop::Run()', 'Execute()', 'FunctionBig']]: self=99000 319 * 320 * In other words, the long tail containing 1000 small paths need not be 321 * dumped (greatly reducing the size of a trace where applicable). 322 * 323 * Important: No paths can be added to a builder once either view has been 324 * built! 325 */ 326 addPath: function(path, value, valueKind) { 327 if (this.buildRoot_ === undefined) { 328 throw new Error( 329 'Paths cannot be added after either view has been built'); 330 } 331 if (path.length !== this.dimensions_) 332 throw new Error('Path must be ' + this.dimensions_ + '-dimensional'); 333 334 var node = this.buildRoot_; 335 336 for (var d = 0; d < path.length; d++) { 337 var singleDimensionPath = path[d]; 338 var singleDimensionPathLength = singleDimensionPath.length; 339 this.maxDimensionDepths_[d] = 340 Math.max(this.maxDimensionDepths_[d], singleDimensionPathLength); 341 for (var i = 0; i < singleDimensionPathLength; i++) 342 node = this.getOrCreateChildNode_(node, d, singleDimensionPath[i]); 343 } 344 345 switch (valueKind) { 346 case MultiDimensionalViewBuilder.ValueKind.SELF: 347 node.self += value; 348 break; 349 350 case MultiDimensionalViewBuilder.ValueKind.TOTAL: 351 node.total += value; 352 break; 353 354 default: 355 throw new Error('Invalid value kind: ' + valueKind); 356 } 357 358 node.isLowerBound = false; 359 }, 360 361 buildView: function(viewType) { 362 switch (viewType) { 363 case MultiDimensionalViewType.TOP_DOWN_TREE_VIEW: 364 return this.buildTopDownTreeView(); 365 case MultiDimensionalViewType.TOP_DOWN_HEAVY_VIEW: 366 return this.buildTopDownHeavyView(); 367 case MultiDimensionalViewType.BOTTOM_UP_HEAVY_VIEW: 368 return this.buildBottomUpHeavyView(); 369 default: 370 throw new Error('Unknown multi-dimensional view type: ' + viewType); 371 } 372 }, 373 374 /** 375 * Build the top-down tree view of the multi-dimensional view. 376 * 377 * Note that no more paths can be added to the builder once either view has 378 * been built. 379 */ 380 buildTopDownTreeView: function() { 381 if (this.topDownTreeViewRoot_ === undefined) { 382 var treeViewRoot = this.buildRoot_; 383 this.buildRoot_ = undefined; 384 385 this.setUpMissingChildRelationships_(treeViewRoot, 386 0 /* firstDimensionToSetUp */); 387 this.finalizeTotalValues_(treeViewRoot, 388 0 /* firstDimensionToFinalize */, 389 new WeakMap() /* dimensionalSelfSumsMap */); 390 391 this.topDownTreeViewRoot_ = treeViewRoot; 392 } 393 394 return this.topDownTreeViewRoot_; 395 }, 396 397 /** 398 * Build the top-down heavy view of the multi-dimensional view. 399 * 400 * Note that no more paths can be added to the builder once either view has 401 * been built. 402 */ 403 buildTopDownHeavyView: function() { 404 if (this.topDownHeavyViewRoot_ === undefined) { 405 this.topDownHeavyViewRoot_ = this.buildGenericHeavyView_( 406 this.addDimensionToTopDownHeavyViewNode_.bind(this)); 407 } 408 return this.topDownHeavyViewRoot_; 409 }, 410 411 /** 412 * Build the bottom-up heavy view of the multi-dimensional view. 413 * 414 * Note that no more paths can be added to the builder once either view has 415 * been built. 416 */ 417 buildBottomUpHeavyView: function() { 418 if (this.bottomUpHeavyViewNode_ === undefined) { 419 this.bottomUpHeavyViewNode_ = this.buildGenericHeavyView_( 420 this.addDimensionToBottomUpHeavyViewNode_.bind(this)); 421 } 422 return this.bottomUpHeavyViewNode_; 423 }, 424 425 createRootNode_: function() { 426 return new MultiDimensionalViewNode( 427 new Array(this.dimensions_) /* title */, true /* isLowerBound */); 428 }, 429 430 getOrCreateChildNode_: function( 431 parentNode, dimension, childDimensionTitle) { 432 if (dimension < 0 || dimension >= this.dimensions_) 433 throw new Error('Invalid dimension'); 434 435 var dimensionChildren = parentNode.children[dimension]; 436 437 var childNode = dimensionChildren.get(childDimensionTitle); 438 if (childNode !== undefined) 439 return childNode; 440 441 var childTitle = parentNode.title.slice(); 442 childTitle[dimension] = childDimensionTitle; 443 childNode = new MultiDimensionalViewNode( 444 childTitle, true /* isLowerBound */); 445 dimensionChildren.set(childDimensionTitle, childNode); 446 447 return childNode; 448 }, 449 450 /** 451 * Set up missing child relationships. 452 * 453 * When an arbitrary multi-dimensional path [path1, path2, ..., pathN] is 454 * added to the build tree (see addPath), only the nodes on the path1 -> 455 * path2 -> ... -> pathN chain are created (i.e. no interleavings of the 456 * single-dimensional paths are added to the tree). This method recursively 457 * adds all the missing paths. 458 * 459 * Two-dimensional example: 460 * 461 * Initial build tree . After path . After missing child 462 * (root only) . [[A, B], [1, 2]] . relationships were 463 * . was added . set up 464 * . . 465 * +---+ . +---+ . +---+ 466 * |*,*| . |*,*| . |*,*| 467 * +---+ . +---+ . +---+ 468 * . A . A 1 469 * . | . | : 470 * . v . v V 471 * . +---+ . +---+ +---+ 472 * . |A,*| . |A,*| |*,1| 473 * . +---+ . +---+ +---+ 474 * . B . B 1 A 2 475 * . | . | : | : 476 * . v . v v v v 477 * . +---+ . +---+ +---+ +---+ 478 * . |B,*| . |B,*| |A,1| |*,2| 479 * . +---+ . +---+ +---+ +---+ 480 * . 1 . 1 B 2 A 481 * . : . : | : | 482 * . v . v v v v 483 * . +---+ . +---+ +---+ 484 * . |B,1| . |B,1| |A,2| 485 * . +---+ . +---+ +---+ 486 * . 2 . 2 B 487 * . : . : | 488 * . v . v V 489 * . +---+ . +---+ 490 * . |B,2| . |B,2| 491 * . +---+ . +---+ 492 */ 493 setUpMissingChildRelationships_: function(node, firstDimensionToSetUp) { 494 // Missing child relationships of this node wrt dimensions 0, ..., 495 // (firstDimensionToSetUp - 1) and all descendants of the associated 496 // children have already been set up. Now we do the same for dimensions 497 // firstDimensionToSetUp, ..., (this.dimensions_ - 1). 498 for (var d = firstDimensionToSetUp; d < this.dimensions_; d++) { 499 // Step 1. Gather the names of all children wrt the current dimension. 500 var currentDimensionChildTitles = new Set(node.children[d].keys()); 501 for (var i = 0; i < d; i++) { 502 for (var previousDimensionChildNode of node.children[i].values()) { 503 for (var previousDimensionGrandChildTitle of 504 previousDimensionChildNode.children[d].keys()) { 505 currentDimensionChildTitles.add(previousDimensionGrandChildTitle); 506 } 507 } 508 } 509 510 // Step 2. Add missing children wrt the current dimension and 511 // recursively set up its missing child relationships. 512 for (var currentDimensionChildTitle of currentDimensionChildTitles) { 513 // Add a missing child (if it doesn't exist). 514 var currentDimensionChildNode = 515 this.getOrCreateChildNode_(node, d, currentDimensionChildTitle); 516 517 // Set-up child relationships (of the child node) wrt dimensions 0, 518 // ..., d - 1. 519 for (var i = 0; i < d; i++) { 520 for (var previousDimensionChildNode of node.children[i].values()) { 521 var previousDimensionGrandChildNode = 522 previousDimensionChildNode.children[d].get( 523 currentDimensionChildTitle); 524 if (previousDimensionGrandChildNode !== undefined) { 525 currentDimensionChildNode.children[i].set( 526 previousDimensionChildNode.title[i], 527 previousDimensionGrandChildNode); 528 } 529 } 530 } 531 532 // Set-up child relationships (of the child node) wrt dimensions d, 533 // ..., (this.dimensions_ - 1). 534 this.setUpMissingChildRelationships_(currentDimensionChildNode, d); 535 } 536 } 537 }, 538 539 /** 540 * Finalize the total values of a multi-dimensional tree. 541 * 542 * The intermediate builder tree, a node of which we want to finalize 543 * recursively, already has the right shape. The only thing that needs to 544 * be done is to propagate self and total values from subsumed child nodes 545 * in each dimension. 546 * 547 * To derive the expression for the lower bound on the total value, we rely 548 * on the following assumptions: 549 * 550 * 1. Each node's self value does NOT overlap with the self or total value 551 * of any other node. 552 * 553 * 2. The total values of a node's children wrt a single dimension (e.g. 554 * [path1/A, path2] and [path1/B, path2]) do NOT overlap. 555 * 556 * 3. The total values of a node's children wrt different dimensions 557 * (e.g. [path1/A, path2] and [path1, path2/1]) MIGHT overlap. 558 * 559 * As a consequence of assumptions 1 and 3, the total value of a node can 560 * be split into the part that cannot overlap (so-called "self-sum") and 561 * the part that can overlap (so-called "residual"): 562 * 563 * total(N) = selfSum(N) + residual(N) (A) 564 * 565 * where the self-sum is calculated as the sum of the node's self value 566 * plus the sum of its descendants' self values (summed over all 567 * dimensions): 568 * 569 * selfSum(N) = self(N) + sum over all descendants C of N { 570 * self (C) (B) 571 * } 572 * 573 * Observe that the residual of a node does not include any self value (of 574 * any node in the view). Furthermore, by assumption 2, we derive that the 575 * residuals of a node's children wrt a single dimension don't overlap. On 576 * the other hand, the residuals of a node's children wrt different 577 * dimensions might overlap. This gives us the following lower bound on the 578 * residual of a node: 579 * 580 * residual(N) >= minResidual(N) = max over dimensions D { 581 * sum over children C of N at dimension D { 582 * residual(C) (C) 583 * } 584 * }) 585 * 586 * By combining equation (A) and inequality (C), we get a lower bound on 587 * the total value of a node: 588 * 589 * total(N) >= selfSum(N) + minResidual(N) 590 * 591 * For example, given a two-dimensional node [path1, path2] with self value 592 * 10 and four children (2 wrt each dimension): 593 * 594 * Child | Self value | Total value 595 * ==================+============+============= 596 * [path1/A, path2] | 21 | 30 597 * [path1/B, path2] | 25 | 32 598 * [path1, path2/1] | 3 | 15 599 * [path1, path2/2] | 40 | 41 600 * 601 * and assuming that the children have no further descendants (i.e. their 602 * residual values are equal to the differences between their total and 603 * self values), the lower bound on the total value of [path1, path2] is: 604 * 605 * total([path1, path2]) 606 * >= selfSum([path1, path2]) + 607 * minResidual([path1, path2]) 608 * = self([path1, path2]) + 609 * sum over all descendants C of [path1, path2] { 610 * self (C) 611 * } + 612 * max over dimensions D { 613 * sum over children C of [path1, path2] at dimension D { 614 * residual(C) 615 * } 616 * } 617 * = self([path1, path2]) + 618 * ((self([path1/A, path2]) + self([path1/B, path2])) + 619 * (self([path1, path2/1]) + self([path1, path2/2]))) + 620 * max(residual([path1/A, path2]) + residual([path1/B, path2]), 621 * residual([path1, path2/1]) + residual([path1, path2/2])) 622 * = 10 + 623 * ((21 + 25) + (3 + 40)) + 624 * max((30 - 21) + (32 - 25), (15 - 3) + (41 - 40)) 625 * = 115 626 * 627 * To reduce the complexity of the calculation, we keep a temporary list of 628 * dimensional self-sums for each node that we have already visited. For a 629 * given node, the Kth element in the list is equal to the self size of the 630 * node plus the sum of self sizes of all its descendants wrt dimensions 0 631 * to K (inclusive). The list has two important properties: 632 * 633 * 1. The last element in the list is equal to the self-sum of the 634 * associated node (equation (B)). 635 * 636 * 2. The calculation of the list can be performed recursively using the 637 * lists of the associated node's children (avoids square complexity 638 * in the size of the graph): 639 * 640 * dimensionalSelfSum(N)[D] = 641 * self(N) + 642 * sum I = 0 to D { 643 * sum over children C of N at dimension I { 644 * dimensionalSelfSum(C)[I] 645 * } 646 * } 647 */ 648 finalizeTotalValues_: function( 649 node, firstDimensionToFinalize, dimensionalSelfSumsMap) { 650 var dimensionalSelfSums = new Array(this.dimensions_); 651 var maxChildResidualSum = 0; 652 var nodeSelfSum = node.self; 653 654 for (var d = 0; d < this.dimensions_; d++) { 655 var childResidualSum = 0; 656 for (var childNode of node.children[d].values()) { 657 if (d >= firstDimensionToFinalize) 658 this.finalizeTotalValues_(childNode, d, dimensionalSelfSumsMap); 659 var childNodeSelfSums = dimensionalSelfSumsMap.get(childNode); 660 nodeSelfSum += childNodeSelfSums[d]; 661 var residual = 662 childNode.total - childNodeSelfSums[this.dimensions_ - 1]; 663 childResidualSum += residual; 664 } 665 dimensionalSelfSums[d] = nodeSelfSum; 666 maxChildResidualSum = Math.max(maxChildResidualSum, childResidualSum); 667 } 668 669 node.total = Math.max(node.total, nodeSelfSum + maxChildResidualSum); 670 671 if (dimensionalSelfSumsMap.has(node)) 672 throw new Error('Internal error: Node finalized more than once'); 673 dimensionalSelfSumsMap.set(node, dimensionalSelfSums); 674 }, 675 676 /** 677 * Build a generic heavy view of the multi-dimensional view. 678 */ 679 buildGenericHeavyView_: function(treeViewNodeHandler) { 680 // 1. Clone the root node of the top-down tree view node (except 681 // children). 682 var treeViewRoot = this.buildTopDownTreeView(); 683 var heavyViewRoot = this.createRootNode_(); 684 heavyViewRoot.total = treeViewRoot.total; 685 heavyViewRoot.self = treeViewRoot.self; 686 heavyViewRoot.isLowerBound = treeViewRoot.isLowerBound; 687 688 // 2. Create recursion depth trackers (to avoid total value 689 // double-counting). 690 var recursionDepthTrackers = new Array(this.dimensions_); 691 for (var d = 0; d < this.dimensions_; d++) { 692 recursionDepthTrackers[d] = 693 new RecursionDepthTracker(this.maxDimensionDepths_[d], d); 694 } 695 696 // 3. Add all paths associated with the single-dimensional descendants of 697 // the top-down tree view root node to the heavy view root node 698 // (depending on the type of the target heavy view). 699 this.addDimensionsToGenericHeavyViewNode_(treeViewRoot, heavyViewRoot, 700 0 /* startDimension */, recursionDepthTrackers, 701 false /* previousDimensionsRecursive */, treeViewNodeHandler); 702 703 // 4. Set up missing child relationships. 704 this.setUpMissingChildRelationships_(heavyViewRoot, 705 0 /* firstDimensionToSetUp */); 706 707 return heavyViewRoot; 708 }, 709 710 /** 711 * Add all paths associated with the single-dimensional descendants of a 712 * top-down tree-view node wrt multiple dimensions to a generic heavy-view 713 * node (depending on the type of the target heavy view). 714 */ 715 addDimensionsToGenericHeavyViewNode_: function(treeViewParentNode, 716 heavyViewParentNode, startDimension, recursionDepthTrackers, 717 previousDimensionsRecursive, treeViewNodeHandler) { 718 for (var d = startDimension; d < this.dimensions_; d++) { 719 this.addDimensionDescendantsToGenericHeavyViewNode_(treeViewParentNode, 720 heavyViewParentNode, d, recursionDepthTrackers, 721 previousDimensionsRecursive, treeViewNodeHandler); 722 } 723 }, 724 725 /** 726 * Add all paths associated with the descendants of a top-down tree-view 727 * node wrt a single dimension to a generic heavy-view node (depending on 728 * the type of the target heavy view). 729 */ 730 addDimensionDescendantsToGenericHeavyViewNode_: function(treeViewParentNode, 731 heavyViewParentNode, currentDimension, recursionDepthTrackers, 732 previousDimensionsRecursive, treeViewNodeHandler) { 733 var treeViewChildren = treeViewParentNode.children[currentDimension]; 734 var recursionDepthTracker = recursionDepthTrackers[currentDimension]; 735 for (var treeViewChildNode of treeViewChildren.values()) { 736 recursionDepthTracker.push(treeViewChildNode); 737 738 // Add all paths associated with the child node to the heavy view-node 739 // parent node. 740 treeViewNodeHandler( 741 treeViewChildNode, heavyViewParentNode, currentDimension, 742 recursionDepthTrackers, previousDimensionsRecursive); 743 744 // Recursively add all paths associated with the descendants of the 745 // tree view child node wrt the current dimension to the heavy-view 746 // parent node. 747 this.addDimensionDescendantsToGenericHeavyViewNode_(treeViewChildNode, 748 heavyViewParentNode, currentDimension, recursionDepthTrackers, 749 previousDimensionsRecursive, treeViewNodeHandler); 750 751 recursionDepthTracker.pop(); 752 } 753 }, 754 755 /** 756 * Add a top-down tree-view child node together with its single-dimensional 757 * subtree to a top-down heavy-view parent node (tree-view node handler for 758 * top-down heavy view). 759 * 760 * Sample resulting top-down heavy view: 761 * 762 * +----------------+ +-----------------+ 763 * | source | | destination | 764 * | tree-view root | ===============> | heavy-view root | 765 * | self=0 | | self=0 | 766 * | total=48 | | total=48 | 767 * +----------------+ +-----------------+ 768 * | | ______| | |______ 769 * v v v v v 770 * +----------+ +----------+ +----------+ +----------+ +----------+ 771 * | A* | | B | | A*** | | B | | C | 772 * | self=10 | | self=12 | | self=13 | | self=13 | | self=2 | 773 * | total=30 | | total=18 | | total=30 | | total=34 | | total=7 | 774 * +----------+ +----------+ +----------+ +----------+ +----------+ 775 * | : : :......... 776 * v v v v 777 * +----------+ ............ ............ ............ 778 * | B | : B : : A : : C : 779 * | self=1 | : self=1 : : self=3 : : self=2 : 780 * | total=16 | : total=16 : : total=8 : : total=7 : 781 * +----------+ ............ ............ ............ 782 * | |________ : :......... 783 * v v v v 784 * +----------+ +----------+ ............ ............ 785 * | A** | | C | : A : : C : 786 * | self=3 | | self=2 | : self=3 : : self=2 : 787 * | total=8 | | total=7 | : total=8 : : total=7 : 788 * +----------+ +----------+ ............ ............ 789 * 790 * Observe that care needs to be taken when dealing with recursion to avoid 791 * double-counting, e.g. the total value of A** (8) was not added to the 792 * total value of A*** (30) because it is already included in the total 793 * value of A* (30) (which was also added to A***). That is why we need to 794 * keep track of the path we traversed along the current dimension (to 795 * determine whether total value should be added or not). 796 */ 797 addDimensionToTopDownHeavyViewNode_: function( 798 treeViewChildNode, heavyViewParentNode, currentDimension, 799 recursionDepthTrackers, previousDimensionsRecursive) { 800 this.addDimensionToTopDownHeavyViewNodeRecursively_(treeViewChildNode, 801 heavyViewParentNode, currentDimension, recursionDepthTrackers, 802 previousDimensionsRecursive, 1 /* subTreeDepth */); 803 }, 804 805 addDimensionToTopDownHeavyViewNodeRecursively_: function( 806 treeViewChildNode, heavyViewParentNode, currentDimension, 807 recursionDepthTrackers, previousDimensionsRecursive, subTreeDepth) { 808 var recursionDepthTracker = recursionDepthTrackers[currentDimension]; 809 var currentDimensionRecursive = 810 subTreeDepth <= recursionDepthTracker.recursionDepth; 811 var currentOrPreviousDimensionsRecursive = 812 currentDimensionRecursive || previousDimensionsRecursive; 813 814 var dimensionTitle = treeViewChildNode.title[currentDimension]; 815 var heavyViewChildNode = this.getOrCreateChildNode_( 816 heavyViewParentNode, currentDimension, dimensionTitle); 817 818 heavyViewChildNode.self += treeViewChildNode.self; 819 if (!currentOrPreviousDimensionsRecursive) 820 heavyViewChildNode.total += treeViewChildNode.total; 821 822 // Add the descendants of the tree-view child node wrt the next 823 // dimensions as children of the heavy-view child node. 824 this.addDimensionsToGenericHeavyViewNode_(treeViewChildNode, 825 heavyViewChildNode, currentDimension + 1, recursionDepthTrackers, 826 currentOrPreviousDimensionsRecursive, 827 this.addDimensionToTopDownHeavyViewNode_.bind(this)); 828 829 for (var treeViewGrandChildNode of 830 treeViewChildNode.children[currentDimension].values()) { 831 recursionDepthTracker.push(treeViewGrandChildNode); 832 833 // Recursively add the tree-view grandchild node to the heavy-view 834 // child node. 835 this.addDimensionToTopDownHeavyViewNodeRecursively_( 836 treeViewGrandChildNode, heavyViewChildNode, currentDimension, 837 recursionDepthTrackers, previousDimensionsRecursive, 838 subTreeDepth + 1); 839 840 recursionDepthTracker.pop(); 841 } 842 }, 843 844 /** 845 * Add a top-down tree-view child node together with all its ancestors wrt 846 * the given dimension as descendants of a bottom-up heavy-view parent node 847 * in the reverse order (tree-view node handler for bottom-up heavy view). 848 * 849 * Sample resulting bottom-up heavy view: 850 * 851 * +----------------+ +-----------------+ 852 * | source | | destination | 853 * | tree-view root | ===============> | heavy-view root | 854 * | self=0 | | self=0 | 855 * | total=48 | | total=48 | 856 * +----------------+ +-----------------+ 857 * | | ______| | |______ 858 * v v v v v 859 * +----------+ +----------+ +----------+ +----------+ +----------+ 860 * | A* | | B | | A*** | | B | | C | 861 * | self=10 | | self=12 | | self=13 | | self=13 | | self=2 | 862 * | total=30 | | total=18 | | total=30 | | total=34 | | total=7 | 863 * +----------+ +----------+ +----------+ +----------+ +----------+ 864 * | : : : 865 * v v v v 866 * +----------+ ............ ............ ............ 867 * | B# | : B : : A : : B## : 868 * | self=1 | : self=3 : : self=1 : : self=2 : 869 * | total=16 | : total=8 : : total=16 : : total=7 : 870 * +----------+ ............ ............ ............ 871 * | |________ : : 872 * v v v v 873 * +----------+ +----------+ ............ ............ 874 * | A** | | C | : A : : A : 875 * | self=3 | | self=2 | : self=3 : : self=2 : 876 * | total=8 | | total=7 | : total=8 : : total=7 : 877 * +----------+ +----------+ ............ ............ 878 * 879 * Similarly to the construction of the top-down heavy view, care needs to 880 * be taken when dealing with recursion to avoid double-counting, e.g. the 881 * total value of A** (8) was not added to the total value of A*** (30) 882 * because it is already included in the total value of A* (30) (which was 883 * also added to A***). That is why we need to keep track of the path we 884 * traversed along the current dimension (to determine whether total value 885 * should be added or not). 886 * 887 * Note that when we add an ancestor (B#) of a top-down tree-view node (C) 888 * to the bottom-up heavy view, the values of the original tree-view node 889 * (C) (rather than the ancestor's values) are added to the corresponding 890 * heavy-view node (B##). 891 */ 892 addDimensionToBottomUpHeavyViewNode_: function( 893 treeViewChildNode, heavyViewParentNode, currentDimension, 894 recursionDepthTrackers, previousDimensionsRecursive) { 895 var recursionDepthTracker = recursionDepthTrackers[currentDimension]; 896 var bottomIndex = recursionDepthTracker.bottomIndex; 897 var topIndex = recursionDepthTracker.topIndex; 898 var firstNonRecursiveIndex = 899 bottomIndex + recursionDepthTracker.recursionDepth; 900 var viewNodePath = recursionDepthTracker.viewNodePath; 901 902 var trackerAncestorNode = recursionDepthTracker.trackerAncestorNode; 903 var heavyViewDescendantNode = heavyViewParentNode; 904 for (var i = bottomIndex; i < topIndex; i++) { 905 var treeViewAncestorNode = viewNodePath[i]; 906 var dimensionTitle = treeViewAncestorNode.title[currentDimension]; 907 heavyViewDescendantNode = this.getOrCreateChildNode_( 908 heavyViewDescendantNode, currentDimension, dimensionTitle); 909 910 var currentDimensionRecursive = i < firstNonRecursiveIndex; 911 var currentOrPreviousDimensionsRecursive = 912 currentDimensionRecursive || previousDimensionsRecursive; 913 914 // The self and total values are taken from the original top-down tree 915 // view child node (rather than the ancestor node). 916 heavyViewDescendantNode.self += treeViewChildNode.self; 917 if (!currentOrPreviousDimensionsRecursive) 918 heavyViewDescendantNode.total += treeViewChildNode.total; 919 920 // Add the descendants of the tree-view child node wrt the next 921 // dimensions as children of the heavy-view child node. 922 this.addDimensionsToGenericHeavyViewNode_(treeViewChildNode, 923 heavyViewDescendantNode, currentDimension + 1, 924 recursionDepthTrackers, currentOrPreviousDimensionsRecursive, 925 this.addDimensionToBottomUpHeavyViewNode_.bind(this)); 926 } 927 } 928 }; 929 930 /** 931 * Recursion depth tracker. 932 * 933 * This class tracks the recursion depth of the current stack (updated via 934 * the push and pop methods). The recursion depth of a stack is the lengh of 935 * its longest leaf suffix that is repeated within the stack itself. 936 * 937 * For example, the recursion depth of the stack A -> B -> C -> A -> B -> B 938 * -> C (where C is the leaf node) is 2 because the suffix B -> C is repeated 939 * within it. 940 * 941 * @{constructor} 942 */ 943 function RecursionDepthTracker(maxDepth, dimension) { 944 this.titlePath = new Array(maxDepth); 945 this.viewNodePath = new Array(maxDepth); 946 this.bottomIndex = this.topIndex = maxDepth; 947 948 this.dimension_ = dimension; 949 this.currentTrackerNode_ = 950 this.createNode_(0 /* recursionDepth */, undefined /* parent */); 951 } 952 953 RecursionDepthTracker.prototype = { 954 push: function(viewNode) { 955 if (this.bottomIndex === 0) 956 throw new Error('Cannot push to a full tracker'); 957 var title = viewNode.title[this.dimension_]; 958 this.bottomIndex--; 959 this.titlePath[this.bottomIndex] = title; 960 this.viewNodePath[this.bottomIndex] = viewNode; 961 962 var childTrackerNode = this.currentTrackerNode_.children.get(title); 963 if (childTrackerNode !== undefined) { 964 // Child node already exists, so we don't need to calculate anything. 965 this.currentTrackerNode_ = childTrackerNode; 966 return; 967 } 968 969 // Child node doesn't exist yet, so we need to calculate its recursion 970 // depth. 971 var maxLengths = zFunction(this.titlePath, this.bottomIndex); 972 var recursionDepth = 0; 973 for (var i = 0; i < maxLengths.length; i++) 974 recursionDepth = Math.max(recursionDepth, maxLengths[i]); 975 976 childTrackerNode = 977 this.createNode_(recursionDepth, this.currentTrackerNode_); 978 this.currentTrackerNode_.children.set(title, childTrackerNode); 979 this.currentTrackerNode_ = childTrackerNode; 980 }, 981 982 pop: function() { 983 if (this.bottomIndex === this.topIndex) 984 throw new Error('Cannot pop from an empty tracker'); 985 986 this.titlePath[this.bottomIndex] = undefined; 987 this.viewNodePath[this.bottomIndex] = undefined; 988 this.bottomIndex++; 989 990 this.currentTrackerNode_ = this.currentTrackerNode_.parent; 991 }, 992 993 get recursionDepth() { 994 return this.currentTrackerNode_.recursionDepth; 995 }, 996 997 createNode_: function(recursionDepth, parent) { 998 return { 999 recursionDepth: recursionDepth, 1000 parent: parent, 1001 children: new Map() 1002 }; 1003 } 1004 }; 1005 1006 /** 1007 * Calculate the Z-function of (a suffix of) a list. 1008 * 1009 * Z-function: Given a list (or a string) of length n, for each index i from 1010 * 1 to n - 1, find the length z[i] of the longest substring starting at 1011 * position i which is also a prefix of the list. This function returns the 1012 * list of maximum lengths z. 1013 * 1014 * Mathematically, for each i from 1 to n - 1, z[i] is the maximum value such 1015 * that [list[0], ..., list[i - 1]] = [list[i], ..., list[i + z[i] - 1]]. 1016 * z[0] is defined to be zero for convenience. 1017 * 1018 * Example: 1019 * 1020 * Input (list): ['A', 'B', 'A', 'C', 'A', 'B', 'A'] 1021 * Output (z): [ 0 , 0 , 1 , 0 , 3 , 0 , 1 ] 1022 * 1023 * Unlike the brute-force approach (which is O(n^2) in the worst case), the 1024 * complexity of this implementation is linear in the size of the list, i.e. 1025 * O(n). 1026 * 1027 * Source: http://e-maxx-eng.github.io/string/z-function.html 1028 */ 1029 function zFunction(list, startIndex) { 1030 var n = list.length - startIndex; 1031 if (n === 0) 1032 return []; 1033 1034 var z = new Array(n); 1035 z[0] = 0; 1036 1037 for (var i = 1, left = 0, right = 0; i < n; ++i) { 1038 var maxLength; 1039 if (i <= right) 1040 maxLength = Math.min(right - i + 1, z[i - left]); 1041 else 1042 maxLength = 0; 1043 1044 while (i + maxLength < n && list[startIndex + maxLength] === 1045 list[startIndex + i + maxLength]) { 1046 ++maxLength; 1047 } 1048 1049 if (i + maxLength - 1 > right) { 1050 left = i; 1051 right = i + maxLength - 1; 1052 } 1053 1054 z[i] = maxLength; 1055 } 1056 1057 return z; 1058 } 1059 1060 return { 1061 MultiDimensionalViewBuilder: MultiDimensionalViewBuilder, 1062 MultiDimensionalViewType: MultiDimensionalViewType, 1063 1064 // Exports below are for testing only. 1065 MultiDimensionalViewNode: MultiDimensionalViewNode, 1066 RecursionDepthTracker: RecursionDepthTracker, 1067 zFunction: zFunction 1068 }; 1069}); 1070</script> 1071