Topk-fold

#!/usr/bin/env node
/**
 * topk-fold — fold a JSONL numeric stream into its TOP-K values, one pass.
 *
 * WHAT
 *   Reads a stream of numbers — one JSON number per line (JSON Lines) — and folds
 *   them in ONE PASS into a single aggregate record:
 *       { count, k, top }
 *   `top` is the k LARGEST values seen, sorted DESCENDING (largest first). With
 *   --min it is the k SMALLEST, sorted ASCENDING (smallest first). `count` is the
 *   total number of values read; `k` is the requested size. If fewer than k values
 *   are seen, `top` holds all of them (still sorted) and count < k.
 *
 * HOW
 *   A BOUNDED HEAP of size k. For top-k a MIN-heap: push each value, and whenever
 *   the heap holds more than k, pop the SMALLEST — so the heap always retains the k
 *   largest seen. (For --min the mirror: a MAX-heap that pops the largest, retaining
 *   the k smallest.) One pass, O(n log k) time and O(k) space — it never holds the
 *   whole stream. At the end the heap is drained and sorted for output.
 *
 *   DETERMINISM (stronger than a float summary like running-stats): the emitted
 *   record is sorted, and numbers are indistinguishable under ties, so the SAME
 *   values in ANY order fold to a BYTE-IDENTICAL record. topk-fold is a partial
 *   order-statistic — the k largest are a fact about the multiset, not the arrival
 *   order. Pure: no clock, no randomness, no files written.
 *
 * USAGE
 *   node topk-fold.js --k N [--min] [FILE]        # stdin if no FILE
 *   printf '%s\n' 5 1 9 3 7 2 | node topk-fold.js --k 3
 *     -> {"count":6,"k":3,"top":[9,7,5]}
 *   printf '%s\n' 5 1 9 3 7 2 | node topk-fold.js --k 3 --min
 *     -> {"count":6,"k":3,"top":[1,2,3]}
 *   --k N   REQUIRED; the number of extreme values to keep (integer >= 1)
 *   --min   keep the k SMALLEST (bottom-k) instead of the k largest
 *   --help
 *
 * EXIT CODES
 *   0  success
 *   2  input error: missing/invalid --k (absent, non-integer, < 1); missing file /
 *      a directory; a line that is not a finite JSON number (incl. a value that
 *      overflows to +/-Infinity, e.g. 1e999) or NaN. Always a clean one-line message
 *      on stderr, never a stack trace.
 *
 * EDGE (what this is NOT)
 *   NOT a sort of the whole stream (keeps only k, in O(k) space), NOT a median or
 *   percentile (keeps no interior order statistics), and NOT a histogram or a
 *   running mean (see histogram-fold / running-stats). Ties at the k-th boundary
 *   are resolved BY VALUE: with duplicates, the k slots are filled by value, so
 *   [5,3,3,3] top-2 is [5,3] — the record is a multiset of values, never tagged by
 *   which arrival a tied value came from.
 *
 * Zero dependencies. Node builtin `require('fs')` for file reads only; runs in a
 * browser with no require (attaches `topkFold` to window.ForestGifts). MIT.
 */
"use strict";

/* ---- a bounded binary heap over numbers (min or max by `keepLargest`) ------
 * For top-k we keep the k LARGEST, so we evict the SMALLEST -> a MIN-heap.
 * For bottom-k (--min) we keep the k SMALLEST, so we evict the LARGEST -> a MAX-heap.
 * `worseThan(a,b)` is true when a should sit ABOVE b at the root (i.e. a is the one
 * we would evict): for a min-heap the smaller value is at the root; for a max-heap
 * the larger value is at the root. */
