JavaScript: Fundamental (ES6), part 2, 98–118

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30const fold = (text) => text.normalize('NFD').replace(/\p{Diacritic}/gu, '').toLowerCase();
const looseIncludes = (haystack, needle) => fold(haystack).includes(fold(needle));

const base = new Intl.Collator('en', { sensitivity: 'base' });      // ignores case AND accents
const accentAware = new Intl.Collator('en', { sensitivity: 'accent' });   // ignores case only

const precomposed = 'Ad\u00e9yemi';          // e-acute as one code point
const decomposed = 'Ade\u0301yemi';          // e followed by a combining acute
const lookTheSame = precomposed === decomposed;
const lengths = [precomposed.length, decomposed.length];
const normalisedMatch = precomposed.normalize('NFD') === decomposed.normalize('NFD');

const record = 'Ọlámidé Adéyemi';
const plainSearch = record.toLowerCase().includes('olamide');
const foldedSearch = looseIncludes(record, 'olamide');
const foldedKey = fold(record);

const names = ['Zainab', 'Ébenezer', 'Adaeze'];
const defaultSort = [...names].sort();
const collatedSort = [...names].sort(base.compare);

const collatorAgrees = base.compare('adeyemi', precomposed);
const foldDoesNotStretch = [fold('Ødegaard'), fold('Stra\u00dfe')];
const collatorDoes = [base.compare('\u00f8', 'o'), base.compare('\u00df', 'ss')];
const accentSensitivity = [accentAware.compare('adeyemi', precomposed), accentAware.compare('adeyemi', 'ADEYEMI')];

console.log('same to look at, different to compare:', lookTheSame, lengths);
console.log('plain includes :', plainSearch, '| folded:', foldedSearch);
console.log('default sort   :', defaultSort);
console.log('collated sort  :', collatedSort);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23function truncate(text, max, ellipsis = '\u2026') {
  if (text.length <= max) return text;
  const room = max - ellipsis.length;
  const oneOver = text.slice(0, room + 1);
  const lastSpace = oneOver.lastIndexOf(' ');
  const kept = lastSpace > 0 ? oneOver.slice(0, lastSpace) : oneOver.slice(0, room);
  return kept.replace(/[\s,.;:!?-]+$/, '') + ellipsis;
}

const blurb = 'Fresh gari from Ibadan, delivered across Lagos within 24 hours.';

const shortEnough = truncate('Gari, 5kg', 20);
const exactlyAtTheLimit = truncate('Gari, 5kg', 9);
const cut = truncate(blurb, 30);
const cutShorter = truncate(blurb, 20);
const noDanglingStop = truncate('Delivered in Lagos. Ibadan next.', 22);
const oneLongWord = truncate('Ikejaaaaaaaaaaaaaaaaaaaaaaa', 12);
const everyLengthWithinBudget = [shortEnough, exactlyAtTheLimit, cut, cutShorter, noDanglingStop, oneLongWord].map((s) => s.length);

console.log('short enough :', shortEnough);
console.log('cut to 30    :', cut, '(' + cut.length + ')');
console.log('cut to 20    :', cutShorter);
console.log('no space     :', oneLongWord);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31const reverseByUnit = (text) => text.split('').reverse().join('');
const reverseByCodePoint = (text) => [...text].reverse().join('');

const plain = 'Lagos';
const withEmoji = 'Lagos \u{1F389}';        // a party popper, one code point, two code units

const bothAgreeOnAscii = [reverseByUnit(plain), reverseByCodePoint(plain)];
const unitLength = withEmoji.length;
const pointLength = [...withEmoji].length;
const arrayFromIsTheSame = reverseByCodePoint(withEmoji) === Array.from(withEmoji).reverse().join('');

const brokenByUnits = reverseByUnit(withEmoji).includes('\u{1F389}');
const keptByCodePoints = reverseByCodePoint(withEmoji);

// A flag is two regional-indicator code points, so reversing them is legal and wrong.
const nigeria = '\u{1F1F3}\u{1F1EC}';
const flagPoints = [...nigeria].length;
const reversedFlag = reverseByCodePoint(nigeria);
const becameGuinea = reversedFlag === '\u{1F1EC}\u{1F1F3}';

// A combining accent is its own code point, and it attaches to whatever precedes it.
const composed = 'Ad\u00e9';
const decomposed = 'Ade\u0301';
const reversedComposed = reverseByCodePoint(composed);
const reversedDecomposed = reverseByCodePoint(decomposed);
const twiceIsIdentity = reverseByCodePoint(reverseByCodePoint(withEmoji)) === withEmoji;

console.log('by code unit :', reverseByUnit(withEmoji), '<- the emoji is in pieces');
console.log('by code point:', keptByCodePoints);
console.log('the flag     :', nigeria, '->', reversedFlag);
console.log('the accent   :', decomposed, '->', JSON.stringify(reversedDecomposed));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45const runs = (text) => text.match(/\d+|\D+/g) ?? [];

function naturalCompare(a, b) {
  const left = runs(a);
  const right = runs(b);
  const shared = Math.min(left.length, right.length);
  for (let i = 0; i < shared; i++) {
    const x = left[i];
    const y = right[i];
    if (/^\d/.test(x) && /^\d/.test(y)) {
      const difference = Number(x) - Number(y);
      if (difference !== 0) return difference;
      continue;                                   // equal numbers: 007 and 7 tie here
    }
    if (x !== y) return x.localeCompare(y, 'en');
  }
  // Same runs so far: the shorter name first, then the raw text so the order is total.
  return left.length - right.length || (a < b ? -1 : a > b ? 1 : 0);
}

const collator = new Intl.Collator('en', { numeric: true });

const files = ['item10', 'item2', 'item1', 'item20', 'item3'];
const plainSort = [...files].sort();
const naturalSort = [...files].sort(naturalCompare);
const collatorSort = [...files].sort(collator.compare);

const invoices = ['Invoice 9.pdf', 'Invoice 10.pdf', 'Invoice 1.pdf', 'Invoice 2.pdf'];
const invoiceOrder = [...invoices].sort(naturalCompare);

const branches = ['ikeja-1', 'apapa-9', 'ikeja-10', 'apapa-10'];
const branchOrder = [...branches].sort(naturalCompare);

const leadingZeros = naturalCompare('item02', 'item2');
const noDigitsAtAll = ['bus stop', 'bus', 'busy'].sort(naturalCompare);

// Past 2^53 the numeric comparison stops being able to tell them apart.
const huge = ['v9007199254740993', 'v9007199254740992'];
const numbersCollapse = Number('9007199254740993') - Number('9007199254740992');
const tieBreakRescuesIt = [...huge].sort(naturalCompare);

console.log('plain sort   :', plainSort);
console.log('natural sort :', naturalSort);
console.log('invoices     :', invoiceOrder);
console.log('past 2^53    :', numbersCollapse, '<- the difference the comparator sees');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58const getPath = (source, path) =>
  path.split('.').reduce((node, key) => (node === null || node === undefined ? undefined : node[key]), source);

function setPath(target, path, value) {
  const keys = path.split('.');
  let node = target;
  for (let i = 0; i < keys.length - 1; i++) {
    if (node[keys[i]] === undefined) node[keys[i]] = {};    // only create what is missing
    node = node[keys[i]];
  }
  node[keys[keys.length - 1]] = value;
  return target;
}

function pick(source, paths) {
  const out = {};
  for (const path of paths) {
    const value = getPath(source, path);
    if (value !== undefined) setPath(out, path, value);      // a miss leaves no key at all
  }
  return out;
}

const order = {
  id: 'ORD-001',
  status: 'paid',
  totalKobo: 1290000,
  customer: {
    name: 'Adaeze Okonkwo',
    phone: '08031234567',
    address: { street: '14 Balogun Street', city: 'Lagos', lga: 'Ikeja' },
  },
  items: [
    { sku: 'GARI-5', name: 'Gari, 5kg', qty: 2 },
    { sku: 'OIL-1', name: 'Palm oil, 1L', qty: 1 },
  ],
  courier: null,
};

const summary = pick(order, [
  'id',
  'customer.name',
  'customer.address.city',
  'courier.tracking',
  'nowhere.at.all',
  'items.0.name',
]);

const sharedBranch = pick(order, ['customer.address']);
const sameObject = sharedBranch.customer.address === order.customer.address;
const nothingAsked = pick(order, []);
const deepHit = getPath(order, 'customer.address.lga');
const deepMiss = getPath(order, 'customer.address.postcode');
const throughNull = getPath(order, 'courier.tracking.code');

console.log('summary     :', summary);
console.log('shared leaf :', sameObject);
console.log('deep hit    :', deepHit, '| deep miss:', deepMiss);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45const isPlainObject = (value) =>
  typeof value === 'object' &&
  value !== null &&
  !Array.isArray(value) &&
  Object.getPrototypeOf(value) === Object.prototype;

function merge(base, patch) {
  const out = { ...base };
  for (const [key, value] of Object.entries(patch)) {
    const current = out[key];
    if (Array.isArray(current) && Array.isArray(value)) out[key] = [...current, ...value];
    else if (isPlainObject(current) && isPlainObject(value)) out[key] = merge(current, value);
    else out[key] = value;                          // including null, and including undefined
  }
  return out;
}

