content: generateDividedTrackList: context groups

4 files changed, 178 insertions, 74 deletions

diff --git a/src/common-util/sugar.js b/src/common-util/sugar.js
index c988156c..26f33c20 100644
--- a/src/common-util/sugar.js
+++ b/src/common-util/sugar.js
@@ -229,6 +229,38 @@ export const mapInPlace = (array, fn) =>
 
 export const unique = (arr) => Array.from(new Set(arr));
 
+export function* permutations(array) {
+  switch (array.length) {
+    case 0: return;
+    case 1: yield array; return;
+    default: {
+      const behind = [];
+      const ahead = array.slice();
+      while (ahead.length) {
+        const here = ahead.shift();
+
+        yield*
+          permutations([...behind, ...ahead])
+            .map(slice => [here, ...slice]);
+
+        behind.push(here);
+      }
+    }
+  }
+}
+
+export function* runs(array) {
+  switch (array.length) {
+    case 0: return;
+    case 1: yield array; return;
+    default: {
+      yield* runs(array.slice(1)).map(run => [array[0], ...run]);
+      yield [array[0]];
+      yield* runs(array.slice(1));
+    }
+  }
+}
+
 export const compareArrays = (arr1, arr2, {checkOrder = true} = {}) =>
   arr1.length === arr2.length &&
   (checkOrder
diff --git a/src/common-util/wiki-data.js b/src/common-util/wiki-data.js
index 74222e9e..21e15725 100644
--- a/src/common-util/wiki-data.js
+++ b/src/common-util/wiki-data.js
@@ -506,8 +506,23 @@ export class TupleMap {
 }
 
 export class TupleMapForBabies {
-  #here = new WeakMap();
-  #next = new WeakMap();
+  #here;
+  #next;
+  #mode;
+
+  constructor(mode = 'weak') {
+    if (mode === 'weak') {
+      this.#mode = 'weak';
+      this.#here = new WeakMap();
+      this.#next = new WeakMap();
+    } else if (mode === 'strong') {
+      this.#mode = 'strong';
+      this.#here = new Map();
+      this.#next = new Map();
+    } else {
+      throw new Error(`Expected mode to be weak or strong`);
+    }
+  }
 
   set(...args) {
     const first = args.at(0);
@@ -519,7 +534,7 @@ export class TupleMapForBabies {
     } else if (this.#next.has(first)) {
       this.#next.get(first).set(...rest, last);
     } else {
-      const tupleMap = new TupleMapForBabies();
+      const tupleMap = new TupleMapForBabies(this.#mode);
       this.#next.set(first, tupleMap);
       tupleMap.set(...rest, last);
     }
@@ -550,6 +565,36 @@ export class TupleMapForBabies {
       return false;
     }
   }
+
+  *keys() {
+    if (this.#mode === 'weak') {
+      throw new Error(`Can't get keys of a weak tuple map`);
+    }
+
+    for (const key of this.#here.keys()) {
+      yield [key];
+
+      if (this.#next.has(key)) {
+        for (const next of this.#next.get(key).keys()) {
+          yield [key, ...next];
+        }
+      }
+    }
+  }
+
+  *values() {
+    if (this.#mode === 'weak') {
+      throw new Error(`Can't get values of a weak tuple map`);
+    }
+
+    for (const key of this.#here.keys()) {
+      yield this.#here.get(key);
+
+      if (this.#next.has(key)) {
+        yield* this.#next.get(key).values();
+      }
+    }
+  }
 }
 
 const combinedWikiDataTupleMap = new TupleMapForBabies();
diff --git a/src/content/dependencies/generateDividedTrackList.js b/src/content/dependencies/generateDividedTrackList.js
index ea349ec8..584eb920 100644
--- a/src/content/dependencies/generateDividedTrackList.js
+++ b/src/content/dependencies/generateDividedTrackList.js
@@ -1,4 +1,5 @@
-import {empty, filterMultipleArrays, stitchArrays} from '#sugar';
+import {empty, filterMultipleArrays, runs, stitchArrays, unique} from '#sugar';
+import {TupleMapForBabies} from '#wiki-data';
 
 export default {
   sprawl: ({wikiInfo}) => ({
@@ -6,40 +7,81 @@ export default {
       wikiInfo.divideTrackListsByGroups,
   }),
 
-  query(sprawl, tracks, _contextTrack) {
-    const dividingGroups = sprawl.divideTrackListsByGroups;
+  query(sprawl, tracks, contextTrack) {
+    const wikiDividingGroups = sprawl.divideTrackListsByGroups;
 
-    const groupings = new Map();
+    const contextDividingGroups =
+      contextTrack.groups
+        .filter(group => !wikiDividingGroups.includes(group));
+
+    const contextGroupRuns =
+      Array.from(runs(contextDividingGroups));
+
+    const groupings = new TupleMapForBabies('strong');
     const ungroupedTracks = [];
 
-    // Entry order matters! Add blank lists for each group
-    // in the order that those groups are provided.
-    for (const group of dividingGroups) {
-      groupings.set(group, []);
-    }
+    const order = [
+      ...contextGroupRuns,
+      ...wikiDividingGroups.map(group => [group]),
+    ];
 
     for (const track of tracks) {
-      const firstMatchingGroup =
-        dividingGroups.find(group => group.albums.includes(track.album));
+      let run;
+      getRun: {
+        run =
+          contextDividingGroups
+            .filter(group => track.groups.includes(group));
+
+        if (!empty(run)) {
+          break getRun;
+        }
+
+        const wikiGroup =
+          wikiDividingGroups.find(group => track.groups.includes(group));
+
+        if (wikiGroup) {
+          run = [wikiGroup];
+          break getRun;
+        }
 
-      if (firstMatchingGroup) {
-        groupings.get(firstMatchingGroup).push(track);
-      } else {
         ungroupedTracks.push(track);
+        continue;
+      }
+
+      if (groupings.has(...run)) {
+        groupings.get(...run).push(track);
+      } else {
+        groupings.set(...run, [track]);
       }
     }
 
-    const groups = Array.from(groupings.keys());
-    const groupedTracks = Array.from(groupings.values());
+    let groupingGroups = order.slice();
+    const groupedTracks = order.map(run => groupings.get(...run) ?? []);
 
-    // Drop the empty lists, so just the groups which
-    // at least a single track matched are left.
     filterMultipleArrays(
-      groups,
+      groupingGroups,
       groupedTracks,
-      (_group, tracks) => !empty(tracks));
-
-    return {groups, groupedTracks, ungroupedTracks};
+      (_groups, tracks) => !empty(tracks));
+
+    const presentContextDividingGroups =
+      unique(groupingGroups.flat())
+        .filter(group => contextDividingGroups.includes(group));
+
+    const uninformativeGroups =
+      presentContextDividingGroups.filter((group, index) =>
+        presentContextDividingGroups
+          .slice(0, index)
+          .some(earlier =>
+            groupingGroups.every(run =>
+              run.includes(earlier) && run.includes(group) ||
+             !run.includes(earlier) && !run.includes(group))));
+
+    groupingGroups =
+      groupingGroups.map(groups =>
+        groups.filter(group =>
+          !uninformativeGroups.includes(group)));
+
+    return {groupingGroups, groupedTracks, ungroupedTracks};
   },
 
   relations: (relation, query, sprawl, tracks, contextTrack) => ({
@@ -52,8 +94,9 @@ export default {
       relation('generateContentHeading'),
 
     groupLinks:
-      query.groups
-        .map(group => relation('linkGroup', group)),
+      query.groupingGroups
+        .map(groups => groups
+          .map(group => relation('linkGroup', group))),
 
     groupedTrackLists:
       query.groupedTracks
@@ -67,8 +110,9 @@ export default {
 
   data: (query, _sprawl, _tracks) => ({
     groupNames:
-      query.groups
-        .map(group => group.name),
+      query.groupingGroups
+        .map(groups => groups
+          .map(group => group.name)),
   }),
 
   slots: {
@@ -85,33 +129,36 @@ export default {
 
       language.encapsulate('trackList', listCapsule => [
         stitchArrays({
-          groupName: data.groupNames,
-          groupLink: relations.groupLinks,
+          groupNames: data.groupNames,
+          groupLinks: relations.groupLinks,
           trackList: relations.groupedTrackLists,
         }).map(({
-            groupName,
-            groupLink,
+            groupNames,
+            groupLinks,
             trackList,
           }) => [
-            language.encapsulate(listCapsule, 'fromGroup', capsule =>
-              (slots.headingString
-                ? relations.contentHeading.clone().slots({
-                    tag: 'dt',
-
-                    title:
-                      language.$(capsule, {
-                        group: groupLink.slot('color', false),
-                      }),
-
-                    stickyTitle:
-                      language.$(slots.headingString, 'sticky', 'fromGroup', {
-                        group: groupName,
-                      }),
-                  })
-                : html.tag('dt',
-                    language.$(capsule, {
-                      group: groupLink.slot('color', false),
-                    })))),
+            language.encapsulate(listCapsule, 'fromGroup', capsule => {
+              const title =
+                language.$(capsule, {
+                  group:
+                    language.formatConjunctionList(
+                      groupLinks.map(link => link.slot('color', false))),
+                });
+
+              if (slots.headingString) {
+                return relations.contentHeading.clone().slots({
+                  tag: 'dt',
+                  title,
+                  stickyTitle:
+                    language.$(slots.headingString, 'sticky', 'fromGroup', {
+                      group:
+                        language.formatConjunctionList(groupNames),
+                    }),
+                });
+              } else {
+                return html.tag('dt', title);
+              }
+            }),
 
             html.tag('dd', trackList),
           ]),
diff --git a/src/static/js/search-worker.js b/src/static/js/search-worker.js
index b79df3d4..9ccaa95d 100644
--- a/src/static/js/search-worker.js
+++ b/src/static/js/search-worker.js
@@ -6,6 +6,7 @@ import {default as searchSpec, makeSearchIndex}
 import {
   empty,
   groupArray,
+  permutations,
   promiseWithResolvers,
   stitchArrays,
   unique,
@@ -542,7 +543,7 @@ function queryIndex({termsKey, indexKey}, query, options) {
 
   const queriesBy = keys =>
     (groupedParticles.get(keys.length) ?? [])
-      .flatMap(permutations)
+      .flatMap(particles => Array.from(permutations(particles)))
       .map(values => values.map(({terms}) => terms.join(' ')))
       .map(values =>
         stitchArrays({
@@ -692,27 +693,6 @@ function particulate(terms) {
   return results;
 }
 
-// This function doesn't even come close to "performant",
-// but it only operates on small data here.
-function permutations(array) {
-  switch (array.length) {
-    case 0:
-      return [];
-
-    case 1:
-      return [array];
-
-    default:
-      return array.flatMap((item, index) => {
-        const behind = array.slice(0, index);
-        const ahead = array.slice(index + 1);
-        return (
-          permutations([...behind, ...ahead])
-            .map(rest => [item, ...rest]));
-      });
-  }
-}
-
 function queryBoilerplate(index) {
   const idToDoc = {};