function BoundedHeap(k, keepLargest) {
  this.k = k;
  this.keepLargest = keepLargest;
  this.a = [];
}
// root should hold the eviction candidate: min-heap when keepLargest (evict smallest),
// max-heap when !keepLargest (evict largest).
BoundedHeap.prototype._rootFirst = function (x, y) {
  return this.keepLargest ? x < y : x > y;
};
BoundedHeap.prototype._swap = function (i, j) {
  var t = this.a[i]; this.a[i] = this.a[j]; this.a[j] = t;
};
BoundedHeap.prototype._up = function (i) {
  while (i > 0) {
    var p = (i - 1) >> 1;
    if (this._rootFirst(this.a[i], this.a[p])) { this._swap(i, p); i = p; } else break;
  }
};
BoundedHeap.prototype._down = function (i) {
  var n = this.a.length;
  for (;;) {
    var l = 2 * i + 1, r = 2 * i + 2, best = i;
    if (l < n && this._rootFirst(this.a[l], this.a[best])) best = l;
    if (r < n && this._rootFirst(this.a[r], this.a[best])) best = r;
    if (best === i) break;
    this._swap(i, best); i = best;
  }
};
BoundedHeap.prototype.offer = function (v) {
  this.a.push(v);
  this._up(this.a.length - 1);
  if (this.a.length > this.k) {
    // evict the root (the eviction candidate), keeping the desired k
    this.a[0] = this.a[this.a.length - 1];
    this.a.pop();
    if (this.a.length) this._down(0);
  }
};

/**
 * Fold a JSONL numeric stream into a top-k record.
 * @param {string} text  the whole input (newline-separated JSON numbers)
 * @param {{k:number, min?:boolean}} opts  k (integer >= 1); min => bottom-k
 * @returns {{count:number, k:number, top:number[]}}
 * @throws {Error} on an invalid k or a non-finite / non-number line.
 */
function fold(text, opts) {
  opts = opts || {};
  var k = opts.k;
  if (typeof k !== "number" || !isFinite(k) || Math.floor(k) !== k || k < 1) {
    throw new Error("k must be an integer >= 1 (got " + k + ")");
  }
  var keepLargest = !opts.min; // default top-k keeps largest; --min keeps smallest
  var heap = new BoundedHeap(k, keepLargest);
  var count = 0;

  var lines = String(text).split("\n");
  for (var i = 0; i < lines.length; i++) {
    var raw = lines[i];
    if (raw.charCodeAt(raw.length - 1) === 13) raw = raw.slice(0, -1); // trim trailing \r
    if (raw.length === 0) continue; // blank line: skipped, not a value
    var v;
    try {
      v = JSON.parse(raw);
    } catch (e) {
      throw new Error("line " + (i + 1) + ": not valid JSON: " + raw);
    }
    if (typeof v !== "number") {
      throw new Error("line " + (i + 1) + ": not a number: " + raw);
    }
    if (!isFinite(v)) {
      throw new Error("line " + (i + 1) + ": not a finite number: " + raw);
    }
    count += 1;
    heap.offer(v);
  }

  // Drain and sort for a deterministic, order-independent output:
  //   top-k    -> descending (largest first)
  //   bottom-k -> ascending  (smallest first)
  var top = heap.a.slice();
  if (keepLargest) top.sort(function (a, b) { return b - a; });
  else top.sort(function (a, b) { return a - b; });

  return { count: count, k: k, top: top };
}

/* ------------------------------------------------------------------ exports */
if (typeof module !== "undefined" && module.exports) {
  module.exports = { fold: fold };
}
if (typeof window !== "undefined") {
  window.ForestGifts = window.ForestGifts || {};
  window.ForestGifts.topkFold = fold;
}

/* ----------------------------------------------------------------- CLI main */
function main(argv) {
  var args = argv.slice(2);
  var k = null;
  var min = false;
  var file = null;
  for (var i = 0; i < args.length; i++) {
    var a = args[i];
    if (a === "--help" || a === "-h") {
      process.stdout.write(
        "usage: topk-fold.js --k N [--min] [FILE]\n" +
          "  --k N       REQUIRED; number of extreme values to keep (integer >= 1)\n" +
          "  --min       keep the k SMALLEST (bottom-k) instead of the k largest\n" +
          "  (no FILE)   read numbers from stdin\n" +
          "  FILE        read numbers from a file\n" +
          "  --help\n" +
          "Each non-blank line is one finite JSON number. Output is one line of compact JSON:\n" +
          '  {"count":N,"k":K,"top":[..]}   (top sorted largest-first, or smallest-first with --min)\n'
      );
      process.exit(0);
    } else if (a === "--min") {
      min = true;
    } else if (a === "--k") {
      var next = args[i + 1];
      if (next === undefined) { process.stderr.write("topk-fold: --k requires a value\n"); process.exit(2); }
      k = Number(next);
      i += 1;
    } else if (a.indexOf("--k=") === 0) {
      k = Number(a.slice(4));
    } else if (a.charAt(0) === "-" && a !== "-") {
      process.stderr.write("topk-fold: unknown option: " + a + "\n");
      process.exit(2);
    } else {
      if (file !== null) { process.stderr.write("topk-fold: more than one FILE given\n"); process.exit(2); }
      file = a;
    }
  }
  if (k === null) { process.stderr.write("topk-fold: --k N is required (integer >= 1)\n"); process.exit(2); }

  function run(text) {
    var rec;
    try {
      rec = fold(text, { k: k, min: min });
    } catch (e) {
      process.stderr.write("topk-fold: " + e.message + "\n");
      process.exit(2);
      return;
    }
    process.stdout.write(JSON.stringify(rec) + "\n");
  }

  if (file === null || file === "-") {
    var chunks = [];
    process.stdin.on("data", function (c) { chunks.push(c); });
    process.stdin.on("end", function () { run(Buffer.concat(chunks).toString("utf8")); });
  } else {
    var fs = require("fs");
    var text;
    try {
      var st = fs.statSync(file);
      if (st.isDirectory()) { process.stderr.write("topk-fold: is a directory: " + file + "\n"); process.exit(2); return; }
      text = fs.readFileSync(file, "utf8");
    } catch (e) {
      process.stderr.write("topk-fold: cannot read file: " + file + "\n");
      process.exit(2);
      return;
    }
    run(text);
  }
}

