How to sort a list of entities once per column sort function in the right order?-CodePudding

Given a bunch of ( not sorted ) entities

const entities = [
  { id: "person-1", type: "person", fields: { age: 34 }}, 
  { id: "car-2", type: "car", fields: { manufacturer: "bar" }}, 
  { id: "house-2", type: "house", fields: { constructionYear: 2010 }}, 
  { id: "person-4", type: "person", fields: { age: 71 }},
  { id: "person-2", type: "person", fields: { age: 57 }}, 
  { id: "house-1", type: "house", fields: { constructionYear: 1968 }}, 
  { id: "car-1", type: "car", fields: { manufacturer: "foo" }},
  { id: "person-3", type: "person", fields: { age: 42 }},
];

to display in a table. Important is the type because all people go into the person column, all cars go into the car column etc. Given some columns

const columns = [
  { type: "person", sort: { index: 1, isLessThan: (left, right) => left.fields.age < right.fields.age }},
  { type: "car", sort: undefined },
  { type: "house", sort: { index: 0, isLessThan: (left, right) => left.fields.constructionYear < right.fields.constructionYear }},
];

you can see that some columns might have a sort feature and others don't. The ones with a sort feature come up with a sort function and an index indicating the column sort order.

I want to sort the array entities by the information gathered from columns and started with

const entities = [
  { id: "person-1", type: "person", fields: { age: 34 }}, 
  { id: "car-2", type: "car", fields: { manufacturer: "bar" }}, 
  { id: "house-2", type: "house", fields: { constructionYear: 2010 }}, 
  { id: "person-4", type: "person", fields: { age: 71 }},
  { id: "person-2", type: "person", fields: { age: 57 }}, 
  { id: "house-1", type: "house", fields: { constructionYear: 1968 }}, 
  { id: "car-1", type: "car", fields: { manufacturer: "foo" }},
  { id: "person-3", type: "person", fields: { age: 42 }},
];

const columns = [
  { type: "person", sort: { index: 1, isLessThan: (left, right) => left.fields.age < right.fields.age }},
  { type: "car", sort: undefined },
  { type: "house", sort: { index: 0, isLessThan: (left, right) => left.fields.constructionYear < right.fields.constructionYear }},
];

function sortEntities(unsortedEntities, allColumns) {
  // if there are no entities, there is nothing to do
  if (unsortedEntities.length === 0) {
    return unsortedEntities;
  }
  
  // only care for the columns with a sort function
  const columnsWithSort = allColumns.filter(column => !!column.sort);
  
  // if there are no columns with sort, there is nothing to do
  if(columnsWithSort.length === 0) {
    return unsortedEntities;
  }
  
  // since we can only compare two entities of the same type we must sort the entities by type first
  let sortedEntities = entities.sort((leftEntity, rightEntity) => {
    // no need for sorting if both have the same type
    if(leftEntity.type === rightEntity.type) {
        return 0;
    }
    
    if(leftEntity.type < rightEntity.type) {
        return -1;
    }
    
    return 1;
  });
  
  // we must sort the columns by sort index ( at this point we now that sort is not undefined )
  const sortColumns = columnsWithSort.sort((leftColumn, rightColumn) => leftColumn.sort.index - rightColumn.sort.index);
  
  // NOW we can start sorting the entities
  for (const column of sortColumns) {
    sortedEntities = sortedEntities.sort((leftEntity, rightEntity) => {
      const { type } = column;
      
      // we can't compare entities if the types aren't equal to the column
      if(leftEntity.type !== type || rightEntity.type !== type) {
        return 0;
      }
      
      const isLeftEntityLessThanRightEntity = column.sort.isLessThan(leftEntity, rightEntity);
      
      if(isLeftEntityLessThanRightEntity) {
        return -1;
      }
      
      return 1;
    });
  }
  
  return sortedEntities;
}

console.log(sortEntities([...entities], [...columns]));

My approach is getting really slow when dealing with many entities ( > 100 ) and many columns ( > 20 ).

Do you have any ideas to improve the approach or any alternatives that might be faster?

CodePudding user response：

First of all, you will need to make sure your data is prepared to go into a table. You will need to process the raw data and convert it into an array of records. After that, you can sort your data much easier. Lastly, you can convert the sorted records into a table and add it to the document.

Also, you have a key on your sorter called isLessThan. You should change that to something more generic like fn or callback. You will want all sorters to be keyed similarly.

const main = () => {
  document.body.append(table(sort(process(entities), columns), columns));
};

const sort = (data, columns) => {
  const sorters = columns
    .map(({ sort }) => sort)
    .filter(s => s)
    .sort(({ index: a }, { index: b }) => a - b)
    .map(({ isLessThan }) => isLessThan); // This is not good...
  return data.sort((a, b) => {
    let sorted = 0, index = 0;
    while (sorted === 0 && index < sorters.length) {
      sorted = sorters[index](a, b);
      index  ;
    }
    return sorted;
  });
};