const defaults = {
  baseUrl: 'https://api.adauramart.ng',
  timeoutMs: 5000,
  middleware: ['cors', 'logging'],
  retry: { attempts: 3, baseMs: 200 },
  cache: { ttlMs: 60000, keys: ['vendor', 'order'] },
  region: { name: 'Lagos', code: 'LOS' },
};

const production = {
  timeoutMs: 15000,
  middleware: ['auth', 'rate-limit'],
  retry: { attempts: 5 },
  cache: { keys: ['rate'] },
  region: null,
};

const spread = { ...defaults, ...production };
const merged = merge(defaults, production);

const wipedByUndefined = merge(defaults, { timeoutMs: undefined });
const typesDisagree = merge(defaults, { retry: [1, 2] });
const baseUntouched = [defaults.middleware, defaults.retry.attempts];

console.log('spread retry :', spread.retry, '<- baseMs is gone');
console.log('merged retry :', merged.retry);
console.log('middleware   :', merged.middleware);
console.log('region       :', merged.region, '<- null replaces, it does not merge');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49function toQuery(params) {
  const search = new URLSearchParams();
  for (const [key, value] of Object.entries(params)) {
    if (value === undefined || value === null) continue;     // absent, not empty
    if (Array.isArray(value)) {
      for (const item of value) search.append(key, String(item));
      continue;
    }
    search.set(key, String(value));
  }
  return search.toString();
}

function fromQuery(query, arrayKeys = []) {
  const search = new URLSearchParams(query);
  const out = {};
  for (const key of new Set(search.keys())) {
    const all = search.getAll(key);
    out[key] = all.length > 1 || arrayKeys.includes(key) ? all : all[0];
  }
  return out;
}

const filters = {
  q: 'gari, 5kg',
  city: 'Lagos',
  page: 2,
  active: true,
  tag: ['fresh', 'bulk'],
  note: '',
  skip: null,
  gone: undefined,
  sign: '\u20a6',
};

const query = toQuery(filters);
const back = fromQuery(query);
const types = [typeof back.page, typeof back.active, back.page, back.active];
const droppedKeys = ['skip' in back, 'gone' in back, 'note' in back];

const oneTag = fromQuery(toQuery({ tag: ['fresh'] }));
const oneTagDeclared = fromQuery(toQuery({ tag: ['fresh'] }), ['tag']);

const spaceEncoding = [query.includes('gari%2C+5kg'), back.q];
const nairaEncoding = [query.includes('sign=%E2%82%A6'), back.sign];

console.log('query :', query);
console.log('back  :', back);
console.log('types :', types);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66function memoise(fn, keyOf) {
  const cache = new Map();
  const wrapped = (...args) => {
    const key = keyOf(...args);
    if (cache.has(key)) {
      wrapped.hits += 1;
      return cache.get(key);
    }
    wrapped.misses += 1;
    const value = fn(...args);
    cache.set(key, value);
    return value;
  };
  wrapped.hits = 0;
  wrapped.misses = 0;
  wrapped.keys = () => [...cache.keys()];
  return wrapped;
}

const joinKey = (...args) => args.join(',');
const jsonKey = (...args) => JSON.stringify(args);
const stableKey = (...args) =>
  JSON.stringify(args, (key, value) =>
    value && typeof value === 'object' && !Array.isArray(value)
      ? Object.fromEntries(Object.entries(value).sort((a, b) => (a[0] < b[0] ? -1 : 1)))
      : value);

// 1. A joined key cannot tell one comma-containing argument from two arguments.
let placeRuns = 0;
const place = (...parts) => { placeRuns += 1; return parts.filter(Boolean).join(' / '); };
const byJoin = memoise(place, joinKey);
const joinedCollision = [byJoin('Lagos,Ikeja'), byJoin('Lagos', 'Ikeja'), byJoin.hits, placeRuns];

const byJson = memoise(place, jsonKey);
const jsonKeepsThemApart = [byJson('Lagos,Ikeja'), byJson('Lagos', 'Ikeja'), byJson.misses];

// 2. JSON.stringify writes undefined, null and NaN in an array identically.
let kindRuns = 0;
const kindOf = (value) => { kindRuns += 1; return value === null ? 'null' : typeof value; };
const kind = memoise(kindOf, jsonKey);
const forUndefined = kind(undefined);
const forNull = kind(null);
const forNaN = kind(Number.NaN);
const threeWayCollision = [forUndefined, forNull, forNaN, kind.keys(), kindRuns];

// 3. Key order changes the JSON, so the same box is measured twice.
let areaRuns = 0;
const area = (box) => { areaRuns += 1; return box.w * box.h; };
const byOrder = memoise(area, jsonKey);
const orderMatters = [byOrder({ w: 2, h: 3 }), byOrder({ h: 3, w: 2 }), byOrder.misses];

const bySorted = memoise(area, stableKey);
const sortedFixesIt = [bySorted({ w: 2, h: 3 }), bySorted({ h: 3, w: 2 }), bySorted.misses, bySorted.hits];

// 4. Keying on the object itself is identity, not equality.
const byIdentity = memoise(area, (box) => box);
const shared = { w: 4, h: 5 };
const identity = [byIdentity(shared), byIdentity(shared), byIdentity({ w: 4, h: 5 }), byIdentity.hits, byIdentity.misses];

const totalRuns = areaRuns;
const cacheGrowth = [byOrder.keys().length, bySorted.keys().length, byIdentity.keys().length];

console.log('joined key :', joinedCollision);
console.log('json key   :', jsonKeepsThemApart);
console.log('undefined, null, NaN share the key', kind.keys());
console.log('identity   :', identity);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113function createStore(initial) {
  let state = initial;
  const listeners = new Set();
  const failures = [];

  return {
    get state() { return state; },
    get listenerCount() { return listeners.size; },
    get failures() { return failures.slice(); },

    subscribe(fn) {
      listeners.add(fn);
      let live = true;
      return function unsubscribe() {
        if (!live) return false;          // idempotent: a second call does nothing
        live = false;
        listeners.delete(fn);
        return true;
      };
    },

    set(patch) {
      const next = { ...state, ...patch };
      const changed = Object.keys(next).some((key) => next[key] !== state[key]);
      if (!changed) return 0;

      const previous = state;
      state = next;

      let delivered = 0;
      for (const fn of [...listeners]) {        // a snapshot, not the live Set
        if (!listeners.has(fn)) continue;       // left after the snapshot was taken
        delivered++;
        try {
          fn(state, previous);
        } catch (err) {
          failures.push(err.message);
        }
      }
      return delivered;
    },
  };
}

const store = createStore({ till: 'Balogun 1', naira: 0 });

const seen = [];
const off = store.subscribe((now, before) => seen.push(before.naira + ' -> ' + now.naira));
const firstDelivery = store.set({ naira: 4500 });
const afterOneEvent = [seen.slice(), store.state.naira];

off();
store.set({ naira: 9000 });
const ignoredAfterUnsubscribe = seen.length;
const secondOffReturns = off();
const stillEmpty = store.listenerCount;

// A warden that removes the victim, subscribed FIRST so it runs first.
const victimCalls = [];
const wardenCalls = [];
const staged = createStore({ open: false });
let removeVictim;
staged.subscribe(() => { wardenCalls.push('warden ran'); removeVictim(); });
removeVictim = staged.subscribe(() => { victimCalls.push('victim ran'); });
const deliveredWhileRemoving = staged.set({ open: true });
const victimNeverRan = [wardenCalls.length, victimCalls.length, staged.listenerCount];

// A listener that subscribes another one while the notification is in flight.
const lateCalls = [];
const growing = createStore({ n: 0 });
let added = false;
growing.subscribe(() => {
  if (added) return;
  added = true;
  growing.subscribe(() => lateCalls.push('late ran'));
});
const deliveredWhileAdding = growing.set({ n: 1 });
const lateMissedThisRound = lateCalls.length;
const lateGetsTheNextOne = [growing.set({ n: 2 }), lateCalls.length];

const noopSet = store.set({ till: 'Balogun 1' });

const order = [];
const guarded = createStore({ n: 0 });
guarded.subscribe(() => { order.push('first'); throw new Error('listener blew up'); });
guarded.subscribe(() => order.push('second'));
const deliveredDespiteThrow = guarded.set({ n: 1 });

// The naive version, for contrast: it walks the live Set.
function naiveStore() {
  const listeners = new Set();
  return {
    subscribe(fn) { listeners.add(fn); return () => listeners.delete(fn); },
    notify() {
      let delivered = 0;
      for (const fn of listeners) { delivered++; fn(); if (delivered > 50) break; }
      return delivered;
    },
  };
}
const naive = naiveStore();
let grewOnce = false;
naive.subscribe(() => {
  if (grewOnce) return;
  grewOnce = true;
  naive.subscribe(() => {});
});
const naiveDelivered = naive.notify();

console.log('after one event  :', afterOneEvent);
console.log('warden/victim    :', victimNeverRan, 'delivered', deliveredWhileRemoving);
console.log('late subscriber  :', lateMissedThisRound, 'then', lateGetsTheNextOne[1]);
console.log('failures kept    :', guarded.failures);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93let running = null;                   // the computation currently evaluating

