import { isHex, size } from '../../index.js'
import type { Hex } from '../../types/misc.js'
import { concat } from '../../utils/data/concat.js'
import { keccak256 } from '../../utils/hash/keccak256.js'

/**
 * Verifies the integrity of a merkle tree structure.
 *
 * @param tree - The merkle tree to verify, represented as an array of levels where each level is a Record mapping node indices to their hash values
 * @returns true if the tree structure is valid, false otherwise
 *
 * @example
 * const tree = [
 *   { 0: '0x...', 1: '0x...' },  // Level 0 (leaves)
 *   { 0: '0x...' }                // Level 1 (root)
 * ]
 * const isValid = verifyMerkleTree(tree)
 */
export function verifyMerkleTree(tree: Record<number, Hex>[]): boolean {
  if (tree.length > 1) {
    for (let level = 0; level < tree.length - 1; level++) {
      const currentLevel = tree[level]
      const nextLevel = tree[level + 1]

      if (Object.keys(currentLevel).length % 2 !== 0) {
        return false
      }

      for (const hash of Object.values(currentLevel)) {
        if (!isHex(hash) || size(hash) !== 32) {
          return false
        }
      }

      for (const hash of Object.values(nextLevel)) {
        if (!isHex(hash) || size(hash) !== 32) {
          return false
        }
      }

      const childIndices = Object.keys(currentLevel)
        .map(Number)
        .sort((a, b) => a - b)

      for (let i = 0; i < childIndices.length; i += 2) {
        const leftIndex = childIndices[i]
        const rightIndex = childIndices[i + 1]

        const leftChild = currentLevel[leftIndex]
        const rightChild = currentLevel[rightIndex]

        const parentIndex = leftIndex >> 1

        const parent = nextLevel[parentIndex]
        if (!parent) {
          return false
        }

        const calculatedHash = keccak256(concat([leftChild, rightChild]))

        if (calculatedHash !== parent) {
          return false
        }
      }
    }
  } else if (tree.length === 0) {
    return true
  }

  const root = tree[tree.length - 1]
  if (Object.keys(root).length !== 1) {
    return false
  }
  if (!isHex(root[0]) || size(root[0]) !== 32) {
    return false
  }

  return true
}