import fs from 'node:fs';
import path from 'node:path';
import process from 'node:process';
import { fileURLToPath } from 'node:url';

const here = path.dirname(fileURLToPath(import.meta.url));
const htmlPath = path.resolve(here, '../../public/strata/finite-simple-groups/index.html');

function fail(message) {
  console.error(`FAIL: ${message}`);
  process.exit(1);
}

function assert(condition, message) {
  if (!condition) fail(message);
}

function equal(actual, expected, label) {
  if (actual !== expected) fail(`${label}: expected ${expected}, got ${actual}`);
}

function includes(haystack, needle, label) {
  if (!haystack.includes(needle)) fail(`${label}: missing ${JSON.stringify(needle)}`);
}

function jsonBlock(html, id) {
  const match = html.match(new RegExp(`<script[^>]+id="${id}"[^>]*>([\\s\\S]*?)<\\/script>`));
  if (!match) fail(`missing JSON block #${id}`);
  try {
    return JSON.parse(match[1]);
  } catch (error) {
    fail(`invalid JSON in #${id}: ${error.message}`);
  }
}

function permutationsHeap(n) {
  const a = Array.from({ length: n }, (_, i) => i);
  const counters = Array(n).fill(0);
  const out = [a.slice()];
  let i = 0;
  while (i < n) {
    if (counters[i] < i) {
      const j = i % 2 === 0 ? 0 : counters[i];
      [a[j], a[i]] = [a[i], a[j]];
      out.push(a.slice());
      counters[i] += 1;
      i = 0;
    } else {
      counters[i] = 0;
      i += 1;
    }
  }
  return out;
}

function permKey(p) {
  return p.join('');
}

function parity(p) {
  let inversions = 0;
  for (let i = 0; i < p.length; i += 1) {
    for (let j = i + 1; j < p.length; j += 1) {
      if (p[i] > p[j]) inversions += 1;
    }
  }
  return inversions % 2;
}

function multiply(a, b) {
  return b.map((image) => a[image]);
}

function inverse(p) {
  const out = Array(p.length);
  p.forEach((image, source) => {
    out[image] = source;
  });
  return out;
}

function permutationOrder(p) {
  let current = Array.from({ length: p.length }, (_, i) => i);
  for (let power = 1; power <= 24; power += 1) {
    current = multiply(current, p);
    if (permKey(current) === Array.from({ length: p.length }, (_, i) => i).join('')) {
      return power;
    }
  }
  fail(`could not find order of ${permKey(p)}`);
}

function indexGroup(elements) {
  const map = new Map(elements.map((p, i) => [permKey(p), i]));
  const identity = map.get(Array.from({ length: elements[0].length }, (_, i) => i).join(''));
  assert(identity !== undefined, 'identity is absent');
  return { elements, map, identity };
}

function subgroupGenerated(group, seedIndices) {
  const generators = new Set(seedIndices);
  for (const index of seedIndices) {
    const inv = group.map.get(permKey(inverse(group.elements[index])));
    assert(inv !== undefined, 'generator inverse is absent from ambient group');
    generators.add(inv);
  }
  const seen = new Set([group.identity]);
  const queue = [group.identity];
  while (queue.length) {
    const h = queue.shift();
    for (const generator of generators) {
      const product = group.map.get(
        permKey(multiply(group.elements[h], group.elements[generator]))
      );
      assert(product !== undefined, 'generated product left ambient group');
      if (!seen.has(product)) {
        seen.add(product);
        queue.push(product);
      }
    }
  }
  return [...seen].sort((a, b) => a - b);
}

function normalClosure(group, seedIndex) {
  const seed = group.elements[seedIndex];
  const conjugates = group.elements.map((g) => {
    const conjugate = multiply(multiply(g, seed), inverse(g));
    const index = group.map.get(permKey(conjugate));
    assert(index !== undefined, 'conjugate left ambient group');
    return index;
  });
  return subgroupGenerated(group, conjugates);
}

