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

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