有向无环图在CoordinatorLayout中的应用

本篇涉及到的概念:

CoordinatorLayout

https://www.jianshu.com/p/d4df913132a3
图相关概念
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V, E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
图按照边的有无方向性分为无向图和有向图。
图中某个节点与其他节点的直连边条数称为该节点的度。有向图中，指向其他节点的边成为出度，被其他节点指向的边称为入度。
如果在有向图中，无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。

想要理解拓扑排序,可参考这里的课程表算法题解:
207. 课程表

在图的基本算法中，根据访问节点的顺序，可分为广度优先搜索（BFS）和深度优先搜索（DFS）.
一般用BFS能做的,DFS也能实现.
当需要搜索整个树时，通常会使用深度优先搜索.DFS比BFS更节省空间.
CoordinatorLayout中使用DFS实现拓扑排序.

这里我问了下chatgpt.

1:为什么这里使用dfs
答:在该示例中，使用 DFS 的主要原因是 CoordinatorLayout中的每个子视图都可能与其他子视图发生交互，而 DFS 可以有效地处理这种情况。与 BFS 不同，DFS 一次只能遍历一个分支，这种特性使得 DFS 更适合处理具有多个互相交错的分支的问题。在 CoordinatorLayout中，每个子视图都可以有多个相邻视图，这意味着视图之间的交互可能构成一个分支。因此，使用 DFS 可以更好地处理这种情况。
2:请告诉我coordinatorlayout为什么使用了dfs进行拓扑排序
答:
CoordinatorLayout 是一个用于协调子视图之间交互的布局容器，可以协调子视图之间的滚动，可拓展、可定制的属性、协调子视图之间的事件处理等。
在 CoordinatorLayout 中，每个子视图都可以具有依赖关系（DependsOn）和偏移量（layout_anchor）。例如，一个子视图可以依赖于另一个子视图的位置或状态，并根据需要调整自己的位置或状态。因此，在绘制子视图之前，需要对子视图之间的依赖关系进行拓扑排序，以确保每个子视图都能够正确地获取所依赖的状态或位置。
为了实现这种拓扑排序，CoordinatorLayout 使用了深度优先搜索（DFS）算法。深度优先搜索算法可以遍历图中所有的节点，并将它们的拓扑排序存储在一个栈中。遍历完成后，栈中的元素按照拓扑排序的顺序依次出栈，然后根据拓扑排序的结果来绘制子视图。这样，就可以确保每个子视图都能够正确地获取所依赖的状态或位置，从而实现了 CoordinatorLayout 的功能。
3:为什么这里不使用bfs
答:虽然广度优先搜索（BFS）和深度优先搜索（DFS）都可以用于拓扑排序，但是在实现 CoordinatorLayout 时，使用 DFS 更为方便和高效。
首先，CoordinatorLayout 中的子视图数量通常不会太大，因此使用 DFS 可以避免创建大量的队列和节点对象，从而节省内存开销。
其次，CoordinatorLayout 中的子视图通常具有多个依赖关系，而 BFS 在处理多个依赖关系时需要遍历整个图，导致时间复杂度较高。相比之下，DFS 可以更快速地处理多个依赖关系，因为 DFS 是从一个节点开始一直遍历到底层，直到无法再进行下去时才回溯到上一层，这样可以在保证正确性的前提下，尽可能少地遍历整个图。
因此，虽然 BFS 也可以用于 CoordinatorLayout 的实现，但是在实际开发中，使用 DFS 更为常见和方便。

android 10 以后,SimpleArrayMap.java 被提取到androidx源码中了,并用kotlin重写,并删除了缓存相关部分.不在superproject目录下了,Android中部分系统应用用kotlin重写了,函数式编程真是势不可挡.
cs.android.com上搜不出来SimpleArrayMap.java ,aospxref上可搜索.最近aosp网站挂了不少.

给出以下几个主要涉及的类.
superproject仓库:
SimpleArrayMap.java
https://cs.android.com/android/platform/superproject/+/android-9.0.0_r40:frameworks/support/collection/src/main/java/androidx/collection/SimpleArrayMap.java
SimpleArrayMap.java
http://aospxref.com/android-9.0.0_r61/xref/frameworks/support/collection/src/main/java/androidx/collection/SimpleArrayMap.java

androidx仓库:
CoordinatorLayout.java
https://cs.android.com/androidx/platform/frameworks/support/+/androidx-main:coordinatorlayout/coordinatorlayout/src/main/java/androidx/coordinatorlayout/widget/CoordinatorLayout.java
DirectedAcyclicGraph.java
https://cs.android.com/androidx/platform/frameworks/support/+/androidx-main:coordinatorlayout/coordinatorlayout/src/main/java/androidx/coordinatorlayout/widget/DirectedAcyclicGraph.java
SimpleArrayMap.kt
https://cs.android.com/androidx/platform/frameworks/support/+/androidx-main:collection/collection/src/commonMain/kotlin/androidx/collection/SimpleArrayMap.kt

SimpleArrayMap 的实现方式和工作过程使其内存占用更小，在数据量不大时效率更高.底层数据结构为数组,通过binarySearch(二分法)去查找数据.
https://cs.android.com/androidx/platform/frameworks/support/+/androidx-main:collection/collection/src/commonMain/kotlin/androidx/collection/internal/ContainerHelpers.kt