function verifyGroup(group, label) {
  const n = group.elements.length;
  const idKey = permKey(group.elements[group.identity]);
  for (let i = 0; i < n; i += 1) {
    const element = group.elements[i];
    const inv = inverse(element);
    assert(group.map.has(permKey(inv)), `${label}: inverse missing`);
    equal(permKey(multiply(element, inv)), idKey, `${label}: right inverse`);
    equal(permKey(multiply(inv, element)), idKey, `${label}: left inverse`);
    for (let j = 0; j < n; j += 1) {
      const product = multiply(element, group.elements[j]);
      assert(group.map.has(permKey(product)), `${label}: closure failed`);
    }
  }
  for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < n; j += 1) {
      for (let k = 0; k < n; k += 1) {
        const left = multiply(multiply(group.elements[i], group.elements[j]), group.elements[k]);
        const right = multiply(group.elements[i], multiply(group.elements[j], group.elements[k]));
        equal(permKey(left), permKey(right), `${label}: associativity failed`);
      }
    }
  }
}

function subsetKey(indices) {
  return indices.slice().sort((a, b) => a - b).join(',');
}

function enumerateSubgroups(group, ambientIndices) {
  const ambientSet = new Set(ambientIndices);
  const identity = group.identity;
  assert(ambientSet.has(identity), 'subgroup ambient set lacks identity');
  const local = {
    elements: ambientIndices.map((i) => group.elements[i]),
    map: new Map(ambientIndices.map((i, localIndex) => [permKey(group.elements[i]), localIndex])),
    identity: ambientIndices.indexOf(identity)
  };
  const localToGlobal = ambientIndices.slice();
  const known = new Map();
  const trivial = [identity];
  known.set(subsetKey(trivial), trivial);
  const queue = [trivial];
  while (queue.length) {
    const current = queue.shift();
    for (const candidate of ambientIndices) {
      if (current.includes(candidate)) continue;
      const seeds = current.concat(candidate).map((globalIndex) => {
        const localIndex = local.map.get(permKey(group.elements[globalIndex]));
        assert(localIndex !== undefined, 'local subgroup seed mapping failed');
        return localIndex;
      });
      const generatedLocal = subgroupGenerated(local, seeds);
      const generatedGlobal = generatedLocal.map((i) => localToGlobal[i]).sort((a, b) => a - b);
      const key = subsetKey(generatedGlobal);
      if (!known.has(key)) {
        known.set(key, generatedGlobal);
        queue.push(generatedGlobal);
      }
    }
  }
  return [...known.values()];
}

function isNormalIn(group, subgroup, ambient) {
  const subgroupSet = new Set(subgroup);
  for (const gIndex of ambient) {
    const g = group.elements[gIndex];
    const gInv = inverse(g);
    for (const hIndex of subgroup) {
      const conjugate = multiply(multiply(g, group.elements[hIndex]), gInv);
      const conjugateIndex = group.map.get(permKey(conjugate));
      if (!subgroupSet.has(conjugateIndex)) return false;
    }
  }
  return true;
}

function maximalProperNormalSubgroups(group, ambient) {
  const normals = enumerateSubgroups(group, ambient)
    .filter((subgroup) => subgroup.length < ambient.length)
    .filter((subgroup) => isNormalIn(group, subgroup, ambient));
  return normals.filter((candidate) => !normals.some((other) => {
    if (other.length <= candidate.length) return false;
    const otherSet = new Set(other);
    return candidate.every((index) => otherSet.has(index));
  }));
}

function quotientTable(group, ambient, normal) {
  const normalSet = new Set(normal);
  assert(isNormalIn(group, normal, ambient), 'quotient requested by a nonnormal subgroup');
  const assigned = new Map();
  const cosets = [];
  for (const representative of ambient) {
    if (assigned.has(representative)) continue;
    const members = [...new Set(normal.map((h) => {
      const product = multiply(group.elements[representative], group.elements[h]);
      return group.map.get(permKey(product));
    }))].sort((a, b) => a - b);
    const cosetIndex = cosets.length;
    members.forEach((member) => assigned.set(member, cosetIndex));
    cosets.push(members);
  }
  equal(cosets.length * normal.length, ambient.length, 'quotient coset partition size');
  const table = cosets.map((rowCoset) => cosets.map((columnCoset) => {
    let target = null;
    for (const a of rowCoset) {
      for (const b of columnCoset) {
        const product = group.map.get(
          permKey(multiply(group.elements[a], group.elements[b]))
        );
        const productCoset = assigned.get(product);
        assert(productCoset !== undefined, 'quotient product left its ambient group');
        if (target === null) target = productCoset;
        equal(productCoset, target, 'quotient operation is not well-defined');
      }
    }
    return target;
  }));
  return { cosets, table };
}

