Summed-area Table

summed-area-table.ts

// https://en.wikipedia.org/wiki/Summed-area_table

type Point = { x: number; y: number };
type DefaultingGetter<T> = (x: number) => T;
type DefaultingGetterFactory = <T>(xs: T[], def: T) => DefaultingGetter<T>;

interface Mapper {
  toxy: (n: number) => Point;
  toi: (x: number, y: number) => number;
}

const makeGet: DefaultingGetterFactory = <T>(xs: T[], def: T) => (x: number): T =>
  x < 0 || x >= xs.length ? def : xs[x];

const xymap = (w: number) => {
  return {
    toxy: (i: number) => ({ x: i % w, y: Math.floor(i / w) }),
    toi: (x: number, y: number) => w * y + x,
  };
};

const sumtable = (xs: number[], m: Mapper) =>
  xs.reduce((acc, n, i) => {
    const { x, y } = m.toxy(i);
    const get = makeGet(acc, 0);
    const a = get(m.toi(x, y - 1));
    const b = get(m.toi(x - 1, y));
    const c = get(m.toi(x - 1, y - 1));
    const nn = n + a + b - c;
    acc[i] = nn;
    return acc;
  }, []);

const areasum = (xs: number[], m: Mapper, get: DefaultingGetter<number>) => (
  { x: ax, y: ay }: Point,
  { x: bx, y: by }: Point,
) => {
  const A = get(m.toi(ax - 1, ay - 1));
  const B = get(m.toi(bx, ay - 1));
  const C = get(m.toi(ax - 1, by));
  const D = get(m.toi(bx, by));

  return D - B - C + A;
};

// these are the example numbers from the wikipedia article
// prettier-ignore
const nums = [
  31, 2, 4, 33, 5, 36, 
  12, 26, 9, 10, 29, 25, 
  13, 17, 21, 22, 20, 18, 
  24, 23, 15, 16, 14, 19, 
  30, 8, 28, 27, 11, 7, 
  1, 35, 34, 3, 32, 6
];

const w = 6;
const m = xymap(w);
const sumstable = sumtable(nums, m);
const getter = makeGet(sumstable, 0);
const summer = areasum(sumstable, m, getter);
const sum = summer({ x: 2, y: 3 }, { x: 4, y: 4 });

console.log(sum); // 111