const process = (rawData) =>
  Object.entries(rawData.reduce((acc, { id, type, fields }) => {
    const [, index] = id.match(/\w -(\d )/);
    if (!acc[index]) acc[index] = { id:  index };
    acc[index][type] = { fields };
    return acc;
  }, {})).sort(([k1], [k2]) => k1 - k2).map(([, v]) => v);

const table = (records, columns) =>
  group('table', {},
    group('thead', {},
      group('tr', {},
        ...columns.map(col =>
          leaf('th', { innerText: col.type })
        )
      )
    ),
    group('tbody', {},
      ...records.map(record =>
        group('tr', {},
          ...columns.map(col =>
            leaf('td', {
              innerText: render(record[col.type], record, col)
            })
          )
        )
      )
    )
  );

const render = (data, record, column) =>
  data ? JSON.stringify(data) : '';

const leaf = (tagName, options) =>
  Object.assign(document.createElement(tagName), options);

const group = (tagName, options, ...children) =>
  appendAll(leaf(tagName, options), children);

const appendAll = (el, children = []) => {
  children.forEach(child => el.appendChild(child));
  return el;
};

const entities = [
  { id: "person-1", type: "person", fields: { age: 34 }}, 
  { id: "car-2", type: "car", fields: { manufacturer: "bar" }}, 
  { id: "house-2", type: "house", fields: { constructionYear: 2010 }}, 
  { id: "person-4", type: "person", fields: { age: 71 }},
  { id: "person-2", type: "person", fields: { age: 57 }}, 
  { id: "house-1", type: "house", fields: { constructionYear: 1968 }}, 
  { id: "car-1", type: "car", fields: { manufacturer: "foo" }},
  { id: "person-3", type: "person", fields: { age: 42 }},
];

const columns = [
  { type: "id" },
  { type: "person", sort: { index: 1, isLessThan: (left, right) => left?.fields?.age < right?.fields?.age }},
  { type: "car" },
  { type: "house", sort: { index: 0, isLessThan: (left, right) => left?.fields?.constructionYear < right?.fields?.constructionYear }},
];

main();

table { border-collapse: collapse; }
table, th, td { border: thin solid grey; }
th, td { padding: 0.5rem; }
th { background: #DDD; }
tbody tr:nth-child(even) { background: #EEE; }
td { font-family: monospace; font-size: smaller; }

CodePudding user response：

You can change the columns array to use a comparator function which directly returns a sort order expected buy the sort comapreFn callback function. For the numerical fields it will be subtraction.

const columns = [
  { type: "person", sort: { index: 1, comparator: (left, right) => left.fields.age - right.fields.age }},
  { type: "car", sort: undefined },
  { type: "house", sort: { index: 0, comparator: (left, right) => left.fields.constructionYear - right.fields.constructionYear }},
];

If you want one for car, it would be

{
  type: "car",
  sort: {
    comparator: (a, b) => a.fields.manufacturer.localeCompare(b.fields.manufacturer)
  }
}

Then you create a mapper object which maps the type to the index and the comparator function. If an index is not mentioned, then it is set to -Infinity (Because, in your case you have car results are on top)

const columnMap = columns.reduce((acc, o) => {
  const { type, sort: { index = -Infinity, comparator } = {} } = o
  acc[type] = { index, comparator };
  return acc
}, {})

It creates this object:

{
  "person": {
    "index": 1,
    "comparator": (e,s)=>e.fields.age-s.fields.age
  },
  "car": {
    "index": -Infinity,
    "comparator": undefined
  },
  "house": {
    "index": 0,
    "comparator": (e,s)=>e.fields.constructionYear-s.fields.constructionYear
  }
}

Then sort the entities based on index value
if the index values are same, then sort based on the type,
if both types are same, then sort based on the type specific comparator function.

Here's a working snippet:

const entities=[{id:"person-1",type:"person",fields:{age:34}},{id:"car-2",type:"car",fields:{manufacturer:"bar"}},{id:"house-2",type:"house",fields:{constructionYear:2010}},{id:"person-4",type:"person",fields:{age:71}},{id:"person-2",type:"person",fields:{age:57}},{id:"house-1",type:"house",fields:{constructionYear:1968}},{id:"car-1",type:"car",fields:{manufacturer:"foo"}},{id:"person-3",type:"person",fields:{age:42}}],
      columns=[{type:"person",sort:{index:1,comparator:(e,s)=>e.fields.age-s.fields.age}},{type:"car",sort:void 0},{type:"house",sort:{index:0,comparator:(e,s)=>e.fields.constructionYear-s.fields.constructionYear}}];

function sortEntities(array, columns) {
  const columnMap = columns.reduce((acc, o) => {
    const { type, sort: { index = -Infinity, comparator } = {} } = o
    acc[type] = { index, comparator };
    return acc
  }, {})
  
 return array.sort((a,b) => 
   columnMap[a.type].index - columnMap[b.type].index 
    || a.type.localeCompare(b.type)
    || columnMap[a.type].comparator?.(a,b)
  )
}

console.log(sortEntities(entities, columns))