function tableIdentity(table) {
  return table.findIndex((row, e) => row.every((value, i) => {
    return value === i && table[i][e] === i;
  }));
}

function tableIsSimple(table) {
  const n = table.length;
  const identity = tableIdentity(table);
  assert(identity >= 0, 'quotient table has no identity');
  for (let a = 0; a < n; a += 1) {
    assert(table[a].includes(identity), 'quotient table has no right inverse');
    for (let b = 0; b < n; b += 1) {
      for (let c = 0; c < n; c += 1) {
        equal(table[table[a][b]][c], table[a][table[b][c]], 'quotient associativity');
      }
    }
  }
  const inverseOf = (a) => table[a].findIndex((value, b) => {
    return value === identity && table[b][a] === identity;
  });
  for (let mask = 1; mask < (1 << n); mask += 1) {
    if ((mask & (1 << identity)) === 0) continue;
    const members = Array.from({ length: n }, (_, i) => i).filter((i) => mask & (1 << i));
    let subgroup = true;
    for (const a of members) {
      if (!members.includes(inverseOf(a))) subgroup = false;
      for (const b of members) {
        if (!members.includes(table[a][b])) subgroup = false;
      }
    }
    if (!subgroup || members.length === 1 || members.length === n) continue;
    let normal = true;
    for (let g = 0; g < n; g += 1) {
      for (const h of members) {
        const conjugate = table[table[g][h]][inverseOf(g)];
        if (!members.includes(conjugate)) normal = false;
      }
    }
    if (normal) return false;
  }
  return true;
}

function fnv1a(text) {
  let hash = 0x811c9dc5;
  for (let i = 0; i < text.length; i += 1) {
    hash ^= text.charCodeAt(i);
    hash = Math.imul(hash, 0x01000193);
  }
  return (hash >>> 0).toString(16).padStart(8, '0');
}

function subgroupSignature(group, subgroup) {
  return subgroup.map((index) => permKey(group.elements[index])).sort().join('.');
}

function compositionRoutes(group, ambient) {
  if (ambient.length === 1) return [{ chain: [ambient], factors: [], tables: [] }];
  const next = maximalProperNormalSubgroups(group, ambient);
  assert(next.length > 0, `no next composition step below order ${ambient.length}`);
  const routes = [];
  for (const normal of next) {
    const quotient = quotientTable(group, ambient, normal);
    assert(tableIsSimple(quotient.table), 'maximal normal quotient is not simple');
    for (const tail of compositionRoutes(group, normal)) {
      routes.push({
        chain: [ambient, ...tail.chain],
        factors: [quotient.table.length, ...tail.factors],
        tables: [quotient.table, ...tail.tables]
      });
    }
  }
  return routes;
}

const html = fs.readFileSync(htmlPath, 'utf8');
const catalog = jsonBlock(html, 'catalog-data');
const fixtures = jsonBlock(html, 'verification-fixtures');

includes(
  html,
  '<title>Classification of Finite Simple Groups: 18 Families and 26 Sporadic Groups</title>',
  'search title'
);
includes(
  html,
  '<link rel="canonical" href="https://artwaste.land/strata/finite-simple-groups/" />',
  'canonical URL'
);
includes(html, '"datePublished":"2026-07-30"', 'JSON-LD publication date');
includes(html, '"dateModified":"2026-07-30"', 'JSON-LD modification date');
includes(html, 'submitted 16 January 2011, and one version', 'Boya metadata showing');
includes(html, 'SIGMA 7:009 (2011), DOI 10.3842/SIGMA.2011.009', 'Boya journal metadata showing');
includes(html, 'Notices of the AMS 51(7), 2004', 'Aschbacher metadata showing');
includes(html, 'Journal of Algebra 319(2), 621-628, 2008', 'Harada-Solomon metadata showing');
includes(html, 'The Classification of Finite Simple Groups, Volume 1</a>, Springer, 1983', 'Gorenstein metadata showing');
includes(html, 'The Classification of the Finite Simple Groups, Number 7</a>, AMS, 2018', 'GLS Number 7 metadata showing');
includes(html, 'No heading or sporadic name matches that filter.', 'catalog empty state');