// Both sides of every link: readers hold nodes, and each node holds the reader
// sets it joined, so it can resign from all of them before it runs again.
function signal(value) {
  const readers = new Set();
  return {
    get() {
      if (running) { readers.add(running); running.joined.add(readers); }
      return value;
    },
    set(next) {
      if (next === value) return 0;     // equal is not a change
      value = next;
      const notified = readers.size;
      for (const node of [...readers]) node.invalidate();
      return notified;
    },
  };
}

function computed(fn) {
  let cached;
  let fresh = false;
  let runs = 0;
  const readers = new Set();

  const node = {
    joined: new Set(),
    invalidate() {
      if (!fresh) return;               // already stale: do not re-notify
      fresh = false;
      for (const reader of [...readers]) reader.invalidate();
    },
  };

  return {
    get runs() { return runs; },
    get() {
      if (running) { readers.add(running); running.joined.add(readers); }
      if (!fresh) {
        for (const set of node.joined) set.delete(node);   // resign from last run
        node.joined.clear();
        const outer = running;
        running = node;
        try { cached = fn(); runs++; fresh = true; } finally { running = outer; }
      }
      return cached;
    },
  };
}

const quantity = signal(3);
const unitKobo = signal(250000);
const chargeVat = signal(true);
const vatRate = signal(0.075);

const subtotal = computed(() => quantity.get() * unitKobo.get());
const vat = computed(() => (chargeVat.get() ? Math.round(subtotal.get() * vatRate.get()) : 0));
const total = computed(() => subtotal.get() + vat.get());

const first = [total.get(), subtotal.runs, vat.runs, total.runs];
const cachedRead = [total.get(), total.get(), subtotal.runs, total.runs];

const notifiedByQuantity = quantity.set(5);
const afterQuantity = [total.get(), subtotal.runs, vat.runs, total.runs];

const settingSameValue = quantity.set(5);
const afterNoChange = [total.get(), subtotal.runs, total.runs];

// Turning VAT off makes vat stop reading vatRate at all.
chargeVat.set(false);
const withoutVat = [total.get(), vat.runs];
const vatRateNotifiedNobody = vatRate.set(0.05);
const afterMovingAnUnreadSignal = [total.get(), vat.runs, total.runs];

// Turning it back on re-registers the dependency it had dropped.
chargeVat.set(true);
const backOn = total.get();
const vatRateMattersAgain = vatRate.set(0.075);

const diamond = signal(2);
const doubled = computed(() => diamond.get() * 2);
const tripled = computed(() => diamond.get() * 3);
const combined = computed(() => doubled.get() + tripled.get());
const diamondFirst = [combined.get(), combined.runs];
diamond.set(4);
const diamondAfter = [combined.get(), combined.runs, doubled.runs, tripled.runs];

console.log('first read       :', first);
console.log('after quantity   :', afterQuantity);
console.log('vat off          :', withoutVat, 'then', afterMovingAnUnreadSignal);
console.log('diamond          :', diamondFirst, '->', diamondAfter);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89const clamp = (n, low, high) => Math.min(high, Math.max(low, n));

function windowFor({ total, rowHeight, viewportHeight, scrollTop, overscan = 0 }) {
  const totalHeight = total * rowHeight;
  if (total === 0) return { first: 0, last: -1, count: 0, padTop: 0, padBottom: 0, totalHeight: 0 };

  const maxScroll = Math.max(0, totalHeight - viewportHeight);
  const top = clamp(scrollTop, 0, maxScroll);

  const firstVisible = Math.floor(top / rowHeight);
  // Subtract one pixel: a bottom edge landing exactly on a boundary belongs to
  // the row above it, not the row that starts there.
  const lastVisible = Math.floor((top + viewportHeight - 1) / rowHeight);

  const first = clamp(firstVisible - overscan, 0, total - 1);
  const last = clamp(lastVisible + overscan, 0, total - 1);
  const count = last - first + 1;

  return {
    first,
    last,
    count,
    padTop: first * rowHeight,
    padBottom: totalHeight - (last + 1) * rowHeight,
    totalHeight,
  };
}

const project = (w) => [w.first, w.last, w.count, w.padTop, w.padBottom];
const invariant = (w, rowHeight) => w.padTop + w.count * rowHeight + w.padBottom === w.totalHeight;

const atRest = windowFor({ total: 10000, rowHeight: 40, viewportHeight: 400, scrollTop: 0 });
const onABoundary = windowFor({ total: 10000, rowHeight: 40, viewportHeight: 400, scrollTop: 400 });
const onePixelPast = windowFor({ total: 10000, rowHeight: 40, viewportHeight: 400, scrollTop: 401 });
const withOverscan = windowFor({ total: 10000, rowHeight: 40, viewportHeight: 400, scrollTop: 400, overscan: 2 });
const overscanAtTheTop = windowFor({ total: 10000, rowHeight: 40, viewportHeight: 400, scrollTop: 0, overscan: 3 });
const atTheBottom = windowFor({ total: 10000, rowHeight: 40, viewportHeight: 400, scrollTop: 399600 });
const overscrolled = windowFor({ total: 10000, rowHeight: 40, viewportHeight: 400, scrollTop: 999999 });
const shorterThanViewport = windowFor({ total: 3, rowHeight: 40, viewportHeight: 400, scrollTop: 0 });
const empty = windowFor({ total: 0, rowHeight: 40, viewportHeight: 400, scrollTop: 0 });

let invariantHolds = true;
for (let top = 0; top <= 2000; top += 7) {
  const w = windowFor({ total: 10000, rowHeight: 40, viewportHeight: 400, scrollTop: top, overscan: 2 });
  if (!invariant(w, 40)) invariantHolds = false;
}

// Variable heights: a prefix sum plus a binary search.
function variableWindow(heights, viewportHeight, scrollTop) {
  const offsets = [0];
  for (let i = 0; i < heights.length; i++) offsets.push(offsets[i] + heights[i]);
  const totalHeight = offsets[heights.length];
  const top = clamp(scrollTop, 0, Math.max(0, totalHeight - viewportHeight));

  let low = 0;
  let high = heights.length - 1;
  let first = 0;
  while (low <= high) {
    const mid = (low + high) >> 1;
    if (offsets[mid] <= top) { first = mid; low = mid + 1; } else { high = mid - 1; }
  }

  let last = first;
  while (last + 1 < heights.length && offsets[last + 1] < top + viewportHeight) last++;

  return {
    first,
    last,
    count: last - first + 1,
    padTop: offsets[first],
    padBottom: totalHeight - offsets[last + 1],
    totalHeight,
    probes: offsets.length,
  };
}

const heights = [30, 90, 30, 120, 30, 30, 200, 30];
const varTop = variableWindow(heights, 150, 0);
const varMiddle = variableWindow(heights, 150, 150);
const varBottom = variableWindow(heights, 150, 10000);
const varInvariant = [
  varMiddle.padTop + heights.slice(varMiddle.first, varMiddle.last + 1).reduce((a, b) => a + b, 0) + varMiddle.padBottom,
  varMiddle.totalHeight,
];

console.log('at rest        :', project(atRest));
console.log('on a boundary  :', project(onABoundary), 'one px past:', project(onePixelPast));
console.log('at the bottom  :', project(atTheBottom));
console.log('variable middle:', [varMiddle.first, varMiddle.last, varMiddle.padTop, varMiddle.padBottom]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100class Heap {
  constructor(compare) {
    this.compare = compare;
    this.items = [];
  }
  get size() { return this.items.length; }
  peek() { return this.items.length ? this.items[0] : undefined; }

  push(item) {
    const a = this.items;
    a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(a[i], a[parent]) >= 0) break;
      [a[i], a[parent]] = [a[parent], a[i]];
      i = parent;
    }
    return this.size;
  }

  pop() {
    const a = this.items;
    if (a.length === 0) return undefined;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const left = 2 * i + 1;
        const right = left + 1;
        let small = i;
        if (left < a.length && this.compare(a[left], a[small]) < 0) small = left;
        if (right < a.length && this.compare(a[right], a[small]) < 0) small = right;
        if (small === i) break;
        [a[i], a[small]] = [a[small], a[i]];
        i = small;
      }
    }
    return top;
  }
}

const byNumber = (a, b) => a - b;
const numbers = new Heap(byNumber);
for (const n of [5, 3, 8, 1, 9, 2, 7]) numbers.push(n);
const rawArray = numbers.items.slice();
const rootIsSmallest = [numbers.peek(), numbers.size];

const drained = [];
while (numbers.size) drained.push(numbers.pop());
const emptyBehaviour = [numbers.pop(), numbers.peek(), numbers.size];

// Every parent no greater than its children, checked directly.
const shaped = new Heap(byNumber);
for (const n of [42, 17, 93, 4, 61, 8, 25, 3, 70, 51]) shaped.push(n);
let heapProperty = true;
for (let i = 1; i < shaped.items.length; i++) {
  if (shaped.items[(i - 1) >> 1] > shaped.items[i]) heapProperty = false;
}

