I'm trying to create a program (I choose Java but can be C/C++ or GoLang) based on an interview process to represent/simulate a Package Installation and System Dependencies like existent in Linux/Unix environments. Basically, I'll do following requirements:
1) Maintain a record of installed packages and their dependencies.
2) Support explicitly installing a package in response to a command (unless it is already installed).
3) Support implicitly installing a package if it is needed to install another package.
4) Support explicitly removing a package in response to a command (if it is not needed to support other packages).
5) Support implicitly removing a package if it is no longer needed to support another component.
Before installing a package, automatically install all the packages it requires. Before removing a package, confirm that no other packages require it. Dependent packages must be removed manually before the package can be removed.
I'd like tips of the best data structure (and the link that I can check) that I can use to do that. I tried using a List of queues as a way to store the dependencies and a Queue to store the packages installed but I'm not sure if this is the best approach like:
...
ArrayList<Queue<String>> dependencies = new ArrayList<>(capacity);
Queue<String> pkgInstalled = new LinkedList<String>();
...The process will capture the entry data from the user until an END command. The command syntaxes are:
DEPEND item1 item2 item(n): Package item1 depends on package item2 (and item3 or any;
INSTALL item1: Installs item1 and any other packages required by item1.
REMOVE item1: Removes item1 and, if possible, packages required by item1.
LIST: Lists the names of all currently installed packages.
END: Marks the end of input, when used in a line by itself.
1) Follow each echoed INSTALL or REMOVE line with the actions taken in response, making certain that the actions are given in the proper order.
2) For the LIST command, display the names of the components currently installed.
3) For the DEPEND and END commands, no output, except the echo, is produced.
4) For the DEPEND command, there will only be one dependency list per item.
</div>
I don't know the value of a Queue in this exercise (or a LinkedList) since you're going to want to be able to random-access the dependencies of a package.
I would suggest
Map<String, Set<String>> dependsOn = new HashMap<>();
Map<String, Set<String>> requiredBy = new HashMap<>();
That way, when you delete a package, you can find all of the packages it has pulled in (dependsOn.get(packageToDelete)) and remove packageToDelete from each of their entries in requiredBy; if that leaves the requiredBy set empty, then that package can be removed too.
I would also suggest using a Set for the dependent packages to be added when you're adding a new root package. It doesn't really matter what order you process them in, and it's more useful to be fast and avoid duplicates.
Originally I assumed that it would be simpler - easier to code and debug - to use unique fully-qualified package names as keys. This requires a way to look up a package based on its name, but that should already exist. However, if you prefer, you could implement equals() and hashcode() for your Package class and use them directly as Map keys.
In order to clarify how this might work, here is an example:
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;
}
(I might have used Map.merge() instead, but after writing it out I thought it was complex enough to be confusing.)
Returning the resulting Set of dependencies is probably overkill, but I can imagine some cases where it might be useful.
If you do choose to use the packages themselves as keys, it looks like this:
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;
}
I'm also not doing error-checking (like if you make a package depend on itself), null checks, etc.