1/* 2 * Copyright 2018 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package androidx.coordinatorlayout.widget; 18 19import static androidx.annotation.RestrictTo.Scope.LIBRARY; 20 21import androidx.annotation.NonNull; 22import androidx.annotation.Nullable; 23import androidx.annotation.RestrictTo; 24import androidx.collection.SimpleArrayMap; 25import androidx.core.util.Pools; 26 27import java.util.ArrayList; 28import java.util.HashSet; 29import java.util.List; 30 31/** 32 * A class which represents a simple directed acyclic graph. 33 * 34 * @param <T> Class for the data objects of this graph. 35 * 36 * @hide 37 */ 38@RestrictTo(LIBRARY) 39public final class DirectedAcyclicGraph<T> { 40 private final Pools.Pool<ArrayList<T>> mListPool = new Pools.SimplePool<>(10); 41 private final SimpleArrayMap<T, ArrayList<T>> mGraph = new SimpleArrayMap<>(); 42 43 private final ArrayList<T> mSortResult = new ArrayList<>(); 44 private final HashSet<T> mSortTmpMarked = new HashSet<>(); 45 46 /** 47 * Add a node to the graph. 48 * 49 * <p>If the node already exists in the graph then this method is a no-op.</p> 50 * 51 * @param node the node to add 52 */ 53 public void addNode(@NonNull T node) { 54 if (!mGraph.containsKey(node)) { 55 mGraph.put(node, null); 56 } 57 } 58 59 /** 60 * Returns true if the node is already present in the graph, false otherwise. 61 */ 62 public boolean contains(@NonNull T node) { 63 return mGraph.containsKey(node); 64 } 65 66 /** 67 * Add an edge to the graph. 68 * 69 * <p>Both the given nodes should already have been added to the graph through 70 * {@link #addNode(Object)}.</p> 71 * 72 * @param node the parent node 73 * @param incomingEdge the node which has is an incoming edge to {@code node} 74 */ 75 public void addEdge(@NonNull T node, @NonNull T incomingEdge) { 76 if (!mGraph.containsKey(node) || !mGraph.containsKey(incomingEdge)) { 77 throw new IllegalArgumentException("All nodes must be present in the graph before" 78 + " being added as an edge"); 79 } 80 81 ArrayList<T> edges = mGraph.get(node); 82 if (edges == null) { 83 // If edges is null, we should try and get one from the pool and add it to the graph 84 edges = getEmptyList(); 85 mGraph.put(node, edges); 86 } 87 // Finally add the edge to the list 88 edges.add(incomingEdge); 89 } 90 91 /** 92 * Get any incoming edges from the given node. 93 * 94 * @return a list containing any incoming edges, or null if there are none. 95 */ 96 @Nullable 97 public List getIncomingEdges(@NonNull T node) { 98 return mGraph.get(node); 99 } 100 101 /** 102 * Get any outgoing edges for the given node (i.e. nodes which have an incoming edge 103 * from the given node). 104 * 105 * @return a list containing any outgoing edges, or null if there are none. 106 */ 107 @Nullable 108 public List<T> getOutgoingEdges(@NonNull T node) { 109 ArrayList<T> result = null; 110 for (int i = 0, size = mGraph.size(); i < size; i++) { 111 ArrayList<T> edges = mGraph.valueAt(i); 112 if (edges != null && edges.contains(node)) { 113 if (result == null) { 114 result = new ArrayList<>(); 115 } 116 result.add(mGraph.keyAt(i)); 117 } 118 } 119 return result; 120 } 121 122 /** 123 * Checks whether we have any outgoing edges for the given node (i.e. nodes which have 124 * an incoming edge from the given node). 125 * 126 * @return <code>true</code> if the node has any outgoing edges, <code>false</code> 127 * otherwise. 128 */ 129 public boolean hasOutgoingEdges(@NonNull T node) { 130 for (int i = 0, size = mGraph.size(); i < size; i++) { 131 ArrayList<T> edges = mGraph.valueAt(i); 132 if (edges != null && edges.contains(node)) { 133 return true; 134 } 135 } 136 return false; 137 } 138 139 /** 140 * Clears the internal graph, and releases resources to pools. 141 */ 142 public void clear() { 143 for (int i = 0, size = mGraph.size(); i < size; i++) { 144 ArrayList<T> edges = mGraph.valueAt(i); 145 if (edges != null) { 146 poolList(edges); 147 } 148 } 149 mGraph.clear(); 150 } 151 152 /** 153 * Returns a topologically sorted list of the nodes in this graph. This uses the DFS algorithm 154 * as described by Cormen et al. (2001). If this graph contains cyclic dependencies then this 155 * method will throw a {@link RuntimeException}. 156 * 157 * <p>The resulting list will be ordered such that index 0 will contain the node at the bottom 158 * of the graph. The node at the end of the list will have no dependencies on other nodes.</p> 159 */ 160 @NonNull 161 public ArrayList<T> getSortedList() { 162 mSortResult.clear(); 163 mSortTmpMarked.clear(); 164 165 // Start a DFS from each node in the graph 166 for (int i = 0, size = mGraph.size(); i < size; i++) { 167 dfs(mGraph.keyAt(i), mSortResult, mSortTmpMarked); 168 } 169 170 return mSortResult; 171 } 172 173 private void dfs(final T node, final ArrayList<T> result, final HashSet<T> tmpMarked) { 174 if (result.contains(node)) { 175 // We've already seen and added the node to the result list, skip... 176 return; 177 } 178 if (tmpMarked.contains(node)) { 179 throw new RuntimeException("This graph contains cyclic dependencies"); 180 } 181 // Temporarily mark the node 182 tmpMarked.add(node); 183 // Recursively dfs all of the node's edges 184 final ArrayList<T> edges = mGraph.get(node); 185 if (edges != null) { 186 for (int i = 0, size = edges.size(); i < size; i++) { 187 dfs(edges.get(i), result, tmpMarked); 188 } 189 } 190 // Unmark the node from the temporary list 191 tmpMarked.remove(node); 192 // Finally add it to the result list 193 result.add(node); 194 } 195 196 /** 197 * Returns the size of the graph 198 */ 199 int size() { 200 return mGraph.size(); 201 } 202 203 @NonNull 204 private ArrayList<T> getEmptyList() { 205 ArrayList<T> list = mListPool.acquire(); 206 if (list == null) { 207 list = new ArrayList<>(); 208 } 209 return list; 210 } 211 212 private void poolList(@NonNull ArrayList<T> list) { 213 list.clear(); 214 mListPool.release(list); 215 } 216} 217