const externalAnchor = {
  source: 'Luis J. Boya, Introduction to Sporadic Groups, arXiv:1101.3055v1',
  title: 'Introduction to Sporadic Groups',
  authors: ['Luis J. Boya'],
  submitted: '2011-01-16',
  versions: 1,
  familyEquation: [1, 1, 16, 18],
  sporadicBreakdown: [5, 7, 8, 6, 26],
  a5Order: 60
};

equal(catalog.families.length, externalAnchor.familyEquation[3], 'catalog family headings');
equal(catalog.families.filter((item) => item.kind === 'cyclic').length, 1, 'cyclic headings');
equal(catalog.families.filter((item) => item.kind === 'alternating').length, 1, 'alternating headings');
equal(catalog.families.filter((item) => item.kind === 'lie').length, 16, 'Lie-type headings');
equal(new Set(catalog.families.map((item) => item.id)).size, 18, 'unique family IDs');
equal(catalog.sporadics.length, externalAnchor.sporadicBreakdown[4], 'sporadic names');
equal(new Set(catalog.sporadics.map((item) => item.name)).size, 26, 'unique sporadic names');
for (const [i, count] of externalAnchor.sporadicBreakdown.slice(0, 4).entries()) {
  equal(
    catalog.sporadics.filter((item) => item.level === i + 1).length,
    count,
    `sporadic level ${i + 1}`
  );
}

const s4Permutations = permutationsHeap(4);
const a5Permutations = permutationsHeap(5).filter((p) => parity(p) === 0);
const s4 = indexGroup(s4Permutations);
const a5 = indexGroup(a5Permutations);
equal(s4.elements.length, 24, 'S4 order from all permutations of four letters');
equal(a5.elements.length, externalAnchor.a5Order, 'A5 external anchor from even permutations');
verifyGroup(s4, 'S4');
verifyGroup(a5, 'A5');
const a5ElementOrders = new Map();
for (const element of a5.elements) {
  const order = permutationOrder(element);
  a5ElementOrders.set(order, (a5ElementOrders.get(order) || 0) + 1);
}
equal(a5ElementOrders.get(1), 1, 'A5 identity count');
equal(a5ElementOrders.get(2), 15, 'A5 order-2 element count');
equal(a5ElementOrders.get(3), 20, 'A5 order-3 element count');
equal(a5ElementOrders.get(5), 24, 'A5 order-5 element count');
equal(a5ElementOrders.size, 4, 'A5 distinct element orders');

const a5Closures = a5.elements
  .map((_, i) => i)
  .filter((i) => i !== a5.identity)
  .map((i) => normalClosure(a5, i).length);
equal(a5Closures.length, 59, 'nonidentity A5 seeds');
equal(Math.min(...a5Closures), 60, 'smallest nonidentity normal closure in A5');
equal(Math.max(...a5Closures), 60, 'largest nonidentity normal closure in A5');

const doubleTransposition = s4.elements.findIndex((p) => {
  return permutationOrder(p) === 2 && p.filter((image, i) => image !== i).length === 4;
});
assert(doubleTransposition >= 0, 'double transposition not found in S4');
equal(normalClosure(s4, doubleTransposition).length, 4, 'S4 double-transposition normal closure');

const allS4 = s4.elements.map((_, i) => i);
const subgroupCount = enumerateSubgroups(s4, allS4).length;
equal(subgroupCount, 30, 'S4 subgroup count');
const routes = compositionRoutes(s4, allS4);
equal(routes.length, 3, 'S4 composition route count');
const multisets = routes.map((route) => route.factors.slice().sort((a, b) => a - b).join(','));
equal(new Set(multisets).size, 1, 'Jordan-Holder factor multiset agreement');
equal(multisets[0], '2,2,2,3', 'S4 simple factor multiset');
equal(routes.reduce((sum, route) => sum + route.tables.length, 0), 12, 'quotient tables across routes');
assert(routes.every((route) => route.tables.every(tableIsSimple)), 'every quotient must be simple');

