拓扑排序在 RelativeLayout 中的应用

2018-02-19  本文已影响0人  1999c1b720cd

背景

最近在项目中使用 RelativeLayout 的过程当中发现 RelativeLayout 内部的孩子 View 节点会收到两次 measure 消息，导致项目中某个自定义控件的尺寸和预期的不一致。本着出了问题需要知道为什么，并且需要给出合理的解决方案这样的原则，因此在阅读分析完源码的基础上输出个人对 RelativeLayout 的一些理解，在此进行记录和分享。

是什么

为什么

内部原理

在阅读 RelativeLayout 的源码时，发现其为了解决多个孩子节点之间相对位置的问题，应用了数据结构中图的拓扑排序来确定孩子节点测量的先后顺序。我们一起来看下如何计算出一些具有依赖关系的任务的执行顺序。当然这只是一种参考解法，肯定还有其他解法。

void add(View view) {
    final int id = view.getId();
    // 把 View 包装到 Node 实例内部
    final Node node = Node.acquire(view);

    if (id != View.NO_ID) {
        // 记录 ID 到 Node 的映射关系，为了接下来的查询效率
        mKeyNodes.put(id, node);
    }

    // 添加一个图节点
    mNodes.add(node);
}

final int N = a.getIndexCount();
// 遍历属性集合
for (int i = 0; i < N; i++) {
    // 读取属性索引号
    int attr = a.getIndex(i);
    switch (attr) {
        case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignWithParentIfMissing:
            alignWithParent = a.getBoolean(attr, false);
            break;
        case com.android.internal.R.styleable.RelativeLayout_Layout_layout_toLeftOf:
            // 读取被依赖 View 的 ID
            // 当前节点 LEFT_OF 于 attr 对应的 res id
            rules[LEFT_OF] = a.getResourceId(attr, 0);
            break;
        // 省略其它依赖规则解析
        ...

// 输出指定边规则后的拓扑序列
void getSortedViews(View[] sorted, int... rules) {
    // 找到所有根节点放进双端队列存放起来
    final ArrayDeque<Node> roots = findRoots(rules);
    int index = 0;

    Node node;
    // 遍历根节点队列
    while ((node = roots.pollLast()) != null) {
        //解封得到 View 对象
        final View view = node.view;
        final int key = view.getId();

        // 输出到拓扑序列数组中
        sorted[index++] = view;

        // 找到当前根节点的出度信息
        final ArrayMap<Node, DependencyGraph> dependents = node.dependents;
        final int count = dependents.size();
        // 遍历出度节点
        for (int i = 0; i < count; i++) {
            final Node dependent = dependents.keyAt(i);
            // 入度信息
            final SparseArray<Node> dependencies = dependent.dependencies;
            // 删除入度
            dependencies.remove(key);
            // 入度为 0 
            if (dependencies.size() == 0) {
                // 成为新的根节点，加入到双端队列中
                roots.add(dependent);
            }
        }
    }

    // 如果拓扑序列中节点个数和图中所有节点的个数不等，则存在环
    if (index < sorted.length) {
        throw new IllegalStateException("Circular dependencies cannot exist"
                + " in RelativeLayout");
    }
}

android.widget.RelativeLayout.DependencyGraph#findRoots

// 根据参数中选择的依赖规则找到所有根节点
private ArrayDeque<Node> findRoots(int[] rulesFilter) {
    final SparseArray<Node> keyNodes = mKeyNodes;
    final ArrayList<Node> nodes = mNodes;
    final int count = nodes.size();

    // Find roots can be invoked several times, so make sure to clear
    // all dependents and dependencies before running the algorithm
    for (int i = 0; i < count; i++) {
        final Node node = nodes.get(i);
        node.dependents.clear();
        node.dependencies.clear();
    }

    // Builds up the dependents and dependencies for each node of the graph
    // 遍历图中所有节点，构建节点的入度和出度信息
    for (int i = 0; i < count; i++) {
        // 读取当前节点
        final Node node = nodes.get(i);

        final LayoutParams layoutParams = (LayoutParams) node.view.getLayoutParams();
        // 从 LayoutParams 中读取依赖信息
        final int[] rules = layoutParams.mRules;
        final int rulesCount = rulesFilter.length;

        // Look only the the rules passed in parameter, this way we build only the
        // dependencies for a specific set of rules
        // 根据参数中选取的部分规则构建依赖信息
        for (int j = 0; j < rulesCount; j++) {
            // 拿到被依赖对象的 ID
            final int rule = rules[rulesFilter[j]];
            if (rule > 0) {
                // The node this node depends on
                final Node dependency = keyNodes.get(rule);
                // Skip unknowns and self dependencies
                if (dependency == null || dependency == node) {
                    continue;
                }
                // Add the current node as a dependent
                // 被依赖节点记录入度信息
                dependency.dependents.put(node, this);
                // Add a dependency to the current node
                // 当前节点记录出度信息
                node.dependencies.put(rule, dependency);
            }
        }
    }

    final ArrayDeque<Node> roots = mRoots;
    // 清理之前的计算结果
    roots.clear();

    // Finds all the roots in the graph: all nodes with no dependencies
    // 遍历所有节点
    for (int i = 0; i < count; i++) {
        final Node node = nodes.get(i);
        if (node.dependencies.size() == 0) 
            // 入度为 0 则为根节点
            roots.addLast(node);
    }

    // 输出根节点队列
    return roots;
}

练习题

总结

到目前为止，RelativeLayout 已经计算出所有孩子节点的依赖关系，接下来可以根据拓扑序列中的顺序来向孩子节点发送 measure 消息，从而计算出 RelativeLayout 的尺寸信息

参考

RelativeLayout 文档
RelativeLayout 代码
拓扑排序

上一篇 下一篇

猜你喜欢

热点阅读