As a sidenote, this question targets JavaScript but I know some other languages like C#, so solutions providing pseudo code will be fine for me :)
---
I have a client application consuming data from an external API based on a configuration during startup.
Since calculating the necessary data is not easy for me, I tried to fake the implementation and calculate it locally for now.
There are many
WorkItems linked to each other and the configuration only knows about the relations to consider.
---
Some explanations:
Workitem
A workitem has a unique id and a type
e.g.
{
id: 1,
type: "person"
}
so you know that
Workitem 1 is of type person
Linkrole
A linkrole is a composite key of three keys
- The parrent workitem type
- The child workitem type
- The name of the role
e.g.
{
parentWorkItemType: "person",
childWorkItemType: "house",
name: "owns",
}
which represents
Person owns House
Links
The backend knows about the relations, a link between workitems might look like
{
linkRole: {
parentWorkItemType: "person",
childWorkItemType: "house",
name: "owns",
},
parentId: 1,
childId: 2
}
so you know that
Person 1 owns House 2
---
Fake prerequisites:
Fake backend
I created some fake data for my calculations. The file
backend.js represents the backend / database
export const workItems = [{
id: 1,
type: "car"
}, {
id: 2,
type: "car"
}, {
id: 3,
type: "bird"
}, {
id: 4,
type: "bird"
}, {
id: 5,
type: "bird"
}, {
id: 6,
type: "invalid"
}, {
id: 7,
type: "house"
}, {
id: 8,
type: "house"
}, {
id: 9,
type: "house",
}, {
id: 10,
type: "person",
}];
export const workItemLinks = [{
linkRole: {
parentWorkItemType: "car",
childWorkItemType: "bird",
name: "isChildOf",
},
parentId: 1,
childId: 3
}, {
linkRole: {
parentWorkItemType: "car",
childWorkItemType: "bird",
name: "isChildOf",
},
parentId: 1,
childId: 4
}, {
linkRole: {
parentWorkItemType: "bird",
childWorkItemType: "house",
name: "with",
},
parentId: 3,
childId: 7
}, {
linkRole: {
parentWorkItemType: "bird",
childWorkItemType: "house",
name: "with",
},
parentId: 3,
childId: 8
}, {
linkRole: {
parentWorkItemType: "person",
childWorkItemType: "car",
name: "owns",
},
parentId: 10,
childId: 1
}, {
linkRole: {
parentWorkItemType: "car",
childWorkItemType: "car",
name: "references",
},
parentId: 1,
childId: 2
}];
Fake API
I created some methods inside the file
api.js to fake an API asking the backend for data.
Important sidenote: These methods just help me to find the data I need. I can add more "helpers" if needed (In the real world I can ask to add more API endpoints) so everything can be queried. Please feel free to modify the "Fake API".
import { workItems, workItemLinks } from "./backend.js";
export function getWorkItemsByType(workItemType) {
return workItems.filter(workItem => workItem.type === workItemType);
}
export function getWorkItemsByIds(workItemIds) {
return workItems.filter(workItem => workItemIds.some(workItemId => workItemId === workItem.id));
}
export function getWorkItemLinksByLinkRoleAndLeftSideIds(linkRole, leftSideIds, leftSideIsParentSide) {
return workItemLinks.filter(workItemLink => {
if (workItemLink.linkRole.parentWorkItemType === linkRole.parentWorkItemType &&
workItemLink.linkRole.childWorkItemType === linkRole.childWorkItemType &&
workItemLink.linkRole.name === linkRole.name) {
const leftSideIdInLink = leftSideIsParentSide ? workItemLink.parentId : workItemLink.childId;
return leftSideIds.some(leftSideId => leftSideId === leftSideIdInLink);
}
return false;
});
}
Fake configuration
I created definitions inside
configuration.js to start the calculations based on those
export const definitions = [
{
linkRole: {
parentWorkItemType: "car",
childWorkItemType: "bird",
name: "isChildOf",
}
},
{
workItemType: "car",
isRootWorkItem: true
},
{
linkRole: {
parentWorkItemType: "bird",
childWorkItemType: "house",
name: "with",
}
},
{
linkRole: {
parentWorkItemType: "person",
childWorkItemType: "car",
name: "owns",
}
},
{
linkRole: {
parentWorkItemType: "car",
childWorkItemType: "car",
name: "references",
}
},
];
---
Problem to solve:
I am looking for a performant way to fetch every
related link and workitem from the backend based on the chain of relations starting with each root item.
Expected output based on the configuration:
export const workItems = [{
id: 1,
type: "car"
}, {
id: 2,
type: "car"
}, {
id: 3,
type: "bird"
}, {
id: 4,
type: "bird"
}, {
id: 7,
type: "house"
}, {
id: 8,
type: "house"
}, {
id: 10,
type: "person",
}];
What I have tried:
import { inspect } from "util";
import { getWorkItemsByType, getWorkItemsByIds, getWorkItemLinksByLinkRoleAndLeftSideIds } from "./api.js";
import { definitions } from "./configuration.js";
const { workItemType: rootWorkItemType } = definitions.find(definition => definition.isRootWorkItem);
const workItems = getWorkItemsByType(rootWorkItemType);
const initialWorkItemIds = workItems.map(workItem => workItem.id);
const workItemIdsToLoad = [];
const workItemLinks = [];
const definitionsToTraverse = definitions.filter(definition => definition.linkRole !== undefined);
run(initialWorkItemIds, rootWorkItemType, definitionsToTraverse, workItemIdsToLoad, workItemLinks);
const missingWorkItemIdsToLoad = workItemIdsToLoad.filter(workItemIdToLoad => !rootWorkItemIds.some(rootWorkItemId => rootWorkItemId === workItemIdToLoad));
const workItemsToAdd = getWorkItemsByIds(missingWorkItemIdsToLoad);
workItems.push(...workItemsToAdd);
console.log(inspect({
workItems,
workItemLinks
}, false, null, true))
function run(leftSideWorkItemIds, leftSideWorkItemType, definitionsToTraverse, workItemIdsToLoad, workItemLinks) {
for (let definitionIndex = definitionsToTraverse.length - 1; definitionIndex >= 0; definitionIndex--) {
const currentDefinition = definitionsToTraverse[definitionIndex];
const { linkRole } = currentDefinition;
const { parentWorkItemType, childWorkItemType } = linkRole;
const leftSideWorkItemTypeIsParent = parentWorkItemType === leftSideWorkItemType;
const leftSideWorkItemTypeIsChild = childWorkItemType === leftSideWorkItemType;
if (leftSideWorkItemTypeIsParent || leftSideWorkItemTypeIsChild) {
definitionsToTraverse.splice(definitionIndex, 1);
const relatedWorkItemLinks = getWorkItemLinksByLinkRoleAndLeftSideIds(linkRole, leftSideWorkItemIds, leftSideWorkItemTypeIsParent);
const rightSideWorkItemIds = [];
for (let relatedWorkItemLinkIndex = 0; relatedWorkItemLinkIndex < relatedWorkItemLinks.length; relatedWorkItemLinkIndex++) {
const relatedWorkItemLink = relatedWorkItemLinks[relatedWorkItemLinkIndex];
if (!workItemLinks.some(workItemLink =>
workItemLink.linkRole.parentWorkItemType === relatedWorkItemLink.linkRole.parentWorkItemType &&
workItemLink.linkRole.childWorkItemType === relatedWorkItemLink.linkRole.childWorkItemType &&
workItemLink.linkRole.name === relatedWorkItemLink.linkRole.name &&
workItemLink.parentId === relatedWorkItemLink.parentId &&
workItemLink.childId === relatedWorkItemLink.childId)) {
workItemLinks.push(relatedWorkItemLink);
const rightSideWorkItemId = leftSideWorkItemTypeIsParent ? relatedWorkItemLink.childId : relatedWorkItemLink.parentId;
rightSideWorkItemIds.push(rightSideWorkItemId);
if (!workItemIdsToLoad.some(workItemIdToLoad => workItemIdToLoad === rightSideWorkItemId)) {
workItemIdsToLoad.push(rightSideWorkItemId);
}
}
}
const rightSideWorkItemType = leftSideWorkItemTypeIsParent ? childWorkItemType : parentWorkItemType;
run(rightSideWorkItemIds, rightSideWorkItemType, definitionsToTraverse, workItemIdsToLoad, workItemLinks);
}
}
}
The problem is that my approach crashes because the backwards loop even runs if
definitionsToTraverse
is empty. And I'm mutating the arrays from the parameters directly, I think I shouldn't do that.
So any help would be appreciated a lot!