Аннотация Описание:
У меня есть набор строк, назовите его «активным набором», а набор наборов строк — назовите его «возможный набор». Когда к активному набору добавляется новая строка, наборы из возможного набора могут внезапно стать подмножествами активного набора, потому что в активном наборе не хватает только этой строки, чтобы быть надмножеством одного из возможных. Мне нужен алгоритм, чтобы эффективно находить их, когда я добавляю новую строку в активный набор. Бонусные баллы, если та же самая структура данных позволяет мне эффективно определять, какие из этих возможных наборов недействительны (больше не являются подмножеством), когда строка удаляется из активного набора.
(Причина, по которой я сформулировал проблему, описанную ниже, в терминах наборов и подмножеств строк в аннотации выше, заключается в том, что язык, на котором я пишу это (Io), является динамически типизированным. Объекты имеют поле «тип», но это строка с именем типа объекта в ней.)
Фон:
В моем игровом движке у меня есть GameObjects, к которым можно добавить несколько типов объектов Representation. Например, если GameObject имеет физическое присутствие, к нему может быть добавлено PhysicsRepresentation (или нет, если это не сплошной объект). К нему могут быть добавлены различные типы GraphicsRepresentations, такие как сетка или эффект частиц (и вы можете иметь более одного, если у вас есть несколько визуальных эффектов, прикрепленных к одному и тому же игровому объекту).
Смысл этого в том, чтобы разделить подсистемы, но вы не можете полностью разделить все: например, когда GameObject имеет как PhysicsRepresentation, так и GraphicsRepresentation, что-то должно создать 3-й объект, который соединяет положение GraphicsRepresentation с местоположением объекта. Представление физики. Чтобы служить этой цели, сохраняя при этом все компоненты отдельными, у меня есть объекты Interaction. Объект Interaction инкапсулирует сквозные знания о том, как должны взаимодействовать два компонента системы.
Но чтобы защитить GameObject от необходимости слишком много знать о представлениях и взаимодействиях, GameObject просто предоставляет общий реестр, в котором объекты-прототипы взаимодействия могут регистрироваться для вызова, когда в GameObject присутствует определенная комбинация представлений. Когда к GameObject добавляется новое Представление, GameObject должен просмотреть свой реестр и активировать только те объекты Interaction, которые вновь активируются благодаря наличию нового Представления, а также существующие Представления.
Я просто застрял на том, какую структуру данных следует использовать для этого реестра и как его искать.
Исправления:
Наборы строк не обязательно сортируются, но я могу сохранить их отсортированными.
Хотя Взаимодействие чаще всего происходит между двумя Представлениями, я не хочу ограничивать его этим; У меня должна быть возможность иметь взаимодействия, которые запускаются с 3 или более различными представлениями, или даже взаимодействия, которые запускаются только на основе 1 представления.
Я хочу оптимизировать это для максимально быстрого добавления/удаления представлений.
У меня будет много активных наборов (у каждого игрового объекта есть активный набор), но у меня есть только один возможный набор (набор всех зарегистрированных типов взаимодействия). Поэтому меня не волнует, сколько времени потребуется для построения структуры данных, представляющей возможный набор, потому что это нужно сделать только один раз, при условии, что алгоритм сравнения различных активных наборов не разрушает структуру данных возможного набора.
