一个排序问题
目录
问题背景
去年开发的一个项目管理系统，我负责其中一部分后端逻辑。问题简要概述如下：有工作项(issue)，工作项之间有父子关系，父子关系最多有三层，即：祖父->父->子。工作项可以放置在不同的泳道(lane)里，且可以在泳道之间来回拖动，拖动之后，必须在泳道内和它的家族放置在一起。即在同一个泳道内，排序必须遵循如下规则：
- 如果有兄弟，则排在最后一个兄弟后面。
- 如果没有兄弟，但有父亲，则排在父亲后面。
- 如果既没有兄弟，也没有父亲，但有祖父，则排在祖父后面。
- 如果祖父也没有，则默认放在泳道的末尾。
如图所示：
表结构
工作项
create table if not exists issue
(
id varchar(64) not null comment 'UUID' primary key,
title varchar(512) not null comment '标题',
parent_id varchar(64) null comment '父工作项ID，Epic->Feature->Story->Task->Subtask，Story->Bug',
root_id varchar(64) null comment '根工作项ID，方便查询',
type varchar(320) not null comment '工作项类型，支持Epic，Feature，Story，Task，Subtask，Bug六种',
lane_id varchar(64) null comment '泳道ID',
sort int(8) null comment '排序，工作项在泳道中的排序'
) comment '工作项';
泳道
create table if not exists sprint_lane
(
id varchar(64) not null comment 'UUID' primary key,
name varchar(255) not null comment '名称',
) comment '迭代泳道';
解决方案
思路
泳道里的工作项实际上组成了一个多叉树，为了处理方便，引入一个虚拟祖先，这样便形成了四层的多叉树结构：
这样一来，排序问题就变成了一个多叉树的先序遍历，初始状态下的排序是这样进行的：
- 获取整个泳道内的工作项总数，假设总数为 $n_{1}$。
- 获取那些不在此泳道内的，但是和此泳道内的工作项有关联的工作项总数，比如子在此泳道内，父却在另一个泳道的。假设这个数字为 $n_{2}$。
- 按照总数$n_{1}+n_{2}$，先序遍历泳道内的这棵树，从高到低给工作项们排好序(即设置好sort值)。
- 遍历排序完后，把不在此泳道的父与祖issue剔除,再按照sort值重排下。
代码
排序初始化
/**
* @param issuesInLane 待排序的issue列表,可能有有序的+无序的,也可能全是未排序的
* @return 排序后的issue列表
*/
private List<Issue> sortIssues(List<Issue> issuesInLane) {
Set<String> issueIdsInLane = issuesInLane.stream().map(Issue::getId).collect(Collectors.toSet());
if (CollUtil.isEmpty(issuesInLane)) {
return issuesInLane;
}
/*
遍历issuesInLane，将不在此泳道的祖先也加入到issuesInLane中，便于levelOrder排序，排序完成后再作调整（看下面的removeIf）
需要递归一层一层往上找，直到找不到parentId为止，所以这里用了while循环，直到tempParentIds为空
因为光看parentId和rootId还是不够，层级远远不止三层，比如：epic->feature->story->bug
epic和feature是不需要参与排序的，但是为了确定story和bug的排序，需要将epic和feature也加入到issuesInLane中
排序完成后再把它们移除，所以看到下面的while循环查询没有加.notIn(Issue::getType, IssueTypeEnum.ISSUE_TYPE_NO_NEED_SORT)这个条件
*/
Set<String> tempParentIds =
issuesInLane.stream().map(Issue::getParentId)
.filter(parentId -> StrUtil.isNotEmpty(parentId) && !issueIdsInLane.contains(parentId))
.collect(Collectors.toSet());
Set<String> issueIdsNotInLane = new HashSet<>(tempParentIds);
while (CollUtil.isNotEmpty(tempParentIds)) {
Set<String> parentIds = issueMapper.listIssue(
new LambdaQueryWrapper<Issue>().in(Issue::getId, tempParentIds)).stream()
.map(Issue::getParentId)
.filter(parentId -> StrUtil.isNotEmpty(parentId) && !issueIdsInLane.contains(parentId))
.collect(Collectors.toSet());
issueIdsNotInLane.addAll(parentIds);
tempParentIds = parentIds;
}
if (CollUtil.isNotEmpty(issueIdsNotInLane)) {
List<Issue> issuesNotInLane =
issueMapper.listIssue(new LambdaQueryWrapper<Issue>().in(Issue::getId, issueIdsNotInLane));
issuesInLane.addAll(issuesNotInLane);
}
//按父分类,key为父id，value为子issue列表
Map<Optional<String>, List<Issue>> parentChildRel = issuesInLane.stream().filter(Objects::nonNull)
//Optional.empty()表示一个虚拟的祖先,本来只有三层,为了后续树的遍历方便,增加一个虚拟祖先,变成了:孙->子->父->虚拟祖先
//因为groupingBy不允许null key
//不允许null key，用Optional包装一下，以前这里用-1，后面保存数据库时还要重新设置为null，多了一次遍历的开销，
.collect(Collectors.groupingBy(issue -> Optional.ofNullable(issue.getParentId())));
Map<Optional<String>, Issue> issueMap = issuesInLane.stream().filter(Objects::nonNull)
.collect(Collectors.toMap(issue -> Optional.ofNullable(issue.getId()), Function.identity()));
//注意这里的排序是同一级的排序,也就是兄弟间的排序,不涉及父子,父子关系的体现在下面的levelOrder方法中
for (List<Issue> siblings : parentChildRel.values()) {
siblings.sort((issue1, issue2) -> {
if (issue1.getSort() == null || issue2.getSort() == null) {
//只要有一个sort为空，则按照sequence排序
return issue2.getSequence().compareTo(issue1.getSequence());
}
//两个都有序,按照原来的sort排序
return issue2.getSort().compareTo(issue1.getSort());
});
}
//树的先序遍历
AtomicInteger counter = new AtomicInteger(issuesInLane.size());
List<Issue> result = new ArrayList<>();
//Optional.empty()表示虚拟的祖先
preOrder(Optional.empty(), result, parentChildRel, issueMap, counter);
//遍历排序完后，把不在此泳道的父与祖issue剔除,再按照sort值重排下
result.removeIf(issue -> issueIdsNotInLane.contains(issue.getId()));
result.sort(Comparator.comparingInt(Issue::getSort).reversed());
AtomicInteger pureSort = new AtomicInteger(result.size());
result.forEach(issue -> issue.setSort(pureSort.getAndDecrement()));
return result;
}
//多叉树的先序遍历
// NULL
// / | \
// / | \
// 2 3 4
// / \ / | \
// 5 6 7 8 9
// / / | \
// 10 11 12 13
/**
* preOrder的遍历顺序是NULL 2 5 10 6 11 12 13 3 4 7 8 9
* 排sort
*
* @param rootIssueId 树的根节点
* @param result 返回排好序的结果
* @param parentChildRel 父子关系，key为父id，value为儿子的集合
* @param issueMap 所有issue的map，key为issueId，value为issue
* @param counter 计数器，用于给每个issue的sort赋值，从高到低递减
* @see <a href="https://www.geeksforgeeks.org/iterative-preorder-traversal-of-a-n-ary-tree/">多叉树的先序遍历</a>
*/
private static void preOrder(Optional<String> rootIssueId, List<Issue> result,
Map<Optional<String>, List<Issue>> parentChildRel,
Map<Optional<String>, Issue> issueMap, AtomicInteger counter) {
//虚拟祖先为Optional.empty(),不要加进去
if (rootIssueId.isPresent()) {
Issue issue = issueMap.get(rootIssueId);
issue.setSort(counter.getAndDecrement());
result.add(issue);
}
List<Issue> children = parentChildRel.get(rootIssueId);
if (CollUtil.isEmpty(children)) {
return;
}
for (Issue child : children) {
preOrder(Optional.of(child.getId()), result, parentChildRel, issueMap, counter);
}
}
跨泳道拖动排序
@Data
public class CrossLaneIssueSortVo extends BaseVo implements Serializable {
private static final long serialVersionUID = 1L;
@NotEmpty(message = "项目ID")
private String projectId;
@NotEmpty(message = "工作项ID")
private String issueId;
@NotEmpty(message = "目标泳道ID")
private String targetLaneId;
@NotEmpty(message = "原泳道ID")
private String sourceLaneId;
}
/**
* 跨泳道工作项排序
* 1.如果目标泳道内没有该issue的家族（家族指的是父、子、孙、兄），则放到泳道最下面
* 2.如果存在家族，则和家族放一起，家族的最后一个，即：有兄弟，放兄弟最后，有父亲，无兄弟，放父后面，无兄弟，无父亲，挂在祖父后面。
* 总而言之，要和家族聚集在一起
* @param vo
*/
public void sortIssueCrossLane(CrossLaneIssueSortVo vo) {
//跨泳道拖动只会拖一个,不考虑父子关系
/*
将工作项拖动到 新泳道后，默认排在该”泳道“的最后一个。
无论该泳道有几个 状态，也无论拖进哪个状态框，
拖过去后默认直接排在该泳道的最后一个即可
（特殊情况：存在父子关系的工作项，子工作项始终排在父工作项下）
源泳道的工作项排序需要更新,大于此issue的全-1
调用此接口前,前端已经调用了updateIssue接口更新了issue状态,也就是说逻辑上,此时这个issue已经在新泳道了,只不过它的sort还没有更新
*/
String targetLaneId = vo.getTargetLaneId();
SprintLane targetLane =
sprintLaneMapper.selectOne(new LambdaQueryWrapper<SprintLane>().eq(SprintLane::getId, targetLaneId));
if (Objects.isNull(targetLane)) {
ExceptionUtils.validParamException(targetLaneId, "targetLaneId", HttpStatus.NOT_FOUND,
ProjectsExceptionCode.INVALID_SPRINT_LANE_NOTFOUND);
}
String sourceLaneId = vo.getSourceLaneId();
SprintLane sourceLane =
sprintLaneMapper.selectOne(new LambdaQueryWrapper<SprintLane>().eq(SprintLane::getId, sourceLaneId));
if (Objects.isNull(sourceLane)) {
ExceptionUtils.validParamException(sourceLaneId, "sourceLaneId", HttpStatus.NOT_FOUND,
ProjectsExceptionCode.INVALID_SPRINT_LANE_NOTFOUND);
}
String issueId = vo.getIssueId();
Issue issue = issueService.getById(issueId);
if (Objects.isNull(issue)) {
ExceptionUtils.validParamException(issueId, "issueId", HttpStatus.NOT_FOUND,
ProjectsExceptionCode.INVALID_ISSUE_NOT_FOUND);
}
String sprintId = issue.getSprintId();
String projectId = vo.getProjectId();
Set<String> stateIdsInTargetLane =
Arrays.stream(targetLane.getStateIds().split(",")).collect(Collectors.toSet());
List<Issue> issuesInTargetLane = issueMapper.listIssue(
new LambdaQueryWrapper<Issue>().in(Issue::getStateId, stateIdsInTargetLane)
.in(Issue::getProjectId, projectId).notIn(Issue::getType, IssueTypeEnum.ISSUE_TYPE_NO_NEED_SORT)
//eq是不为null的情况，isNotNull是为null的情况
.eq(StrUtil.isNotEmpty(sprintId), Issue::getSprintId, sprintId)
.isNull(StrUtil.isEmpty(sprintId), Issue::getSprintId)
//排除掉自己，因为调用此接口前,前端已经调用了updateIssue接口更新了issue状态,也就是说逻辑上,此时这个issue已经在targetLane了,只不过它的sort还没有更新
.ne(Issue::getId, issueId));
if (CollUtil.isEmpty(issuesInTargetLane)) {
//1.如果目标泳道是空的,直接插入,sort值为1
//注意！！！updateIssueSortInSourceLane和issue.setSort顺序不能乱！！！因为updateIssueSortInSourceLane里要和原来的sort比较
updateIssueSortInSourceLane(projectId, sprintId, sourceLane, issue);
issue.setSort(1);
issueService.updateById(issue);
return;
}
//2.如果目标泳道不是空的,则找到被拖工作项最终的归属
//先找同泳道内的父亲
String parentId = issue.getParentId();
Issue parentIssue = issueService.getOne(new LambdaQueryWrapper<Issue>().eq(Issue::getProjectId, projectId)
.in(Issue::getStateId, stateIdsInTargetLane)
.eq(StrUtil.isNotEmpty(sprintId), Issue::getSprintId, sprintId)
.isNull(StrUtil.isEmpty(sprintId), Issue::getSprintId).eq(Issue::getId, parentId));
if (StringUtils.isBlank(parentId) || Objects.isNull(parentIssue)) {
//根本没有父亲，或者父亲不在泳道内,则看是否在泳道内有子嗣
List<Issue> descendants = listFamily(issueId, sprintId, stateIdsInTargetLane, false);
if (CollUtil.isEmpty(descendants)) {
//在泳道内无依无靠（上无祖先，下无子嗣）则插入到最后,issues每个工作项的sort值都要+1
issuesInTargetLane.forEach(item -> item.setSort(item.getSort() + 1));
updateIssueSortInSourceLane(projectId, sprintId, sourceLane, issue);
issue.setSort(1);
issuesInTargetLane.add(issue);
if (CollUtil.isNotEmpty(issuesInTargetLane)) {
issueService.updateBatchById(issuesInTargetLane);
}
return;
}
//有后代，放在后代前面，找出后代最大的sort值，大于sort值的issue，全都+1，然后插入到该sort值+1的位置
int maxSort = descendants.stream().mapToInt(Issue::getSort).max().orElse(1);
issuesInTargetLane.stream().filter(item -> item.getSort() > maxSort)
.forEach(item -> item.setSort(item.getSort() + 1));
updateIssueSortInSourceLane(projectId, sprintId, sourceLane, issue);
issue.setSort(maxSort + 1);
issuesInTargetLane.add(issue);
if (CollUtil.isNotEmpty(issuesInTargetLane)) {
issueService.updateBatchById(issuesInTargetLane);
}
return;
}
//有同一泳道的父亲,挂在父亲后面
List<Issue> siblings = issueService.list(new LambdaQueryWrapper<Issue>().eq(Issue::getParentId, parentId)
.in(Issue::getStateId, stateIdsInTargetLane)
//排除掉自己
.ne(Issue::getId, issueId).in(Issue::getProjectId, projectId));
if (CollUtil.isEmpty(siblings)) {
//没有兄弟,则跟在父亲后面,所有大于等于父亲的sort值都要+1,自己占据父亲原来的位置
updateIssueSortInSourceLane(projectId, sprintId, sourceLane, issue);
insertAfter(issuesInTargetLane, issue, parentIssue.getSort());
return;
}
//有兄弟,则挂在最后一个兄弟后面,查询出最小sort值的兄弟,自己占据最小兄弟的位置,其他大于等于最小兄弟的sort值都要+1
Issue minSibling = siblings.stream().min(Comparator.comparing(Issue::getSort)).get();
//最后,把源泳道里大于等于源工作项的sort值都要-1
updateIssueSortInSourceLane(projectId, sprintId, sourceLane, issue);
insertAfter(issuesInTargetLane, issue, minSibling.getSort());
}
/**
* 插入到targetSort的位置,大于等于targetSort的sort值都要+1
*
* @param issuesInTargetLane 目标泳道的工作项集合
* @param issue 插入的工作项
* @param targetSort 插入的目标位置
*/
private void insertAfter(List<Issue> issuesInTargetLane, Issue issue, Integer targetSort) {
//插入到目标工作项后面
issue.setSort(targetSort);
issuesInTargetLane.stream().filter(item -> item.getSort() >= targetSort)
.forEach(item -> item.setSort(item.getSort() + 1));
issuesInTargetLane.add(issue);
if (CollUtil.isNotEmpty(issuesInTargetLane)) {
issueService.updateBatchById(issuesInTargetLane);
}
}
/**
* 查询此issueId下的所有工作项和子工作项
* 不包括epic和feature，因为epic和feature不会在泳道中显示，不参与排序
*
* @param issueId 祖先
* @param sprintId 迭代id
* @param stateIds 泳道里的状态
* @param includeSelf 返回的结果是否包括祖先自己
* @return 家族
*/
private List<Issue> listFamily(String issueId, String sprintId, Set<String> stateIds, boolean includeSelf) {
List<Issue> result = new ArrayList<>();
if (StringUtils.isEmpty(issueId)) {
return result;
}
if (includeSelf) {
List<Issue> self = issueMapper.listIssue(
new LambdaQueryWrapper<Issue>().eq(Issue::getId, issueId).in(Issue::getStateId, stateIds)
.eq(StrUtil.isNotEmpty(sprintId), Issue::getSprintId, sprintId)
.isNull(StrUtil.isEmpty(sprintId), Issue::getSprintId)
.notIn(Issue::getType, IssueTypeEnum.ISSUE_TYPE_NO_NEED_SORT));
result.addAll(self);
}
List<Issue> children = issueMapper.listIssue(
new LambdaQueryWrapper<Issue>().in(Issue::getParentId, issueId).in(Issue::getStateId, stateIds)
.eq(StrUtil.isNotEmpty(sprintId), Issue::getSprintId, sprintId)
.isNull(StrUtil.isEmpty(sprintId), Issue::getSprintId)
.notIn(Issue::getType, IssueTypeEnum.ISSUE_TYPE_NO_NEED_SORT));
result.addAll(children);
if (CollUtil.isNotEmpty(children)) {
List<String> childrenIds = children.stream().map(Issue::getId).collect(Collectors.toList());
List<Issue> grandChildren = issueMapper.listIssue(
new LambdaQueryWrapper<Issue>().in(Issue::getParentId, childrenIds).in(Issue::getStateId, stateIds)
.eq(StrUtil.isNotEmpty(sprintId), Issue::getSprintId, sprintId)
.isNull(StrUtil.isEmpty(sprintId), Issue::getSprintId)
.notIn(Issue::getType, IssueTypeEnum.ISSUE_TYPE_NO_NEED_SORT));
result.addAll(grandChildren);
}
return result;
}
/**
* 更新原泳道中的issue排序
*
* @param projectId 项目id
* @param sprintId 迭代id
* @param sourceLane 源泳道
* @param issue 拖拽出去的工作项
*/
private void updateIssueSortInSourceLane(String projectId, String sprintId, SprintLane sourceLane, Issue issue) {
List<String> stateIdsInSourceLane =
Arrays.stream(sourceLane.getStateIds().split(",")).collect(Collectors.toList());
List<Issue> issuesInSourceLane = issueMapper.listIssue(
new LambdaQueryWrapper<Issue>().in(Issue::getStateId, stateIdsInSourceLane)
.in(Issue::getProjectId, projectId)
.eq(StrUtil.isNotEmpty(sprintId), Issue::getSprintId, sprintId)
.isNull(StrUtil.isEmpty(sprintId), Issue::getSprintId)
.notIn(Issue::getType, IssueTypeEnum.ISSUE_TYPE_NO_NEED_SORT));
//大于等于拖拽出去的工作项的sort值都要-1
issuesInSourceLane.forEach(item -> {
if (item.getSort() >= issue.getSort() && !item.getId().equals(issue.getId())) {
item.setSort(item.getSort() - 1);
}
});
if (CollUtil.isNotEmpty(issuesInSourceLane)) {
issueService.updateBatchById(issuesInSourceLane);
}
}