const factorHash = fnv1a(multisets[0]);
const routeSignatures = routes.map((route) => {
  return route.chain.map((subgroup) => subgroupSignature(s4, subgroup)).join('>');
}).sort();
const routeSetHash = fnv1a(routeSignatures.join('|'));

equal(fixtures.a5Order, 60, 'page fixture A5 order');
equal(fixtures.a5NonidentitySeeds, 59, 'page fixture A5 seed count');
equal(fixtures.a5ClosureMin, 60, 'page fixture A5 closure minimum');
equal(fixtures.s4Order, 24, 'page fixture S4 order');
equal(fixtures.s4Subgroups, 30, 'page fixture S4 subgroup count');
equal(fixtures.s4Routes, 3, 'page fixture S4 route count');
equal(fixtures.factorMultiset.join(','), '2,2,2,3', 'page fixture factor multiset');
equal(fixtures.factorHash, factorHash, 'page fixture factor hash');
equal(fixtures.routeSetHash, routeSetHash, 'page fixture route-set hash');
equal(fixtures.quasithinVolumes.length, 2, 'page fixture quasithin volume count');
equal(fixtures.quasithinVolumes.reduce((sum, volume) => sum + volume.pages, 0), 1220, 'quasithin exact page sum');
equal(fixtures.quasithinRoundedPages, 1200, 'Aschbacher rounded quasithin page count');
equal(fixtures.laterStandardComponentYear, 2008, 'later standard-component treatment year');
equal(fixtures.scaleContributorEstimate, 100, 'Gorenstein contributor estimate');
equal(fixtures.scalePageEstimates[0], 10000, 'Gorenstein page estimate');
equal(fixtures.scalePageEstimates[1], 15000, 'later broader page estimate');
equal(fixtures.glsPublishedVolumes, 10, 'page fixture GLS published count');
equal(fixtures.glsLatestYear, 2023, 'page fixture GLS latest year');
equal(fixtures.glsCatalogChecked, '2026-07-29', 'GLS official catalog check date');

console.log('finite-simple-groups verification');
console.log(`external anchor: ${externalAnchor.title}, ${externalAnchor.authors.join(', ')}, ${externalAnchor.submitted}, v${externalAnchor.versions}`);
console.log(`catalog: 1 cyclic + 1 alternating + 16 Lie-type = ${catalog.families.length} family headings`);
console.log(`sporadics: 5 + 7 + 8 + 6 = ${catalog.sporadics.length} unique names`);
console.log(`A5: order ${a5.elements.length}; ${a5Closures.length} nonidentity seeds; normal closures ${Math.min(...a5Closures)}..${Math.max(...a5Closures)}`);
console.log(`A5 selectable element orders: 1:${a5ElementOrders.get(1)}, 2:${a5ElementOrders.get(2)}, 3:${a5ElementOrders.get(3)}, 5:${a5ElementOrders.get(5)}`);
console.log(`S4: order ${s4.elements.length}; ${subgroupCount} subgroups; double-transposition normal closure 4`);
console.log(`S4 composition series: ${routes.length} routes; factors ${multisets[0]}; ${routes.length * 4} simple quotient tables`);
console.log(`checksums: factors ${factorHash}; route set ${routeSetHash}`);
console.log(`quasithin catalog lengths: 477 + 743 = ${fixtures.quasithinVolumes.reduce((sum, volume) => sum + volume.pages, 0)} pages across ${fixtures.quasithinVolumes.length} volumes`);
console.log(`GLS catalog status fixture: ${fixtures.glsPublishedVolumes} numbered volumes, latest found ${fixtures.glsLatestYear}`);
console.log(`sourced estimates: about ${fixtures.scaleContributorEstimate} contributors; ${fixtures.scalePageEstimates[0]} to ${fixtures.scalePageEstimates[1]} pages under different scopes`);
console.log(`dated source checks: later treatment ${fixtures.laterStandardComponentYear}; AMS catalog checked ${fixtures.glsCatalogChecked}`);
console.log('LIMIT: this verifies the catalog transcription and finite computations, not CFSG completeness.');
