const crypto = require('crypto');

function canonical(value) {
  if (Array.isArray(value)) {
    return value.map(canonical);
  }
  if (value && typeof value === 'object') {
    return Object.keys(value)
      .sort()
      .reduce((acc, key) => {
        acc[key] = canonical(value[key]);
        return acc;
      }, {});
  }
  return value;
}

function canonicalString(value) {
  return JSON.stringify(canonical(value));
}

function sha256(value) {
  const text = typeof value === 'string' ? value : canonicalString(value);
  return `0x${crypto.createHash('sha256').update(text, 'utf8').digest('hex')}`;
}

function pairHash(left, right) {
  return sha256({ left, right });
}

function merkleRoot(leaves) {
  if (!leaves.length) {
    return sha256({ empty: true });
  }
  let level = [...leaves];
  while (level.length > 1) {
    if (level.length % 2 === 1) {
      level.push(level[level.length - 1]);
    }
    const next = [];
    for (let i = 0; i < level.length; i += 2) {
      next.push(pairHash(level[i], level[i + 1]));
    }
    level = next;
  }
  return level[0];
}

function merkleProof(leaves, index) {
  const proof = [];
  let idx = index;
  let level = [...leaves];
  while (level.length > 1) {
    if (level.length % 2 === 1) {
      level.push(level[level.length - 1]);
    }
    const siblingIndex = idx % 2 === 0 ? idx + 1 : idx - 1;
    proof.push({
      position: idx % 2 === 0 ? 'right' : 'left',
      hash: level[siblingIndex],
    });
    idx = Math.floor(idx / 2);
    const next = [];
    for (let i = 0; i < level.length; i += 2) {
      next.push(pairHash(level[i], level[i + 1]));
    }
    level = next;
  }
  return proof;
}

function verifyMerkleProof(leaf, proof, root) {
  let current = leaf;
  for (const item of proof) {
    if (item.position === 'left') {
      current = pairHash(item.hash, current);
    } else if (item.position === 'right') {
      current = pairHash(current, item.hash);
    } else {
      return false;
    }
  }
  return current === root;
}

module.exports = {
  canonicalString,
  sha256,
  pairHash,
  merkleRoot,
  merkleProof,
  verifyMerkleProof,
};
