<!DOCTYPE html>
<!--
Copyright (c) 2013 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="/core/tracks/multi_row_track.html">
<link rel="import" href="/base/sorted_array_utils.html">
<link rel="import" href="/base/ui.html">

<script>
'use strict';

tr.exportTo('tr.c.tracks', function() {
  /**
   * A track that displays a SliceGroup.
   * @constructor
   * @extends {MultiRowTrack}
   */
  var SliceGroupTrack = tr.b.ui.define(
      'slice-group-track', tr.c.tracks.MultiRowTrack);

  SliceGroupTrack.prototype = {

    __proto__: tr.c.tracks.MultiRowTrack.prototype,

    decorate: function(viewport) {
      tr.c.tracks.MultiRowTrack.prototype.decorate.call(this, viewport);
      this.classList.add('slice-group-track');
      this.group_ = undefined;
      // Set the collapse threshold so we don't collapse by default, but the
      // user can explicitly collapse if they want it.
      this.defaultToCollapsedWhenSubRowCountMoreThan = 100;
    },

    addSubTrack_: function(slices) {
      var track = new tr.c.tracks.SliceTrack(this.viewport);
      track.slices = slices;
      this.appendChild(track);
      return track;
    },

    get group() {
      return this.group_;
    },

    set group(group) {
      this.group_ = group;
      this.setItemsToGroup(this.group_.slices, this.group_);
    },

    get eventContainer() {
      return this.group;
    },

    addContainersToTrackMap: function(containerToTrackMap) {
      containerToTrackMap.addContainer(this.group, this);
    },

    /**
     * Breaks up the list of slices into N rows, each of which is a list of
     * slices that are non overlapping.
     */
    buildSubRows_: function(slices) {
      // This function works by walking through slices by start time.
      //
      // The basic idea here is to insert each slice as deep into the subrow
      // list as it can go such that every subSlice is fully contained by its
      // parent slice.
      //
      // Visually, if we start with this:
      //  0:  [    a       ]
      //  1:    [  b  ]
      //  2:    [c][d]
      //
      // To place this slice:
      //               [e]
      // We first check row 2's last item, [d]. [e] wont fit into [d] (they dont
      // even intersect). So we go to row 1. That gives us [b], and [d] wont fit
      // into that either. So, we go to row 0 and its last slice, [a]. That can
      // completely contain [e], so that means we should add [e] as a subchild
      // of [a]. That puts it on row 1, yielding:
      //  0:  [    a       ]
      //  1:    [  b  ][e]
      //  2:    [c][d]
      //
      // If we then get this slice:
      //                      [f]
      // We do the same deepest-to-shallowest walk of the subrows trying to fit
      // it. This time, it doesn't fit in any open slice. So, we simply append
      // it to row 0:
      //  0:  [    a       ]  [f]
      //  1:    [  b  ][e]
      //  2:    [c][d]
      if (!slices.length)
        return [];

      var ops = [];
      for (var i = 0; i < slices.length; i++) {
        if (slices[i].subSlices)
          slices[i].subSlices.splice(0,
                                     slices[i].subSlices.length);
        ops.push(i);
      }

      ops.sort(function(ix, iy) {
        var x = slices[ix];
        var y = slices[iy];
        if (x.start != y.start)
          return x.start - y.start;

        // Elements get inserted into the slices array in order of when the
        // slices start. Because slices must be properly nested, we break
        // start-time ties by assuming that the elements appearing earlier in
        // the slices array (and thus ending earlier) start earlier.
        return ix - iy;
      });

      var subRows = [[]];
      this.badSlices_ = [];  // TODO(simonjam): Connect this again.

      for (var i = 0; i < ops.length; i++) {
        var op = ops[i];
        var slice = slices[op];

        // Try to fit the slice into the existing subrows.
        var inserted = false;
        for (var j = subRows.length - 1; j >= 0; j--) {
          if (subRows[j].length == 0)
            continue;

          var insertedSlice = subRows[j][subRows[j].length - 1];
          if (slice.start < insertedSlice.start) {
            this.badSlices_.push(slice);
            inserted = true;
          }
          if (insertedSlice.bounds(slice)) {
            // Insert it into subRow j + 1.
            while (subRows.length <= j + 1)
              subRows.push([]);
            subRows[j + 1].push(slice);
            if (insertedSlice.subSlices)
              insertedSlice.subSlices.push(slice);
            inserted = true;
            break;
          }
        }
        if (inserted)
          continue;

        // Append it to subRow[0] as a root.
        subRows[0].push(slice);
      }

      return subRows;
    }
  };

  return {
    SliceGroupTrack: SliceGroupTrack
  };
});
</script>