/**
 * Advanced graph primitives - path finding and relationship analysis
 *
 * Answer: "How do notes connect?"
 */

import type { VaultIndex, Backlink } from '../../core/read/types.js';
import { getBacklinksForNote, resolveTarget, findHubNotes } from '../../core/read/graph.js';

// Module-level cache: keyed on VaultIndex instance, auto-invalidates on rebuild
const hubConnectionCache = new WeakMap<VaultIndex, Map<string, number>>();

function getHubConnectionCounts(index: VaultIndex): Map<string, number> {
  let cached = hubConnectionCache.get(index);
  if (cached) return cached;

  const hubNotes = findHubNotes(index, 0);
  cached = new Map<string, number>();
  for (const hub of hubNotes) {
    cached.set(hub.path, hub.total_connections);
  }
  hubConnectionCache.set(index, cached);
  return cached;
}

/**
 * Binary search for sorted insertion into priority queue
 */
function binaryInsert(pq: { node: string; cost: number }[], entry: { node: string; cost: number }): void {
  let lo = 0, hi = pq.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (pq[mid].cost <= entry.cost) lo = mid + 1;
    else hi = mid;
  }
  pq.splice(lo, 0, entry);
}

/**
 * Find shortest path between two notes using BFS
 */
export function getLinkPath(
  index: VaultIndex,
  fromPath: string,
  toPath: string,
  maxDepth: number = 10
): {
  exists: boolean;
  path: string[];
  length: number;
} {
  // Normalize paths
  const from = index.notes.has(fromPath) ? fromPath : resolveTarget(index, fromPath);
  const to = index.notes.has(toPath) ? toPath : resolveTarget(index, toPath);

  if (!from || !to) {
    return { exists: false, path: [], length: -1 };
  }

  if (from === to) {
    return { exists: true, path: [from], length: 0 };
  }

  // BFS to find shortest path
  const visited = new Set<string>();
  const queue: { path: string[]; current: string }[] = [{ path: [from], current: from }];

  while (queue.length > 0) {
    const { path: currentPath, current } = queue.shift()!;

    if (currentPath.length > maxDepth) {
      continue;
    }

    const note = index.notes.get(current);
    if (!note) continue;

    // Get all outlinks from current note
    for (const link of note.outlinks) {
      const targetPath = resolveTarget(index, link.target);
      if (!targetPath) continue;

      if (targetPath === to) {
        const fullPath = [...currentPath, targetPath];
        return {
          exists: true,
          path: fullPath,
          length: fullPath.length - 1,
        };
      }

      if (!visited.has(targetPath)) {
        visited.add(targetPath);
        queue.push({
          path: [...currentPath, targetPath],
          current: targetPath,
        });
      }
    }
  }

  return { exists: false, path: [], length: -1 };
}

/**
 * Find shortest weighted path between two notes using Dijkstra's algorithm.
 * Penalizes hub nodes so paths reflect genuine conceptual connections.
 */
