Javascript: align parallel arrays index avoiding overlaps

user_3872998 0
Viewed 148

I have a list of arrays where the same item may appear in different lists (but not in the same list). I'm trying to sort the arrays so that matching items have the same index in all the arrays. I'm also trying to fill the empty spots where possible, but it's fine if some positions remain undefined.

Conditions

  1. All dupes are always sequential, so if an element is a dupe, there's for sure a copy in the previous array.
  2. Each item can occur only once per array (the dupes are only in different arrays)
  3. The foo arrays may have different lenghts
  4. The foo array always exist, in the worst case it's empty.
  5. The order in the foo array is not relevant as long as the goal is accomplished.
  6. The wrapper array can't be sorted.

Input

const myWrapper [
    { foo: [] },
    { foo: ['A', 'B', 'C', 'D'] },
    { foo: ['X', 'A', 'E', 'C'] },
    { foo: ['X', 'F', 'C', 'G', 'H'] },
    { foo: ['C'] }
];

Desired output

const myWrapper [
    { foo: [] },
    { foo: ['B', 'A', 'C', 'D'] },
    { foo: ['X', 'A', 'C', 'E'] },
    { foo: ['X', 'F', 'C', 'G', 'H'] },
    { foo: [undefined, undefined, 'C'] }
];

Is there a neat way to achieve this?

My attempt, sorting from the right and using a tmp variable to swap the items. This doesn't seem to work well as the following position sometimes move previous items messing with the order set in the previous iteration.

    let tmp;
    myWrapper.forEach((item, wrapperIndex) => {
        item.foo.forEach((currentFoo, fooIndex) => {
             // Search for match in the previous foo
             if(myWrapper[wrapperIndex - 1]) {
                const prevFoo = myWrapper[wrapperIndex - 1].foo;
                const prevIndex = prevFoo.indexOf(item);
                if (prevIndex >= 0 && prevIndex !== fooIndex) {
                    tmp = prevFoo[fooIndex];
                    prevFoo[fooIndex] = prevEvents[prevIndex];
                    prevFoo[prevIndex] = tmp;
                }
            }
        });
    });

Edit: the issue is also that the loop does other operations on the single items (which are objects really, I used strings to simplify), so I can't move from the right (current items).

The output is rendered via Angular using 2 nested *ngFor so the final result has to maintain this array structure.

sorting arrays javascript
3 Answers

Edit

A simpler solution using the same map of duplicates from my original answer but then using a simple swap algorithm to move duplicate values into their appropriate indexes.

const myWrapper = [
  { foo: [] },
  { foo: ['A', 'B', 'C', 'D'] },
  { foo: ['X', 'A', 'E', 'C'] },
  { foo: ['X', 'F', 'C', 'G', 'H'] },
  { foo: ['C'] }
];

// find dupes and create map of indexes
let
  seen = new Set,
  dupeMap = {}, d = 0;
for (const { foo } of myWrapper) {
  for (const x of foo) {
    seen.has(x)
      ? dupeMap[x] ??= d++
      : seen.add(x);
  }
}

// swap duplicates into appropriate indexes
for (const { foo } of myWrapper) {
  let
    i, j, temp;
  for (i = 0; i < foo.length; i++) {
    j = dupeMap[foo[i]];
    if (j !== undefined && j !== i) {
      temp = foo[i];
      foo[i] = foo[j];
      foo[j] = temp;
      i--;
    }
  }
}

myWrapper.forEach(({ foo }) => console.log(`{foo: [${foo.map(e => e ?? ' ').join(', ')}]}`));
.as-console-wrapper { max-height: 100% !important; top: 0; }

Original Answer

Here's a fairly straightforward solution that avoids sorting. It first creates an object with props of duplicate values and expected index of that value in the final array as value.

It then iterates over each foo array placing duplicate values in a temporary array by index from the duplicate map, and pushing unique values to a second temp array.

before exiting, it tries to backfill holes in the temporary duplicate array from any values in the unique array.

This mutates the myWrapper array in place.

const myWrapper = [
  { foo: [] },
  { foo: ['A', 'B', 'C', 'D'] },
  { foo: ['X', 'A', 'E', 'C'] },
  { foo: ['X', 'F', 'C', 'G', 'H'] },
  { foo: ['C'] }
];

// find dupes and create map of indexes
let
  seen = new Set,
  dupeMap = {}, d = 0;
