<!DOCTYPE html>
<!--
Copyright (c) 2014 The Chromium Authors. All rights reserved.
Use of this source code is governed by a BSD-style license that can be
found in the LICENSE file.
-->
<link rel="import" href="/base/base.html">
<link rel="import" href="/base/iteration_helpers.html">
<script>
'use strict';

/**
 * @fileoverview Provides event merging functionality for grouping/analysis.
 */
tr.exportTo('tr.e.audits', function() {
  function mergeRanges(inRanges, mergeThreshold, mergeFunction) {
    return mergeExplicitRanges(inRanges,
                               mergeThreshold,
                               mergeFunction,
                               function(r) { return r.min; },
                               function(r) { return r.max; });
  }

  function mergeExplicitRanges(inRanges, mergeThreshold, mergeFunction,
                       opt_startFunction, opt_endFunction) {
    var startFunction = opt_startFunction;
    var endFunction = opt_endFunction;
    if (!startFunction)
      startFunction = function(event) { return event.start; };
    if (!endFunction)
      endFunction = function(event) { return event.end; };

    var remainingEvents = inRanges.slice();
    remainingEvents.sort(function(x, y) {
      return startFunction(x) - startFunction(y);
    });

    if (remainingEvents.length <= 1) {
      var merged = [];
      if (remainingEvents.length == 1) {
        merged.push(mergeFunction(remainingEvents));
      }
      return merged;
    }

    var mergedEvents = [];

    var currentMergeBuffer = [];
    var rightEdge;
    function beginMerging() {
      currentMergeBuffer.push(remainingEvents[0]);
      remainingEvents.splice(0, 1);
      rightEdge = endFunction(currentMergeBuffer[0]);
    }

    function flushCurrentMergeBuffer() {
      if (currentMergeBuffer.length == 0)
        return;

      mergedEvents.push(mergeFunction(currentMergeBuffer));
      currentMergeBuffer = [];

      // Refill merge buffer if needed.
      if (remainingEvents.length != 0)
        beginMerging();
    }

    beginMerging();

    while (remainingEvents.length) {
      var currentEvent = remainingEvents[0];

      var distanceFromRightEdge = startFunction(currentEvent) - rightEdge;
      if (distanceFromRightEdge < mergeThreshold) {
        rightEdge = Math.max(rightEdge, endFunction(currentEvent));
        remainingEvents.splice(0, 1);
        currentMergeBuffer.push(currentEvent);
        continue;
      }

      // Too big a gap.
      flushCurrentMergeBuffer();
    }
    flushCurrentMergeBuffer();

    return mergedEvents;
  }

  // 'opt_totalRange' allows capturing an empty range before the first of
  // 'inRanges' and after the last of 'inRanges'.
  function findEmptyRangesBetweenExplicitRanges(
      inRanges, opt_totalRange, opt_startFunction, opt_endFunction) {
    var startFunction = opt_startFunction;
    if (!startFunction)
      startFunction = function(range) { return range.start; };
    var endFunction = opt_endFunction;
    if (!endFunction)
      endFunction = function(range) { return range.end; };

    var emptyRanges = [];
    if (!inRanges.length) {
      if (opt_totalRange) {
        emptyRanges.push(tr.b.Range.fromExplicitRange(
            startFunction(opt_totalRange), endFunction(opt_totalRange)));
      }
      return emptyRanges;
    }

    inRanges = inRanges.slice();
    inRanges.sort(function(x, y) {
      return startFunction(x) - startFunction(y);
    });
    if (opt_totalRange &&
        (startFunction(opt_totalRange) < startFunction(inRanges[0]))) {
      emptyRanges.push(tr.b.Range.fromExplicitRange(
          startFunction(opt_totalRange), startFunction(inRanges[0])));
    }

    inRanges.forEach(function(range, index) {
      for (var otherIndex = 0; otherIndex < inRanges.length; ++otherIndex) {
        if (index === otherIndex)
          continue;
        var other = inRanges[otherIndex];

        if (startFunction(other) > endFunction(range)) {
          // 'inRanges' is sorted, so 'other' is the first range after 'range',
          // and there is an empty range between them.
          emptyRanges.push(tr.b.Range.fromExplicitRange(
              endFunction(range), startFunction(other)));
          return;
        }
        // Otherwise, 'other' starts before 'range' ends, so 'other' might
        // possibly contain the end of 'range'.

        if (endFunction(other) > endFunction(range)) {
          // 'other' does contain the end of 'range', so no empty range starts
          // at the end of this 'range'.
          return;
        }
      }
      if (opt_totalRange &&
          (endFunction(range) < endFunction(opt_totalRange))) {
        emptyRanges.push(tr.b.Range.fromExplicitRange(
            endFunction(range), endFunction(opt_totalRange)));
      }
    });
    return emptyRanges;
  }

  return {
    findEmptyRangesBetweenExplicitRanges: findEmptyRangesBetweenExplicitRanges,
    mergeExplicitRanges: mergeExplicitRanges,
    mergeRanges: mergeRanges
  };
});
</script>