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