写在前面

这几天接触了CoordinatorLayout和所谓layout_behavior，然后进一步理了一遍源码。有两点惊艳到了我，一个是嵌套滑动机制，再一个便是依赖管理机制。

对于嵌套滑动NestedScroll的分析，网上有挺多博客。那本文打算从依赖管理的角度来讲一些东西。

效果图

这是一个模仿java继承关系的例子，定义了一个DependencyBehavior来描述继承关系。
即A extends B代表A DependsOn B，我拖动B时，A也会跟着动：

源码

https://github.com/fashare2015/DependencyBehavior

分析

实现就不说了，只是定义一个DependencyBehavior，简单的实现了两个回调：

• layoutDependsOn()
• onDependentViewChanged()

然后，用这个DependencyBehavior，把7个TextView串起来，即根据继承关系建立好依赖。

建模 —— 有向无环图

那CoordinatorLayout是怎么管理这么复杂的树形依赖呢？事实上，依赖关系可能更复杂，比如说我有一个类MapList，既实现了Map又实现了List，此时用树就无法表达它。这个场景是一个有向无环图，CoordinatorLayout里正是用这个数据结构来建模的。

图的表示

mChildDag是一个有向无环图，保存了边(依赖)的信息。其中 DirectedAcyclicGraph的实现使用邻接表实现的，邻接表 = 数组嵌套链表，是图的常规表示方式。本质上和HashMap的实现差不多，从图的角度看，HashMap也是一个有向无环图。

public class CoordinatorLayout extends ViewGroup implements NestedScrollingParent {
    private final List<View> mDependencySortedChildren = new ArrayList<>(); // 所有子节点
    private final DirectedAcyclicGraph<View> mChildDag = new DirectedAcyclicGraph<>(); // 有向无环图,保存了边(依赖)的信息
}

建图

A DependsOn B可以用一条边表示，代码中方向为B -> A，也可以反过来建图，得到的拓扑序相反而已，其他没区别。那我们按照B -> A来建一下图：

PS：可以看到，形成了一个树形依赖，其中Object的位置决定了所有TextView的位置，所以先要确定它。
其实，箭头反过来更加自然。而B -> A建图，方向是反着的，很别扭。其得到的拓扑序列也是反着的。所以代码里会有一步翻转列表:
Collections.reverse(mDependencySortedChildren);

实现的时候，往mChildDag里mChildDag.addEdge(B,A);即可，他帮你封装了图的细节。看一下源码怎么建图：

// 双重 for 循环，简单粗暴，
// 一个 O(N^2) 的算法，还能优化
private void prepareChildren(final boolean forceRefresh) {
    ...
    // 枚举每个 child
    for (int i = 0,count = getChildCount(); i < count; i++) {
        final View view = getChildAt(i);
        final LayoutParams lp = getResolvedLayoutParams(view);

        mChildDag.addNode(view); // 在图中添加节点

        // 枚举每个 otherChild
        for (int j = 0; j < count; j++) {
            if (j == i) 
                continue;
            } 
            final View other = getChildAt(j);
            final LayoutParams otherLp = getResolvedLayoutParams(other);
            if (otherLp.dependsOn(this,other,view)) { // other dependsOn view
                if (!mChildDag.contains(other)) 
                    mChildDag.addNode(other);

                mChildDag.addEdge(view,other); // 添加边 view -> other
            }
        }
    }

    // getSortedList() 很关键，这里准备好 mDependencySortedChildren，
    // 之后的 onMeasure(),onLayout() 都直接遍历它即可。
    mDependencySortedChildren.addAll(mChildDag.getSortedList());
    Collections.reverse(mDependencySortedChildren); // 之前建图建反了，这里拓扑序要反一下。
}

拓扑排序

前面其实没细讲，为啥要有排序这一步？试想一下，如果不排序，直接onLayout()。此时，若A dependsOn B且先碰到了A，得先知道B的位置啊，然而B还没onLayout()呢。怎么办呢？递归地搞，先搞出B的位置，写一个深度优先搜索？最开始我是这么想的，想想好复杂。直到看了源码才顿悟，这不就是拓扑排序么，实在是被惊艳到了。

拓扑排序是有向无环图的一种特定排序方式，结果并不唯一，只要保证结果序列中，任意两节点始终满足偏序关系。简单来讲，就是排完序以后，你再onLayout()，若A dependsOn B且碰到了A时，B肯定排在A前面已经被onLayout()过了。恼人的问题解决！！！

此时，再回过头看一下代码：

// 之前的 mChildDag.getSortedList()
// 帮你实现了"拓扑排序"
final class DirectedAcyclicGraph<T> {
    /** * Returns a topologically sorted list of the nodes in this graph. This uses the DFS algorithm * as described by Cormen et al. (2001). */
    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;
    }
}

之前的分析是基于24.2.0的，再看一下老版本23.2.1的做法：
甚至没有建图，很奇葩的用选择排序实现拓扑排序，效率不是一般的低，怪不得在24.2.0被优化掉了。不过思路是一致的，我们对比着看一下：

private void prepareChildren() {
    ... // 前面一样，添加节点到 mDependencySortedChildren
    // 吐糟：为何不用快速排序
    selectionSort(mDependencySortedChildren,mLayoutDependencyComparator); // 选择排序
}

// 重点看这个比较器，描述了两个节点之间的 "偏序关系"，
// 也就是描述了 "谁该排在前面" 先 "onLayout()".
final Comparator<View> mLayoutDependencyComparator = new Comparator<View>() {
    @Override
    public int compare(View lhs,View rhs) {
        if (lhs == rhs) {
            return 0;
        } else if (((LayoutParams) lhs.getLayoutParams()).dependsOn(
                CoordinatorLayout.this,lhs,rhs)) { // r 为 dependency,得排在前面，需要交换一下 
            return 1;
        } else if (((LayoutParams) rhs.getLayoutParams()).dependsOn(
                CoordinatorLayout.this,rhs,lhs)) { // l 为 dependency,已经排在前面，不需要交换
            return -1;
        } else {
            return 0;
        }
    }
};

总结

以上便是CoordinatorLayout的依赖机制，基于有向无环图。不过，老司机终究是老司机，建模能力太厉害。虽然是基础数据结构，吾等一下子还想不到呢。