2 ms·
There isn't really anything to implement. Basic "entities" get integer ids starting from 0. You just point into the flat array. Child lists or other structures
by jstimpfle 8y ago
There isn't really anything to implement. Basic "entities" get integer ids starting from 0. You just point into the flat array.
Child lists or other structures that don't have natural ids can for example get "indexed" with first- and last-indices like this:
struct Parent {
some data;
Child childFirst;
Child childLast;
};
struct Child {
some childdata;
Parent parent;
};
struct Parent *parent;
struct Child *child;
int parentCnt;
int childCnt;
These indices are trivial to setup:
SORT(child, childCnt, compare_child_by_parent);
for (int i = 0; i < parentCnt; i++) {
parent[i].childFirst = childCnt;
parent[i].childLast = 0;
}
for (int i = 0; i < childCnt; i++) {
if (parent[child[i].parent].childFirst > i)
parent[child[i].parent].childFirst = i;
if (parent[child[i].parent].childLast < i + 1)
parent[child[i].parent].childLast = i + 1;
}
The important thing to see is that most operations are inside whole-table loops. Not in the O(n) sense - each step does something meaningful. Nested loops or complicated data manipulations are drastically decreased compared to OOP approaches.