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
8<link rel="import" href="/tracing/base/base.html">
9<link rel="import" href="/tracing/base/iteration_helpers.html">
10
11<script>
12'use strict';
13
14/**
15 * @fileoverview Provides event merging functionality for grouping/analysis.
16 */
17tr.exportTo('tr.b', function() {
18  function convertEventsToRanges(events) {
19    return events.map(function(event) {
20      return tr.b.Range.fromExplicitRange(event.start, event.end);
21    });
22  }
23
24  function mergeRanges(inRanges, mergeThreshold, mergeFunction) {
25    var remainingEvents = inRanges.slice();
26    remainingEvents.sort(function(x, y) {
27      return x.min - y.min;
28    });
29
30    if (remainingEvents.length <= 1) {
31      var merged = [];
32      if (remainingEvents.length == 1) {
33        merged.push(mergeFunction(remainingEvents));
34      }
35      return merged;
36    }
37
38    var mergedEvents = [];
39
40    var currentMergeBuffer = [];
41    var rightEdge;
42    function beginMerging() {
43      currentMergeBuffer.push(remainingEvents[0]);
44      remainingEvents.splice(0, 1);
45      rightEdge = currentMergeBuffer[0].max;
46    }
47
48    function flushCurrentMergeBuffer() {
49      if (currentMergeBuffer.length == 0)
50        return;
51
52      mergedEvents.push(mergeFunction(currentMergeBuffer));
53      currentMergeBuffer = [];
54
55      // Refill merge buffer if needed.
56      if (remainingEvents.length != 0)
57        beginMerging();
58    }
59
60    beginMerging();
61
62    while (remainingEvents.length) {
63      var currentEvent = remainingEvents[0];
64
65      var distanceFromRightEdge = currentEvent.min - rightEdge;
66      if (distanceFromRightEdge < mergeThreshold) {
67        rightEdge = Math.max(rightEdge, currentEvent.max);
68        remainingEvents.splice(0, 1);
69        currentMergeBuffer.push(currentEvent);
70        continue;
71      }
72
73      // Too big a gap.
74      flushCurrentMergeBuffer();
75    }
76    flushCurrentMergeBuffer();
77
78    return mergedEvents;
79  }
80
81  // Pass in |opt_totalRange| in order to find empty ranges before the first of
82  // |inRanges| and after the last of |inRanges|.
83  function findEmptyRangesBetweenRanges(inRanges, opt_totalRange) {
84    if (opt_totalRange && opt_totalRange.isEmpty)
85      opt_totalRange = undefined;
86
87    var emptyRanges = [];
88    if (!inRanges.length) {
89      if (opt_totalRange)
90        emptyRanges.push(opt_totalRange);
91      return emptyRanges;
92    }
93
94    inRanges = inRanges.slice();
95    inRanges.sort(function(x, y) {
96      return x.min - y.min;
97    });
98    if (opt_totalRange &&
99        (opt_totalRange.min < inRanges[0].min)) {
100      emptyRanges.push(tr.b.Range.fromExplicitRange(
101          opt_totalRange.min, inRanges[0].min));
102    }
103
104    inRanges.forEach(function(range, index) {
105      for (var otherIndex = 0; otherIndex < inRanges.length; ++otherIndex) {
106        if (index === otherIndex)
107          continue;
108        var other = inRanges[otherIndex];
109
110        if (other.min > range.max) {
111          // |inRanges| is sorted, so |other| is the first range after |range|,
112          // and there is an empty range between them.
113          emptyRanges.push(tr.b.Range.fromExplicitRange(
114              range.max, other.min));
115          return;
116        }
117        // Otherwise, |other| starts before |range| ends, so |other| might
118        // possibly contain the end of |range|.
119
120        if (other.max > range.max) {
121          // |other| does contain the end of |range|, so no empty range starts
122          // at the end of this |range|.
123          return;
124        }
125      }
126      if (opt_totalRange && (range.max < opt_totalRange.max)) {
127        emptyRanges.push(tr.b.Range.fromExplicitRange(
128            range.max, opt_totalRange.max));
129      }
130    });
131    return emptyRanges;
132  }
133
134  return {
135    convertEventsToRanges: convertEventsToRanges,
136    findEmptyRangesBetweenRanges: findEmptyRangesBetweenRanges,
137    mergeRanges: mergeRanges
138  };
139});
140</script>
141