Javascript merge objects in array by values

Question

In Javascript, I have an array with objects that looks like this:

var arr = [
    {
        value_1: 0,
        value_2: 4,
        encounter_bits: {
            min_level: 8,
            max_level: 12,
            rarity: 20,
            conditions: [1, 5]
        }
    },
    {
        value_1: 1,
        value_2: 4,
        encounter_bits: {
            min_level: 5,
            max_level: 5,
            rarity: 20,
            conditions: [2, 9]
        }
    },
    {
        value_1: 0,
        value_2: 4,
        encounter_bits: {
            min_level: 8,
            max_level: 12,
            rarity: 5,
            conditions: [1, 5]
        }
    },
];

I need to merge the objects that have the same min_level, max_level and conditions. The merged objects will have their rarity added up. I also need to preserve the array order.

So arr[0] and arr[2] will become:

    arr[0] = {
        value_1: 0,
        value_2: 4,
        encounter_bits: {
            min_level: 8,
            max_level: 12,
            rarity: 25,
            conditions: [1, 5]
        }
    }

From roughly the same dataset, this is being done in Python:

# Combine "level 3-4, 50%" and "level 3-4, 20%" into "level 3-4, 70%".
existing_encounter = filter(lambda enc: enc['min_level'] == encounter.min_level
                                    and enc['max_level'] == encounter.max_level,
                            encounter_bits)
if existing_encounter:
    existing_encounter[0]['rarity'] += encounter.slot.rarity
else:
    encounter_bits.append({
        'min_level': encounter.min_level,
        'max_level': encounter.max_level,
        'rarity': encounter.slot.rarity,
    })

I know I might have to do something with array.sort and array.splice but I can't figure this out. What would be the most efficient way to achieve this?

Answer 1

This is some experimental code that i just came up with and its native javascript.

First Define a function that compares two arrays.

function compareArrays( val_one, val_two ) {
  var arr_one = val_one, arr_two = val_two;

   if ( arr_one.length !== arr_two.length ) return false;

   for ( var i = 0; i < arr_one.length; i++ ) {
     if( arr_one[i] !== arr_two[i] ) return false;
   }  
  return true;
}

**Also define a function that merges two objects

function mergeObjects( obj_1, obj_2 ) {
  var a = obj_1, b = obj_2;

  for ( prop in b ) { 
    if ( !a[prop] ) {
      a[prop] = b[prop];
    }
    else if ( prop === 'encounter_bits' ) {
      a[prop]['rarity'] += b[prop]['rarity'];
    }
  }
  return a;
}

Let us traverse our array

for ( var i=0; i<arr.length; i++ ) {  // loop over the array that holds objects.
 if(arr[i] !== null){    // if object has not been used
  var _min = arr[i].encounter_bits.min_level,  
      _max = arr[i].encounter_bits.max_level,
      _con = arr[i].encounter_bits.conditions; //create variables that hold values you want to compare

for ( var c = 0; c < arr.length; c++ ) { /*  create an inner loop that will also traverse the array */

  if ( c !== i && arr[c] !== null ) {   // if inner loop is not on current loop index 
    if ( _min === arr[c].encounter_bits.min_level &&
        _max === arr[c].encounter_bits.max_level &&
        compareArrays(_con, arr[c].encounter_bits.conditions)  
      ) 
        {
         var newObject = mergeObjects(arr[i], arr[c]);
         arr[i] = newObject;     
         arr[c] = null; 
         }
        }

    }
  }       
}

Please let me know if it works.

Answer 2

I haven't tested it, but it should give basic idea. Doesn't use splice or sort.

// Collect members that have same min-max levels in one array.
// this array is saved in a map keyed by a string made up of min-max levels
var m = {};
for(var i=0; i<arr.length; i++)
{
    var a = arr[i];
    tag = ''+a.encounter_bits.min_level+'-'+a.encounter_bits.max_level);
    if(m[tag]){
        m[tag].push(i);
    }else {
        m[tag] = [i]
    }
}

