import { normalizeWhitespace, stableHash } from "../utils/text";

export interface RetrievedItem {
  text: string;
  score: number;
  citation?: string;
  sourceName?: string;
  confidence?: number;
}

// ── Deduplication with improved collision resistance ──────────────────────────

/**
 * Deduplicate retrieved results, keeping the highest-scored version of each
 * near-duplicate chunk.
 *
 * OPTIMIZATIONS over the original:
 *  1. Uses a Map<fp, index> for O(1) fingerprint lookup + index retrieval
 *     instead of parallel arrays with O(n) linear scan for collision resolution.
 *  2. Reduced bigram comparison threshold from 0.85 to 0.80 to reduce false
 *     negatives while still catching true duplicates.
 */

const MAX_SEEN_CACHE = 2048;

function doubleHash(input: string): string {
  return stableHash(stableHash(input));
}

function fingerprint(text: string): string {
  const normalized = normalizeWhitespace(text.slice(0, 1200).toLowerCase());
  return doubleHash(normalized);
}

function isNearDuplicate(a: string, b: string, threshold: number = 0.8): boolean {
  const normA = normalizeWhitespace(a.slice(0, 800).toLowerCase());
  const normB = normalizeWhitespace(b.slice(0, 800).toLowerCase());

  if (normA.length === 0 || normB.length === 0) return false;
  if (Math.abs(normA.length - normB.length) > Math.max(normA.length, normB.length) * 0.5) {
    return false;
  }

  const bigramsA = new Set<string>();
  for (let i = 0; i < normA.length - 1; i++) {
    bigramsA.add(normA.substring(i, i + 2));
  }

  let overlap = 0;
  for (let i = 0; i < normB.length - 1; i++) {
    const bigram = normB.substring(i, i + 2);
    if (bigramsA.has(bigram)) overlap++;
  }

  const unionSize = bigramsA.size + (normB.length - 1) - overlap;
  if (unionSize === 0) return false;

  return (overlap / unionSize) >= threshold;
}

export function dedupeResults(results: RetrievedItem[]): RetrievedItem[] {
  const kept: RetrievedItem[] = [];
  const fpToIndex = new Map<string, number>();
  const fpSet = new Set<string>();

  for (const result of results) {
    const fp = fingerprint(result.text);

    // O(1) lookup via Map — was O(n) linear scan for collision resolution.
    if (fpSet.has(fp)) {
      const idx = fpToIndex.get(fp);
      if (idx !== undefined && isNearDuplicate(kept[idx].text, result.text)) {
        if (result.score > kept[idx].score) {
          kept[idx] = result;
        }
      }
      continue;
    }

    fpSet.add(fp);
    const index = kept.length;
    fpToIndex.set(fp, index);
    kept.push(result);

    if (fpSet.size > MAX_SEEN_CACHE) {
      const oldestFp = fpToIndex.keys().next().value;
      if (oldestFp !== undefined) {
        fpToIndex.delete(oldestFp);
        fpSet.delete(oldestFp);
      }
      kept.shift();
      // Rebuild index map after shift — O(k) where k = kept.length
      for (let i = 0; i < kept.length; i++) {
        const fp = fingerprint(kept[i].text);
        fpToIndex.set(fp, i);
      }
    }
  }

  return kept;
}

import { normalizeWhitespace, stableHash } from "../utils/text";

export interface RetrievedItem {
  text: string;
  score: number;
  citation?: string;
  sourceName?: string;
  confidence?: number;
}

// ── Deduplication with improved collision resistance ──────────────────────────

/**
 * Deduplicate retrieved results, keeping the highest-scored version of each
 * near-duplicate chunk.
 *
 * OPTIMIZATIONS over the original:
 *  1. Uses a Map<fp, index> for O(1) fingerprint lookup + index retrieval
 *     instead of parallel arrays with O(n) linear scan for collision resolution.
 *  2. Reduced bigram comparison threshold from 0.85 to 0.80 to reduce false
 *     negatives while still catching true duplicates.
 */

const MAX_SEEN_CACHE = 2048;

function doubleHash(input: string): string {
  return stableHash(stableHash(input));
}

function fingerprint(text: string): string {
  const normalized = normalizeWhitespace(text.slice(0, 1200).toLowerCase());
  return doubleHash(normalized);
}

function isNearDuplicate(a: string, b: string, threshold: number = 0.8): boolean {
  const normA = normalizeWhitespace(a.slice(0, 800).toLowerCase());
  const normB = normalizeWhitespace(b.slice(0, 800).toLowerCase());

  if (normA.length === 0 || normB.length === 0) return false;
  if (Math.abs(normA.length - normB.length) > Math.max(normA.length, normB.length) * 0.5) {
    return false;
  }

  const bigramsA = new Set<string>();
  for (let i = 0; i < normA.length - 1; i++) {
    bigramsA.add(normA.substring(i, i + 2));
  }

  let overlap = 0;
  for (let i = 0; i < normB.length - 1; i++) {
    const bigram = normB.substring(i, i + 2);
    if (bigramsA.has(bigram)) overlap++;
  }

  const unionSize = bigramsA.size + (normB.length - 1) - overlap;
  if (unionSize === 0) return false;

  return (overlap / unionSize) >= threshold;
}

export function dedupeResults(results: RetrievedItem[]): RetrievedItem[] {
  const kept: RetrievedItem[] = [];
  const fpToIndex = new Map<string, number>();
  const fpSet = new Set<string>();

  for (const result of results) {
    const fp = fingerprint(result.text);

    // O(1) lookup via Map — was O(n) linear scan for collision resolution.
    if (fpSet.has(fp)) {
      const idx = fpToIndex.get(fp);
      if (idx !== undefined && isNearDuplicate(kept[idx].text, result.text)) {
        if (result.score > kept[idx].score) {
          kept[idx] = result;
        }
      }
      continue;
    }

    fpSet.add(fp);
    const index = kept.length;
    fpToIndex.set(fp, index);
    kept.push(result);

    if (fpSet.size > MAX_SEEN_CACHE) {
      const oldestFp = fpToIndex.keys().next().value;
      if (oldestFp !== undefined) {
        fpToIndex.delete(oldestFp);
        fpSet.delete(oldestFp);
      }
      kept.shift();
      // Rebuild index map after shift — O(k) where k = kept.length
      for (let i = 0; i < kept.length; i++) {
        const fp = fingerprint(kept[i].text);
        fpToIndex.set(fp, i);
      }
    }
  }

  return kept;
}