// Same as Arrays.binarySearch(), but doesn't do any argument validation. Very importantly, also
// guarantees consistent result on duplicate values, which is required for indexOfNull in
// SimpleArrayMap, because the mapped hash for `null` is 0, the same as default initialized value.
internal fun binarySearch(array: IntArray, size: Int, value: Int): Int {
    var lo = 0
    var hi = size - 1
    while (lo <= hi) {
        val mid = lo + hi ushr 1
        val midVal = array[mid]
        if (midVal < value) {
            lo = mid + 1
        } else if (midVal > value) {
            hi = mid - 1
        } else {
            return mid // value found
        }
    }
    return lo.inv() // value not present
}

https://cs.android.com/androidx/platform/frameworks/support/+/androidx-main:coordinatorlayout/coordinatorlayout/src/main/java/androidx/coordinatorlayout/widget/DirectedAcyclicGraph.java

    /**
     * Returns a topologically sorted list of the nodes in this graph. This uses the DFS algorithm
     * as described by Cormen et al. (2001). If this graph contains cyclic dependencies then this
     * method will throw a {@link RuntimeException}.
     *
     * <p>The resulting list will be ordered such that index 0 will contain the node at the bottom
     * of the graph. The node at the end of the list will have no dependencies on other nodes.</p>
     */
    @NonNull
    public ArrayList<T> getSortedList() {
        mSortResult.clear();
        mSortTmpMarked.clear();

        // Start a DFS from each node in the graph
        for (int i = 0, size = mGraph.size(); i < size; i++) {
            dfs(mGraph.keyAt(i), mSortResult, mSortTmpMarked);
        }

        return mSortResult;
    }

    private void dfs(final T node, final ArrayList<T> result, final HashSet<T> tmpMarked) {
        if (result.contains(node)) {
            // We've already seen and added the node to the result list, skip...
            return;
        }
        if (tmpMarked.contains(node)) {
            throw new RuntimeException("This graph contains cyclic dependencies");
        }
        // Temporarily mark the node
        tmpMarked.add(node);
        // Recursively dfs all of the node's edges
        final ArrayList<T> edges = mGraph.get(node);
        if (edges != null) {
            for (int i = 0, size = edges.size(); i < size; i++) {
                dfs(edges.get(i), result, tmpMarked);
            }
        }
        // Unmark the node from the temporary list
        tmpMarked.remove(node);
        // Finally add it to the result list
        result.add(node);
    }

https://cs.android.com/androidx/platform/frameworks/support/+/androidx-main:coordinatorlayout/coordinatorlayout/src/main/java/androidx/coordinatorlayout/widget/CoordinatorLayout.java

    private void prepareChildren() {
        mDependencySortedChildren.clear();
        mChildDag.clear();

        for (int i = 0, count = getChildCount(); i < count; i++) {
            final View view = getChildAt(i);

            final LayoutParams lp = getResolvedLayoutParams(view);
            lp.findAnchorView(this, view);

            mChildDag.addNode(view);

            // Now iterate again over the other children, adding any dependencies to the graph
            for (int j = 0; j < count; j++) {
                if (j == i) {
                    continue;
                }
                final View other = getChildAt(j);
                if (lp.dependsOn(this, view, other)) {
                    if (!mChildDag.contains(other)) {
                        // Make sure that the other node is added
                        mChildDag.addNode(other);
                    }
                    // Now add the dependency to the graph
                    mChildDag.addEdge(other, view);
                }
            }
        }

        // Finally add the sorted graph list to our list
        mDependencySortedChildren.addAll(mChildDag.getSortedList());
        // We also need to reverse the result since we want the start of the list to contain
        // Views which have no dependencies, then dependent views after that
        Collections.reverse(mDependencySortedChildren);
    }

SimpleArrayMap使用数组+二分法,是高效率查找的数据结构+算法组合.
android 使用 DirectedAcyclicGraph.java,来代表一个有向无环图DAG,并在其中使用DFS实现了拓扑排序(getSortedList).
图的存储一般有2种,邻接矩阵和邻接表.
在邻接表实现中，保存Graph 对象中的所有顶点的主列表，然后图中的每个顶点对象维护连接到的其他顶点的列表。这里通过addNode和addEdge,使用邻接表存储图.
https://cs.android.com/androidx/platform/frameworks/support/+/androidx-main:coordinatorlayout/coordinatorlayout/src/main/java/androidx/coordinatorlayout/widget/DirectedAcyclicGraph.java

 ArrayList<T> edges = mGraph.get(node);
        if (edges == null) {
            // If edges is null, we should try and get one from the pool and add it to the graph
            edges = getEmptyList();
            mGraph.put(node, edges);
        }
        // Finally add the edge to the list
        edges.add(incomingEdge);

最后在CoordinatorLayout.java中,getSortedList会被onMeasure调用.
参考链接:
数据结构与算法之美
CoordinatorLayout 子 View 之间的依赖管理机制 —— 有向无环图
图论（1）：有向无环图的定义及应用

图的基本算法（BFS和DFS）
浅析深度优先和广度优先遍历实现过程、区别及使用场景

SimpleArrayMap 源码分析
SimpleArrayMap 源码 (你还是只会用 HashMap 么？)

邻接矩阵和邻接表