// for each element of map, calculate sum of rarities
// set the rarity of all member in that element of map to sum of rarities
for(var i in m){
    var candidates = m[i];
    var r = 0;
    for(var j=0; j<candidates.length; j++){
      r += candidates[j].encounter_bits.rarity;
    }
    for(var j=0; j<candidates.length; j++){
       candidates[j].encounter_bits.rarity = r;
    }            
 }

Answer 3

This is my solution:

arr.forEach(function(el,i,a){
    if (el.toDelete == true) return;
    var toMerge = a.filter(function(elF,iF,aF){
        if (elF.toDelete==undefined && iF != i &&  
            elF.encounter_bits.min_level == el.encounter_bits.min_level && 
            elF.encounter_bits.max_level == el.encounter_bits.max_level
            ) {
            aF[iF].toDelete = true; /* mark element to delete */
            return 1;
        }
    });

    for (var m in toMerge){
        el.encounter_bits.rarity += toMerge[m].encounter_bits.rarity; 
    }
});
/* delete marked elements */
for (var i=0;i<arr.length;i++){
    if(arr[i].toDelete ==true){
        arr.splice(i,1);
        i--;
    }
}

It works in Mozilla and Chrome. For IE you need to add "filter" and "forEach" methods to array's prototype, you can find it here.

UPD: My mistake. forEach and filter didn't likes splice for own array and miss some elements. I replaced splice to "toDelete" property and have to delete marked elements after merge.

Answer 4

Here is nicely namespaced and self-contained solution in code. It uses no "modern" (and possibly unavailable) features like forEach and filter. It cleans up the invalidated records after all is said and done, instead of going about deleting items i the live array while the process is going on. It is also very easy to modify if you want to change the way you identify duplicates or how to merge objects.

There is a commented version (with example and a minified version) at pastie, here.

(function (global, ns) {
function mergeRecordsAndCleanUp(arr) {
  var rec, dupeIndices, foundDupes;
  for(var idx=0, len=arr.length; idx<len-1; ++idx) {
    rec = arr[idx];
    if (rec===null) continue;
    dupeIndices = findDupeIndices(rec, arr.slice(idx+1), idx+1);
    if (dupeIndices.length===0) continue;
    foundDupes = true;
    processDupes(rec, dupeIndices, arr);
  }
  if (foundDupes) cleanUpArray(arr);
}
function cleanUpArray(arr) {
  for (var idx=0, len=arr.length; idx<len; ++idx) {
    if (arr[idx]===null) arr.splice(idx--, 1);
  }
}
function processDupes(rec, dupeIndices, arr) {
  var dupeRealIdx, dupeRec;
  for (var dupeIdx=0, dupesLen=dupeIndices.length; dupeIdx<dupesLen; ++dupeIdx) {
    dupeRealIdx = dupeIndices[dupeIdx];
    dupeRec = arr[dupeRealIdx];
    updateRecord(rec, dupeRec);
    arr[dupeRealIdx] = null;
  }
}
function findDupeIndices(rec, arr, offset) {
  var other, result = [];
  for (var idx=0, len=arr.length; idx<len; ++idx) {
    other = arr[idx];
    if (other===null) continue;
    if (isDupe(rec, other)) result.push(idx+offset);
  }
  return result;
}
function identicalArrays(arr0, arr1) {
  if (arr0.length!==arr1.length) return false;
  for (var idx=0, len=arr0.length; idx<len; ++idx) {
    if (arr0[idx]!==arr1[idx]) return false;
  }
  return true;
}
function isDupe(original_record, candidate_record) {
  var orec_bits = original_record.encounter_bits
    , crec_bits = candidate_record.encounter_bits;
  return (crec_bits.min_level===orec_bits.min_level && crec_bits.max_level===orec_bits.max_level) 
    && (identicalArrays(crec_bits.conditions, orec_bits.conditions));
}
function updateRecord(rec, dupe) {rec.encounter_bits.rarity += dupe.encounter_bits.rarity}
global[ns] = {
  npup: mergeRecordsAndCleanUp
};
})(this, 'npup'/* sweet namespace eh */);
// npup.npup(arr);