improve ActionQueue.InsertActionSorter's sort() by topological sorting algorithm

Description

The implementation of ActionQueue.InsertActionSorter has gone through quite some back and forth. Currently it settles on some bubble sorting algorithm which has following drawbacks:

  • time complexity is unnecessarily high (i.e O(n^2));

  • no reliable way to detect circular dependencies;

  • not ideal code readability, which usually leads to difficult maintainability;

Topological sorting (https://en.wikipedia.org/wiki/Topological_sorting) is the canonical solution for such ordering in face of inter dependencies. Our case is a simplified topological sorting problem for maximally only one dependency exists for each item to be sorted. It will solve all the above issues ending up with elegant, quick and maintainable implementation.

Environment

None

Assignee

Nathan Xu

Reporter

Nathan Xu

Fix versions

None

Labels

None

backPortable

None

Suitable for new contributors

Yes, likely

Requires Release Note

None

backportDecision

None

Components

Affects versions

Priority

Major
Configure