/*
|
* 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, { 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 whold width and heigth 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 postion base 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;
|
}
|