export function getWeightedLinkPath(
  index: VaultIndex,
  fromPath: string,
  toPath: string,
  maxDepth: number = 10
): {
  exists: boolean;
  path: string[];
  length: number;
  total_weight: number;
  weights: number[];
} {
  const from = index.notes.has(fromPath) ? fromPath : resolveTarget(index, fromPath);
  const to = index.notes.has(toPath) ? toPath : resolveTarget(index, toPath);

  if (!from || !to) {
    return { exists: false, path: [], length: -1, total_weight: 0, weights: [] };
  }

  if (from === to) {
    return { exists: true, path: [from], length: 0, total_weight: 0, weights: [] };
  }

  // Get hub connection counts (cached per VaultIndex instance)
  const connectionCounts = getHubConnectionCounts(index);

  // Dijkstra's algorithm
  const dist = new Map<string, number>();
  const prev = new Map<string, string>();
  const depthMap = new Map<string, number>();
  dist.set(from, 0);
  depthMap.set(from, 0);

  // Simple priority queue (sorted insert) — vault graphs are small
  const pq: { node: string; cost: number }[] = [{ node: from, cost: 0 }];
  const visited = new Set<string>();

  while (pq.length > 0) {
    const { node: current, cost: currentCost } = pq.shift()!;

    if (current === to) break;
    if (visited.has(current)) continue;
    visited.add(current);

    const currentDepth = depthMap.get(current) ?? 0;
    if (currentDepth >= maxDepth) continue;

    const note = index.notes.get(current);
    if (!note) continue;

    for (const link of note.outlinks) {
      const targetPath = resolveTarget(index, link.target);
      if (!targetPath || visited.has(targetPath)) continue;

      // Edge weight: 1 / (1 + connectionStrength) * hub penalty
      const strength = getConnectionStrength(index, current, targetPath);
      const baseWeight = 1 / (1 + strength.score);
      const targetConnections = connectionCounts.get(targetPath) ?? 0;
      const hubPenalty = targetConnections > 0 ? 1 + Math.log2(targetConnections) : 1;
      const edgeWeight = baseWeight * hubPenalty;

      const newDist = currentCost + edgeWeight;
      const existingDist = dist.get(targetPath);

      if (existingDist === undefined || newDist < existingDist) {
        dist.set(targetPath, newDist);
        prev.set(targetPath, current);
        depthMap.set(targetPath, currentDepth + 1);

        // Insert in sorted order (binary search)
        binaryInsert(pq, { node: targetPath, cost: newDist });
      }
    }
  }

  if (!dist.has(to)) {
    return { exists: false, path: [], length: -1, total_weight: 0, weights: [] };
  }

  // Reconstruct path
  const resultPath: string[] = [];
  let node: string | undefined = to;
  while (node) {
    resultPath.unshift(node);
    node = prev.get(node);
  }

  // Compute per-edge weights
  const weights: number[] = [];
  for (let i = 0; i < resultPath.length - 1; i++) {
    const edgeDist = (dist.get(resultPath[i + 1]) ?? 0) - (dist.get(resultPath[i]) ?? 0);
    weights.push(Math.round(edgeDist * 1000) / 1000);
  }

  return {
    exists: true,
    path: resultPath,
    length: resultPath.length - 1,
    total_weight: Math.round((dist.get(to) ?? 0) * 1000) / 1000,
    weights,
  };
}

/**
 * Find notes that both A and B link to (common neighbors)
 */
export function getCommonNeighbors(
  index: VaultIndex,
  noteAPath: string,
  noteBPath: string
): Array<{
  path: string;
  title: string;
  linked_from_a_line: number;
  linked_from_b_line: number;
}> {
  const noteA = index.notes.get(noteAPath);
  const noteB = index.notes.get(noteBPath);

  if (!noteA || !noteB) return [];

  // Get targets from A
  const aTargets = new Map<string, number>();
  for (const link of noteA.outlinks) {
    const resolved = resolveTarget(index, link.target);
    if (resolved) {
      aTargets.set(resolved, link.line);
    }
  }

  // Find overlap with B
  const common: Array<{
    path: string;
    title: string;
    linked_from_a_line: number;
    linked_from_b_line: number;
  }> = [];

  for (const link of noteB.outlinks) {
    const resolved = resolveTarget(index, link.target);
    if (resolved && aTargets.has(resolved)) {
      const targetNote = index.notes.get(resolved);
      if (targetNote) {
        common.push({
          path: resolved,
          title: targetNote.title,
          linked_from_a_line: aTargets.get(resolved)!,
          linked_from_b_line: link.line,
        });
      }
    }
  }

  return common;
}

/**
 * Find bidirectional links (A links to B AND B links to A)
 */
export function findBidirectionalLinks(
  index: VaultIndex,
  notePath?: string
): Array<{
  noteA: string;
  noteB: string;
  a_to_b_line: number;
  b_to_a_line: number;
}> {
  const results: Array<{
    noteA: string;
    noteB: string;
    a_to_b_line: number;
    b_to_a_line: number;
  }> = [];

  const seen = new Set<string>();

  const notesToCheck = notePath
    ? [index.notes.get(notePath)].filter(Boolean)
    : Array.from(index.notes.values());

  for (const noteA of notesToCheck) {
    if (!noteA) continue;

    for (const linkFromA of noteA.outlinks) {
      const targetPath = resolveTarget(index, linkFromA.target);
      if (!targetPath) continue;

      const noteB = index.notes.get(targetPath);
      if (!noteB) continue;

      // Check if B links back to A
      for (const linkFromB of noteB.outlinks) {
        const backTarget = resolveTarget(index, linkFromB.target);
        if (backTarget === noteA.path) {
          // Found bidirectional link
          const pairKey = [noteA.path, noteB.path].sort().join('|');
          if (!seen.has(pairKey)) {
            seen.add(pairKey);
            results.push({
              noteA: noteA.path,
              noteB: noteB.path,
              a_to_b_line: linkFromA.line,
              b_to_a_line: linkFromB.line,
            });
          }
        }
      }
    }
  }

  return results;
}

