DependencyGraph.java revision 80d9301c2e874b29889c41adb0623666cf534fa0
180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye/* 280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * Copyright (C) 2011 The Android Open Source Project 380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * 480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * Licensed under the Eclipse Public License, Version 1.0 (the "License"); 580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * you may not use this file except in compliance with the License. 680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * You may obtain a copy of the License at 780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * 880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * http://www.eclipse.org/org/documents/epl-v10.php 980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * 1080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * Unless required by applicable law or agreed to in writing, software 1180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * distributed under the License is distributed on an "AS IS" BASIS, 1280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * See the License for the specific language governing permissions and 1480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * limitations under the License. 1580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye */ 1680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyepackage com.android.ide.common.layout.relative; 1780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 1880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport static com.android.ide.common.layout.LayoutConstants.ANDROID_URI; 1980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport static com.android.ide.common.layout.LayoutConstants.ATTR_ID; 2080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport static com.android.ide.common.layout.LayoutConstants.ATTR_LAYOUT_PREFIX; 2180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport static com.android.ide.common.layout.LayoutConstants.VALUE_TRUE; 2280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 2380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport com.android.ide.common.api.IDragElement; 2480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport com.android.ide.common.api.INode; 2580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport com.android.ide.common.api.IDragElement.IDragAttribute; 2680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport com.android.ide.common.api.INode.IAttribute; 2780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport com.android.ide.common.layout.BaseLayoutRule; 2880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 2980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport java.util.ArrayList; 3080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport java.util.Collection; 3180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport java.util.HashMap; 3280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport java.util.HashSet; 3380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport java.util.List; 3480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport java.util.Map; 3580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeimport java.util.Set; 3680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 3780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye/** 3880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * Data structure about relative layout relationships which makes it possible to: 3980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * <ul> 4080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * <li> Quickly determine not just the dependencies on other nodes, but which nodes 4180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * depend on this node such that they can be visualized for the selection 4280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * <li> Determine if there are cyclic dependencies, and whether a potential move 4380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * would result in a cycle 4480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * <li> Determine the "depth" of a given node (in terms of how many connections it 4580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * is away from a parent edge) such that we can prioritize connections which 4680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * minimizes the depth 4780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * </ul> 4880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye */ 4980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbyeclass DependencyGraph { 5080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye /** Format to chain include cycles in: a=>b=>c=>d etc */ 5180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye static final String CHAIN_FORMAT = "%1$s=>%2$s"; //$NON-NLS-1$ 5280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 5380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye /** Format to chain constraint dependencies: button 1 above button2 etc */ 5480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye private static final String DEPENDENCY_FORMAT = "%1$s %2$s %3$s"; //$NON-NLS-1$ 5580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 5680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye private final Map<String, ViewData> mIdToView = new HashMap<String, ViewData>(); 5780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye private final Map<INode, ViewData> mNodeToView = new HashMap<INode, ViewData>(); 5880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 5980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye /** Constructs a new {@link DependencyGraph} for the given relative layout */ 6080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye DependencyGraph(INode layout) { 6180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye INode[] nodes = layout.getChildren(); 6280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 6380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // Parent view: 6480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye String parentId = layout.getStringAttr(ANDROID_URI, ATTR_ID); 6580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (parentId != null) { 6680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye parentId = BaseLayoutRule.stripIdPrefix(parentId); 6780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } else { 6880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye parentId = "RelativeLayout"; // For display purposes; we never reference 6980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // the parent id from a constraint, only via parent-relative params 7080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // like centerInParent 7180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 7280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye ViewData parentView = new ViewData(layout, parentId); 7380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye mNodeToView.put(layout, parentView); 7480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (parentId != null) { 7580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye mIdToView.put(parentId, parentView); 7680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 7780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 7880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye for (INode child : nodes) { 7980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye String id = child.getStringAttr(ANDROID_URI, ATTR_ID); 8080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (id != null) { 8180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye id = BaseLayoutRule.stripIdPrefix(id); 8280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 8380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye ViewData view = new ViewData(child, id); 8480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye mNodeToView.put(child, view); 8580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (id != null) { 8680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye mIdToView.put(id, view); 8780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 8880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 8980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 9080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye for (ViewData view : mNodeToView.values()) { 9180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye for (IAttribute attribute : view.node.getLiveAttributes()) { 9280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye String name = attribute.getName(); 9380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye ConstraintType type = ConstraintType.fromAttribute(name); 9480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (type != null) { 9580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye String value = attribute.getValue(); 9680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 9780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (type.targetParent) { 9880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (value.equals(VALUE_TRUE)) { 9980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye Constraint constraint = new Constraint(type, view, parentView); 10080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye view.dependsOn.add(constraint); 10180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye parentView.dependedOnBy.add(constraint); 10280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 10380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } else { 10480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // id-based constraint. 10580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // NOTE: The id could refer to some widget that is NOT a sibling! 10680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye String targetId = BaseLayoutRule.stripIdPrefix(value); 10780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye ViewData target = mIdToView.get(targetId); 10880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (target == view) { 10980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // Self-reference. RelativeLayout ignores these so it's 11080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // not an error like a deeper cycle (where RelativeLayout 11180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // will throw an exception), but we might as well warn 11280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // the user about it. 11380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // TODO: Where do we emit this error? 11480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } else if (target != null) { 11580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye Constraint constraint = new Constraint(type, view, target); 11680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye view.dependsOn.add(constraint); 11780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye target.dependedOnBy.add(constraint); 11880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } else { 11980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // This is valid but we might want to warn... 12080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye //System.out.println("Warning: no view data found for " + targetId); 12180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 12280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 12380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 12480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 12580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 12680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 12780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 12880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public ViewData getView(IDragElement element) { 12980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye IDragAttribute attribute = element.getAttribute(ANDROID_URI, ATTR_ID); 13080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (attribute != null) { 13180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye String id = attribute.getValue(); 13280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye id = BaseLayoutRule.stripIdPrefix(id); 13380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return getView(id); 13480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 13580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 13680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return null; 13780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 13880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 13980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public ViewData getView(String id) { 14080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return mIdToView.get(id); 14180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 14280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 14380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public ViewData getView(INode node) { 14480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return mNodeToView.get(node); 14580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 14680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 14780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye /** 14880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * Returns the set of views that depend on the given node in either the horizontal or 14980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * vertical direction 15080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * 15180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * @param nodes the set of nodes that we want to compute the transitive dependencies 15280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * for 15380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * @param vertical if true, look for vertical dependencies, otherwise look for 15480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * horizontal dependencies 15580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * @return the set of nodes that directly or indirectly depend on the given nodes in 15680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * the given direction 15780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye */ 15880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public Set<INode> dependsOn(Collection<? extends INode> nodes, boolean vertical) { 15980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye List<ViewData> reachable = new ArrayList<ViewData>(); 16080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 16180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // Traverse the graph of constraints and determine all nodes affected by 16280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // this node 16380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye Set<ViewData> visiting = new HashSet<ViewData>(); 16480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye for (INode node : nodes) { 16580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye ViewData view = mNodeToView.get(node); 16680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (view != null) { 16780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye findBackwards(view, visiting, reachable, vertical, view); 16880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 16980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 17080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 17180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye Set<INode> dependents = new HashSet<INode>(reachable.size()); 17280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 17380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye for (ViewData v : reachable) { 17480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye dependents.add(v.node); 17580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 17680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 17780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return dependents; 17880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 17980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 18080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye private void findBackwards(ViewData view, 18180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye Set<ViewData> visiting, List<ViewData> reachable, 18280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye boolean vertical, ViewData start) { 18380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye visiting.add(view); 18480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye reachable.add(view); 18580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 18680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye for (Constraint constraint : view.dependedOnBy) { 18780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (vertical && !constraint.type.verticalEdge) { 18880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye continue; 18980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } else if (!vertical && !constraint.type.horizontalEdge) { 19080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye continue; 19180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 19280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 19380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye assert constraint.to == view; 19480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye ViewData from = constraint.from; 19580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (visiting.contains(from)) { 19680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // Cycle - what do we do to highlight this? 19780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye List<Constraint> path = getPathTo(start.node, view.node, vertical); 19880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (path != null) { 19980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye System.out.println(Constraint.describePath(path, null, null)); 20080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 20180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } else { 20280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye findBackwards(from, visiting, reachable, vertical, start); 20380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 20480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 20580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 20680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye visiting.remove(view); 20780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 20880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 20980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public List<Constraint> getPathTo(INode from, INode to, boolean vertical) { 21080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // Traverse the graph of constraints and determine all nodes affected by 21180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // this node 21280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye Set<ViewData> visiting = new HashSet<ViewData>(); 21380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye List<Constraint> path = new ArrayList<Constraint>(); 21480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye ViewData view = mNodeToView.get(from); 21580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (view != null) { 21680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return findForwards(view, visiting, path, vertical, to); 21780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 21880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 21980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return null; 22080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 22180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 22280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye private List<Constraint> findForwards(ViewData view, Set<ViewData> visiting, 22380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye List<Constraint> path, boolean vertical, INode target) { 22480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye visiting.add(view); 22580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 22680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye for (Constraint constraint : view.dependsOn) { 22780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (vertical && !constraint.type.verticalEdge) { 22880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye continue; 22980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } else if (!vertical && !constraint.type.horizontalEdge) { 23080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye continue; 23180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 23280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 23380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye try { 23480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye path.add(constraint); 23580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 23680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (constraint.to.node == target) { 23780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return new ArrayList<Constraint>(path); 23880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 23980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 24080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye assert constraint.from == view; 24180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye ViewData to = constraint.to; 24280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (visiting.contains(to)) { 24380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // CYCLE! 24480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye continue; 24580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 24680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 24780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye List<Constraint> chain = findForwards(to, visiting, path, vertical, target); 24880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (chain != null) { 24980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return chain; 25080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 25180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } finally { 25280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye path.remove(constraint); 25380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 25480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 25580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 25680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye visiting.remove(view); 25780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 25880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return null; 25980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 26080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 26180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye /** 26280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * Info about a specific widget child of a relative layout and its constraints. This 26380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * is a node in the dependency graph. 26480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye */ 26580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye static class ViewData { 26680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public final INode node; 26780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public final String id; 26880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public final List<Constraint> dependsOn = new ArrayList<Constraint>(4); 26980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public final List<Constraint> dependedOnBy = new ArrayList<Constraint>(8); 27080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 27180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye ViewData(INode node, String id) { 27280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye this.node = node; 27380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye this.id = id; 27480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 27580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 27680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 27780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye /** 27880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * Info about a specific constraint between two widgets in a relative layout. This is 27980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye * an edge in the dependency graph. 28080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye */ 28180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye static class Constraint { 28280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public final ConstraintType type; 28380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public final ViewData from; 28480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye public final ViewData to; 28580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 28680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // TODO: Initialize depth -- should be computed independently for top, left, etc. 28780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // We can use this in GuidelineHandler.MatchComparator to prefer matches that 28880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye // are closer to a parent edge: 28980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye //public int depth; 29080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 29180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye Constraint(ConstraintType type, ViewData from, ViewData to) { 29280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye this.type = type; 29380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye this.from = from; 29480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye this.to = to; 29580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 29680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 29780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye static String describePath(List<Constraint> path, String newName, String newId) { 29880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye String s = ""; 29980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye for (int i = path.size() - 1; i >= 0; i--) { 30080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye Constraint constraint = path.get(i); 30180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye String suffix = (i == path.size() -1) ? constraint.to.id : s; 30280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye s = String.format(DEPENDENCY_FORMAT, constraint.from.id, 30380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye stripLayoutAttributePrefix(constraint.type.name), suffix); 30480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 30580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 30680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (newName != null) { 30780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye s = String.format(DEPENDENCY_FORMAT, s, stripLayoutAttributePrefix(newName), 30880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye BaseLayoutRule.stripIdPrefix(newId)); 30980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 31080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 31180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return s; 31280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 31380d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 31480d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye private static String stripLayoutAttributePrefix(String name) { 31580d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye if (name.startsWith(ATTR_LAYOUT_PREFIX)) { 31680d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return name.substring(ATTR_LAYOUT_PREFIX.length()); 31780d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 31880d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye 31980d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye return name; 32080d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 32180d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye } 32280d9301c2e874b29889c41adb0623666cf534fa0Tor Norbye} 323