Repository: d3/d3-array
Pull request #237 (2021-10-02 04:43:12)

allow rank to take a comparator

Fil: I don't know if it helps, but the comparator is available in https://observablehq.com/@d3/rank-dev, as well as multiple accessors. 

mbostock: Thanks! I think it’s nice for d3.rank to be next to d3.quantile since it feels more closely related than d3.sort.

I don’t think I want to commit to multiple accessors at this point. We don’t do that for d3.bisector, for example, and at the least it’s always possible to express as an equivalent comparator now that comparators are supported.

Also, and I’m not sure whether to file a separate issue for this, but using function.length to differentiate an accessor from a comparator feels brittle in retrospect. For example, you’d hope that d3.sort(values, Math.random) would interpret Math.random as an accessor, but since Math.random’s function.length is zero it gets interpreted as a comparator. This confusion bubbles up to Plot e.g. https://github.com/observablehq/plot/pull/564. So, I’m tempted to assume an accessor if function.length !== 2 instead of if function.length === 1; but that change isn’t really backwards-compatible, so we’re a bit stuck.

Patch:
diff --git a/README.md b/README.md
index 244699a..af354e7 100644
--- a/README.md
+++ b/README.md
@@ -141,13 +141,15 @@ An optional *accessor* function may be specified, which is equivalent to calling
 
 Similar to *quantile*, but expects the input to be a **sorted** *array* of values. In contrast with *quantile*, the accessor is only called on the elements needed to compute the quantile.
 
-<a name="rank" href="#rank">#</a> d3.<b>rank</b>(<i>iterable</i>[, <i>accessor</i>]) · [Source](https://github.com/d3/d3-array/blob/main/src/rank.js), [Examples](https://observablehq.com/@d3/rank)
+<a name="rank" href="#rank">#</a> d3.<b>rank</b>(<i>iterable</i>[, <i>comparator</i>]) · [Source](https://github.com/d3/d3-array/blob/main/src/rank.js), [Examples](https://observablehq.com/@d3/rank)
+<br><a name="rank" href="#rank">#</a> d3.<b>rank</b>(<i>iterable</i>[, <i>accessor</i>])
 
