Лучшая структура данных, представляющая установку пакета и системные зависимости - PullRequest
Новая
       37

Лучшая структура данных, представляющая установку пакета и системные зависимости

0 голосов
/ 01 июня 2018

Я пытаюсь создать программу (я выбираю 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.Синтаксис команды:

ЗАВИСИМО от item1 item2 item (n): Package item1 зависит от пакета item2 (и item3 или любого другого;

INSTALL item1: устанавливает item1 и любые другие пакеты, необходимые для item1.

REMOVE item1: удаляет item1 и, если возможно, пакеты, необходимые для item1.

LIST: список имен всех установленных на данный момент пакетов.

END: отмечает конецinput, если он используется в отдельной строке.

1) Следуйте за каждой повторяющейся строкой INSTALL или REMOVE с действиями, предпринятыми в ответе, убедившись, что действия заданы в правильном порядке.2) Для команды LIST отобразите имена установленных компонентов.3) Для команд DEPEND и END вывод, кроме эха, не производится.4) Для команды DEPEND будет только один список зависимостей на элемент.

1 Ответ

0 голосов
/ 01 июня 2018

Я не знаю значения Queue в этом упражнении (или LinkedList), так как вы захотите иметь возможность произвольного доступа к зависимостям пакета.

Я бы предложил 

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

Таким образом, когда вы удаляете пакет, вы можете найти все пакеты, в которые он был извлечен (dependsOn.get(packageToDelete)), и удалить packageToDelete из каждой их записи в requiredBy;если при этом набор requiredBy остается пустым, этот пакет также можно удалить.

Я бы также предложил использовать Set для зависимых пакетов, которые будут добавлены при добавлении нового корневого пакета.На самом деле не имеет значения, в каком порядке вы их обрабатываете, и более полезно быть быстрым и избегать дублирования.

Изначально я предполагал, что будет проще - проще кодировать и отлаживать - использовать уникальные полностьюквалифицированные имена пакетов в качестве ключей.Для этого требуется способ поиска пакета по его имени, но он должен уже существовать.Однако, если вы предпочитаете, вы можете реализовать equals() и hashcode() для вашего Package класса и использовать их непосредственно в качестве 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;
}

Iя также не делаю проверку ошибок (например, если вы делаете пакет зависимым от себя), нулевые проверки и т. д.

...