JavaScript: order array by taking alternately an object of each type

Question

I have an array of objects like this (ordered by type, the objects of the same type are identical):

[
    { "type":"A", "height":50, "width":80 },
    { "type":"A", "height":50, "width":80 },
    { "type":"B", "height":20, "width":100 },
    { "type":"B", "height":20, "width":100 },
    { "type":"C", "height":90, "width":10 }
]

I want to have all these objects in an array which is ordered by taking alternately an object of each type:

[
    { "type":"A", "height":50, "width":80 },
    { "type":"B", "height":20, "width":100 },
    { "type":"C", "height":90, "width":10 },
    { "type":"A", "height":50, "width":80 },
    { "type":"B", "height":20, "width":100 }
]

Answer 1

So since you have the objects arriving ordered then you may also do as follows;

function braide(a){
  // get the chunks ie [a,a,a,a,a,b,b,b,c,c,d] -> [[a,a,a,a,a],[b,b,b],[c,c],[d]]
  var chunks = a.reduce((r,o,i,a) => a[i+1] && o.type !== a[i+1].type ? (r[r.length-1].push(o),r.push([]),r)
                                                                      : (r[r.length-1].push(o),r),[[]]);
  // find the longest chunk by appending items from every chunk at the same index position
  return chunks.reduce((p,c) => p.length > c.length ? p : c)
               .reduce((r,_,i) => (chunks.forEach(c => c[i] && r.push(c[i])),r), []);
}

var data = [{"type":"A","height":50,"width":80},{"type":"A","height":50,"width":80},{"type":"A","height":50,"width":80},{"type":"A","height":50,"width":80},{"type":"A","height":50,"width":80},{"type":"B","height":20,"width":100},{"type":"B","height":20,"width":100},{"type":"B","height":20,"width":100},{"type":"C","height":90,"width":10},{"type":"C","height":90,"width":10},{"type":"D","height":30,"width":70}];

console.log(braide(data));

Answer 2

You could take a Map and iterate until all items are processed in the right order.

var array = [{ type: "A", height: 50, width: 80 }, { type: "A", height: 50, width: 80 }, { type: "B", height: 20, width: 100 }, { type: "B", height: 20, width: 100 }, { type: "C", height: 90, width: 10 }],
    order = ['A', 'B', 'C'],
    types = new Map(order.map(k => [k, []])),
    result = [];

array.forEach(o => types.get(o.type).push(o));

while (types.size) {
    types.forEach((a, k) => (result.push(a.shift()), a.length || types.delete(k)));
}

console.log(result);

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

Answer 3

Wrote a little snippet in ES6. It should be fairly easy to follow through

const getAlternate = (ar) => {
    const types = [];
    const objects = {};
    const typeCounts = {};
    let totalCount = 0;

    ar.forEach((object) => { 
        if(!types.includes(object.type)) {
            types.push(object.type);
            objects[object.type] = object;
            typeCounts[object.type] = 1;
        } else {
            typeCounts[object.type]++;
        }
        totalCount++;
    });

    /**
     * at this point, the state variables will look like this:
     * types ['A', 'B', 'C']
     * objects { A: { type: 'A', height: 50, width: 80 },
     *           B: { type: 'B', height: 20, width: 100 },
     *           C: { type: 'C', height: 90, width: 10 } }
     * typeCounts { A: 2, B: 2, C: 1 }
     * totalCount 5
     *
     * now we can use this data to get the alternation!
     */

    const newAr = [];
    let typeIndex = 0;
    while(totalCount > 0) {
        totalCount--;

        let type = types[typeIndex];
        newAr.push(objects[type]);
        typeCounts[type]--;

        if(typeCounts[type] <= 0) {
            types.splice(typeIndex, 1);
            typeIndex--;
            delete objects[type];
            delete typeCounts[type];
        }

        typeIndex = (typeIndex + 1) % types.length;
    }

    return newAr
}

First thing I do is set some state up in order for it to be easier to iterate over the types later, and that includes a list of each type, a copy of an object of each type, and a count of each type.

From there, I declare a new array and simply follow the alternation using a modulo, deleting everything I don't need anymore

// here we invoke the function
console.log(getAlternate([
    { "type":"A", "height":50, "width":80 },
    { "type":"A", "height":50, "width":80 },
    { "type":"B", "height":20, "width":100 },
    { "type":"B", "height":20, "width":100 },
    { "type":"C", "height":90, "width":10 }
]));

// and, as expected, we get
[
    {"type":"A","height":50,"width":80},
    {"type":"B","height":20,"width":100},
    {"type":"C","height":90,"width":10},
    {"type":"A","height":50,"width":80},
    {"type":"B","height":20,"width":100}
]

Answer 4

Here's my attempt. It's not the most efficient but so long as the input isn't too large it should cope fine.

It assumes that the type will always be a string but it doesn't assume they will always be A, B and C. It loops over the input data to determine the types and collects matching types together as 'partitions'. Once that completes it loops over the types shifting entries off each partition in turn until it's done. If partitions have different numbers of entries that's no problem but it will waste time shifting off objects that don't exist.

You mention that objects of each type are identical but I haven't taken that detail into account. If by 'identical' you mean 'the same object' (i.e. obj1 === obj2) then you could probably take advantage of that to just track counts instead of creating all those partition arrays.

var input = [
    { "type":"A", "height":50, "width":80 },
    { "type":"A", "height":50, "width":80 },
    { "type":"B", "height":20, "width":100 },
    { "type":"B", "height":20, "width":100 },
    { "type":"C", "height":90, "width":10 }
];

var types = [];
var partitions = {};

input.forEach(function(row) {
    var type = row.type;
    
    if (partitions[type]) {
        partitions[type].push(row);
    }
    else {
        partitions[type] = [row];
        types.push(type);
    }
});

var output = [];

while (output.length < input.length) {
    types.forEach(function(type) {
        var next = partitions[type].shift();
        
        if (next) {
            output.push(next);
        }
    });
}

console.log(output);

Answer 5

Try this (explanation in comments)

var inputArr = [
    { "type":"A", "height":50, "width":80 },
    { "type":"A", "height":50, "width":80 },
    { "type":"B", "height":20, "width":100 },
    { "type":"B", "height":20, "width":100 },
    { "type":"C", "height":90, "width":10 }
];

//create an index by type
var typeMap = {};

inputArr.forEach( function( item ){
  typeMap[ item.type ] = typeMap[ item.type ] || [];
  typeMap[ item.type ].push( item );
});

//get sorted type-list
var sortedKeyList = Object.keys( typeMap ); //assuming that keys are always going to be uppercase strings

var output = [];

var noMoreItems = false;

//iterate till there is nothing to iterate
while( !noMoreItems )
{
   //add the top item of every key of the map
   sortedKeyList.forEach( function( key ){      
      var arr = typeMap[ key ];
      output = output.concat(arr.splice(0,1));
      typeMap[ key ] = arr;
   });
   //remove the empty array keys in the map
   sortedKeyList = sortedKeyList.filter( function( key ){
      return typeMap[ key ].length > 0;
   });

   noMoreItems = ( output.length == inputArr.length );  
}

console.log( output );