An idea for adding groups to an archetype-based ECS

archetype_groups.c

enum JoinKind {
	InnerJoin,
	OuterJoin
};

/** Create group.
 * A group stores a set of entities for a given list of archetypes.
 * Entities within the group will be ordered according to a component
 * pivot list, such that the first component is guaranteed to be  
 * stored in a contiguous array. Subsequent components may or may not 
 * be stored in contiguous arrays, with components towards the end of
 * the list being the least likely to be stored in contiguous arrays.
 *
 * If archetypes contain components that do not occur in the pivot list,
 * the join kind determines what should happen. If the join kind is
 * InnerJoin, the archetype will be discarded. If the archetype is
 * OuterJoin, the additional components will be added to the pivot list
 * in no particular order, and become part of the group.
 *
 * All archetypes that are not discarded will no longer be matched with
 * systems, as systems will match the group directly. A system will,
 * based on its interest expression, construct a sparse set of indices
 * that identify entities with the relevant combinations of components.
 *
 * Archetypes that are discarded as a result of an inner join will not
 * become part of the group, and will still be matched with systems as
 * usual. This allows applications to easily create groups for any archetype
 * that at least or at most has the components in the pivot list.
 *
 * The group will be matched with systems according to the components in
 * the pivot list, including components that have been added as a result
 * of an outer join.
 */
Group create_group(const Component pivot[], const Type archetypes[], JoinKind join)

/* Create a group for all existing archetypes with at most these five components */
create_group([A, B, C, D, E], [*], InnerJoin);

/* 
This is an example of the group that the above operation could yield. On the
horizontal axis, the combinations of letters represent the archetypes. If each
archetype had a single entity, each line would represent an entity.

The vertical axis represents the component arrays (SoA). Different archetypes
can be stored in the same component array, and component arrays start at
different offsets, so that a single index can be used to retrieve all the
components for a single entity (O(1)).

As can be seen, component A is stored in a contiguous array (there are no
interruptions on the vertical axis), but the other components are not. This
is due to constraints in which components can be ordered: it is theoretically
impossible to order this set of archetypes in a way that each component array
is contiguous while also allowing for O(1) component lookups for an entity.

The sorting algorithm will prioritize packing components at the start of the
array at the expense of components towards the end of the array. The further
towards the end a component is, and the more components there are in the group,
the less efficient it becomes for a system to iterate over that component.

Adding more components to the group will degrade it to the point where it is
no better (or worse) than a standard archetype based system.

A
A  D
A  DE
AB DE
AB D
AB
AB  E
ABC E
ABC
ABCD
ABCDE
A CDE
A CD
A C
A C E
A   E
 B DE
 B D
 B
 B  E
 BC E
 BC
 BCD
 BCDE
*/