/**
 * Find notes with only inbound links (dead ends - consume but don't contribute)
 */
export function findDeadEnds(
  index: VaultIndex,
  folder?: string,
  minBacklinks: number = 1
): Array<{
  path: string;
  title: string;
  backlink_count: number;
}> {
  const results: Array<{
    path: string;
    title: string;
    backlink_count: number;
  }> = [];

  for (const note of index.notes.values()) {
    if (folder && !note.path.startsWith(folder)) continue;

    // Has no outlinks
    if (note.outlinks.length === 0) {
      const backlinkCount = getBacklinksForNote(index, note.path).length;

      // But has backlinks
      if (backlinkCount >= minBacklinks) {
        results.push({
          path: note.path,
          title: note.title,
          backlink_count: backlinkCount,
        });
      }
    }
  }

  return results.sort((a, b) => b.backlink_count - a.backlink_count);
}

/**
 * Find notes with only outbound links (sources - contribute but aren't referenced)
 */
export function findSources(
  index: VaultIndex,
  folder?: string,
  minOutlinks: number = 1
): Array<{
  path: string;
  title: string;
  outlink_count: number;
}> {
  const results: Array<{
    path: string;
    title: string;
    outlink_count: number;
  }> = [];

  for (const note of index.notes.values()) {
    if (folder && !note.path.startsWith(folder)) continue;

    const backlinkCount = getBacklinksForNote(index, note.path).length;

    // Has outlinks but no backlinks
    if (note.outlinks.length >= minOutlinks && backlinkCount === 0) {
      results.push({
        path: note.path,
        title: note.title,
        outlink_count: note.outlinks.length,
      });
    }
  }

  return results.sort((a, b) => b.outlink_count - a.outlink_count);
}

/**
 * Get link context - the paragraph containing a specific link
 */
export async function getLinkContext(
  index: VaultIndex,
  sourcePath: string,
  targetPath: string,
  vaultPath: string
): Promise<Array<{
  line: number;
  context: string;
}>> {
  const note = index.notes.get(sourcePath);
  if (!note) return [];

  const fs = await import('fs');
  const path = await import('path');

  const absolutePath = path.join(vaultPath, sourcePath);
  let content: string;

  try {
    content = await fs.promises.readFile(absolutePath, 'utf-8');
  } catch {
    return [];
  }

  const lines = content.split('\n');
  const results: Array<{ line: number; context: string }> = [];

  // Find links to the target
  for (const link of note.outlinks) {
    const resolved = resolveTarget(index, link.target);
    if (resolved === targetPath || link.target.toLowerCase() === targetPath.toLowerCase().replace(/\.md$/, '')) {
      // Get surrounding lines for context
      const startLine = Math.max(0, link.line - 2);
      const endLine = Math.min(lines.length - 1, link.line + 1);
      const context = lines.slice(startLine, endLine + 1).join('\n');

      results.push({
        line: link.line,
        context,
      });
    }
  }

  return results;
}

/**
 * Calculate connection strength between two notes
 * Based on: mutual links, shared tags, shared outlinks, proximity in hierarchy
 */
