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