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