if (typeof require !== "undefined" && require.main === module) {
  main(process.argv);
}

#!/usr/bin/env node
/* test_topk-fold.js — external battery for the topk-fold gift.
 *
 *   node test_topk-fold.js   ->  exit 0 GREEN / non-zero RED
 *
 * Proves the gift against an INDEPENDENT full-sort-then-slice oracle (a genuinely
 * different method than the gift's one-pass bounded heap), plus frozen hand goldens,
 * BYTE-IDENTICAL order-independence (the record is a fact about the multiset, not the
 * arrival order), ties at the k-th boundary, k > n, --min (bottom-k), determinism,
 * numeric-honesty hard errors, and invalid-k guards.
 */
"use strict";
var assert = require("assert");
var fold = require("./topk-fold.js").fold;

var pass = 0, fail = 0;
function ok(name, cond) {
  try { assert.ok(cond, name); pass++; }
  catch (e) { fail++; console.error("  RED  " + name); }
}
function throws(name, fn) {
  try { fn(); fail++; console.error("  RED  " + name + " (did not throw)"); }
  catch (e) { pass++; }
}
function J(v) { return JSON.stringify(v); }
function jsonl(arr) { return arr.map(String).join("\n"); }

/* ---- independent oracle: sort the whole stream, slice k (a different method) -- */
function oracle(vals, k, min) {
  var s = vals.slice().sort(function (a, b) { return min ? a - b : b - a; });
  return { count: vals.length, k: k, top: s.slice(0, k) };
}
function giftRec(vals, k, min) { return fold(jsonl(vals), { k: k, min: min }); }

/* ---- frozen hand goldens --------------------------------------------------- */
ok("golden top-3 of [5,1,9,3,7,2] == [9,7,5]",
  J(giftRec([5, 1, 9, 3, 7, 2], 3, false)) === J({ count: 6, k: 3, top: [9, 7, 5] }));
ok("golden bottom-3 (--min) of [5,1,9,3,7,2] == [1,2,3]",
  J(giftRec([5, 1, 9, 3, 7, 2], 3, true)) === J({ count: 6, k: 3, top: [1, 2, 3] }));
ok("golden top-1 of [5,1,9,3,7,2] == [9]",
  J(giftRec([5, 1, 9, 3, 7, 2], 1, false).top) === J([9]));
ok("golden min-1 of [5,1,9,3,7,2] == [1]",
  J(giftRec([5, 1, 9, 3, 7, 2], 1, true).top) === J([1]));

/* ---- agreement with the independent full-sort oracle ----------------------- */
var vectors = [
  [5, 1, 9, 3, 7, 2],
  [-3, -1, 0, 2, 4],
  [10, 20, 30, 40, 50, 60],
  [42],
  [1.5, 2.5, 0.5, 3.5],
  [7, 7, 7, 7],
  [100, -100, 0]
];
[1, 2, 3].forEach(function (k) {
  vectors.forEach(function (v) {
    ok("top-" + k + " == oracle " + J(v), J(giftRec(v, k, false)) === J(oracle(v, k, false)));
    ok("min-" + k + " == oracle " + J(v), J(giftRec(v, k, true)) === J(oracle(v, k, true)));
  });
});

