_find2CommonAncestor(a, b) {
if (a === this.layer || b === this.layer) {
return this.layer;
}
const la = this._computeLinkLength(a);
const lb = this._computeLinkLength(b);
let diff = Math.abs(la - lb);
if (la < lb)[a, b] = [b, a];
while (diff--) {
a = a.group;
}
while (a && b) {
if (a === b) {
return a;
}
a = a.group;
b = b.group;
}
return this.layer;
}
Eqx 组合管理
组合(EqxGroup)作为编辑器中的可编辑元素,同组件一样也具有增/删/改/查功能,下面对核心算法进行简要的介绍。
合并组合
首先组合只能由组件/组合合并生成,不能存在空组合,并且组合作为一个树状的结构其深度理论上是无限的,但是在编辑器中默认限制为2层,实现起来也比较简单,只需要使用待合并项作为参数,实例化一个新的组合到当前层即可:
比较麻烦的是,组合业务逻辑中涉及到的约束比较多:
抢夺性合并
假设我们有一个场景示意如图,当前图层中有一个组合 A 和一个组件 C,组合 A 中包含一个组件 B,这时我们想要合并组件 B 和组件 C,结果如何?
对于这个场景,在编辑器中得到的结果如图所示,组件 B 和组件 C 合并为组合 D,并且组合 D 挂载在当前层上,组合 A 消失。我们规定的第一个约束是抢夺性合并,即在合并组合 D 时,由于组件 B 挂载在组合 A 上,所以需要从组合 A 中删除再挂载到组合 D 上。
不允许存在空组合
在约束一的场景中也有提到,由于组件 B 从组合 A 中移除,导致组合 A 变成空组合,所以需要将组合 A 删除,这是我们规定的第二个原则。
合并组合挂载在待合并项的最低公共祖先上
假设我们有一个场景示意如图,我们需要把组件 E 和组件 C 合并,结果如何?
对于这个场景,在编辑器中得到的结果如图所示,组件 E 和组件 C 合并为组合 F,并且组合 F 挂载在组合 D 上。这里不难看出组合 F 挂载的目标对象是,待合并项组件 E 和组件 C 的最低公共祖先,也就是我们的第三个约束。
最低公共祖先
在这里我们的需求是在以图层为根节点的多叉树中寻找多个节点的最低公共祖先,这是一道比较经典的数据结构/算法题目。我们不妨先考虑寻找两个节点的最低公共祖先,有几种不同的解决方案,我们选择在每个组件/组合中持有指向其父组合/图层的引用,相当于每个节点都持有指向父节点的指针,那么这个问题就变成寻找两个单向链表的第一个公共节点:
实现 _find2CommonAncestor 方法后不难用循环写出 _findCommonAncestor 方法,就可以找到多个待合并项的最低公共祖先。
保持组件层级关系
以约束三中的场景为例,在图层管理中的组件层级关系自高到低从大到小,如下所示:
把组合 E 和组合 C 合并后的图层管理中的组件层级关系如下所示,这是因为组合本身是没有层级概念的(因为它只表示组件间的关系),我们规定组合的层级是其子孙组件中层级最高的组件层级,所以就出现这样的结果,组合 F 的层级高于组件 B,并且在组合 F 中组件 E 的层级高于组件 C。
在约束四中,我们规定合并组合时要刷新组件层级,目的是如果拆分组合,得到的结果应该如下所示,即保持图层管理中组件的相对位置不变,这里相当于组件 C 沾光组件 E,在合并组合的过程中提升层级。
代码如下:
避免待合并项间存在嵌套的情况
判断待合并项中是否存在互相嵌套的情况,比如组合 A 和组合 A 的子组件 B 进行合并,这样的行为被视为无效操作。
限制组合嵌套的深度
组合在理论上是可以无限潜逃的,就好像一颗非常非常深的多叉树,显然在开放给用户使用时我们需要限制组合嵌套的深度。
在这里我们的做法时,把超出限制深度的组合拆分成组件重新插入至父组合中,可以理解为把超出限制的组合递归拆分,也可以理解成一种数组的扁平化处理。
更新组合/组件当前状态
跨层合并处理
具备图层编辑能力的用户,在操作图层管理时可能出现跨图层合并组合的情况,这里我们规定在跨层合并发生时遵循3个原则:
其他特殊处理
拆分组合
存在组合的合并,相应的就会有组合的拆分,拆分的逻辑相对合并组合来说相当简单一些,就是把待拆分组合中的子孙元素挂载到其父组合/层中即可。
子孙元素重新挂载
删除待拆分组合
其他特殊处理
复制列表项
题目中说的列表项是一个基于图层管理的的概念(由于图层管理中所有图层/组合/组件是按照层级关系呈列表状),实际上就是可编辑元素 EqxItem 的复制。
复制组件
复制组件时还涉及到触发的复制,在上述代码中注释掉没有体现,在此不赘述。
复制组合
组合复制比较简单,就是复制其子组件然后合并返回一个新组合的递归过程。
Eqx 组合管理至此结束。