robey · May 21, 2024 16:59 · May 21, 2024
diff --git a/arrays.ts b/arrays.ts
@@ -0,0 +1,166 @@
+// missing from JS stdlib
+
+// return an array of numbers starting at `start`, not reaching `end`, incrementing by `step`.
+export function range(start: number, end: number, step: number = 1): number[] {
+  return [...Array(Math.ceil((end - start) / step)).keys()].map(i => i * step + start);
+}
+
+// return the average of an array of numbers.
+export function average(array: number[]): number {
+  return array.reduce((sum, n) => sum + n) / array.length;
+}
+
+
+// ----- arrays
+
+// this is really just a trick to make typescript happy.
+export function removeMissing<A>(list: (A | undefined)[]): A[] {
+  return list.filter(x => x !== undefined) as A[];
+}
+
+// remove an item discovered via `indexOf`.
+export function arrayRemove<A>(array: Array<A>, item: A) {
+  const index = array.indexOf(item);
+  if (index >= 0) array.splice(index, 1);
+}
+
+// call `f` on each item of the array, and return a new array containing only the results that were not undefined.
+export function filterMap<A, B>(list: A[], f: (item: A, index: number) => B | undefined): B[] {
+  return list.reduce<B[]>((rv, item, i) => {
+    const b = f(item, i);
+    if (b !== undefined) rv.push(b);
+    return rv;
+  }, []);
+}
+
+// return the index of the first element where test returns true. if none did, return the array length.
+export function binarySearch<A>(array: A[], test: (item: A) => boolean): number {
+  let lo = -1, hi = array.length;
+  while (lo + 1 < hi) {
+    const m = lo + ((hi - lo) >> 1);
+    if (test(array[m])) {
+      hi = m;
+    } else {
+      lo = m;
+    }
+  }
+  return hi;
+}
+
+// break an array into a list of arrays where each new array's size is `maxSize` except (possibly) the last one.
+export function arraySlice<A>(array: A[], maxSize: number): A[][] {
+  return range(0, array.length, maxSize).map(i => array.slice(i, i + maxSize));
+}
+
+export function groupBy<A>(array: A[], grouper: (a: A) => string): { [key: string]: A[] } {
+  const rv: { [key: string]: A[] } = {};
+  array.forEach(a => {
+    const key = grouper(a);
+    if (rv[key] === undefined) rv[key] = [];
+    rv[key].push(a);
+  });
+  return rv;
+}
+
+// return a list that only contains each item once, based on a lookup per item.
+export function uniqueBy<A>(list: A[], getKey: (item: A) => string): A[] {
+  const seenKeys = new Set<string>();
+  return list.filter(x => {
+    const key = getKey(x);
+    if (seenKeys.has(key)) return false;
+    seenKeys.add(key);
+    return true;
+  });
+}
+
+// return two lists: the first is every item where `f` returned true, the second is every item where `f` returned false.
+export function partition<A>(array: A[], f: (item: A) => boolean): [ A[], A[] ] {
+  const left: A[] = [];
+  const right: A[] = [];
+  array.forEach(item => (f(item) ? left : right).push(item));
+  return [ left, right ];
+}
+
+// return the most popular item from a list.
+export function consensus<A>(
+  array: Array<A>,
+  comparer: (a: A, b: A) => number
+): A | undefined {
+  const sorted: Array<[ A, number ]> = array.sort(comparer).map(item => [ item, 1 ] as [ A, number ]);
+  if (sorted.length == 0) return undefined;
+
+  let i = 1;
+  while (i < sorted.length) {
+    if (comparer(sorted[i - 1][0], sorted[i][0]) == 0) {
+      sorted[i - 1][1]++;
+      sorted.splice(i, 1);
+    } else {
+      i++;
+    }
+  }
+  return sorted.sort((a, b) => b[1] - a[1])[0][0];
+}
+
+
+// ----- iterators
+
+// generate a list of numbers starting at `start`. each subsequent item is
+// supplied by `next`, until `condition` returns false.
+export function generate(
+  start: number,
+  next: (n: number) => number,
+  condition: (n: number, len: number) => boolean
+): number[] {
+  const rv: number[] = [];
+  let current = start;
+  do {
+    rv.push(current);
+    current = next(current);
+  } while (condition(current, rv.length));
+  return rv;
+}
+
+// make an iterator that yields the first `max` items.
+export function* iterTake<A>(iterable: Iterable<A>, max: number): Iterable<A> {
+  const iter = iterable[Symbol.iterator]();
+  for (let i = 0; i < max; i++) {
+    const item = iter.next();
+    if (item.done) return;
+    yield item.value;
+  }
+}
+
+// return an iterable that concatenates all the iterables in `array`.
+export function *iterFlatten<A>(array: Iterable<A>[]): Iterable<A> {
+  for (const x of array) yield* x;
+}
+
+
+// ----- maps
+
+// like `map`, but applying only to the keys of a Map.
+export function mapKeys<A, B, V>(inMap: Map<A, V>, f: (key: A) => B): Map<B, V> {
+  return new Map([...inMap].map(([ k, v ]) => [ f(k), v ]));
+}
+
+// like `filterMap`, but applying only to the keys of a Map.
+export function filterMapKeys<A, B, V>(inMap: Map<A, V>, f: (key: A) => (B | undefined)): Map<B, V> {
+  return new Map(removeMissing([...inMap].map(([ k, v ]) => {
+    const newKey = f(k);
+    return newKey === undefined ? undefined : [ newKey, v ];
+  })));
+}
+
+
+// ----- promises
+
+// like `filter`, for a list of promises.
+export async function asyncFilter<A>(list: A[], f: (item: A) => Promise<boolean>): Promise<A[]> {
+  const allowed = await Promise.all(list.map(f));
+  return list.filter((x, i) => allowed[i]);
+}
+
+// return true if any of the promises returned true.
+export async function asyncSome<A>(list: A[], f: (item: A) => Promise<boolean>): Promise<boolean> {
+  return (await Promise.all(list.map(f))).some(x => x);
+}