java - 表示包安装和系统依赖关系的最佳数据结构

Question

我正在尝试根据面试过程创建一个程序(我选择 Java，但可以是 C/C++ 或 GoLang)来表示/模拟 Linux/Unix 环境中存在的包安装和系统依赖项。基本上，我会执行以下要求:

1) 维护已安装包及其依赖项的记录。
2) 支持响应命令显式安装包(除非已经安装)。
3) 如果需要安装另一个包，支持隐式安装一个包。
4) 支持显式删除一个包以响应命令(如果不需要支持其他包)。
5) 如果不再需要支持另一个组件，则支持隐式删除包。

在安装包之前，自动安装它需要的所有包。在删除包之前，请确认没有其他包需要它。在删除包之前，必须手动删除依赖包。

我想要最好的数据结构(以及我可以检查的链接)的提示，我可以用它来做到这一点。我尝试使用队列列表作为存储依赖项的方式，并使用队列来存储已安装的包，但我不确定这是否是最好的方法，例如:

...
ArrayList<Queue<String>> dependencies = new ArrayList<>(capacity);
Queue<String> pkgInstalled = new LinkedList<String>();
...

该过程将捕获来自用户的条目数据，直到 END 命令。命令语法是:

DEPEND item1 item2 item(n):包item1依赖于包item2(和item3或任何；

INSTALL item1:安装 item1 和 item1 所需的任何其他包。

REMOVE item1:删除 item1，如果可能，删除 item1 所需的包。

LIST:列出所有当前安装的包的名称。

END:标记输入的结束，单独在一行中使用时。

1) 在每个回显的 INSTALL 或 REMOVE 行后面加上响应所采取的操作，确保以正确的顺序给出操作。
2) LIST命令，显示当前安装的组件名称。
3) 对于 DEPEND 和 END 命令，除了回显外，没有输出。
4) 对于DEPEND命令，每一项只有一个依赖列表。

Answer 1

我不知道本练习中 Queue 的值(或 LinkedList)，因为您将希望能够随机访问包的依赖关系。

我会建议

Map<String, Set<String>> dependsOn = new HashMap<>();
Map<String, Set<String>> requiredBy = new HashMap<>();

这样，当您删除一个包时，您可以找到它已拉入的所有包 (dependsOn.get(packageToDelete)) 并从每个包中删除 packageToDelete他们在 requiredBy 中的条目；如果这使得 requiredBy 设置为空，那么也可以删除该包。

我还建议您在添加新的根包时使用 Set 来添加要添加的依赖包。以什么顺序处理它们并不重要，快速和避免重复更有用。

最初我假设使用唯一的完全限定包名称作为键会更简单 - 更容易编码和调试。这需要一种根据名称查找包的方法，但该方法应该已经存在。但是，如果您愿意，可以为您的 Package 类实现 equals() 和 hashcode() 并将它们直接用作 Map 键。

为了阐明这是如何工作的，这里有一个例子:

public Set<String> addDependencies(Item pkg, Item... dependencies) {
    Set<String> pkgDependsOn = dependsOn.get(pkg.getFullyQualifiedName());
    if (pkgDependsOn == null) {
        pkgDependsOn = new HashSet<>();
        dependsOn.put(pkg.getFullyQualifiedName(), pkgDependsOn);
    }
    pkgDependsOn.addAll(Stream.of(dependencies).map(dep -> dep.getFullyQualifiedName()).collect(Collectors.toSet()));
    return pkgDependsOn;
}

(我可能使用了 Map.merge() 来代替，但是写出来之后我觉得它太复杂了，容易混淆。)

返回生成的 Set 依赖项可能有点矫枉过正，但我​​可以想象在某些情况下它可能会有用。

如果您确实选择使用包本身作为键，它看起来像这样:

public Set<Item> addDependencies(Item pkg, Item... dependencies) {
    Set<Item> pkgDependsOn = dependsOn.get(pkg);
    if (pkgDependsOn == null) {
        pkgDependsOn = new HashSet<>();
        dependsOn.put(pkg, pkgDependsOn);
    }
    pkgDependsOn.addAll(Arrays.asList(dependencies));
    return pkgDependsOn;
}

我也没有做错误检查(比如如果你让一个包依赖于它自己)、空检查等。