前言
最近做一个矩阵图编辑器需求，其实就是一个表格编辑器。
主要要求
- 表头支持多层级行列合并，抽象出来也就是多棵树组成的表头
- 表体行单元格随表头叶子节点的变化去做diff联动
其他业务就不细述了。
具体UI
先看UI图效果
从图中可以看出单元格是通过 + - icon不断去增加删除的，有增加同级的、下级的，这样就类似一棵树了，而且树可以有多棵。
下面的图可能更加清晰，有1、2、3 三棵树。
那么第一个问题来了，在不断增加单元格的过程中，怎么去保持每棵树的行、列同步呢？，比如1单元格在不断增加子单元格的时候，1这个单元格要实现列合并，同时2这个单元格也要不断实现行合并。
要解决这个问题，需要分步骤：
第一步：按行去一行行渲染单元格
第二步：计算哪些单元格需要行合并、哪些单元格需要列合并
那么第一步，我们定义一个最简单的树的数据结构为：
type IdType = string
interface TreeItem {
id: IdType;
name: string; // 名称
level: number; // 层级
children: TreeItem[]
}
其中level 层级用来记录该节点处于树的第几层，而这也是用来确定该节点在第几行渲染，level从0开始，根节点1是0。1-1、1-2的level是1；而1-1-1,1-1-2的level是2如此。我们需要写一个方法把树转成二维数组，然后通过循环二维数组去渲染单元格:,期待的二维数组的结构如下，注意这里用二维数组也有一个取巧的地方，那就是数组arr的index 与 level相对应
arr = [
[{id, name: 1, level: 0}, {id, name: 2: level: 0}],
[{id, name: 1-1, level: 1}, {id, name: 1-2: level: 1}]
[{id, name: 1-1-1, level: 2}, {id, name: 1-1-2, level: 2}]
]
写一个转换方法
// 树转换层级数组
function generateLevelArray(treeData: TreeItem[]) {
const arr = [];
treeForEach(treeData, (item) => {
if (!Array.isArray(arr[item.level])) {
arr[item.level] = [];
}
arr[item.level].push(item);
});
return arr;
}
这里的treeForEach是一个深度遍历树节点的方法。遍历树的方法有深度优先遍历与广度优先遍历。这里用深度的原因是广度优先遍历过程中无法传递当前节点的parent；而深度优先遍历是通过递归方式，可以传递parent，省心省力完成后面的一些特色需求，所以一般没啥特殊要求的话还是深度优先遍历比较好。
// 是否有子节点，一般用来判断是否是叶子节点
export function hasChildren(item: TreeItem): boolean {
return Array.isArray(item.children) && item.children.length > 0;
}
// 深度遍历树执行回调函数
export function treeForEach(tree: TreeItem[], cb: Function, parent?: TreeItem): void {
const isFunction = typeof cb === 'function';
if (!isFunction) return;
tree.forEach((item, index) => {
const hasChild = hasChildren(item);
cb(item, index, parent);
if (hasChild) {
treeForEach(item.children, cb, item);
}
});
}
通过树转换成数组方法，我们遍历二维数组就能生成下面的表格,（先忽略“工作内容”这个单元格）
这与我们的实际需求相差甚远：
所以我们上面说的第二个步骤要实现。
再次通过观察实际效果，我们可以发现1单元格的列合并数量，其实等于它下面的叶子节点数量（没有后代的节点是叶子节点），注意这里说的是叶子节点，不是儿子节点。1单元格下面的叶子节点是1-1-1、1-1-2、1-2 。由此得出列合并的规律就是：
- 单元格不是叶子节点，因为叶子节点不需要合并
- 找出该单元格下面的叶子节点数量
那么行合并怎么算呢？比如2单元格是要三行合并成一行。通过观察1-2、2这两个单元格，我们也可以得到行合并数量的规律：
- 单元格必须为叶子节点，且它所在的level不是最大的层级level
- 找到该单元格的层级level与最大level的差距， 即等于二维数组的长度减去当前的层级： arr.length - currentLevel
由此我们可以得到一个表头二维数组的computed
const columnTree: Ref<TreeItem[]> = ref([]);
const tableHeadData = computed(() => {
const levelArray = generateLevelArray(columnTree.value);
const tableHeadData: Array<Array<TableHeadCell>> = [];
const maxLevel = levelArray.length - 1; // 最大层级
levelArray.forEach((level) => {
const row: Array<TableHeadCell> = [];
level.forEach((treeItem: TreeItem) => {
if (hasChildren(treeItem)) {
// 非叶子节点列合并
const item: TableHeadCell = {
id: treeItem.id,
name: treeItem.name,
level: treeItem.level,
colspan: getLeafNumber([treeItem]),
}
row.push(item);
} else if (treeItem.level !== maxLevel) {
// 非末端叶子节点需要行合并
const rowspan = maxLevel - treeItem.level + 1;
const item: TableHeadCell = {
id: treeItem.id,
name: treeItem.name,
level: treeItem.level,
rowspan,
}
row.push(item);
} else {
// 末端叶子节点 啥也不干
const item: TableHeadCell = {
id: treeItem.id,
name: treeItem.name,
level: treeItem.level,
}
row.push(item);
}
});
tableHeadData.push(row);
});
const firstCell: TableHeadCell = { id: FIRST_CELL_ID, name: '工作内容', rowspan: maxLevel + 1, level: 0 };
if (tableHeadData[0]) {
tableHeadData[0].unshift(firstCell);
} else {
tableHeadData[0] = [firstCell]
}
return tableHeadData;
})
// 获取叶子节点数量来实现列合并
export function getLeafNumber(tree: TreeItem[]): number {
let num = 0;
treeForEach(tree, (item: TreeItem) => {
if (!hasChildren(item)) {
num++;
}
});
return num;
}
这样子就实现我们的行合并、列合并的效果。
咋一看好像没啥问题，但是实际上却有严重的性能问题！问题就出在getLeafNumber这里，这个方法是获取节点下面有几个叶子节点的。单独算一个节点的下面的叶子节点数量是完全没有问题的，但是如果你遍历一棵树的过程中，每个节点都去算其下有几个叶子节点，这实际上是存在巨大的重复工作的，比如1节点的叶子数量应该等于1-1、1-2两者的叶子节点之和，而不是1节点算一遍、1-1、1-2自己又算一遍。
遍历一颗树，分别计算每个节点下面有几个叶子节点，最好的时间复杂度应该是O(n),怎么实现呢？
这里还是用到了递归方式，上面也说了每个节点的叶子节点数量等于它下面的儿子的叶子节点数量之和，直到该节点是叶子节点才退出递归。
// 记录每个节点下面有几个叶子节点
export function getLeafNumber(tree: TreeItem) {
function deep(node: TreeItem) {
if (!hasChildren(node)) {
return 1 // 叶子节点直接返回本身1个数量
}
// 否则有children 去计算其下的children的叶子数量之和
let num = 0;
node.children.forEach(item => {
num += deep(item);
})
return num;
}
return deep(tree);
}
参照基本逻辑实现了一版，仔细看这里还是有重复计算的问题，缺失了计算结果缓存，所以我们需要一个map来缓存计算过的节点结果，优化版：
// 记录每个节点下面有几个叶子节点
export function getLeafNumberMap(tree: TreeItem): NodeLeafNumberMap {
const nodeLeafNumberMap: NodeLeafNumberMap = Object.create(null);
function deep(node: TreeItem) {
if (!hasChildren(node)) {
nodeLeafNumberMap[node.id] = 1;
return nodeLeafNumberMap[node.id];
}
// 有children 有leaf
if (Object.hasOwn(nodeLeafNumberMap, node.id)) return nodeLeafNumberMap[node.id];
// 有children 没leaf
let num = 0;
node.children.forEach(item => {
num += deep(item);
})
nodeLeafNumberMap[node.id] = num;
return num;
}
deep(tree);
return nodeLeafNumberMap;
}
有了nodeLeafNumberMap知道每个节点的叶子数量那就好办了，上面的表头二维数组的computed可以改成下面优化版， 去掉getLeafNumber方法，改成 leafNumberMap[treeItem.id]
const tableHeadData = computed(() => {
const leafNumberMapList = columnTree.value.map(tree => getLeafNumberMap(tree));
const leafNumberMap = leafNumberMapList.reduce((prevMap, currentMap) => ({ ...prevMap, ...currentMap }), Object.create(null))
const levelArray = generateLevelArray(columnTree.value);
const tableHeadData: Array<Array<TableHeadCell>> = [];
const maxLevel = levelArray.length - 1; // 最大层级
levelArray.forEach((level) => {
const row: Array<TableHeadCell> = [];
level.forEach((treeItem: TreeItem) => {
if (hasChildren(treeItem)) {
// 非叶子节点列合并
const item: TableHeadCell = {
id: treeItem.id,
name: treeItem.name,
level: treeItem.level,
colspan: leafNumberMap[treeItem.id],
}
row.push(item);
} else if (treeItem.level !== maxLevel) {
// 非末端叶子节点需要行合并
const rowspan = maxLevel - treeItem.level + 1;
const item: TableHeadCell = {
id: treeItem.id,
name: treeItem.name,
level: treeItem.level,
rowspan,
}
row.push(item);
} else {
// 末端叶子节点 啥也不干
const item: TableHeadCell = {
id: treeItem.id,
name: treeItem.name,
level: treeItem.level,
}
row.push(item);
}
});
tableHeadData.push(row);
});
const firstCell: TableHeadCell = { id: FIRST_CELL_ID, name: '工作内容', rowspan: maxLevel + 1, level: 0 };
if (tableHeadData[0]) {
tableHeadData[0].unshift(firstCell);
} else {
tableHeadData[0] = [firstCell]
}
return tableHeadData;
})
表格导出到excel
另外一个需求就是支持导出到excel, 我采用 exceljs 这个库来导出。我觉得这是整个表格编辑器最难的地方，难点就是要拿到表头的单元格行列位置信息与合并信息。其中导出的单元格位置信息数据结构为
// sheet表格中单元格位置信息
export type SheetCellPosition = {
c: number; // 列位置
r: number // 行位置
cs: number // 列合并数
rs: number // 行合并数
}
其中每个单元格的 r \ rs \ cs 信息都可以轻松拿到，r = node.level; rs = node.rowspan; cs = node.colspan, 上面的二维数组都有，唯独这个列信息c 没有；这个列位置信息不是二维数组的每个单元格的index坐标信息，而是要包含列合并后的位置信息，总结就是
当前单元格的c = 同行的前一个单元格的c + cs
看到这里有人可能会想：既然这样子那还不简单？对二维数组的每一行进行遍历，根据上面的公式不就能知道每个单元格的c信息了吗？
确实我一开始也是这么做的，导出后发现有些单元格就不符合预期了，原因是第一行的单元格可以这么做得到单元格的对应信息没问题，回到上面的例子中
二维数组简略后应该是这样子：
[
[{name: '1'}, {name: '2'}, {name: 3}],
[{name: '1-1'}, {name: '1-2'},{name: '3-1'}, {name: '3-2'}],
[{name: '1-1-1'}, {name: '1-1-2'}],
]
从第二行开始，仔细观察，你会发现 ‘3-1’ 的c信息并不能依靠同行前面的'1-2'的c信息和cs得到，因为从图中可以看到它们之间还隔着一个“2”单元格的距离，所以不能简单遍历二维数组就能得到每个单元格的列位置信息也就是c信息。
那要怎么才能得到呢？
能不能记录不同行的信息也就是上面的“2”单元格的信息，用到的时候再加上？可以这么想，但是中间可能不仅仅是“2”一个单元格，实际导出过程中存在可能隔着好几个单元格都有的情况，而且隔着的这些单元格可能分别分布在不同的行里面！这么一想就感觉太复杂了，难度系数剧增!
现在我们整理一下思路，要知道当前单元格的列位置信息c，需要知道：
- 同行的前面的位置信息c + cs
- 类似“2”单元格这种不同行的一个或者多个单元格信息
而第2点很难计算出来，那么有没有代替方法呢？
终于经过一段时间的摸索之后我发现其实要知道“3-1”的位置不用第2点也行，我们只要知道“3”单元格这个位置信息就行了！因为第2点的信息太难计算，无论它隔着几个单元格，“3”单元格这个信息我们是可以轻易得到的，因为“3”，“3-1”在同一颗树上且是父子节点！
那么我们就可以通过遍历树的方式， 而且计算公式还是：
当前单元格的c = 同层的前一个单元格的c + cs
不过要注意，当 “当前单元格” 是同层的第一个节点的时候，它的列位置信息其实 === 父节点的列位置信息！
这样子就能通过深度遍历树得到所有单元格的正确的列位置信息了！
而且恰好第一个子节点的信息依赖父节点的信息，一次遍历即可计算出所有的节点信息，这就是我前面说的深度优先遍历算法省心省力完成的特色需求！
想通了就好办了，代码如下：
// 设置每个单元格的colIndex
function setCellColIndex(treeData: TreeItem[], positionMap: SheetCellPositionMap): SheetCellPositionMap {
// 获取单元格的列位置
function getCellColIndex(list: TreeItem[], itemIndex: number, parentColIndex: number = 0): number {
let currentIndex = itemIndex - 1
let currentItem: TreeItem
let currentItemPosition: SheetCellPosition
let c = parentColIndex;
while (currentIndex >= 0) {
currentItem = list[currentIndex];
currentItemPosition = positionMap[currentItem.id]
if (currentItemPosition.c !== 0) {
return currentItemPosition.c + currentItemPosition.cs
} else {
c = c + currentItemPosition.cs
}
currentIndex--;
}
return c;
}
treeForEach(treeData, (item, index, parent) => {
if (!parent) {
// 没有parent就是根节点
positionMap[item.id].c = getCellColIndex(treeData, index)
} else {
// 非第一行数据，先找parent.c再找自身的index和累计的cs
const parentColIndex = positionMap[parent.id].c;
// 第一个子节点就要基于父节点的colIndex来加，后面的子节点就直接拿前面兄弟节点的colIndex + cs
positionMap[item.id].c = getCellColIndex(parent.children, index, parentColIndex);
}
})
return positionMap;
}
其中的positionMap 是一个记录了 每个节点的 c 、r、 rs、 cs信息的map如：
positionMap = {
'id1': {
c: 0,
cs: 2,
r: 2,
rs: 3
},
'id2': {
c: 0,
cs: 3,
r: 1,
rs: 2
}
}
通过上面的setCellColIndex方法就能补全positionMap 的每个节点的c信息。同时我们注意到同层节点的后一个节点的结果 依赖前一个节点的结果，这其实有点类似我另外一篇文章 斐波那契数列解法有感: 递归+缓存 or 动态规划里面提到的场景。而在这里我其实用到的是“递归+缓存”的思想，而不是动态规划，因为这里是要计算所有节点的信息，动态规划只适于求某个节点的信息，动态规划在这里就不是最优解了。
最后
感谢你仔细的阅读，希望你可以从中获得一些感悟与共鸣，以上如有不对，不烦指出，不胜感激。