// Equal priorities, unstable.
const tickets = [
  { name: 'Adaeze', priority: 2 },
  { name: 'Bode', priority: 1 },
  { name: 'Chidi', priority: 2 },
  { name: 'Dayo', priority: 2 },
  { name: 'Emeka', priority: 1 },
  { name: 'Funke', priority: 2 },
];
const unstable = new Heap((a, b) => a.priority - b.priority);
for (const t of tickets) unstable.push(t);
const unstableOrder = [];
while (unstable.size) unstableOrder.push(unstable.pop().name);
const insertionOrderOfTwos = tickets.filter((t) => t.priority === 2).map((t) => t.name);
const poppedTwos = unstableOrder.filter((n) => insertionOrderOfTwos.includes(n));

let seq = 0;
const stable = new Heap((a, b) => a.priority - b.priority || a.seq - b.seq);
for (const t of tickets) stable.push({ ...t, seq: seq++ });
const stableOrder = [];
while (stable.size) stableOrder.push(stable.pop().name);

// Three largest, using a min-heap of at most three.
const readings = [12, 45, 3, 78, 23, 91, 6, 67, 34, 88, 19];
const topThree = new Heap(byNumber);
let heldAtRest = 0;
for (const r of readings) {
  topThree.push(r);
  if (topThree.size > 3) topThree.pop();
  heldAtRest = Math.max(heldAtRest, topThree.size);
}
const largestThree = [];
while (topThree.size) largestThree.push(topThree.pop());

console.log('backing array :', rawArray);
console.log('popped        :', drained);
console.log('unstable twos :', poppedTwos, 'vs insertion', insertionOrderOfTwos);
console.log('largest three :', largestThree);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127const roads = [
  ['Lagos', 'Ibadan', 130],
  ['Ibadan', 'Ilorin', 160],
  ['Ibadan', 'Benin', 300],
  ['Lagos', 'Benin', 320],
  ['Ilorin', 'Abuja', 350],
  ['Ilorin', 'Lokoja', 250],
  ['Benin', 'Onitsha', 130],
  ['Benin', 'Lokoja', 290],
  ['Onitsha', 'Enugu', 110],
  ['Enugu', 'Makurdi', 240],
  ['Lokoja', 'Abuja', 200],
  ['Lokoja', 'Makurdi', 260],
  ['Abuja', 'Kaduna', 190],
  ['Kaduna', 'Kano', 230],
  ['PortHarcourt', 'Yenagoa', 90],
];

function buildGraph(list) {
  const adjacent = new Map();
  const lengths = new Map();
  const link = (from, to) => {
    if (!adjacent.has(from)) adjacent.set(from, []);
    adjacent.get(from).push(to);
  };
  for (const [a, b, km] of list) {
    link(a, b);
    link(b, a);
    lengths.set(a + '|' + b, km);
    lengths.set(b + '|' + a, km);
  }
  return { adjacent, lengths };
}

const { adjacent, lengths } = buildGraph(roads);
const kmOf = (path, table) => {
  let total = 0;
  for (let i = 1; i < path.length; i++) total += table.get(path[i - 1] + '|' + path[i]);
  return total;
};

// Seen is set at push time. The counter is how many pushes that costs.
function shortestHops(adjacent, start, goal) {
  if (!adjacent.has(start) || !adjacent.has(goal)) return { path: null, hops: -1, pushes: 0 };
  const cameFrom = new Map([[start, null]]);
  const levels = new Map([[start, 0]]);
  let queue = [start];
  let pushes = 1;

  while (queue.length) {
    const next = [];
    for (const city of queue) {
      if (city === goal) {
        const path = [];
        for (let at = goal; at !== null; at = cameFrom.get(at)) path.unshift(at);
        return { path, hops: path.length - 1, pushes, levels };
      }
      for (const neighbour of adjacent.get(city)) {
        if (cameFrom.has(neighbour)) continue;      // already queued by somebody
        cameFrom.set(neighbour, city);
        levels.set(neighbour, levels.get(city) + 1);
        next.push(neighbour);
        pushes++;
      }
    }
    queue = next;
  }
  return { path: null, hops: -1, pushes, levels };
}

// The same walk, but a city is only marked seen once it is popped.
function lateMarking(adjacent, start, goal) {
  const seen = new Set();
  const queue = [start];
  let pushes = 1;
  let popped = 0;
  while (queue.length) {
    const city = queue.shift();
    popped++;
    if (seen.has(city)) continue;
    seen.add(city);
    if (city === goal) return { pushes, popped, reached: true };
    for (const neighbour of adjacent.get(city)) {
      if (seen.has(neighbour)) continue;
      queue.push(neighbour);
      pushes++;
    }
  }
  return { pushes, popped, reached: false };
}

const toKano = shortestHops(adjacent, 'Lagos', 'Kano');
const levelSpread = [toKano.levels.size, toKano.levels.get('Abuja'), toKano.levels.get('Kano'), toKano.levels.has('Yenagoa')];
const sameCity = shortestHops(adjacent, 'Lagos', 'Lagos');
const unreachable = shortestHops(adjacent, 'Lagos', 'Yenagoa');
const notOnTheMap = shortestHops(adjacent, 'Lagos', 'Sokoto');

const late = lateMarking(adjacent, 'Lagos', 'Kano');
const pushComparison = [toKano.pushes, late.pushes, late.pushes > toKano.pushes];

let symmetric = true;
let directedEntries = 0;
for (const [city, neighbours] of adjacent) {
  directedEntries += neighbours.length;
  for (const n of neighbours) if (!adjacent.get(n).includes(city)) symmetric = false;
}

const component = (start) => {
  const seen = new Set([start]);
  const queue = [start];
  while (queue.length) {
    for (const n of adjacent.get(queue.shift())) if (!seen.has(n)) { seen.add(n); queue.push(n); }
  }
  return seen.size;
};
const twoComponents = [component('Lagos'), component('Yenagoa')];

// One long straight road, and fewest hops stops being cheapest.
const expressway = buildGraph([...roads, ['Lagos', 'Abuja', 750]]);
const byHops = shortestHops(expressway.adjacent, 'Lagos', 'Abuja');
const viaIbadan = ['Lagos', 'Ibadan', 'Ilorin', 'Abuja'];
const hopsVsKm = [byHops.hops, kmOf(byHops.path, expressway.lengths), viaIbadan.length - 1, kmOf(viaIbadan, expressway.lengths)];

console.log('Lagos to Kano :', toKano.path.join(' -> '), '=', toKano.hops, 'hops');
console.log('levels        :', levelSpread);
console.log('pushes        :', pushComparison);
console.log('hops vs km    :', hopsVsKm);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96function topoSort(nodes, edges, { tieBreak = (a, b) => (a < b ? -1 : a > b ? 1 : 0) } = {}) {
  const dependents = new Map(nodes.map((n) => [n, []]));
  const incoming = new Map(nodes.map((n) => [n, 0]));
  for (const [before, after] of edges) {
    dependents.get(before).push(after);
    incoming.set(after, incoming.get(after) + 1);
  }

  const ready = nodes.filter((n) => incoming.get(n) === 0).sort(tieBreak);
  const done = [];
  while (ready.length) {
    const task = ready.shift();
    done.push(task);
    for (const next of dependents.get(task)) {
      incoming.set(next, incoming.get(next) - 1);
      if (incoming.get(next) === 0) {
        ready.push(next);
        ready.sort(tieBreak);
      }
    }
  }

  if (done.length === nodes.length) return { order: done, done, stuck: [], cycle: null };
  const stuck = nodes.filter((n) => !done.includes(n));
  return { order: null, done, stuck, cycle: findCycle(nodes, dependents) };
}

function findCycle(nodes, dependents) {
  const UNTOUCHED = 0;
  const ON_STACK = 1;
  const FINISHED = 2;
  const colour = new Map(nodes.map((n) => [n, UNTOUCHED]));
  const stack = [];
  let found = null;

  const visit = (node) => {
    colour.set(node, ON_STACK);
    stack.push(node);
    for (const next of dependents.get(node)) {
      if (found) break;
      if (colour.get(next) === ON_STACK) {
        found = [...stack.slice(stack.indexOf(next)), next];
        break;
      }
      if (colour.get(next) === UNTOUCHED) visit(next);
    }
    stack.pop();
    colour.set(node, FINISHED);
  };

  for (const node of nodes) {
    if (found) break;
    if (colour.get(node) === UNTOUCHED) visit(node);
  }
  return found;
}

const tasks = ['fitOut', 'hire', 'insurance', 'launch', 'lease', 'permit', 'signage', 'stock', 'train'];
const before = [
  ['lease', 'fitOut'],
  ['permit', 'fitOut'],
  ['fitOut', 'stock'],
  ['stock', 'launch'],
  ['hire', 'train'],
  ['train', 'launch'],
  ['permit', 'signage'],
  ['signage', 'launch'],
];

const forwards = topoSort(tasks, before);
const edgesGoForwards = (order, list) =>
  list.every(([a, b]) => order.indexOf(a) < order.indexOf(b));
const forwardsValid = [edgesGoForwards(forwards.order, before), forwards.order.length, forwards.order.includes('insurance')];