for (const { foo } of myWrapper) {
  for (const x of foo) {
    seen.has(x)
      ? dupeMap[x] ??= d++
      : seen.add(x);
  }
}

for (const obj of myWrapper) {
  // collect elements into dupe/unique temp arrays
  const
    { foo } = obj,
    dTemp = [], uTemp = [];
  for (const e of foo) {
    (e in dupeMap)
      ? dTemp[dupeMap[e]] = e
      : uTemp.push(e);
  }

  // backfill empty indexes in dupe temp array
  for (const [i, d] of dTemp.entries()) {
    if (d === undefined && uTemp.length) {
      dTemp.splice(i, 1, uTemp.shift());
    }
  }

  // concat back into foo
  obj.foo = [...dTemp, ...uTemp];
}

myWrapper.forEach(({ foo }) => console.log(`{foo: [${foo.map(e => e ?? ' ').join(', ')}]}`));
.as-console-wrapper { max-height: 100% !important; top: 0; }

user_137623010

Your refactor relies on continuity of duplicates from one array to the next in order to maintain consistent indexing (because it's only looking behind one array). If you break this continuity, the indexing resets.

I copied your snippet and added a 'breaking' short array. 

function arrangeParallelItems(wrapper) {
  // start from the second element, so we're sure we can backlook
  wrapper.slice(1).forEach((item, itemIndex) => {
    let i = -1,
      dupeIndex,
      tmp;
    while (++i < item.foo.length) {
      if (!item.foo[i]) {
        // Skip empty values
        continue;
      }
      dupeIndex = wrapper[itemIndex].foo.indexOf(item.foo[i]);
      if (dupeIndex > -1 && dupeIndex !== i) {
        tmp = item.foo[i];
        item.foo[i] = item.foo[dupeIndex];
        item.foo[dupeIndex] = tmp;
        i--;
      }
    }
  });
}

const myWrapper = [
  { foo: [] },
  { foo: ['A', 'B', 'C', 'D'] },
  { foo: ['H'] },
  { foo: ['X', 'A', 'E', 'C'] },
  { foo: ['A', 'B', 'C', 'D'] },
  { foo: ['F', 'C', 'G', 'H', 'X'] },
  { foo: ['C'] }
];

arrangeParallelItems(myWrapper);

myWrapper.forEach(({ foo }) =>
  console.log(`{foo: [${foo.map(e => e ?? ' ').join(', ')}]}`)
)
.as-console-wrapper { max-height: 100% !important; top: 0; }

user_137623010

In the end I came up with an even simpler solution starting from @pilchard's work.

working with simple strings

function arrangeParallelItems(wrapper) {
  // start from the second element, so we're sure we can backlook
  wrapper.slice(1).forEach((item, itemIndex) => {
let i = -1,
  dupeIndex,
  tmp;
while (++i < item.foo.length) {
  if (!item.foo[i]) {
    // Skip empty values
    continue;
  }
  dupeIndex = wrapper[itemIndex].foo.indexOf(item.foo[i]);
  if (dupeIndex > -1 && dupeIndex !== i) {
    tmp = item.foo[i];
    item.foo[i] = item.foo[dupeIndex];
    item.foo[dupeIndex] = tmp;
    i--;
  }
}
  });
}

const myWrapper = [
  { foo: [] },
  { foo: ['A', 'B', 'C', 'D'] },
  { foo: ['X', 'A', 'E', 'C'] },
  { foo: ['X', 'F', 'C', 'G', 'H'] },
  { foo: ['C'] }
];

arrangeParallelItems(myWrapper);

myWrapper.forEach(({ foo }) =>
console.log(`{foo: [${foo.map(e => e ?? ' ').join(', ')}]}`)
)

working with objects (the id here is the unique key to match the items)

function arrangeParallelItems(wrapper) {
    // start from the second element, so we're sure we can backlook
    wrapper.slice(1).forEach((item, itemIndex) => {
        let i = -1, dupeIndex, tmp;
        while (++i < item.foo.length) {
            if (!item.foo[i]) {
                // Skip empty values
                continue;
            }
            dupeIndex = wrapper[itemIndex].foo.findIndex((e) => e.id === item.foo[i].id);
            if (dupeIndex > -1 && dupeIndex !== i) {
                tmp = item.foo[i];
                item.foo[i] = item.foo[dupeIndex];
                item.foo[dupeIndex] = tmp;
                i--;
            }
        }
    });
}

Blitz with more cases here

user_38729980
Related