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