const backwards = topoSort(tasks, before, { tieBreak: (a, b) => (a < b ? 1 : a > b ? -1 : 0) });
const bothValid = [edgesGoForwards(backwards.order, before), same(backwards.order, forwards.order)];

const withCycle = topoSort(tasks, [...before, ['launch', 'permit']]);
const kahnGaveUp = [withCycle.order, withCycle.done, withCycle.stuck.length];

const reported = withCycle.cycle;
const cycleIsReal = (() => {
  const pairs = [...before, ['launch', 'permit']].map(([a, b]) => a + '->' + b);
  let everyStepIsAnEdge = true;
  for (let i = 1; i < reported.length; i++) {
    if (!pairs.includes(reported[i - 1] + '->' + reported[i])) everyStepIsAnEdge = false;
  }
  return [everyStepIsAnEdge, reported[0] === reported[reported.length - 1]];
})();

const selfLoop = topoSort(['audit'], [['audit', 'audit']]);

console.log('alphabetical  :', forwards.order.join(' '));
console.log('reverse       :', backwards.order.join(' '));
console.log('with a cycle  :', withCycle.done, 'stuck:', withCycle.stuck);
console.log('the cycle     :', reported.join(' -> '));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95function deepEqual(a, b, seen = new Map()) {
  if (Object.is(a, b)) return true;                     // covers NaN, and -0 vs 0
  if (typeof a !== 'object' || typeof b !== 'object' || a === null || b === null) return false;
  if (Object.getPrototypeOf(a) !== Object.getPrototypeOf(b)) return false;

  if (seen.get(a) === b) return true;                   // this pair is already in flight
  seen.set(a, b);

  if (a instanceof Date) return a.getTime() === b.getTime();
  if (a instanceof RegExp) return a.source === b.source && a.flags === b.flags;

  if (a instanceof Map) {
    if (a.size !== b.size) return false;
    for (const [key, value] of a) {
      if (!b.has(key)) return false;                    // keys matched by identity
      if (!deepEqual(value, b.get(key), seen)) return false;
    }
    return true;
  }

  if (a instanceof Set) {
    if (a.size !== b.size) return false;
    for (const value of a) if (!b.has(value)) return false;
    return true;
  }

  if (Array.isArray(a)) {
    if (a.length !== b.length) return false;
    for (let i = 0; i < a.length; i++) if (!deepEqual(a[i], b[i], seen)) return false;
    return true;
  }

  const keysA = Object.keys(a);
  const keysB = Object.keys(b);
  if (keysA.length !== keysB.length) return false;
  for (const key of keysA) {
    if (!Object.prototype.hasOwnProperty.call(b, key)) return false;
    if (!deepEqual(a[key], b[key], seen)) return false;
  }
  return true;
}

const attempt = (fn) => { try { return fn(); } catch (err) { return err.name; } };

const order1 = { till: 'Balogun 1', items: [{ sku: 'ADR-1', kobo: 450000 }], staff: { name: 'Adaeze' } };
const order2 = { staff: { name: 'Adaeze' }, items: [{ kobo: 450000, sku: 'ADR-1' }], till: 'Balogun 1' };
const reordered = [deepEqual(order1, order2), JSON.stringify(order1) === JSON.stringify(order2)];

const nudged = { ...order2, items: [{ sku: 'ADR-1', kobo: 450001 }] };
const oneKoboOut = deepEqual(order1, nudged);

const nanCase = [deepEqual({ reading: NaN }, { reading: NaN }), JSON.stringify({ reading: NaN })];
const zeroCase = [deepEqual({ drift: 0 }, { drift: -0 }), Object.is(0, -0)];

const missingKey = [deepEqual({ a: 1, b: undefined }, { a: 1 }), JSON.stringify({ a: 1, b: undefined }) === JSON.stringify({ a: 1 })];

const dates = [deepEqual(new Date('2024-03-01T00:00:00Z'), new Date('2024-03-01T00:00:00Z')), deepEqual(new Date('2024-03-01T00:00:00Z'), new Date('2024-03-02T00:00:00Z'))];
const patterns = [deepEqual(/ade/gi, /ade/gi), deepEqual(/ade/g, /ade/gi)];

const arrayVsObject = deepEqual([1, 2], { 0: 1, 1: 2, length: 2 });

const maps = [
  deepEqual(new Map([['a', 1], ['b', { n: 2 }]]), new Map([['b', { n: 2 }], ['a', 1]])),
  deepEqual(new Map([['a', 1]]), new Map([['a', 2]])),
];
const sets = [deepEqual(new Set([1, 2, 3]), new Set([3, 2, 1])), deepEqual(new Set([1, 2]), new Set([1, 2, 3]))];

// Two cycles built independently, and one built differently.
const left = { name: 'Lagos' };
left.self = left;
left.pair = { name: 'Abuja', back: left };
const right = { name: 'Lagos' };
right.self = right;
right.pair = { name: 'Abuja', back: right };
const cyclesMatch = deepEqual(left, right);

const wrong = { name: 'Lagos' };
wrong.self = wrong;
wrong.pair = { name: 'Kano', back: wrong };
const cyclesDiffer = deepEqual(left, wrong);
const stringifyGivesUp = attempt(() => JSON.stringify(left));

// The limitation: Map keys are matched by identity, not by value.
const keyedByObject = deepEqual(
  new Map([[{ sku: 'ADR-1' }, 3]]),
  new Map([[{ sku: 'ADR-1' }, 3]])
);
const sameKeyObject = (() => {
  const key = { sku: 'ADR-1' };
  return deepEqual(new Map([[key, 3]]), new Map([[key, 3]]));
})();

console.log('reordered keys :', reordered);
console.log('cycles         :', cyclesMatch, cyclesDiffer, '| stringify:', stringifyGivesUp);
console.log('object map key :', keyedByObject, 'vs the same key object:', sameKeyObject);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91let allocated = 0;
const node = (key, value, left, right) => {
  allocated++;
  return Object.freeze({ key, value, left, right });
};

const insert = (tree, key, value) => {
  if (tree === null) return node(key, value, null, null);
  if (key === tree.key) {
    if (tree.value === value) return tree;                    // nothing to change
    return node(key, value, tree.left, tree.right);
  }
  if (key < tree.key) {
    const left = insert(tree.left, key, value);
    return left === tree.left ? tree : node(tree.key, tree.value, left, tree.right);
  }
  const right = insert(tree.right, key, value);
  return right === tree.right ? tree : node(tree.key, tree.value, tree.left, right);
};

const get = (tree, key) => {
  let at = tree;
  while (at !== null) {
    if (key === at.key) return at.value;
    at = key < at.key ? at.left : at.right;
  }
  return undefined;
};

const entries = (tree, out = []) => {
  if (tree === null) return out;
  entries(tree.left, out);
  out.push([tree.key, tree.value]);
  entries(tree.right, out);
  return out;
};

const size = (tree) => (tree === null ? 0 : 1 + size(tree.left) + size(tree.right));

// Keys chosen so the tree is balanced: 'm' at the root, 'e' and 't' below it.
let version1 = null;
for (const [key, value] of [['m', 1], ['e', 2], ['t', 3], ['c', 4], ['g', 5], ['p', 6], ['w', 7]]) {
  version1 = insert(version1, key, value);
}
const buildCost = allocated;

allocated = 0;
const version2 = insert(version1, 'f', 8);
const insertCost = allocated;
const bothReadable = [entries(version1).length, entries(version2).length, get(version1, 'f'), get(version2, 'f')];
const oldOneUnchanged = entries(version1).map(([k]) => k).join('');

// The right-hand subtree was not on the path, so it is the very same object.
const sharing = [
  version2.right === version1.right,
  version2.left === version1.left,
  version2.left.left === version1.left.left,
  version2 === version1,
];
const totalNodes = [size(version1), size(version2), insertCost];

allocated = 0;
const version3 = insert(version2, 'f', 8);
const noopInsert = [version3 === version2, allocated];

allocated = 0;
const version4 = insert(version2, 'f', 99);
const changedValue = [version4 === version2, allocated, get(version4, 'f'), get(version2, 'f')];

const frozenWrite = (() => {
  try { version1.value = 'tampered'; return 'no error'; } catch (err) { return err.name; }
})();

// The same idea, one dimension down: a cons list sharing its tail.
let listAllocated = 0;
const cons = (head, tail) => { listAllocated++; return Object.freeze({ head, tail }); };
const toArray = (list) => { const out = []; for (let at = list; at !== null; at = at.tail) out.push(at.head); return out; };

listAllocated = 0;
let queue = null;
for (const till of ['Balogun 1', 'Balogun 2', 'Ikeja 1']) queue = cons(till, queue);
const threeCost = listAllocated;
const branchA = cons('Yaba', queue);
const branchB = cons('Ojota', queue);
const listSharing = [branchA.tail === queue, branchB.tail === queue, branchA.tail === branchB.tail];
const listCost = [listAllocated, toArray(branchA), toArray(branchB).length];