export function getConnectionStrength(
  index: VaultIndex,
  noteAPath: string,
  noteBPath: string
): {
  score: number;
  factors: {
    mutual_link: boolean;
    shared_tags: string[];
    shared_outlinks: number;
    same_folder: boolean;
  };
} {
  const noteA = index.notes.get(noteAPath);
  const noteB = index.notes.get(noteBPath);

  if (!noteA || !noteB) {
    return {
      score: 0,
      factors: {
        mutual_link: false,
        shared_tags: [],
        shared_outlinks: 0,
        same_folder: false,
      },
    };
  }

  let score = 0;
  const factors = {
    mutual_link: false,
    shared_tags: [] as string[],
    shared_outlinks: 0,
    same_folder: false,
  };

  // Check mutual link (+3)
  const aLinksToB = noteA.outlinks.some(l => {
    const resolved = resolveTarget(index, l.target);
    return resolved === noteBPath;
  });
  const bLinksToA = noteB.outlinks.some(l => {
    const resolved = resolveTarget(index, l.target);
    return resolved === noteAPath;
  });

  if (aLinksToB && bLinksToA) {
    factors.mutual_link = true;
    score += 3;
  } else if (aLinksToB || bLinksToA) {
    score += 1;
  }

  // Shared tags (+1 each)
  const tagsA = new Set(noteA.tags);
  for (const tag of noteB.tags) {
    if (tagsA.has(tag)) {
      factors.shared_tags.push(tag);
      score += 1;
    }
  }

  // Shared outlinks (+0.5 each)
  const common = getCommonNeighbors(index, noteAPath, noteBPath);
  factors.shared_outlinks = common.length;
  score += common.length * 0.5;

  // Same folder (+1)
  const folderA = noteAPath.split('/').slice(0, -1).join('/');
  const folderB = noteBPath.split('/').slice(0, -1).join('/');
  if (folderA === folderB && folderA !== '') {
    factors.same_folder = true;
    score += 1;
  }

  return { score, factors };
}

// =============================================================================
// Centrality Metrics (Brandes betweenness + closeness + degree)
// =============================================================================

export interface CentralityResult {
  path: string;
  title: string;
  degree: number;
  betweenness: number;
  closeness: number;
}

/**
 * Compute degree, betweenness, and closeness centrality for all notes.
 * Uses Brandes algorithm for betweenness (O(V*E)).
 */
export function computeCentralityMetrics(
  index: VaultIndex,
  limit: number = 20,
): CentralityResult[] {
  // Build adjacency (directed outlinks)
  const paths = Array.from(index.notes.keys());
  const N = paths.length;
  if (N === 0) return [];

  const pathIdx = new Map<string, number>();
  paths.forEach((p, i) => pathIdx.set(p, i));

  // Also map normalized targets to indices
  for (const note of index.notes.values()) {
    const normalized = note.title.toLowerCase();
    if (!pathIdx.has(normalized)) {
      pathIdx.set(normalized, pathIdx.get(note.path)!);
    }
  }

  const outAdj: number[][] = Array.from({ length: N }, () => []);
  const inAdj: number[][] = Array.from({ length: N }, () => []);

  for (const note of index.notes.values()) {
    const fromIdx = pathIdx.get(note.path);
    if (fromIdx === undefined) continue;
    for (const link of note.outlinks) {
      let toIdx = pathIdx.get(link.target);
      if (toIdx === undefined) toIdx = pathIdx.get(link.target.toLowerCase());
      if (toIdx !== undefined && toIdx !== fromIdx) {
        outAdj[fromIdx].push(toIdx);
        inAdj[toIdx].push(fromIdx);
      }
    }
  }

  // Degree centrality
  const degree = new Float64Array(N);
  for (let i = 0; i < N; i++) {
    degree[i] = outAdj[i].length + inAdj[i].length;
  }

  // Brandes betweenness + closeness (undirected BFS from each node)
  const betweenness = new Float64Array(N);
  const closenessSum = new Float64Array(N); // sum of distances
  const reachable = new Int32Array(N); // count of reachable nodes

  // Build undirected adjacency for BFS
  const undirAdj: number[][] = Array.from({ length: N }, () => []);
  for (let i = 0; i < N; i++) {
    for (const j of outAdj[i]) {
      undirAdj[i].push(j);
      undirAdj[j].push(i);
    }
  }

  for (let s = 0; s < N; s++) {
    // BFS from s (Brandes)
    const stack: number[] = [];
    const pred: number[][] = Array.from({ length: N }, () => []);
    const sigma = new Float64Array(N);
    const dist = new Int32Array(N).fill(-1);
    sigma[s] = 1;
    dist[s] = 0;
    const queue: number[] = [s];
    let head = 0;

    while (head < queue.length) {
      const v = queue[head++];
      stack.push(v);
      for (const w of undirAdj[v]) {
        if (dist[w] < 0) {
          dist[w] = dist[v] + 1;
          queue.push(w);
        }
        if (dist[w] === dist[v] + 1) {
          sigma[w] += sigma[v];
          pred[w].push(v);
        }
      }
    }

    // Accumulate closeness distance
    for (let t = 0; t < N; t++) {
      if (dist[t] > 0) {
        closenessSum[s] += dist[t];
        reachable[s]++;
      }
    }

    // Accumulate betweenness
    const delta = new Float64Array(N);
    while (stack.length > 0) {
      const w = stack.pop()!;
      for (const v of pred[w]) {
        delta[v] += (sigma[v] / sigma[w]) * (1 + delta[w]);
      }
      if (w !== s) {
        betweenness[w] += delta[w];
      }
    }
  }

  // Normalize betweenness (divide by (N-1)*(N-2) for directed graph normalization)
  const normFactor = N > 2 ? (N - 1) * (N - 2) : 1;

  // Build results
  const results: CentralityResult[] = [];
  for (let i = 0; i < N; i++) {
    const note = index.notes.get(paths[i]);
    results.push({
      path: paths[i],
      title: note?.title || paths[i],
      degree: degree[i],
      betweenness: Math.round((betweenness[i] / normFactor) * 10000) / 10000,
      closeness: reachable[i] > 0
        ? Math.round((reachable[i] / closenessSum[i]) * 10000) / 10000
        : 0,
    });
  }

  // Sort by betweenness descending
  results.sort((a, b) => b.betweenness - a.betweenness);
  return results.slice(0, limit);
}

