/* THESEUS · KG Statistics core. No network access or dependencies.
   Mirrors TripletsStats.calculate_navigation_calibration and common graph stats. */
(function (scope) {
  'use strict';
  const quantile = (sorted, p) => {
    if (!sorted.length) return 0;
    const pos = (sorted.length - 1) * p, i = Math.floor(pos), a = pos - i;
    return sorted[i] + (sorted[Math.min(i + 1, sorted.length - 1)] - sorted[i]) * a;
  };
  const median = a => quantile(a, .5);
  const mean = a => a.length ? a.reduce((x, y) => x + y, 0) / a.length : 0;
  const frequencies = a => {
    const f = new Map();
    for (const n of a) f.set(n, (f.get(n) || 0) + 1);
    return [...f].sort((a, b) => a[0] - b[0]).map(([degree, count]) => ({degree, count}));
  };
  function createAccumulator() {
    const ids = new Map(), names = [], parent = [], rank = [], out = [], inc = [], outRaw = [], inRaw = [],
      neighbors = [], outgoingNeighbors = [], outgoingRels = [], incidentRels = [],
      relIds = new Map(), relNames = [], relFreq = [], relEdges = [], unique = new Set();
    let rows = 0, simpleEdges = 0, bad = 0, selfLoops = 0;
    function node(label) {
      let id = ids.get(label);
      if (id !== undefined) return id;
      id = names.length; ids.set(label,id); names.push(label); parent.push(id); rank.push(1);
      out.push(0); inc.push(0); outRaw.push(0); inRaw.push(0);
      neighbors.push(new Set()); outgoingNeighbors.push(new Set()); outgoingRels.push(new Set()); incidentRels.push(new Set());
      return id;
    }
    function relation(label) {
      let id = relIds.get(label);
      if (id !== undefined) return id;
      id = relNames.length; relIds.set(label,id); relNames.push(label); relFreq.push(0); relEdges.push([]);
      return id;
    }
    function root(x) { let y=x; while(parent[y]!==y)y=parent[y];while(parent[x]!==x){const k=parent[x];parent[x]=y;x=k;}return y; }
    function unite(a,b) {a=root(a);b=root(b);if(a===b)return;if(rank[a]<rank[b])[a,b]=[b,a];parent[b]=a;rank[a]+=rank[b];}
    function add(h,r,t){
      h=String(h??'').trim();r=String(r??'').trim();t=String(t??'').trim();
      if(!h||!r||!t){bad++;return;}
      const a=node(h), b=node(t), relationId=relation(r); rows++;
      outRaw[a]++;inRaw[b]++;relFreq[relationId]++;
      const key=`${a}:${relationId}:${b}`;
      if(unique.has(key))return;
      unique.add(key);out[a]++;inc[b]++;
      outgoingNeighbors[a].add(b);outgoingRels[a].add(relationId);
      incidentRels[a].add(relationId);incidentRels[b].add(relationId);
      relEdges[relationId].push([a,b]);
      if(a===b)selfLoops++;
      if(!neighbors[a].has(b)){neighbors[a].add(b);if(a!==b) neighbors[b].add(a);simpleEdges++;unite(a,b);}
    }
    function addNode(n){n=String(n??'').trim();if(n)node(n);}
    function output(options={}){
      const n=names.length, m=relNames.length;
      const outValues=[...out].sort((a,b)=>a-b), inValues=[...inc].sort((a,b)=>a-b),
        onValues=outgoingNeighbors.map(s=>s.size).sort((a,b)=>a-b),
        orValues=outgoingRels.map(s=>s.size).sort((a,b)=>a-b);
      const sums=new Map();for(let i=0;i<n;i++){const p=root(i);sums.set(p,(sums.get(p)||0)+1);}
      const wcc=[...sums.values()].sort((a,b)=>a-b), largest=wcc[wcc.length-1]||0;
      const s={
        triplet_rows:rows, unique_triples:unique.size, duplicate_triplet_rows:rows-unique.size,
        entities:n,relations:m,self_loop_triples:selfLoops,zero_out_degree_nodes:out.filter(v=>v===0).length,
        out_degree_mean:mean(outValues),out_degree_median:median(outValues),out_degree_p90:quantile(outValues,.9),
        out_degree_p95:quantile(outValues,.95),out_degree_p99:quantile(outValues,.99),out_degree_max:outValues[n-1]||0,
        in_degree_mean:mean(inValues),in_degree_median:median(inValues),in_degree_p90:quantile(inValues,.9),
        in_degree_p95:quantile(inValues,.95),in_degree_p99:quantile(inValues,.99),in_degree_max:inValues[n-1]||0,
        unique_out_neighbors_mean:mean(onValues),unique_out_neighbors_median:median(onValues),
        unique_out_neighbors_p90:quantile(onValues,.9), unique_out_neighbors_p95:quantile(onValues,.95),
        unique_out_neighbors_p99:quantile(onValues,.99),unique_out_neighbors_max:onValues[n-1]||0,
        distinct_out_relations_mean:mean(orValues),distinct_out_relations_median:median(orValues),
        distinct_out_relations_p90:quantile(orValues,.9),distinct_out_relations_p95:quantile(orValues,.95),
        distinct_out_relations_p99:quantile(orValues,.99),distinct_out_relations_max:orValues[n-1]||0,
        nodes_out_degree_gt_10_fraction: n?out.filter(v=>v>10).length/n:0,
        nodes_out_degree_gt_50_fraction:n?out.filter(v=>v>50).length/n:0,
        nodes_out_degree_gt_100_fraction:n?out.filter(v=>v>100).length/n:0,
        wcc_count:wcc.length,largest_wcc_nodes:largest,largest_wcc_fraction:n?largest/n:0,
        median_wcc_nodes:median(wcc),singleton_wcc_count:wcc.filter(v=>v===1).length,
        isolated_nodes:out.reduce((sum,v,i)=>sum+(v===0 && inc[i]===0?1:0),0),
        out_degree_mean_legacy:mean(outRaw.filter((v,i)=>v>0||inRaw[i]>0)),
        in_degree_mean_legacy:mean(inRaw.filter((v,i)=>outRaw[i]>0||v>0)),
        graph_density:n>1?2*simpleEdges/(n*(n-1)):0
      };
      const nodes=names.map((name,i)=>({name,out_degree:out[i],in_degree:inc[i],out_degree_rows:outRaw[i],in_degree_rows:inRaw[i],unique_out_neighbors:outgoingNeighbors[i].size,distinct_out_relations:outgoingRels[i].size,distinct_incident_relations:incidentRels[i].size,total_degree_rows:outRaw[i]+inRaw[i]}));
      const maxTop=options.maxTop||25;
      const topNodes=[...nodes].sort((a,b)=>b.total_degree_rows-a.total_degree_rows || a.name.localeCompare(b.name)).slice(0,maxTop);
      const diverseNodes=[...nodes].sort((a,b)=>b.distinct_incident_relations-a.distinct_incident_relations || a.name.localeCompare(b.name)).slice(0,maxTop);
      const relations=relNames.map((name,i)=>({name,count:relFreq[i],unique_triples:relEdges[i].length})).sort((a,b)=>b.count-a.count||a.name.localeCompare(b.name));
      const optional={};
      if(options.clustering){
        // Exact NetworkX-style undirected average clustering, ignoring self-loops.
        // Orient edges by increasing degree (then numeric node id), and count each
        // triangle once using intersections of forward neighbors. This avoids the
        // O(degree^2) cost at high-degree hubs in sparse graphs such as MetaQA.
        const degree=neighbors.map((adj,i)=>adj.size-(adj.has(i)?1:0));
        const forward=Array.from({length:n},()=>new Set());
        for(let u=0;u<n;u++)for(const v of neighbors[u]){
          if(u===v)continue;
          if(degree[u]<degree[v]||(degree[u]===degree[v]&&u<v))forward[u].add(v);
        }
        let estimate=0;
        const budget=30000000;
        for(let u=0;u<n&&estimate<=budget;u++)for(const v of forward[u]){
          estimate+=Math.min(forward[u].size,forward[v].size);
          if(estimate>budget)break;
        }
        if(estimate>budget){
          optional.clustering=`Skipped. Estimated triangle-intersection work exceeds ${budget.toLocaleString('en-US')} checks. This optional calculation was skipped to avoid excessive browser resource use.`;
        } else {
          const triangles=new Float64Array(n);
          for(let u=0;u<n;u++)for(const v of forward[u]){
            const small=forward[u].size<=forward[v].size?forward[u]:forward[v];
            const large=small===forward[u]?forward[v]:forward[u];
            for(const w of small)if(large.has(w)){triangles[u]++;triangles[v]++;triangles[w]++;}
          }
          let sum=0;
          for(let u=0;u<n;u++)if(degree[u]>1)sum+=2*triangles[u]/(degree[u]*(degree[u]-1));
          s.clustering_coefficient=n?sum/n:0;
        }
      }
      if(options.eigenvector){
        // Matches NetworkX's undirected graph construction and (A + I) power iteration; no isolated metadata nodes.
        const connected=[];for(let i=0;i<n;i++)if(outRaw[i]||inRaw[i])connected.push(i);
        if(connected.length>10000||simpleEdges>80000)optional.eigenvector='Skipped. Eigenvector centrality is capped at 10,000 connected nodes / 80,000 undirected edges.';
        else if(connected.length){
          const nn=connected.length;let x=new Float64Array(n),last=new Float64Array(n);
          for(const i of connected)x[i]=1/Math.sqrt(nn);
          let converged=false;
          for(let iter=0;iter<1000;iter++){
            let norm=0;for(const i of connected){let v=x[i];for(const j of neighbors[i])v+=x[j];last[i]=v;norm+=v*v;}
            norm=Math.sqrt(norm)||1;let err=0;for(const i of connected){last[i]/=norm;err+=Math.abs(last[i]-x[i]);}
            [x,last]=[last,x];if(err<nn*1e-6){converged=true;break;}
          }
          if(!converged)optional.eigenvector='Did not converge within 1,000 iterations (as in NetworkX, this result is not reported).';
          else optional.eigenvector_top=connected.map(i=>({name:names[i],value:x[i]})).sort((a,b)=>b.value-a.value).slice(0,20);
        }
      }
      if(options.legacy){
        if(unique.size>20000||n>10000) optional.legacy='Skipped. Legacy per-relation cycle pruning and reachability are capped at 20,000 unique triples and 10,000 nodes.';
        else {
          const lengths=[], kh=[];
          for(let r=0;r<m;r++){
            const edges=relEdges[r], vx=new Set();for(const [a,b] of edges){vx.add(a);vx.add(b);}
            // Directed per-relation graph, SCC via iterative Kosaraju; prune edges within SCC.
            const f=new Map(), rev=new Map();for(const v of vx){f.set(v,[]);rev.set(v,[]);}
            for(const [a,b] of edges){f.get(a).push(b);rev.get(b).push(a);}
            const seen=new Set(),order=[];
            for(const src of vx){if(seen.has(src))continue;seen.add(src);const stack=[[src,0]];
              while(stack.length){const top=stack[stack.length-1], ns=f.get(top[0]);if(top[1]<ns.length){const v=ns[top[1]++];if(!seen.has(v)){seen.add(v);stack.push([v,0]);}}
              else{order.push(top[0]);stack.pop();}}
            }
            const scc=new Map();let sid=0;
            for(let i=order.length-1;i>=0;i--){const src=order[i];if(scc.has(src))continue;const stack=[src];scc.set(src,sid);
              while(stack.length){for(const t of rev.get(stack.pop()))if(!scc.has(t)){scc.set(t,sid);stack.push(t);}}sid++;
            }
            const graph=new Map(),indeg=new Map(),height=new Map();for(const v of vx){graph.set(v,[]);indeg.set(v,0);height.set(v,0);}
            for(const [a,b] of edges)if(scc.get(a)!==scc.get(b)){graph.get(a).push(b);indeg.set(b,indeg.get(b)+1);}
            const q=[...vx].filter(v=>indeg.get(v)===0);let best=0;
            for(let k=0;k<q.length;k++){const u=q[k];for(const v of graph.get(u)){height.set(v,Math.max(height.get(v),height.get(u)+1));best=Math.max(best,height.get(v));indeg.set(v,indeg.get(v)-1);if(indeg.get(v)===0)q.push(v);}}
            lengths.push(best);
            if(vx.size>600){kh.push(null);continue;}
            let count=0,oneWay=0;const reach=new Map();
            for(const src of vx){const visited=new Set([src]),queue=[src];for(let k=0;k<queue.length;k++)for(const t of f.get(queue[k]))if(!visited.has(t)){visited.add(t);queue.push(t);}visited.delete(src);reach.set(src,visited);}
            for(const [a,reachA] of reach)for(const b of reachA){count++;if(!reach.get(b).has(a))oneWay++;}
            kh.push(count?oneWay/count:0);
          }
          s.legacy_max_non_cyclic_path=lengths.length?Math.max(...lengths):0;
          if(kh.every(v=>v!==null))s.legacy_krackhardt_mean=mean(kh);
          else optional.legacy_krackhardt='Partial only: some relation graphs exceeded 600 vertices; no mean reported.';
          optional.legacy_path_per_relation=relNames.map((name,i)=>({relation:name,maximum: lengths[i],krackhardt:kh[i]}));
        }
      }
      return {summary:s,optional,topNodes,diverseNodes,relations,nodes,
        components:wcc.slice().reverse().slice(0,20),
        distributions:{out_degree:frequencies(out),in_degree:frequencies(inc),distinct_out_relations:frequencies(orValues),unique_out_neighbors:frequencies(onValues)},
        parse:{bad_rows:bad},sourceNote:'Measures from complete parsed input, not a sample.',
      };
    }
    return {add,addNode,output,get rows(){return rows;},get nodes(){return names.length;}};
  }
  const api={createAccumulator,quantile};
  if(typeof module==='object'&&module.exports)module.exports=api;
  if(scope)scope.KGCore=api;
})(typeof self!=='undefined'?self:null);