join.ts

type LeftRight<Left, Right> = {
    left: Left | false,
    right: Right | false
}

type LeftsAndRightsWithSameId<Left, Right> = {
    lefts: Left[],
    rights: Right[]
}

type JoinAccumulator<Left, Right> = Record<string, LeftsAndRightsWithSameId<Left, Right>>

function permutations<Left, Right>(lefts: Left[], rights: Right[]): Array<LeftRight<Left, Right>> {
    if (lefts.length > 0 && rights.length > 0) {
        const results: Array<LeftRight<Left, Right>> = []
        lefts.forEach(left => {
            rights.forEach(right => {
                results.push({left, right})
            })
        })
        return results
    } else if (lefts.length > 0) {
        return lefts.map<LeftRight<Left, Right>>(left => ({left, right: false}))
    } else if (rights.length > 0) {
        return rights.map<LeftRight<Left, Right>>(right => ({left: false, right}))
    } else {
        return []
    }
}

function join<Left, Right>(lefts: Left[], rights: Right[], getLeftId: (left: Left) => string, getRightId: (right: Right) => string) {
    const acc: JoinAccumulator<Left, Right> = {}
    lefts.forEach(left => {
        const leftId = getLeftId(left)
        let leftsAndRightsWithSameId = acc[leftId]
        if (leftsAndRightsWithSameId === undefined) {
            leftsAndRightsWithSameId = { lefts: [], rights: [] }
            acc[leftId] = leftsAndRightsWithSameId
        }
        leftsAndRightsWithSameId.lefts.push(left)
    })
    rights.forEach(right => {
        const rightId = getRightId(right)
        let leftsAndRightsWithSameId = acc[rightId]
        if (leftsAndRightsWithSameId === undefined) {
            leftsAndRightsWithSameId = { lefts: [], rights: [] }
            acc[rightId] = leftsAndRightsWithSameId
        }
        leftsAndRightsWithSameId.rights.push(right)
    })
    const permutationsForEachId = Object.keys(acc).map(key => permutations(acc[key].lefts, acc[key].rights))

    const results: Array<LeftRight<Left, Right>> = []
    permutationsForEachId.forEach(leftRights => {
        results.push(...leftRights)
    })
    return results
}

const lefts = ['rups', 'kever', 'kever', 'aap']
const rights = ['rups', 'kever', 'kever', 'mol'].map((id, index) => ({id, index}))
console.log(join(lefts, rights, x => x, y => y.id))