// =============================================================================
// Cycle Detection (DFS with coloring)
// =============================================================================

export interface CycleResult {
  cycle: string[];
  length: number;
}

/**
 * Detect cycles in the directed wikilink graph using DFS coloring.
 */
export function detectCycles(
  index: VaultIndex,
  maxLength: number = 10,
  limit: number = 20,
): CycleResult[] {
  const paths = Array.from(index.notes.keys());
  const N = paths.length;
  if (N === 0) return [];

  const pathIdx = new Map<string, number>();
  paths.forEach((p, i) => pathIdx.set(p, i));

  for (const note of index.notes.values()) {
    const normalized = note.title.toLowerCase();
    if (!pathIdx.has(normalized)) {
      pathIdx.set(normalized, pathIdx.get(note.path)!);
    }
  }

  const adj: number[][] = Array.from({ length: N }, () => []);
  for (const note of index.notes.values()) {
    const fromIdx = pathIdx.get(note.path);
    if (fromIdx === undefined) continue;
    for (const link of note.outlinks) {
      let toIdx = pathIdx.get(link.target);
      if (toIdx === undefined) toIdx = pathIdx.get(link.target.toLowerCase());
      if (toIdx !== undefined && toIdx !== fromIdx) {
        adj[fromIdx].push(toIdx);
      }
    }
  }

  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Uint8Array(N); // WHITE by default
  const cycles: CycleResult[] = [];
  const stack: number[] = [];

  function dfs(u: number): void {
    if (cycles.length >= limit) return;
    color[u] = GRAY;
    stack.push(u);

    for (const v of adj[u]) {
      if (cycles.length >= limit) return;
      if (color[v] === GRAY) {
        // Found cycle — extract from stack
        const cycleStart = stack.indexOf(v);
        if (cycleStart >= 0) {
          const cyclePath = stack.slice(cycleStart);
          if (cyclePath.length <= maxLength) {
            const note = (idx: number) => index.notes.get(paths[idx])?.title || paths[idx];
            cycles.push({
              cycle: cyclePath.map(note),
              length: cyclePath.length,
            });
          }
        }
      } else if (color[v] === WHITE) {
        dfs(v);
      }
    }

    stack.pop();
    color[u] = BLACK;
  }

  for (let i = 0; i < N; i++) {
    if (color[i] === WHITE && cycles.length < limit) {
      dfs(i);
    }
  }

  cycles.sort((a, b) => a.length - b.length);
  return cycles;
}