-Returns an array with the rank of each value in the *iterable*, *i.e.* the index of the value when the iterable is sorted. Nullish values are sorted to the end and ranked NaN. An optional *accessor* function may be specified, which is equivalent to calling *array*.map(*accessor*) before computing the ranks. Ties (equivalent values) all get the same rank, defined as the first time the value is found.
+Returns an array with the rank of each value in the *iterable*, *i.e.* the zero-based index of the value when the iterable is sorted. Nullish values are sorted to the end and ranked NaN. An optional *comparator* or *accessor* function may be specified; the latter is equivalent to calling *array*.map(*accessor*) before computing the ranks. If *comparator* is not specified, it defaults to [ascending](#ascending). Ties (equivalent values) all get the same rank, defined as the first time the value is found.
 
 ```js
 d3.rank([{x: 1}, {}, {x: 2}, {x: 0}], d => d.x); // [1, NaN, 2, 0]
 d3.rank(["b", "c", "b", "a"]); // [1, 3, 1, 0]
+d3.rank([1, 2, 3], d3.descending); // [2, 1, 0]
 ```
 
 <a name="variance" href="#variance">#</a> d3.<b>variance</b>(<i>iterable</i>[, <i>accessor</i>]) · [Source](https://github.com/d3/d3-array/blob/main/src/variance.js), [Examples](https://observablehq.com/@d3/d3-mean-d3-median-and-friends)
diff --git a/src/rank.js b/src/rank.js
index 488f820..7c4ebc8 100644
--- a/src/rank.js
+++ b/src/rank.js
@@ -1,23 +1,24 @@
-import range from "./range.js";
-import sort from "./sort.js";
+import ascending from "./ascending.js";
+import {ascendingDefined, compareDefined} from "./sort.js";
 
-export default function rank(values, valueof) {
+export default function rank(values, valueof = ascending) {
   if (typeof values[Symbol.iterator] !== "function") throw new TypeError("values is not iterable");
-  values = Array.from(values, valueof);
-  const n = values.length;
-  const r = new Float64Array(n);
-  let last, l;
-  sort(range(n), (i) => values[i]).forEach((j, i) => {
-    const value = values[j];
-    if (value == null || !(value <= value)) {
-      r[j] = NaN;
-      return;
-    }
-    if (last === undefined || !(value <= last)) {
-      last = value;
-      l = i;
-    }
-    r[j] = l;
-  });
-  return r;
+  let V = Array.from(values);
+  const R = new Float64Array(V.length);
+  if (valueof.length === 1) V = V.map(valueof), valueof = ascending;
+  const compareIndex = (i, j) => valueof(V[i], V[j]);
+  let k, r;
+  Uint32Array
+    .from(V, (_, i) => i)
+    .sort(valueof === ascending ? (i, j) => ascendingDefined(V[i], V[j]) : compareDefined(compareIndex))
+    .forEach((j, i) => {
+      const c = compareIndex(j, k === undefined ? j : k);
+      if (c >= 0) {
+        if (k === undefined || c > 0) k = j, r = i;
+        R[j] = r;
+      } else {
+        R[j] = NaN;
+      }
+    });
+  return R;
 }


Test patch:
diff --git a/test/rank-test.js b/test/rank-test.js
index 00b5914..9e2d4c4 100644
--- a/test/rank-test.js
+++ b/test/rank-test.js
@@ -1,4 +1,6 @@
 import assert from "assert";
+import ascending from "../src/ascending.js";
+import descending from "../src/descending.js";
 import rank from "../src/rank.js";
 
 it("rank(numbers) returns the rank of numbers", () => {
@@ -28,12 +30,19 @@ it("rank(values, valueof) accepts an accessor", () => {
   assert.deepStrictEqual(rank([{x: 3}, {x: 1}, {x: 2}, {x: 4}, {}], d => d.x), Float64Array.of(2, 0, 1, 3, NaN));
 });
 
-it("rank(values, ties) computes the ties as expected", () => {
+it("rank(values, compare) accepts a comparator", () => {
+  assert.deepStrictEqual(rank([{x: 3}, {x: 1}, {x: 2}, {x: 4}, {}], (a, b) => a.x - b.x), Float64Array.of(2, 0, 1, 3, NaN));
+  assert.deepStrictEqual(rank([{x: 3}, {x: 1}, {x: 2}, {x: 4}, {}], (a, b) => b.x - a.x), Float64Array.of(1, 3, 2, 0, NaN));
+  assert.deepStrictEqual(rank(["aa", "ba", "bc", "bb", "ca"], (a, b) => ascending(a[0], b[0]) || ascending(a[1], b[1])), Float64Array.of(0, 1, 3, 2, 4));
+  assert.deepStrictEqual(rank(["A", null, "B", "C", "D"], descending), Float64Array.of(3, NaN, 2, 1, 0));
+});
+
+it("rank(values) computes the ties as expected", () => {
   assert.deepStrictEqual(rank(["a", "b", "b", "b", "c"]), Float64Array.of(0, 1, 1, 1, 4));
   assert.deepStrictEqual(rank(["a", "b", "b", "b", "b", "c"]), Float64Array.of(0, 1, 1, 1, 1, 5));
 });
 
-it("rank(values, ties) handles NaNs as expected", () => {
+it("rank(values) handles NaNs as expected", () => {
   assert.deepStrictEqual(rank(["a", "b", "b", "b", "c", null]), Float64Array.of(0, 1, 1, 1, 4, NaN));
   assert.deepStrictEqual(rank(["a", "b", "b", "b", "b", "c", null]), Float64Array.of(0, 1, 1, 1, 1, 5, NaN));
 });