Given an array of objects named allItems which is pre-sorted, but cannot be sorted again from the information it contains - what is an alternative implementation to the reduce function below that will retain the sorted order of allItems?

The logic below will output:

[{ id: 'd' }, { id: 'a' }, { id: 'b' }]

The desired output is:

[{ id: 'a' }, { id: 'b' }, { id: 'd' }]

// NOTE: allItems is pre-sorted, but lacks the information to re-sort it
const allItems = [{id:'a'}, {id:'b'}, {id:'c'}, {id:'d'}, {id:'e'}, {id:'f'}];

const includedIds = ['d', 'a', 'b'];

// QUESTION: How to create the same output, but in the order they appear in allItems
const unsortedIncludedItems = includedIds.reduce((accumulator, id) => {
  const found = allItems.find(n => n.id === id);
  if (found) accumulator.push(found);
  return accumulator;
}, [])

As mentioned in response to @Ben, simply reversing the logic is a deal breaker for performance reasons.

CodePudding user response：

Try .filter() to get the desired objects and then .sort(). The example below requires the original array (array = [{id:'a'}, {id:'b'}, {id:'c'},...]), the array of values (vArray = ['d', 'b', 'a']), and the property (key = 'id').

const all = [{id:'a'}, {id:'b'}, {id:'c'}, {id:'d'}, {id:'e'}, {id:'f'}];

const values = ['d', 'a', 'b'];

const sortByStringValue = (array, vArray, key) => array.filter(obj => vArray.includes(obj[key])).sort((a, b) => a[key].localeCompare(b[key]));

console.log(JSON.stringify(sortByStringValue(all, values, 'id')));

<iframe name="sif1" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

CodePudding user response：

Instead of iterating over the includedIds (in the wrong order) and seeing whether you can find them in allItems, just iterate over allItems (which is the right order) and see whether you can find their ids in includedIds:

const allItems = [{id:'a'}, {id:'b'}, {id:'c'}, {id:'d'}, {id:'e'}, {id:'f'}];

const includedIds = ['d', 'a', 'b'];

const includedItems = allItems.filter(item => includedIds.includes(item.id));

CodePudding user response：

The issue you have here is that your code reverses the list. You can simply push to the front of the list instead, and the original order will be maintained.

Unfortunately, pushing to the front of a list is slower, it's O(n) rather than O(1). It looks like Array.prototype.unshift is supposed to be faster, but it's still O(n) according to this blog. Assuming that the number of found elements is small you won't notice any performance issues. In that case, replace push with unshift like so:

// NOTE: allItems is pre-sorted, but lacks the information to re-sort it
const allItems = [{id:'a'}, {id:'b'}, {id:'c'}, {id:'d'}, {id:'e'}, {id:'f'}];

const includedIds = ['d', 'a', 'b'];

// QUESTION: How to create the same output, but in the order they appear in allItems
const unsortedIncludedItems = includedIds.reduce((accumulator, id) => {
  const found = allItems.find(n => n.id === id);
  if (found) accumulator.unshift(found);
  return accumulator;
}, [])

Otherwise, these are your options:

1. Create a wrapper around this object that reverses the indexes rather than the array. This can be done with a function like this:

   const getFromEnd = (arr, i) => arr[arr.length - 1 - i]

Note that this can be replaced with arr.at(-i) in new browser versions (last few months). This could be encapsulated within a class if you're feeling OOP inclined.

2. Remember to manually invert the indices wherever you use this array (this will be bug-prone, as you may forget to invert them)
3. Reverse the array. As shown in this fiddle, even with 10,000 elements, the performance is not bad. Assuming this isn't a hotpath or user-interactive code, I think that even 100,000 is probably fine.