/* ---- k > n : all values, still sorted -------------------------------------- */
ok("k>n top: k=10 of [3,1,2] == [3,2,1], count 3",
  J(giftRec([3, 1, 2], 10, false)) === J({ count: 3, k: 10, top: [3, 2, 1] }));
ok("k>n min: k=10 of [3,1,2] == [1,2,3], count 3",
  J(giftRec([3, 1, 2], 10, true)) === J({ count: 3, k: 10, top: [1, 2, 3] }));

/* ---- count is n even when k < n -------------------------------------------- */
ok("count == n even when k<n", giftRec([9, 8, 7, 6, 5], 2, false).count === 5);

/* ---- ties at the k-th boundary (resolved by value) ------------------------- */
ok("ties: top-2 of [5,3,3,3] == [5,3]", J(giftRec([5, 3, 3, 3], 2, false).top) === J([5, 3]));
ok("ties: top-2 of [5,5,5,1] == [5,5]", J(giftRec([5, 5, 5, 1], 2, false).top) === J([5, 5]));
ok("ties: min-2 of [1,1,1,9] == [1,1]", J(giftRec([1, 1, 1, 9], 2, true).top) === J([1, 1]));

/* ---- BYTE-IDENTICAL order-independence (stronger than a float summary) ------ */
var base = [5, 1, 9, 3, 7, 2, 8, 4, 6, 0];
var shuffled = [8, 0, 5, 9, 1, 6, 3, 2, 7, 4];
var reversed = base.slice().reverse();
ok("order-independent: shuffled == base (byte-identical)",
  J(giftRec(base, 4, false)) === J(giftRec(shuffled, 4, false)));
ok("order-independent: reversed == base (byte-identical)",
  J(giftRec(base, 4, false)) === J(giftRec(reversed, 4, false)));
ok("order-independent --min: shuffled == base (byte-identical)",
  J(giftRec(base, 4, true)) === J(giftRec(shuffled, 4, true)));

/* ---- determinism: folds twice identical ------------------------------------ */
ok("folds twice identical", J(giftRec(base, 5, false)) === J(giftRec(base, 5, false)));

/* ---- empty stream ---------------------------------------------------------- */
ok("empty stream -> {count:0,k:3,top:[]}",
  J(fold("", { k: 3 })) === J({ count: 0, k: 3, top: [] }));

/* ---- blank lines skipped, CRLF trimmed ------------------------------------- */
ok("blank lines skipped", J(fold("5\n\n1\n\n9\n", { k: 2 }).top) === J([9, 5]));
ok("CRLF trimmed", J(fold("5\r\n1\r\n9\r\n", { k: 2 }).top) === J([9, 5]));

/* ---- numeric honesty: hard errors ------------------------------------------ */
throws("NaN -> throw", function () { fold("1\nNaN\n2", { k: 2 }); });
throws("1e999 (Infinity) -> throw", function () { fold("1\n1e999\n2", { k: 2 }); });
throws("string -> throw", function () { fold('1\n"x"\n2', { k: 2 }); });
throws("bad JSON -> throw", function () { fold("1\nabc\n2", { k: 2 }); });

/* ---- invalid k guards ------------------------------------------------------ */
throws("k=0 -> throw", function () { fold("1\n2\n3", { k: 0 }); });
throws("k=-1 -> throw", function () { fold("1\n2\n3", { k: -1 }); });
throws("k=1.5 -> throw", function () { fold("1\n2\n3", { k: 1.5 }); });
throws("k absent -> throw", function () { fold("1\n2\n3", {}); });

/* ---- negatives + mixed correctness ----------------------------------------- */
ok("negatives top-2 of [-5,-1,-9,-3] == [-1,-3]", J(giftRec([-5, -1, -9, -3], 2, false).top) === J([-1, -3]));
ok("negatives min-2 of [-5,-1,-9,-3] == [-9,-5]", J(giftRec([-5, -1, -9, -3], 2, true).top) === J([-9, -5]));

console.log((fail === 0 ? "GREEN" : "RED") + ": " + pass + " assertions passed, " + fail + " failed  [test_topk-fold]");
process.exit(fail === 0 ? 0 : 1);