Mutating an array with the elements of another array while maintaining order and existing instances

Question

Need help with an algorithm that takes two arrays and results in a specific comparison between them that maintains the same order:

• If _ID in existing but _ID not in overwriter, then do Not include element in result
• If _ID is in overwriter but _ID not in existing, then add element to RESULT
• If _ID is in both existing and overwriter, then add element with version/instance of _ID from existing to result

captial letter represents reference _ID v# represents version/instance of reference _ID

1.

existing: [ Av1 Bv1 Cv1 Ev1 Fv1 Gv1 ]

overwriter: [ Bv2 Dv1 Fv2 Hv1 Jv1 ]

result: [ Bv1 Dv1 Fv1 Hv1 Jv1 ]

2.

existing: [ Bv1 Cv1 Ev1 Fv1 Gv1 ]

overwriter: [ Av1 Bv2 Dv1 Fv2 Hv1 Jv1 ]

result: [ Av1 Bv1 Dv1 Fv1 Hv1 Jv1 ]

3.

existing: [ Av1 Bv1 Cv1 Ev1 Fv1 Gv1 ]

overwriter: [ Av2 Bv2 Dv1 Fv2 Hv1 Jv1 ]

result: [ Av1 Bv1 Dv1 Fv1 Hv1 Jv1 ]

4.

existing: [ Cv1 Dv1 Ev1 ]

overwriter: [ Av1 Bv1 Dv2 Fv1 Hv1 Jv1 ]

result: [ Av1 Bv1 Dv1 Fv1 Hv1 Jv1 ]

5.

existing: [ Av1 Bv1 Cv1 Ev1 Fv1 Gv1 ]

overwriter: [ Dv1 ]

result: [ Dv1 ]

I am looking for a log(n) function that performs this mutation operation in one pass (perhaps with pivot indices for both existing and overwriter but I'm unsure).

do not want to use indexOf.

This is my log(n^2) solution using a shrinking tail technique:

let eIndx = 0,
    existing = [ Av1, Bv1, Cv1, Ev1, Fv1, Gv1 ],
    overwriter = [ Bv2, Dv1, Fv2, Hv1, Jv1 ];

overwriter.map( element => {

    while( element._ID !== existing[ eIndx ]._ID && 
           eIndx       !== existing.length ) {

        delete existing[ eIndx ];

        ++eIndx;
    }

    return eIndx !== existing.length ? existing[ eIndx ] : element;
});

This solution is slowest if none of the _ID's in existing are in overwriter.

I am not sure if I should be iterating through the existing array or the overwriter array.

In my expanded (more convoluted) solution that I've paraphrased this post from, I iterated through the overwriter and I had a hash dictionary to reference whether a _ID/version combo already existed in the future (later indeces that have yet to be iterated upon) of the array. I can no longer use that global dictionary and I am trying to figure out whether I need to make a local dictionary for each array instance or if there is a way i don't need the dictionary and just use the pivots to compare. A problem I see with the pivots in a log(n) solution is that it doesn't know whether the first element of overwriter is a new _ID without iterating through all of the existing array.

Mostly I am looking for something as fast as possible

I am most grateful for help you can share.

Answer 1

You could use a Map and check the existence of the id.

function merge(existing, overwriter) {
    const getId = s => s.split('v')[0]; // or whatever is suitable

    var versions = new Map;

    existing.forEach(s => versions.set(getId(s),  s));
    return overwriter.map(s => versions.get(getId(s)) || s);
}

console.log(merge([ 'Av1', 'Bv1','Cv1','Ev1','Fv1', 'Gv1' ],[ 'Bv2', 'Dv1','Fv2','Hv1','Jv1']));

.as-console-wrapper { max-height: 100% !important; top: 0; }