1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
/*
* Copyright (C) 2019 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.android.builder.dexing
import java.io.Serializable
/**
* Directed graph to model the dependencies among objects of interest. An edge from A to B means
* that object A depends on object B (A is a dependent of B, and B is a dependency of A).
*/
class MutableDependencyGraph<T> : DependencyGraphUpdater<T>, Serializable {
/** Map from a node B to all the nodes A that have an edge from A to B. */
private val dependentsMap: MutableMap<T, MutableSet<T>> = mutableMapOf()
/** Returns all the nodes. */
fun getNodes(): Set<T> {
return dependentsMap.keys.toSet()
}
/**
* Returns the directly dependent nodes of a given node. The returned set does not include the
* given node.
*
* If the given node does not exist, the returned set is empty.
*/
fun getDirectDependents(node: T): Set<T> {
return dependentsMap[node]?.toSet() ?: emptySet()
}
override fun addEdge(dependent: T, dependency: T) {
check(dependent != dependency) { "Can't add an edge from a node to itself: $dependent" }
dependentsMap.computeIfAbsent(dependency) { mutableSetOf() }.add(dependent)
dependentsMap.computeIfAbsent(dependent) { mutableSetOf() }
}
/**
* Removes a node and all the edges from it and to it.
*
* If the given node does not exist, it will be ignored.
*/
fun removeNode(nodeToRemove: T) {
dependentsMap.remove(nodeToRemove)
dependentsMap.values.forEach { it.remove(nodeToRemove) }
}
/**
* Returns all the directly and transitively dependent nodes of a given set of nodes. The
* returned set does not include the nodes in the given set.
*
* Any nodes in the given set that do not exist are ignored.
*/
fun getAllDependents(nodes: Set<T>): Set<T> {
val visitedSet: MutableSet<T> = mutableSetOf()
val toVisitSet: MutableSet<T> = nodes.toMutableSet()
while (toVisitSet.isNotEmpty()) {
val toVisitNextSet = mutableSetOf<T>()
for (toVisitNode in toVisitSet) {
dependentsMap[toVisitNode]?.let { toVisitNextSet.addAll(it) }
}
visitedSet.addAll(toVisitSet)
toVisitSet.clear()
toVisitSet.addAll(toVisitNextSet - visitedSet)
}
return visitedSet - nodes
}
companion object {
private const val serialVersionUID = 1L
}
}
/** Interface for updating a dependency graph. */
interface DependencyGraphUpdater<T> {
/**
* Adds an edge from a dependent to a dependency.
*
* If any of the given nodes does not yet exist, it will be added.
*/
fun addEdge(dependent: T, dependency: T)
}
|