console.log('build cost    :', buildCost, 'nodes; one insert cost', insertCost);
console.log('sharing       :', sharing);
console.log('old version   :', oldOneUnchanged);
console.log('list sharing  :', listSharing, 'for', listCost[0], 'nodes total');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117const isSpace = (c) => c === ' ' || c === '\t' || c === '\n' || c === '\r';
const isDigit = (c) => c >= '0' && c <= '9';
const startsName = (c) => (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c === '_';
const inName = (c) => startsName(c) || isDigit(c);
const sourceLines = (source) => source.split(/\r\n|\r|\n/);

function tokenise(source) {
  const tokens = [];
  let i = 0;
  let line = 1;
  let column = 1;

  // The only place line and column are allowed to change.
  const advance = () => {
    if (source[i] === '\r' && source[i + 1] === '\n') { i += 2; line++; column = 1; return; }
    if (source[i] === '\n' || source[i] === '\r') { i += 1; line++; column = 1; return; }
    i += 1;
    column += 1;
  };

  const fail = (message, atLine, atColumn) => {
    const err = new Error(message + ' at line ' + atLine + ', column ' + atColumn);
    err.name = 'SyntaxError';
    err.line = atLine;
    err.column = atColumn;
    const text = sourceLines(source)[atLine - 1] || '';
    err.caret = text + '\n' + ' '.repeat(atColumn - 1) + '^';
    throw err;
  };

  while (i < source.length) {
    if (isSpace(source[i])) { advance(); continue; }
    if (source[i] === '#') {
      while (i < source.length && source[i] !== '\n' && source[i] !== '\r') advance();
      continue;
    }

    const from = i;
    const atLine = line;
    const atColumn = column;

    if (source[i] === '"') {
      advance();
      while (i < source.length && source[i] !== '"') {
        if (source[i] === '\n' || source[i] === '\r') fail('unterminated string', atLine, atColumn);
        advance();
      }
      if (i >= source.length) fail('unterminated string', atLine, atColumn);
      advance();
      const text = source.slice(from, i);
      tokens.push({ type: 'string', value: text.slice(1, -1), text, line: atLine, column: atColumn });
      continue;
    }

    if (isDigit(source[i])) {
      while (i < source.length && (isDigit(source[i]) || source[i] === '.')) advance();
      const text = source.slice(from, i);
      tokens.push({ type: 'number', value: Number(text), text, line: atLine, column: atColumn });
      continue;
    }

    if (startsName(source[i])) {
      while (i < source.length && inName(source[i])) advance();
      const text = source.slice(from, i);
      tokens.push({ type: 'name', value: text, text, line: atLine, column: atColumn });
      continue;
    }

    if ('{}=,'.indexOf(source[i]) !== -1) {
      const text = source[i];
      advance();
      tokens.push({ type: 'punct', value: text, text, line: atLine, column: atColumn });
      continue;
    }

    fail('unexpected character ' + JSON.stringify(source[i]), atLine, atColumn);
  }

  tokens.push({ type: 'end', value: '', text: '', line, column });
  return tokens;
}

const attempt = (fn) => { try { fn(); return null; } catch (err) { return err; } };

const config = [
  'till "Balogun 1" {',
  '  rate = 0.075   # VAT, as a fraction',
  '  items = 42',
  '}',
].join('\n');

const tokens = tokenise(config);
const placed = tokens.map((t) => t.value + '@' + t.line + ':' + t.column);
const kinds = [tokens.map((t) => t.type).join(' '), typeof tokens[5].value, tokens[5].value];
const commentGone = [tokens.some((t) => String(t.value).indexOf('#') !== -1), tokens[6].value, tokens[6].line];

const stray = attempt(() => tokenise('rate = 0.075\nitems = 42 ?\n}'));
const strayReport = [stray.name, stray.line, stray.column, stray.message];
const strayCaret = stray.caret.split('\n');

const open = attempt(() => tokenise('till "Balogun 1 {\n  rate = 1\n}'));
const openReport = [open.line, open.column, open.message];

const crlf = tokenise('a\r\nb').map((t) => [t.value, t.line, t.column]);

const lines = sourceLines(config);
let cutsBackOut = true;
for (const t of tokens) {
  if (!t.text) continue;
  if (lines[t.line - 1].slice(t.column - 1, t.column - 1 + t.text.length) !== t.text) cutsBackOut = false;
}

console.log('placed  :', placed.join(' '));
console.log('stray   :', strayReport);
console.log('caret   :');
console.log(stray.caret);
console.log('opened  :', openReport);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165function lex(source) {
  const tokens = [];
  let i = 0;
  while (i < source.length) {
    const c = source[i];
    if (c === ' ') { i++; continue; }
    if (c >= '0' && c <= '9') {
      let text = '';
      while (i < source.length && ((source[i] >= '0' && source[i] <= '9') || source[i] === '.')) text += source[i++];
      tokens.push({ type: 'number', value: Number(text), column: i - text.length + 1 });
      continue;
    }
    if (/[a-zA-Z_]/.test(c)) {
      let text = '';
      while (i < source.length && /[a-zA-Z0-9_]/.test(source[i])) text += source[i++];
      tokens.push({ type: 'name', value: text, column: i - text.length + 1 });
      continue;
    }
    if ('+-*/%^(),'.indexOf(c) !== -1) { tokens.push({ type: 'op', value: c, column: i + 1 }); i++; continue; }
    const err = new Error('unexpected character ' + JSON.stringify(c) + ' at column ' + (i + 1));
    err.name = 'SyntaxError';
    throw err;
  }
  tokens.push({ type: 'end', value: '', column: source.length + 1 });
  return tokens;
}

function parse(source) {
  const tokens = lex(source);
  let at = 0;

  const peek = () => tokens[at];
  const fail = (wanted) => {
    const t = tokens[at];
    const found = t.type === 'end' ? 'end of input' : JSON.stringify(String(t.value));
    const err = new Error('expected ' + wanted + ' but found ' + found + ' at column ' + t.column);
    err.name = 'SyntaxError';
    err.column = t.column;
    throw err;
  };
  const eat = (value) => {
    if (tokens[at].type === 'op' && tokens[at].value === value) { at++; return true; }
    return false;
  };

  // sum := product (('+' | '-') product)*        loop, so left-associative
  const sum = () => {
    let left = product();
    for (;;) {
      if (eat('+')) left = { op: '+', left, right: product() };
      else if (eat('-')) left = { op: '-', left, right: product() };
      else return left;
    }
  };

  // product := unary (('*' | '/' | '%') unary)*
  const product = () => {
    let left = unary();
    for (;;) {
      if (eat('*')) left = { op: '*', left, right: unary() };
      else if (eat('/')) left = { op: '/', left, right: unary() };
      else if (eat('%')) left = { op: '%', left, right: unary() };
      else return left;
    }
  };

  // unary := ('-' | '+') unary | power           so -2 ^ 2 is -(2 ^ 2)
  const unary = () => {
    if (eat('-')) return { op: 'neg', operand: unary() };
    if (eat('+')) return unary();
    return power();
  };

  // power := primary ('^' unary)?                recursion, so right-associative
  const power = () => {
    const base = primary();
    if (eat('^')) return { op: '^', left: base, right: unary() };
    return base;
  };

  const primary = () => {
    const t = peek();
    if (t.type === 'number') { at++; return { num: t.value }; }
    if (t.type === 'name') {
      at++;
      if (eat('(')) {
        const args = [];
        if (!eat(')')) {
          for (;;) {
            args.push(sum());
            if (eat(',')) continue;
            if (eat(')')) break;
            fail('"," or ")"');
          }
        }
        return { call: t.value, args };
      }
      return { name: t.value };
    }
    if (eat('(')) {
      const inner = sum();
      if (!eat(')')) fail('")"');
      return inner;
    }
    return fail('a number, a name or "("');
  };

  const tree = sum();
  if (peek().type !== 'end') fail('end of input');
  return tree;
}

const FUNCTIONS = { min: Math.min, max: Math.max, abs: Math.abs };

function evaluate(node, env = {}) {
  if ('num' in node) return node.num;
  if ('name' in node) {
    if (!Object.prototype.hasOwnProperty.call(env, node.name)) {
      const err = new Error('unknown name "' + node.name + '"');
      err.name = 'ReferenceError';
      throw err;
    }
    return env[node.name];
  }
  if ('call' in node) {
    const fn = FUNCTIONS[node.call];
    if (!fn) {
      const err = new Error('unknown function "' + node.call + '"');
      err.name = 'ReferenceError';
      throw err;
    }
    return fn(...node.args.map((a) => evaluate(a, env)));
  }
  if (node.op === 'neg') return -evaluate(node.operand, env);
  const l = evaluate(node.left, env);
  const r = evaluate(node.right, env);
  if (node.op === '+') return l + r;
  if (node.op === '-') return l - r;
  if (node.op === '*') return l * r;
  if (node.op === '/') return l / r;
  if (node.op === '%') return l % r;
  return Math.pow(l, r);
}

const run = (source, env) => evaluate(parse(source), env);
const errorOf = (fn) => { try { fn(); return 'no error'; } catch (err) { return err.name + ': ' + err.message; } };

const precedence = [run('2 + 3 * 4'), run('(2 + 3) * 4'), run('2 * 3 + 4 * 5')];
const leftAssociative = [run('10 - 3 - 2'), parse('10 - 3 - 2')];
const rightAssociative = [run('2 ^ 3 ^ 2'), parse('2 ^ 3 ^ 2')];
const unaryVsPower = [run('-2 ^ 2'), run('(-2) ^ 2'), errorOf(() => new Function('return -2 ** 2'))];

const env = { rate: 0.075, items: 42, floor: 2 };
const withNames = [run('items * rate', env), run('max(items * rate, floor) + 1', env), run('abs(0 - items)', env)];

const unknownName = errorOf(() => run('items * vat', env));
const missingBracket = errorOf(() => run('2 * (3 + 4'));
const leftovers = errorOf(() => run('2 + 3 4'));
const emptyInput = errorOf(() => run(''));
const oddEdges = [run('7 / 0') === Infinity, run('0 - 7 / 0') === -Infinity, run('7 % 3'), run('0 - 7 % 3')];

console.log('precedence      :', precedence);
console.log('10 - 3 - 2 tree :', JSON.stringify(leftAssociative[1]));
console.log('2 ^ 3 ^ 2 tree  :', JSON.stringify(rightAssociative[1]));
console.log('errors          :', [unknownName, missingBracket, leftovers]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142const BACKSLASH = String.fromCharCode(92);   // written this way to keep the escaping readable
const SHORT = { '"': '"', '/': '/', b: '\b', f: '\f', n: '\n', r: '\r', t: '\t' };
SHORT[BACKSLASH] = BACKSLASH;
const NUMBER = /^-?(0|[1-9][0-9]*)(\.[0-9]+)?([eE][+-]?[0-9]+)?/;

function parseJson(text, { protoSafe = true } = {}) {
  let i = 0;

  const fail = (message) => {
    const err = new Error(message + ' at position ' + i);
    err.name = 'SyntaxError';
    err.position = i;
    throw err;
  };
  const skipSpace = () => {
    while (i < text.length && (text[i] === ' ' || text[i] === '\t' || text[i] === '\n' || text[i] === '\r')) i++;
  };
  const expect = (c) => { if (text[i] !== c) fail('expected ' + JSON.stringify(c)); i++; };

  const string = () => {
    expect('"');
    let out = '';
    for (;;) {
      if (i >= text.length) fail('unterminated string');
      const c = text[i];
      if (c === '"') { i++; return out; }
      if (c.charCodeAt(0) < 32) fail('raw control character in string');
      if (c !== BACKSLASH) { out += c; i++; continue; }
      i++;
      const kind = text[i];
      if (kind === 'u') {
        const hex = text.slice(i + 1, i + 5);
        if (!/^[0-9a-fA-F]{4}$/.test(hex)) fail('bad unicode escape');
        out += String.fromCharCode(parseInt(hex, 16));
        i += 5;
        continue;
      }
      if (!Object.prototype.hasOwnProperty.call(SHORT, kind)) fail('unknown escape');
      out += SHORT[kind];
      i++;
    }
  };

  const value = () => {
    skipSpace();
    const c = text[i];
    if (c === '{') {
      i++;
      const out = {};
      skipSpace();
      if (text[i] === '}') { i++; return out; }
      for (;;) {
        skipSpace();
        const key = string();
        skipSpace();
        expect(':');
        const parsed = value();
        if (protoSafe) {
          Object.defineProperty(out, key, { value: parsed, writable: true, enumerable: true, configurable: true });
        } else {
          out[key] = parsed;                 // wrong for exactly one key
        }
        skipSpace();
        if (text[i] === ',') { i++; continue; }
        expect('}');
        return out;
      }
    }
    if (c === '[') {
      i++;
      const out = [];
      skipSpace();
      if (text[i] === ']') { i++; return out; }
      for (;;) {
        out.push(value());
        skipSpace();
        if (text[i] === ',') { i++; continue; }
        expect(']');
        return out;
      }
    }
    if (c === '"') return string();
    if (text.startsWith('true', i)) { i += 4; return true; }
    if (text.startsWith('false', i)) { i += 5; return false; }
    if (text.startsWith('null', i)) { i += 4; return null; }
    const match = NUMBER.exec(text.slice(i));
    if (match) { i += match[0].length; return Number(match[0]); }
    return fail('unexpected ' + (i >= text.length ? 'end of input' : JSON.stringify(c)));
  };

  const out = value();
  skipSpace();
  if (i < text.length) fail('unexpected trailing ' + JSON.stringify(text[i]));
  return out;
}

const rejects = (fn) => { try { fn(); return false; } catch (err) { return true; } };
const errorOf = (fn) => { try { fn(); return 'no error'; } catch (err) { return err.message; } };

const receipt = '{ "till": "Balogun 1", "items": [ { "sku": "ADR-1", "kobo": 450000 }, ' +
  '{ "sku": "ADR-2", "kobo": 125000 } ], "paid": true, "void": false, "note": null, "vat": 7.5e-2 }';
const mine = parseJson(receipt);
const theirs = JSON.parse(receipt);
const matchesTheRealThing = [same(mine, theirs), mine.items[1].kobo, mine.vat, mine.note, mine.void];

// A string with every awkward escape in it, built without drowning in backslashes.
const escaped = '"Adaeze' + BACKSLASH + 'nsaid ' + BACKSLASH + '"eleven' + BACKSLASH + '" ' +
  BACKSLASH + 'u20a6450 ' + BACKSLASH + BACKSLASH + ' end"';
const decoded = parseJson(escaped);
const escapeBehaviour = [decoded === JSON.parse(escaped), decoded.split('\n').length, decoded.indexOf('\u20a6450') !== -1, decoded.indexOf(BACKSLASH) !== -1];

const numbers = '[0, -0.5, 12, 1e3, -2.5E+2, 1e-3]';
const numbersMatch = [same(parseJson(numbers), JSON.parse(numbers)), parseJson(numbers)];

const duplicated = '{"kobo": 100, "kobo": 250}';
const duplicateKeys = [parseJson(duplicated).kobo, JSON.parse(duplicated).kobo, Object.keys(parseJson(duplicated)).length];

const bad = ['{"a": 1,}', "{'a': 1}", '{"a": NaN}', '[01]', '[+1]', '[.5]', '{"a": 1} extra', '', '   ', '[1, 2'];
const bothReject = bad.map((text) => [rejects(() => parseJson(text)), rejects(() => JSON.parse(text))]);
const everyOneRejectedByBoth = bothReject.every(([a, b]) => a === true && b === true);

const positioned = errorOf(() => parseJson('{"a": 1, "b": tru}'));

const polluting = '{"__proto__": {"admin": true}, "user": "Adaeze"}';
const safe = parseJson(polluting);
const naive = parseJson(polluting, { protoSafe: false });
const real = JSON.parse(polluting);
const protoStory = [
  Object.keys(safe),
  Object.keys(naive),
  same(Object.keys(safe), Object.keys(real)),
  naive.admin === true,
  safe.admin,
];

const huge = '{"n": 9007199254740993}';
const precisionLoss = [parseJson(huge).n === JSON.parse(huge).n, parseJson(huge).n === 9007199254740992];

console.log('receipt matches :', matchesTheRealThing);
console.log('escapes         :', JSON.stringify(decoded));
console.log('bad input       :', everyOneRejectedByBoth, 'for', bad.length, 'inputs');
console.log('__proto__       :', protoStory);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128const SYMBOLS = { NGN: '\u20a6', USD: '$' };
const roundHalfAway = (n) => (n < 0 ? -Math.round(-n) : Math.round(n));

class Money {
  constructor(kobo, currency = 'NGN') {
    if (!Number.isInteger(kobo)) {
      throw new TypeError('kobo must be a whole number, got ' + kobo);
    }
    if (!SYMBOLS[currency]) throw new RangeError('unknown currency ' + currency);
    this.kobo = kobo;
    this.currency = currency;
    Object.freeze(this);
  }

  static fromNaira(naira, currency = 'NGN') {
    return new Money(roundHalfAway(naira * 100), currency);
  }

  sameCurrency(other) {
    if (other.currency !== this.currency) {
      throw new TypeError('cannot mix ' + this.currency + ' and ' + other.currency);
    }
  }

  plus(other) { this.sameCurrency(other); return new Money(this.kobo + other.kobo, this.currency); }
  minus(other) { this.sameCurrency(other); return new Money(this.kobo - other.kobo, this.currency); }
  times(factor) { return new Money(roundHalfAway(this.kobo * factor), this.currency); }

  splitInto(parts) {
    if (!Number.isInteger(parts) || parts < 1) throw new RangeError('parts must be a positive whole number');
    const base = Math.trunc(this.kobo / parts);
    let left = this.kobo - base * parts;              // same sign as the amount
    const step = left < 0 ? -1 : 1;
    const out = [];
    for (let i = 0; i < parts; i++) {
      const extra = left === 0 ? 0 : step;
      left -= extra;
      out.push(new Money(base + extra, this.currency));
    }
    return out;
  }

  allocate(ratios) {
    if (!ratios.length) throw new RangeError('need at least one ratio');
    const whole = ratios.reduce((a, b) => a + b, 0);
    let left = this.kobo;
    const shares = ratios.map((r) => {
      const share = Math.trunc((this.kobo * r) / whole);
      left -= share;
      return share;
    });
    for (let i = 0; left !== 0; i = (i + 1) % shares.length) {
      const step = left < 0 ? -1 : 1;
      shares[i] += step;
      left -= step;
    }
    return shares.map((k) => new Money(k, this.currency));
  }

  format() {
    const sign = this.kobo < 0 ? '-' : '';
    const size = Math.abs(this.kobo);
    const naira = String(Math.trunc(size / 100)).replace(/\B(?=([0-9]{3})+(?![0-9]))/g, ',');
    const kobo = String(size % 100).padStart(2, '0');
    return sign + SYMBOLS[this.currency] + naira + '.' + kobo;
  }

  toJSON() { return { kobo: this.kobo, currency: this.currency }; }
}

const errorOf = (fn) => { try { fn(); return 'no error'; } catch (err) { return err.name + ': ' + err.message; } };
const kobos = (list) => list.map((m) => m.kobo);
const sumOf = (list) => list.reduce((a, m) => a + m.kobo, 0);

const tenKobo = new Money(10);
const twentyKobo = new Money(20);
const floatVersus = [0.1 + 0.2 === 0.3, tenKobo.plus(twentyKobo).kobo];

let floatTotal = 0;
let koboTotal = new Money(0);
for (let i = 0; i < 10; i++) { floatTotal += 0.1; koboTotal = koboTotal.plus(tenKobo); }
const tenAdditions = [floatTotal === 1, koboTotal.kobo, koboTotal.format()];

const tenNaira = Money.fromNaira(10);
const threeWays = tenNaira.splitInto(3);
const splitStory = [kobos(threeWays), sumOf(threeWays), sumOf(threeWays) === tenNaira.kobo];

const refund = new Money(-1000);
const refundSplit = refund.splitInto(3);
const refundStory = [kobos(refundSplit), sumOf(refundSplit)];

// The property, over every amount and every number of parts in a range.
let nothingEverLost = true;
for (let amount = -37; amount <= 37; amount++) {
  for (let parts = 1; parts <= 7; parts++) {
    const pieces = new Money(amount).splitInto(parts);
    if (sumOf(pieces) !== amount) nothingEverLost = false;
    if (pieces.length !== parts) nothingEverLost = false;
  }
}

const rent = Money.fromNaira(1000);
const uneven = rent.allocate([3, 2, 1]);
const allocateStory = [kobos(uneven), sumOf(uneven) === rent.kobo];

const formatting = [
  Money.fromNaira(1234567.05).format(),
  new Money(-4550).format(),
  new Money(7).format(),
  new Money(0).format(),
  new Money(199, 'USD').format(),
];

const roundingTrap = [Math.round(-2.5), Math.round(2.5), roundHalfAway(-2.5), roundHalfAway(2.5)];
const vat = [new Money(45000).times(0.075).kobo, new Money(1).times(0.075).kobo, new Money(-45000).times(0.075).kobo];

const refusals = [
  errorOf(() => new Money(10.5)),
  errorOf(() => new Money(100).plus(new Money(100, 'USD'))),
  errorOf(() => new Money(100).splitInto(0)),
];
const frozen = errorOf(() => { tenKobo.kobo = 9999; });
const projected = [JSON.parse(JSON.stringify(new Money(45000))), Object.isFrozen(tenKobo)];

console.log('floats vs kobo :', floatVersus, tenAdditions);
console.log('split of 1000  :', splitStory);
console.log('allocate 3:2:1 :', allocateStory);
console.log('formatted      :', formatting.join('  '));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128const kindOf = (v) => (v === null ? 'null' : Array.isArray(v) ? 'array' : typeof v);
const pass = (value) => ({ ok: true, value });
const failAt = (path, message) => ({ ok: false, errors: [{ path, message }] });

const isString = () => (value, path) =>
  typeof value === 'string' ? pass(value) : failAt(path, 'expected a string, got ' + kindOf(value));
const isWholeNumber = () => (value, path) =>
  Number.isInteger(value) ? pass(value) : failAt(path, 'expected a whole number, got ' + kindOf(value));
const atLeast = (n) => (value, path) =>
  value >= n ? pass(value) : failAt(path, 'must be at least ' + n);
const longerThan = (n) => (value, path) =>
  value.length > n ? pass(value) : failAt(path, 'must be longer than ' + n + ' characters');
const oneOf = (allowed) => (value, path) =>
  allowed.indexOf(value) !== -1 ? pass(value) : failAt(path, 'must be one of ' + allowed.join(', '));

// Chaining STOPS at the first failure: later rules assume the earlier ones held.
const all = (...checks) => (value, path) => {
  let current = value;
  for (const check of checks) {
    const result = check(current, path);
    if (!result.ok) return result;
    current = result.value;
  }
  return pass(current);
};

const optional = (check) => (value, path) => (value === undefined ? pass(undefined) : check(value, path));

// Structures ACCUMULATE: every element is checked before anything is returned.
const arrayOf = (check) => (value, path) => {
  if (!Array.isArray(value)) return failAt(path, 'expected an array, got ' + kindOf(value));
  const out = [];
  const errors = [];
  value.forEach((item, index) => {
    const result = check(item, path + '[' + index + ']');
    if (result.ok) out.push(result.value);
    else for (const e of result.errors) errors.push(e);
  });
  return errors.length ? { ok: false, errors } : pass(out);
};

const shape = (fields, { allowUnknown = false } = {}) => (value, path) => {
  if (value === null || typeof value !== 'object' || Array.isArray(value)) {
    return failAt(path, 'expected an object, got ' + kindOf(value));
  }
  const out = {};
  const errors = [];
  for (const key of Object.keys(fields)) {
    const at = path ? path + '.' + key : key;
    const result = fields[key](value[key], at);
    if (!result.ok) { for (const e of result.errors) errors.push(e); continue; }
    if (result.value !== undefined) out[key] = result.value;
  }
  if (!allowUnknown) {
    for (const key of Object.keys(value)) {
      if (!Object.prototype.hasOwnProperty.call(fields, key)) {
        errors.push({ path: path ? path + '.' + key : key, message: 'unknown key' });
      }
    }
  }
  return errors.length ? { ok: false, errors } : pass(out);
};

const lineItem = shape({
  sku: all(isString(), longerThan(2)),
  kobo: all(isWholeNumber(), atLeast(1)),
});

const order = shape({
  till: all(isString(), longerThan(2)),
  currency: oneOf(['NGN', 'USD']),
  note: optional(all(isString(), longerThan(0))),
  items: arrayOf(lineItem),
});

const report = (result) => (result.ok ? 'ok' : result.errors.map((e) => e.path + ': ' + e.message));

const good = order({
  till: 'Balogun 1',
  currency: 'NGN',
  items: [{ sku: 'ADR-1', kobo: 450000 }, { sku: 'ADR-2', kobo: 125000 }],
}, '');
const goodStory = [good.ok, good.value, 'note' in good.value];

const messy = order({
  till: 'B',
  currency: 'GBP',
  items: [{ sku: 'ADR-1', kobo: 4.5 }, { kobo: 0 }, 'not an object'],
  discount: 500,
}, '');
const everyProblem = report(messy);

const chainStops = report(order({ till: 42, currency: 'NGN', items: [] }, ''));

const optionalStory = [
  report(order({ till: 'Ikeja 1', currency: 'NGN', note: 'rush', items: [] }, '')),
  report(order({ till: 'Ikeja 1', currency: 'NGN', note: '', items: [] }, '')),
  report(order({ till: 'Ikeja 1', currency: 'NGN', note: 7, items: [] }, '')),
];

const unknownKeys = [
  report(order({ till: 'Ikeja 1', currency: 'NGN', items: [], extra: 1 }, '')),
  report(shape({ till: isString() }, { allowUnknown: true })({ till: 'Ikeja 1', extra: 1 }, '')),
];

const notAnArray = report(order({ till: 'Ikeja 1', currency: 'NGN', items: { 0: 'x' } }, ''));
const nullVsMissing = [
  report(order({ till: null, currency: 'NGN', items: [] }, '')),
  report(order({ currency: 'NGN', items: [] }, '')),
];

// A new rule is just another function. Nothing above it changes.
const divisibleBy = (n) => (value, path) =>
  value % n === 0 ? pass(value) : failAt(path, 'must be a multiple of ' + n);
const roundKobo = shape({ kobo: all(isWholeNumber(), atLeast(1), divisibleBy(50)) });
const customRule = [report(roundKobo({ kobo: 450000 }, '')), report(roundKobo({ kobo: 12 }, ''))];

const deep = shape({ batches: arrayOf(shape({ items: arrayOf(lineItem) })) });
const deepReport = report(deep({
  batches: [
    { items: [{ sku: 'ADR-1', kobo: 100 }] },
    { items: [{ sku: 'ADR-2', kobo: 100 }, { sku: 'X', kobo: 100 }] },
  ],
}, ''));

console.log('good order   :', goodStory);
console.log('every problem:', everyProblem);
console.log('deep path    :', deepReport);