How to sort a list of entities once per custom 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 }},
];

When reading a configuration file I get some "sources" which also have a type and might have a sort function with a sort index ( optional )

const sources = [
  { 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 }},
];

Each source describes how to deal with entities of the given type. The source for "person" defines how entities of type "person" should be sorted.

I do not have any control over the configuration, the isLessThan function comes as a stringified function and its signature is (leftEntity: Entity, rightEntity: Entity) => boolean, so the logic inside the compare function could be anything

I want to sort the array entities by the information gathered from sources 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 sources = [
  { 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, allSources) {
  // if there are no entities, there is nothing to do
  if (unsortedEntities.length === 0) {
    return unsortedEntities;
  }
  
  // only care for the sources with a sort function
  const sourcesWithSort = allSources.filter(source => !!source.sort);
  
  // if there are no sources with sort, there is nothing to do
  if(sourcesWithSort.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 sources by sort index ( at this point we now that sort must exist )
  const sortSources = sourcesWithSort.sort((leftSource, rightSource) => leftSource.sort.index - rightSource.sort.index);
  
  // NOW we can start sorting the entities
  for (const source of sortSources) {
    sortedEntities = sortedEntities.sort((leftEntity, rightEntity) => {
      const { type } = source;
      
      // we can't compare entities if the types aren't equal to the source type
      if(leftEntity.type !== type || rightEntity.type !== type) {
        return 0;
      }
      
      const isLeftEntityLessThanRightEntity = source.sort.isLessThan(leftEntity, rightEntity);
      
      if(isLeftEntityLessThanRightEntity) {
        return -1;
      }
      
      return 1;
    });
  }
  
  return sortedEntities;
}

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

My approach is getting really slow when dealing with many entities ( > 100 ) and many sources ( > 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

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 the car results 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": (a,b)=>a.fields.age-b.fields.age
  },
  "car": {
    "index": -Infinity,
    "comparator": undefined
  },
  "house": {
    "index": 0,
    "comparator": (a,b)=>a.fields.constructionYear-b.fields.constructionYear
  }
}

Then sort the entities based on index value
if the index values are same (or both are -Infinity), then sort based on the type name
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))