Skip to content

Instantly share code, notes, and snippets.

@jlevy
Last active June 10, 2023 22:11
Show Gist options
  • Save jlevy/67c9d1f0a92db5529467c403042c4309 to your computer and use it in GitHub Desktop.
Save jlevy/67c9d1f0a92db5529467c403042c4309 to your computer and use it in GitHub Desktop.
Comparison chain for advanced sorting in TypeScript, inspired by Guava
import { comparisonChain, ordering } from './comparisonChain';
interface Item {
title: string | null;
url: string | null;
sequenceNum: number | null;
}
// Setup a sample data
const items: Item[] = [
{ title: 'D', url: 'd.com', sequenceNum: null },
{ title: 'B', url: 'c.com', sequenceNum: 1 },
{ title: 'A', url: 'b.com', sequenceNum: 2 },
{ title: null, url: 'b.com', sequenceNum: 3 },
{ title: 'C', url: 'd.com', sequenceNum: 4 },
{ title: 'A', url: null, sequenceNum: 5 },
{ title: 'B', url: 'a.com', sequenceNum: 6 },
{ title: 'A', url: null, sequenceNum: 7 },
{ title: null, url: 'd.com', sequenceNum: 8 },
{ title: 'C', url: 'd.com', sequenceNum: 9 },
{ title: 'A', url: null, sequenceNum: 10 },
{ title: null, url: null, sequenceNum: 11 },
{ title: 'C', url: 'd.com', sequenceNum: 13 },
{ title: 'C', url: 'd.com', sequenceNum: 12 },
];
describe('comparisonChain', () => {
it('sorts correctly with multiple sorts and nullsLast', () => {
const sorted1 = [...items].sort(
comparisonChain<Item>()
.compare((item) => item.title, ordering.nullsLast)
.compare((item) => item.url, ordering.nullsLast)
.compare((item) => item.sequenceNum, ordering.nullsLast)
.result(),
);
expect(sorted1).toEqual([
{ title: 'A', url: 'b.com', sequenceNum: 2 },
{ title: 'A', url: null, sequenceNum: 5 },
{ title: 'A', url: null, sequenceNum: 7 },
{ title: 'A', url: null, sequenceNum: 10 },
{ title: 'B', url: 'a.com', sequenceNum: 6 },
{ title: 'B', url: 'c.com', sequenceNum: 1 },
{ title: 'C', url: 'd.com', sequenceNum: 4 },
{ title: 'C', url: 'd.com', sequenceNum: 9 },
{ title: 'C', url: 'd.com', sequenceNum: 12 },
{ title: 'C', url: 'd.com', sequenceNum: 13 },
{ title: 'D', url: 'd.com', sequenceNum: null },
{ title: null, url: 'b.com', sequenceNum: 3 },
{ title: null, url: 'd.com', sequenceNum: 8 },
{ title: null, url: null, sequenceNum: 11 },
]);
});
it('sorts correctly with numeric field', () => {
const sorted2 = [...items].sort(
comparisonChain<Item>()
.compare((item) => item.sequenceNum, ordering.nullsLast)
.result(),
);
expect(sorted2).toEqual([
{ title: 'B', url: 'c.com', sequenceNum: 1 },
{ title: 'A', url: 'b.com', sequenceNum: 2 },
{ title: null, url: 'b.com', sequenceNum: 3 },
{ title: 'C', url: 'd.com', sequenceNum: 4 },
{ title: 'A', url: null, sequenceNum: 5 },
{ title: 'B', url: 'a.com', sequenceNum: 6 },
{ title: 'A', url: null, sequenceNum: 7 },
{ title: null, url: 'd.com', sequenceNum: 8 },
{ title: 'C', url: 'd.com', sequenceNum: 9 },
{ title: 'A', url: null, sequenceNum: 10 },
{ title: null, url: null, sequenceNum: 11 },
{ title: 'C', url: 'd.com', sequenceNum: 12 },
{ title: 'C', url: 'd.com', sequenceNum: 13 },
{ title: 'D', url: 'd.com', sequenceNum: null },
]);
});
it('sorts correctly with manual sorting order', () => {
// Manual sorting order for titles.
const titleOrder = ['B', 'A', 'D', 'C', null];
const sorted3 = [...items].sort(
comparisonChain<Item>()
.compare((item) => item.title, ordering.manual(titleOrder))
.compare((item) => item.url, ordering.nullsLast)
.compare((item) => item.sequenceNum, ordering.nullsLast)
.result(),
);
expect(sorted3).toEqual([
{ title: 'B', url: 'a.com', sequenceNum: 6 },
{ title: 'B', url: 'c.com', sequenceNum: 1 },
{ title: 'A', url: 'b.com', sequenceNum: 2 },
{ title: 'A', url: null, sequenceNum: 5 },
{ title: 'A', url: null, sequenceNum: 7 },
{ title: 'A', url: null, sequenceNum: 10 },
{ title: 'D', url: 'd.com', sequenceNum: null },
{ title: 'C', url: 'd.com', sequenceNum: 4 },
{ title: 'C', url: 'd.com', sequenceNum: 9 },
{ title: 'C', url: 'd.com', sequenceNum: 12 },
{ title: 'C', url: 'd.com', sequenceNum: 13 },
{ title: null, url: 'b.com', sequenceNum: 3 },
{ title: null, url: 'd.com', sequenceNum: 8 },
{ title: null, url: null, sequenceNum: 11 },
]);
});
});
export type Selector<T, K> = (item: T) => K;
export type Comparator<T> = (a: T, b: T) => number;
const nullLastCompare: Comparator<any | null> = (a, b) => {
if (a === null) return b === null ? 0 : 1;
if (b === null) return -1;
return defaultCompare(a, b);
};
const nullFirstCompare: Comparator<any | null> = (a, b) => {
if (a === null) return b === null ? 0 : -1;
if (b === null) return 1;
return defaultCompare(a, b);
};
const defaultCompare: Comparator<any> = (a, b) => {
if (typeof a === 'string' && typeof b === 'string') {
return a.localeCompare(b);
}
if (a < b) return -1;
if (a > b) return 1;
return 0;
};
/**
* A Google Guava-style comparison chain to make complex sorting, such as secondary
* sorts, significantly easier.
*
* For example:
*
* items.sort(comparisonChain<Item>()
* .compare(item => item.title, ordering.nullsLast)
* .compare(item => item.url)
* .result());
*/
export const comparisonChain = <T>() => {
let compare: Comparator<T> = (a, b) => 0;
const chain: {
compare: <K>(selector: Selector<T, K>, comparator?: Comparator<K>) => typeof chain;
result: () => Comparator<T>;
} = {
compare: <K>(selector: Selector<T, K>, comparator: Comparator<K> = defaultCompare) => {
const prevCompare = compare;
compare = (a, b) => prevCompare(a, b) || comparator(selector(a), selector(b));
return chain;
},
result: () => compare,
};
return chain;
};
export const reverse =
<T>(comparator: Comparator<T>) =>
(a: T, b: T) =>
comparator(b, a);
// Manually specified comparison order.
const manualOrderComparator = <T>(order: T[]): Comparator<T> => {
// Create a map from value to index in the order array.
const orderMap = new Map(order.map((value, index) => [value, index]));
// Return a comparator that uses the index in the order array.
return (a: T, b: T): number => {
const indexA = orderMap.get(a);
const indexB = orderMap.get(b);
// If a value is not in the manually ordered array, put it at the end.
if (indexA === undefined) return indexB === undefined ? 0 : 1;
if (indexB === undefined) return -1;
return indexA - indexB;
};
};
export const ordering = {
// Simple for now, but could make the ordering interface fluent like Guava as well,
// to allow reversing combined with nulls last, etc.
nullsLast: nullLastCompare,
nullsFirst: nullFirstCompare,
default: defaultCompare,
reversed: reverse(defaultCompare),
manual: manualOrderComparator,
};
@jlevy
Copy link
Author

jlevy commented Jun 10, 2023

Comparison chains are a really nice abstraction for complex sorting situations.

More on Guava's version is here and a couple more thoughts here on Twitter.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment