text: /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *   http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */
  
  /*
  * A third-party license is embeded for some of the code in this file:
  * The treemap layout implementation was originally copied from
  * "d3.js" with some modifications made for this project.
  * (See more details in the comment of the method "squarify" below.)
  * The use of the source code of this file is also subject to the terms
  * and consitions of the license of "d3.js" (BSD-3Clause, see
  * </licenses/LICENSE-d3>).
  */
  
  import * as zrUtil from 'zrender/src/core/util';
  import BoundingRect from 'zrender/src/core/BoundingRect';
  import {parsePercent, MAX_SAFE_INTEGER} from '../../util/number';
  import * as layout from '../../util/layout';
  import * as helper from '../helper/treeHelper';
  
  var mathMax = Math.max;
  var mathMin = Math.min;
  var retrieveValue = zrUtil.retrieve;
  var each = zrUtil.each;
  
  var PATH_BORDER_WIDTH = ['itemStyle', 'borderWidth'];
  var PATH_GAP_WIDTH = ['itemStyle', 'gapWidth'];
  var PATH_UPPER_LABEL_SHOW = ['upperLabel', 'show'];
  var PATH_UPPER_LABEL_HEIGHT = ['upperLabel', 'height'];
  
  /**
   * @public
   */
  export default {
      seriesType: 'treemap',
      reset: function (seriesModel, ecModel, api, payload) {
          // Layout result in each node:
          // {x, y, width, height, area, borderWidth}
          var ecWidth = api.getWidth();
          var ecHeight = api.getHeight();
          var seriesOption = seriesModel.option;
  
          var layoutInfo = layout.getLayoutRect(
              seriesModel.getBoxLayoutParams(),
              {
                  width: api.getWidth(),
                  height: api.getHeight()
              }
          );
  
          var size = seriesOption.size || []; // Compatible with ec2.
          var containerWidth = parsePercent(
              retrieveValue(layoutInfo.width, size[0]),
              ecWidth
          );
          var containerHeight = parsePercent(
              retrieveValue(layoutInfo.height, size[1]),
              ecHeight
          );
  
          // Fetch payload info.
          var payloadType = payload && payload.type;
          var types = ['treemapZoomToNode', 'treemapRootToNode'];
          var targetInfo = helper
              .retrieveTargetInfo(payload, types, seriesModel);
          var rootRect = (payloadType === 'treemapRender' || payloadType === 'treemapMove')
              ? payload.rootRect : null;
          var viewRoot = seriesModel.getViewRoot();
          var viewAbovePath = helper.getPathToRoot(viewRoot);
  
          if (payloadType !== 'treemapMove') {
              var rootSize = payloadType === 'treemapZoomToNode'
                  ? estimateRootSize(
                      seriesModel, targetInfo, viewRoot, containerWidth, containerHeight
                  )
                  : rootRect
                  ? [rootRect.width, rootRect.height]
                  : [containerWidth, containerHeight];
  
              var sort = seriesOption.sort;
              if (sort && sort !== 'asc' && sort !== 'desc') {
                  sort = 'desc';
              }
              var options = {
                  squareRatio: seriesOption.squareRatio,
                  sort: sort,
                  leafDepth: seriesOption.leafDepth
              };
  
              // layout should be cleared because using updateView but not update.
              viewRoot.hostTree.clearLayouts();
  
              // TODO
              // optimize: if out of view clip, do not layout.
              // But take care that if do not render node out of view clip,
              // how to calculate start po
  
              var viewRootLayout = {
                  x: 0, y: 0,
                  width: rootSize[0], height: rootSize[1],
                  area: rootSize[0] * rootSize[1]
              };
              viewRoot.setLayout(viewRootLayout);
  
              squarify(viewRoot, options, false, 0);
              // Supplement layout.
              var viewRootLayout = viewRoot.getLayout();
              each(viewAbovePath, function (node, index) {
                  var childValue = (viewAbovePath[index + 1] || viewRoot).getValue();
                  node.setLayout(zrUtil.extend(
                      {dataExtent: [childValue, childValue], borderWidth: 0, upperHeight: 0},
                      viewRootLayout
                  ));
              });
          }
  
          var treeRoot = seriesModel.getData().tree.root;
  
          treeRoot.setLayout(
              calculateRootPosition(layoutInfo, rootRect, targetInfo),
              true
          );
  
          seriesModel.setLayoutInfo(layoutInfo);
  
          // FIXME
          // 现在没有clip功能，暂时取ec高宽。
          prunning(
              treeRoot,
              // Transform to base element coordinate system.
              new BoundingRect(-layoutInfo.x, -layoutInfo.y, ecWidth, ecHeight),
              viewAbovePath,
              viewRoot,
              0
          );
      }
  };
  
  /**
   * Layout treemap with squarify algorithm.
   * The original presentation of this algorithm
   * was made by Mark Bruls, Kees Huizing, and Jarke J. van Wijk
   * <https://graphics.ethz.ch/teaching/scivis_common/Literature/squarifiedTreeMaps.pdf>.
   * The implementation of this algorithm was originally copied from "d3.js"
   * <https://github.com/d3/d3/blob/9cc9a875e636a1dcf36cc1e07bdf77e1ad6e2c74/src/layout/treemap.js>
   * with some modifications made for this program.
   * See the license statement at the head of this file.
   *
   * @protected
   * @param {module:echarts/data/Tree~TreeNode} node
   * @param {Object} options
   * @param {string} options.sort 'asc' or 'desc'
   * @param {number} options.squareRatio
   * @param {boolean} hideChildren
   * @param {number} depth
   */
  function squarify(node, options, hideChildren, depth) {
      var width;
      var height;
  
      if (node.isRemoved()) {
          return;
      }
  
      var thisLayout = node.getLayout();
      width = thisLayout.width;
      height = thisLayout.height;
  
      // Considering border and gap
      var nodeModel = node.getModel();
      var borderWidth = nodeModel.get(PATH_BORDER_WIDTH);
      var halfGapWidth = nodeModel.get(PATH_GAP_WIDTH) / 2;
      var upperLabelHeight = getUpperLabelHeight(nodeModel);
      var upperHeight = Math.max(borderWidth, upperLabelHeight);
      var layoutOffset = borderWidth - halfGapWidth;
      var layoutOffsetUpper = upperHeight - halfGapWidth;
      var nodeModel = node.getModel();
  
      node.setLayout({
          borderWidth: borderWidth,
          upperHeight: upperHeight,
          upperLabelHeight: upperLabelHeight
      }, true);
  
      width = mathMax(width - 2 * layoutOffset, 0);
      height = mathMax(height - layoutOffset - layoutOffsetUpper, 0);
  
      var totalArea = width * height;
      var viewChildren = initChildren(
          node, nodeModel, totalArea, options, hideChildren, depth
      );
  
      if (!viewChildren.length) {
          return;
      }
  
      var rect = {x: layoutOffset, y: layoutOffsetUpper, width: width, height: height};
      var rowFixedLength = mathMin(width, height);
      var best = Infinity; // the best row score so far
      var row = [];
      row.area = 0;
  
      for (var i = 0, len = viewChildren.length; i < len;) {
          var child = viewChildren[i];
  
          row.push(child);
          row.area += child.getLayout().area;
          var score = worst(row, rowFixedLength, options.squareRatio);
  
          // continue with this orientation
          if (score <= best) {
              i++;
              best = score;
          }
          // abort, and try a different orientation
          else {
              row.area -= row.pop().getLayout().area;
              position(row, rowFixedLength, rect, halfGapWidth, false);
              rowFixedLength = mathMin(rect.width, rect.height);
              row.length = row.area = 0;
              best = Infinity;
          }
      }
  
      if (row.length) {
          position(row, rowFixedLength, rect, halfGapWidth, true);
      }
  
      if (!hideChildren) {
          var childrenVisibleMin = nodeModel.get('childrenVisibleMin');
          if (childrenVisibleMin != null && totalArea < childrenVisibleMin) {
              hideChildren = true;
          }
      }
  
      for (var i = 0, len = viewChildren.length; i < len; i++) {
          squarify(viewChildren[i], options, hideChildren, depth + 1);
      }
  }
  
  /**
   * Set area to each child, and calculate data extent for visual coding.
   */
  function initChildren(node, nodeModel, totalArea, options, hideChildren, depth) {
      var viewChildren = node.children || [];
      var orderBy = options.sort;
      orderBy !== 'asc' && orderBy !== 'desc' && (orderBy = null);
  
      var overLeafDepth = options.leafDepth != null && options.leafDepth <= depth;
  
      // leafDepth has higher priority.
      if (hideChildren && !overLeafDepth) {
          return (node.viewChildren = []);
      }
  
      // Sort children, order by desc.
      viewChildren = zrUtil.filter(viewChildren, function (child) {
          return !child.isRemoved();
      });
  
      sort(viewChildren, orderBy);
  
      var info = statistic(nodeModel, viewChildren, orderBy);
  
      if (info.sum === 0) {
          return (node.viewChildren = []);
      }
  
      info.sum = filterByThreshold(nodeModel, totalArea, info.sum, orderBy, viewChildren);
  
      if (info.sum === 0) {
          return (node.viewChildren = []);
      }
  
      // Set area to each child.
      for (var i = 0, len = viewChildren.length; i < len; i++) {
          var area = viewChildren[i].getValue() / info.sum * totalArea;
          // Do not use setLayout({...}, true), because it is needed to clear last layout.
          viewChildren[i].setLayout({area: area});
      }
  
      if (overLeafDepth) {
          viewChildren.length && node.setLayout({isLeafRoot: true}, true);
          viewChildren.length = 0;
      }
  
      node.viewChildren = viewChildren;
      node.setLayout({dataExtent: info.dataExtent}, true);
  
      return viewChildren;
  }
  
  /**
   * Consider 'visibleMin'. Modify viewChildren and get new sum.
   */
  function filterByThreshold(nodeModel, totalArea, sum, orderBy, orderedChildren) {
  
      // visibleMin is not supported yet when no option.sort.
      if (!orderBy) {
          return sum;
      }
  
      var visibleMin = nodeModel.get('visibleMin');
      var len = orderedChildren.length;
      var deletePoint = len;
  
      // Always travel from little value to big value.
      for (var i = len - 1; i >= 0; i--) {
          var value = orderedChildren[
              orderBy === 'asc' ? len - i - 1 : i
          ].getValue();
  
          if (value / sum * totalArea < visibleMin) {
              deletePoint = i;
              sum -= value;
          }
      }
  
      orderBy === 'asc'
          ? orderedChildren.splice(0, len - deletePoint)
          : orderedChildren.splice(deletePoint, len - deletePoint);
  
      return sum;
  }
  
  /**
   * Sort
   */
  function sort(viewChildren, orderBy) {
      if (orderBy) {
          viewChildren.sort(function (a, b) {
              var diff = orderBy === 'asc'
                  ? a.getValue() - b.getValue() : b.getValue() - a.getValue();
              return diff === 0
                  ? (orderBy === 'asc'
                      ? a.dataIndex - b.dataIndex : b.dataIndex - a.dataIndex
                  )
                  : diff;
          });
      }
      return viewChildren;
  }
  
  /**
   * Statistic
   */
  function statistic(nodeModel, children, orderBy) {
      // Calculate sum.
      var sum = 0;
      for (var i = 0, len = children.length; i < len; i++) {
          sum += children[i].getValue();
      }
  
      // Statistic data extent for latter visual coding.
      // Notice: data extent should be calculate based on raw children
      // but not filtered view children, otherwise visual mapping will not
      // be stable when zoom (where children is filtered by visibleMin).
  
      var dimension = nodeModel.get('visualDimension');
      var dataExtent;
  
      // The same as area dimension.
      if (!children || !children.length) {
          dataExtent = [NaN, NaN];
      }
      else if (dimension === 'value' && orderBy) {
          dataExtent = [
              children[children.length - 1].getValue(),
              children[0].getValue()
          ];
          orderBy === 'asc' && dataExtent.reverse();
      }
      // Other dimension.
      else {
          var dataExtent = [Infinity, -Infinity];
          each(children, function (child) {
              var value = child.getValue(dimension);
              value < dataExtent[0] && (dataExtent[0] = value);
              value > dataExtent[1] && (dataExtent[1] = value);
          });
      }
  
      return {sum: sum, dataExtent: dataExtent};
  }
  
  /**
   * Computes the score for the specified row,
   * as the worst aspect ratio.
   */
  function worst(row, rowFixedLength, ratio) {
      var areaMax = 0;
      var areaMin = Infinity;
  
      for (var i = 0, area, len = row.length; i < len; i++) {
          area = row[i].getLayout().area;
          if (area) {
              area < areaMin && (areaMin = area);
              area > areaMax && (areaMax = area);
          }
      }
  
      var squareArea = row.area * row.area;
      var f = rowFixedLength * rowFixedLength * ratio;
  
      return squareArea
          ? mathMax(
              (f * areaMax) / squareArea,
              squareArea / (f * areaMin)
          )
          : Infinity;
  }
  
  /**
   * Positions the specified row of nodes. Modifies `rect`.
   */
  function position(row, rowFixedLength, rect, halfGapWidth, flush) {
      // When rowFixedLength === rect.width,
      // it is horizontal subdivision,
      // rowFixedLength is the width of the subdivision,
      // rowOtherLength is the height of the subdivision,
      // and nodes will be positioned from left to right.
  
      // wh[idx0WhenH] means: when horizontal,
      //      wh[idx0WhenH] => wh[0] => 'width'.
      //      xy[idx1WhenH] => xy[1] => 'y'.
      var idx0WhenH = rowFixedLength === rect.width ? 0 : 1;
      var idx1WhenH = 1 - idx0WhenH;
      var xy = ['x', 'y'];
      var wh = ['width', 'height'];
  
      var last = rect[xy[idx0WhenH]];
      var rowOtherLength = rowFixedLength
          ? row.area / rowFixedLength : 0;
  
      if (flush || rowOtherLength > rect[wh[idx1WhenH]]) {
          rowOtherLength = rect[wh[idx1WhenH]]; // over+underflow
      }
      for (var i = 0, rowLen = row.length; i < rowLen; i++) {
          var node = row[i];
          var nodeLayout = {};
          var step = rowOtherLength
              ? node.getLayout().area / rowOtherLength : 0;
  
          var wh1 = nodeLayout[wh[idx1WhenH]] = mathMax(rowOtherLength - 2 * halfGapWidth, 0);
  
          // We use Math.max/min to avoid negative width/height when considering gap width.
          var remain = rect[xy[idx0WhenH]] + rect[wh[idx0WhenH]] - last;
          var modWH = (i === rowLen - 1 || remain < step) ? remain : step;
          var wh0 = nodeLayout[wh[idx0WhenH]] = mathMax(modWH - 2 * halfGapWidth, 0);
  
          nodeLayout[xy[idx1WhenH]] = rect[xy[idx1WhenH]] + mathMin(halfGapWidth, wh1 / 2);
          nodeLayout[xy[idx0WhenH]] = last + mathMin(halfGapWidth, wh0 / 2);
  
          last += modWH;
          node.setLayout(nodeLayout, true);
      }
  
      rect[xy[idx1WhenH]] += rowOtherLength;
      rect[wh[idx1WhenH]] -= rowOtherLength;
  }
  
  // Return [containerWidth, containerHeight] as defualt.
  function estimateRootSize(seriesModel, targetInfo, viewRoot, containerWidth, containerHeight) {
      // If targetInfo.node exists, we zoom to the node,
      // so estimate whold width and heigth by target node.
      var currNode = (targetInfo || {}).node;
      var defaultSize = [containerWidth, containerHeight];
  
      if (!currNode || currNode === viewRoot) {
          return defaultSize;
      }
  
      var parent;
      var viewArea = containerWidth * containerHeight;
      var area = viewArea * seriesModel.option.zoomToNodeRatio;
  
      while (parent = currNode.parentNode) { // jshint ignore:line
          var sum = 0;
          var siblings = parent.children;
  
          for (var i = 0, len = siblings.length; i < len; i++) {
              sum += siblings[i].getValue();
          }
          var currNodeValue = currNode.getValue();
          if (currNodeValue === 0) {
              return defaultSize;
          }
          area *= sum / currNodeValue;
  
          // Considering border, suppose aspect ratio is 1.
          var parentModel = parent.getModel();
          var borderWidth = parentModel.get(PATH_BORDER_WIDTH);
          var upperHeight = Math.max(borderWidth, getUpperLabelHeight(parentModel, borderWidth));
          area += 4 * borderWidth * borderWidth
              + (3 * borderWidth + upperHeight) * Math.pow(area, 0.5);
  
          area > MAX_SAFE_INTEGER && (area = MAX_SAFE_INTEGER);
  
          currNode = parent;
      }
  
      area < viewArea && (area = viewArea);
      var scale = Math.pow(area / viewArea, 0.5);
  
      return [containerWidth * scale, containerHeight * scale];
  }
  
  // Root postion base on coord of containerGroup
  function calculateRootPosition(layoutInfo, rootRect, targetInfo) {
      if (rootRect) {
          return {x: rootRect.x, y: rootRect.y};
      }
  
      var defaultPosition = {x: 0, y: 0};
      if (!targetInfo) {
          return defaultPosition;
      }
  
      // If targetInfo is fetched by 'retrieveTargetInfo',
      // old tree and new tree are the same tree,
      // so the node still exists and we can visit it.
  
      var targetNode = targetInfo.node;
      var layout = targetNode.getLayout();
  
      if (!layout) {
          return defaultPosition;
      }
  
      // Transform coord from local to container.
      var targetCenter = [layout.width / 2, layout.height / 2];
      var node = targetNode;
      while (node) {
          var nodeLayout = node.getLayout();
          targetCenter[0] += nodeLayout.x;
          targetCenter[1] += nodeLayout.y;
          node = node.parentNode;
      }
  
      return {
          x: layoutInfo.width / 2 - targetCenter[0],
          y: layoutInfo.height / 2 - targetCenter[1]
      };
  }
  
  // Mark nodes visible for prunning when visual coding and rendering.
  // Prunning depends on layout and root position, so we have to do it after layout.
  function prunning(node, clipRect, viewAbovePath, viewRoot, depth) {
      var nodeLayout = node.getLayout();
      var nodeInViewAbovePath = viewAbovePath[depth];
      var isAboveViewRoot = nodeInViewAbovePath && nodeInViewAbovePath === node;
  
      if (
          (nodeInViewAbovePath && !isAboveViewRoot)
          || (depth === viewAbovePath.length && node !== viewRoot)
      ) {
          return;
      }
  
      node.setLayout({
          // isInView means: viewRoot sub tree + viewAbovePath
          isInView: true,
          // invisible only means: outside view clip so that the node can not
          // see but still layout for animation preparation but not render.
          invisible: !isAboveViewRoot && !clipRect.intersect(nodeLayout),
          isAboveViewRoot: isAboveViewRoot
      }, true);
  
      // Transform to child coordinate.
      var childClipRect = new BoundingRect(
          clipRect.x - nodeLayout.x,
          clipRect.y - nodeLayout.y,
          clipRect.width,
          clipRect.height
      );
  
      each(node.viewChildren || [], function (child) {
          prunning(child, childClipRect, viewAbovePath, viewRoot, depth + 1);
      });
  }
  
  function getUpperLabelHeight(model) {
      return model.get(PATH_UPPER_LABEL_SHOW) ? model.get(PATH_UPPER_LABEL_HEIGHT) : 0;
  }