const { performance } = require("perf_hooks");
const crypto = require("crypto");

const TOTAL_SIZE = 100_000;
const RANGE_SIZE = 5_000;
const PREFIX_LENGTH = 3;
const PREFIX_THRESHOLD = 1;
const NUMBER_SIMULATIONS = 1000;
const SKIP_SIZE = Math.round(4096 * 0.3);

console.log(`
=== Configuration ===
Total numbers: ${TOTAL_SIZE.toLocaleString()}
Block size: ${RANGE_SIZE.toLocaleString()}
Prefix: ${PREFIX_LENGTH} chars (${16 ** PREFIX_LENGTH} comb.)
Skip ${SKIP_SIZE} keys per prefix match
Threshold: ${PREFIX_THRESHOLD} matches/block
Simulations: ${NUMBER_SIMULATIONS}
`);

function generateH160(data) {
  return crypto.createHash("ripemd160").update(data.toString()).digest("hex");
}

function shuffledRange(n) {
  const arr = Array.from({ length: n + 1 }, (_, i) => i);
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

function sequentialRandom(totalSize, rangeSize, targetHash) {
  const numRanges = Math.floor(totalSize / rangeSize);
  const rangeOrder = shuffledRange(numRanges - 1);
  let keyChecks = 0;

  for (const blockIndex of rangeOrder) {
    const start = blockIndex * rangeSize;
    const end = (blockIndex + 1) * rangeSize;

    for (let num = start; num < end; num++) {
      const hash = generateH160(num);
      keyChecks++;
      if (hash === targetHash) return keyChecks;
    }
  }
  return keyChecks;
}

function preciseSkipSearch(totalSize, rangeSize, prefixLength, targetHash) {
  const numRanges = Math.floor(totalSize / rangeSize);
  const rangeOrder = shuffledRange(numRanges - 1);
  let keyChecks = 0;
  const targetPrefix = targetHash.substring(0, prefixLength);
  const skippedRanges = [];

  for (const blockIndex of rangeOrder) {
    const start = blockIndex * rangeSize;
    const end = (blockIndex + 1) * rangeSize;
    let prefixCount = 0;
    let current = start;

    while (current < end && prefixCount < PREFIX_THRESHOLD) {
      const hash = generateH160(current);
      keyChecks++;

      if (hash === targetHash) return keyChecks;

      if (hash.startsWith(targetPrefix)) {
        prefixCount++;
        const skipStart = current + 1;
        const skipEnd = Math.min(current + SKIP_SIZE, end);

        if (skipStart < skipEnd) {
          skippedRanges.push({ blockIndex, start: skipStart, end: skipEnd });
        }
        current = skipEnd;
      } else {
        current++;
      }
    }

    if (prefixCount >= PREFIX_THRESHOLD) {
      skippedRanges.push({
        blockIndex,
        start: current + 1,
        end: end - 1
      });
    }
  }

  const shuffledIndices = shuffledRange(skippedRanges.length - 1);
  for (const i of shuffledIndices) {
    const { start, end } = skippedRanges[i];
    for (let num = start; num <= end; num++) {
      const hash = generateH160(num);
      keyChecks++;
      if (hash === targetHash) return keyChecks;
    }
  }

  return keyChecks;
}

async function compareMethods() {
  console.log("Warm-up...");
  for (let i = 0; i < 5; i++) generateH160(i);

  const results = {
    sequential: { checks: [], times: [] },
    precise: { checks: [], times: [] }
  };

  console.log("\nStarting comparison...");
  const startTime = performance.now();

  for (let i = 0; i < NUMBER_SIMULATIONS; i++) {
    const targetNum = Math.floor(Math.random() * TOTAL_SIZE);
    const targetHash = generateH160(targetNum);

    if (i % 2 === 0) {
      const startSeq = performance.now();
      results.sequential.checks.push(sequentialRandom(TOTAL_SIZE, RANGE_SIZE, targetHash));
      results.sequential.times.push(performance.now() - startSeq);

      const startPrecise = performance.now();
      results.precise.checks.push(preciseSkipSearch(TOTAL_SIZE, RANGE_SIZE, PREFIX_LENGTH, targetHash));
      results.precise.times.push(performance.now() - startPrecise);
    } else {
      const startPrecise = performance.now();
      results.precise.checks.push(preciseSkipSearch(TOTAL_SIZE, RANGE_SIZE, PREFIX_LENGTH, targetHash));
      results.precise.times.push(performance.now() - startPrecise);

      const startSeq = performance.now();
      results.sequential.checks.push(sequentialRandom(TOTAL_SIZE, RANGE_SIZE, targetHash));
      results.sequential.times.push(performance.now() - startSeq);
    }

    if ((i + 1) % 10 === 0) console.log(`Test ${i + 1}/${NUMBER_SIMULATIONS}`);
  }

  const calculateStats = (data) => {
    const avg = data.reduce((a, b) => a + b, 0) / data.length;
    const squaredDiffs = data.map(x => Math.pow(x - avg, 2));
    const variance = squaredDiffs.reduce((a, b) => a + b, 0) / data.length;
    const stdDev = Math.sqrt(variance);
    return { avg, min: Math.min(...data), max: Math.max(...data), stdDev };
  };

  const seqStats = calculateStats(results.sequential.checks);
  const preciseStats = calculateStats(results.precise.checks);
  const seqTime = results.sequential.times.reduce((a, b) => a + b, 0) / NUMBER_SIMULATIONS;
  const preciseTime = results.precise.times.reduce((a, b) => a + b, 0) / NUMBER_SIMULATIONS;

  const improvement = ((seqStats.avg - preciseStats.avg) / seqStats.avg * 100).toFixed(2);
  const timeImprovement = ((seqTime - preciseTime) / seqTime * 100).toFixed(2);

  console.log(`
=== FINAL RESULTS ===

Random Sequential:
- Average comparisons: ${seqStats.avg.toFixed(0)}
- Average time: ${(seqTime / 1000).toFixed(3)}s
- Range: [${seqStats.min} - ${seqStats.max}]

Prefixes Search (${SKIP_SIZE} keys skip + threshold ${PREFIX_THRESHOLD}):
- Average comparisons: ${preciseStats.avg.toFixed(0)}
- Average time: ${(preciseTime / 1000).toFixed(3)}s
- Range: [${preciseStats.min} - ${preciseStats.max}]

=== CONCLUSION ===
The ${preciseStats.avg < seqStats.avg ? 'PREFIXES' : 'RANDOM+SEQUENTIAL'} method is more efficient:
- ${improvement}% fewer comparisons
- ${timeImprovement}% faster
`);

  console.log(`Total time: ${((performance.now() - startTime)/1000).toFixed(1)} seconds`);
}

compareMethods();