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