RelativeLayoutでのトポロジーソートの適用
7140 ワード
背景
最近、プロジェクトでRelativeLayoutを使用している間に、RelativeLayout内部の子供Viewノードに2回measureメッセージが表示され、プロジェクト内のカスタムコントロールのサイズが予想と一致しないことがわかりました.問題が発生した理由を知る必要があり、合理的な解決策を与える必要があるという原則に基づいて、ソースコードを読み分析した上で、RelativeLayoutに対する個人の理解を出力し、ここで記録と共有を行う.
何だ? RelativeLayout Android SDK API 1に追加されたクラスで、インタフェース内の複数のコントロール間の相対レイアウトの問題を解決するために使用され、現在の子供と他の子供、または親ノードとの相対位置を記述することによって決定される現在の子供レイアウト情報 を記述することができる.クラスの継承構造では、ViewGroupのサブクラス です.実行時は、子供 を含むことができるビューコントロールツリーの非リーフノードです.
トポロジソート は、無ループ図のトポロジーシーケンスを求める際に用いるソート方法 である.この方法の入力は有向無ループ図であり、出力はトポロジーシーケンス である.
どうしてアプリケーション開発者がAPPを開発する際にインタフェース内の複数のコントロール間の相対的な位置を実現する必要がある多くのアプリケーション開発者のニーズを解決するために、SDK開発者たちが設計し実現したクラス/ライブラリ/モジュール. 考えてみてください.もし私にモジュールを設計して実現させて、これらの相対的な位置関係を持つコントロールのレイアウト問題を解決させたら、私はどうしますか.これは現在私が一人で問題を解決する能力をよく試すことができると思う考え方 です.
ないぶげんり
RelativeLayoutのソースコードを読むと,複数の子供ノード間の相対位置の問題を解決するために,データ構造中の図のトポロジーソートを適用して,子供ノード測定の前後順序を決定することが分かった.依存関係のあるタスクの実行順序をどのように計算するかを見てみましょう.もちろんこれは参考解法にすぎず、他の解法もあるに違いない.データ構造(関連情報の記録) ノードandroid.widget.RelativeLayout.DependencyGraph.ノード依存関係図のノードで、ViewとViewの依存ノードと依存ノードがカプセル化されています.簡単に言えば、図中のノードがあり、そのノードは自分の入度と出度情報を知っている.入度0のノードをルートノード と呼ぶ.弧(辺)android.widget.RelativeLayout.LayoutParams#mRules各RelativeLayoutの子供ノードのレイアウトパラメータには、現在のノードが他のノードに依存しているという情報が記録されています.子供ノードはid識別子を採用し、各ノードが記述できる相対位置パラメータは22個(android.widget.RelativeLayout#VERB_COUNT)である.intタイプの配列を用いて依存情報を記録する、配列の下付きは相対位置パラメータであり、配列内の値は依存ノードのID である.図android.widget.RelativeLayout.DependencyGraphは依存関係の図情報を記録する.RelativeLayoutインスタンスが持つ子供ノード情報を記録します.
アルゴリズム(所与の入力/出力、計算プロセスを実現) ノードandroidを追加する.widget.RelativeLayout.DependencyGraph#add
エッジandroidを追加します.widget.RelativeLayout.LayoutParams#LayoutParams(android.context,android.util.AttributeSet)LayoutParamsオブジェクトの作成時に、AttributeSetからエッジ情報 を解析するトポロジーシーケンスandroidを計算する.widget.RelativeLayout.DependencyGraph#getSortedViews
android.widget.RelativeLayout.DependencyGraph#findRoots
練習問題 RelativeLayoutのコードとリソースを自分のプロジェクトにコピーし、コピーしたRelativeLayoutを適用して基本的に を使用します.コピーされたRelativeLayoutコードを変更し、RelativeLayout追加ノード、追加エッジ、トポロジーソートのワークフローログ情報 を印刷する.は、図の隣接行列、隣接チェーンテーブルの基本動作 を実現する.百科事典のトポロジーソートのアルゴリズムによると、簡単なトポロジーソート を手動で実現する.同じ図は、入力エッジ情報に基づいてトポロジーシーケンス を複数回出力ことをサポートする. RelativeLayoutの関連トポロジーソートAPIの実装を削除し、自分で手動で実装し、テスト例が を通過できることを確保する.出力トポロジーソートRelativeLayoutに適用される文書 まとめ
これまでRelativeLayoutはすべての子供ノードの依存関係を計算してきたが,次にトポロジーシーケンスの順序に従って子供ノードにmeasureメッセージを送信し,RelativeLayoutのサイズ情報を計算することができる.
リファレンス
RelativeLayoutドキュメントRelativeLayoutコードトポロジーソート
最近、プロジェクトでRelativeLayoutを使用している間に、RelativeLayout内部の子供Viewノードに2回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 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 dependents = node.dependents;
final int count = dependents.size();
//
for (int i = 0; i < count; i++) {
final Node dependent = dependents.keyAt(i);
//
final SparseArray 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 findRoots(int[] rulesFilter) {
final SparseArray keyNodes = mKeyNodes;
final ArrayList 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 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コードトポロジーソート