表示包安装和系统依赖关系的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>(); ...

Answer 1

我不知道在这个练习中Queue（或LinkedList）的值，因为您希望能够随机访问包的依赖项

我建议

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

这样，当您删除一个包时，您可以找到它拉入的所有包（dependsOn.get(packageToDelete)），并从requiredBy中的每个条目中删除packageToDelete；如果这使得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;
}

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