src/third_party/trace-viewer/third_party/tvcm/src/tvcm/interval_tree.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 tvcm.exportTo('tvcm', function() {
   8   function max(a, b) {
   9     if (a === undefined)
  10       return b;
  11     if (b === undefined)
  12       return a;
  13     return Math.max(a, b);
  14   }
  15
  16   /**
  17    * This class implements an interval tree.
  18    *    See: http://wikipedia.org/wiki/Interval_tree
  19    *
  20    * Internally the tree is a Red-Black tree. The insertion/colour is done using
  21    * the Left-leaning Red-Black Trees algorithm as described in:
  22    *       http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
  23    *
  24    * @param {function} beginPositionCb Callback to retrieve the begin position.
  25    * @param {function} endPositionCb Callback to retrieve the end position.
  26    *
  27    * @constructor
  28    */
  29   function IntervalTree(beginPositionCb, endPositionCb) {
  30     this.beginPositionCb_ = beginPositionCb;
  31     this.endPositionCb_ = endPositionCb;
  32
  33     this.root_ = undefined;
  34     this.size_ = 0;
  35   }
  36
  37   IntervalTree.prototype = {
  38     /**
  39      * Insert events into the interval tree.
  40      *
  41      * @param {Object} begin The left object.
  42      * @param {Object=} opt_end The end object, optional. If not provided the
  43      *     begin object is assumed to also be the end object.
  44      */
  45     insert: function(begin, opt_end) {
  46       var startPosition = this.beginPositionCb_(begin);
  47       var endPosition = this.endPositionCb_(opt_end || begin);
  48
  49       var node = new IntervalTreeNode(begin, opt_end || begin,
  50                                       startPosition, endPosition);
  51       this.size_++;
  52
  53       this.root_ = this.insertNode_(this.root_, node);
  54       this.root_.colour = Colour.BLACK;
  55     },
  56
  57     insertNode_: function(root, node) {
  58       if (root === undefined)
  59         return node;
  60
  61       if (root.leftNode && root.leftNode.isRed &&
  62           root.rightNode && root.rightNode.isRed)
  63         this.flipNodeColour_(root);
  64
  65       if (node.key < root.key)
  66         root.leftNode = this.insertNode_(root.leftNode, node);
  67       else if (node.key === root.key)
  68         root.merge(node);
  69       else
  70         root.rightNode = this.insertNode_(root.rightNode, node);
  71
  72       if (root.rightNode && root.rightNode.isRed &&
  73           (root.leftNode === undefined || !root.leftNode.isRed))
  74         root = this.rotateLeft_(root);
  75
  76       if (root.leftNode && root.leftNode.isRed &&
  77           root.leftNode.leftNode && root.leftNode.leftNode.isRed)
  78         root = this.rotateRight_(root);
  79
  80       return root;
  81     },
  82
  83     rotateRight_: function(node) {
  84       var sibling = node.leftNode;
  85       node.leftNode = sibling.rightNode;
  86       sibling.rightNode = node;
  87       sibling.colour = node.colour;
  88       node.colour = Colour.RED;
  89       return sibling;
  90     },
  91
  92     rotateLeft_: function(node) {
  93       var sibling = node.rightNode;
  94       node.rightNode = sibling.leftNode;
  95       sibling.leftNode = node;
  96       sibling.colour = node.colour;
  97       node.colour = Colour.RED;
  98       return sibling;
  99     },
 100
 101     flipNodeColour_: function(node) {
 102       node.colour = this.flipColour_(node.colour);
 103       node.leftNode.colour = this.flipColour_(node.leftNode.colour);
 104       node.rightNode.colour = this.flipColour_(node.rightNode.colour);
 105     },
 106
 107     flipColour_: function(colour) {
 108       return colour === Colour.RED ? Colour.BLACK : Colour.RED;
 109     },
 110
 111     /* The high values are used to find intersection. It should be called after
 112      * all of the nodes are inserted. Doing it each insert is _slow_. */
 113     updateHighValues: function() {
 114       this.updateHighValues_(this.root_);
 115     },
 116
 117     /* There is probably a smarter way to do this by starting from the inserted
 118      * node, but need to handle the rotations correctly. Went the easy route
 119      * for now. */
 120     updateHighValues_: function(node) {
 121       if (node === undefined)
 122         return undefined;
 123
 124       node.maxHighLeft = this.updateHighValues_(node.leftNode);
 125       node.maxHighRight = this.updateHighValues_(node.rightNode);
 126
 127       return max(max(node.maxHighLeft, node.highValue), node.maxHighRight);
 128     },
 129
 130     /**
 131      * Retrieve all overlapping intervals.
 132      *
 133      * @param {number} lowValue The low value for the intersection interval.
 134      * @param {number} highValue The high value for the intersection interval.
 135      * @return {Array} All [begin, end] pairs inside intersecting intervals.
 136      */
 137     findIntersection: function(lowValue, highValue) {
 138       if (lowValue === undefined || highValue === undefined)
 139         throw new Error('lowValue and highValue must be defined');
 140       if ((typeof lowValue !== 'number') || (typeof highValue !== 'number'))
 141         throw new Error('lowValue and highValue must be numbers');
 142
 143       if (this.root_ === undefined)
 144         return [];
 145
 146       return this.findIntersection_(this.root_, lowValue, highValue);
 147     },
 148
 149     findIntersection_: function(node, lowValue, highValue) {
 150       var ret = [];
 151
 152       /* This node starts has a start point at or further right then highValue
 153        * so we know this node is out and all right children are out. Just need
 154        * to check left */
 155       if (node.lowValue >= highValue) {
 156         if (!node.hasLeftNode)
 157           return [];
 158         return this.findIntersection_(node.leftNode, lowValue, highValue);
 159       }
 160
 161       /* If we have a maximum left high value that is bigger then lowValue we
 162        * need to check left for matches */
 163       if (node.maxHighLeft > lowValue) {
 164         ret = ret.concat(
 165             this.findIntersection_(node.leftNode, lowValue, highValue));
 166       }
 167
 168       /* We know that this node starts before highValue, if any of it's data
 169        * ends after lowValue we need to add those nodes */
 170       if (node.highValue > lowValue) {
 171         for (var i = (node.data.length - 1); i >= 0; --i) {
 172           /* data nodes are sorted by high value, so as soon as we see one
 173            * before low value we're done. */
 174           if (node.data[i].high < lowValue)
 175             break;
 176
 177           ret.unshift([node.data[i].start, node.data[i].end]);
 178         }
 179       }
 180
 181       /* check for matches in the right tree */
 182       if (node.hasRightNode) {
 183         ret = ret.concat(
 184             this.findIntersection_(node.rightNode, lowValue, highValue));
 185       }
 186
 187       return ret;
 188     },
 189
 190     /**
 191      * Returns the number of nodes in the tree.
 192      */
 193     get size() {
 194       return this.size_;
 195     },
 196
 197     /**
 198      * Returns the root node in the tree.
 199      */
 200     get root() {
 201       return this.root_;
 202     },
 203
 204     /**
 205      * Dumps out the [lowValue, highValue] pairs for each node in depth-first
 206      * order.
 207      */
 208     dump_: function() {
 209       if (this.root_ === undefined)
 210         return [];
 211       return this.dumpNode_(this.root_);
 212     },
 213
 214     dumpNode_: function(node) {
 215       var ret = {};
 216       if (node.hasLeftNode)
 217         ret['left'] = this.dumpNode_(node.leftNode);
 218
 219       ret['node'] = node.dump();
 220
 221       if (node.hasRightNode)
 222         ret['right'] = this.dumpNode_(node.rightNode);
 223
 224       return ret;
 225     }
 226   };
 227
 228   var Colour = {
 229     RED: 'red',
 230     BLACK: 'black'
 231   };
 232
 233   function IntervalTreeNode(startObject, endObject, lowValue, highValue) {
 234     this.lowValue_ = lowValue;
 235
 236     this.data_ = [{
 237       start: startObject,
 238       end: endObject,
 239       high: highValue,
 240       low: lowValue
 241     }];
 242
 243     this.colour_ = Colour.RED;
 244
 245     this.parentNode_ = undefined;
 246     this.leftNode_ = undefined;
 247     this.rightNode_ = undefined;
 248
 249     this.maxHighLeft_ = undefined;
 250     this.maxHighRight_ = undefined;
 251   }
 252
 253   IntervalTreeNode.prototype = {
 254     get colour() {
 255       return this.colour_;
 256     },
 257
 258     set colour(colour) {
 259       this.colour_ = colour;
 260     },
 261
 262     get key() {
 263       return this.lowValue_;
 264     },
 265
 266     get lowValue() {
 267       return this.lowValue_;
 268     },
 269
 270     get highValue() {
 271       return this.data_[this.data_.length - 1].high;
 272     },
 273
 274     set leftNode(left) {
 275       this.leftNode_ = left;
 276     },
 277
 278     get leftNode() {
 279       return this.leftNode_;
 280     },
 281
 282     get hasLeftNode() {
 283       return this.leftNode_ !== undefined;
 284     },
 285
 286     set rightNode(right) {
 287       this.rightNode_ = right;
 288     },
 289
 290     get rightNode() {
 291       return this.rightNode_;
 292     },
 293
 294     get hasRightNode() {
 295       return this.rightNode_ !== undefined;
 296     },
 297
 298     set parentNode(parent) {
 299       this.parentNode_ = parent;
 300     },
 301
 302     get parentNode() {
 303       return this.parentNode_;
 304     },
 305
 306     get isRootNode() {
 307       return this.parentNode_ === undefined;
 308     },
 309
 310     set maxHighLeft(high) {
 311       this.maxHighLeft_ = high;
 312     },
 313
 314     get maxHighLeft() {
 315       return this.maxHighLeft_;
 316     },
 317
 318     set maxHighRight(high) {
 319       this.maxHighRight_ = high;
 320     },
 321
 322     get maxHighRight() {
 323       return this.maxHighRight_;
 324     },
 325
 326     get data() {
 327       return this.data_;
 328     },
 329
 330     get isRed() {
 331       return this.colour_ === Colour.RED;
 332     },
 333
 334     merge: function(node) {
 335       this.data_ = this.data_.concat(node.data);
 336       this.data_.sort(function(a, b) {
 337         return a.high - b.high;
 338       });
 339     },
 340
 341     dump: function() {
 342       if (this.data_.length === 1)
 343         return [this.data_[0].low, this.data[0].high];
 344
 345       return this.data_.map(function(d) { return [d.low, d.high]; });
 346     }
 347   };
 348
 349   return {
 350     IntervalTree: IntervalTree
 351   };
 352 });