How to insert objects in array next to objects with the same property value

Question

I have an array of objects

const allRecords = [
  {
    type: 'fruit',
    name: 'apple'
  },
  {
    type: 'vegetable',
    name: 'celery'
  },
  {
    type: 'meat',
    name: 'chicken'
  }
]

I want to insert objects from another array such that the elements are placed next to elements of the same type.

const  newRecords = [
  {
    type: 'fruit',
    name: 'pear'
  },
  {
    type: 'vegetable',
    name: 'spinach'
  },
  {
    type: 'meat',
    name: 'pork'
  }
]

So that a call like this:

allRecords.sortAndInsert(newRecords)

returns something like this:

[
  {
    type: 'fruit',
    name: 'apple'
  },
  {
    type: 'fruit',
    name: 'pear'
  },
  {
    type: 'vegetable',
    name: 'celery'
  },
  {
    type: 'vegetable',
    name: 'spinach'
  },
  {
    type: 'meat',
    name: 'chicken'
  },
  {
    type: 'meat',
    name: 'pork'
  },

In my case, I can't compare "types" to determine where it should go in the array alphabetically or by length ((vegetables come before meat, but after fruit) . In addition, there's no ID attribute that could numerically position things. I just want to group things by the same type.

I've found that I can insert into the correct index by getting the index using the length of the arrays:

// This gives the amount of records for each group. 
//In our example, this would be 2 for 'apple' and 'pear', etc
const multiplier = (allRecords.length + newRecords.length) / 
   (newRecords.length);
for (let i = 0; i < newRecords.length; i++){
    // Insert the record at 1 + i + multiplier. 'pear' will go to 1 + 0 * 2 = 1
    allRecords.splice(1 + i * multiplier, 0, newRecords[i]);
  }
return allRecords;

However, it is not very readable or obvious what the function is doing. In addition, it assumes that the new records have one of each type.

I would like a function that, instead, looks at the properties and groups them together. Ideally, it should also be able to sort the groups in some order (such as, specifying that the 'fruit' group goes first, the 'vegetable' group goes next, then the 'meat' group.

Answer 1

Grouping

There's a lot to cover here, so I'm going to move somewhat quickly. If you get stuck at any part, please leave a comment and I'll do my best to expand on any problematic areas.

First, there's no guarantee that allRecords or newRecords will be sorted before they are combined. Grouping like items efficiently can be handled easily using a Map. When we want to print out the items in a desired order however, the Map's values will need to be sorted. We'll handle that as the second part of this answer. We start by grouping allRecords by the type property -

const allRecords =
  [ { type: 'fruit', name: 'apple' }
  , { type: 'vegetable', name: 'spinach' }
  , { type: 'meat', name: 'chicken' }
  , { type: 'fruit', name: 'raspberry' } // added this item
  ]

const m1 =
  groupBy(x => x.type, allRecords)

console.log(m1)

// Map
//   { 'fruit' =>
//       [ { type: 'fruit', name: 'apple' }
//       , { type: 'fruit', name: 'raspberry' }
//       ]
//   , 'vegetable' =>
//       [ { type: 'vegetable', name: 'spinach' }
//       ]
//   , 'meat' =>
//       [ { type: 'meat', name: 'chicken' }
//       ]
//   }

Next, we group newRecords the same way -

const newRecords =
  [ { type: 'meat', name: 'pork' }
  , { type: 'fruit', name: 'pear' }
  , { type: 'vegetable', name: 'celery' }
  , { type: 'dairy', name: 'milk' } // added this item
  ]

const m2 =
  groupBy(x => x.type, newRecords)

console.log(m2)

// Map
//   { 'meat' =>
//       [ { type: 'meat', name: 'pork' }
//       ]
//   , 'fruit' =>
//       [ { type: 'fruit', name: 'pear' } 
//       ]
//   , 'vegetable' =>
//       [ { type: 'vegetable', name: 'celery' }
//       ]
//   , 'dairy' =>
//       [ { type: 'dairy', name: 'milk' }
//       ]
//   }

Before we go on, let's define generic function groupBy -

const groupBy = (f, a = []) =>
  a.reduce
    ( (map, v) => upsert(map, [ f (v), v ])
    , new Map
    )

// helper
const upsert = (map, [ k, v ]) =>
  map.has(k)
    ? map.set(k, map.get(k).concat(v))
    : map.set(k, [].concat(v))

Next we need a way to combine the two maps m1 and m2 -

const m3 =
  mergeMap(m1, m2)

console.log(m3)
// Map
//   { 'fruit' =>
//       [ { type: 'fruit', name: 'apple' }
//       , { type: 'fruit', name: 'raspberry' }
//       , { type: 'fruit', name: 'pear' } 
//       ]
//   , 'vegetable' =>
//       [ { type: 'vegetable', name: 'spinach' }
//       , { type: 'vegetable', name: 'celery' }
//       ]
//   , 'meat' =>
//       [ { type: 'meat', name: 'chicken' }
//       , { type: 'meat', name: 'pork' }
//       ]
//   , 'dairy' =>
//       [ { type: 'dairy', name: 'milk' }
//       ]
//   }

We can define mergeMap easily to support merging any number of maps together -

const mergeMap = (...maps) =>
  maps.reduce(mergeMap1, new Map)

// helper
const mergeMap1 = (m1, m2) =>
  Array.from(m2.entries()).reduce(upsert, m1)

As we can see, the Map has nicely grouped the items together. Let's collect all the values now -

const unsorted =
  [].concat(...m3.values())

console.log(unsorted)

// [ { type: 'fruit', name: 'apple' }
// , { type: 'fruit', name: 'raspberry' }
// , { type: 'fruit', name: 'pear' }
// , { type: 'vegetable', name: 'spinach' }
// , { type: 'vegetable', name: 'celery' }
// , { type: 'meat', name: 'chicken' }
// , { type: 'meat', name: 'pork' }
// , { type: 'dairy', name: 'milk' }
// ]

---

Sorting

This section of the answer is not for the feint of heart, but I strongly encourage you to stick with it. We take a functional approach to writing comparison functions, but there are trade-offs with the techniques used. Here, we use many simple functions that are easy to write, test, and maintain. As a result, the functions are more flexible and can be reused in other areas of your program. For more reasoning behind this approach as well as what happens when these techniques are not used, see this recent answer on the topic.

Ok, so we see the list is currently ordered by fruit, vegetable, meat, and then dairy. This is due to the order in which they were grouped in the original Maps. What if you wanted them ordered in a different way?

unsorted.sort(orderByTypes("vegetable", "meat", "fruit"))

// [ { type: 'vegetable', name: 'spinach' }
// , { type: 'vegetable', name: 'celery' }
// , { type: 'meat', name: 'chicken' }
// , { type: 'meat', name: 'pork' }
// , { type: 'fruit', name: 'apple' }
// , { type: 'fruit', name: 'raspberry' }
// , { type: 'fruit', name: 'pear' }
// , { type: 'dairy', name: 'milk' } 
// ]

Ok, and what if we wanted them ordered by name instead?

unsorted.sort(orderByName)

// [ { type: 'fruit', name: 'apple' }
// , { type: 'vegetable', name: 'celery' }
// , { type: 'meat', name: 'chicken' }
// , { type: 'dairy', name: 'milk' }
// , { type: 'fruit', name: 'pear' }
// , { type: 'meat', name: 'pork' }
// , { type: 'fruit', name: 'raspberry' }
// , { type: 'vegetable', name: 'spinach' }
// ]

Would it be possible to orderByTypes first and then do a secondary sorting using orderByName?

unsorted.sort
  ( mergeComparator
      ( orderByTypes("meat", "fruit", "dairy") // primary sort
      , orderByName                            // secondary sort (tie breaker)
      )
  )

// [ { type: 'meat', name: 'chicken' }
// , { type: 'meat', name: 'pork' }
// , { type: 'fruit', name: 'apple' }
// , { type: 'fruit', name: 'pear' }
// , { type: 'fruit', name: 'raspberry' }
// , { type: 'dairy', name: 'milk' }
// , { type: 'vegetable', name: 'celery' }
// , { type: 'vegetable', name: 'spinach' }
// ]

We see the result is first order by types, meat, fruit, and dairy first. And we also see secondary sorting by name. Meats chicken and pork are in ascending order as are fruits apple, pear and raspberry. Note, even though "vegetables" wasn't used in orderByTypes, the secondary sort still applies so celery and spinach are in order.

As you can see, we can define flexible comparator functions like orderByTypes and orderByName and the combine them using mergeComparator to achieve a more intricate and complex behavior. We'll start with the simpler of the two, orderByName -

const orderByName =
  contramap
    ( ascending     // transform base comparator
    , x => x.name   // by first getting object's name property
    )

// base comparator
const ascending = (a, b) =>
  a > b
    ? 1
    : a < b
      ? -1
      : 0

// functional utility
const contramap = (f, g) =>
  (a, b) =>
    f(g(a), g(b))

The orderByTypes comparator is a little more involved -

const orderByTypes = (...types) =>
  contramap
    ( ascending                         // transform base comparator
    , pipe                              // using a function sequence
        ( x => x.type                   // first get the item's type property
        , x => matchIndex(types, x)     // then get the index of the matched type
        , x => x === -1 ? Infinity : x  // then if it doesn't match, put it at the end
        )
    )

// helper
const matchIndex = (values = [], query) =>
  values.findIndex(v => v === query)

// functional utility
const identity = x =>
  x

// functional utility
const pipe = (f = identity, ...more) =>
  more.reduce(pipe1, f)

// pipe helper
const pipe1 = (f, g) =>
  x => g(f(x))

We've defined two (2) separate comparators orderByName and orderByTypes and the last thing we have to do is determine how to combine them -

const mergeComparator = (c = ascending, ...more) =>
  more.reduce(mergeComparator1, c)

// helper 1
const mergeComparator1 = (c1, c2) =>
  (a, b) =>
    mergeComparator2(c1(a, b), c2(a, b))

// helper 2
const mergeComparator2 = (a, b) =>
  a === 0 ? b : a

---

Putting it all together

Okay, let's see if we can put a bow on it -

const allRecords =
  [ { type: 'fruit', name: 'apple' }
  , { type: 'vegetable', name: 'spinach' }
  , { type: 'meat', name: 'chicken' }
  , { type: 'fruit', name: 'raspberry' }
  ]

const newRecords =
  [ { type: 'meat', name: 'pork' }
  , { type: 'fruit', name: 'pear' }
  , { type: 'vegetable', name: 'celery' }
  , { type: 'dairy', name: 'milk' }
  ]

// efficient grouping, can support any number of maps
const grouped = 
  mergeMap
    ( groupBy(x => x.type, allRecords)
    , groupBy(x => x.type, newRecords)
    )

const unsorted =
  [].concat(...grouped.values())

// efficient sorting; can support any number of comparators
const sorted =
  unsorted.sort
    ( mergeComparator
        ( orderByTypes("meat", "fruit", "dairy")
        , orderByName
        )
    )

Output

console.log(sorted)

// [ { type: 'meat', name: 'chicken' }
// , { type: 'meat', name: 'pork' }
// , { type: 'fruit', name: 'apple' }
// , { type: 'fruit', name: 'pear' }
// , { type: 'fruit', name: 'raspberry' }
// , { type: 'dairy', name: 'milk' }
// , { type: 'vegetable', name: 'celery' }
// , { type: 'vegetable', name: 'spinach' }
// ]

Expand the snippet below to verify the results in your own browser -

// ---------------------------------------------------
// STEP 1
const upsert = (map, [ k, v ]) =>
  map.has(k)
    ? map.set(k, map.get(k).concat(v))
    : map.set(k, [].concat(v))

const groupBy = (f, a = []) =>
  a.reduce
    ( (map, v) =>
        upsert(map, [ f (v), v ])
    , new Map
    )

const allRecords =
  [ { type: 'fruit', name: 'apple' }
  , { type: 'vegetable', name: 'spinach' }
  , { type: 'meat', name: 'chicken' }
  , { type: 'fruit', name: 'raspberry' }
  ]

const newRecords =
  [ { type: 'meat', name: 'pork' }
  , { type: 'fruit', name: 'pear' }
  , { type: 'vegetable', name: 'celery' }
  , { type: 'dairy', name: 'milk' }
  ]

const m1 =
  groupBy(x => x.type, allRecords)

console.log("first grouping\n", m1)
// Map
//   { 'fruit' =>
//       [ { type: 'fruit', name: 'apple' }
//       , { type: 'fruit', name: 'raspberry' }
//       ]
//   , 'vegetable' =>
//       [ { type: 'vegetable', name: 'spinach' }
//       ]
//   , 'meat' =>
//       [ { type: 'meat', name: 'chicken' }
//       ]
//   }

const m2 =
  groupBy(x => x.type, newRecords)

console.log("second grouping\n", m2)
// Map
//   { 'meat' =>
//       [ { type: 'meat', name: 'pork' }
//       ]
//   , 'fruit' =>
//       [ { type: 'fruit', name: 'pear' } 
//       ]
//   , 'vegetable' =>
//       [ { type: 'vegetable', name: 'celery' }
//       ]
//   , 'dairy' =>
//       [ { type: 'dairy', name: 'milk' }
//       ]
//   }

// ---------------------------------------------------
// STEP 2
const mergeMap1 = (m1, m2) =>
  Array.from(m2.entries()).reduce(upsert, m1)

const mergeMap = (...maps) =>
  maps.reduce(mergeMap1, new Map)

const m3 =
  mergeMap(m1, m2)

console.log("merged grouping\n", m3)
// Map
//   { 'fruit' =>
//       [ { type: 'fruit', name: 'apple' }
//       , { type: 'fruit', name: 'raspberry' }
//       , { type: 'fruit', name: 'pear' } 
//       ]
//   , 'vegetable' =>
//       [ { type: 'vegetable', name: 'spinach' }
//       , { type: 'vegetable', name: 'celery' }
//       ]
//   , 'meat' =>
//       [ { type: 'meat', name: 'chicken' }
//       , { type: 'meat', name: 'pork' }
//       ]
//   , 'dairy' =>
//       [ { type: 'dairy', name: 'milk' }
//       ]
//   }

const unsorted =
  [].concat(...m3.values())

console.log("unsorted\n", unsorted)
// [ { type: 'fruit', name: 'apple' }
// , { type: 'fruit', name: 'raspberry' }
// , { type: 'fruit', name: 'pear' }
// , { type: 'vegetable', name: 'spinach' }
// , { type: 'vegetable', name: 'celery' }
// , { type: 'meat', name: 'chicken' }
// , { type: 'meat', name: 'pork' }
// , { type: 'dairy', name: 'milk' }
// ]

// ---------------------------------------------------
// STEP 3
const ascending = (a, b) =>
  a > b
    ? 1
: a < b
    ? -1
: 0

const contramap = (f, g) =>
  (a, b) =>
    f(g(a), g(b))

const orderByName =
  contramap(ascending, x => x.name)

const sorted1 =
  unsorted.sort(orderByName)

console.log("sorted by name only\n", sorted1)
// [ { type: 'fruit', name: 'apple' }
// , { type: 'vegetable', name: 'celery' }
// , { type: 'meat', name: 'chicken' }
// , { type: 'dairy', name: 'milk' }
// , { type: 'fruit', name: 'pear' }
// , { type: 'meat', name: 'pork' }
// , { type: 'fruit', name: 'raspberry' }
// , { type: 'vegetable', name: 'spinach' }
// ]


// ---------------------------------------------------
// STEP 4
const identity = x =>
  x

const pipe1 = (f, g) =>
  x => g(f(x))

const pipe = (f = identity, ...more) =>
  more.reduce(pipe1, f)

const matchIndex = (values = [], query) =>
  values.findIndex(v => v === query)

const orderByTypes = (...types) =>
  contramap
    ( ascending
    , pipe
        ( x => x.type 
        , x => matchIndex(types, x)
        , x => x === -1 ? Infinity : x
        )
    )

const sorted2 =
  unsorted.sort(orderByTypes("vegetable", "meat", "fruit"))

console.log("sorted by types\n", sorted2)
// [ { type: 'vegetable', name: 'spinach' }
// , { type: 'vegetable', name: 'celery' }
// , { type: 'meat', name: 'chicken' }
// , { type: 'meat', name: 'pork' }
// , { type: 'fruit', name: 'apple' }
// , { type: 'fruit', name: 'raspberry' }
// , { type: 'fruit', name: 'pear' }
// , { type: 'dairy', name: 'milk' } 
// ]

// ---------------------------------------------------
// STEP 5
const mergeComparator = (c = ascending, ...more) =>
  more.reduce(mergeComparator1, c)

const mergeComparator1 = (c1, c2) =>
  (a, b) =>
    mergeComparator2(c1(a, b), c2(a, b))

const mergeComparator2 = (a, b) =>
  a === 0 ? b : a

const sorted3 =
  unsorted.sort
    ( mergeComparator
        ( orderByTypes("meat", "fruit", "dairy")
        , orderByName
        )
    )

console.log("sorted by types, then name\n", sorted3)
// [ { type: 'meat', name: 'chicken' }
// , { type: 'meat', name: 'pork' }
// , { type: 'fruit', name: 'apple' }
// , { type: 'fruit', name: 'pear' }
// , { type: 'fruit', name: 'raspberry' }
// , { type: 'dairy', name: 'milk' }
// , { type: 'vegetable', name: 'celery' }
// , { type: 'vegetable', name: 'spinach' }
// ]

Note, you will need to open your browser's developer console if you wish to view the Map contents

Answer 2

I'd totally use maps for that. An example would be as follows.

let myMap = new Map();

myMap.set('fruit', [{
  name: 'apple',
  type: 'fruit'
}]);
myMap.set('vegetable', [{
  name: 'celery',
  type: 'vegetable'
}]);
myMap.set('meat', [{
  name: 'chicken',
  type: 'meat'
}]);

const newRecords = [{
  type: 'fruit',
  name: 'pear'
}, {
  type: 'vegetable',
  name: 'spinach'
}, {
  type: 'meat',
  name: 'pork'
}]

newRecords.forEach(function(el) {
  let arr = myMap.get(el.type);
  arr.push(el);
  myMap.set(el.type, arr);
});

for (let [k, v] of myMap) {
  console.log(k);
  console.log(v);
}

Answer 3

Assuming that allRecords is already ordered by type such that the values with any particular type are located in one contiguous segment of the array (or that type doesn't yet exist at all in the array), then the following will work very similarly to Object.assign():

function spliceBy<T, K extends keyof T> (key: K, target: T[], ...sources: Iterable<T>[]) {
  const groups: Map<T[K], T[]> = new Map()

  for (const source of sources) {
    for (const entry of source) {
      const value = entry[key]
      const oldEntries = groups.get(value)
      const entries = oldEntries || []

      if (!oldEntries) groups.set(value, entries)

      entries.push(entry)
    }
  }

  for (const [value, entries] of groups) {
    // find the end of a group of entries
    let found = false
    const index = target.findIndex(
      entry => entry[key] === value ? (found = true, false) : found
    )

    if (found) target.splice(index, 0, ...entries)
    else target.push(...entries)
  }

  return target
}

const allRecords = [{type:'fruit',name:'apple'},{type:'vegetable',name:'celery'},{type:'meat',name:'chicken'}]
const newRecords = [{type:'fruit',name:'pear'},{type:'vegetable',name:'spinach'},{type:'meat',name:'pork'}]

console.log(spliceBy('type', allRecords, newRecords))

^{Try it online!}

If you don't want to modify allRecords, you can call it like this instead:

console.log(spliceBy('type', [], allRecords, newRecords))

Answer 4

Not sure if it's the best solution performance-wise but here it is:

const allRecords = [
  {
    type: 'fruit',
    name: 'apple'
  },
  {
    type: 'vegetable',
    name: 'celery'
  },
  {
    type: 'meat',
    name: 'chicken'
  }
]

const  newRecords = [
  {
    type: 'fruit',
    name: 'pear'
  },
  {
    type: 'vegetable',
    name: 'spinach'
  },
  {
    type: 'meat',
    name: 'pork'
  }
]

function sortAndInsert(...records){
    let totalRecords = [];
    for(let record of records){
        totalRecords = totalRecords.concat(record);
    }
    totalRecords.sort((rec1, rec2)=>{
        if(rec1.type == rec2.type)
            return 0;
        else if(rec1.type > rec2.type)
            return 1;
        else
            return -1;
    })
    return totalRecords;
}

let completeRecords = sortAndInsert(newRecords, allRecords);

Answer 5

This should do the job:

interface Record {
   type: string;
   name: string;
}

interface TypedRecords {
   [type: string]: records[];
}

private _recordsByType: TypedRecords = {};

sortAndInsert(allRecords: Record[], newRecords: Record[]): Record[] {
   const records: Record[] = [];
   this.insert(allRecords);
   this.insert(newRecords);
   Object.keys(this._recordsByType).forEach(type => {
      this._recordsByType[type].forEach(name => {
         records.push({type, name});
      });
   });

   return records;
}

private insert(records: Record[]) {
   records.forEach(record => {
      if (!this._recordsByType[record.type]) {
         this._recordsByType[record.type] = [];
      }
      this._recordsByType[record.type].push(record.value);
   });
}