src/chart/treemap/treemapLayout.ts - echarts - Git at Google

 /*
 * 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 embedded 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, { RectLike } 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';
 import TreemapSeriesModel, { TreemapSeriesNodeItemOption } from './TreemapSeries';
 import GlobalModel from '../../model/Global';
 import ExtensionAPI from '../../core/ExtensionAPI';
 import { TreeNode } from '../../data/Tree';
 import Model from '../../model/Model';
 import { TreemapRenderPayload, TreemapMovePayload, TreemapZoomToNodePayload } from './treemapAction';

 const mathMax = Math.max;
 const mathMin = Math.min;
 const retrieveValue = zrUtil.retrieve;
 const each = zrUtil.each;

 const PATH_BORDER_WIDTH = ['itemStyle', 'borderWidth'] as const;
 const PATH_GAP_WIDTH = ['itemStyle', 'gapWidth'] as const;
 const PATH_UPPER_LABEL_SHOW = ['upperLabel', 'show'] as const;
 const PATH_UPPER_LABEL_HEIGHT = ['upperLabel', 'height'] as const;

 export interface TreemapLayoutNode extends TreeNode {
     parentNode: TreemapLayoutNode
     children: TreemapLayoutNode[]
     viewChildren: TreemapLayoutNode[]
 }

 export interface TreemapItemLayout extends RectLike {
     area: number
     isLeafRoot: boolean
     dataExtent: [number, number]

     borderWidth: number
     upperHeight: number
     upperLabelHeight: number

     isInView: boolean
     invisible: boolean

     isAboveViewRoot: boolean
 };

 type NodeModel = Model<TreemapSeriesNodeItemOption>;

 type OrderBy = 'asc' | 'desc' | boolean;

 type LayoutRow = TreemapLayoutNode[] & {
     area: number
 };
 /**
  * @public
  */
 export default {
     seriesType: 'treemap',
     reset: function (
         seriesModel: TreemapSeriesModel,
         ecModel: GlobalModel,
         api: ExtensionAPI,
         payload?: TreemapZoomToNodePayload | TreemapRenderPayload | TreemapMovePayload
     ) {
         // Layout result in each node:
         // {x, y, width, height, area, borderWidth}
         const ecWidth = api.getWidth();
         const ecHeight = api.getHeight();
         const seriesOption = seriesModel.option;

         const layoutInfo = layout.getLayoutRect(
             seriesModel.getBoxLayoutParams(),
             {
                 width: api.getWidth(),
                 height: api.getHeight()
             }
         );

         const size = seriesOption.size || []; // Compatible with ec2.
         const containerWidth = parsePercent(
             retrieveValue(layoutInfo.width, size[0]),
             ecWidth
         );
         const containerHeight = parsePercent(
             retrieveValue(layoutInfo.height, size[1]),
             ecHeight
         );

         // Fetch payload info.
         const payloadType = payload && payload.type;
         const types = ['treemapZoomToNode', 'treemapRootToNode'];
         const targetInfo = helper
             .retrieveTargetInfo(payload, types, seriesModel);
         const rootRect = (payloadType === 'treemapRender' || payloadType === 'treemapMove')
             ? payload.rootRect : null;
         const viewRoot = seriesModel.getViewRoot();
         const viewAbovePath = helper.getPathToRoot(viewRoot) as TreemapLayoutNode[];

         if (payloadType !== 'treemapMove') {
             const rootSize = payloadType === 'treemapZoomToNode'
                 ? estimateRootSize(
                     seriesModel, targetInfo, viewRoot, containerWidth, containerHeight
                 )
                 : rootRect
                 ? [rootRect.width, rootRect.height]
                 : [containerWidth, containerHeight];

             let sort = seriesOption.sort;
             if (sort && sort !== 'asc' && sort !== 'desc') {
                 // Default to be desc order.
                 sort = 'desc';
             }
             const 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

             let 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.
             viewRootLayout = viewRoot.getLayout();
             each(viewAbovePath, function (node, index) {
                 const childValue = (viewAbovePath[index + 1] || viewRoot).getValue();
                 node.setLayout(zrUtil.extend(
                     {
                         dataExtent: [childValue, childValue],
                         borderWidth: 0,
                         upperHeight: 0
                     },
                     viewRootLayout
                 ));
             });
         }

         const 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: TreemapLayoutNode,
     options: {
         sort?: OrderBy
         squareRatio?: number
         leafDepth?: number
     },
     hideChildren: boolean,
     depth: number
 ) {
     let width;
     let height;

     if (node.isRemoved()) {
         return;
     }

     const thisLayout = node.getLayout();
     width = thisLayout.width;
     height = thisLayout.height;

     // Considering border and gap
     const nodeModel = node.getModel<TreemapSeriesNodeItemOption>();
     const borderWidth = nodeModel.get(PATH_BORDER_WIDTH);
     const halfGapWidth = nodeModel.get(PATH_GAP_WIDTH) / 2;
     const upperLabelHeight = getUpperLabelHeight(nodeModel);
     const upperHeight = Math.max(borderWidth, upperLabelHeight);
     const layoutOffset = borderWidth - halfGapWidth;
     const layoutOffsetUpper = upperHeight - halfGapWidth;

     node.setLayout({
         borderWidth: borderWidth,
         upperHeight: upperHeight,
         upperLabelHeight: upperLabelHeight
     }, true);

     width = mathMax(width - 2 * layoutOffset, 0);
     height = mathMax(height - layoutOffset - layoutOffsetUpper, 0);

     const totalArea = width * height;
     const viewChildren = initChildren(
         node, nodeModel, totalArea, options, hideChildren, depth
     );

     if (!viewChildren.length) {
         return;
     }

     const rect = {x: layoutOffset, y: layoutOffsetUpper, width: width, height: height};
     let rowFixedLength = mathMin(width, height);
     let best = Infinity; // the best row score so far
     const row = [] as LayoutRow;
     row.area = 0;

     for (let i = 0, len = viewChildren.length; i < len;) {
         const child = viewChildren[i];

         row.push(child);
         row.area += child.getLayout().area;
         const 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) {
         const childrenVisibleMin = nodeModel.get('childrenVisibleMin');
         if (childrenVisibleMin != null && totalArea < childrenVisibleMin) {
             hideChildren = true;
         }
     }

     for (let 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: TreemapLayoutNode,
     nodeModel: NodeModel,
     totalArea: number,
     options: {
         sort?: OrderBy
         leafDepth?: number
     },
     hideChildren: boolean,
     depth: number
 ) {
     let viewChildren = node.children || [];
     let orderBy = options.sort;
     orderBy !== 'asc' && orderBy !== 'desc' && (orderBy = null);

     const 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);

     const 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 (let i = 0, len = viewChildren.length; i < len; i++) {
         const area = viewChildren[i].getValue() as number / 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: NodeModel,
     totalArea: number,
     sum: number,
     orderBy: OrderBy,
     orderedChildren: TreemapLayoutNode[]
 ) {

     // visibleMin is not supported yet when no option.sort.
     if (!orderBy) {
         return sum;
     }

     const visibleMin = nodeModel.get('visibleMin');
     const len = orderedChildren.length;
     let deletePoint = len;

     // Always travel from little value to big value.
     for (let i = len - 1; i >= 0; i--) {
         const value = orderedChildren[
             orderBy === 'asc' ? len - i - 1 : i
         ].getValue() as number;

         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: TreemapLayoutNode[],
     orderBy: OrderBy
 ) {
     if (orderBy) {
         viewChildren.sort(function (a, b) {
             const diff = orderBy === 'asc'
                 ? a.getValue() as number - (b.getValue() as number)
                 : b.getValue() as number - (a.getValue() as number);
             return diff === 0
                 ? (orderBy === 'asc'
                     ? a.dataIndex - b.dataIndex : b.dataIndex - a.dataIndex
                 )
                 : diff;
         });
     }
     return viewChildren;
 }

 /**
  * Statistic
  */
 function statistic(
     nodeModel: NodeModel,
     children: TreemapLayoutNode[],
     orderBy: OrderBy
 ) {
     // Calculate sum.
     let sum = 0;
     for (let i = 0, len = children.length; i < len; i++) {
         sum += children[i].getValue() as number;
     }

     // 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).

     const dimension = nodeModel.get('visualDimension');
     let dataExtent: number[];

     // The same as area dimension.
     if (!children || !children.length) {
         dataExtent = [NaN, NaN];
     }
     else if (dimension === 'value' && orderBy) {
         dataExtent = [
             children[children.length - 1].getValue() as number,
             children[0].getValue() as number
         ];
         orderBy === 'asc' && dataExtent.reverse();
     }
     // Other dimension.
     else {
         dataExtent = [Infinity, -Infinity];
         each(children, function (child) {
             const value = child.getValue(dimension) as number;
             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: LayoutRow, rowFixedLength: number, ratio: number) {
     let areaMax = 0;
     let areaMin = Infinity;

     for (let i = 0, area, len = row.length; i < len; i++) {
         area = row[i].getLayout().area;
         if (area) {
             area < areaMin && (areaMin = area);
             area > areaMax && (areaMax = area);
         }
     }

     const squareArea = row.area * row.area;
     const 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: LayoutRow,
     rowFixedLength: number,
     rect: RectLike,
     halfGapWidth: number,
     flush?: boolean
 ) {
     // 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'.
     const idx0WhenH = rowFixedLength === rect.width ? 0 : 1;
     const idx1WhenH = 1 - idx0WhenH;
     const xy = ['x', 'y'] as const;
     const wh = ['width', 'height'] as const;

     let last = rect[xy[idx0WhenH]];
     let rowOtherLength = rowFixedLength
         ? row.area / rowFixedLength : 0;

     if (flush || rowOtherLength > rect[wh[idx1WhenH]]) {
         rowOtherLength = rect[wh[idx1WhenH]]; // over+underflow
     }
     for (let i = 0, rowLen = row.length; i < rowLen; i++) {
         const node = row[i];
         const nodeLayout = {} as TreemapItemLayout;
         const step = rowOtherLength
             ? node.getLayout().area / rowOtherLength : 0;

         const wh1 = nodeLayout[wh[idx1WhenH]] = mathMax(rowOtherLength - 2 * halfGapWidth, 0);

         // We use Math.max/min to avoid negative width/height when considering gap width.
         const remain = rect[xy[idx0WhenH]] + rect[wh[idx0WhenH]] - last;
         const modWH = (i === rowLen - 1 || remain < step) ? remain : step;
         const 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 default.
 function estimateRootSize(
     seriesModel: TreemapSeriesModel,
     targetInfo: { node: TreemapLayoutNode },
     viewRoot: TreemapLayoutNode,
     containerWidth: number,
     containerHeight: number
 ) {
     // If targetInfo.node exists, we zoom to the node,
     // so estimate whole width and height by target node.
     let currNode = (targetInfo || {}).node;
     const defaultSize = [containerWidth, containerHeight];

     if (!currNode || currNode === viewRoot) {
         return defaultSize;
     }

     let parent;
     const viewArea = containerWidth * containerHeight;
     let area = viewArea * seriesModel.option.zoomToNodeRatio;

     while (parent = currNode.parentNode) { // jshint ignore:line
         let sum = 0;
         const siblings = parent.children;

         for (let i = 0, len = siblings.length; i < len; i++) {
             sum += siblings[i].getValue() as number;
         }
         const currNodeValue = currNode.getValue() as number;
         if (currNodeValue === 0) {
             return defaultSize;
         }
         area *= sum / currNodeValue;

         // Considering border, suppose aspect ratio is 1.
         const parentModel = parent.getModel<TreemapSeriesNodeItemOption>();
         const borderWidth = parentModel.get(PATH_BORDER_WIDTH);
         const upperHeight = Math.max(borderWidth, getUpperLabelHeight(parentModel));
         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);
     const scale = Math.pow(area / viewArea, 0.5);

     return [containerWidth * scale, containerHeight * scale];
 }

 // Root position based on coord of containerGroup
 function calculateRootPosition(
     layoutInfo: layout.LayoutRect,
     rootRect: RectLike,
     targetInfo: { node: TreemapLayoutNode }
 ) {
     if (rootRect) {
         return {x: rootRect.x, y: rootRect.y};
     }

     const 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.

     const targetNode = targetInfo.node;
     const layout = targetNode.getLayout();

     if (!layout) {
         return defaultPosition;
     }

     // Transform coord from local to container.
     const targetCenter = [layout.width / 2, layout.height / 2];
     let node = targetNode;
     while (node) {
         const 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: TreemapLayoutNode,
     clipRect: BoundingRect,
     viewAbovePath: TreemapLayoutNode[],
     viewRoot: TreemapLayoutNode,
     depth: number
 ) {
     const nodeLayout = node.getLayout();
     const nodeInViewAbovePath = viewAbovePath[depth];
     const 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
     }, true);

     // Transform to child coordinate.
     const 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: NodeModel): number {
     return model.get(PATH_UPPER_LABEL_SHOW) ? model.get(PATH_UPPER_LABEL_HEIGHT) : 0;
 }
	/*
	* 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 embedded 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, { RectLike } 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';
	import TreemapSeriesModel, { TreemapSeriesNodeItemOption } from './TreemapSeries';
	import GlobalModel from '../../model/Global';
	import ExtensionAPI from '../../core/ExtensionAPI';
	import { TreeNode } from '../../data/Tree';
	import Model from '../../model/Model';
	import { TreemapRenderPayload, TreemapMovePayload, TreemapZoomToNodePayload } from './treemapAction';

	const mathMax = Math.max;
	const mathMin = Math.min;
	const retrieveValue = zrUtil.retrieve;
	const each = zrUtil.each;

	const PATH_BORDER_WIDTH = ['itemStyle', 'borderWidth'] as const;
	const PATH_GAP_WIDTH = ['itemStyle', 'gapWidth'] as const;
	const PATH_UPPER_LABEL_SHOW = ['upperLabel', 'show'] as const;
	const PATH_UPPER_LABEL_HEIGHT = ['upperLabel', 'height'] as const;

	export interface TreemapLayoutNode extends TreeNode {
	parentNode: TreemapLayoutNode
	children: TreemapLayoutNode[]
	viewChildren: TreemapLayoutNode[]
	}

	export interface TreemapItemLayout extends RectLike {
	area: number
	isLeafRoot: boolean
	dataExtent: [number, number]

	borderWidth: number
	upperHeight: number
	upperLabelHeight: number

	isInView: boolean
	invisible: boolean

	isAboveViewRoot: boolean
	};

	type NodeModel = Model<TreemapSeriesNodeItemOption>;

	type OrderBy = 'asc' \| 'desc' \| boolean;

	type LayoutRow = TreemapLayoutNode[] & {
	area: number
	};
	/**
	* @public
	*/
	export default {
	seriesType: 'treemap',
	reset: function (
	seriesModel: TreemapSeriesModel,
	ecModel: GlobalModel,
	api: ExtensionAPI,
	payload?: TreemapZoomToNodePayload \| TreemapRenderPayload \| TreemapMovePayload
	) {
	// Layout result in each node:
	// {x, y, width, height, area, borderWidth}
	const ecWidth = api.getWidth();
	const ecHeight = api.getHeight();
	const seriesOption = seriesModel.option;

	const layoutInfo = layout.getLayoutRect(
	seriesModel.getBoxLayoutParams(),
	{
	width: api.getWidth(),
	height: api.getHeight()
	}
	);

	const size = seriesOption.size \|\| []; // Compatible with ec2.
	const containerWidth = parsePercent(
	retrieveValue(layoutInfo.width, size[0]),
	ecWidth
	);
	const containerHeight = parsePercent(
	retrieveValue(layoutInfo.height, size[1]),
	ecHeight
	);

	// Fetch payload info.
	const payloadType = payload && payload.type;
	const types = ['treemapZoomToNode', 'treemapRootToNode'];
	const targetInfo = helper
	.retrieveTargetInfo(payload, types, seriesModel);
	const rootRect = (payloadType === 'treemapRender' \|\| payloadType === 'treemapMove')
	? payload.rootRect : null;
	const viewRoot = seriesModel.getViewRoot();
	const viewAbovePath = helper.getPathToRoot(viewRoot) as TreemapLayoutNode[];

	if (payloadType !== 'treemapMove') {
	const rootSize = payloadType === 'treemapZoomToNode'
	? estimateRootSize(
	seriesModel, targetInfo, viewRoot, containerWidth, containerHeight
	)
	: rootRect
	? [rootRect.width, rootRect.height]
	: [containerWidth, containerHeight];

	let sort = seriesOption.sort;
	if (sort && sort !== 'asc' && sort !== 'desc') {
	// Default to be desc order.
	sort = 'desc';
	}
	const 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

	let 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.
	viewRootLayout = viewRoot.getLayout();
	each(viewAbovePath, function (node, index) {
	const childValue = (viewAbovePath[index + 1] \|\| viewRoot).getValue();
	node.setLayout(zrUtil.extend(
	{
	dataExtent: [childValue, childValue],
	borderWidth: 0,
	upperHeight: 0
	},
	viewRootLayout
	));
	});
	}

	const 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: TreemapLayoutNode,
	options: {
	sort?: OrderBy
	squareRatio?: number
	leafDepth?: number
	},
	hideChildren: boolean,
	depth: number
	) {
	let width;
	let height;

	if (node.isRemoved()) {
	return;
	}

	const thisLayout = node.getLayout();
	width = thisLayout.width;
	height = thisLayout.height;

	// Considering border and gap
	const nodeModel = node.getModel<TreemapSeriesNodeItemOption>();
	const borderWidth = nodeModel.get(PATH_BORDER_WIDTH);
	const halfGapWidth = nodeModel.get(PATH_GAP_WIDTH) / 2;
	const upperLabelHeight = getUpperLabelHeight(nodeModel);
	const upperHeight = Math.max(borderWidth, upperLabelHeight);
	const layoutOffset = borderWidth - halfGapWidth;
	const layoutOffsetUpper = upperHeight - halfGapWidth;

	node.setLayout({
	borderWidth: borderWidth,
	upperHeight: upperHeight,
	upperLabelHeight: upperLabelHeight
	}, true);

	width = mathMax(width - 2 * layoutOffset, 0);
	height = mathMax(height - layoutOffset - layoutOffsetUpper, 0);

	const totalArea = width * height;
	const viewChildren = initChildren(
	node, nodeModel, totalArea, options, hideChildren, depth
	);

	if (!viewChildren.length) {
	return;
	}

	const rect = {x: layoutOffset, y: layoutOffsetUpper, width: width, height: height};
	let rowFixedLength = mathMin(width, height);
	let best = Infinity; // the best row score so far
	const row = [] as LayoutRow;
	row.area = 0;

	for (let i = 0, len = viewChildren.length; i < len;) {
	const child = viewChildren[i];

	row.push(child);
	row.area += child.getLayout().area;
	const 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) {
	const childrenVisibleMin = nodeModel.get('childrenVisibleMin');
	if (childrenVisibleMin != null && totalArea < childrenVisibleMin) {
	hideChildren = true;
	}
	}

	for (let 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: TreemapLayoutNode,
	nodeModel: NodeModel,
	totalArea: number,
	options: {
	sort?: OrderBy
	leafDepth?: number
	},
	hideChildren: boolean,
	depth: number
	) {
	let viewChildren = node.children \|\| [];
	let orderBy = options.sort;
	orderBy !== 'asc' && orderBy !== 'desc' && (orderBy = null);

	const 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);

	const 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 (let i = 0, len = viewChildren.length; i < len; i++) {
	const area = viewChildren[i].getValue() as number / 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: NodeModel,
	totalArea: number,
	sum: number,
	orderBy: OrderBy,
	orderedChildren: TreemapLayoutNode[]
	) {

	// visibleMin is not supported yet when no option.sort.
	if (!orderBy) {
	return sum;
	}

	const visibleMin = nodeModel.get('visibleMin');
	const len = orderedChildren.length;
	let deletePoint = len;

	// Always travel from little value to big value.
	for (let i = len - 1; i >= 0; i--) {
	const value = orderedChildren[
	orderBy === 'asc' ? len - i - 1 : i
	].getValue() as number;

	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: TreemapLayoutNode[],
	orderBy: OrderBy
	) {
	if (orderBy) {
	viewChildren.sort(function (a, b) {
	const diff = orderBy === 'asc'
	? a.getValue() as number - (b.getValue() as number)
	: b.getValue() as number - (a.getValue() as number);
	return diff === 0
	? (orderBy === 'asc'
	? a.dataIndex - b.dataIndex : b.dataIndex - a.dataIndex
	)
	: diff;
	});
	}
	return viewChildren;
	}

	/**
	* Statistic
	*/
	function statistic(
	nodeModel: NodeModel,
	children: TreemapLayoutNode[],
	orderBy: OrderBy
	) {
	// Calculate sum.
	let sum = 0;
	for (let i = 0, len = children.length; i < len; i++) {
	sum += children[i].getValue() as number;
	}

	// 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).

	const dimension = nodeModel.get('visualDimension');
	let dataExtent: number[];

	// The same as area dimension.
	if (!children \|\| !children.length) {
	dataExtent = [NaN, NaN];
	}
	else if (dimension === 'value' && orderBy) {
	dataExtent = [
	children[children.length - 1].getValue() as number,
	children[0].getValue() as number
	];
	orderBy === 'asc' && dataExtent.reverse();
	}
	// Other dimension.
	else {
	dataExtent = [Infinity, -Infinity];
	each(children, function (child) {
	const value = child.getValue(dimension) as number;
	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: LayoutRow, rowFixedLength: number, ratio: number) {
	let areaMax = 0;
	let areaMin = Infinity;

	for (let i = 0, area, len = row.length; i < len; i++) {
	area = row[i].getLayout().area;
	if (area) {
	area < areaMin && (areaMin = area);
	area > areaMax && (areaMax = area);
	}
	}

	const squareArea = row.area * row.area;
	const 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: LayoutRow,
	rowFixedLength: number,
	rect: RectLike,
	halfGapWidth: number,
	flush?: boolean
	) {
	// 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'.
	const idx0WhenH = rowFixedLength === rect.width ? 0 : 1;
	const idx1WhenH = 1 - idx0WhenH;
	const xy = ['x', 'y'] as const;
	const wh = ['width', 'height'] as const;

	let last = rect[xy[idx0WhenH]];
	let rowOtherLength = rowFixedLength
	? row.area / rowFixedLength : 0;

	if (flush \|\| rowOtherLength > rect[wh[idx1WhenH]]) {
	rowOtherLength = rect[wh[idx1WhenH]]; // over+underflow
	}
	for (let i = 0, rowLen = row.length; i < rowLen; i++) {
	const node = row[i];
	const nodeLayout = {} as TreemapItemLayout;
	const step = rowOtherLength
	? node.getLayout().area / rowOtherLength : 0;

	const wh1 = nodeLayout[wh[idx1WhenH]] = mathMax(rowOtherLength - 2 * halfGapWidth, 0);

	// We use Math.max/min to avoid negative width/height when considering gap width.
	const remain = rect[xy[idx0WhenH]] + rect[wh[idx0WhenH]] - last;
	const modWH = (i === rowLen - 1 \|\| remain < step) ? remain : step;
	const 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 default.
	function estimateRootSize(
	seriesModel: TreemapSeriesModel,
	targetInfo: { node: TreemapLayoutNode },
	viewRoot: TreemapLayoutNode,
	containerWidth: number,
	containerHeight: number
	) {
	// If targetInfo.node exists, we zoom to the node,
	// so estimate whole width and height by target node.
	let currNode = (targetInfo \|\| {}).node;
	const defaultSize = [containerWidth, containerHeight];

	if (!currNode \|\| currNode === viewRoot) {
	return defaultSize;
	}

	let parent;
	const viewArea = containerWidth * containerHeight;
	let area = viewArea * seriesModel.option.zoomToNodeRatio;

	while (parent = currNode.parentNode) { // jshint ignore:line
	let sum = 0;
	const siblings = parent.children;

	for (let i = 0, len = siblings.length; i < len; i++) {
	sum += siblings[i].getValue() as number;
	}
	const currNodeValue = currNode.getValue() as number;
	if (currNodeValue === 0) {
	return defaultSize;
	}
	area *= sum / currNodeValue;

	// Considering border, suppose aspect ratio is 1.
	const parentModel = parent.getModel<TreemapSeriesNodeItemOption>();
	const borderWidth = parentModel.get(PATH_BORDER_WIDTH);
	const upperHeight = Math.max(borderWidth, getUpperLabelHeight(parentModel));
	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);
	const scale = Math.pow(area / viewArea, 0.5);

	return [containerWidth * scale, containerHeight * scale];
	}

	// Root position based on coord of containerGroup
	function calculateRootPosition(
	layoutInfo: layout.LayoutRect,
	rootRect: RectLike,
	targetInfo: { node: TreemapLayoutNode }
	) {
	if (rootRect) {
	return {x: rootRect.x, y: rootRect.y};
	}

	const 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.

	const targetNode = targetInfo.node;
	const layout = targetNode.getLayout();

	if (!layout) {
	return defaultPosition;
	}

	// Transform coord from local to container.
	const targetCenter = [layout.width / 2, layout.height / 2];
	let node = targetNode;
	while (node) {
	const 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: TreemapLayoutNode,
	clipRect: BoundingRect,
	viewAbovePath: TreemapLayoutNode[],
	viewRoot: TreemapLayoutNode,
	depth: number
	) {
	const nodeLayout = node.getLayout();
	const nodeInViewAbovePath = viewAbovePath[depth];
	const 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
	}, true);

	// Transform to child coordinate.
	const 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: NodeModel): number {
	return model.get(PATH_UPPER_LABEL_SHOW) ? model.get(PATH_UPPER_LABEL_HEIGHT) : 0;
	}